Parallelisierung? Auf welcher Ebene? Und: Genereller Umgang mit Parallelisierung

[Gregor]

Hi.

Angenommen, ich habe ein Programm, welches sich auf verschiedenen Ebenen parallelisieren lässt. Wie geht man damit um? Auf welcher Ebene parallelisiert man? Eher auf einer höheren Ebene oder eher auf einer niedrigeren Ebene? Angenommen, das Programm nutzt auf einer mittleren Ebene eine externe Bibliothek, die plötzlich parallelisiert wird. Was macht man dann? Dann hat man plötzlich ein Programm, das auf mehreren Ebenen parallelisiert ist und ich glaube, so etwas ist nicht gut: Aus dem einfachen Grund, dass dann die Anzahl der Threads exponentiell von der Anzahl der Ebenen abhängt.

Wie geht man damit um, wenn man ein Framework bereitstellen möchte, das prinzipiell gut parallelisierbare Funktionen bietet. Parallelisiert man die einfach so? Oder lässt man das lieber, weil die Parallelisierung vielleicht eher auf höheren Ebenen stattfinden sollte? Was ist, wenn sich bei jemandem die höheren Ebenen weniger gut parallelisieren lassen? Sollte man heutzutage Frameworks schreiben, die dem Nutzer eine Möglichkeit bieten, dem Framework die Anzahl der Prozessorkerne mitzuteilen, die es benutzen darf? Wie sollte so ein Mechanismus aussehen?

...Fragen über Fragen. Ich wollte das Thema zumindest mal ansprechen und bin gespannt, welche Ideen Ihr diesbezüglich habt. Wie geht man generell mit der Parallelisierbarkeit um.

Dieser Thread soll dabei nicht nur dem oben beschriebenen Szenario dienen: Wenn euch andere Szenarien einfallen, die zu Problemen bei der Parallelisierung führen, würde mich das auch sehr interessieren. Zum Beispiel der Umgang mit unterschiedlichen Hardwarearchitekturen: Da können sich ja völlig unterschiedliche Varianten der Parallelisierung anbieten. Soll man jetzt jeden Algorithmus dreimal implementieren? Welche Annahmen kann man bezüglich der Parallelisierung treffen? Soll man eher darauf achten, dass die Verarbeitung im Programm lokal bleibt, damit der Cache oft getroffen wird? Oder sollte man Lokalität eher vermeiden, um die Anzahl der Konflikte zwischen den Threads zu minimieren? Kann man überhaupt generelle Herangehensweisen an die Parallelisierung empfehlen?

[rüdiger]

Parallelisierung hängt halt stark von den unterliegenden Prinzipien ab. Im Grunde gibt es wohl zwei entscheidende Prinzipien. Einmal shared state vs. single state: Ersteres ist leider die verbreitete Form. Aber extrem schwierig zu programmieren (Mutexes, Locks und allen möglichen scheiß). Bei so einem Modell ist die Planung und die Architektur natürlich wesentlich kritischer. Bei Single State (Prozesse, Erlang Threads) ist die Programmierung einfacher, da man abgeschlossene Programm-Teile einfach ohne Probleme in einen Thread auslagern kann, auch wenn man dies am Anfang gar nicht geplant hat. Dafür muss man natürlich ein kleines Protokoll zwischen den einzelnen Threads haben.

Eine weitere wichtige Frage ist einfach die Kosten eines Threads. Wie teuer ist es einen Thread zu starten und welchen Verwaltungsaufwand habe ich damit. (Letzteres ist natürlich unmittelbar mit dem Shared State vs Single State Prinzip verknüpft) Wenn die Erzeugung eines Threads teuer ist, muss man vorsichtig sein, dass die Erzeugung nicht den Vorteil wieder auffrisst. Threadpools können natürlich eine Alternative sein, dies erhöht aber wieder den Verwaltungsaufwand.

Ich denke daher sollte man sich ruhig mal mit dem Erlang-Prinzip befassen, was eben single state mit extrem billig zu erzeugenden Threads verbindet. Ich spreche mal von Erlang-Prinzip, da das Prinzip eben nicht nur an Erlang gebunden es und es zB auch Lisp Varianten gibt oä.

[mathik]

rüdiger schrieb:

Eine weitere wichtige Frage ist einfach die Kosten eines Threads. Wie teuer ist es einen Thread zu starten und welchen Verwaltungsaufwand habe ich damit. (Letzteres ist natürlich unmittelbar mit dem Shared State vs Single State Prinzip verknüpft) Wenn die Erzeugung eines Threads teuer ist, muss man vorsichtig sein, dass die Erzeugung nicht den Vorteil wieder auffrisst. Threadpools können natürlich eine Alternative sein, dies erhöht aber wieder den Verwaltungsaufwand.

in einem aktuellen projekt, das sehr viele daten nach dem pipes and filter pattern verarbeitet, musste ich leider feststellen, dass die synchronisation zwischen den pipe-stufen sehr teuer ist. die zeit für das erzeugen von threads ist dagegen irrelevant. man muss verarbeitungsstufen finden, wo der gewinn an parallelität die kosten an synchronisation amortisiert.

das ist auch ein problem, das ich momentan bei erlang sehe (ich muss zugeben, ich habe mich damit noch nicht detailliert befasst). dass dort threads relativ schnell erzeugt werden können ist ja schön und gut, aber message-passing muss doch auch bei Erlang irgendwie synchronisiert werden. und deshalb wird man da auch nur dann performancegewinne haben wenn die einzelnen prozesse wirklich "viel arbeiten", also grobkörnig sind.

zudem behaupten ja viele, dass erlang irgendwie auch OO ist (prozesse sind objekte zwischen denen nachrichten ausgetauscht werden). bei erlang müssen die prozesse jedoch "grobkörnig" sein (wegen synchronisationskosten.) das schöne an OO ist aber, dass man dort viele "kleine" interagierende objekte hat. ich verstehe deshalb den hype um erlang nicht so ganz. wenn man das active-object-pattern in die sprache einbaut, wie es herb sutter mal für C++0x vorgeschlagen hat (active und future schlüsselworte), dann finde ich, dass das um einiges besser ist, als das "primitive message-passing" von erlang.
ich denke, dass das auch dem von gregor angesprochenen bibliotheksproblem zumindest teilweise zugute kommen würde. man programmiert so viel es geht parallel, die "laufzeitumgebung" sollte dann selber entscheiden, was tatsächlich parallel läuft.
oder was meint ihr?

[Mr. N]

mathik schrieb:

das ist auch ein problem, das ich momentan bei erlang sehe (ich muss zugeben, ich habe mich damit noch nicht detailliert befasst). dass dort threads relativ schnell erzeugt werden können ist ja schön und gut, aber message-passing muss doch auch bei Erlang irgendwie synchronisiert werden. und deshalb wird man da auch nur dann performancegewinne haben wenn die einzelnen prozesse wirklich "viel arbeiten", also grobkörnig sind.

Bei so einer eng gefassten Aufgabe wie einer Message Queue kann man die Synchronisierungskosten ganz wesentlich reduzieren. Die Tatsache, dass die zu übertragenden Daten unveränderlich sind, mag auch helfen.