程式區域性(Locality)對快取失誤率與執行時間影響的評估

矩陣操作在一般計算機程式中常常被使用到，舉凡影像處理，或是統計方面等等的領域。
假設我們今天在程式中開闢出一個矩陣的記憶體空間後。我們將各個元素的資料清為零，考慮以下兩種方式：

1. 列存取優先: （程式區域性較佳）

     也就是說，我們先鎖定矩陣的一個列，然後在列中依序把各個元素清成零。
在C語言中的程式碼如下:

      for (row = 0; row < dimention; row++)

           for(col = 0; col < dimension; col++)

                     array[row][col] = 0;

2.行存取優先：（程式區域性較差）

     也就是說，我們先鎖定矩陣的一個行，然後在行中依序把各個元素清成零。
在C語言中的程式碼如下:

      for (col = 0; col < dimention; col++)

           for(raw = 0; raw < dimension; raw++)

                     array[row][col] = 0;

程式區域性

以矩陣16維度為例，如果是以列優先存取的方式進行清零的動作的話，將會由第一列第一個元素開始，到第一列最後一個元素為止。
從這個範例來看，第一步會先清記憶體位址 0x6020a0 再來會清 0x6020a4, 再之後就是 0x6020a8。也就是說，每一步存取的記憶體位址前後只差 4 byte。而且即使矩陣維度變大，只要在一列中依序存取，前後記憶體位址差異只會是 4 byte。

如果是以行優先存取的方式進行清零的動作的話，將會由第一列第一個元素開始，到最後一行第一個元素為止。
從這個範例來看，第一步會先清記憶體位址 0x6020a0 再來會清 0x602140, 再之後就是 0x6021e0。也就是說，每一步存取的記憶體位址前後差 160 byte。

因此，我們可以看到行優先存取確實有比較差的區域性。另外矩陣維度越大行優先存取的區域性越差。

開始實驗：

在 Intel i5-3317U 平台進行實驗，根據規格

Level 1 cache size	2 x 32 KB 8-way set associative instruction caches 2 x 32 KB 8-way set associative data caches
Level 2 cache size	2 x 256 KB 8-way set associative caches
Level 3 cache size	3 MB 12-way set associative shared cache

可以看到實驗平台有三層快取，第一層是八路集合關聯式的指令與資料分離快取各兩個，每一個大小32KB。第二層是兩個256KB的八路集合關聯式快取，分別作為指令快取跟資料快取。第三層是一個3MB的十二路集合關聯式快取。


實驗結果：
註:紅線表示列存取優先，綠線表示行存取優先。

                                           L1 資料快取失誤率與方陣維度關係

                       
                                           L2 資料快取失誤率與方陣維度關係

                                            LLd 資料快取失誤率與方陣維度關係

                                            

測試程式執行時間與方陣維度關係

從實驗結果可以看到，因為L1資料快取容量比較小，所以在矩陣維度為256的時候，列優先存取的失誤率便會大幅提昇。當然，在維度256以下的時候因為矩陣比較小，所以列優先存取跟行優先存取的程式區域性差異不大。

至於L2和LL快取可以看到在維度2048的時候快取失誤率會大幅提昇。且LL快取失誤率相對L2快取也比較小。
 

對於執行時間方面，可以看到列優先存取因為LL快取的失誤率已經大幅提昇，所以快取的失誤罰時（miss penalty）也增加了不少，導致兩個演算法的效能已經有了相當顯著的差異。 在維度為16384的時候可以看到兩個程式的效能差了將近七倍。

註：

測試程式碼下載位址：https://github.com/Awe31402/cache_test.git