Hierarchischer SpeicherBearbeiten

Hierarchischer Speicher ist eine Hardware-Optimierung, die die Vorteile der räumlichen und zeitlichen Lokalität nutzt und auf mehreren Ebenen der Speicherhierarchie eingesetzt werden kann. Paging profitiert offensichtlich von zeitlicher und räumlicher Lokalität. Ein Cache ist ein einfaches Beispiel für die Ausnutzung der zeitlichen Lokalität, da es sich um einen speziell entworfenen, schnelleren, aber kleineren Speicherbereich handelt, der im Allgemeinen dazu dient, kürzlich referenzierte Daten und Daten in der Nähe von kürzlich referenzierten Daten aufzubewahren, was zu potenziellen Leistungssteigerungen führen kann.

Datenelemente in einem Cache entsprechen nicht notwendigerweise Datenelementen, die im Hauptspeicher räumlich nahe beieinander liegen; Datenelemente werden jedoch jeweils eine Cache-Zeile in den Cache gebracht. Dies bedeutet, dass die räumliche Lokalität ebenfalls wichtig ist: Wenn auf ein Element verwiesen wird, werden auch einige benachbarte Elemente in den Cache gebracht. Schließlich spielt auch die zeitliche Lokalität auf der untersten Ebene eine Rolle, da Ergebnisse, die sehr nahe beieinander liegen, in den Maschinenregistern gehalten werden können. In einigen Programmiersprachen (z. B. C) kann der Programmierer vorschlagen, dass bestimmte Variablen in Registern gehalten werden.

Datenlokalität ist ein typisches Merkmal von Speicherreferenzen in regulären Programmen (obwohl es viele unregelmäßige Speicherzugriffsmuster gibt). Sie macht das hierarchische Speicherlayout profitabel. In Computern wird der Speicher in eine Hierarchie eingeteilt, um Datenzugriffe zu beschleunigen. Die unteren Ebenen der Speicherhierarchie sind tendenziell langsamer, aber größer. Ein Programm ist also leistungsfähiger, wenn es den Speicher nutzt, während er in den oberen Ebenen der Speicherhierarchie zwischengespeichert ist, und es vermeidet, andere Daten in die oberen Ebenen der Hierarchie zu bringen, die Daten verdrängen, die erst in der Zukunft verwendet werden. Dies ist ein Ideal, das manchmal nicht erreicht werden kann.

Typische Speicherhierarchie (Zugriffszeiten und Cache-Größen sind Näherungswerte für typische Werte, die 2013 zum Zweck der Diskussion verwendet wurden; die tatsächlichen Werte und die tatsächliche Anzahl der Ebenen in der Hierarchie variieren):

• CPU-Register (8-256 Register) – sofortiger Zugriff, mit der Geschwindigkeit des innersten Kerns des Prozessors
• L1 CPU-Caches (32 KiB bis 512 KiB) – schneller Zugriff, mit der Geschwindigkeit des innersten Speicherbusses, der jedem Kern exklusiv gehört
• L2 CPU-Caches (128 KiB bis 24 MiB) – etwas langsamerer Zugriff, mit der Geschwindigkeit des Speicherbusses, der von Zwillingen von Kernen geteilt wird
• L3 CPU-Caches (2 MiB bis 32 MiB) – noch langsamerer Zugriff, mit der Geschwindigkeit des Speicherbusses, der von noch mehr Kernen desselben Prozessors geteilt wird
• Physischer Hauptspeicher (RAM) (256 MiB bis 64 GiB) – langsamerer Zugriff, dessen Geschwindigkeit durch die räumlichen Abstände und die allgemeinen Hardwareschnittstellen zwischen dem Prozessor und den Speichermodulen auf der Hauptplatine begrenzt ist
• Festplatte (virtueller Speicher, Dateisystem) (1 GiB bis 256 TiB) – sehr langsam, wegen des engeren (in Bitbreite), physikalisch viel längeren Datenkanals zwischen der Hauptplatine des Computers und den Festplattengeräten, und wegen des fremden Softwareprotokolls, das zusätzlich zur langsamen Hardwareschnittstelle benötigt wird
• Fernspeicher (andere Computer oder die Cloud) (praktisch unbegrenzt) – die Geschwindigkeit variiert von sehr langsam bis extrem langsam

