标签

, ,

 http://chuck42315.wordpress.com/2011/10/29/cache/

最近被問了些有關 Cache 的知識,趁這個機會來了解一下吧 XD
什麼是 L1, L2, L3?
什麼又是 VIVT, VIPIT, PIPT?
還有 Aliasing 的問題又是什麼東西呢?
另外常聽到 Write Through, Write Back 則是代表什麼呢?
Non-Cacheable 又是怎麼回事呢?

Multi-level Cache
L1, L2, L3。L 原來是 Level 的意思
在多層 Cache 的架構下,L1 是最靠近 CPU 的 Cache
當 L1 發生 Cache Miss 時,就會嘗試到 L2 中尋找,若不幸又發生 Cache Miss
那就再進到下一層找資料,最後都沒找到時才會到 Memory 去尋找!

這其實是一個 tradeoff,Cache Size 越大 hit rate 越高
但同時 latency 也越高,需要較多時間搜尋 …
所以就演變出這種多層的架構~ 以較大的 cache 當作小 cache 的 back up
L1 通常是最小且最快的,之後 L2, L3 每層會越來越大越來越慢
這時一定會好奇那為什麼要做這麼多層?!
因為 Memory 離 cpu 太遠了,通常都會有個 bus 在中間做溝通橋樑
所以相比之下 cache 還是比存取 memory 來的快。

PS. 在 ARM v7 架構下,最多可支援到 Level 7 喔!

Indexed & Tagged

要如何在 Cache 中找資料呢? 當然是使用 memory address 呀!
那 ... 是 virtual address 還是 physical address 啊?
嗚 ...

這問題就要了解到 VIVT, VIPT, 及 PIPT 了 ~
index 跟 tag,分別是兩個拿來判斷資料是屬於誰的資訊
兩者要同時相符合,才會說是 cache hit, 並回傳資料

所謂的 VIVT 指的是 Virtual Indexed Virtual Tagged
同理 VIPT = Virtual Indexed Physical Tagged,
PIPT = Physical Indexed Physical Tagged

當 Cache 為 VIVT 時,皆只使用 Virtual Address 去作存取
速度較快 (因為程式執行時,傳遞的本來就是 virtual address)
但是卻會常常需要作 invalidate 的動作。
由於每個 Process 都會有 4G 的 virtual address,
雖然對應到的 Physical Address 不同,但是 VIVT cache 只使用 virtual address
造成 context switch 時就一定得進行 clean+invalidate(flush) 的動作
以防止存取到錯誤的資料。

與 VIVT 相對的極端 PIPT
只使用 physical address 作存取,不用擔心資料取錯
但是得進行 physical address 轉換, 如果不巧發生 TLB miss …
這轉換的工作就會是個漫長的旅途了 哈

在 VIPT 的情況下,
由於多了 Physical Tag,就能讓資料在 cache 存在的時間拉長
所謂的 physical tag 指的是當 virtual address 進來後得進行一次轉換
同時 virtual, physical address 都 match 才會取得資料
缺點就是在 physical address 轉換出來之前,都無法找到正確的資料
不過卻也比 PIPT 來的好很多,因為當 virtual address 在 cache 中流竄的同時
也能在 TLB 當中流竄進行 physical address 轉換

根據排列組合,應該還有個 PIVT 的存在才對啊!
這東西 … 沒用處,所以基本上大家都不討論。
This fourth theoretical type of cache, physically indexed, virtually tagged (PIVT), is basically useless and is not discussed further. ※from Linux Journal

Aliasing Problem
當兩個 Virtual Address 指到同一個 Physical Address 時,
雖然都是同樣的資料,但 VIVT, VIPT 皆會保存兩次 (因為 index 不同)。
此時就會稱之為 cache-line aliasing problem

舉例來講,Kernel 中有 copy_from_user, copy_to_user 使用此兩個 API 時
Kernel 會使用 kernel space virtual address 來 map physical address
但此 physical address 一定也有 user space virtual address 對應
這時就會發生兩個不同的 virtual adress 卻對應到同樣的 physical address 的情形

為解決此問題,有人提出了 page coloring 的作法。(在此不贅述 Orz)

Write Through & Write Back
這是兩種不同的 cache type,差別在於
Write Through – 每次將資料寫回 cache 時,同時也寫到 main memory
Write Back – 只有當 Cache Line 要被 Flush 時,才寫回 main memory
在 write-back cache 中,cache, memory 的資料通常是不同步的。
所以可能會多使用 dirty bit 來標示說 memory 的資料已經是舊的。
當 cache 要將資料清除時,得負責把資料寫回 memory ~

Non-Cacheable

咦? Cache 不是加速用的嗎?
那為什麼會有 non-cacheable 的需求?

一般而言 Memory 的存取,能 cache 一定是比較有幫助的!
但是若今天是 I/O device 時,每次去跟裝置要資料時應該都是不同的值
若被 cache 住,cache hit 就拿不到裝置上最新的資料了 …
所以像這種每次都有可能拿到不同值的,原則上都不應 cache
如此才能確保資料的 Reliability ~

– Reference –
CPU Cache (Wikipedia)
Understanding Caching | Linux Journal

Advertisements