Try   HackMD

現代處理器設計: Cache 原理和實際影響

直播錄影

Cache 介紹

Cache 基本認識

Cache 介紹

CPU cache 是用於減少處理器存取記憶體所需平均時間的機制

  1. level-1 data cache: 一級資料 cache(D$)
  2. level-1 inst cache: 一級指令 cache(I$)
  3. MMU：記憶體管理單元
  4. TLB：translation lookaside buffer
  5. level-2 cache: 二級 cache
  6. level-3 cache: 三級 cache

根據我的電腦的資訊，可以看到快取記憶體從 L1 的 32K 到 L3 的 6144K，如此設計並不是沒有道理，Cache 越上層的記憶體越貴，速度越快，容量越小。越下層記憶體越便宜，速度慢，但容量越大。

整個過程大致如下：

  1. CPU 根據虛擬地址嘗試從 L1 cache (存放的是虛擬地址的索引) 中讀取資料；
  2. 如果 L1 cache 中查找不到，則需向 MMU 請求資料；
  3. MMU 從 TLB 中查找虛擬地址的快取 (換言之，TLB 是負責改進虛擬地址到實體地址轉換速度、存放虛擬地址的快取)；
  4. 若 TLB 中存在該虛擬地址的 cache，則 MMU 將該虛擬地址轉化為實體地址，如果地址轉換失敗，則發生 page fault，由作業系統核心進行處理，見上文所述；如果地址轉換成功，則從二級快取 (存放的是實體地址的索引) 中讀取；如果 L2 cache 中也沒有，則需要從 L3 cache，甚至實體記憶體中請求；
  5. 如果 TLB 中不存在該虛擬地址的 cache，則 MMU 從實體記憶體中的轉換表 (translation tables，也稱為分頁表 page tables) 中獲取，同時存入 TLB；(注意，這個操作由硬體實作，可由 MMU 通過硬體直接從實體記憶體中讀取)；
  6. 跳到第4步。

延伸閱讀:

Cache latency

在一般的個人電腦上，指令概略執行時間（相對）：

execute typical instruction 1/1,000,000,000 sec = 1 nanosec
fetch from L1 cache memory 0.5 nanosec
branch misprediction 5 nanosec
fetch from L2 cache memory 7 nanosec
Mutex lock/unlock 25 nanosec
fetch from main memory 100 nanosec
send 2K bytes over 1Gbps network 20,000 nanosec
read 1MB sequentially from memory 250,000 nanosec
fetch from new disk location (seek) 8,000,000 nanosec
read 1MB sequentially from disk 20,000,000 nanosec
send packet US to Europe and back 150 milliseconds = 150,000,000 nanosec

reference:

Cache line

  • cache line 是 cpu cache 中的最小快取單位。

  • 主流的 CPU Cache 的 Cache Line 大小多為 64 Bytes

    • 有些例外，如 ARMv8-A 為基礎的 Cavium ThunderX 的 cache line 為 128 Bytes
    • Reference: Cavium ThunderX

  • 假設有一個 512 bytes 的一級快取，那按照 64 Bytes 的快取單位大小來算，這個一級快取所能存放的快取個數就是 512/64 = 8 個。

    ​​​​cache line size 為 64 bytes

​​​​L1D size 為 512 bytes

​​​​cache line #0      "    64 bytes    "
​​​​cache line #1      "    64 bytes    "
​​​​cache line #2      "    64 bytes    "
​​​​cache line #3      "    64 bytes    "
​​​​cache line #4      "    64 bytes    "
​​​​cache line #5      "    64 bytes    "
​​​​cache line #6      "    64 bytes    "
​​​​cache line #7      "    64 bytes    "

Cache 的設計模式

快取記憶體有三種對映函數 (mapping function)：

  • Direct Mapped
  • Fully Associative
  • n-way associative

1. Direct Mapped

一塊資料（佔一個 cache line 的空間），只有一個 cache line 與之對應。為多對一的映射關係。在 1990 年代初期，直接映射是當時最流行的機制，因為所需的硬體資源非常有限。現在直接映射機制正在逐漸被淘汰。