Moderne Maschinen neigen dazu, Blöcke aus dem unteren Speicher in die nächste Ebene der Speicherhierarchie zu lesen. Wenn dadurch benutzter Speicher verdrängt wird, versucht das Betriebssystem vorherzusagen, auf welche Daten am wenigsten (oder am spätesten) zugegriffen wird, und verschiebt sie in der Speicherhierarchie nach unten. Vorhersagealgorithmen sind in der Regel einfach, um die Hardwarekomplexität zu verringern, werden aber immer komplizierter.

MatrixmultiplikationBearbeiten

Ein gängiges Beispiel ist die Matrixmultiplikation:

for i in 0..n for j in 0..m for k in 0..p C = C + A * B;

Durch Umschalten der Schleifenreihenfolge für j und k wird die Beschleunigung bei großen Matrixmultiplikationen dramatisch, zumindest für Sprachen, die zusammenhängende Array-Elemente in die letzte Dimension setzen. Dies ändert nichts am mathematischen Ergebnis, verbessert aber die Effizienz. In diesem Fall bedeutet „groß“ ungefähr mehr als 100.000 Elemente in jeder Matrix oder genügend adressierbarer Speicher, so dass die Matrizen nicht in L1- und L2-Caches passen.

for i in 0..n for k in 0..p for j in 0..m C = C + A * B;

Der Grund für diese Beschleunigung ist, dass im ersten Fall die Lesevorgänge von A im Cache sind (da der k-Index die letzte zusammenhängende Dimension ist), aber B ist es nicht, so dass es eine Cache-Miss-Malus auf B gibt. C ist irrelevant, weil es aus der inneren Schleife herausgezogen werden kann – die Schleifenvariable dort ist k.

for i in 0..n for j in 0..m temp = C for k in 0..p temp = temp + A * B; C = temp

Im zweiten Fall sind die Lese- und Schreibvorgänge von C beide im Cache, die Lesevorgänge von B sind im Cache, und der Lesevorgang von A kann aus der inneren Schleife herausgezogen werden.

for i in 0..n for k in 0..p temp = A for j in 0..m C = C + temp * B;

Das zweite Beispiel hat also keine Cache-Miss-Penalty in der inneren Schleife, während das erste Beispiel eine Cache-Penalty hat.

Auf einem Prozessor des Jahres 2014 ist der zweite Fall etwa fünfmal schneller als der erste Fall, wenn er in C geschrieben und mit gcc -O3 kompiliert wird. (Eine sorgfältige Untersuchung des disassemblierten Codes zeigt, dass GCC im ersten Fall SIMD-Anweisungen verwendet und im zweiten Fall nicht, aber die Cache-Strafe ist viel schlimmer als der SIMD-Gewinn.)

Die zeitliche Lokalität kann im obigen Beispiel auch durch eine Technik namens Blocking verbessert werden. Die größere Matrix kann in gleich große Teilmatrizen unterteilt werden, so dass die kleineren Blöcke mehrmals referenziert (multipliziert) werden können, während sie sich im Speicher befinden.

for (ii = 0; ii < SIZE; ii += BLOCK_SIZE) for (kk = 0; kk < SIZE; kk += BLOCK_SIZE) for (jj = 0; jj < SIZE; jj += BLOCK_SIZE) maxi = min(ii + BLOCK_SIZE, SIZE); for (i = ii; i < maxi; i++) maxk = min(kk + BLOCK_SIZE, SIZE); for (k = kk; k < maxk; k++) maxj = min(jj + BLOCK_SIZE, SIZE); for (j = jj; j < maxj; j++) C = C + A * B;

Die zeitliche Lokalität der obigen Lösung ist gegeben, weil ein Block mehrmals verwendet werden kann, bevor er weitergeht, so dass er seltener in den und aus dem Speicher bewegt wird. Die räumliche Lokalität wird verbessert, weil Elemente mit aufeinanderfolgenden Speicheradressen in der Regel gemeinsam in der Speicherhierarchie nach oben gezogen werden.