系統加速利器Hardware Cache（一）——三種類型的Cache

Hardware cache的目的

Hardware Cache的是為系統加速而生的，這個是衆所周知的事情。不過為了本文内容的完整性，我在此還是先将hardware cache的功能講一下，不過我會盡量簡短一點。

cpu通路hardware cache的速度要遠高于通路主記憶體的速度，為了加快系統運作速度，會将主記憶體的部分資料放在hardware cache中，這樣cpu就不必每次都通路主記憶體，如果要通路的資料在cache中命中，則直接從cache中讀資料或者直接修改cache中的資料即可，進而加快了系統運作速度。至于由于hardware cache的引入，出現的多master環境下記憶體不一緻問題，我們在後面的章節讨論。

這裡有兩個問題要特别注意：

第一，hardware cache由于比較昂貴，是以一般容量較小，而主記憶體一般容量很大，是以主記憶體中的資料不可能全部放在hardware cache中，是以cache中的内容在必要的時候會同步到記憶體，以便能裝入新的内容。

第二，hardware的操作機關是cache line，cache line的長度由晶片設計而定，本文我們以32B cache line分析。

三種類型的cache

我們以32K的cache容量，32B的cache line size來分析。32K的cache容量，每個cache line是32B，是以總共有1024個cache line。

直接映射的cache

直接映射的cache方案中，每個cache line所對應的實體記憶體都是固定的，映射關系如下：

主記憶體位址	Cache Line
0 - 31
32 - 63	1
64 - 95	2
96 - 127	3
……	……
32K-32 - 32K-1	1023
32k+0 - 32k+31
32k+32 - 32k+63	1
32k+64 - 32k+95	2
……	……

即主記憶體每連續32K分成一組，分别映射到cache line0-1024。這樣主記憶體位址0-31和32k+0 - 32k+31都映射到cache line 0。

直接映射的cache line格式如下：

Tag（addr 15 - 31/63）+ Data(32B)
           

到cache這邊的位址譯碼格式如下：

addr 15 - 31/63	addr 5 - 14	addr 0 - 4
tag	cache line 索引	在標明cache line内尋址

cache這邊使用實體位址還是虛拟位址依據硬體設計而定，我們在此不加以讨論，統一稱位址。

Cpu通路操作處理過程如下：

1. 根據位址的 bit5-14，索引到某個cache line。
2. 将位址的bit15-31/63與cache line的tag比較，如果一緻，則cache命中，否則cache沒有命中。
3. 如果cache命中，則根據位址的bit0-4在cache line内找到要通路的資料。
4. 如果cache沒有命中，則通路主記憶體，同時可以選擇将主記憶體中的資料按cache line對齊載入到對應的cache line中。

直接映射cache的好處是查找速度快，直接解析位址并索引就可以了。同時直接映射的cache line也有比較緻命的問題，因為每個cache line映射到比較多的固定位址，比如cache line 0對應實體位址0-31以及32k+0 - 32k+31，如果本次通路位址0-31，則位址0-31的資料緩存到cache line0，下次通路位址32k+0 - 32k+31，則需要從主記憶體将資料載入cache line0，下次再通路位址0-31，又需要從主記憶體載入資料到cache line0，這種情況下，cache形同虛設，因為每次都會通路主記憶體。

全相聯cache

全相聯的cache，每一個主記憶體位址可以緩存到任意一個cache line。

cache line格式如下：

Tag（addr 5 - 31/63）+ Data(32B)
           

到cache這邊的位址譯碼格式如下：

addr 5 - 31/63	addr 0 - 4
tag	在標明cache line内尋址

這裡沒有cache line索引大概念，依次比較位址的tag與cache line的tag，如果tag一緻，則表明cache命中。

全相聯的cache也很非常明顯的确定，那就是查找速度慢，因為要依次比較cache line，最壞的情況下，需要比較1024次才能命中。

組相聯cache

組相連cache結合了直接映射cache和全相聯cache的特點，我們以8路組相連為例做說明。

每8個cache line為一組，1024個cache line共分成128組。每個組采用直接映射方案，而組内的8個cache line則使用全相聯方案。映射方案如下：

主記憶體位址	Cache Line
0 - 31	可以緩存到第一組cache lines中的任意一條cache line中
32 - 63	可以緩存到第二組cache lines中的任意一條cache line中
64 - 95	可以緩存到第三組cache lines中的任意一條cache line中
……	……
4k-32 - 4k-1	可以緩存到第一組cache lines中的任意一條cache line中
4k-4k+31	可以緩存到第二組cache lines中的任意一條cache line中
……	……

cache line格式如下：

Tag（addr 12 - 31/63）+ Data(32B)
           

到cache這邊的位址譯碼格式如下：

addr 12 - 31/63	addr 5 - 11	addr 0 - 4
tag	組索引	在標明cache line内尋址

Cpu通路處理過程如下：

1. 根據位址bit5-11索引組
2. 根據位址tag bit12-31/63與組内cache line的tag依次比較，如果有一緻的，則命中。
3. 如果cache line命中，則根據位址bit0-4在cache line内找到要通路的資料。
4. 如果cache沒有命中，則通路主記憶體，同時可以選擇将主記憶體中的資料按cache line對齊載入組内任意一條空閑cache line中，如果沒有空閑的cache line，則驅逐一個cache line。

組相聯cache是直接映射和全相聯折中的方案。跟直接映射cache相比，它的查詢速度不夠，但是cache沖突的機率大大降低；跟全相聯cache相比，它的cache沖突的機率大一點，但是它的查詢速度比較快。