有一個有趣的問題: 假如 cache size 是 8KB, 而 virtual memory 的 page 是 4KB 會怎麼樣? 這個就是 cache alias的問題.
根據新版的 “See MIPS Run" 這本書的 10.3.4 Cache Aliases and Page Coloring, 名詞定義是這樣:
1. index range = the size of one “set" of cache. 舉例來說 4 KB 的 page 可以對應到 8KB 的 direct map, 或是 32KB 的 4-way set-associative cache.
2. page color = the value of those one or more virtual address bits that choose a page size chunk within the propriate page set.
3. cache aliases = two virtual pointers to the same physical data can produce an alias only if they have different page colors.
若是把 32KB 4-way associative cache memory 看作 4 塊 8KB 的 cache memory, 那麼每一塊都比 4KB page 大一倍, 一抓就有機會抓到和另外一個 way 重疊的內容.
解法: 只要 virtual address 彼此距離夠遠, 比方說在 4KB page 下間隔 64KB, 那麼每個 page 的 color 都會一樣.
另外有人說, 可以讓 virtual address 的 bit 12 (假設 page 是 4KB, 12 bis) 強制和 physical address 的 bit 12 一樣, 也就是說每 8KB 的第一個 4KB, 和第二個 4KB 在 physical address 上都沒有重疊. 由於每一個 way 不會抓到一樣的東西, 這就確保了兩個 way 之間的 cache 不會重複. 它聽起來等效於 page size 變成 8KB, 所以應該會沒問題.
先不管軟體實作上的困難, 這種 work around 的 hit rate 將會很低. 每次 hit 到奇數 page, 就要連前一個偶數 page 都抓進來. 那些資料通常已經是過去式了, 所以 cache 的效率應該挺差的.
——————————————————–
20090320 重新整理
cache alias 可能發生在 Linux 的 user mode 之間, 也可能發生在 user mode 與 kernel mode 之間.
單純在 user mode 的解法有很多種:
1. 只要 virtual address 彼此距離夠遠, 比方說在 4KB page 下間隔 64KB, 那麼每個 page 的 color 都會一樣均勻, 如小魚的第一個回覆一樣.
2. 根據小魚的說法: 奇數 8KB (i.e. 4(2n+1)KB) 和偶數 8KB (i.e. 4(2n)KB) 的 physical address 都對應到不同組的 virtual address. 而 memory cache 既然是根據 virtual address 所做的, 那麼就沒有機會 cache 到重複的 physical address.
有人說用這種說法: “可以讓 virtual address 的 bit 12 (假設 page 是 4KB, 12 bis) 強制和 physical address 的 bit 12 一樣, 也就是說每 8KB 的第一個 4KB, 和第二個 4KB 在 physical address 上都沒有重疊. 由於每一個 way 不會抓到一樣的東西, 這就確保了兩個 way 之間的 cache 不會重複. 它聽起來等效於 page size 變成 8KB, 所以應該會沒問題.
為了 hit 到 8KB 裡的一個 Linux 4KB page, 現在必須抓 8 KB 的 cache. 和原來的方式相比, 原來讀到 0x80001-000 的時候, 我們 cache 0x80001-000~0x80002-FFF, 是指望後面進到 cache 的 0x80002-000~0x80002-FFF 這個 page 等一下會用到. 根據新的方式, 就會變成 cache 0x80000-000~0x80001-FFF 這 8 KB. 所以還是會有一些差別, 如小魚第四篇回覆所說的: " 0×00410_000 和 0×00411_000 是無法同時對到 0×40400_000 的“.
本來我有個直覺, 覺得分了類之後, 對於大量連續資料, 又放在虛擬記憶體的連續位置時, 上面的做法可能會降低效率. 但想想也只是 cache 到不同 way 的 cache memory 去了, 應該是還好.
[後記]
1. Kernel space 和 user space 存取同一個 page 的話, 也會有 virtual alias 的問題.
2. 還是要感謝小魚啦! 哈!
Cash Chou's Blog 