Gestern habe ich mit einer neuen Serie angefangen, die sich intensiv mit dem Thema OpenMP beschäftigt. Im ersten Teil ging es sehr fundamental um die Voraussetzungen, die eine Schleife erfüllen muss, um per OpenMP multithreading-tauglich zu sein. Heute geht es um die Frage, welche Dinge zu beachten sind, damit eine Schleife ordnungsgemäß in mehrere Threads aufgeteilt werden kann.

Zunächst einmal: Das Threaden von Schleifenkonstrukten bedeutet nichts anderes, als dass unabhängige Schleifeniterationen auf mehreren Threads gleichzeitig ausgeführt werden können, was natürlich Rechenzeit pro Takt spart. Hierzu wird die Schleife in eine neue Form gebracht, die das Parallelisieren derselben überhaupt erst ermöglicht. Dies ist aber nur umsetzbar, wenn die Schleife keine Abhängigkeiten aufweist.

Daher muss man als Entwickler zunächst einmal mit einem passenden Tool wie VTune Performance Analyzer diejenige Schleife finden, die insgesamt die meiste Rechenzeit verschlingt. Anschließend wird diese umstrukturiert, um festzustellen, dass keine iterationsübergreifenden Abhängigkeiten bestehen. Erst dann sollte diese Schleife mithilfe eines OpenMP-Pragmas parallelisiert werden.

Dabei geht es um bereits dargestellte Datenabhängigkeiten, die in Data Race Conditions oder Dead Locks münden können. Man unterscheidet zwischen drei wesentlichen Abhängigkeiten:

Flussabhängigkeit (Schreiben-vor-Lesen): Eine Anweisung ist von einer anderen abhängig, wenn der erste Befehl ein Datum speichert, das der nachfolgende lesen will.

Ausgabeabhängigkeit: Zwei Befehle speichern in dieselbe Speicherzelle ihre Daten.

Antiabhängigkeit (Lesen-vor-Schreiben): Ein Befehl liest ein Datum, bevor dieses überhaupt gespeichert wird.

Um zu zeigen, wie sich das Umstellen von Schleifencode auf die richtige Ausführung des gesamten Programms auswirkt, folgen an dieser Stelle zwei Beispiele: ein nicht-funktionierendes und ein OpenMP-taugliches.

Nicht-funktionierende OpenMP-Schleife wegen einer iterationsübergreifenden Abhängigkeit!

x[0] = 0;
y[0] = 1;
#pragma omp parallel for private(k)

……for ( k = 1; k < 100; k++ ) {
……….x[k] = y[k-1] + 1; // Operation 1
……….y[k] = x[k-1] + 2; // Operation 2

….. }

OpenMP-basiertes Threading mittels einer Strip-Mining-Transformation

x[0] = 0;
y[0] = 1;
x[49] = 74; // abgeleitet von der Gleichung x(k)=x(k-2)+3
y[49] = 74; // abgeleitet von der Gleichung y(k)=y(k-2)+3

#pragma omp parallel for private(m, k)

…..for ( m=0; m<2; m++ ) {
……….for ( k = M*49+1; k < m*50+50; k++) {

……….….x[k] = y[k-1] + 1; // Operation 1
…………..y[k] = x[k-1] + 2; // Operation 2
……..}
….}