Multicore-Programmierung in Haskell - Control.Parallel

Question

Ich versuche zu lernen, wie man das Control.Parallel-Modul zu verwenden, aber ich denke, dass ich es nicht richtig verstanden habe.

Ich versuche, den folgenden Code auszuführen (fibs.hs).

import Control.Parallel 

fib :: Int -> Int 
fib 0 = 0 
fib 1 = 1 
fib n = p `par` (q `pseq` (p + q)) 
    where 
     p = fib (n-1) 
     q = fib (n-2) 


main = print $ fib 30 

ich zusammengestellt dies mit:

ghc -O2 --make -threaded fibs.hs 

Und dann bekomme ich folgende Ergebnisse dieses Programm (Ausgabe eines Python-Skript ausgeführt wird, dass jedes Programm 100 mal läuft und gibt den Mittelwert und Standardabweichung von der Ausführungszeit):

./fibs +RTS -N1 -> avg= 0.060203 s, deviation = 0.004112 s 
./fibs +RTS -N2 -> avg= 0.052335 s, deviation = 0.006713 s 
./fibs +RTS -N3 -> avg= 0.052935 s, deviation = 0.006183 s 
./fibs +RTS -N4 -> avg= 0.053976 s, deviation = 0.007106 s 
./fibs +RTS -N5 -> avg= 0.055227 s, deviation = 0.008598 s 
./fibs +RTS -N6 -> avg= 0.055703 s, deviation = 0.006537 s 
./fibs +RTS -N7 -> avg= 0.058327 s, deviation = 0.007526 s 

Meine Fragen sind:

1. Was genau passiert, wenn ich beurteilen:

   a `par` (b `pseq` (a + b)) ? 
   

   Ich verstehe, dass ein par b soll der Compiler über die Berechnung ein parallel zu b und das Rück b andeuten. OK. Aber was macht pseq?

2. Warum sehe ich eine so kleine Leistungssteigerung? Ich führe dies in einem Intel Core 2 Quad-Rechner. Ich würde erwarten, dass das Laufen mit -N5 oder -N6 keinen wirklichen Unterschied in der Leistung machen würde oder dass das Programm tatsächlich sehr schlecht arbeiten würde. Aber warum sehe ich keine Verbesserung von -N2 zu -N3 und warum ist die anfängliche Verbesserung so gering?

Answer 1

Als Don explained ist das Problem, dass Sie zu viele Funken erstellen. Hier ist, wie Sie es umschreiben können, um eine gute Beschleunigung zu bekommen.

import Control.Parallel 

cutoff :: Int 
cutoff = 20 

parFib :: Int -> Int 
parFib n | n < cutoff = fib n 
parFib n = p `par` q `pseq` (p + q) 
    where 
     p = parFib $ n - 1 
     q = parFib $ n - 2 

fib :: Int -> Int 
fib 0 = 0 
fib 1 = 1 
fib n = fib (n - 1) + fib (n - 2) 

main :: IO() 
main = print $ parFib 40 

Demonstration:

[computer ~]$ ghc --make -threaded -O2 Main.hs 
[1 of 1] Compiling Main    (Main.hs, Main.o) 
Linking Main ... 
[computer ~]$ time ./Main +RTS -N1 
102334155 

real 0m1.509s 
user 0m1.450s 
sys  0m0.003s 
[computer ~]$ time ./Main +RTS -N2 
102334155 

real 0m0.776s 
user 0m1.487s 
sys  0m0.023s 
[computer ~]$ time ./Main +RTS -N3 
102334155 

real 0m0.564s 
user 0m1.487s 
sys  0m0.030s 
[computer ~]$ time ./Main +RTS -N4 
102334155 

real 0m0.510s 
user 0m1.587s 
sys  0m0.047s 
[computer ~]$ 

Answer 2

Re (1): par ermöglicht a in einem anderen Thread berechnet werden. Ich denke hier, aber ich denke, pseq verhält sich sehr ähnlich wie seq: dass es zwingt das erste Ergebnis zuerst berechnet (na ja, seq ist nicht garantiert, dies zu tun, aber in der Praxis auf GHC tut es). In diesem Fall wird also die Berechnung von a als ein Thread abgespalten, und der andere Thread berechnet b und summiert dann a und b.

Re (2): Dies ist eine ziemlich triviale Berechnung, die auf andere Threads abgezweigt wird; es ist wahrscheinlich genauso schnell für die CPU, um es selbst zu berechnen. Ich wette, der Overhead von Threads schmerzt fast genauso sehr wie die Hilfe für diese einfache Berechnung.

Answer 3

Sie erstellen eine exponentielle Anzahl von Funken (denken Sie daran, wie viele rekursive Aufrufe Sie hier erstellen). Um tatsächlich eine gute Parallelität zu erhalten, müssen Sie in diesem Fall weniger parallele Arbeit erstellen, da Ihre Hardware so viele Threads nicht verarbeiten kann (und GHC macht sie daher nicht).

Die Lösung ist eine Grenz Strategie zu verwenden, wie es in diesem Vortrag beschrieben: http://donsbot.wordpress.com/2009/09/05/defun-2009-multicore-programming-in-haskell-now/

Grundsätzlich auf die gerade Linie Version wechseln, wenn Sie eine bestimmte Tiefe zu erreichen, und die Verwendung + RTS -sstderr, um zu sehen, wie viele Funken werden konvertiert, so dass Sie feststellen können, ob Sie Arbeit verschwenden oder nicht.

Answer 4

Da niemand eine definitive Antwort über pseq gab, ist hier der official description:

Semantisch Seq identisch, aber mit einem subtilen operativen Unterschied: seq ist streng in beiden Argumente, so der Compiler, zum Beispiel, Umlagerung einer seq b in b seq a seq b. Dies ist normalerweise kein Problem bei Verwendung Seq, um Strenge, , aber es kann ein Problem sein, wenn Code für Parallelität, Annotation, weil wir mehr Kontrolle über die Reihenfolge der Auswertung benötigen; wir wollen auswerten a vor b, weil wir wissen, dass b bereits in parallel mit Par ausgelöst worden ist.

Deshalb haben wir Pseq. Im Gegensatz Seq ist pseq nur streng in seinem ersten Argumente (soweit der Compiler betroffen ist), die die Transformationen beschränkt, dass der Compiler tun kann, und sorgt dafür, dass der Benutzer Steuerung der Auswertung behalten kann bestellen.