下面用停車場當作例子來做說明：
假設有 1000 個停車位，每個位子依 000~999 的順序給一個號碼，你的學生證號碼的前三碼就是你的停車位號碼。這就是 cache 對映最簡單的例子。

然而這會有什麼問題呢？數字小的號碼(如:200多)可能有更大的機會同一個位置有多個學生要停。數字大的號碼就可能會比較空，因為學生證號碼900多開頭的學生可能不多。

優點：

  • 簡單，記憶體中的每一個位置只會對應到 cache 中的一個特定位置。

缺點：

  • 兩個變數映射到同一個 cache line 時，他們會不停地把對方替換出去。由於嚴重的衝突，頻繁刷新 cache 將造成大量的延遲，而且在這種機制下，如果沒有足夠大的 cache，處理程序幾乎無時間局部性可言。

2. Fully Associative

在一個 Cache 集內，任何一個記憶體地址的數據可以被 cache 在任何一個 Cache Line 裡。

下面用停車場當作例子來做說明：
停車許可證比停車位還要多的狀況。有 1000 個停車位，但是有 5000 個同學。

優點：

  • 可以完整利用記憶體

缺點：

  • cache 中尋找 block 時需要搜尋整個 cache

3. N-way Set Associative Cache

直接映射會遭遇衝突的問題，當多個塊同時競爭 cache 的同一個 cache line 時，它們不停地將對方踢出快取，這將降低命中率。

另一方面，完全關聯過於複雜，很難在硬體層面實現。

N路關聯快映射則是直接映射跟全映射的混合，在兩者之前取得平衡。

下面用停車場當作例子來做說明：
假設有 1000 個停車位，分成 10 組，使用 00~99 作為每一組內車位的編號。你的停車位就是學生證的前兩碼，如此一來你就有 10 個停車位可以選擇。

優點：

  • 給定一個記憶體地址可以唯一對應一個 set ，對於 set 中只需遍歷 16 個元素就可以確定對象是否在快取中。
  • 相對 Direct Mapped，連續熱點數據 (會導致一個 set 內的 conflict) 的區間更大

reference:

Cache miss

cache miss 有三種：

  • Compulsory misses（強迫性失誤）：也稱為 cold start misses，第一次存取未曾在 cache 內的 block 而發生的 cache miss ，這種 miss 是不可避免的。

  • Capacity misses（空間性失誤）：因為在程式執行期間， cache 無法包含所有需要的 block 而產生的 cache miss。發生在一個 block 被取代後，稍後卻又需要用到。

  • Conflict misses（衝突性失誤）：發生在 set-associative 或 direct-mapped caches ，當多個 blocks 競爭相同的 set。通常也稱作 collision misses。

比較 capacity misses 和 conflict miss 的差異

  • 假設有 32KB 的 cache

  • 情況一（capacity misses）：如果有一個 64KB 的陣列需要重複存取，因為陣列大小遠大於 cache 大小，所以沒辦法全部放入 cache 。第一次存取陣列發生的 cache misses 全都是 compulsory misses 。但之後存取陣列發生的 cache misses 全都是 capacity misses ，這時的 cache 已存滿，容量不足以儲存全部的資料。

  • 情況二（conflict misses）：如果有兩個 8KB 的陣列需要來回存取，但是這兩個陣列都映射到相同的地址， cache 的大小足夠儲存全部的資料，但是因為相同地址發生衝突，需要來回替換，這時候發生的 cache misses 全都是 conflict misses（不過，第一次存取陣列發生的 cache misses 仍然都是 compulsory misses），這時 cache 並沒有存滿。

發生 conflict misses 的替換，有三種方法：

  • LRU(least recently used,最近罕用)
    • 將集合中目前最不常用的的區塊加以取代
    • 可減少失誤次數,實作困難且成本高,常用在虛擬記憶體中
      e.g. 設block frame=4,進入的block順序為1,3,2,5,6,7,2,4,5,2,5,3,1,2,則2,2,5,2被hit
