Racket代码在N皇后问题中的并行运行

Question

我正在使用以下简单代码解决n皇后问题：

#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 个）。如何修改此代码以使用来自 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)

- rnso

---

欢迎回来，好久不见。这并不能回答你的问题，但是你的代码仍然有点令人困惑的命令式。如果你在check-diagonals中只使用for/or而不是命令式的for，你可以消除突变的res绑定、set!的使用和#:break子句。 - Alexis King

好建议。谢谢。我已经修改了上面的代码。关于主要问题呢？ - rnso

我也有一个关于同样问题的问题在另一个论坛上：https://codereview.stackexchange.com/questions/175297/solution-to-n-queens-problem-in-racket - rnso

我曾经花了一些时间尝试使用 futures 来实现某些功能，但是我尝试的所有方法最终都比串行解决方案慢，即使对于大量的 N 值也是如此。也许可以通过使用 places 来加速，但我不确定。我还没有尝试过。 - Alexis King

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的futures，专为细粒度并行ism而设计。由于Racket的运行时设计方式（基本上是由于历史原因），因此Future相当受限制，因此并非所有操作都可以并行化，而且相当多的操作可能会导致Future阻塞。幸运的是，Racket还附带了Future Visualizer，这是一个用于理解Future运行时行为的图形化工具。

在我们开始之前，我使用N = 11运行了程序的顺序版本，并记录了结果。

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

我会把这些数字作为本答案的比较基准。

首先，我们可以尝试用for/async替换主要的for循环，它可以并行运行所有的操作。这是一个非常简单的转换，这样我们就得到了以下循环：

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

然而，做出这种改变并不能提高性能；事实上，它显著降低了性能。仅仅运行N=9版本就需要大约6.5秒钟；而N=10时，则需要大约55秒钟。

然而，这并不太令人惊讶。使用futures visualizer（使用N=7）运行代码表明，从future中调用displayln是不合法的，阻止任何并行执行的实际发生。我们可以通过创建仅计算结果的futures，然后串行打印它们来修复这个问题。

(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秒。

查看此程序的futures可视化器（再次，N=7），现在没有阻塞，但有一些同步（在jit_on_demand和分配内存时）。然而，在花费一些时间进行JIT编译后，执行似乎开始运行，并且实际上可以并行运行许多futures！

然而，经过一段时间的运行，平行执行似乎开始失去动力，事情似乎又开始相对顺序地运行。

我不太确定这里到底发生了什么，但我认为可能是因为一些future太小了。似乎有可能调度成千上万（当N=10时，甚至是数百万）个future的开销远远超过了实际在future中完成的工作运行时间。幸运的是，这似乎可以通过将工作分组成块来解决，使用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))))

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

查看具有N = 11和块大小为1,000,000的该版本程序的未来可视化器，我发现似乎存在一些持续的并行期间，但是futures在内存分配方面经常被阻塞：

这是有道理的，因为现在每个future都处理更多的工作，但这意味着futures不断同步，很可能会导致我看到的显著性能开销。

目前，我不确定还有什么其他方法可以调整来提高future的性能。我尝试通过使用向量而不是列表和专门的fixnum操作来减少分配，但出于某种原因，那似乎完全破坏了并行性。我认为这可能是因为futures从未并行启动，所以我用would-be-future替换了future，但结果让我感到困惑，我真的不明白它们的含义。

我的结论是，Racket的futures对于这个问题来说太脆弱了，尽管它可能很简单。我放弃了。

---

现在，作为一个小小的奖励，我决定尝试在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在我写的这个主题的邮件列表中所指出的那样：

总体上，对并行性要保持谨慎。不久前，常春藤联盟学校的某人研究了不同用途和应用程序中并行性的使用。目标是找出“并行性”对人们的影响有多大。我记得他们发现了近20个项目，其中教授们（在CE、EE、CS、Bio、Econ等领域）告诉他们的研究生/博士使用并行性来加快程序运行速度。他们检查了所有项目，对于N-1或2，一旦去除了并行性，项目的运行速度就会更快。显著更快。

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

小心不要犯同样的错误。

- Alexis King

---

我只能说，非常好的回答！这一定是Stackoverflow中最好的之一。谢谢。 - rnso