為什麼轉置 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 <p>透過更改 MATSIZE 宏，可以修改矩陣的大小。以下基準說明了明顯的差異：</p>
<ul>
<li>大小512：平均2.46 毫秒</li>
<li>大小513：平均0.75 毫秒</li>
</ul>
<h2 id="快取爭用和關鍵步幅">快取爭用和關鍵步幅</h2>
<p>此異常背後的原因在於快取行為以及快取爭用的概念。以下是細分：</p>
<ul>
<li>快取由集合和行組成。在任何給定時刻，僅訪問一組，並且可以使用該組內的任何線路。總快取大小由行數乘以每行大小決定。 </li>
<li>要計算特定記憶體位址所屬的集合，請使用下列公式：set = ( address / lineSize ) % numberOfsets.</li>
<li>當多個記憶體位址存取同一個集合時，就會出現緩存衝突。在這種情況下，集合中最近最少使用的行將被新檢索的資料覆蓋。 </li>
<li>關鍵步長，表示導致快取衝突的記憶體存取次數，計算公式為： criticalStride = numberOfSets * lineSize。 </li>
<li>對於具有 8kb 快取的 64x64 矩陣，關鍵步幅將與矩陣的行完美對齊，從而導致轉置期間過多的快取重新載入。 </li>
<li>但是，當矩陣大小增加到 65x65 時，關鍵步幅不再完美對齊，從而減少快取衝突的頻率並提高效能。 </li>
</ul>
<p>因此，由於快取爭用，對於維度為 2^n 倍數的矩陣，轉置操作會明顯變慢。 </p></iostream></time.h>

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