1 3 2 5 6 7 2 4 5 2 5 3 1 2
1 3 2 5 6 7 7 7 4 2 5
1 3 2 5 6 7 2 4 4 2 5 3
1 3 2 5 6 7 2 4 5 2 5 3 1
1 3 2 5 6 7 2 4 5 2 5 3 1 2
  • FIFO(first in first out,先進先出)
    • 將集合中最早進入的區塊加以取代
    • 實作較簡單,失誤較高
      e.g. 設block frame=4,進入的block順序為1,3,2,5,6,7,2,4,5,2,5,3,1,2,則2,5,2被hit
1 3 2 5 6 7 2 4 5 2 5 3 1 2
1 3 2 2 5 5 6 7 4 2 2
1 3 2 5 5 6 6 7 4 2 5 5
1 3 2 5 6 6 7 7 4 2 5 3 3
1 3 2 5 6 7 7 4 4 2 5 3 1 1

  • random(隨機選取)

    • 由集合中隨機選一個區塊加以取代
    • 實作最簡單,常用在快取記憶體

  • reference: 替代方法

SIMD Prefetch + Cache

      for i in `seq 1 100`; do  \
          printf "$$i " >> time.txt ; \
          ./naive_transpose >> time.txt ; \
          printf " " >> time.txt; \
          ./sse_transpose >> time.txt; \
          printf " " >> time.txt; \
          ./sse_prefetch_transpose >> time.txt; \
          printf "\n" >> time.txt ; \
       done

改變 _mm_prefetch 指令位置

  • prefetch 指令的主要目的，是提前讓 CPU 載入稍後運算所需要的資料。
  • 通常是在對目前的資料進行運算之前，告訴 CPU 載入下一筆資料。
  • 這樣就可以讓目前的運算，和載入下一筆資料的動作，可以同時進行。

Q: prefetch 能不能預取 指令 cache 和 data cache

  • reference: photo

  • Harvard architecture
    此種架構，分別儲存 instructions 和 data
    單獨存儲表示程式和資料儲存可分處不同地方。也表示著指令預取得以與其他活動並行。

  • reference:Harvard architecture

  • reference: photo

  • von Neumann architecture

簡單來說，此種架構部分的處理單元中含有
1.一個算術邏輯單元 (arithmetic logic unit) 和處理器暫存器 (processor registers)
2.含有指令暫存器和程式計數器的控制單元
3.含有一個儲存單元來保存資料和指令
4.輸入和輸出機制

此種架構的指令獲取和數據操作不能同時發生，因為它們共享公共匯流排。這被稱為 von Neumann 瓶頸，並經常限制系統的性能

sse prefetch

sse prefetch 1 沒有改變_mm_prefetch 指令位置
sse prefetch 2 改變_mm_prefetch 指令位置


執行 100 次後，平均時間分別為

sse prefetch 1: 56088.767
sse prefetch 2: 55974.668

時間為原本的 99.797％，減少的並不是很明顯，僅約 0.2％ 的差距

  • perf

    • 沒有改變 _mm_prefetch 指令位置
    ​​​​Performance counter stats for './sse_prefetch_transpose' (50 runs):

​​​​    10,839,523      cache-misses              #   60.111 % of all cache refs      ( +-  0.33% )
​​​​    18,032,645      cache-references                                              ( +-  0.24% )
​​​​ 1,813,591,769      instructions              #    2.65  insn per cycle           ( +-  0.00% )
​​​​   683,678,792      cycles                                                        ( +-  0.08% )

​​​​   0.220839448 seconds time elapsed                                          ( +-  0.31% )
    • 改變 _mm_prefetch 指令位置
    ​​​​Performance counter stats for './sse_prefetch_transpose' (50 runs):

​​​​    11,172,775      cache-misses              #   60.703 % of all cache refs      ( +-  0.26% )
​​​​    18,405,763      cache-references                                              ( +-  0.20% )
​​​​ 1,813,547,154      instructions              #    2.71  insn per cycle           ( +-  0.00% )
​​​​   668,991,058      cycles                                                        ( +-  0.14% )

​​​​   0.214681570 seconds time elapsed                                          ( +-  0.39% )

    兩個 cache misses 的值並沒有相差多少

  • perf raw counter:

    • r014c: LOAD_HIT_PRE.SW_PF
    • r024c: LOAD_HIT_PRE.HW_PF

    perf stat -e r014c ./sse_prefetch_transpose

    • 沒有改變 _mm_prefetch 指令位置
      SW hit: 286700
      HW hit: 253292

    perf stat -e r024c ./sse_prefetch_transpose

    • 改變 _mm_prefetch 指令位置
      SW hit: 1537262
      HW hit: 259003

