Automatische Parallelisierung

Question

Was ist Ihre Meinung zu einem Projekt, das versucht, einen Code zu nehmen und ihn automatisch in Threads aufzuteilen (vielleicht zur Kompilierzeit, wahrscheinlich zur Laufzeit).

Werfen Sie einen Blick auf den unten stehenden Code:

for(int i=0;i<100;i++)
   sum1 += rand(100)
for(int j=0;j<100;j++)
   sum2 += rand(100)/2

Diese Art von Code kann automatisch auf 2 verschiedene Threads aufgeteilt werden, die parallel laufen. Glauben Sie, dass das überhaupt möglich ist? Ich habe das Gefühl, dass es theoretisch unmöglich ist (es erinnert mich an das Halteproblem), aber ich kann diesen Gedanken nicht begründen.

Halten Sie es für ein nützliches Projekt? Gibt es etwas Vergleichbares?

Answer 1

Dies wird als automatische Parallelisierung bezeichnet. Wenn Sie nach einem Programm suchen, das dies für Sie erledigt, gibt es das noch nicht. Aber vielleicht kommt es irgendwann. Dies ist ein schwieriges Problem und ein Gebiet, auf dem aktiv geforscht wird. Wenn Sie immer noch neugierig sind...

Es ist möglich, Ihr Beispiel automatisch in mehrere Threads aufzuteilen, aber nicht so, wie Sie es sich vorstellen. Einige aktuelle Techniken versuchen, jede Iteration eines für -Schleife in ihrem eigenen Thread. Ein Thread würde die geraden Indizes (i=0, i=2, ...) erhalten, der andere die ungeraden (i=1, i=3, ...). Sobald das für -Schleife beendet ist, kann die nächste Schleife gestartet werden. Andere Techniken könnten noch verrückter werden, indem sie die i++ Inkrement in einem Thread und die rand() in einem separaten Thema.

Wie bereits erwähnt, besteht eine echte Abhängigkeit zwischen den Iterationen, denn rand() hat einen internen Status. Das steht der Parallelisierung an sich nicht im Wege. Der Compiler kann die Speicherabhängigkeit erkennen, und der veränderte Zustand von rand() kann von einem Thread zum anderen weitergeleitet werden. Aber wahrscheinlich ist die Anzahl der parallelen Threads dadurch begrenzt. Ohne Abhängigkeiten könnten Sie dies auf so vielen Kernen ausführen, wie Sie zur Verfügung haben.

Wenn Sie wirklich an diesem Thema interessiert sind und es Ihnen nichts ausmacht, Forschungsunterlagen zu durchforsten:

1. Automatische Thread-Extraktion mit entkoppeltem Software-Pipelining (2005) von G. Ottoni.
2. Spekulative Parallelisierung mit Software-Multithreading-Transaktionen (2010) von A. Raman.

Answer 2

Dies ist praktisch nicht möglich.

Das Problem ist, dass man im Voraus viel mehr Informationen wissen muss, als dem Compiler oder sogar der Laufzeit zur Verfügung stehen, um effektiv parallelisieren zu können.

