有趣的 cache line 效應

在忙著處理一些個人事務的時候, Jim Huang 請我幫忙回覆學弟妹碰到的 一些問題
主要是 Jim Huang 修改了之前 Matrix Transpose 的例子作為範例給學弟妹們練功使用
而學弟妹碰到了一個問題, 就是對於 Matrix Transpose 的寬做調整時
執行時間與長寬度的調整的分佈圖如下:

如上圖所示, 隨著對寬作 4096 + (i*64)的調整時經分佈呈現鋸齒狀的變化!
依照文中敘述的實驗平台為俱備 6MB cache 的 Core-i5 6300HQ
以 Intel Skylake 架構而言, 為 64 bytes cache line, 8-way associative cache
基本上俱備 6MB/64/8 = 12288 sets (entries)
以這個 int matrix 而言, 原始的寬度為 4096x4=16384 bytes
16384/64 = 256
因此每增加一行記憶體基本上會跳躍 256 cache line index

接著再觀察 naive transpose 的實作:
https://github.com/yangyang95/prefetcher/blob/master/impl/naive_transpose.c
若 buffer 對應的 cache line index offset 為 X

首先考慮最簡單的 i == 0 的情況
對於第 n 行的 cache line index 計算為: (X + 256*n) % 12288
1. 12288 / 256 = 48 (自 cache line 0 ~ 12288, 每次跳 256 可以消耗 48 行)
2. 12288 % 256 = 0 (每次的 cache line index shift)
所以填完 output 第一行來說, 這也代表著當資料(二維座標以(x,y)表示)自 (0, 0), (0, 1) .... (0, 4095) 要讀 (1, 0) 時
而相關的 cache line 早已被反覆地填入了 4096/48 = 85.33次 > 8
當 CPU 需要讀入 (1, 0) 時, 因為讀入 (0, 0) 所讀入的 cache line 有相當高的機會早已被 replace

接著當每次寬度增加 64 時(也就是 256 byte, 4 cache lines)
這裡我們先考慮 i == 1 的情況
對於第 n 行的 cache line index 計算為: (X + 260*n) % 12288
1. 12288 / 260 = 47.26 ...
2. 12288 % 260 = 68
260 與 68 兩者最小公倍數為 4420
4420/68 = 65  (表示反覆繞 cache line index 0 ~ 12288 到第 65 次才開始 cache line index 有所重疊)
而 4160/47.25 約為 88.02, 88.02 / 65 = 1.35 < 8
這表示在讀取 (1, 0) 時, 有很大的機會 (0, 0) 所填入的 cache line 還在

再考慮 i == 8 的情況
對於第 n 行的 cache line index 計算為: (X + 288*n) % 12288
1. 12288 / 288 = 42.6666....
2. 12288 % 288 = 192
而 288 與 192 兩者最小公倍數為 576
576/192 = 3 (表示反覆繞填 cache line index 0 ~ 12288 到第 3 次 cache line index 就有所重疊)
而 4608/42.666 約為 108, 108 / 3 = 36 > 8
這表示在讀取 (1, 0) 時, (0, 0) 所填入的 cache line 有相當高的機會早已被 replace

由類似的計算可以得知, 造成這樣的時間分佈的原因, 而 SSE 版本的成因也是基於相同道理
而這樣的效應更顯示程式的記憶體使用方式, data layout 與 cache 影響程式的效能甚巨