concurrency - N皇后问题的Racket代码并行运行

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)))

它可以正常工作，但是对于较大的N值会花费很长时间。它使用 in-permutations函数来获取排列流。我还看到它仅使用25％的cpu功耗（正在使用4个内核中的1个）。我如何修改此代码，以便它使用排列内流中排列的并行测试并使用所有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

首先，甚至在并行化任何东西之前，您都可以对原始程序进行很多改进。您可以进行以下更改：

使用for/or而不是突变绑定并使用#:break。
使用for*/or而不是在彼此内部嵌套for/or循环。
尽可能使用in-range来确保for循环在扩展时专门用于简单循环。
在相关位置使用方括号而不是括号，以使代码更容易被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的 futures，专为细粒度的并行性而设计。由于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。
但是，这并不奇怪。使用Futures可视化工具运行代码（使用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上并分配内存）。但是，经过一段时间的调整后，执行似乎开始进行了，实际上它并行运行许多期货！

然而，经过一小会儿之后，并行执行似乎就没劲了，事情似乎又开始相对顺序地运行了。

我不太确定这是怎么回事，但我想也许是因为某些期货太小了。调度数千个期货（或在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操作来减少分配，但是无论出于何种原因，这似乎完全破坏了并行性。我以为那也许是因为期货永远不会平行启动，所以我用未来的期货代替了期货，但结果令我感到困惑，我并不真正了解它们的含义。
我的结论是，球拍的期货太脆弱了，无法解决这个问题，尽管可能如此简单。我放弃。

现在，作为一点好处，我决定尝试在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库轻松添加一些并行性。我在主要功能中添加了一行，引入了一些并行评估：

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 noted in a mailing list thread I wrote on this subject：

一般而言，对并行性要谨慎。不久之前，一个常春藤盟校的CS中的某人研究了并行性在不同用途和应用中的使用。目的是找出有关并行性的“炒作”对人们的影响。我的回忆是，他们发现了将近20个项目，其中教授（CE，EE，CS，生物，经济等）告诉他们的研究生/博士学位使用并行性来更快地运行程序。他们检查了所有这些，并且对于N-1或2，一旦删除了并行性，项目的运行速度就会更快。明显更快。
人们通常会低估并行性带来的通信成本。

注意不要犯同样的错误。