Automatische Parallelisierung

Bei der Compiler-Option -O3 wird zusätzlich eine ''automatische Parallelisierung'' durchgeführt, d.h. es wird versucht, das Programm in mehrere Threads zu zerlegen, die unabhängig voneinander von mehreren CPUs gleichzeitig bearbeitet werden können. Im Gegensatz zur Vektorisierung, die schon so weit geht, daß man oft auch ohne manuelle Nachbearbeitung zufriedenstellende Resultate erzielen kann, ist die Parallelisierung eher in den Anfängen.¹⁸ Die einzige Konstruktion, die der Compiler selbsttätig parallelisiert, ist eine äußere Schleife (innere werden vektorisiert, s.o.). Welche Schleife die äußere ist, hängt dabei von vorhergehenden Optimierungen ab; beispielsweise kann sie durch Vertauschungen nach außen gekommen oder durch ''Strip Mining'', also Zerhacken von Schleifen in 128-er Blöcke, überhaupt erst entstanden sein. Es werden so viele Threads erzeugt wie Prozessoren vorhanden sind - auf der C3840 also vier -, die alle den gleichen Code ausführen (symmetrische Parallelisierung, s. Abschnitt 4.1). Auf wievielen Prozessoren die Threads wirklich abgearbeitet werden, ist aufgrund des ASAP-Verfahrens stark von der momentanen Systemlast abhängig (vgl. Abschnitt 4.1). Ein Thread bearbeitet immer die nächste freie Iteration der Schleife (einen ''Chore''), bis die ganze Schleife abgearbeitet ist. Welches der nächste Chore ist, wird in einem Kommunikations-Register festgehalten, so daß die Synchronisation der Threads gewährleistet ist. Da die einzelnen Chores u.U. verschieden lange laufen und die CPUs unterschiedlich ausgelastet sein können, ist auch die Verteilung der Chores auf die Threads i.a. bei jedem Programmlauf anders.

Als Beispiel betrachten wir folgenden Ausschnitt aus der Routine LUINV des Programms linalg:

      0028    C
      0029    C SET UP IDENTITY MATRIX
      0030    C
      0031          DO 11 I = 1, N
      0032             DO 12 J = 1, N
      0033                B(I, J) = 0.0
      0034     12      CONTINUE
      0035             B(I, I) = 1.0
      0036     11   CONTINUE

Der zugehörige Ausschnitt aus dem Optimierungs-Bericht ist:

Line		Iter.	Reordering	Optimizing/Special	Exec.
Num.		Var.	Transformation	Transformation	Mode
31		I	Dist
31	-1	I	FULL VECTOR Inter
31	-2	I	PARA/VECTOR
32	-1	J	PARALLEL
Line		Iter.	Analysis
Num.		Var.
31	-1	I	Interchanged to innermost
31	-2	I	Parallel outer strip mine loop

Folgende Umformungen wurden vom Compiler vorgenommen:

1. Die I-Schleife wurde in zwei Teile zerhackt (''distributed''):
   31-1 : Doppelschleife B(I,J) = 0.0
   31-2 : Einfachschleife B(I,I) = 1.0
2. In 31-1 wurde die I-Schleife nach innen getauscht und voll vektorisiert, die (jetzt äußere) J-Schleife wurde voll parallelisiert.
3. In 31-2 wurde die I-Schleife in 128-er Blöcke zerhackt (''strip mining''), der innere Teil wurde vektorisiert, der äußere Teil über die Blöcke parallelisisert (deshalb ''PARA/VEKTOR'').

Natürlich gibt es wieder einige Konstruktionen, die das Parallelisieren einer äußeren Schleife verhindern. I.w. handelt es sich um dieselben Faktoren wie beim Vektorisieren, u.a. Unterprogramm-Aufrufe oder I/O-Anweisungen in der Schleife oder Rückgriffe, d.h. Abhängigkeiten von Array-Elementen von in der Schleife vorher berechneten Elementen. Neu ist, daß auch nach vorne gehende Abhängigkeiten in einer Schleife das Parallelisieren behindern, wie etwa im folgenden Beispiel:

     DO I=1, N-1
        A(I) = A(I+1) + 31.93
     ENDDO

Diese Schleife kann zwar vektorisiert, aber nicht parallelisiert werden!