2011-01-02 9 views
29

Sto cercando di capire il motivo per cui abbiamo bisogno di tutte le parti del codice campione standard:Perché abbiamo bisogno di "seq" o "pseq" con "par" in Haskell?

a `par` b `pseq` a+b 

Perché non sarà il seguente essere sufficiente?

a `par` b `par` a+b 

L'espressione di cui sopra sembra molto descrittivo: Prova di valutare sia a e b in parallelo, e restituire il risultato a+b. La ragione è solo quella dell'efficienza: la seconda versione si innescherebbe due volte anziché una volta?

E la seguente, versione più succinta?

a `par` a+b 

Perché avremmo bisogno di assicurarsi b viene valutata prima a+b come nel codice originale, di serie?

risposta

29

Ok. Credo che il seguente documento risponde alla mia domanda: http://community.haskell.org/~simonmar/papers/threadscope.pdf

In sintesi, il problema con

a `par` b `par` a+b 

e

a `par` a+b 

è la mancanza di ordinamento della valutazione. In entrambe le versioni, il thread principale inizia a lavorare su a (o talvolta su b) immediatamente, causando lo "scintillio" delle scintille immediatamente poiché non c'è più bisogno di avviare un thread per valutare cosa il thread principale ha già iniziato a valutare.

La versione originale

a `par` b `pseq` a+b 

assicura il filo principale lavora bprimaa+b (altrimenti avrebbe iniziato valutare a invece), dando così la possibilità per la scintilla a di materializzare in un filo per valutazione parallela.

+6

Questo è corretto e spiega anche perché 'seq' non è sufficiente per questo problema. 'seq' non fornisce garanzie sull'ordinazione della valutazione. In 'seq b (a + b)', il thread principale può valutare 'a' prima di' b' fintanto che 'b' è in WHNF quando' (a + b) 'viene valutato. –

+2

Non vedo come questo argomento descriva il problema con 'par a (par b (a + b))' - sicuro, o 'a' o' b' sarà immediatamente valutato, e la scintilla corrispondente si spegnerà, ma l'altra scintilla dovrebbe essere molto viva, producendo parallelismo. Ovviamente, creare una scintilla quindi non potrebbe essere il modo più efficace per farlo, ma funziona e lascia la domanda dell'ordine di valutazione al compilatore. – gereeter

+0

Nel caso di 'par a (a + b)', è ancora possibile ottenere una parallelizzazione "fortunata", se il runtime sceglie invece 'b' prima. Quindi la scintilla 'a' non verrà fiaccata. Questo è menzionato nel PDF: community.haskell.org/~simonmar/papers/threadscope.pdf (pagina 2) – CMCDragonkai

16
a `par` b `par` a+b 

valuterà a e b in parallelo e restituisce a + b, sì.

Tuttavia, il pseq ci assicura sia a che b vengono valutate prima a + b è.

Vedere this link per ulteriori dettagli su tale argomento.

6

a `par` b `par` a+b crea scintille sia a e b, ma a+b si raggiunge immediatamente così una delle scintille fiasco (cioè, viene valutato nel thread principale). Il problema con questo è l'efficienza, in quanto abbiamo creato una scintilla inutile. Se stai usando questo per implementare il parallel divide & conquista, il sovraccarico limiterà la tua velocità.

a `par` a+b sembra migliore perché crea solo una singola scintilla. Tuttavia, il tentativo di valutare a prima dello b interromperà la scintilla per a e, poiché b non ha una scintilla, ciò comporterà una valutazione sequenziale di a+b. Commutare l'ordine su b+a risolverebbe questo problema, ma siccome il codice non impone l'ordine e Haskell potrebbe ancora valutarlo come a+b.

Quindi, facciamo a `par` b `pseq` a+b forzare la valutazione di b nella discussione principale prima di tentare di valutare a+b. Questo dà la possibilità che si verifichi la scintilla a prima di provare a valutare a+b e non abbiamo creato scintille inutili.