Briding the gap

Cache 存在的意義是彌合內存與CPU之間的速度差距，CPU的指令執行是低於ns級的，而內存的訪存時延時十幾到幾十ns級的，一次訪存操作，CPU就需要等幾十上百個時鐘周期，這樣會嚴重降低系統的整體效率。然而內存速度慢僅體現在時延上，從帶寬的角度，內存又是能滿足CPU的要求的，這時引入一個容易稍小的快速存儲介質就可以將這個時延隱藏掉。具體就是在CPU執行某條訪存指令之前，先將需要訪問的內存數據載入到Cache中，CPU執行到那條指令時，數據已經在Cache，因而可以以同樣數量級的時延訪問到數據。

三種典型組織形式

CPU發出一個訪存指令，怎麼才能知道目標地址上的數據在Cache中是否存在呢？這就涉及Cache的組織形式問題。Cache通常理解為一個表，表中的每個條目記錄了一個內存塊的數據及這個內存塊的起始地址。這樣一個條目稱為一個Cache line。一個Cache line存儲的數據大小（即內存塊的大小）在一個系統中通常是固定的，即每個cache line都是等長的。在x86系統中，這個數據是64Bytes。這也正常是一次DDR內存訪問能得到的數據大小。一個Cache line不但要記錄數據，還要記錄數據對應的地址，通常只記錄地址的一部分，比如說在32位系統中，Cache line為64Bytes的情況下，只要記錄32 - 6 = 26個高位就好了。這裡的5取自2^6=64。

怎麼根據地址去查詢Cache是否命中呢？最簡單的辦法是拿這個地址與Cache中的第一行的tag去對比，對上了就命中，沒有對上的就是不命中。查詢Cache的速度不能慢，所以這個挨個比較需要用硬體去並行的做。這個做法（做法1）做起來硬體複雜無比。

全相聯緩存

最好是能拿到地址，我就知道它可能存儲在Cache的哪一行，我再去那一行去看，如果和那一行的tag對得上就命中，對不上就是不命中。一個可行的辦法就是拿內存地址對Cache的總大小取模，模的值就是Cache的目標行號，規定每個內存地址上的數據只能存在這個目標行。我們暫時稱這種辦法是做法2。做法2有一個顯著的問題就是某個內存地址上的數據只能存在固定的Cache行上。如果遇到兩個取模後相同的地址，做其中一個就沒有辦法存進去，此時其他Cache行是空也不能用，因而可能造成空間利用率低。做法1由於沒有這個限制，只要Cache中還是未存儲的空間，就可以不用換出某個Cache行。

直接射緩存

圖示的Cache中有8行，每行的大小為16位元組。給定一個內存地址，它的最低4位對於從Cache中取數據來講是沒有用的。真正有用的是高28位。這28位數對Cache行數取模，得到的值恰好是這28位中的低3位。因而圖中用低3位做索引，從Cache中選中一行。選出來的一行可能用目標內存的數據，也可能是空的，也可能是其他與類似地址（低三位相同）上的內存數據。因而選出來後，還要拿高25位與tag比對，才知道選出來的數據是否是目標內存塊上的數據。

直接映射緩存地址含義

做法1和做法2是兩個級端，做法1稱為全關聯緩存，即每個內存地址都可以與任何內存行關聯，做法2稱為直接映射緩存，即每個內存地址直接映射某個Cache line，不可以佔用其他Cache line。

針對做法2，考慮到同時訪問多個映射到同一個Cache line的內存地址的可能性也不是那麼大，提出了一個優化辦法，即在做法2的基礎上，每個Cache line引入幾個影子行。比如說原來的一個Cache line現在變成了4個Cache line，則只要同一段時間使用的映射到這一行的內存地址不多於4，就不會出現換出。這種一個內存地址對應一組幾個Cache line的方式稱為n路組相聯緩存。

兩路組相聯緩存（2-way associative 8-entry cache)

推薦閱讀：