今天來複習 cache 相關的知識！
首先可以參考一下這篇：Day.8 Cache 的基本原理

cache 相關計算

cache 是一個折衷的設計，存取速度比 RAM 快上一大截，比較接近 CPU 的運作速度，但是 size 沒有 RAM 大，所以 cache 能夠儲存的資料量一定是 RAM 的子集，那麼要怎麼知道現在 CPU 要存取的資料有沒有在 cache 中呢？
cache 的設計原理有點像是一個雜湊表(hash table)，取要存取位址的某些部份來做比對，很多資訊工程碩士班的入學考試，都會有相關的題目，筆者作為一個考試錄取的碩士生，從來沒有真正的理解這部分怎麼計算XDDDD
直到這次的整理，才大致上瞭解 cache 計算的細節，那我們就以考題為例，來複習一下 cache 的相關計算囉！

• 重點：
  • cache 的 hashing 方式是將要比對的位址，分成以下幾個部分：

    [ tag | index | block or line offset | byte offset ]
    

    • 計算方法
      • byte offset：用來存取一個 word 裡面的某個 byte，所以所需的 bit 數會是可以代表一個 word 裡面可以存的 byte 數，通常 1 word == 4 byte 所以這個部分通常為 2 bit
      • block offset：用來存取 cache line 中的某個 word，所以由 cache line size(cache block size) 和 byte per word 來決定，舉例 64 B 的 cache block size，4 byte per word，那 block offset 就是 4 bit (64/4 == 2^4)
      • index：用來存取某個 set，所以由 way 和 cache block entry 數目決定；若為 direct-mapped，表示有 cache block entry 這麼多個 set；若為 fully associative 則是只有 1 個 set (index bit 數目為零)；若是 n-way associative，則 set 數量 == (# of cache block entry / n)
      • tag：用來比對是否存在 cache 中的索引，bit 數量 == (# of bit representing the address space - # of bit for byte offset - # of bit for block offset - # of bit for index)
  • 題目通常會提類似 "64 KB資料量大小的 cache，<其他的一些條件>，請問 cache 的大小"
    • cache 是由 tag bit、valid bit 還有儲存的資料量所組成，題目給的是儲存的資料量，要來計算整個 cache 的大小
    • 題目若沒有多加描述的話，全部都是 byte addressable (byte offset == 2 bit)

題目範例

題目	答案

cache & TLB: VIVT、VIPT、PIPT

從上面可以大致上理解，cache 比對的方式，那麼接下來記錄的是 cache 比對方式的種類。
上個圖：

TLB 的位置決定了 cache 比對的方式，最左邊 PIPT(Physically Indexed, Physically Tagged)，中間 VIVT(Virtually Indexed, Virtually Tagged)，最右邊 (Virtually Indexed, Physically Tagged)。

• VIVT：上述 cache 的相關計算都是用 VA 來算的
  • 優點：VA 一出 CPU 就直接可以去 cache 做比對，效率高
  • 缺點：會有 aliasing 問題(包含了 homonyms 和 synonyms)
    • homonyms：同一個 VA 對應到 2 個不同的 PA
    • synonyms：同一個 PA 對應到在 cache 中的 2 個 VA；對其中一個 VA 做修改，會導致兩個 VA 的值有歧異的問題。
    • 解法： flush cache
• PIPT：上述 cache 的相關計算都是使用 PA 來計算
  • 優點：不會有 aliasing 問題
  • 缺點：要經過 TLB 轉譯後才會去比對 cache，若 TLB miss 會有極大的 latency
• VIPT： 則是兩者的折衷， Index 部分可以直接到 cache 中做比較，而 tag 的部分則是要經過 TLB 做轉換，換成 PA 之後才做比較
  • 優點：TLB 和 cache 的比對可以並行，且有機會避免 aliasing 問題，兼具 VIVT 與 PIPT 的部分好處
  • 缺點：還是有機會有 aliasing 問題 (synonyms)
    • 解法：cache coloring、設計支援 alias detection 的硬體、設計使 VIPT 表現得像是 PIPT

附錄

圖片來源

參考資料

• 題目來源 (大碩 計算機組織與結構 講義)
  • Ptt Grad-ProbAsk1
  • Ptt Grad-ProbAsk2
• stackoverflow：Cache Addressing
• stackoverflow：Cache Addressing confusion
• CPU Cache 原理探討
• 附錄.B 記憶體架構複習
• Cache 原理和實際影響
• chapter 21 cache
• 深入理解cache對寫好程式碼至關重要
• L1 Cache architecture in ARM
• 如何計算 CPU Cache size?
• page coloring
• 圖解| CPU-Cache
  以上資料都閱讀過的話，相信對 cache 會有一定程度的瞭解的！
  今天複習了 cache 相關的計算和觀念，也回答了部分自己在閱讀這份文件的疑惑，明天來做些總結，就啟程前往下篇文件吧！
  感謝各位，我們明天見！