Speicherhierarchie und Leistung

Wird ein zweidimensionales C-Array a[i][j] wie oben mit j als innerer Schleife durchlaufen, ist dies tendenziell schneller als mit i als innerer Schleife. Was ist der Grund?

for (i = 0; i < N; i++)
    for (j = 0; j < N; j++)
        sum += a[i][j];
  1. AWeil es zeilenweise gespeichert ist, werden aufeinanderfolgende Adressen der Reihe nach gelesen, und die Cache-Zeilen werden gut genutzt
  2. BWeil der Compiler die Additionen in der Schleife zusammenfasst und entfernt und die Berechnung selbst zur Laufzeit ausgelassen wird
  3. CWeil bei j als innerer Schleife der TLB überhaupt nicht mehr referenziert wird und die Umsetzung von virtueller auf physische Adresse entfällt
Antwort und Erläuterung anzeigen

Antwort: A. Weil es zeilenweise gespeichert ist, werden aufeinanderfolgende Adressen der Reihe nach gelesen, und die Cache-Zeilen werden gut genutzt

Zweidimensionale Arrays in C werden zeilenweise (row-major) gespeichert, und a[i][0], a[i][1] … liegen im Speicher nebeneinander. Mit j als innerer Schleife werden aufeinanderfolgende Adressen der Reihe nach gelesen, sodass der Rest der durch einen einzigen Miss geladenen 64-Byte-Cache-Zeile sofort genutzt wird. Mit i als innerer Schleife werden Adressen im Abstand einer Zeile sprunghaft gelesen, und die Zeile wird leicht verdrängt, bevor nur ein kleiner Teil genutzt wurde. Der TLB wird weiterhin verwendet, und die Adressumsetzung entfällt nicht.

Dieses Thema üben Zur Themenseite

Weitere Fragen zu Speicherhierarchie und Leistung

  1. Wie viele Bit hat das Tag bei einem Direct-Mapped-Cache mit 32-Bit-Adressen, 32 KB Kapazität und 64 Byte Zeilengröße?
  2. Wie viele Sätze hat ein 4-fach satzassoziativer Cache mit 32-Bit-Adressen, 32 KB Kapazität und 64 Byte Zeilengröße?
  3. Wie viele Adressbits dienen bei einem voll assoziativen Cache als Index (der Teil, der den Satz auswählt)?
  4. Der L1-Cache hat eine Trefferzeit von 1 ns und eine Miss-Rate von 5 %, der L2-Cache eine Trefferzeit von 10 ns und eine lokale Miss-Rate von 20 %, der Hauptspeicher eine Zugriffszeit von 100 ns. Wie groß ist die mittlere Speicherzugriffszeit?
  5. In einem Direct-Mapped-Cache entsprechen Elemente zweier Arrays derselben Cache-Position und verdrängen sich bei abwechselndem Zugriff gegenseitig. In welche Klasse fällt dieser Miss?

Vergleiche zu diesem Thema