細說Cache-L1/L2/L3/TLB

本來打算今天把Cache寫透的，結果今天陪娃出去玩了兩次，先虎頭蛇尾了，放出來，有時間再補。補了我會通知的~~。大家別忘了關注我的專欄。

概述

cache是一種又小又快的存儲器。它存在的意義是彌合Memory與CPU之間的速度差距。

現在的CPU中有好幾個等級的緩存。通常L1和L2緩存都是每個CPU一個的, L1緩存有分為L1i和L1d，分別用來存儲指令和數據。L2緩存是不區分指令和數據的。L3緩存多個核心共用一個，通常也不區分指令和數據。 還有一種緩存叫TLB，它主要用來緩存MMU使用的頁表，通常我們講緩存（cache)的時候是不算它的。

Cache hierarchy of the K8 core in the AMD Athlon 64 CPU

Cache Line

Cache存儲數據是固定大小為單位的，稱為一個Cache entry，這個單位稱為Cache line或Cache block。給定Cache容量大小和Cache line size的情況下，它能存儲的條目個數(number of cache entries)就是固定的。因為Cache是固定大小的，所以它從DRAM獲取數據也是固定大小。對於X86來講，它的Cache line大小與DDR3、4一次訪存能得到的數據大小是一致的，即64Bytes。對於ARM來講，較舊的架構(新的不知道有沒有改）的Cache line是32Bytes，但一次內存訪存只訪問一半的數據也不太合適，所以它經常是一次填兩個Cache line，叫做double fill。

CPU從Cache數據的最小單位是位元組，Cache從Memory拿數據的最小單位（這裡不講嵌入式系統）是64Bytes，Memory從硬碟拿數據通常最小是4092Bytes。

替換策略

Cache里存的數據是Memory中的常用數據一個拷貝，Cache比較小，不可以緩存Memory中的所有數據。當Cache存滿後，再需要存入一個新的條目時，就需要把一個舊的條目從緩存中拿掉，這個過程稱為evict，一個被evict的條目稱為victim。緩存管理單元通過一定的演算法決定哪些數據有資格留在Cache里，哪些數據需要從Cache里移出去。這個策略稱為替換策略（replacement policy)。最簡單的替換策略稱為LRU(least recently used)，即Cache管理單元記錄每個Cache line最近被訪問的時間，每次需要evict時，選最近一次訪問時間最久遠的那一條做為victim。在實際使用中，LRU並不一定是最好的替換策略，在CPU設計的過程中，通常會不段對替換策略進行改進，每一款晶元幾乎都使用了不同的替換策略。

寫入策略與一致性

CPU需要讀寫一個地址的時候，先去Cache中查找，如果數據不在Cache中，稱為Cache miss，就需要從Memory中把這個地址所在的那個Cache line上的數據載入到Cache中。然後再把數返回給CPU。這時會伴隨著另一個Cache 條目成為victim被替換出去。

如果CPU需要訪問的數據在Cache中，則稱為Cache hit。

針對寫操作，有兩種寫入策略，分別為write back和write through。write through策略下，數據直接同時被寫入到Memory中，在write back策略中，數據僅寫到Cache中，此時Cache中的數據與Memory中的數據不一致，Cache中的數據就變成了臟數據(dirty)。如果其他部件（DMA， 另一個核）訪問這段數據的時候，就需要通過Cache一致性協議(Cache coherency protocol)保證取到的是最新的數據。另外這個Cache被替換出去的時候就需要寫回到內存中。

Cache Miss 與CPU stall

如果發生了Cache Miss，就需要從Memory中取數據，這個取數據的過程中，CPU可以執行幾十上百條指令的，如果等待數據時什麼也不做時間就浪費了。可以在這個時候提高CPU使用效率的有兩種方法，一個是亂序執行（out of order execution)，即把當前線程中後面的、不依賴於當前指令執行結果的指令拿過來提前執行，另一個是超線程技術，即把另一個線程的指令拿過來執行。

L1/L2 Cache速度差別

L1 cache: 3 cycles

L2 cache: 11 cycles

L3 cache: 25 cycles

Main Memory: 100 cycles

L1/L2 Cache都是用SRAM做為存儲介質，為什麼說L1比L2快呢？這裡面有三方面的原因：

1. 存儲容量不同導致的速度差異

L1的容量通常比L2小，容量大的SRAM訪問時間就越長，同樣製程和設計的情況下，訪問延時與容量的開方大致是成正比的。

2. 離CPU遠近導致的速度差異

通常L1 Cache離CPU核心需要數據的地方更近，而L2 Cache則處於邊緩位置，訪問數據時，L2 Cache需要通過更遠的銅線，甚至更多的電路，從而增加了延時。

