Automatische Parallelisierung - Automatic parallelization

Automatische Parallelisierung , auch Auto Parallelisierung oder autoparallelization bezieht sich auf sequentiellen Umwandlung Code in Multi-Threaded - und / oder vektorisiert Code, um mehrere Prozessoren zu verwenden , gleichzeitig in einer gemeinsamen Speicher - Multiprozessor ( SMP ) Maschine. Die vollautomatische Parallelisierung von sequentiellen Programmen ist eine Herausforderung, da sie eine komplexe Programmanalyse erfordert und der beste Ansatz möglicherweise von Parameterwerten abhängt, die zum Zeitpunkt der Kompilierung nicht bekannt sind.

Die Programmierkontrollstrukturen, auf die die Autoparallelisierung den größten Fokus legt, sind Schleifen , da im Allgemeinen der größte Teil der Ausführungszeit eines Programms innerhalb einer Form von Schleife stattfindet. Es gibt zwei Hauptansätze zur Parallelisierung von Schleifen: Pipeline-Multithreading und zyklisches Multithreading. Betrachten Sie beispielsweise eine Schleife, die bei jeder Iteration hundert Operationen anwendet und tausend Iterationen durchläuft. Dies kann man sich als Raster von 100 Spalten mal 1000 Zeilen vorstellen, also insgesamt 100.000 Operationen. Zyklisches Multithreading weist jede Zeile einem anderen Thread zu. Beim Pipeline-Multithreading wird jede Spalte einem anderen Thread zugewiesen.

Automatische Parallelisierungstechnik

Analysieren

Dies ist die erste Phase, in der der Scanner die Eingabequelldateien liest, um alle statischen und externen Verwendungen zu identifizieren. Jede Zeile in der Datei wird anhand vordefinierter Muster überprüft, um sie in Token aufzuteilen . Diese Token werden in einer Datei gespeichert, die später von der Grammatik-Engine verwendet wird. Die Grammatik-Engine überprüft Muster von Token, die mit vordefinierten Regeln übereinstimmen, um Variablen, Schleifen, Steueranweisungen, Funktionen usw. im Code zu identifizieren.

Analysieren

Der Analysator wird verwendet, um Codeabschnitte zu identifizieren, die gleichzeitig ausgeführt werden können. Der Analysator verwendet die vom Scanner-Parser bereitgestellten statischen Dateninformationen. Der Analysator findet zunächst alle völlig unabhängigen Funktionen und markiert sie als einzelne Aufgaben. Der Analysator findet dann, welche Aufgaben Abhängigkeiten haben.

Zeitlicher Ablauf

Der Scheduler listet alle Aufgaben und deren Abhängigkeiten voneinander in Bezug auf Ausführung und Startzeiten auf. Der Scheduler erstellt den optimalen Zeitplan in Bezug auf die Anzahl der zu verwendenden Prozessoren oder die Gesamtausführungszeit für die Anwendung.

Codegenerierung

Der Scheduler generiert eine Liste aller Aufgaben und der Details der Kerne, auf denen sie ausgeführt werden, zusammen mit der Zeit, für die sie ausgeführt werden. Der Code-Generator fügt spezielle Konstrukte in den Code ein, die während der Ausführung vom Scheduler gelesen werden. Diese Konstrukte weisen den Scheduler an, auf welchem ​​Kern eine bestimmte Aufgabe zusammen mit den Start- und Endzeiten ausgeführt wird.

Zyklisches Multithreading

Ein zyklischer parallelisierender Multithreading-Compiler versucht, eine Schleife aufzuteilen, damit jede Iteration gleichzeitig auf einem separaten Prozessor ausgeführt werden kann .

Compiler-Parallelisierungsanalyse

Der Compiler führt vor der eigentlichen Parallelisierung normalerweise zwei Analysedurchgänge durch, um Folgendes zu bestimmen:

• Ist es sicher, die Schleife zu parallelisieren? Die Beantwortung dieser Frage erfordert eine genaue Abhängigkeitsanalyse und Aliasanalyse
• Lohnt sich eine Parallelisierung? Diese Antwort erfordert eine zuverlässige Schätzung (Modellierung) der Programmbelastung und der Kapazität des Parallelsystems.

Der erste Durchlauf des Compilers führt eine Datenabhängigkeitsanalyse der Schleife durch, um zu bestimmen, ob jede Iteration der Schleife unabhängig von den anderen ausgeführt werden kann. Die Datenabhängigkeit kann manchmal bewältigt werden, sie kann jedoch zusätzlichen Overhead in Form von Nachrichtenweitergabe , Synchronisation des gemeinsam genutzten Speichers oder einer anderen Methode der Prozessorkommunikation verursachen.

Der zweite Durchlauf versucht, den Parallelisierungsaufwand zu rechtfertigen, indem die theoretische Ausführungszeit des Codes nach der Parallelisierung mit der sequentiellen Ausführungszeit des Codes verglichen wird. Etwas kontraintuitiv profitiert Code nicht immer von der parallelen Ausführung. Der zusätzliche Overhead, der mit der Verwendung mehrerer Prozessoren verbunden sein kann, kann die potenzielle Geschwindigkeit von parallelisiertem Code beeinträchtigen.

Beispiel

Eine Schleife heißt DOALL, wenn alle ihre Iterationen in einem beliebigen Aufruf gleichzeitig ausgeführt werden können. Der folgende Fortran- Code ist DOALL und kann von einem Compiler automatisch parallelisiert werden, da jede Iteration unabhängig von den anderen ist und das Endergebnis von Array zunabhängig von der Ausführungsreihenfolge der anderen Iterationen korrekt ist.

   do i = 1, n
     z(i) = x(i) + y(i)
   enddo

