并行运行N皇后问题的球拍代码

Question

我使用以下简单代码来解决n-queens问题:

#lang racket

; following returns true if queens are on diagonals:  
(define (check-diagonals bd) 
  (for/or ((r1 (length bd)))
    (for/or ((r2 (range (add1 r1) (length bd))))
      (= (abs (- r1 r2))
         (abs(- (list-ref bd r1)
                (list-ref bd r2)))))))

; set board size: 
(define N 8)
; start searching: 
(for ((brd (in-permutations (range N))))
  (when (not (check-diagonals brd))
    (displayln brd)))

它工作正常但需要很长时间in-permutations才能获得更大的N值.它使用函数来获得排列流.我还看到它仅使用25%的CPU功率(正在使用4个核中的1个).如何修改此代码,以便它使用来自in-permutations流的排列并行测试并使用所有4个cpu内核？谢谢你的帮助.

编辑:check-diagonals评论中建议的修改功能.旧代码是:

(define (check-diagonals bd) 
  (define res #f)
  (for ((r1 (length bd))
        #:break res)
    (for ((r2 (range (add1 r1) (length bd)))
          #:break res)
      (when (= (abs (- r1 r2))
               (abs(- (list-ref bd r1)
                      (list-ref bd r2))))
        (set! res #t))))
  res)

Answer 1

首先,在进行任何并行化之前,您可以相当多地改进原始程序.您可以进行以下更改:

1. 使用for/or而不是改变绑定和使用#:break.
2. 使用for*/or而不是嵌套for/or在彼此内部的循环.
3. in-range尽可能使用以确保for循环在扩展时专用于简单循环.
4. 在相关位置使用方括号而不是括号,以使您的代码对Racketeers更具可读性(特别是因为此代码不是远程可移植的Scheme,无论如何).

通过这些更改,代码如下所示:

#lang racket

; following returns true if queens are on diagonals:  
(define (check-diagonals bd) 
  (for*/or ([r1 (in-range (length bd))]
            [r2 (in-range (add1 r1) (length bd))])
    (= (abs (- r1 r2))
       (abs (- (list-ref bd r1)
               (list-ref bd r2))))))

; set board size: 
(define N 8)
; start searching: 
(for ([brd (in-permutations (range N))])
  (unless (check-diagonals brd)
    (displayln brd)))

现在我们可以转向并行化.事情就是这样:并行化的事情往往很棘手.并行调度工作往往会产生开销,而且开销可能比您想象的更频繁地超过收益.我花了很长时间尝试并行化这段代码,最终,我无法生成比原始顺序程序运行得更快的程序.

不过,你可能对我的所作所为感兴趣.也许你(或其他人)能够提出比我更好的东西.这里工作的相关工具是Racket的未来,专为细粒度并行而设计.期货是相当严格的,因为Racket的运行时设计方式(基本上是出于历史原因的方式),因此不仅任何东西都可以并行化,并且相当多的操作可能导致期货被阻止.幸运的是,Racket还附带了Future Visualizer,这是一个用于理解期货运行时行为的图形工具.

在我们开始之前,我运行N = 11的程序的顺序版本并记录结果.

$ time racket n-queens.rkt
[program output elided]
       14.44 real        13.92 user         0.32 sys

我将使用这些数字作为本答案其余部分的比较点.

首先,我们可以尝试用一个并行运行所有主体的主for循环替换for/asnyc它.这是一个非常简单的转换,它给我们留下了以下循环:

(for/async ([brd (in-permutations (range N))])
  (unless (check-diagonals brd)
    (displayln brd)))

但是,进行这种改变并不能提高性能; 事实上,它显着减少了它.仅使用N = 9运行此版本需要约6.5秒; N = 10,需要~55.

然而,这并不令人惊讶.使用期货可视化器运行代码(使用N = 7)表示displayln未来不合法,阻止任何并行执行实际发生.据推测,我们可以通过创建仅计算结果的期货来解决这个问题,然后按顺序打印它们:

(define results-futures
  (for/list ([brd (in-permutations (range N))])
    (future (? () (cons (check-diagonals brd) brd)))))

(for ([result-future (in-list results-futures)])
  (let ([result (touch result-future)])
    (unless (car result)
      (displayln (cdr result)))))

通过这种改变,我们可以在天真的尝试中获得一个小的加速for/async,但是我们仍然比顺序版本慢得多.现在,N = 9,需要~4.58秒,N = 10,需要~44.

看看这个程序的期货可视化器(再次,N = 7),现在没有块,但有一些同步(在jit_on_demand和分配内存).然而,经过一段时间的jitting,执行似乎开始了,它实际上并行运行了很多未来!

然而,经过一段时间后,并行执行似乎已经失去了动力,事情似乎开始相对顺序地再次运行.

我真的不知道发生了什么事情就到这里,但我想也许这是因为有些期货是太微小.调度成千上万的期货(或者,在N = 10,数百万的情况下)的开销远远超过期货中正在进行的工作的实际运行时间.幸运的是,这似乎可以通过将工作分组为块来解决,这是一个相对可行的使用in-slice:

(define results-futures
  (for/list ([brds (in-slice 10000 (in-permutations (range N)))])
    (future
     (? ()
       (for/list ([brd (in-list brds)])
         (cons (check-diagonals brd) brd))))))

(for* ([results-future (in-list results-futures)]
       [result (in-list (touch results-future))])
  (unless (car result)
    (displayln (cdr result))))

似乎我的怀疑是正确的,因为这种变化有很大帮助.现在,对于N = 10,运行该程序的并行版本仅需要约3.9秒,比使用期货的先前版本加速超过10倍.然而,不幸的是,这仍然比完全顺序版本慢,仅需要约1.4秒.将N增加到11会使并行版本需要大约44秒,如果提供的块大小in-slice增加到100,000,则需要更长时间,大约55秒.

看看该版本程序的未来可视化器,N = 11,块大小为1,000,000,我看到似乎有一些扩展并行性的时期,但是期货在内存分配方面受到很大阻碍:

这是有道理的,因为现在每个未来都在处理更多的工作,但这意味着期货不断同步,可能导致我所看到的显着的性能开销.

在这一点上,我不确定还有很多我知道如何调整以改善未来的性能.我试图通过使用向量而不是列表和专门的fixnum操作来减少分配,但无论出于何种原因,这似乎完全破坏了并行性.我想也许那是因为期货从来没有同时开始,所以我用未来的未来取代了未来,但结果让我感到困惑,我真的不明白他们的意思.

我的结论是,对于这个问题,Racket的期货太脆弱了,尽管它可能很简单.我放弃.

现在,作为一个小小的奖励,我决定尝试在Haskell中模拟相同的事情,因为Haskell有一个特别强大的故事,用于细粒度的并行评估.如果我无法在Haskell中获得性能提升,我也不希望能够在Racket中获得一个.

我会跳过关于我尝试的不同事情的所有细节,但最终,我最终得到了以下程序:

import Data.List (permutations)
import Data.Maybe (catMaybes)

checkDiagonals :: [Int] -> Bool
checkDiagonals bd =
  or $ flip map [0 .. length bd - 1] $ \r1 ->
    or $ flip map [r1 + 1 .. length bd - 1] $ \r2 ->
      abs (r1 - r2) == abs ((bd !! r1) - (bd !! r2))

n :: Int
n = 11

main :: IO ()
main =
  let results = flip map (permutations [0 .. n-1]) $ \brd ->
        if checkDiagonals brd then Nothing else Just brd
  in mapM_ print (catMaybes results)

我能够使用Control.Parallel.Strategies库轻松添加一些并行性.我在main函数中添加了一行,引入了一些并行评估:

import Control.Parallel.Strategies
import Data.List.Split (chunksOf)

main :: IO ()
main =
  let results =
        concat . withStrategy (parBuffer 10 rdeepseq) . chunksOf 100 $
        flip map (permutations [0 .. n-1]) $ \brd ->
          if checkDiagonals brd then Nothing else Just brd
  in mapM_ print (catMaybes results)

花了一些时间来确定正确的块和滚动缓冲区大小,但是这些值比原始的顺序程序提供了一致的30-40%的加速.

现在,显然,Haskell的运行时比Racket更适合并行编程,所以这种比较很难公平.但它帮助我亲眼看到,尽管我拥有4个核心(8个超线程),我甚至无法获得50%的加速.记在脑子里.

正如Matthias在邮件列表中所说,我在这个主题上写道:

关于并行性的一般警告.不久前,常春藤联盟学校的CS人员研究了不同用途和应用程序中并行性的使用.目标是找出关于并行性影响人们的"大肆宣传".我的回忆是,他们发现了近20个项目,其中教授(CE,EE,CS,Bio,Econ等)告诉他们的研究生/博士使用并行性来更快地运行程序.他们检查了所有这些,对于N - 1或2,一旦删除了并行性,项目运行得更快.明显更快.

人们经常低估并行性引入的通信成本.

小心不要犯同样的错误.