為甚麼我們需要 Cache?

在思考為甚麼需要 Cache 之前，先思考程序是如何運行起來的 ?

我們知道程序是因運行在 RAM 之中，當我們需要運行一個 process 時，首先會從磁盤設備中將可執行的程序Load到主記憶體中，然後開始執行，然後如有需要計算，則我們必須透過在CUP內部的通用暫存器，在寫回我們的主記憶體。

但在現實中，CUP的通用暫存器與記憶體之間有很大的速度落差(將近百倍)，因此CUP必須等待記憶體的時間，因此，我們有一種折中的方法，那就是製作一個速度極快的同時又容量極小的存儲設備，其成本也不會太高。這塊存儲設備我們稱作 Cache Memory。

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

Cache hierarchy

現代的電腦，引入了多層級的快取機制(Cache hierarchy)，可以看到快取記憶體從 L1 的速度 1.1ns 到 L3 的 12.8ns，都是為了讓系統性能提升。

圖片連結

多層級的Cache之間如何運作?

CPU要訪問的資料在cache中有緩存，稱為"命中" (hit)，反之則稱為"缺失" (miss)，電腦會從L1 cache 到 L4 cache 查詢是否命中，如果都缺失(Miss)，就必須從主記憶體中Load資料，在多層級的Cache之間工作不須保證某一地址的資料緩存只會存在於多層級 Cache 其中之一。

快取記憶體的設計方式

Cache 的組成

在現代大多數的處理器中，Cache 的大小稱為 Cache Size，代表cache 可以緩存的最大數據的大小，Cache被分成很多行 (Cache Line)，Cache Line 大小不一，從16Byte 到 128Byte不等。

舉一個例子：我們共有８行的cache line，cache line 的 size 為 8 Bytes，所以我們可以利用 3 bits 來循址 8 bytes 中的某一字節，我們稱這個部分 bits 的組合為 offset， 8 行的cache line，同理需要 3 bits 查找某一行，這部分稱之為 index，我們又引入tag array區域，tag array和data array一一對應。每一個cache line都對應唯一一個tag，tag中保存的是整個地址位寬去除index和offset使用的bit剩餘部分，所以，當我們根據地址中index位找到cache line後，取出當前cache line對應的tag，然後和地址中的tag進行比較，如果相等，這說明cache命中。如果不相等，說明當前cache line存儲的是其他地址的數據，這就是cache缺失

快取記憶體有三種對映機制

• 直接對映式 Direct Mapped
  • 直接對映可以理解為每個地址都可以立刻直接且只能映射到某個Cache Line上，有那些壞處呢？那就是Cache Miss率極高，因為數據的相關性和局限性，當兩個變數映射到同一個 cache line 時，他們會不停地把對方替換出去。
• 完全關聯式 Fully Associative
  • 完全關聯就是所有Cache Line 可以對映所有的記憶體地址，可以減少大量的 Cache Miss，但是查詢Cache是否命中的代價(Over Head)很高，必須遍歷整個Cache。
• N路集合關聯式 n-way associative
  • 直接對映式和完全關聯式尋找平衡所提出的方法，n-way的意思就是將 Cache分成 N 組，每一組對映一個記憶體地址，對於 組中只需遍歷組中每個元素就可以確定對象是否在快取中。

三種對映機制詳細說明 Cache的基本原理

參考資料

現代處理器設計: Cache 原理和實際影響
Cache的基本原理
Cache是怎么组织和工作的？