Hindernisse für die Vektorisierung

Natürlich gibt es Schleifen, die grundsätzlich nicht vektorisiert werden können, etwa wenn gar keine Array-Operationen vorkommen. Es gibt aber einige oft vorkommende Konstruktionen, die ein automatisches Vektorisieren auch in solchen Fällen verhindern, in denen es bei etwas anderer Programmierung möglich wäre. Beispiele für solche Vektorisierungs-Hemmnisse wollen wir uns nun ansehen.
Ein Routinen-Aufruf, eine Ein-/Ausgabe-Anweisung oder ein ''switch''-Statement in einer Schleife verhindern die Vektorisierung sofort, ebenso eine Schleife mit einer Induktionsvariable vom Typ unsigned.
Wird in einer Schleife während einer Iteration auf ein Array-Element zugegriffen, das in einer anderen Iteration berechnet wurde, sprechen wir von ''Rückgriff'' (''Recurrence''). Ein solcher Rückgriff kann u.U. die Vektorisierung verhindern, wie etwa im einfachen Beispiel

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

Da der Wert von A(2) vom Wert von A(1) abhängt, würde eine Vektorisierung, d.h. eine quasi gleichzeitige Berechnung von A(1) und A(2), zum falschen Ergenis führen. Dies wäre nicht der Fall, wenn A(I) von A(I+1) abhängen würde, da dann die notwendige Reihenfolge der Schritte auch bei der Vektorisierung erhalten bleibt. Es gibt allerdings Fälle, in denen der Compiler nicht entscheiden kann, ob ein Rückgriff vorliegt, etwa bei

     DO I = 2, 99
        A(I) = A(I + K) + B(I)
     ENDDO

Hier hängt es vom Vorzeichen von K ab, ob vektorisiert werden kann oder nicht. Kann der Compiler das nicht entscheiden (z.B. weil K als Parameter übergeben wird), wird er nicht vektorisieren. Man spricht dann von einem ''anscheinenden Rückgriff'' (''apparent recurrence'').
Allerdings benutzt der Compiler einige Tricks, um aus einem Rückgriff das Beste zu machen. So kann er die Berechnung von Zwischenergebnisse in eigene Schleifen ziehen, die dann vektorisieren, oder er kann durch Skalare entstehende Rückgriffe manchmal dadurch auflösen, daß er den Skalar zu einem Vektor aufbläht. Außerdem gibt es eine große Klasse von Rückgriffen, die nichts anderes sind als Vektor-Reduktionen (Summe, Maximum etc. eines Vektors). Diese erkennt der Compiler in der Regel und vektorisiert sie entsprechend.
Ein großes Problem für die Vektorisierung ist auch das sogenannte ''Aliasing'', nämlich das Zugreifen auf einen Speicherbereich unter verschiedenen Namen. Dies tritt in der Regel bei der Verwendung von Zeigern auf, ist damit vor allem bei der Programmierung in C wichtig. ¹⁵ Wir sehen uns dazu folgendes Beispiel an:

    void bla(float *a, float *b, int n)
    {
       int i;

       for (i=0; i<n; i++)
       {
          a[i] = b[i];
       }
    }

An sich sollte man meinen, daß es kaum schönere Vektor-Schleifen gibt. Was aber, wenn diese Routine folgendermaßen aufgerufen wird:

    float x[1000];

    /* versieh x mit Werten */
    initialize_array(x, 1000);

    bla(x+100, x+99, 100);

Durch die Überlappung der Arrays a und b ist ein Rückgriff entstanden, der eine Vektorisierung verhindert. Da der Compiler bei der Optimierung der Routine bla vom schlimmsten Fall ausgehen muß, darf er die Schleife nicht vektorisieren. Nun wird aber in C oft mit Pointern gearbeitet, so daß dies eine starke Einschränkung der Vektorisierung zur Folge hat.
Um mögliche Überlappungen verhindern zu können, geht der Compiler im ANSI-Mode folgendermaßen vor: Er sieht alle Pointer auf einen Typ (Pointer auf int, float etc.) als Zeiger in ein großes Array an, das alle globalen Variablen, alle lokalen statischen Variablen und alle lokalen Variablen, deren Adresse benutzt wird, enthält, die vom entsprechenden Typ sind. Zwei beliebige Zeiger in diesen Bereich werden als potentielle Aliasse angesehen und verhindern dadurch u.U. eine Vektorisierung. Folgendes Beispiel zeigt, wie weitreichende Folgen dieses Verfahren haben kann:

    void bla(int *int_array)
    {
       int i;
       int *int_ptr;

       int_ptr = &i;

       for (i=0; i<4711; i++)
       {
          int_array[i] = 42;
       }
    }

Diese harmlos wirkende Schleife wird nicht vektorisiert: Da von der Variablen i der Adress-Operator genommen wird, gehört auch sie in den Bereich des imaginären Arrays aller int-Pointer, könnte also auch vom int_array erreicht werden. Die Wert-Zuweisung im int_array ist somit potentiell eine Änderung an i, das seinen Wert mithin innerhalb der Schleife ändern kann und somit keine echte Schleifenvariable darstellt. Noch schlimmer wird es, wenn man nicht mit ANSI-C arbeitet: Da die Typen von Pointern im alten K&R-C nicht streng unterschieden werden, gibt es überhaupt nur ein einziges gedachtes Array für alle Pointer, nicht mehrere für die verschiedenen Typen. Die Anzahl der potentiellen Überlappungen ist daher noch größer, es werden noch weniger Schleifen vektorisiert. Problematisch wird es, wenn man mit ANSI-C arbeitet, aber die Pointer-Typisierung nicht strikt beachtet, wie etwa in

     int   *int_ptr;
     float *float_ptr;

     float_ptr = int_ptr;

Der Compiler gibt zwar eine Warnung aus (''operands of $=$ point to incompatible types.''), akzeptiert es aber ansonsten. Auf diese Weise kann Aliasing auftreten, ohne daß der Compiler es merkt! Zum Glück wird das Aliasing-Problem durch den Application-Compiler deutlich entschärft. Man kann aber auch ohne diesen durch den Programmierstil eine bessere Vektorisierung seiner C-Programme erreichen (s. Abschnitt 4.3.1).