Warum ist das Transponieren einer 512x512-Matrix deutlich langsamer als das Transponieren einer 513x513-Matrix?

Warum das Transponieren von 512x512-Matrizen langsamer ist als das Transponieren von 513x513

Eine besondere Beobachtung beim Transponieren von Matrizen ergab sich nach der Durchführung von Experimenten mit Matrizen unterschiedlicher Größe: Transponieren einer Matrix mit den Dimensionen 2^ n ist rechenintensiv als die Transponierung eines mit den Dimensionen 2^n 1. Das Die Diskrepanz wird signifikant, wenn n gleich 512 ist.

Der für die Transpositionsoperation bereitgestellte Code lautet wie folgt:

#define SAMPLES 1000
#define MATSIZE 512

#include <time.h>
#include <iostream>
int mat[MATSIZE][MATSIZE];

void transpose()
{
   for ( int i = 0 ; i < MATSIZE ; i++ )
   for ( int j = 0 ; j < MATSIZE ; j++ )
   {
       int aux = mat[i][j];
       mat[i][j] = mat[j][i];
       mat[j][i] = aux;
   }
}

int main()
{
   //initialize matrix
   for ( int i = 0 ; i < MATSIZE ; i++ )
   for ( int j = 0 ; j < MATSIZE ; j++ )
       mat[i][j] = i+j;

   int t = clock();
   for ( int i = 0 ; i < SAMPLES ; i++ )
       transpose();
   int elapsed = clock() - t;

   std::cout << "Average for a matrix of " << MATSIZE << ": " << elapsed / SAMPLES;
}

Durch Ändern des MATSIZE-Makros kann die Größe der Matrix geändert werden. Die folgenden Benchmarks verdeutlichen den krassen Unterschied:

• Größe 512: Durchschnittlich 2,46 ms
• Größe 513: Durchschnittlich 0,75 ms

Cache Contention und Critical Stride

Der Grund für diese Anomalie liegt im Cache-Verhalten und dem Cache-Konzept Streit. Hier ist eine Aufschlüsselung:

• Ein Cache ist in Sets und Zeilen strukturiert. Zu jedem Zeitpunkt wird nur auf einen Satz zugegriffen und jede Zeile innerhalb dieses Satzes kann verwendet werden. Die gesamte Cache-Größe wird durch die Anzahl der Zeilen multipliziert mit der Größe jeder Zeile bestimmt.
• Um den Satz zu berechnen, zu dem eine bestimmte Speicheradresse gehört, wird die folgende Formel verwendet: Satz = (Adresse / Zeilengröße) % numberOfsets.
• Wenn mehrere Speicheradressen auf denselben Satz zugreifen, kommt es zu Cache-Konflikten. In solchen Szenarien wird die am längsten verwendete Zeile im Satz mit den neu abgerufenen Daten überschrieben.
• Der kritische Schritt, der die Anzahl der Speicherzugriffe darstellt, die zu einem Cache-Konflikt führen, wird als „criticalStride = numberOfSets“ berechnet * lineSize.
• Im Fall einer 64x64-Matrix mit einem 8-KB-Cache würde der kritische Schritt perfekt mit den Zeilen der Matrix übereinstimmen, also voreilend zu übermäßigen Cache-Neuladungen während der Transposition.
• Wenn jedoch die Matrixgröße auf 65x65 erhöht wird, ist der kritische Schritt nicht mehr perfekt ausgerichtet, was die Häufigkeit von Cache-Konflikten verringert und die Leistung verbessert.

Daher wird der Transponierungsvorgang für Matrizen mit Dimensionen, die ein Vielfaches von 2^n sind, aufgrund von Cache-Konflikten erheblich langsamer.

Das obige ist der detaillierte Inhalt vonWarum ist das Transponieren einer 512x512-Matrix deutlich langsamer als das Transponieren einer 513x513-Matrix?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!