爲什麼矩陣乘法算法中的循環順序會影響性能？

我給定兩個函數用於查找兩個矩陣的乘積：爲什麼矩陣乘法算法中的循環順序會影響性能？

void MultiplyMatrices_1(int **a, int **b, int **c, int n){ 
     for (int i = 0; i < n; i++) 
      for (int j = 0; j < n; j++) 
       for (int k = 0; k < n; k++) 
        c[i][j] = c[i][j] + a[i][k]*b[k][j]; 
    } 

void MultiplyMatrices_2(int **a, int **b, int **c, int n){ 
     for (int i = 0; i < n; i++) 
      for (int k = 0; k < n; k++) 
       for (int j = 0; j < n; j++) 
        c[i][j] = c[i][j] + a[i][k]*b[k][j]; 
}

我跑和使用gprof，每個具有除了該功能相同的代碼異形兩個可執行。對於2048 x 2048大小的矩陣，其中第二個顯着（約5倍）。關於爲什麼？

來源

2011-09-13 kevlar1818

我相信你在看的是locality of reference在計算機內存層次結構中的影響。

典型地，計算機存儲器被分成具有不同的性能特性的不同類型（這通常被稱爲memory hierarchy）。最快的存儲器位於處理器的寄存器中，可以（通常）在一個時鐘週期內訪問和讀取。但是，這些寄存器通常只有少數（通常不超過1KB）。另一方面，計算機的主存很大（如8GB），但訪問速度要慢得多。爲了提高性能，計算機通常在物理上構造成在處理器和主存儲器之間具有several levels of caches。這些緩存比寄存器慢，但比主內存快得多，所以如果你在緩存中查看內存訪問，它往往比如果你必須去主內存快得多（通常在5-25倍之間更快）。當訪問內存時，處理器首先檢查內存緩存中的該值，然後返回主內存讀取該值。如果始終訪問緩存中的值，則最終性能會比跳過內存時的性能好得多內存，隨機訪問值。

大多數程序都是以一種方式寫入的，如果內存中的單個字節被讀入內存，程序稍後會從該內存區域讀取多個不同的值。因此，這些緩存通常被設計成當你從內存中讀取單個值時，圍繞該單值的一塊內存（通常介於1KB和1MB之間）的值也被拉入緩存。這樣，如果你的程序讀取附近的值，它們已經在緩存中，你不必去主內存。

現在，最後一個細節 - 在C/C++中，數組以行優先順序存儲，這意味着矩陣的單個行中的所有值都相鄰存儲。因此，在內存中，陣列看起來像第一行，然後是第二行，然後是第三行等。

鑑於此，我們來看看您的代碼。第一個版本如下所示：

for (int i = 0; i < n; i++) 
     for (int j = 0; j < n; j++) 
      for (int k = 0; k < n; k++) 
       c[i][j] = c[i][j] + a[i][k]*b[k][j];

現在，我們來看看最內層的代碼行。在每次迭代中，k的值都在變化。這意味着在運行最內層循環時，循環的每次迭代很可能在加載b[k][j]的值時發生緩存缺失。原因在於，因爲矩陣以行優先順序存儲，所以每次增加k時，都會跳過矩陣的整行並進一步跳到內存中，可能遠遠超過已緩存的值。但是，在查找c[i][j]時（因爲i和j是相同的），您不會錯過，也不會錯過a[i][k]，因爲這些值是按行優先順序排列的，並且如果a[i][k]的值是從先前緩存的迭代，在此迭代中讀取的a[i][k]的值是來自相鄰的存儲器位置。因此，在最內層循環的每次迭代中，您可能會有一次高速緩存未命中。

但考慮這第二個版本：

for (int i = 0; i < n; i++) 
     for (int k = 0; k < n; k++) 
      for (int j = 0; j < n; j++) 
       c[i][j] = c[i][j] + a[i][k]*b[k][j];

現在，因爲你在每次迭代增加j，讓我們想想有多少高速緩存未命中你可能對最裏面的語句。因爲這些值是按行優先順序排列的，所以c[i][j]的值很可能是緩存中的，因爲前一次迭代中的c[i][j]的值可能會被緩存並準備好讀取。同樣，b[k][j]可能被緩存，並且由於i和k不會更改，所以緩存a[i][k]的機率也是可能的。這意味着在內部循環的每次迭代中，您可能沒有緩存未命中。總的來說，這意味着代碼的第二個版本不太可能在循環的每次迭代中都存在緩存未命中，而第一個版本幾乎肯定會發生。因此，如你所見，第二個循環可能比第一個循環更快。有趣的是，許多編譯器開始有原型支持來檢測代碼的第二版本比第一版本更快。有些人會嘗試自動重寫代碼以最大化並行性。如果您有Purple Dragon Book的副本，第11章將討論這些編譯器的工作方式。

此外，您可以使用更復雜的循環來進一步優化此循環的性能。例如，一種名爲blocking的技術可用於通過將陣列拆分爲可保存在緩存中的更長的子區域，然後對這些區塊使用多個操作來計算總體結果，從而顯着提高性能。

希望這會有所幫助！

來源

2011-09-13 00:42:34 templatetypedef

+1確實不錯！另外，關於緩存調試的建議@Kerrek SB增加了更多的技術細節。 – rbaleksandar

可能是第二個不得不在內存中跳過訪問數組元素。它也可能是其他的東西 - 你可以檢查編譯後的代碼，看看實際發生了什麼。

來源

2011-09-13 00:34:45 xpda

這可能是記憶的地方。當您重新排序循環時，最內層循環中所需的內存越來越近並且可以被緩存，而在低效版本中，您需要從整個數據集中訪問內存。

測試此假設的方法是在兩段代碼上運行緩存調試器（如cachegrind），並查看它們產生多少緩存未命中。

來源

2011-09-13 00:34:56

+1 cachegrind –

除了內存的地方之外，還有編譯器優化。矢量和矩陣運算的關鍵之一是循環展開。

for (int k = 0; k < n; k++) 
    c[i][j] = c[i][j] + a[i][k]*b[k][j];

您可以在此內環i和j不改看。這意味着它可以被重寫爲

for (int k = 0; k < n; k+=4) { 
    int * aik = &a[i][k]; 
    c[i][j] += 
     + aik[0]*b[k][j] 
     + aik[1]*b[k+1][j] 
     + aik[2]*b[k+2][j] 
     + aik[3]*b[k+3][j]; 
}

你可以看到會有

四次循環更少並且訪問到c [i] [j]
A [1] [k]的正在內存中連續訪問
內存訪問和倍增可以在CPU中流水線（幾乎同時）。

如果n不是4或6或8的倍數？（或者編譯器決定將其展開到哪裏）編譯器會爲你處理這個問題。;）

爲了加快此解決方案的速度，您可以嘗試先轉置b矩陣。這是一些額外的工作和編碼，但這意味着對b轉置的訪問在內存中也是連續的。（當你用[j]交換[k]時）

你可以做的另一件事是提高性能，以便多線程乘法。這可以在4核CPU上將性能提高3倍。

最後，你可能會考慮使用float或double你可能會認爲int會更快，但是這是情況並非總是如此的浮點運算可以更加高度優化的（無論是在硬件和編譯器）

第二例如，c [i] [j]在每次迭代中都會發生變化，這使得優化變得更加困難。

來源

2011-09-13 07:58:12

爲什麼矩陣乘法算法中的循環順序會影響性能？

回答

相關問題