¿Cómo escribo una reducción paralela usando estrategias en Haskell?

Question

En computación de alto rendimiento, sumas, productos, etc. a menudo se calculan usando una "reducción paralela" que toma n elementos y completa en O (log n) tiempo (dado suficiente paralelismo). En Haskell, generalmente usamos un veces para este tipo de cálculo, pero el tiempo de evaluación siempre es lineal en la longitud de la lista.

Datos paralelos Haskell tiene algo de esto integrado, pero ¿qué pasa con el marco común de una lista? ¿Podemos hacerlo con Control.Parallel.Strategies?

Así, suponiendo f es asociativa, ¿cómo se escribe

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

por lo que sólo necesita parFold f xs logarítmica vez en length xs?

Answer 1

No creo que una lista sea el tipo de datos correcto para esto. Como solo se trata de una lista vinculada, necesariamente se accederá a los datos secuencialmente. Aunque puede evaluar los elementos en paralelo, no ganará mucho en el paso de reducción. Si realmente necesita una lista, creo que la mejor función sería simplemente

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

o tal vez

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

Si la etapa de reducción es compleja, es posible obtener una ganancia mediante la subdivisión de la lista como esta:

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) 

me he tomado la libertad de asumir sus datos es una Monoid para mempty, si esto no es posible, puede reemplazar mempty con su propio tipo de vacío, o peor caso de uso foldl1'.

Hay dos operadores de Control.Parallel.Strategies en uso aquí. El parList evalúa todos los elementos de la lista en paralelo. Después de eso, el chunkList divide la lista en fragmentos de 1000 elementos. Cada uno de esos trozos se reduce en paralelo por el parMap.

También puede intentar

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) 

Dependiendo de exactamente cómo se distribuye el trabajo, uno de ellos puede ser más eficiente que los otros.

Si puede usar una estructura de datos que tiene buen soporte para la indexación (Array, Vector, Map, etc.), entonces puede hacer subdivisiones binarias para el paso de reducción, que probablemente será mejor en general.

Answer 2

Este parece ser un buen comienzo:

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 

Funciona, pero el paralelismo no es tan grande. Reemplazar parList con algo como parListChunks 1000 ayuda un poco, pero la aceleración aún está limitada a menos de 1,5x en una máquina de 8 núcleos.

Answer 3

No estoy seguro de qué debe hacer su función parFold. Si se pretende que sea una versión paralela de foldr o foldl, creo que su definición es incorrecta.

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

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

Fold aplica la misma función a cada elemento de la lista y acumula el resultado de cada aplicación. La creación de una versión paralela de la misma, supongo, requeriría que la aplicación de función a los elementos se haga en paralelo, un poco como lo hace 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'