Profilen parallelisierter Programme

Ein großes Problem beim Parallelisieren ist, daß der Erfolg nicht direkt sichtbar wird: Da die normalerweise ausgegebenen CPU-Zeiten immer die Summe über alle CPUs sind, steigt die Zeit bei Verwendung von ''-O3'' durch den Parallelisierungs-Overhead immer an! Um zu sehen, wie gut ein Programm parallelisiert wird, muß man es mit dem CXpa untersuchen. Dazu übersetzt und linkt man es wieder mit der Option ''-pa'' und startet den CXpa dann mit

        cpa -f linalg  .

Die Option ''-f'' bewirkt, daß der CXpa mit ''fixed scheduling'' arbeitet, also - wie schon beim CXdb möglich - innerhalb einer zugeteilten Zeitscheibe alle CPUs zur Verfügung stehen.

Im CXpa können jetzt alle parallelen Schleifen mit

        monitor pregion all

ausgewählt werden. Statt ''all'' ist mit ''in ROUTINE'' oder ''at LINE'' wieder eine Auswahl der zu überwachenden parallelen Bereiche möglich. Nach

        run
        analyze pregion [ROUTINE ...]

erhält man die Meß-Ergebnisse in Form von zwei Tabellen.

Als Beispiel betrachten wir folgenden Teil der Routine TESTMT aus dem Programm linalg:

      0024          MAXVAL = 0.0
      0025    C
      0026    C  BERECHNE REST = A*AINV - ID
      0027    C
      0028          DO 11 I = 1, N
      0029             DO 12 J = 1, N
      0030                REST = 0.0
      0031                DO 13 K = 1, N
      0032                   REST = REST + A(I, K)*AINV(K, J)
      0033     13         CONTINUE
      0034                IF (I .EQ. J) THEN
      0035                   REST = DABS(REST - 1.0)
      0036                ELSE
      0037                       REST = DABS(REST)
      0038                END IF
      0039                MAXVAL = MAX(MAXVAL, REST)
      0040     12      CONTINUE
      0041     11   CONTINUE

Beim Übersetzen mit ''-O3'' bekommen wir folgenden Optimierungs-Bericht:

Optimization for Procedure TESTMT
Line		Iter.	Reordering	Optimizing/Special	Exec.
Num.		Var.	Transformation	Transformation	Mode
28		I	PARALLEL
29		J	Scalar
31		K	FULL VECTOR	Reduction
Line		Iter.	Analysis
Num.		Var.
28		I	Unable to distribute
29		J	Unable to distribute

Die äußere I-Schleife wird also parallelisiert, während die J-Schleife skalar bleibt. Nur die innere K-Schleife wird vektorisiert. Nach entsprechender Instrumentierung erhalten wir vom CXpa folgendes Ergebnis:

Parallel Region Performance Analysis
For testmt.f:testmt
Line	Num Exec	Cpu Time	Wall Clock Time	Process Virtual	CPU/PVT
Num				Time
28	2	0.153986	0.395657	0.039482	3.90016

Line	Cpu Time	Wall Clock Time	Chore Count
Num
28	0.039302	0.395461	51
	0.039135	0.395470	51
	0.038609	0.394882	50
	0.036940	0.393540	48

Die erste Tabelle zeigt, daß die I-Schleife (Zeile 28) zweimal durchlaufen wurde (TESTMT wird zweimal aufgerufen). Die CPU-Zeit für die Schleife ist wieder die Summe über alle CPUs, also näherungsweise gleich der CPU-Zeit der Schleife ohne Parallelisierung. Die ''Wall Clock Time'' ist die ''real''-Zeit, also stark von der momentanen Auslastung abhängig. Die zur Bestimmung der Parallelität wichtige Zeit ist die ''Process Virtual Time'' (PVT). Sie wird durch einen Timer aufgenommen, der die ''real''-Zeit ''innerhalb eines Prozesses'' mißt, d.h. er läuft nur weiter, wenn der Prozeß RUNNING ist, wobei die Zahl der CPUs, die gerade benutzt werden, keine Rolle spielt. Allerdings berücksichtigt die PVT nur User-, keine System-Anteile (insbesondere also keine I/O-Zeiten) und enthält den Instrumentierungs-Overhead vom CXpa, der nur insgesamt, aber nicht für jede CPU einzeln abgezogen werden kann.
Bis auf diese Ungenauigkeiten, die insbesondere bei CPU-intensiven Schleifen gering sind, gibt die letzte Spalte ''CPU/PVT'' die Geschwindigkeitserhöhung durch die Parallelisierung an. Ein Wert von 3.9 bei vier Prozessoren ist natürlich nahezu ideal; er entspricht einer Parallelisierungs-Effektivität von

