矩陣乘法速度問題

我正在研究緩存未命中如何影響計算速度。我知道有更好的爲兩個矩陣（即使是簡單的兩個循環之下，將有助於交換）乘以很多算法，但請考慮下面的代碼：矩陣乘法速度問題

float a[N][N]; 
float b[N][N]; 
float c[N][N]; 
// ... 
{ 
    for (int i = 0; i < N; i++) { 
     for (int j = 0; j < N; j++) { 
      float sum = 0.0; 
      for (int k = 0; k < N; k++) { 
       sum = sum + a[i][k] * b[k][j]; 
      } 
      c[i][j] = sum; 
     } 
    } 
}

我已經重新編譯爲N許多值這個代碼，並測量時間來運行它。我預計在N=1250附近會發現突然增加的時間，此時矩陣c不再適合緩存（大小爲c然後是1250*1250*sizeof(float)=6250000，或大約6MB，這是我的L3緩存的大小）。

事實上，總體趨勢是在此之後，與從前的推斷時間相比，平均時間大約爲三倍。但N%8的價值似乎對結果有巨大影響。例如：

1601 - 11.237548 
1602 - 7.679103 
1603 - 12.216982 
1604 - 6.283644 
1605 - 11.360517 
1606 - 7.486021 
1607 - 11.292025 
1608 - 5.794537 
1609 - 11.469469 
1610 - 7.581660 
1611 - 11.367203 
1612 - 6.126014 
1613 - 11.730543 
1614 - 7.632121 
1615 - 11.773091 
1616 - 5.778463 
1617 - 11.556687 
1618 - 7.682941 
1619 - 11.576068 
1620 - 6.273122 
1621 - 11.635411 
1622 - 7.804220 
1623 - 12.053517 
1624 - 6.008985

有一段時間，我想那些可能是對齊的問題 - 任何矩陣的行對齊到32個字節時N%8==0（第一個問題 - 爲什麼32個字節特別SSE指令，如movaps可以嗎？在16B對齊的數據上工作）。

另一個想法是，這可能以某種方式連接到緩存關聯性（我的機器上L1和L2的8路和L3的12路）。

但後來我發現，對於諸如1536的N一些價值，也有意想不到的峯值（即使走線應在這些情況下，優良 - 1536==256*6，關聯性是非問題太 - 1536==128*12==192*8）。例如：

1504 - 4.644781 
1512 - 4.794254 
1520 - 4.768555 
1528 - 4.884714 
1536 - 7.949040 
1544 - 5.162613 
1552 - 5.083331 
1560 - 5.388706

時序非常一致，所以處理器負載的峯值不成問題。我打開優化編譯代碼（-O2）。我的想法不幸用完了。什麼可能是這種行爲的原因？

來源

2016-12-20 akrasuski1

的權力 - 的 - 兩個大國 - 的 - 兩個小倍數的大的尖峯可能是由於：http://stackoverflow.com/questions/12264970/why-is-my-program慢慢循環完全-8192元素 – Mysticial

您是否在編譯AVX？這將使32字節對齊變得重要。 – Mysticial

我正在使用GCC的默認設置，並且從程序集轉儲看來，AVX未使用。感謝您的鏈接，但我會讀它。 – akrasuski1

對於您的示例最重要的是CPU高速緩存行大小。對於CPU，通常是64字節。即使您的程序讀取或寫入1個字節，CPU也會爲所有行（64字節）讀取/寫入。這就是爲什麼，如果你的程序達到緩存線，你的表現很好。如果錯過了，讀/寫內存會有額外的開銷。 L3緩存的大小並不那麼重要。

爲您的代碼

// all your stack variables are good. Compiler will optimize them well. 
for (int i = 0; i < N; i++) { 
    for (int j = 0; j < N; j++) { 
     float sum = 0.0; 
     for (int k = 0; k < N; k++) { 
      sum = sum + 
        a[i][k] * // here you are good, you read memory sequentially 
        b[k][j]; // here, you are not good, every read comes from different cache line 
     } 
     c[i][j] = sum; // here doesn't matter, it is rare operation 
    } 
}

類似你的情況is here。此演示文稿解釋瞭如何優化此類代碼以及爲什麼以這種方式工作。我希望你會找到你需要的一切。

來源

2017-04-02 17:57:59 BayK

矩陣乘法速度問題

回答

相關問題