Come scrivere una riduzione parallela utilizzando le strategie in Haskell?

Question

Nel calcolo ad alte prestazioni, somme, prodotti, ecc sono spesso calcolati utilizzando una "riduzione parallela" che prende n elementi e completa in O (log n) tempo (dato abbastanza parallelismo). In Haskell, solitamente usiamo una piega per questo tipo di calcolo, ma il tempo di valutazione è sempre lineare nella lunghezza della lista.

Data Parallel Haskell ha un po 'di questo incorporato, ma nel quadro comune di un elenco? Possiamo farlo con Control.Parallel.Strategies?

Quindi, ipotizzando f è associativa, come facciamo scriviamo

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

modo che parFold f xs ha solo bisogno di tempo logaritmico a length xs?

Answer 1

Non penso che una lista sia il giusto tipo di dati per questo. Perché è solo una lista collegata, i dati saranno necessariamente utilizzati in sequenza. Sebbene sia possibile valutare gli articoli in parallelo, non si otterrà molto nel passaggio di riduzione. Se si ha realmente bisogno di un elenco, penso che la funzione migliore sarebbe solo

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

o forse

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

Se la fase di riduzione è complesso, si potrebbe ottenere un guadagno suddividendo la lista come questa:

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) 

mi sono preso la libertà di assumere i dati è un Monoid per mempty, se questo non è possibile è possibile sostituire mempty con il proprio tipo di vuoto, o l'uso caso peggiore foldl1'.

Ci sono due operatori da Control.Parallel.Strategies in uso qui. Lo parList valuta tutti gli elementi della lista in parallelo. Dopodiché, lo chunkList divide l'elenco in blocchi di 1000 elementi. Ciascuno di questi blocchi viene quindi ridotto in parallelo dal numero parMap.

Si potrebbe anche provare

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) 

A seconda esattamente come è distribuito il lavoro, uno di questi può essere più efficiente rispetto agli altri.

Se è possibile utilizzare una struttura dati con un buon supporto per l'indicizzazione (Array, Vector, Mappa, ecc.), È possibile eseguire suddivisioni binarie per il passaggio di riduzione, che sarà probabilmente nel complesso migliore.

Answer 2

Questo mi sembra un buon inizio:

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 

Funziona, ma il parallelismo non è così grande. Sostituire parList con qualcosa come parListChunks 1000 aiuta un po ', ma l'accelerazione è ancora limitata a meno di 1,5x su un computer a 8 core.

Answer 3

Non so cosa dovrebbe fare la funzione parFold. Se si vuole che sia una versione parallela di foldr o foldl, penso che la sua definizione sia sbagliata.

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

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

Fold applica la stessa funzione a ciascun elemento dell'elenco e accumula il risultato di ciascuna applicazione. Supponendo che una versione parallela di esso richieda che l'applicazione della funzione agli elementi venga eseguita in parallelo, un po 'come fa 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'