avx prefetch

avx prefetch 1 改變_mm_prefetch 指令位置
avx prefetch 2 沒有改變_mm_prefetch 指令位置


執行 100 次後，平均時間分別為

avx prefetch 1: 47355.499
avx prefetch 2: 50230.853

Q: 討論為什麼圖片會這樣
時間為原本的 94.276 ％，大約減少 6 ％

  • perf

    • 改變 _mm_prefetch 指令位置
    ​​​​Performance counter stats for './avx_prefetch_transpose' (50 runs):

​​​​    14,018,457      cache-misses              #   62.922 % of all cache refs      ( +-  0.15% )
​​​​    22,279,089      cache-references                                              ( +-  0.13% )
​​​​ 1,684,193,250      instructions              #    2.50  insn per cycle           ( +-  0.00% )
​​​​   672,647,334      cycles                                                        ( +-  0.16% )

​​​​   0.225615808 seconds time elapsed                                          ( +-  0.40% )
    • 沒有改變 _mm_prefetch 指令位置
    ​​​​Performance counter stats for './avx_prefetch_transpose' (50 runs):

​​​​    13,336,332      cache-misses              #   58.380 % of all cache refs      ( +-  0.35% )
​​​​    22,843,932      cache-references                                              ( +-  0.23% )
​​​​ 1,684,019,663      instructions              #    2.49  insn per cycle           ( +-  0.00% )
​​​​   676,128,022      cycles                                                        ( +-  0.07% )

​​​​   0.224623318 seconds time elapsed                                          ( +-  0.25% )

    改變 _mm_prefetch 指令位置後， cache misses 反而增加，由原本 58.380 % 增至 62.922 % ，大約增加 4.5％

  • perf raw counter:

    • r014c: LOAD_HIT_PRE.SW_PF
    • r024c: LOAD_HIT_PRE.HW_PF

    perf stat -e r014c ./avx_prefetch_transpose

    • 沒有改變 _mm_prefetch 指令位置
      SW hit: 2030
      HW hit: 259499

    perf stat -e r024c ./avx_prefetch_transpose

    • 改變 _mm_prefetch 指令位置
      SW hit: 3900
      HW hit: 268269

perf raw counter

  • 參考 linux perf example
    其中說明在有些系統架構中，大多數的 counter 並不能被 perf list 找到，但如果你找到一個你想用的 counter ，你可以將它指定為一個 raw event (格式:rUUEE,UU == umask,EE == event)

  • example:

    ​​# perf stat -e cycles,instructions,r80a2,r2b1 gzip file1

​​Performance counter stats for 'gzip file1':

​​   5,586,963,328 cycles                    #    0.000 GHz                    
​​   8,608,237,932 instructions              #    1.54  insns per cycle        
​​       9,448,159 raw 0x80a2                                                  
​​  11,855,777,803 raw 0x2b1                                                   

​​     1.588618969 seconds time elapsed

r80a2，其中80是 mask number，a2 是 event number，可以查出 raw 0x80a2 是 RESOURCE_STALLS.OTHER 用來查看因為其它 resource issues 而被 stall 的 cycle數。r2b1同理是UOPS_DISPATCHED.CORE

raw counter 測試數據參考


































