N-Queens 问题的 Racket 代码的并行 运行
Parallel running of Racket code for N-Queens problem
我正在使用以下简单代码来解决 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 函数来获取排列流。我还看到它只使用了 cpu 功率的 25%（使用了 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)
首先，在并行化任何东西之前，您可以对原始程序进行相当多的改进。以下是您可以进行的一些更改：
- 使用
for/or 而不是改变绑定并使用 #:break。
- 使用
for*/or 而不是彼此嵌套 for/or 循环。
- 尽可能使用
in-range 以确保 for 循环在扩展时专用于简单循环。
- 在相关位置使用方括号代替圆括号，使你的代码对 Racketeer 更具可读性（特别是因为这段代码不是远程可移植的 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, designed for fine-grained parallelism. Futures are fairly restrictive due to the way Racket’s runtime is designed (which is essentially the way it is for historical reasons), so not just anything can be parallelized, and a fairly large number of operations can cause futures to block. Fortunately, Racket also ships with the Future Visualizer，这是一种用于理解 运行 期货时间行为的图形工具。
在我们开始之前，我运行 N=11 的程序的顺序版本并记录了结果。
$ time racket n-queens.rkt
[program output elided]
14.44 real 13.92 user 0.32 sys
我将使用这些数字作为此答案剩余部分的比较点。
首先，我们可以尝试用 for/asnyc 替换主 for 循环，运行 它的所有主体都是并行的。这是一个非常简单的 t运行 形式，它给我们留下了以下循环：
(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，执行似乎开始了，实际上 运行 有很多并行的 futures！
然而，经过一点点之后，并行执行似乎 运行 失去了动力，事情似乎再次开始 运行ning 相对顺序。
我不太确定这里发生了什么，但我认为可能是因为某些期货太 小 。安排数千个 futures（或者，在 N=10 的情况下，数百万）的开销似乎远远超过在 futures 中完成工作的实际 运行 时间。幸运的是，这似乎可以通过将工作分成块来解决，使用 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 秒，比以前使用 futures 的版本加速了 10 倍以上。然而，不幸的是，这仍然比完全顺序的版本 慢 ，后者只需要大约 1.4 秒。将 N 增加到 11 会使并行版本花费约 44 秒，如果提供给 in-slice 的块大小增加到 100,000，则需要更长的时间，约 55 秒。
查看该程序版本的未来可视化器，N=11，块大小为 1,000,000，我发现似乎有一些扩展并行性的时期，但未来被阻塞了很多关于内存分配：
这是有道理的，因为现在每个 future 正在处理更多的工作，但这意味着 futures 不断同步，可能导致我看到的显着性能开销。
在这一点上，我不确定还有多少我知道如何调整以提高未来的表现。我尝试通过使用向量而不是列表和专门的 fixnum 操作来减少分配，但无论出于何种原因，这似乎完全破坏了并行性。我想也许是因为futures从来没有并行启动过，所以我把future换成了would-be-future，但是结果让我很困惑，我也不太明白他们的意思。
我的结论是，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 库轻松添加一些并行性。我在引入一些并行计算的主函数中添加了一行：
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 的 运行time 比 Racket 的更适合并行编程，所以这种比较是不公平的。但这帮助我亲眼看到，尽管有 4 个内核（8 个带有超线程）可供我使用，但我什至无法获得 50% 的加速。请记住这一点。
如Matthias noted in a mailing list thread I wrote on this subject:
A word of caution on parallelism in general. Not too long ago, someone in CS at an Ivy League school studied the use of parallelism across different uses and applications. The goal was to find out how much the ‘hype’ about parallelism affected people. My recollection is that they found close to 20 projects where professors (in CE, EE, CS, Bio, Econ, etc) told their grad students/PhDs to use parallelism to run programs faster. They checked all of them and for N - 1 or 2, the projects ran faster once the parallelism was removed. Significantly faster.
People routinely underestimate the communication cost that parallelism introduces.
注意不要重蹈覆辙
我正在使用以下简单代码来解决 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 函数来获取排列流。我还看到它只使用了 cpu 功率的 25%（使用了 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)
首先，在并行化任何东西之前，您可以对原始程序进行相当多的改进。以下是您可以进行的一些更改：
- 使用
for/or而不是改变绑定并使用#:break。 - 使用
for*/or而不是彼此嵌套for/or循环。 - 尽可能使用
in-range以确保for循环在扩展时专用于简单循环。 - 在相关位置使用方括号代替圆括号，使你的代码对 Racketeer 更具可读性（特别是因为这段代码不是远程可移植的 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, designed for fine-grained parallelism. Futures are fairly restrictive due to the way Racket’s runtime is designed (which is essentially the way it is for historical reasons), so not just anything can be parallelized, and a fairly large number of operations can cause futures to block. Fortunately, Racket also ships with the Future Visualizer，这是一种用于理解 运行 期货时间行为的图形工具。
在我们开始之前，我运行 N=11 的程序的顺序版本并记录了结果。
$ time racket n-queens.rkt
[program output elided]
14.44 real 13.92 user 0.32 sys
我将使用这些数字作为此答案剩余部分的比较点。
首先，我们可以尝试用 for/asnyc 替换主 for 循环，运行 它的所有主体都是并行的。这是一个非常简单的 t运行 形式，它给我们留下了以下循环：
(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，执行似乎开始了，实际上 运行 有很多并行的 futures！
然而，经过一点点之后，并行执行似乎 运行 失去了动力，事情似乎再次开始 运行ning 相对顺序。
我不太确定这里发生了什么，但我认为可能是因为某些期货太 小 。安排数千个 futures（或者，在 N=10 的情况下，数百万）的开销似乎远远超过在 futures 中完成工作的实际 运行 时间。幸运的是，这似乎可以通过将工作分成块来解决，使用 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 秒，比以前使用 futures 的版本加速了 10 倍以上。然而，不幸的是，这仍然比完全顺序的版本 慢 ，后者只需要大约 1.4 秒。将 N 增加到 11 会使并行版本花费约 44 秒，如果提供给 in-slice 的块大小增加到 100,000，则需要更长的时间，约 55 秒。
查看该程序版本的未来可视化器，N=11，块大小为 1,000,000，我发现似乎有一些扩展并行性的时期，但未来被阻塞了很多关于内存分配：
这是有道理的，因为现在每个 future 正在处理更多的工作，但这意味着 futures 不断同步，可能导致我看到的显着性能开销。
在这一点上，我不确定还有多少我知道如何调整以提高未来的表现。我尝试通过使用向量而不是列表和专门的 fixnum 操作来减少分配，但无论出于何种原因，这似乎完全破坏了并行性。我想也许是因为futures从来没有并行启动过，所以我把future换成了would-be-future，但是结果让我很困惑，我也不太明白他们的意思。
我的结论是，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 库轻松添加一些并行性。我在引入一些并行计算的主函数中添加了一行：
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 的 运行time 比 Racket 的更适合并行编程，所以这种比较是不公平的。但这帮助我亲眼看到，尽管有 4 个内核（8 个带有超线程）可供我使用，但我什至无法获得 50% 的加速。请记住这一点。
如Matthias noted in a mailing list thread I wrote on this subject:
A word of caution on parallelism in general. Not too long ago, someone in CS at an Ivy League school studied the use of parallelism across different uses and applications. The goal was to find out how much the ‘hype’ about parallelism affected people. My recollection is that they found close to 20 projects where professors (in CE, EE, CS, Bio, Econ, etc) told their grad students/PhDs to use parallelism to run programs faster. They checked all of them and for N - 1 or 2, the projects ran faster once the parallelism was removed. Significantly faster.
People routinely underestimate the communication cost that parallelism introduces.
注意不要重蹈覆辙