数据并行Haskell前缀总和

我正在玩一些Data Parallel Haskell代码，发现自己需要prefix sum。但是，我没有看到dph package前缀总和中的任何基本运算符。数据并行Haskell前缀总和

我推出我自己的，但由于我是新来的DPH，我不知道这是否是正确采取并行的优势：

{-# LANGUAGE ParallelArrays #-} 
{-# OPTIONS_GHC -fvectorise #-} 

module PrefixSum (scanP) where 
import Data.Array.Parallel (lengthP, indexedP, mapP, zipWithP, concatP, filterP, singletonP, sliceP, (+:+), (!:)) 
import Data.Array.Parallel.Prelude.Int ((<=), (-), (==), Int, mod) 
-- hide prelude 
import qualified Prelude 

-- assuming zipWithP (a -> b -> c) given 
-- [:a:] of length n and 
-- [:b:] of length m, n /= m 
-- will return 
-- [:c:] of length min n m 

scanP :: (a -> a -> a) -> [:a:] -> [:a:] 
scanP f xs = if lengthP xs <= 1 
       then xs 
       else head +:+ tail 
    where -- [: x_0, x_2, ..., x_2n :] 
     evens = mapP snd . filterP (even . fst) $ indexedP xs 
     -- [: x_1, x_3 ... :] 
     odds = mapP snd . filterP (odd . fst) $ indexedP xs 
     lenEvens = lengthP evens 
     lenOdds = lengthP odds 
     -- calculate the prefix sums [:w:] of the pair sums [:z:] 
     psums = scanP f $ zipWithP f evens odds 
     -- calculate the total prefix sums as 
     -- [: x_0, w_0, f w_0 x_2, w_1, f w_1 x_4, ..., 
     head = singletonP (evens !: 0) 
     body = concatP . zipWithP (\p e -> [: p, f p e :]) psums $ sliceP 1 lenOdds evens 
     -- ending at either 
     -- ... w_{n-1}, f w_{n-1} x_2n :] 
     -- or 
     -- ... w_{n-1}, f w_{n-1} x_2n, w_n :] 
     -- depending on whether the length of [:x:] is 2n+1 or 2n+2 
     tail = if lenEvens == lenOdds then body +:+ singletonP (psums !: (lenEvens - 1)) else body 

-- reimplement some of Prelude so it can be vectorised 
f $ x = f x 
infixr 0 $ 
(.) f g y = f (g y) 

snd (a,b) = b 
fst (a,b) = a 

even n = n `mod` 2 == 0 
odd n = n `mod` 2 == 1

来源

2012-01-31 rampion

嗯，它可以并行吗？看起来像一个漂亮的连续想法，但也许我错过了一些东西。 – luqui 2012-01-31 15:16:02

@luqui：大小为“n”的数组的并行前缀和算法需要执行“O（log n）”循环的并行计算。有两个阶段。在前进阶段，给定'{a_i |我在[0,2n-1]}'你计算出{a_2i + a_ {2i + 1} | i \ in [0，n-1]}'使用'n/2'并行加法。在后退阶段，给定'{\ sum_0^{2i + 1} a_j |我在[0，n-1]}'和'{a_i |我在[0,2n-1]}'中计算了'{\ sum_0^i a_j |我在[0，2n-1}'中使用了'n/2'并行加法。 – rampion 2012-01-31 16:24:40

@luqui：自然，这只适用于关联性'+'，因为存在内在的假设，即（a_0 + a_1）+（a_2 + a_3）==（（a_0 + a_1）+ a_2）+ a_3' – rampion 2012-01-31 16:27:10

并行前缀扫描是supported，事实上，他们”相当重要。所以只需通过(+)作为您的关联运算符。

来源

2012-05-03 17:21:54

啊，我看着错误的包装。谢谢！ – rampion 2012-05-04 13:07:24

数据并行Haskell前缀总和

回答

相关问题