Données Parallèle Haskell Préfixe Somme

Je joue avec du code Data Parallel Haskell et j'ai moi-même besoin d'un prefix sum. Cependant, je n'ai vu aucun opérateur de base dans le dph package pour la somme des préfixes.Données Parallèle Haskell Préfixe Somme

je roulais seul, mais, depuis que je suis nouveau à DPH, je ne sais pas si cela prend bien avantage de parallélisation:

{-# 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

Source

2012-01-31 rampion

Hmm, est-ce qu'il est même parallélisable? On dirait une jolie idée de série, mais peut-être qu'il me manque quelque chose. – luqui

@luqui: L'algorithme de somme de préfixes parallèles pour un tableau de taille «n» prend 'O (log n)' tours de calcul parallèles. Il y a deux phases. Dans la phase avant, donné '{a_i | i \ in [0,2n-1]} 'vous calculez' {a_2i + a_ {2i + 1} | i \ in [0, n-1]} 'en utilisant des additions parallèles' n/2'. Dans la phase arrière, donné {{sum_0^{2i + 1} a_j | i \ in [0, n-1]} 'et' {a_i | i \ in [0,2n-1]} ', vous calculez' {\ sum_0^i a_j | i \ in [0, 2n-1} 'en utilisant des additions parallèles' n/2'. – rampion

@luqui: naturellement, ceci ne fonctionne correctement que pour l'associatif «+», car il y a l'hypothèse inhérente que '(a_0 + a_1) + (a_2 + a_3) == ((a_0 + a_1) + a_2) + a_3' – rampion

scans préfixe parallèles sont supported, en fait, ils » re plutôt fondamental. Il suffit donc de passer (+) en tant qu'opérateur associatif.

Source

2012-05-03 17:21:54

Ah, je regardais dans le mauvais paquet. Merci! – rampion

Données Parallèle Haskell Préfixe Somme

Répondre

Questions connexes