Wie funktioniert der Cache-Speicher?

Question

Heute, als ich im Computer-Organisationsunterricht war, sprach der Lehrer über etwas Interessantes für mich. Wenn es darum geht, darüber zu sprechen Warum Cache-Speicher arbeitet, sagte er, dass:

for (i=0; i<M; i++) 
    for(j=0; j<N; j++) 
     X[i][j] = X[i][j] + K; //X is double(8 bytes) 

es nicht gut ist die erste Zeile mit dem zweiten zu ändern. Was sind deine Meinungen dazu? Und warum ist es so?

Answer 1

Ort der Referenz. Da die Daten in Zeilen gespeichert sind, befinden sich die Spalten j für jede Zeile in benachbarten Speicheradressen. Das Betriebssystem lädt typischerweise eine ganze Seite aus dem Speicher in den Cache, und benachbarte Adressreferenzen beziehen sich wahrscheinlich auf dieselbe Seite. Wenn Sie um den Zeilenindex in der inneren Schleife inkrementieren, ist es möglich, dass sich diese Zeilen auf verschiedenen Seiten befinden (da sie jeweils durch j doubles getrennt sind), und der Cache muss ständig Seiten von Speicher heranholen und wegwerfen die Daten. Dies wird als Thrashing bezeichnet und ist schlecht für die Leistung.

In der Praxis und mit größeren, modernen Caches, die Größen der Zeilen/Spalten müssten relativ groß sein, bevor dies ins Spiel kommen würde, aber es ist immer noch gute Praxis.

[EDIT] Die obige Antwort ist spezifisch für C und kann für andere Sprachen abweichen. Der einzige, den ich kenne, ist FORTRAN. FORTRAN speichert die Dinge in der Reihenfolge der Spalten (die obige Zeile ist größer) und es wäre richtig, die Reihenfolge der Anweisungen in FORTRAN zu ändern. Wenn Sie Effizienz benötigen/brauchen, ist es wichtig zu wissen, wie Ihre Sprache den Datenspeicher implementiert.

Answer 2

Es ist so, weil Caches wie Örtlichkeit. Die gleiche Anzahl von Speicher, auf die zugegriffen wird, aber weiter voneinander entfernt ist, trifft auf verschiedene "Zeilen" des Caches oder kann sogar den Cache insgesamt verfehlen. Es ist daher gut, wann immer Sie die Wahl haben, Daten so zu organisieren, dass Zugriffe, die wahrscheinlich zeitlich nahe beieinander liegen, auch im Weltraum stattfinden. Dies erhöht die Chance auf einen Cache-Treffer und erhöht die Performance.

Es gibt natürlich eine Fülle von Informationen zu diesem Thema zur Verfügung, siehe zum Beispiel this wikipedia entry on locality of reference. Oder, denke ich, dein eigenes Kursbuch. :)

Answer 3

In C sind n-dimensionale Matrizen Zeilenmajor, was bedeutet, dass der letzte Index in die Matrix benachbarte Leerzeichen im Speicher darstellt. Dies ist anders als bei einigen anderen Sprachen, zum Beispiel FORTRAN, die Spaltenspalten sind. In Fortran, ist es effizienter, durch eine 2D-Matrix wie folgt durchlaufen:

do jj = 1,N 
    do ii = 1,M 
    x(ii,jj) = x(ii,jj) + K; 
    enddo 
enddo 

Answer 4

Der Cache-Speicher ist sehr schnell und sehr teuer Speicher, der mit der CPU der Nähe sitzt. Anstatt jedesmal ein kleines Stück Daten aus dem RAM zu holen, holt die CPU einen Datenblock und speichert ihn im Cache. Die Wette ist, dass, wenn Sie gerade ein Byte lesen, das nächste Byte, das Sie lesen, wahrscheinlich direkt danach ist. Wenn dies der Fall ist, kann es aus dem Cache kommen.

Indem Sie Ihre Schleife so einrichten, wie Sie sie haben, lesen Sie die Bytes in der Reihenfolge, in der sie im Speicher abgelegt sind. Dies bedeutet, dass sie sich im Cache befinden und von der CPU sehr schnell gelesen werden können. Wenn Sie die Zeilen 1 und 2 vertauscht haben, würden Sie jedes Mal "N" Bytes jedes Mal in der Schleife lesen. Die Bytes, die Sie lesen, sind nicht mehr im Speicher aufeinanderfolgend, und daher sind sie möglicherweise nicht im Cache. Die CPU muss sie aus dem (langsameren) RAM holen, und so sinkt Ihre Leistung.

Answer 5

Es gibt eine sehr gute Arbeit von Ulrich Drepper von Red Hat und glibc fame, What Every Programmer Should Know About Memory. In einem Abschnitt wurden Caches ausführlich besprochen. Zum Beispiel gibt es Cache-Effekte in SMP-Systemen, bei denen CPUs dazu führen können, dass Besitzer einer modifizierten Cache-Zeile hin und her gehen, was die Leistung stark beeinträchtigt.