L1 Cache分為ICache（指令緩存）和DCache(數據緩存）,指令緩存ICache通常是放在CPU核心的指令預取單遠附近的，數據緩存DCache通常是放在CPU核心的load/store單元附近。而L2 Cache是放在CPU pipeline之外的。

為什麼不把L2 Cache也放在很近的地方呢？由於Cache的容量越大，面積越大，相應的邊長的就越長（假設是正方形的話），總有離核遠的。

下面的圖並不是物理上的圖，只是為大家回顧一下CPU的pipe line。

另外需要注意的是這張圖裡展示了一個二級的DTLB結構，和一級的ITLB。

3. 製程不同的造成的速度差異

在實際設計製造時，針對L1/L2的不同角色，L1更加註重速度， L2更加註重節能和容量。在製程上這方面有體現，（但我不懂，。。。。）。在設計時，這方面的有體現：

首先， L1 Cache都是N路組相聯的，N路組相聯的意思時，給定一個地址，N個Cache單元同時工作，取出N份tag和N份數據，然後再比較tag，從中選出hit的那一個採用，其它的丟棄不用。這種方式一聽就很浪費，很不節能。

另外，L2 Cache即便也是N路組相聯的，但它是先取N個tag，然後比對tag後發現cache hit之後再把對應的數據取出來。由於L2是在L1 miss之後才會訪問，所以L2 cache hit的概率並不高，訪問的頻率也不高，而且有前面L1抵擋一下，所以它的延遲高點也無所謂，L2容量比較大，如果數據和tag一起取出來，也比較耗能。

通常專家都將L1稱為latency filter, L2稱為bandwidth filter。

L3 Cache

L1/L2 Cache通常都是每個CPU核心一個（x86而言，ARM一般L2是為一個簇即4個核心共享的），這意味著每增加一個CPU核心都要增加相同大小的面積，即使各個CPU核心的L2 Cache有很多相同的數據也只能各保存一份，因而一個所有核心共享的L3 Cache也就有必要了。

L3 Cache通常都是各個核心共享的，而且DMA之類的設備也可以用。

由於L3 Cache的時延要求沒有那麼高，現在大家也要考慮不使用SRAM，轉而使用STT-MRAM，或是eDRAM來做L3 Cache。

邏輯Cache和物理Cache

Cache在系統中的位置根據與MMU的相對位置不同，分別稱為logical Cache和physical cache。

Logical Cache接受的是邏輯地址，物理Cache接受的是物理地址。

logical cache有一個優勢就是可以在完成虛擬地址到物理地址的翻譯之前就可以開始比對cache，但是有一個問題就是Cache 一致性還有cache eviction必須通過物理地址來做，因為多個虛擬地址可能對應同一個物理地址，不能保證不同的虛擬地址所以應的cache就一定不是同一份數據。為了解決這個問題，就不得不把物理地址也保存在為tag。這樣tag要存的內容就增加了一倍。

相對而言，physical cache由於一開始就是物理地址，所以只需要存物理地址為tag，而不需要再保存虛擬地址為tag，看起來簡單了很多。

其實總結起來，Cache的tag有兩種作用：（1）對於N路組相聯cache中，通過tag比對選擇使用哪一路的數據，（2）決定cache hit還是miss。前者配合操作系統的情況下，虛擬地址就可以做到，比如說給虛擬地址和物理頁配對的時候總是保證根據兩者的某些位來選way的時候是一樣的，而且前者不需要完全的正確，偶爾錯一些是可以接受的，你可以先選出數據，默認是cache hit，然後拿著數據是計算，但後來通過物理tag比對時發現是miss的情況下，再無效掉這次計算，反正cache miss的情況下cpu本來也需要stall好多個cycle。後者則必須依靠物理地址才可以做到。這樣一來，很多設計都把虛擬地址tag弱化為hint, 僅用於選哪個way。

又沒寫完了，心情不好，吐嘈一下，為什麼有些人自己能力差無法跟上優秀的人節奏，一點都不感到羞愧，反而理直氣壯的要求別人為他維持他自己的心理舒適區？

以下是後面接著寫時需要參考的資料，大家也可以自己看看。

CPU cache - Wikipedia

https://faculty.tarleton.edu/agapie/documents/cs_343_arch/04_CacheMemory.pdf

http://www.ecs.csun.edu/~cputnam/Comp546/Putnam/Cache%20Memory.pdf

進一步閱讀：

https://cseweb.ucsd.edu/classes/fa14/cse240A-a/pdf/08/CSE240A-MBT-L15-Cache.ppt.pdf

http://www.ecs.csun.edu/~cputnam/Comp546/Putnam/Cache%20Memory.pdf

https://ece752.ece.wisc.edu/lect11-cache-replacement.pdf

http://www.ipdps.org/ipdps2010/ipdps2010-slides/session-22/2010IPDPS.pdf