next up previous contents
Next: Arbeiten mit FEM-Programmpaketen auf Up: Datenlokalität - Wie Compiler Previous: Loop Unrolling

Loop-Blocking

Das wichtigste Ziel bei der Optimierung mit -O2 ist die Ausnutzung der Caches - schließlich braucht der Zugriff auf den Speicher 50 mal so lange wie der auf den Cache. Dabei kann man Daten, die im Cache liegen, auf zwei verschiedene Weisen gebrauchen:

i) räumliches Wiederverwenden

Bei jedem Laden aus dem Speicher werden 32 Byte auf einmal in den Cache geholt, auch wenn man zunächst nur die ersten 8 Byte (einen Double-Wert etwa) braucht. Werden die anderen Werte später benötigt, stehen sie nun schnell bereit - vorausgesetzt, sie wurden inzwischen nicht von anderen Daten überschrieben.

ii) zeitliches Wiederverwenden

Daten, die mehrmals gebraucht werden, können bei späteren Zugriffen direkt aus dem Cache geholt werden - falls sie nicht inzwischen verdrängt wurden.

Um ein solches Wiederverwenden zu erreichen, zerlegt der Compiler große Schleifen in Blöcke, so daß auch die benötigten Arrays in Blöcken abgearbeitet werden, die dann jeweils alle komplett im Cache liegen können. Als Beispiel diene uns die Matrix-Multiplikation von REAL*4-Arrays, wobei ich der Übersicht halber eine einfache Blockinggröße verwende. gif

    vorher:

   DO I = 1, 1000
      DO J = 1, 1000
         DO K = 1, 1000
            C(I, J) = C(I, J) + A(I, K) * B(K, J)
         ENDDO
      ENDDO
   ENDDO

    nachher:

   DO IOUT = 1, 1000, 100
      DO KOUT = 1, 1000, 100
         DO J = 1, 1000
            DO I = IOUT, IOUT + 99
               DO K = KOUT, KOUT + 99
                  C(I, J) = C(I, J) + A(I, K) * B(K, J)
               ENDDO
            ENDDO
         ENDDO
      ENDDO
   ENDDO

Um zu verstehen, was hier passiert, sehen wir uns nur die inneren drei Schleifen der geblockten Version an und halten die beiden äußeren Schleifen fest:

Matrix Blockgröße Speicherbedarf
A 100 x 100 40kB
B 100 x 1000 400kB
C 100 x 1000 400kB

In diesem Fall passen alle drei Blöcke komplett in den Cache, sie werden erst bei anderen Blockindizes IOUT und KOUT durch neue Blöcke ersetzt. Damit wird eine Menge an Möglichkeiten geschaffen, Daten aus dem Cache wiederzuverwenden:

B wird innerhalb der K-Schleife räumlich wiederverwendet, denn bei einem Zugriff werden gleich die Daten für die nächsten drei B-Werte in den Cache geladen. B wird außerdem in der I-Schleife zeitlich wiederverwendet, weil bei jedem Wert von I der gesamte B-Block wieder gebraucht wird, der beim ersten I-Wert schon vollständig in den Cache geholt wurde. Analog werden A in der I-Schleife räumlich, in der J-Schleife zeitlich und C in der I-Schleife räumlich, in der K-Schleife zeitlich wiederverwendet.

Ohne die Blockbildung würden alle Schleifen jeweils über die gesamten Arrays laufen, die aber mit zusammen 12 MB nicht in den Cache passen würden. Allein durch die andere Reihenfolge der Abarbeitung würden die meisten Daten aus dem Cache verdrängt, bevor sie wieder verwendet werden können.

Um den praktischen Erfolg dieser Maßnahmen sehen zu können, vergleichen wir die CPU-Zeiten für die obige kleine Routine bei -O1 und bei -O2:

    -O2: 36 s             -O1: 4min 49s

Wie man sieht, lohnt sich der Aufwand. Um ehrlich zu sein, hat der Compiler hier sogar noch einiges mehr getan als beschrieben. Im Optimierungs-Report taucht zum Beispiel noch eine Transformation ``Unroll-and-jam'' auf. Wer nach dem bisherigen noch Lust auf mehr hat, kann diese und alle übrigen Optimierungen nachlesen im ``Exemplar Programming Guide'', der bei mir eingesehen - und notfalls ausgeliehen - werden kann.

Peter Junglas


next up previous contents
Next: Arbeiten mit FEM-Programmpaketen auf Up: Datenlokalität - Wie Compiler Previous: Loop Unrolling

rztms 26.2.96