Es gibt viele erfreulicherweise parallele Probleme, die solche DOALL-Schleifen haben. Zum Beispiel kann beim Rendern eines Raytracing-Films jeder Frame des Films unabhängig gerendert werden, und jedes Pixel eines einzelnen Frames kann unabhängig gerendert werden.

Andererseits kann der folgende Code nicht automatisch parallelisiert werden, da der Wert von z(i)vom Ergebnis der vorherigen Iteration abhängt, z(i - 1).

   do i = 2, n
     z(i) = z(i - 1)*2
   enddo

Dies bedeutet nicht, dass der Code nicht parallelisiert werden kann. Tatsächlich ist es äquivalent zu

   do i = 2, n
     z(i) = z(1)*2**(i - 1)
   enddo

Aktuelle parallelisierende Compiler sind jedoch normalerweise nicht in der Lage, diese Parallelitäten automatisch hervorzubringen, und es ist fraglich, ob dieser Code überhaupt von der Parallelisierung profitieren würde.

Pipeline-Multithreading

Ein parallelisierender Multithreading-Compiler mit Pipeline versucht, die Abfolge von Operationen innerhalb einer Schleife in eine Reihe von Codeblöcken aufzuteilen, sodass jeder Codeblock gleichzeitig auf separaten Prozessoren ausgeführt werden kann .

Es gibt viele erfreulicherweise parallele Probleme, die solche relativ unabhängigen Codeblöcke aufweisen, insbesondere Systeme, die Pipes und Filter verwenden . Bei der Produktion von Live-Fernsehsendungen müssen beispielsweise die folgenden Aufgaben viele Male pro Sekunde ausgeführt werden:

1. Lesen Sie einen Frame mit rohen Pixeldaten vom Bildsensor,
2. Führen Sie eine MPEG- Bewegungskompensation für die Rohdaten durch,
3. Entropie komprimiert die Bewegungsvektoren und andere Daten,
4. Zerlegen Sie die komprimierten Daten in Pakete,
5. Fügen Sie die entsprechende Fehlerkorrektur hinzu und führen Sie eine FFT durch, um die Datenpakete in COFDM- Signale umzuwandeln , und
6. Senden Sie die COFDM-Signale über die TV-Antenne.

Ein parallelisierender Compiler mit Pipeline-Multithreading könnte jede dieser 6 Operationen einem anderen Prozessor zuweisen, der möglicherweise in einem systolischen Array angeordnet ist , und den entsprechenden Code einfügen, um die Ausgabe eines Prozessors an den nächsten Prozessor weiterzuleiten.

Neuere Forschungen konzentrieren sich darauf, die Leistung von GPUs und Multicore-Systemen zu nutzen, um solche unabhängigen Codeblöcke (oder einfach unabhängige Iterationen einer Schleife) zur Laufzeit zu berechnen. Der Speicher, auf den (ob direkt oder indirekt) zugegriffen wird, kann einfach für verschiedene Iterationen einer Schleife markiert und zur Abhängigkeitserkennung verglichen werden. Anhand dieser Informationen werden die Iterationen in Ebenen gruppiert, so dass Iterationen, die derselben Ebene angehören, unabhängig voneinander sind und parallel ausgeführt werden können.

Schwierigkeiten

Eine automatische Parallelisierung durch Compiler oder Tools ist aus folgenden Gründen sehr schwierig:

• Die Abhängigkeitsanalyse ist schwierig für Code, der indirekte Adressierung, Zeiger, Rekursion oder indirekte Funktionsaufrufe verwendet, da es schwierig ist, solche Abhängigkeiten zur Kompilierzeit zu erkennen;
• Schleifen haben eine unbekannte Anzahl von Iterationen;
• Zugriffe auf globale Ressourcen sind in Bezug auf Speicherzuweisung, E/A und gemeinsame Variablen schwer zu koordinieren;
• unregelmäßige Algorithmen , die eingabeabhängige Indirektion verwenden, beeinträchtigen die Analyse und Optimierung zur Kompilierzeit.

Problemumgehung

Aufgrund der inhärenten Schwierigkeiten bei der vollautomatischen Parallelisierung gibt es mehrere einfachere Ansätze, um ein paralleles Programm in höherer Qualität zu erhalten. Eine davon besteht darin, Programmierern zu ermöglichen, ihren Programmen "Hinweise" hinzuzufügen, um die Compiler-Parallelisierung zu führen, wie beispielsweise HPF für verteilte Speichersysteme und OpenMP oder OpenHMPP für gemeinsam genutzte Speichersysteme . Ein anderer Ansatz besteht darin, ein interaktives System zwischen Programmierern und parallelisierenden Tools/Compilern aufzubauen. Bemerkenswerte Beispiele sind Pareon von Vector Fabrics , SUIF Explorer (der Compiler des Stanford University Intermediate Format), der Polaris-Compiler und ParaWise (ehemals CAPTools). Ein weiterer Ansatz ist schließlich das hardwareunterstützte spekulative Multithreading .

Compiler und Tools parallelisieren

Die meisten Forschungs Compiler für die automatische Parallelisierung betrachten Fortran - Programme, weil Fortran stärkere Garantien macht über Aliasing als Sprachen wie C . Typische Beispiele sind:

• Paradigmen-Compiler
• Polaris-Compiler
• Rice Fortran D-Compiler
• SUIF- Compiler
• Wiener Fortran-Compiler

Siehe auch

• Optimierung des Schleifennests
• Polytope-Modell
• Skalierbare Parallelität
• BMDFM
• Vektorisierung
• SequenzL

Verweise