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.
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