Performance counter stats for './sse_prefetch_transpose' (10 runs):

       753,555,879      L1-dcache-loads                                               ( +-  1.41% )  (20.78%)
        12,533,750      L1-dcache-load-misses         1.66% of all L1-dcache hits    ( +-  4.66% )  (19.03%)
       298,091,414      L1-dcache-stores                                              ( +-  1.65% )  (11.40%)
         3,626,299      L1-dcache-store-misses                                        ( +-  5.59% )  (12.06%)
  /* <not supported>      L1-dcache-prefetches */                                        
         1,174,323      L1-dcache-prefetch-misses                                     ( +-  8.22% )  (11.92%)
  /* <not supported>      L1-icache-loads */                                             
           127,860      L1-icache-load-misses                                         ( +- 17.28% )  (18.31%)
  /* <not supported>      L1-icache-prefetches */                                       
  /* <not supported>      L1-icache-prefetch-misses */                                  
         3,418,508      LLC-loads                                                     ( +-  6.44% )  (24.06%)
  /* <not supported>      LLC-load-misses */                                            
         3,219,088      LLC-stores                                                    ( +-  2.30% )  (23.69%)
  /* <not supported>      LLC-store-misses */                                           
           997,209      LLC-prefetches                                                ( +- 12.67% )  (11.63%)
  /* <not supported>      LLC-prefetch-misses */                                        
       675,085,070      dTLB-loads                                                    ( +-  1.68% )  (11.70%)
         4,973,121      dTLB-load-misses          #    0.74% of all dTLB cache hits   ( +-  9.00% )  (11.57%)
       270,220,422      dTLB-stores                                                   ( +-  0.92% )  (11.41%)
           163,715      dTLB-store-misses                                             ( +-  3.27% )  (11.19%)
  /* <not supported>      dTLB-prefetches */                                            
  /* <not supported>      dTLB-prefetch-misses */                                       
             2,221      iTLB-loads                                                    ( +- 15.88% )  (10.96%)
             3,428      iTLB-load-misses          #  154.37% of all iTLB cache hits   ( +- 38.32% )  (16.47%)
       261,610,532      branch-loads                                                  ( +-  3.23% )  (21.68%)
           509,599      branch-load-misses                                            ( +-  3.42% )  (21.35%)
         1,994,238      r014c   /* LOAD_HIT_PRE.SW_PF */                              ( +- 12.91% )  (21.05%)
           486,587      r024c   /* LOAD_HIT_PRE.HW_PF */                              ( +- 23.72% )  (20.91%)

       0.376223174 seconds time elapsed                                          ( +-  1.29% )

locality hint

  • prefetch 的意義

如果在CPU操作數據之前，我們就已經將數據提前加載到快取中，那麼就減少了由於快取未中 (cache-miss)，需要從記憶體取值的情況，這樣就可以加速操作，獲得性能上提升。使用主動快取技術來優化記憶體複製。

值得注意的是，CPU 對數據操作擁有絕對自由！使用預取指令只是按我們自己的想法對 CPU 的數據操作進行補充，有可能CPU當前並不需要我們加載到快取的數據。這樣，我們的預取指令可能會帶來相反的結果，比如對於多工系統，有可能我們沖掉了有用的 cache。不過，在多工系統上，由於執行緒 (thread) 或行程 (process) 的切換所花費的時間相對於預取操作來說太長了, 所以可以忽略執行緒或行程切換對預取的影響。

Q: locality

locality of reference(存取的局部性)
說明: 大多數的存取都集中在極少數的指令或資料上,其他多數的指令或資料則很少被取用
幫助: 讓快取記憶體只需很小的空間就可存放這些少數重覆的指令或資料,提高擊中率使平均存取時間接近快取記憶體時間,提高效能

可分為:

  • temporal locality(時間的局部性): 一個記憶體位址被存取後，不久會再度被存取
    • 如: 迴圈,副程式,以及堆疊,迴圈控制變數,計算總合變數
  • spatial locality (空間的局部性): 一個記憶體位址被存取後，不久其附近的記憶體位址也會被存取
    • 如: 循序指令、陣列，和相關的變數

ps:無存取局部性的有分支指令、雜湊搜尋表、二元搜尋…等

Q: cache invalidate

Cache invalidation is a process in a computer system whereby entries in a cache are replaced or removed. It can be done explicitly, as part of a cache coherence protocol. In such a case, a processor changes a memory location and then invalidates the cached values of that memory location across the rest of the computer system.

Q: cache invalidate VS cache flush

–Flush
把 Cache 內容寫回 Memory ,當 Cache 為 Write through ,不需要 Flush

–Invalidate
把 Cache 內容直接丟掉不要

Q: write back vs write through

Cache 的兩個類型：

–Write Through
當寫數據進 Cache 時，也同時更新了相應的 Memory 裡的內容

–Write back
只是寫到 Cache 裡，Memory 的內容要等到 cache 保存的內容要被別的數據替換或者系統做 cache flush 時，才會被更新。

