【C++】如何提高Cache的命中率，示例

參考鏈接? ? ?https://stackoverflow.com/questions/16699247/what-is-a-cache-friendly-code

?

只是堆積：緩存不友好與緩存友好代碼的典型例子是矩陣乘法的“緩存阻塞”。

樸素矩陣乘法看起來像

for(i=0;i<N;i++) {for(j=0;j<N;j++) {dest[i][j] = 0;for( k==;k<N;i++) {dest[i][j] += src1[i][k] * src2[k][j];}}
}

?

如果N很大，例如，如果N * sizeof(elemType)大于高速緩存大小，那么每次訪問都src2[k][j]將是高速緩存未命中。

有許多不同的方法可以為緩存優化它。這是一個非常簡單的示例：不是在內部循環中每個緩存行讀取一個項目，而是使用所有項目：

int itemsPerCacheLine = CacheLineSize / sizeof(elemType);for(i=0;i<N;i++) {for(j=0;j<N;j += itemsPerCacheLine ) {for(jj=0;jj<itemsPerCacheLine; jj+) {dest[i][j+jj] = 0;}for( k==;k<N;i++) {for(jj=0;jj<itemsPerCacheLine; jj+) {dest[i][j+jj] += src1[i][k] * src2[k][j+jj];}}}
}

?

如果高速緩存行大小為64字節，并且我們在32位（4字節）浮點數上運行，則每個高速緩存行有16個項目。通過這種簡單的轉換，緩存未命中的數量減少了大約16倍。

Fancier轉換在2D圖塊上運行，針對多個緩存（L1，L2，TLB）進行優化，等等。

谷歌搜索“緩存阻塞”的一些結果：

http://stumptown.cc.gt.atl.ga.us/cse6230-hpcta-fa11/slides/11a-matmul-goto.pdf

http://software.intel.com/en-us/articles/cache-blocking-techniques

一個優化的緩存阻塞算法的精彩視頻動畫。

http://www.youtube.com/watch?v=IFWgwGMMrh0

循環平鋪非常密切相關：

http://en.wikipedia.org/wiki/Loop_tiling

?