Speicherhierarchie und Leistung

Welche Kombination aus Grund und typischer Gegenmaßnahme ist richtig, warum beim Transponieren einer großen Matrix (b[j][i] = a[i][j]) leicht viele Cache-Misses auftreten?

  1. AGrund ist der hohe Rechenaufwand. Gegenmaßnahme ist, Gleitkomma in Ganzzahlen umzuwandeln
  2. BGrund ist, dass das Lesen sprunghaft wird. Gegenmaßnahme ist, nur die Schreibseite zusammenhängend zu machen
  3. CGrund ist, dass entweder das Lesen oder das Schreiben in Spaltenrichtung erfolgt. Gegenmaßnahme ist blockweises Transponieren
Antwort und Erläuterung anzeigen

Antwort: C. Grund ist, dass entweder das Lesen oder das Schreiben in Spaltenrichtung erfolgt. Gegenmaßnahme ist blockweises Transponieren

Beim Transponieren wird a zeilenweise gelesen und nach b spaltenweise geschrieben; schreibt man umgekehrt b zeilenweise, liest man a spaltenweise, sodass einer der beiden Zugriffe zwangsläufig sprunghaft ist. Wird die Matrix daher in kleine Blöcke zerlegt, die in den Cache passen, und innerhalb der Blöcke transponiert, werden die geladenen Zeilen vollständig genutzt, bevor es weitergeht, und die Misses sinken stark. Nur die Schreibseite zusammenhängend zu machen löst das Problem nicht grundlegend, da das Lesen sprunghaft wird. Auch der Rechenaufwand ist nicht das Problem.

Dieses Thema üben Zur Themenseite

Weitere Fragen zu Speicherhierarchie und Leistung

  1. Welche Eigenschaft gilt in der Speicherhierarchie eines üblichen Computers umso mehr, je höher die Ebene liegt (je näher an der CPU)?
  2. Warum müssen Caches bei der Leistungsbewertung nicht nur nach der Miss-Rate, sondern nach der mittleren Speicherzugriffszeit verglichen werden?
  3. Werden zwei Programme abwechselnd auf demselben Kern ausgeführt, können sie langsamer sein als bei einzelner Ausführung. Welche Erklärung aus Sicht des Caches ist am besten geeignet?
  4. Welches ist das am besten geeignete Beispiel für zeitliche Lokalität?
  5. 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?

Vergleiche zu diesem Thema