在上一篇部落格 C++性能優化系列——矩陣轉置(一)通路記憶體順序帶來的性能差異 中，分析了記憶體通路行列連續帶來的性能差異。本篇以上一篇中寫記憶體行連續的實作方案為Base版本，通過循環分塊的優化技巧，進一步優化Base版本中的緩存通路問題。
優化後執行情況如下：
1024 * 1024的二維矩陣，分塊優化後耗時 0.605469 ms
老規矩先上結論：
通過循環分塊方法，計算合理的分塊尺寸，将循環邏輯實作為内層循環周遊通路塊内資料，可以有效減少Cache Miss。本文中Base版本耗時是優化版本的2.56倍。
緩存結構
測試機器CPU Cache結構如下：
緩存通路模式分析
分析一下pSource的L1 D Cache通路模式，由于二維矩陣尺寸為1024 * 1024，元素大小一個位元組，是以pSource是按照間隔為1K讀取記憶體資料。
最内層内循環執行1024次，L1 Cache一共加載CacheLine1024個，一共需要加載至緩存64 * 1K = 64K，大于L1 D Cache 32K，是以目前通路模式L1 D Cache無法存下所有需要的記憶體，即每次内層循環執行pSource都會發生Cache Miss。
是以，需要一個優化方式，使每次最内層通路都在L1 D Cache中。循環分塊是處理這類問題的一種優化手段。本文嘗試按照128 * 128的塊尺寸，将二維矩陣分塊，内層循環pSource和pTarget都隻通路塊内資料。
按照這種分塊方式進行記憶體通路，pSource和pTarget每次加載到緩存的大小為2 * 128 * 128 = 32K，剛好可以放在L1緩存中。
代碼實作
代碼中矩陣尺寸的相關定義，增加分塊尺寸BLOCK
#define NROW 1024
#define NCOL 1024
#define NSLICE NROW*NCOL
#define REPEAT 1024
#define BLOCK 128
基于Base版本實作，内層循環隻通路128 * 128 的記憶體塊，保證所有資料都在緩存中。
代碼實作
void BlockRowSeqTranspose(unsigned char* pSource, unsigned char* pTarget)
{
//Target 連續通路行
//BlockRowSeqTranspose Time (ms) 0.605469
clock_t begin = clock();
int nbC = NCOL / BLOCK, nbR = NROW / BLOCK;
for (int i = 0; i < REPEAT; ++i)
{
for (int ibr = 0; ibr < nbR; ++ibr)
{
for (int ibc = 0; ibc < nbC; ++ibc)
{
for (int irow = 0; irow < BLOCK; ++irow)
{
for (int icol = 0; icol < BLOCK; ++icol)
{
pTarget[(ibr*BLOCK +irow) * NCOL + icol] = pSource[(ibc*BLOCK+icol) * NROW + irow];
}
}
}
}
}
clock_t end = clock();
std::cout << "BlockRowSeqTranspose 1024 Time " << (end - begin) << std::endl;
std::cout << "BlockRowSeqTranspose Time (ms) " << ((float)(end - begin)) / (float)REPEAT << std::endl;
}
執行時間
Base版本執行時間
和之前版本對比執行時間從1.5498加速到0.605469，速度提高2.56倍。可以看到針對L1緩存進行優化後的代碼執行速度有明顯提升。
VTune資料分析
将Base版本VTune抓取資料包和分析放在這裡，友善對比。
Base版本
可以看大Base版本記憶體瓶頸為核心的熱點。
代碼整體CPI為1.164.大于1，通常CPI高于1需要進行優化。
具體熱點位置，L3 Cache Miss高。這裡和之前分析的結果不太一樣，之前分析的結果是L1會頻繁發生Cache Miss。猜測原因可能是緩存一緻性算法在替換L1 Cache時做的一些優化工作，将Miss轉移到L3 Cache上了。
檢視反彙編，通路記憶體的指令CPI都大于1。整體看下來，Base版本的執行情況符合之前分析的預期。
優化版本
整體性能瓶頸集中在後端，記憶體瓶頸占比例比較小。
優化版本CPI為0.438，小于1。指令執行平均耗時還不錯。
熱點代碼位置，CPI也在0.4多一點。其中後端（即CPU的執行部分）問題突出。這裡主要的問題是c++代碼編譯器無法做向量化。因為二維矩陣轉置邏輯pSource通路記憶體不連續。
檢視反彙編，彙編指令的CPI也都在0.4左右，沒有慢的特别突出的存在。
對比兩個版本的執行情況，做了分塊優化後，代碼在通路記憶體方面得到了不小的提升。
總結
在實作 按照一定間隔通路記憶體 的功能時，要警惕記憶體的通路模式，尤其是性能敏感的功能。當通路記憶體間隔過大時，緩存無法将通路的記憶體全部裝載進去。通過循環分塊技術，将資料劃分成緩存能夠全部轉載的尺寸，能夠有效提高程式的速度。