Comment écrire une réduction parallèle en utilisant des stratégies dans Haskell?

Question

En calcul haute performance, les sommes, produits, etc. sont souvent calculés à l'aide d'une "réduction parallèle" qui prend n éléments et se termine en O (log n) temps (avec suffisamment de parallélisme). Dans Haskell, nous utilisons généralement un pour pour ce type de calcul, mais le temps d'évaluation est toujours linéaire dans la longueur de la liste.

Données Parallèle Haskell incorpore une partie de ceci, mais qu'en est-il dans le cadre commun d'une liste? Pouvons-nous le faire avec Control.Parallel.Strategies?

Ainsi, en supposant f est associative, comment pouvons-nous écrire

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

pour que parFold f xs n'a besoin que logarithmique de temps en length xs?

Answer 1

Je ne pense pas qu'une liste soit le bon type de données pour cela. Parce que c'est juste une liste liée, les données seront nécessairement accédées séquentiellement. Bien que vous puissiez évaluer les éléments en parallèle, vous ne gagnerez pas grand-chose dans l'étape de réduction. Si vous avez vraiment besoin d'une liste, je pense que la meilleure fonction serait juste

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

ou peut-être

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

Si l'étape de réduction est complexe, vous pourriez obtenir un gain en subdivisant la liste comme ceci:

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) 

J'ai pris la liberté d'assumer vos données est un Monoid pour mempty, si cela est impossible, vous pouvez remplacer mempty avec votre propre type vide, ou pire des cas d'utilisation foldl1'.

Deux opérateurs de Control.Parallel.Strategies sont utilisés ici. Le parList évalue tous les éléments de la liste en parallèle. Après cela, le chunkList divise la liste en blocs de 1000 éléments. Chacun de ces morceaux est ensuite réduit en parallèle par le parMap.

Vous pouvez également essayer

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) 

Selon exactement comment le travail est distribué, l'un d'entre eux peuvent être plus efficaces que les autres. Si vous pouvez utiliser une structure de données supportant bien l'indexation (Array, Vector, Map, etc.), alors vous pouvez faire des subdivisions binaires pour l'étape de réduction, ce qui sera probablement meilleur dans l'ensemble.

Answer 2

Cela semble être un bon point de départ:

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 

Il fonctionne, mais le parallélisme est pas si grand. Remplacer parList avec quelque chose comme parListChunks 1000 aide un peu, mais l'accélération est toujours limitée à moins de 1,5x sur une machine 8-core.

Answer 3

Vous ne savez pas exactement ce que votre fonction parFold est censée faire. Si cela est destiné à être une version parallèle de foldr ou foldl, je pense que sa définition est fausse.Fold applique la même fonction à chaque élément de la liste et accumule le résultat de chaque application. En arriver à une version parallèle, je suppose, il faudrait que l'application de la fonction aux éléments soit faite en parallèle - un peu comme ce que fait 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'