在 write-back cache 中，cache, memory 的資料通常是不同步的。
所以可能會多使用 dirty bit 來標示說 memory 的資料已經是舊的。
當 cache 要將資料清除時，得負責把資料寫回 memory ～

以下為 prefetch 的指令：

void _mm_prefetch(char *p, int i)

從地址 P 處預取長度為 cache line 大小的 data cache，參數 i 指示預取方式。

其中預取的方式分成 4 類：

  • T0 預取資料到所有級別的快取
  • T1 預取資料到第一級以外所有級別的快取
  • T2 預取資料到第一、二級以外所有級別的快取
  • NTA 預取資料到非臨時 cache 結構中，可以最小化對快取的污染

以下實驗 prefetch distance = 8，附上的數據為第一次執行結果

L1d cache:   32K
L1i cache:   32K
L2 cache:   256K
L3 cache:  3072K
  • _MM_HINT_T0
naive:			443001 us
sse:			165594 us
sse prefetch:	  	 99746.6 us
  • _MM_HINT_T1
naive:			445146 us
sse:			167271 us
sse prefetch:	  	 96087.9 us
  • _MM_HINT_T2
naive:			446486 us
sse:			172104 us
sse prefetch:	  	 89992.4 us
  • _MM_HINT_NTA
naive:			375468 us
sse:			141636 us
sse prefetch:	  	122507 us

上面的四張圖，主要不同的部分是 sse prefetch 改動了 locality hint，可以觀察到的是 T0 的圖形 sse prefetch 抖動相當厲害，T1、T2的圖形就相對平順許多，NTA則是 sse prefetch 所需的平均執行時間相對其他三者來的高。

prefetch distance

做這個實驗，第一個要考慮的是 distance 要設多少才合理，回憶一下公式：

D≥[ls]

l 是 prefetch latency
s 是 the length of the shortest path through the loop body

參考 carolc0708 HackMD 筆記，嘗試算出 prefetch distance，但還不太清楚 mlc 工具如何使用。

  • distance 1 ~ 20

  • distance 1 ~ 100

  • distance 1 ~ 20 (只有這個實驗每個距離重複做20次取平均)

可以看到 distance = 8 的時候效果最好

改變 array size

不同 array size 的實驗結果

從下圖可知，矩陣大小越大，時間差越多

Q: 不知道為何? 矩陣大小每次增加 96 時，和每次增加 64 時，所呈現的圖都是一高一低的齒狀圖形，尤其是 naive 和 sse 特別明顯。
測試過程中，沒有辦法從 4096 大小，執行到 4096+40*64 大小，中途電腦滑鼠會無法動，而所得的資料，會極其怪異，每次測試都不大相同。

這是很棒的發現喔, 但是這樣的分佈是可以解釋的, 簡單回覆在下列文章
https://champyen.blogspot.tw/2017/05/cache-line.html
"champ"

  • 4096+i*64(i=0~29)
  • 4096+(i)*64(i=30~44)
  • 4096+(i)*64(i=45~59)

對上述關於不同 array size 的執行時間的分析

這是一個每次增加 64 的圖表分析（以此張圖作為分析）

這是一個每次增加 96 的圖表分析

在 i == 8 時，與上述 i == 12 時，是為同ㄧ大小 4864，並且能看出在 i == 8 時，與上述 i == 12 時的執行時間較久，表示 array size 在某些特定的值，執行時間較久。

  • 實驗環境為 6MB cache 的 Core-i5 6300HQ 而且以 Intel Skylake 架構而言,是 64 bytes cache line 和 8-way associative cache （n way set associatve 表示為是指 n 個 cache line 為 1 個 set ）。

  • 由上述資訊可計算出具備6MB/64/8 = 12288 sets (entries)

  • 這是一張 4 way set associative 的圖，1個 set 中有 4 個 cache line ，每個 cache line 為 64 bytes

champ: 請注意 8-way 的意思, 另外針對文中的計算方式, 解釋一下 i == 4 的情況

Cache line 填入次數計算

發現不同 array size 的執行時間不同的原因，有部份是因為 conflict misses ，以下算法為計算發生衝突的次數，大於 8 表示 cache line 有相當高的機會早已被 replace 。

