如何在Haskell中使用策略編寫並行約簡？

在高性能計算中，通常使用「並行減少」來計算總和，產品等，該「並行減少」需要時間（給定足夠的並行性），並且在O（日誌n）時間內完成。在Haskell中，我們通常使用摺疊來進行這種計算，但評估時間在列表長度上總是線性的。如何在Haskell中使用策略編寫並行約簡？

數據並行Haskell有一些內置的，但在列表的通用框架呢？我們可以用Control.Parallel.Strategies嗎？

因此，假設f是關聯的，我們怎麼寫

parFold :: (a -> a -> a) -> [a] -> a

使parFold f xs只需要在length xs時間對數？

來源

2010-10-26 Chad Scherrer

正如人們已經注意到的，list是遞歸併行分割的一個糟糕的數據結構。你需要某種二叉樹/繩索結構，如Fortress語言：http://labs.oracle.com/projects/plrg/Publications/ICFPAugust2009Steele.pdf – sclv 2010-10-27 00:56:42

我不認爲列表是正確的數據類型。因爲它只是一個鏈表，所以必須按順序訪問數據。雖然您可以並行評估這些項目，但在減少步驟中不會獲得太多收益。如果你真的需要一個名單，我認爲最好的功能將只是

parFold f = foldl1' f . withStrategy (parList rseq)

也許

parFold f = foldl1' f . withStrategy (parBuffer 5 rseq)

如果還原步驟是複雜的，你可以通過細分列表這樣得到的增益：

parReduce f = foldl' f mempty . reducedList . chunkList . withStrategy (parList rseq) 
where 
    chunkList list = let (l,ls) = splitAt 1000 list in l : chunkList ls 
    reducedList = parMap rseq (foldl' f mempty)

我已經採取了假設你的數據的自由是mempty一個Monoid，如果無法做到這一點，你可以用自己的空類型更換mempty，或者更糟的情況下，使用foldl1'。

從這裏使用Control.Parallel.Strategies有兩個運營商。 parList並行評估列表中的所有項目。之後，chunkList將列表分成1000個元素的塊。然後，這些塊中的每一塊隨後由parMap並行減少。

您也可以嘗試

parReduce2 f = foldl' f mempty . reducedList . chunkList 
where 
    chunkList list = let (l,ls) = splitAt 1000 list in l : chunkList ls 
    reducedList = parMap rseq (foldl' f mempty)

根據工作究竟是如何分佈的，其中之一可能比其他人更有效。

如果您可以使用對索引有很好支持的數據結構（數組，矢量，映射等），那麼您可以對縮減步驟執行二進制細分，總體來說可能會更好。

來源

2010-10-26 22:32:01

謝謝，約翰。我喜歡使用foldl'over chunk的想法。但是在每個塊減少之後，外部摺疊'是連續的，並且其輸入可能非常大。什麼是表達遞歸的最佳方式？輸入可能是也可能不是列表，但是這應該可以使用策略來表達。 – 2010-10-27 18:11:19

'reducedList'中的'parMap'函數將並行評估所有塊。但是，如果您的輸入太大以至於您不想一次將所有內容加載到內存中，那麼您可以使用laziness和parBuffer。我在'parBuffer'方面取得了非常好的成績，因爲它可以讓你利用並行和懶惰。我認爲它會工作，如果你使用'reducedList = withStrategy（parBuffer 10 rseq）。地圖（foldl'f mempty）'。我認爲這比列表的遞歸更好，因爲你避免了多次遍歷。 – 2010-10-27 19:01:32

這似乎是一個良好的開端：

parFold :: (a -> a -> a) -> [a] -> a 
parFold f = go 
    where 
    strategy = parList rseq 

    go [x] = x 
    go xs = go (reduce xs `using` strategy) 

    reduce (x:y:xs) = f x y : reduce xs 
    reduce list  = list -- empty or singleton list

它的工作原理，但其並行是沒有那麼大。用parListChunks 1000之類的東西代替parList會有所幫助，但在8核機器上加速仍然限制在1.5x以下。

來源

2010-10-26 21:42:51

不知道你的parFold函數應該做什麼。如果這是一個平行版本的foldr或foldl，我認爲它的定義是錯誤的。

parFold :: (a -> a -> a) -> [a] -> a 

// fold right in haskell (takes 3 arguments) 
foldr :: (a -> b -> b) -> b -> [a] -> b

摺疊將相同的功能應用於列表的每個元素並累積每個應用程序的結果。使用它的一個並行版本，我想，將要求功能應用程序的元素並行完成 - 有點像parList做什麼。

par_foldr :: (NFData a, NFData b) => (a -> b -> b) -> b -> [a] -> b 
    par_foldr f z [] = z 
    par_foldr f z (x:xs) = res `using` \ _ -> rseq x' `par` rdeepseq res 
         where x' = par_foldr f z xs 
          res = x `f` x'

來源

2011-07-01 00:44:37 vis

如何在Haskell中使用策略編寫並行約簡？

回答

相關問題