Haskell中是否存在并行查找？

问题描述：

我有一些我喜欢在Haskell中解决的蛮力问题。我的机器有16个内核，所以我想加快我目前的算法。Haskell中是否存在并行查找？

我有一个方法“tryCombination”，它返回一个Just（String）或Nothing。我的循环如下所示：

findSolution = find (isJust) [tryCombination a1 a2 a3 n z p | 
           a1 <- [600..700], 
           a2 <- [600..700], 
           a3 <- [600..700], 
           n <- [1..100], 
           ....

我知道有一个特殊的parMap来并行化映射函数。 mapFind可能会很棘手，因为它不可预测，如果一个线程真的发现第一个发生。但是有没有像mapAny加快搜索？

编辑：

我改写使用 “withStrategy（parList RSEQ）” 片段的代码。状态报告如下：

38,929,334,968 bytes allocated in the heap 
2,215,280,048 bytes copied during GC 
    3,505,624 bytes maximum residency (795 sample(s)) 
     202,696 bytes maximum slop 
      15 MB total memory in use (0 MB lost due to fragmentation) 

            Tot time (elapsed) Avg pause Max pause 
Gen 0  44922 colls, 44922 par 37.33s 8.34s  0.0002s 0.0470s 
Gen 1  795 colls, 794 par 7.58s 1.43s  0.0018s 0.0466s 

Parallel GC work balance: 4.36% (serial 0%, perfect 100%) 

TASKS: 10 (1 bound, 9 peak workers (9 total), using -N8) 

SPARKS: 17576 (8198 converted, 9378 overflowed, 0 dud, 0 GC'd, 0 fizzled) 

INIT time 0.00s ( 0.00s elapsed) 
MUT  time 81.79s (36.37s elapsed) 
GC  time 44.91s ( 9.77s elapsed) 
EXIT time 0.00s ( 0.00s elapsed) 
Total time 126.72s (46.14s elapsed) 

Alloc rate 475,959,220 bytes per MUT second 

Productivity 64.6% of total user, 177.3% of total elapsed 

gc_alloc_block_sync: 834851 
whitehole_spin: 0 
gen[0].sync: 10 
gen[1].sync: 3724

正如我已经提到的（见我的意见），所有的内核正在为只有三个秒（德恩所有的火花被处理）。接下来的30年代所有的工作都是由一个核心完成的。我怎样才能优化更多？

一些更多的编辑：

我现在给 “withStrategy（parBuffer 10 rdeepseq）” 一试，并用不同的缓冲区大小摆弄周围：

Buffersize GC work Balance  MUT  GC 
     10    50%  11,69s 0,94s 
     100    47%  12,31s 1,67s 
     500    40%  11,5 s 1,35s 
    5000    21%  11,47s 2,25s

首先，我可以说，这这对于没有多线程的59s来说是一个很大的改进。第二个结论是，缓冲区的大小应尽可能小，但要大于核心数量。但最好的是，我既没有溢出也没有失去火花。所有都成功转换。

我猜* *看的地方是'unamb'包。 'unambs'功能看起来很有前途。 – dfeuer

听起来很有趣，但我无法想象如何在这个特殊情况下应用unamb。你手边有片段吗？ – Hennes

不是。从未使用任何它。 – dfeuer

答

取决于tryCombination的lazyness和所需的并行化，其中一个可能会做你想要什么：

import Control.Parallel.Strategies 
findSolution = 
    find (isJust) $ 
    withStrategy (parList rseq) $ 
    [ tryCombination a1 a2 a3 n z p 
    | a1 <- [600..700] 
    , a2 <- [600..700] 
    , a3 <- [600..700] 
    , n <- [1..100]]

这paralleizes通过tryCombination完成的工作要弄清楚它是否是Just或Nothing，但不是Just中的实际结果。

如果有被利用没有这样的lazyness和结果类型简单，它可能会更好地工作，写

findSolution = 
    find (isJust) $ 
    withStrategy (parList rdeepseq) $ 
    [ tryCombination a1 a2 a3 n z p 
    | a1 <- [600..700] 
    , a2 <- [600..700] 
    , a3 <- [600..700] 
    , n <- [1..100]]

看起来不错。我对这两个版本进行了一些测试，发现运行时间没有区别。使用四个线程（-N4）只需要程序的一半时间，使用四个以上的线程可以减少运行时间，而不会进一步增加。当我监视taks窗口时，我可以看到，在开始时，程序完全消耗了16个内核中的四个。但是，尽管我没有IO操作，但CPU使用率仅下降到5％。奇怪....似乎我必须安装threadscope来进一步分析.... – Hennes

如果'rdeepseq'与'rseq'没有什么区别，那么很可能'tryCombination'在确定某个东西是一个解决方案。 –

我大幅减少了组合参数的集合（仅在约一分钟内得到结果），因此无法解决问题。所以我清楚地看到它如何使用所有内核。但是现在我使用了threadscope并计算出19000个火花是生产的，但只处理了8000个火花。这就是为什么只使用所有核心四秒钟，之后只有主核心在剩下的9000个火花中处于活动状态的原因。似乎这种并行化还有一些优化的潜力。 – Hennes

Haskell中是否存在并行查找？

相关推荐