Warum sind 513x513-Matrixtranspositionen schneller als 512x512-Matrixtranspositionen?

Leistungsunterschiede bei der Matrixtransposition für Matrixgrößen von 512 x 512 und 513 x 513 verstehen

Quadratische Matrizen unterschiedlicher Größe weisen einzigartige Zeitunterschiede auf sie umzusetzen. Interessanterweise neigen Matrizen mit der Dimension 2^n dazu, langsamere Transpositionszeiten zu haben als Matrizen mit der Dimension 2^n 1. Während diese Unterschiede für kleine Werte von n unbedeutend erscheinen mögen, werden sie bei größeren Dimensionen signifikant, wie MATSIZE 512 zeigt .

Um den zugrunde liegenden Grund für diese Leistungsunterschiede zu verstehen, beschäftigen wir uns mit dem Konzept von Caching.

Cache-Organisation und Set-Mapping

Caches sind in Sets und Zeilen organisiert. Jeder Satz enthält mehrere Zeilen, die Daten speichern können. Um den Satz zu finden, zu dem eine bestimmte Speicheradresse gehört, verwenden wir die folgende Formel:

set = (address / lineSize) % numberOfsets

Dadurch werden Speicheradressen auf ziemlich einheitliche Weise den Sätzen zugeordnet.

Cache Misses und Line Evictions

Beim Zugriff auf einen Speicherort prüft der Cache, ob die Daten bereits vorhanden sind. Wenn nicht, kommt es zu einem Cache-Fehler und die entsprechende Zeile wird aus dem Speicher gelesen und im Cache abgelegt. Wenn der Cache jedoch voll ist, wird die LRU-Zeile (Least Recent Used) gelöscht, um die neuen Daten aufzunehmen.

Kritischer Schritt

Der kritische Schritt stellt den Abstand dar zwischen Variablen, die um dieselben Cache-Zeilen konkurrieren. Sie wird wie folgt berechnet:

criticalStride = numberOfSets * lineSize

Variablen, die um den kritischen Schritt oder ein Vielfaches davon voneinander entfernt sind, verursachen mit größerer Wahrscheinlichkeit Cache-Räumungen.

Matrixtransposition und kritischer Schritt

Stellen Sie sich eine 64x64-Matrix mit einem 8-kB-Cache und vier Zeilen pro Satz vor. Jede Zeile kann acht 64-Bit-Ganzzahlen enthalten. Der kritische Schritt in diesem Szenario beträgt 2048 Bytes, was vier Zeilen der Matrix entspricht.

Beim Transponieren der Matrix tauschen wir Zeilen und Spalten aus. Während wir jede Zeile verarbeiten und mit der entsprechenden Spalte austauschen, kommt es bei Elementen, die durch den kritischen Schritt (vier Zeilen) getrennt sind, zu Cache-Räumungen. Dies führt zu einer erheblichen Anzahl von Cache-Neuladungen, was zu einer langsameren Transposition führt.

Schlussfolgerung

Die Ungleichheit in den Transpositionszeiten zwischen 512x512- und 513x513-Matrizen ergibt sich aus der Beziehung zwischen den Matrixabmessungen und der kritische Schritt des Caches. Matrizen mit Dimensionen, die kein Vielfaches des kritischen Schritts sind, führen zu reduzierten Cache-Räumungen und folglich zu schnelleren Umsetzungszeiten.

Das obige ist der detaillierte Inhalt vonWarum sind 513x513-Matrixtranspositionen schneller als 512x512-Matrixtranspositionen?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!