Wie Cache-Speicher funktioniert?

Question

Wenn ich heute in der Computerorganisation Klasse war, sprach Lehrer über etwas interessant für mich. Wenn es darum geht, darüber zu sprechen Warum Cache-Speicher arbeitet, sagte er:

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 ist nicht gut, die erste Zeile mit dem zweiten zu ändern. Was ist Ihre Meinung dazu? Und warum ist es so?

Answer 1

Stelle Bezug genommen wird. Da die Daten von Zeilen gespeichert sind, für jede Zeile sind die j Spalten in benachbarten Speicheradressen. Das Betriebssystem wird in der Regel eine ganze Seite aus dem Speicher in den Cache und den angrenzenden Adreßverweise laden wahrscheinlich zu derselben Seite verweisen. Wenn Sie von dem Zeilenindex in der inneren Schleife erhöhen ist es möglich, dass diese Zeilen auf verschiedenen Seiten sein werden (da sie durch j getrennt verdoppelt jeweils) und die Cache kann ständig in bringen und Speicherseiten wegzuwerfen wie es verweist die Daten. Dies nennt man Dreschen und ist schlecht für die Leistung.

In der Praxis und mit größerem, modernem Caches, die Größen der Zeilen / Spalten müßten ausreichend groß sein, bevor diese ins Spiel kommen würden, aber es ist immer noch ein gute Praxis.

[EDIT] Die Antwort oben ist spezifisch für C und kann für andere Sprachen unterscheiden. Die einzige, die ich weiß, anders ist, ist Fortran. FORTRAN speichern Dinge in Spaltenhauptordnung (die oben ist Zeile major) und es wäre richtig, um die Reihenfolge der Aussagen in Fortran zu ändern. Wenn Sie / müssen Effizienz wollen, ist es wichtig zu wissen, wie Sie Ihre Sprachdatenspeicher implementiert.

Answer 2

Es ist ein sehr gutes Papier von Ulrich Drepper von Red Hat und glibc Ruhm, Was jeder Programmierer sollte Know About Speicher . Ein Abschnitt diskutiert Caches im Detail. Zum Beispiel gibt es Cache-Effekte in SMP-Systemen, bei denen CPUs Dreschen Eigentum an einer modifizierten Cache-Zeile hin und her am Ende, die Leistung erheblich zu schädigen.

Answer 3

Es ist so becauses Caches wie Lokalität. Die gleiche Anzahl von Speicher zugegriffen, aber weiter voneinander entfernt, werden verschiedene „Linien“ des Cache-Treffers, oder könnte sogar den Cache insgesamt verfehlen. Es ist daher gut, wenn Sie die Wahl haben, Daten so zu organisieren, dass Zugriffe, die miteinander passieren zeitnah wahrscheinlich auch tut so im Raum. Dadurch erhöht sich die Chance auf einen Cache-Treffer, und gibt Ihnen mehr Leistung.

Natürlich gibt es eine Fülle von Informationen zu diesem Thema zur Verfügung, siehe zum Beispiel dieses Wikipedia-Eintrag auf Lokalität von Referenz . Oder ich denke, Ihr eigenes Kurs Lehrbuch. :)

Answer 4

C, n-dimensionale Matrizen Reihe major, der letzte Index in die Matrix im Speicher benachbarte Räume repräsentiert bedeutet. Dies ist anders als einige andere Sprachen, Fortran zum Beispiel des Spaltenhaupt sind. In Fortran, ist es effizienter, durch eine 2D-Matrix wie folgt zu wiederholen:

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

Answer 5

Die Cache-Speicher ist sehr schnell und sehr teuer Speicher, der mit der CPU der Nähe sitzt. Anstatt jedes Mal ein kleines Stück von Daten aus dem RAM zu holen, holt sich die CPU einen Teil der Daten und speichert sie im Cache. Die Wette ist, dass, wenn Sie nur ein Byte lesen, dann die nächsten Byte Sie ist wahrscheinlich richtig gelesen, nachdem es sein. Wenn dies der Fall ist, dann kann es aus dem Cache kommen.

Durch Ihre Windungsleger aus, wie Sie es haben, lesen Sie die Bytes in der Reihenfolge, dass sie im Speicher gespeichert sind. Dies bedeutet, dass sie im Cache ist, und kann durch die CPU sehr schnell gelesen werden. Wenn Sie rund um die Linien 1 und 2 vertauscht, dann würden Sie alle „N“ lesen jedes Mal um die Schleife Bytes. Das Bytes, die Sie lesen, sind nicht mehr in Folge im Speicher, und so können sie nicht im Cache sein. Die CPU hat sie aus dem (langsamer) RAM zu holen, und so Ihre Leistung nimmt ab.