[問題] Cache size量測小程式數據解釋

[hsnuer1171 (humanforestQQ)]

開發平台(Platform): (Ex: Win10, Linux, ...) 
Linux

編譯器(Ex: GCC, clang, VC++...)+目標環境(跟開發平台不同的話需列出)
GCC

額外使用到的函數庫(Library Used): (Ex: OpenGL, ...) 
STL only

問題(Question)：

Stackoverflow 詳細內容:
https://stackoverflow.com/questions/57343855/program-to-measure-cache-size-please-explain-results/57344177#57344177

我寫了一個簡單的程式來量測Cache Line Size

就是每次跳一個step (offset)去存取array, 透過加大offset來觀察執行時間

預計當offset超過cache line size時

會導致每次都要從下層(L2)抓一條新的cache line

Code:

void access_array(char* arr, int steps)
{
    const int loop_cnt = 1024 * 1024 * 32; // arbitary loop count
    int idx = 0;
    for (int i = 0; i < loop_cnt; i++)
    {
        arr[idx] += 10;
        idx = (idx + steps) & (ARRAY_SIZE - 1);
    }
}

Result:

step    , time(us)
1       , 29929
2       , 30003
4       , 30410
8       , 30046
16      , 31987
32      , 36796
64      , 72008
128     , 72300
256     , 71439
512     , 71460
1024    , 126504
2048    , 156086
4096    , 212619
8192    , 188025
16384   , 155549
32768   , 46295

在64的時候執行時間增加兩倍, 因為我的cache line size = 64, 符合預期

我的問題是:

為什麼從64到512時間幾乎都沒有改變, 而從1K開始到4K又遞增上去?

Array size是256KB, 我試過128KB / 64 / 32 都是一樣結果

Stackoverflow上面的回應是覺得跟prefetch / TLB miss有關,

我覺得解釋聽起來還算合理但是好像沒有辦法証明

我試著查過不少資料, 大多數是講理論沒有講到太詳細spec

所以想請各位幫忙解惑...

感謝

CPU: Intel Xeon(R) CPU E5-2667 0 @ 2.90GHz

Cache size:
LEVEL1_ICACHE_SIZE                 32768
LEVEL1_ICACHE_ASSOC                8
LEVEL1_ICACHE_LINESIZE             64
LEVEL1_DCACHE_SIZE                 32768
LEVEL1_DCACHE_ASSOC                8
LEVEL1_DCACHE_LINESIZE             64
LEVEL2_CACHE_SIZE                  262144
LEVEL2_CACHE_ASSOC                 8
LEVEL2_CACHE_LINESIZE              64
LEVEL3_CACHE_SIZE                  15728640
LEVEL3_CACHE_ASSOC                 20
LEVEL3_CACHE_LINESIZE              64
LEVEL4_CACHE_SIZE                  0
LEVEL4_CACHE_ASSOC                 0
LEVEL4_CACHE_LINESIZE              0


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.229.42.20 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1565324968.A.C35.html
推 wa120: 32768bytes/1024剛好32KB,for loop的loop_cnt用const,他會
→ wa120: 自動unrolling排vector register,因為vector register用滿
→ wa120: 了,所以在固定倍數上產生兩倍的load/store
→ wa120: register說錯 不好意思 用的是general register排滿
推 eye5002003: 從32768開始,花費的時間反而變少了,確實值得研究
推 johnjohnlin: Benchmarking GPUs to Tune Dense Linear Algebra
→ johnjohnlin: ↑這篇論文有說明，主要原因是 cache assoc
→ johnjohnlin: google 可以找這篇有公開