前幾天在看論文時看到這樣一段話：We observe that a program often exhibits several different memory access patterns with different objects or at different phases, and they benefit from different Cache configurations. For example, sequential accesses fit a small directly mapped Cache with a Cache line size of multiple consecutive data elements, while accesses with good locality but large working sets fit a relatively large set-associative Cache.
這學期在上計算機體系結構課的時候老師提到過Cache的三種映射方式是direct mapping，set associative和fully associative。但是當時只是單純記住了這個知識點，並沒有理解，因此看上面這段話看的一頭霧水，Cache裏的數據存儲形式是怎樣的？不同的workload爲什麼會受益於不同的Cache映射方式？帶着這些疑問，我去查了一些資料複習了一下順便寫了這篇筆記。
首先來明確一下Cache是什麼，本文中的Cache指的是CPU高速緩存，是用於減少處理器訪問內存所需平均時間的部件。在金字塔式存儲體系中它位於自頂向下的第二層，僅次於CPU寄存器。其容量遠小於內存，但速度卻可以接近處理器的頻率。
其實在遙遠的PC-AT/XT和286時代，CPU是沒有Cache，直接訪問內存的。那後來爲什麼要在CPU寄存器和內存之間設置一個CPU緩存呢？這是因爲CPU訪問寄存器和內存的延遲差距太大了。
可以看到，訪問寄存器的延遲約爲0.3ns，而訪問內存的延遲爲62.9ns [2]，兩者之間差了數百倍，如果在Cache中沒有我們想要的數據，那麼CPU就需要等待漫長的load操作將數據從內存copy到Cache中。因此後來引入了多級Cache，等級越高，速度越慢，容量越大。在3級Cache的緩衝下，相鄰Cache之間和Cache與memory之間的延遲差距也越來越小。讓我們來看一下一個真實的案例——ARMv8-A架構的Cortex-A53處理器的Cache組織方式[3]（Switch上的SoC——Tegra X1裏就是四個Cortex-A57核心和四個Cortex-A53核心）。
Cortex-A53 通常採用兩級或多級Cache來實現，即小型 L1 指令緩存(instruction Cache)和數據緩存(data Cache)以及較大的統一 L2 緩存，該緩存在集羣(cluster)中的多個內核(core)之間共享。此外，還可以有一個外部 L3 緩存在集羣之間共享。CPU每個core都有一個私有的L1 Cache。一個cluster內的所有core共享一個L2 Cache，L2 Cache不區分指令和數據，都可以緩存。所有cluster之間共享L3 Cache。L3 Cache通過總線和主存相連。
現在我們只知道了Cache是什麼，以及爲什麼要有Cache，那先來思考一個問題，如果是你來設計Cache，你會考慮哪些方面？
首先，Cache的大小應該是多大呢？裏面的內容的組織形式是什麼樣的？第二，既然是作爲CPU寄存器和內存之間的緩衝，那麼肯定是存儲內存中的數據，怎麼存儲和尋找呢？另外，既然是將內存中的數據複製到Cache中，一致性的問題也需要考慮，如果內存中的數據改變了但是Cache中的數據沒有變，這時CPU再去Cache中訪問數據就會訪問到過時的數據。
天吶，居然要考慮這麼多，那我們還是先來直接看看現在的Cache的工作方式是什麼吧。
衆所周知，在程序執行過程中，CPU會從內存中讀取所需的數據到Cache中，而需要取哪些數據是根據所需數據的地址來決定的，一個地址對應一個字節，32位系統的地址空間就是2^32B即4GB，64位系統的地址空間就是2^64B（以目前的科技發展水平來說基本不可能用完）。一種比較直觀的想法是，在Cache中存儲一些訪問過的數據作爲緩存，CPU讀取數據的時候先去Cache裏面找，如果找不到就去內存裏讀，讀到了順便就放在Cache裏。但是程序訪問內存具有空間局部性的特徵，短時間內訪問的數據或是指令大概率會在一段連續的地址範圍內，因此Cache和內存之間的傳輸卻不是以單個字節進行的，而是一次取特定大小的連續內存。這個特定大小我們就稱爲cache line。它也是Cache的基本組成單位。cache line的大小在4-128字節，一般爲64B。Cortex-A53的cache line大小就爲64B。注意這裏Cache的大小（或者說容量）不包括標記位（tag）和有效位（後面會提到）。
那麼現在我們知道了Cache是由一個個cache line組成的，那Cache裏肯定不能光存儲數據，不然CPU靠什麼來查找裏面的數據呢？
我們假設這樣一種情況：
- 64位系統（地址用64bits=8Bytes表示）
- 32GB=2^35B內存
- 1MB=2^20B L1 Cache
- cache line大小爲64B
最早的時候Cache使用一種叫做direct mapping的組織方式。在這種模式下，64位地址被分爲3個部分。首先，L1 Cache中一共有1MB/64B=2^20B/2^6B=2^14個cache line，因此我們需要14位 Index 來標記是哪一個cache line。找到了cache line之後，需要6位 Offset 來在64B的cache line中找出是哪一個Byte，還剩下64-6-14也就是44位我們將其作爲標記位（tag）。可能有聰明的同學已經想到了，我們只需要兩個部分也就是Index和Offset就可以定位Cache中一個cache line中的某一個字節了呀，爲什麼還要設置tag呢？
這是因爲我們剛纔一直討論的是地址，這64位地址不僅僅是用來在Cache中尋找cache line的，它同時也是內存中的一個字節的唯一標識，也就是說，後14+6=20位相同但前44位不同的地址，儘管他們指向了Cache中同一條cache line中的同一個字節，但是它們標識的是內存中的不同位置！因此CPU拿着一條地址在Cache中尋找數據的時候需要tag來標識我們正在尋找的數據究竟是不是正確的，相應地，每條cache line中也必須包含tag。
那這種方式有沒有什麼問題呢？設想一下如果我們需要並行訪問內存的多處區域，如果這些區域正好包含了Index相同的內存地址，那麼就會頻繁地發生衝突，因爲它們都要用到Cache中的同一條cache line，從而降低性能。這種現象叫做緩存顛簸（cache thrashing）
那麼有沒有方式可以減少這種衝突造成的影響呢？思考一下，在衝突發生時，我們可不可以通過某種方式減少這種內存的頻繁換入換出？
答案是有的，現在的Cache普遍採用一種叫做Set Associative的方式進行組織，簡單來說 n-way associative 就是把Cache進行了分組，使得每個組（Set）裏面有n個cache line，這樣在遇到Index相同但是tag不同的情況時就可以在一個組中同時存n個cache line，比如2-way associative就是下面這種形式，下面我們假設CPU爲4-way associative
那我們現在看看在set associative的情況下如何尋找cache line，在L1 Cache中一共有2^14個cache line，而又因爲是4-way associative，因此一共有2^14/2^2=2^12個組，也就是說我們需要12位Index來找到是哪個組。同時我們同樣需要6位Offset來在64B的cache line中找出是哪一個Byte。
那64位的地址我們已經用掉了6+12=18位，剩下的46位我們將其作爲標記位（tag）
CPU在訪問Cache時，先根據index找到set，然後將組內的所有cache line對應的tag和地址中的tag部分對比，如果其中有相等的就說明緩存命中也就是找到了所需數據。
對比一下direct mapping和set associative，我們可以發現其實direct mapping也可以看做成set associative中set大小爲1的情況。那有大膽的同學可能會想，如果把set大小增大，變成整個Cache會怎麼樣呢？這種情況我們就稱爲fully associative。
在fully associative的情況下，因爲整個Cache就是一個組，那麼我們就不需要Index來尋找是哪個set了，因此地址只剩下了tag和offset。因爲在訪問Cache時高速緩存電路必須並行匹配許多tag，想要構造又大又快的fully associative cache是十分困難且昂貴的。因此fully associative cache只適合做小容量的cache，如TLB（又是一個坑）。
最後我們回到剛開始的那段話，爲什麼順序訪問適合具有多個連續數據元素的cache line大小的小型direct mapped cache，而具有良好局部性但較大工作集的訪問適合相對較大的set associative cache呢。這是因爲direct mapped Cache能夠利用順序訪問的局部性，將連續數據元素映射到同一個cache line中，取了一個元素相當於取了相鄰連續的多個元素。具有良好局部性說明程序訪問內存會比較集中在某一個範圍內，因此最好用大一點的Cache把這塊內存儘量裝下，此外，工作集較大說明程序運行時訪問內存範圍較大，如果是direct mapped cache很有可能會出現thrashing，因此最好使用set associative cache。
關於CPU Cache這次先講這麼多，後面會（視心情）更新其他關於存儲相關的知識筆記。（可能也會更新一些生活方面的？）
[1] 維基百科編者. CPU緩存[G/OL]. 維基百科, 2023(20231213)[2023-12-13]. https://zh.*********.org/w/index.php?title=CPU%E7%BC%93%E5%AD%98&oldid=80104215.[2] https://cs.brown.edu/courses/csci1310/2020/assign/labs/lab4.html
[3] https://developer.arm.com/documentation/den0024/a/Caches
[4] Bryant, Randal E., and David R. O'Hallaron. Computer Systems: A Programmer's Perspective. 3rd ed., Pearson, 2016.
更多遊戲資訊請關註：電玩幫遊戲資訊專區
電玩幫圖文攻略 www.vgover.com