Es wäre zwar möglich, sehr einfache Schleifen zu parallelisieren, aber selbst dann besteht ein gewisses Risiko. Ihr obiger Code könnte zum Beispiel nur parallelisiert werden, wenn rand() thread-sicher ist - und viele Routinen zur Erzeugung von Zufallszahlen sind es nicht. (Javas [Math.random()](http://java.sun.com/j2se/1.4.2/docs/api/java/lang/Math.html#random()) wird jedoch für Sie synchronisiert.)

Der Versuch, diese Art der automatischen Parallelisierung durchzuführen, ist, zumindest zum jetzigen Zeitpunkt, für eine "echte" Anwendung nicht praktikabel.

Answer 3

Das ist sicherlich möglich, aber es ist eine unglaublich schwierige Aufgabe. Dies ist seit mehreren Jahrzehnten das zentrale Anliegen der Compiler-Forschung. Das Grundproblem besteht darin, dass wir kein Werkzeug entwickeln können, das die beste Aufteilung in Threads für Java-Code finden kann (dies entspricht dem Halteproblem).

Stattdessen müssen wir unser Ziel von der besten Partition in irgendeine Partition des Codes verlagern. Dies ist im Allgemeinen immer noch sehr schwierig. Wir müssen also Wege finden, um das Problem zu vereinfachen. Einer davon ist, den allgemeinen Code zu vergessen und sich mit spezifischen Programmtypen zu beschäftigen. Wenn man einen einfachen Kontrollfluss hat (konstante begrenzte for-Schleifen, begrenzte Verzweigungen....), kann man viel weiter kommen.

Eine weitere Vereinfachung ist die Verringerung der Anzahl der parallelen Einheiten, die Sie beschäftigen wollen. Nimmt man diese beiden Vereinfachungen zusammen, so erhält man den Stand der Technik bei der automatischen Vektorisierung (eine spezielle Art der Parallelisierung, die zur Erzeugung von Code im MMX/SSE-Stil verwendet wird). Es hat Jahrzehnte gedauert, diesen Stand zu erreichen, aber wenn man sich Compiler wie den von Intel ansieht, dann wird die Leistung langsam ziemlich gut.

Wenn man von Vektoranweisungen innerhalb eines einzelnen Threads zu mehreren Threads innerhalb eines Prozesses übergeht, erhöht sich die Latenzzeit beim Verschieben von Daten zwischen den verschiedenen Punkten im Code enorm. Das bedeutet, dass die Parallelisierung sehr viel besser sein muss, um den Kommunikations-Overhead auszugleichen. Dies ist derzeit ein sehr aktuelles Thema in der Forschung, aber es gibt keine automatischen, auf den Benutzer zugeschnittenen Tools. Wenn Sie eines schreiben können, das funktioniert, wäre das für viele Leute sehr interessant.

Wenn Sie für Ihr Beispiel davon ausgehen, dass rand() eine parallele Version ist, die unabhängig von verschiedenen Threads aufgerufen werden kann, dann ist es recht einfach zu erkennen, dass der Code in zwei Teile aufgeteilt werden kann. Ein Compiler müsste lediglich eine Abhängigkeitsanalyse durchführen, um festzustellen, dass keine der beiden Schleifen Daten der anderen verwendet oder diese beeinflusst. Die Reihenfolge zwischen den beiden Schleifen im Code auf Benutzerebene ist also eine falsche Abhängigkeit, die aufgespalten werden könnte (z. B. indem jede Schleife in einen separaten Thread gesetzt wird).

Aber das ist nicht wirklich die Art und Weise, wie Sie den Code parallelisieren wollen. Es sieht so aus, als ob jede Schleifeniteration von der vorherigen abhängt, da sum1 += rand(100) dasselbe ist wie sum1 = sum1 + rand(100), wobei sum1 auf der rechten Seite der Wert aus der vorherigen Iteration ist. Die einzige beteiligte Operation ist jedoch die Addition, die assoziativ ist, so dass wir die Summe auf viele verschiedene Arten umschreiben können.

sum1 = (((rand_0 + rand_1) + rand_2) + rand_3) ....
sum1 = (rand_0 + rand_1) + (rand_2 + rand_3) ...

Der Vorteil der zweiten Variante ist, dass jede einzelne Addition in Klammern parallel zu allen anderen berechnet werden kann. Sobald Sie 50 Ergebnisse haben, können diese zu weiteren 25 Additionen kombiniert werden und so weiter... Auf diese Weise wird mehr Arbeit geleistet: 50+25+13+7+4+2+1 = 102 Additionen im Vergleich zu 100 im Original, aber es gibt nur 7 sequenzielle Schritte, so dass es abgesehen vom parallelen Forking/Joining und dem Kommunikations-Overhead 14 Mal schneller geht. Dieser Baum von Additionen wird in parallelen Architekturen als Gathering-Operation bezeichnet und ist in der Regel der teuerste Teil einer Berechnung.

Auf einer sehr parallelen Architektur wie einer GPU wäre die obige Beschreibung der beste Weg, den Code zu parallelisieren. Bei der Verwendung von Threads innerhalb eines Prozesses würde dieser durch den Overhead zunichte gemacht werden.

Zusammengefasst Es ist unmöglich, es perfekt zu machen, es ist sehr schwer, es gut zu machen, und es gibt eine Menge aktiver Forschung, um herauszufinden, wie viel wir tun können.

Answer 4

Es gibt einige Projekte, die versuchen, die Parallelisierung zu vereinfachen - wie z. B. Cilk . Allerdings funktioniert das nicht immer so gut.

Answer 5

Ob es im allgemeinen Fall möglich ist zu wissen, ob ein Stück Code parallelisiert werden kann, spielt keine Rolle, denn selbst wenn Ihr Algorithmus nicht alle Fälle erkennen kann, die parallelisiert werden können, kann er vielleicht einige davon erkennen.

Das heißt aber nicht, dass sie nützlich wäre. Betrachten Sie das Folgende:

1. Um dies zur Kompilierzeit zu tun, müssen Sie zunächst alle Codepfade untersuchen, die Sie innerhalb des Konstrukts, das Sie parallelisieren möchten, potenziell erreichen können. Dies kann für alles andere als einfache Berechnungen schwierig sein.
2. Zweitens müssen Sie irgendwie entscheiden, was parallelisierbar ist und was nicht. Sie können beispielsweise eine Schleife, die denselben Zustand ändert, nicht trivialerweise in mehrere Threads aufteilen. Dies ist wahrscheinlich eine sehr schwierige Aufgabe, und in vielen Fällen werden Sie sich am Ende nicht sicher sein - zwei Variablen könnten tatsächlich auf dasselbe Objekt verweisen.
3. Selbst wenn Sie dies erreichen könnten, wäre es für den Benutzer verwirrend. Es wäre sehr schwierig zu erklären, warum sein Code nicht parallelisierbar ist und wie er geändert werden sollte.

Ich denke, wenn man dies in Java erreichen will, muss man es eher als Bibliothek schreiben und den Benutzer entscheiden lassen, was parallelisiert werden soll (Bibliotheksfunktionen zusammen mit Anmerkungen? ich denke nur laut). Funktionale Sprachen sind dafür viel besser geeignet.

Ein kleines Detail am Rande: In einem Kurs über parallele Programmierung mussten wir Code untersuchen und entscheiden, ob er parallelisierbar war oder nicht. Ich kann mich nicht mehr an die Einzelheiten erinnern (irgendetwas mit der "at-most-once"-Eigenschaft? Kann mich jemand aufklären?), aber die Moral von der Geschicht ist, dass es selbst für scheinbar triviale Fälle extrem schwierig war.