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來說是一個很大的改進。第二個結論是，緩衝區的大小應儘可能小，但要大於核心數量。但最好的是，我既沒有溢出也沒有失去火花。所有都成功轉換。

來源

2015-04-23 Hennes

我猜* *看的地方是'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]]

來源

2015-04-23 07:35:49

看起來不錯。我對這兩個版本進行了一些測試，發現運行時間沒有區別。使用四個線程（-N4）只需要程序的一半時間，使用四個以上的線程可以減少運行時間，而不會進一步增加。當我監視taks窗口時，我可以看到，在開始時，程序完全消耗了16個內核中的四個。但是，儘管我沒有IO操作，但CPU使用率僅下降到5％。奇怪....似乎我必須安裝threadscope來進一步分析.... – Hennes

如果'rdeepseq'與'rseq'沒有什麼區別，那麼很可能'tryCombination'在確定某個東西是一個解決方案。 –

我大幅減少了組合參數的集合（僅在約一分鐘內得到結果），因此無法解決問題。所以我清楚地看到它如何使用所有內核。但是現在我使用了threadscope並計算出19000個火花是生產的，但只處理了8000個火花。這就是爲什麼只使用所有核心四秒鐘，之後只有主核心在剩下的9000個火花中處於活動狀態的原因。似乎這種並行化還有一些優化的潛力。 – Hennes

Haskell中是否存在並行查找？

回答

相關問題