Code-Umstellungen durch den Compiler

Die für die Vektorisierung grundlegende Fähigkeit des Compilers ist das Erkennen von Schleifen. Dabei sind nicht nur DO-Schleifen in Fortran oder for-Schleifen in C mögliche Kandidaten, sondern auch while- oder until-Schleifen, ja sogar mit GOTOs selbstprogrammierte Schleifen können vom Compiler erkannt werden. Wichtig ist dafür das Vorhandensein einer Schleifen-Variablen, die bei jeder Iteration um einen konstanten Betrag geändert wird. Manchmal gelingt aber sogar die Vektorisierung in komplizierteren Fällen, wie das Beispiel am Ende dieses Abschnitts eindrucksvoll beweist.
Die einfachste Umformung ist das sogenannte ''Strip Mining''. Dabei wird eine Schleife, die u.U. mehr als 128 Iterationen lang ist, in eine innere Schleife mit 128 Iterationen (beim letzten Mal evtl. weniger) und eine äußere über die entsprechende Anzahl von 128er Blöcken aufgeteilt:¹⁴

vorher:

       DO I = 1, N
          BLA(I)
       ENDDO

nachher:

       N_BLOCK = N / 128
       N_REST = MOD(N, 128)
  C
  C 128er Bloecke
  C
       DO BL = 0, N_BLOCK-1
         DO I = 1, 128
            BLA(128*BL + I)
         ENDDO
       ENDDO
  C
  C Rest
  C
       DO I = 1, N_REST
          BLA(128*N_BLOCK + I)
       ENDDO

Eine Schleife, die neben normalen Operationen weitere Schleifen enthält, kann vektorisiert werden, indem sie in Teile gleicher Tiefe zerhackt wird (''loop distribution''), z.B.:

vorher:

       DO I = 1, N
          BLA1(I)
          DO J = 1, M
             BLA2(I, J)
          ENDDO
       ENDDO

nachher:

       DO I = 1, N
          BLA1(I)
       ENDDO

       DO I = 1, N
          DO J = 1, M
             BLA2(I, J)
          ENDDO
       ENDDO

Eine Operation, die häufig vorkommt, ist das Vertauschen von innerer und äußerer Schleife, z.B. um den Speicherzugriff zu optimieren oder die Schleife mit der größeren Vektorlänge nach innen zu bringen. Z.B. würde bei

      DO I = 1, N
        DO J = 1, M
           A(I,J) = 2* B(I,J)
        ENDDO
      ENDDO

ohne weitere Kenntnis von N und M die I-Schleife nach innen getauscht, da Fortran-Arrays spaltenweise im Speicher liegen (d.h. es folgen im Speicher A(1,1), A(2,1), A(3,1),...) und die Vektorzugriffe dann auf direkt hintereinanderliegende Elemente erfolgen. Wäre dagegen N$=$10, M$=$1000 dem Compiler bekannt, würde er die Schleifen nicht tauschen und die längere Schleife vektorisieren (vgl. Abschnitt 3.3.1).

Schleifen, in denen IF-Abfragen vorkommen, sind schwierig zu vektorisieren. Da solche Schleifen aber oft vorkommen, gibt es spezielle Hardware, um damit fertig zu werden (Masken-Register, s. Abschnitt 4.1). Außerdem hat der Compiler verschiedene Strategien zur Verfügung, z.B. das Herausziehen aus der Schleife wie im folgenden Beispiel:

vorher:

       DO I = 1, N
          IF (SEIN_ODER_NICHT_SEIN) THEN
             BLA1(I)
          ELSE
             BLA2(I)
          ENDIF
       ENDDO

nachher:

       IF (SEIN_ODER_NICHT_SEIN) THEN
          DO I = 1, N
             BLA1(I)
          ENDDO
       ELSE
          DO I = 1, N
             BLA2(I)
          ENDDO
       ENDIF

oder das Herauslösen von Anfangs- oder Endabfragen (''Loop Peeling''), etwa:

vorher:

       DO I = 1, N
          IF (I .EQ. 1) THEN
             A(I) = B(N)
          ELSE
             A(I) = B(I-1)
          ENDIF
       ENDDO

nachher:

       A(1) = B(N)
       DO I = 2, N
          A(I) = B(I-1)
       ENDDO

Schließlich gibt es gewisse Konstruktionen, die immer wieder vorkommen, z.B:

       MAX = A(1)
       DO I = 2, N
          IF (A(I) .GT. MAX) THEN
             MAX = A(I)
          ENDIF
       ENDDO

Solche Fälle erkennt der Compiler durch Vergleich mit einem Satz von Standardmustern.

Schließlich zeigt das folgende Beispiel, zu welch erstaunlichen Leistungen der Compiler fähig ist:

     K = 0
     DO I = 1, 100
        IF (TEST(I) .EQ. .TRUE.) THEN
           K = K + 1
           A(I) = B(K)
        ENDIF
     ENDDO

Der erzeugte Maschinencode macht folgendes: Zunächst werden die Werte von I bestimmt, für die der TEST wahr ist und ihre Anzahl gezählt. Dann wird der entsprechende Teil von B geladen und nach A expandiert, wobei der Vektor der I-Werte als Index-Vektor wirkt (scatter-Operation, s. Abschnitt 4.1). Schließlich wird der Vektor A abgespeichert.