緩存友好的方法，以將兩個矩陣相乘

Question

我打算乘以使用緩存友好的方法2點矩陣（這將導致較少的未命中的數目）

我發現，這可以與高速緩存友好轉置函數來完成。

但我無法找到這個算法。我可以知道如何實現這一目標嗎？

Answer 1

你正在尋找的詞是顛簸。在Google yields more results中搜索顛簸矩陣乘法。

對於C的標準乘算法= A * B看起來像

void multiply(double[,] a, double[,] b, double[,] 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] += a[i, k] * b[k, j]; 
} 

基本上，在大步驟快速度導航存儲器是不利的性能。 B中的k的訪問模式正在完成該操作。因此，而不是在存儲跳來跳去，我們可能會重新安排操作，使得最內環僅在矩陣的第二存取操作指數：

void multiply(double[,] a, double[,] B, double[,] c) 
{ 
    for (i = 0; i < n; i++) 
    { 
     double t = a[i, 0]; 
     for (int j = 0; j < n; j++) 
     c[i, j] = t * b[0, j]; 

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

這是該網頁上給出的例子。但是，另一種方法是事先將B [k，*]的內容複製到數組中，並在內部循環計算中使用該數組。這種方法通常比替代方案快，即使它涉及複製數據。即使這看起來可能與直覺相反，請隨時嘗試一下。

void multiply(double[,] a, double[,] b, double[,] c) 
{ 
    double[] Bcolj = new double[n]; 
    for (int j = 0; j < n; j++) 
    { 
     for (int k = 0; k < n; k++) 
      Bcolj[k] = b[k, j]; 

     for (int i = 0; i < n; i++) 
     { 
      double s = 0; 
      for (int k = 0; k < n; k++) 
       s += a[i,k] * Bcolj[k]; 
      c[j, i] = s; 
     } 
    } 
} 

Answer 2

@ Cesar的回答不正確。例如，內部循環

for (int k = 0; k < n; k++) 
    s += a[i,k] * Bcolj[k]; 

經過a的第i列。

以下代碼應確保我們總是按行訪問數據。

void multiply(const double (&a)[I][K], 
       const double (&b)[K][J], 
       const double (&c)[I][J]) 
{ 
    for (int j=0; j<J; ++j) { 
     // iterates the j-th row of c 
     for (int i=0; i<I; ++i) { 
     c[i][j] = 0; 
     } 

     // iterates the j-th row of b 
     for (int k=0; k<K; ++k) { 
      double t = b[k][j]; 
      // iterates the j-th row of c 
      // iterates the k-th row of a 
      for (int i=0; i<I; ++i) { 
      c[i][j] += a[i][k] * t; 
      } 
     } 
    } 
}