iT邦幫忙

2021 iThome 鐵人賽

DAY 14
0
Software Development

閱讀 Linux Kernel 文件系列 第 14

# Day 14 Cache and TLB Flushing Under Linux (Q&A - II)

今天來複習 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

附錄

圖片來源

參考資料


上一篇
# Day 13 Cache and TLB Flushing Under Linux (Q&A - I)
下一篇
# Day 15 Cache and TLB Flushing Under Linux (summary)
系列文
閱讀 Linux Kernel 文件30

尚未有邦友留言

立即登入留言