$$(\mbox{CPU}/\mbox{PVT})/ \mbox{NCPU} * 100\% = 3.9 / 4 * 100\% = 97.5\% \mbox{.}$$

Eine Möglichkeit, die Genauigkeit etwas zu erhöhen, besteht darin, die CPU-Zeit für die nicht-parallelisierte Schleife explizit zu messen (also: -O2, CXpa für die zu untersuchende Schleife). Wer auf ganz genaue Ergebnisse angewiesen ist, etwa für offizielle Benchmarks, dem bleibt nichts anderes übrig, als die Programmlaufzeiten im Single-User-Betrieb zu messen. Für die meisten Belange sollte aber der einfache CPU/PVT-Wert des CXpa ausreichen.
Die zweite Tabelle gibt an, wie stark sich die Arbeit auf die einzelnen CPUs verteilt hat. Die Beispiel-Schleife wurde zweimal mit jeweils 100 Iterationen durchlaufen, d.h. die Gesamtzahl der Chores beträgt 200. Wie man sieht, haben diese sich sehr gut auf die CPUs verteilt, sowohl nach der Zahl der Chores als auch nach der CPU-Zeit. Eine ungleiche Verteilung der Arbeit ist oft die Ursache für einen schlechten Parallelisierungsgrad. Dieses Problem tritt vor allem auf, wenn die Zahl der Chores klein ist (etwa 5 Chores auf 4 Prozessoren) oder wenn eine äußere ''Strip-Mining''-Schleife mit zu kleiner Vektorlänge aufgeteilt wird (z.B. 400 Vektor-Elemente bei 4 Prozessoren: drei bekommen jeweils 128 Elemente, einer die restlichen 16). In solchen Fällen ist u.U. über Compiler-Direktiven eine bessere Aufteilung zu erreichen (s. Abschnitt 4.4.4).
Leider haben meine Messungen ergeben, daß die Concurrency-Werte des CXpa in manchen Fällen völlig falsch sind (zu großer Overhead?). Man braucht also gelegentlich eine Methode, um unabhängig den Parallelisierungsgrad zu messen. Dazu muß man die System-Routine cvxprusage benutzen, am besten, indem man sich eine kleine Hilfsroutine schreibt, wie etwa die folgende:

/*
 *  Routine zur Messungen von parallelen Zeiten
 */

#include <sys/time.h>
#include <sys/resource.h>


void paruse(long long *nsamples, long long *nthreads)
{

   /*
    * gibt die Gesamtzahl der Samples und der Threads bis zum Aufruf-Zeitpunkt
    * zurueck
    */

   struct cvxprusage   usage;

   cvxprusage(&usage);

   *nsamples = usage.pru_usamples;
   *nthreads = usage.pru_utotal;

}

Damit bestimmt man den Parallelisierungsgrad auf folgende Weise:

       long long nsamp1, nsamp2, nthr1, nthr2;

       paruse(&nsamp1, &nthr1);
       compute();
       paruse(&nsamp2, &nthr2);
       concurrency = (nthr2 - nthr1)/(double)(nsamp2 - nsamp1);

Möchte man paruse in einem FORTRAN-Programm benutzen, muß man es in paruse_ umnennen und aufrufen mit

      INTEGER*8 NSAMP, NTHR
      CALL PARUSE(NSAMP, NTHR)    .

Um das Programm - ebenso wie bei CXpa-Messungen - unter ''fixed scheduling'' ablaufen zu lassen, startet man es auf folgende Weise:

      mpa -f PROGRAMMNAME [ARGUMENTE]    .