為什麼轉置 512x512 矩陣比轉置 513x513 矩陣慢很多？

為什麼轉置512x512 矩陣比轉置513x513 慢

在對不同大小的矩陣進行實驗後，出現了轉置矩陣的一個奇特現象：轉置矩陣維度為2^ 的矩陣n 在計算上比轉置維度為2^n 1 的計算成本更高。當 n 等於 512 時，差異變得顯著。

為轉置運算提供的程式碼如下：

#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;
}

透過更改 MATSIZE 宏，可以修改矩陣的大小。以下基準說明了明顯的差異：

• 大小512：平均2.46 毫秒
• 大小513：平均0.75 毫秒

快取爭用和關鍵步幅

此異常背後的原因在於快取行為以及快取爭用的概念。以下是細分：

• 快取由集合和行組成。在任何給定時刻，僅訪問一組，並且可以使用該組內的任何線路。總快取大小由行數乘以每行大小決定。
• 要計算特定記憶體位址所屬的集合，請使用下列公式：set = ( address / lineSize ) % numberOfsets.
• 當多個記憶體位址存取同一個集合時，就會出現緩存衝突。在這種情況下，集合中最近最少使用的行將被新檢索的資料覆蓋。
• 關鍵步長，表示導致快取衝突的記憶體存取次數，計算公式為： criticalStride = numberOfSets * lineSize。
• 對於具有 8kb 快取的 64x64 矩陣，關鍵步幅將與矩陣的行完美對齊，從而導致轉置期間過多的快取重新載入。
• 但是，當矩陣大小增加到 65x65 時，關鍵步幅不再完美對齊，從而減少快取衝突的頻率並提高效能。

因此，由於快取爭用，對於維度為 2^n 倍數的矩陣，轉置操作會明顯變慢。

以上是為什麼轉置 512x512 矩陣比轉置 513x513 矩陣慢很多？的詳細內容。更多資訊請關注PHP中文網其他相關文章！