首先考慮最簡單的 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 (8-way associative)

當 CPU 需要讀入 (1, 0) 時, 因為讀入 (0, 0) 所讀入的 cache line 有相當高的機會早已被 replace

考慮 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 == 2 的情況
於第 n 行的 cache line index 計算為: (X + 264*n) % 12288

  1. 12288 / 264 = 46.55 …
  2. 12288 % 264 = 144

而 264 與 144 兩者最小公倍數為 1584
1584/144 = 11 (表示反覆繞 cache line index 0 ~ 12288 到第 11 次才開始 cache line index 有所重疊)
而 4224/46.55 約為 90.74, 90.74 / 11 = 8.25 > 8

考慮 i == 4 的情況
( 272 = 1617 -> 43524 = 1024 * 17 )
於第 n 行的 cache line index 計算為: (X + 272*n) % 12288

  1. 12288 / 272 = 45.17 …
  2. 12288 % 272 = 48

而 272 與 48 兩者最小公倍數為 816
816/48 = 17 (表示反覆繞 cache line index 0 ~ 12288 到第 17 次才開始 cache line index 有所重疊)
而 4352/45.17 約為 96.35, 96.34 / 17 = 5.66 < 8

考慮 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

考慮 i == 12 的情況
( 304 = 1619 -> 48644 = 1024 * 19 )
於第 n 行的 cache line index 計算為: (X + 304*n) % 12288

  1. 12288 / 304 = 40.42 …
  2. 12288 % 304 = 128

而 304 與 128 兩者最小公倍數為 2432
2432/128 = 19 (表示反覆繞 cache line index 0 ~ 12288 到第 19 次才開始 cache line index 有所重疊)
而 4864/40.42 約為 120.34, 120.34 / 19 = 6.33 < 8

Perf 分析

下面 perf 分析會使用到的 raw counter：

  • r02D1 - L2 cache hit
  • r10D1 - L2 cache miss
  • r04D1 - L3 cache hit
  • r20D1 - L3 cache miss

這幾個是屬於 Intel® Core™ i5-6300HQ CPU 的 raw counter

實驗細節參見:

Column major 與 Row major

  • 分析 array size 與 總執行時間 
    ​​​​    int repeat_times = 1000000000;
​​​​    long array[array_size];
​​​​    for (int i = 0; i<array_size; i++)
​​​​        array[i] = 0;
​​​​    int k = 0;
​​​​    while (int j++ < repeat_times){
​​​​        if (k == array_size)
​​​​            k=0;
​​​​        c = array[k++];
​​​​    }

  • 從上圖可以發現從 16*4 bytes 後的數值增加幅度很大，原因是當 array sizes 小於 64Bytes 時，array 可能落在同ㄧ條 cache line 中。然而一個元素的存取就會使整條 cache line 被填充，也就是說當我接下來要存取的元素，不在同一個 cache line 的話，就會使另一條 cache line 被填充。而后面的若干個元素則會受益於 cache 带来的加速。所以當數组大於 64 Bytes 时，一定需要两條 cache line，而由於 cache line 填充的时間遠高於數據在同一個 cache line 存取的時間，因此多一次快取填充，會使總時間增大。

  • 下圖陣列存取的方式，第一種會快於第二種，因為
    在以 row major 存取陣列時，當你第一次讀取，會讀取 a[0][0] 的記憶體地址，此時，整個 cache line 都被從主記憶體取到 cache 中，並且，接著讀取同一個 cache line 中的其他數值會非常快，所以接著存取 a[0][1] ～ a[0][7] 會很快。
    但在以 col major 存取陣列時，當你第一次讀取，會讀取 a[0][0] 的記憶體地址，此時，整個 cache line 都被從主記憶體取到 cache 中，然而，接著存取到的卻是 a[1][0] ，因為不在同一個 cache line 中，所以會使另一條 cache line 被填充，導致時間花費久。

在不同 array size 中，可以從下圖看出 row major 比 col major 的執行時間快

  • row major
  • col major

SMP 考量點

待整理

Last changed by 
 
sysprog
System Software Programming
2
41
81667
Published on HackMD