Übungszettel 10

Parallelismus & Nebenläufigkeit

Issue 1

Im Modul Parallel finden Sie eine Funktion, die Sie noch von Zettel 3 kennen. Zur Erinnerung: Die Funktion nBesteEingaben gibt Ihnen mit beliebiger numerischer Genauigkeit diejenigen Eingaben (4-Tupel, jeweils mit Werten aus [-10,10]) zurück, für die eine komlizierteFunktion maximal wird. Hierfür wird der komplizierten Funktion mithilfe von List-Applicative (kartesisches Produkt) eine lange, beliebig dichte Liste möglicher Eingabewerte zwischen (-10,-10,-10,-10) und (10,10,10,10) übergeben. Bei einem Abstand von 0.5 ergeben sich damit 41^4 = 2 825 761 Berechnungen. Diese lohnt es sich zu parallelisieren!

Parallelisieren Sie die Funktion nBesteEingaben, mit mindestens drei verschiedenen Strategien für Lists (bzw. Lazy Lists) aus Control.Parallel.Strategies.

Um ihre Parallelisierung zu testen, verwenden Sie die folgenden Terminalbefehle:

stack exec -- MainParallel1 +RTS -N1 -s
stack exec -- MainParallel1 +RTS -N2 -s
stack exec -- MainParallel1 +RTS -N4 -s
stack exec -- MainParallel1 +RTS -N8 -s

-Nx steht für die Verwendung von x Kernen. MainParallelx steht für die Verwendung der Strategie x.

Eine sinnvolle Parallelisierung erkennen Sie daran, dass die Berechnung schneller wird, je mehr echte Kerne Sie für zur Verfügung stellen. Mindestens eine Strategie sollte in diesem Sinne sinnvoll sein.

Notieren sie die Laufzeiten ihrer Versuche in einer Tabelle und geben sie den Speedup (-N1-Zeit/-NxZeit) an.

Nützliche Funktion: using :: a -> Strategy a -> a

Issue 2

Sie werden bemerkt haben, dass der Speedup sich nicht linear mit der Anzahl der Kerne steigern lässt. Nach Amdahls Gesetz ist bei vielen Kernen der nicht-parallelisierte Part (in unserem Fall das sortieren) für die schlechte Performance verantwortlich.

Da wir uns nur für die Top n eingaben interessieren, schreiben Sie eine Funktion

topn :: Int -> [a] -> [a]

welche nach n Einsortierungsversuchen das zu sortierende Element verwirft (z.B. als Liste oder Array) und somit die Sortierung frühestmöglich abbricht.

Füllen sie die Speedup-Tabelle erneut aus. Was ändert sich?

Issue 3

Sie besitzen eine Bank und sollen Überweisungen programmieren. Sie finden in Banking.hs alles fertig. Nur noch die debit-Funktion muss geschrieben werden, die von dem ersten auf das zweite Konto überweist.

Im Szenario der Main-Funktionen hat die Bank 10 verschiedene Server, die gleichzeitig dieselbe Transaktion auf der Datenbank ausführen wollen (also haben sie mehrere "Banken" in der Main, die auch alle etwas ausgeben, aber alle zeigen denselben Kontostand, da die Konten selbst nur 1x existieren).

Führen Sie anschließend MainBanking1 und MainBanking2 aus. Was können sie beobachten? Wie kommt es zu den Ergebnissen?

Hint (optional!): Mittels stack exec -- MainBanking1 +RTS -ls können Sie ein eventlog ausgeben lassen, welches Sie mittels threadscope (stack install threadscope) ansehen können.

Was passiert, wenn Sie dies mit -N1 ausführen? Wieso?

Issue 4

Da Sie in Aufgabe 3 in Probleme gelaufen sind (sind Sie doch, oder? ;) ), benutzen Sie hier statt MVars die STM-eigenen TMVars.

In STMBanking.hs finden Sie die gleiche Situation vor - nur müssen Sie hier mit STM statt mit MVar arbeiten.

Führen Sie anschließend MainSTMBanking1 und MainSTMBanking2 aus. Was können Sie beobachten? Inwiefern unterscheiden sich die Ergebnisse zu den MVars?

Hint (optional!): Mittels stack exec -- MainBanking1 +RTS -ls können Sie ein eventlog ausgeben lassen, welches Sie mittels threadscope (stack install threadscope) ansehen können.

Was passiert, wenn Sie dies mit -N1 ausführen? Wieso?

Wo sind die Unterschiede zu MVars (Performance, Einfachheit der Programmierung, Resistenz gegen Programmierfehler, ..)? Beschreiben Sie kurz wie sich ihre Probleme mit der jeweiligen Implementation anfühlten und wieso Sie welche Lösung selbst bevorzugen würden.