cache結(jié)構(gòu)與工作原理

cache是ARM最難理解，也是最具有閃光點的地方之一，現(xiàn)在是解決他的時候了。

高速緩沖存儲器是存在于主存與CPU之間的一級存儲器， 由靜態(tài)存儲芯片（SRAM）組成，容量比較小但速度比主存高得多， 接近于CPU的速度。 Cache的功能是用來存放那些近期需要運行的指令與數(shù)據(jù)。目的是提高CPU對存儲器的訪問速度。為此需要解決2個技術(shù)問題：一是主存地址與緩存地址的映象及轉(zhuǎn)換； 二是按一定原則對Cache的內(nèi)容進行替換。

Cache是介于CPU與主內(nèi)存之間、或者主內(nèi)存與磁盤之間的高速緩沖器，其作用是解決系統(tǒng)中數(shù)據(jù)讀寫速度不匹配的問題。其中介于CPU與主內(nèi)存之間的緩沖器又稱為RAM Cache，而介于主內(nèi)存與磁盤驅(qū)動器之間的緩沖器則稱之為Disk Cache，這里要討論的是前者，也就通常簡稱的Cache。

cache結(jié)構(gòu)與工作原理

首先，要想理解cache，先理解內(nèi)存。內(nèi)存的簡單表示如下圖，內(nèi)存里面的內(nèi)容的查找是根據(jù)地址來進行的，也就是說內(nèi)存包含兩點①地址②內(nèi)存的內(nèi)容（存的數(shù)據(jù)），根據(jù)地址來找數(shù)據(jù)。

圖1 內(nèi)存的結(jié)構(gòu)

上圖的0000~0008是地址，A~I是存的數(shù)據(jù)，cpu根據(jù)地址去尋找數(shù)據(jù)。圖中的一個字母代表一個字節(jié)的數(shù)據(jù)。

我們都清楚，cache中的數(shù)據(jù)就是物理內(nèi)存中的數(shù)據(jù)的子集，那么對于物理內(nèi)存的一個數(shù)據(jù)，根據(jù)cache中可以放置這個數(shù)據(jù)位置的多少，可以分為三種：①如果cache中只有一個位置可以容納這個數(shù)據(jù)，則為直接映射的cache；②如果cache中有多個地方可以放置這個數(shù)據(jù)，它就是組相聯(lián)的cache；③如果cache中的任何地方都可以放置這個數(shù)據(jù)，那么它就是全相連的cache；如下圖2所示：

圖2 cache的三種組成方式

更詳細(xì)的講，cache的結(jié)構(gòu)其實和內(nèi)存的結(jié)構(gòu)類似，也包含地址和內(nèi)容，只是cache的內(nèi)容除了存的數(shù)據(jù)（data）之外，還包含存的數(shù)據(jù)的物理內(nèi)存的地址信息（tag），因為CPU發(fā)出的尋址信息都是針對物理內(nèi)存發(fā)出的，所以cache中除了要保存數(shù)據(jù)信息之外，還要保存數(shù)據(jù)對應(yīng)的地址，這樣才能在cache中根據(jù)物理內(nèi)存的地址信息查找物理內(nèi)存中對應(yīng)的數(shù)據(jù)。（當(dāng)然為了加快尋找速度，cache中一般還包含一個有效位（valid），用來標(biāo)記這個cache line是否保存著有效的數(shù)據(jù)）。一個tag和它對應(yīng)的數(shù)據(jù)組成的一行稱為一個cache line。如下圖所示，下表中的一行就是一個cache line。

圖3 cache的基本結(jié)構(gòu)

具體的Data、Valid、Tag各有多大，在介紹了內(nèi)存的地址劃分之后再在下文中講。

知道了cache的結(jié)構(gòu)之后，如何在cache中去尋找對應(yīng)的數(shù)據(jù)呢？簡單起見，我們先選擇 直接映射的cache組成方式進行下文的分析。

首先對于一段物理內(nèi)存（block），該物理內(nèi)存上的每個字節(jié)的地址劃分為以下幾段：［3］

圖4 處理器物理內(nèi)存地址的劃分

這樣的話物理內(nèi)存中的數(shù)據(jù)到cache的映射關(guān)系如下圖5所示：

圖5 cache的查找過程

上圖的映射原則就是：根據(jù)物理地址的中間三位（index字段）來定位當(dāng)前數(shù)據(jù)應(yīng)該在cache的哪一行，把物理地址的tag字段和該地址對應(yīng)的內(nèi)容放入對應(yīng)的cache line的tag字段和data字段，并把相應(yīng)的valid位置1。那么在之后進行cache尋找的時候就可以根據(jù)cache line的tag字段來辨認(rèn)當(dāng)前l(fā)ine中的數(shù)據(jù)是數(shù)據(jù)哪個block的。

上圖5中的地址00 000 00~11 111 11按照圖4的原則進行地址劃分：地址的最高兩位為Tag字段；中間三位為index字段；最低兩位為Block Offset 字段；由于Block Offset是兩位，也就是一個block的大小是22=4個字節(jié)的數(shù)據(jù)，也就是一個cache line的data字段包含4個字節(jié)的數(shù)據(jù)；index為3位，說明cache共包含23=8個組（對于直接映射的cache，也稱為8個行）；很明顯，cache的一個行中只能存儲1 塊（Block ）=4字節(jié)的數(shù)據(jù)，但是按照圖5的映射方式，會有2^（tag位數(shù)） = 2^2 = 4塊的數(shù)映射到同一個行，此時通過Tag字段的比較來辨別是不是我們要取數(shù)據(jù)的地址，如果不是的話，也就是發(fā)生了cache的缺失。如圖5的Block 0和Block 1的index字段都是000，按照上面的理論它們都應(yīng)該映射到第 000=0行（這兒的行也就是組，因為圖5是直接映射的cache），但是現(xiàn)在第0行的內(nèi)容是K、L、M、N，也就是Block 1的內(nèi)容，為什么呢？仔細(xì)看該cache line的tag=01，映射到第0行的塊只有Block 1的tag字段=01，所以可以得知此時該cache line中存儲的數(shù)據(jù)是Block 1的數(shù)據(jù)，此時如果CPU發(fā)出的訪存請求是訪問Block 0 的話，也就是發(fā)生了缺失。此時進一步定量分析的話，共有4個數(shù)據(jù)塊競爭使用cache 第0行的位置，也就是說cache的命中率為25%。

上面的過程總結(jié)起來就是：物理內(nèi)存的索引字段（Index）選擇cache 的行，通過對比物理內(nèi)存和cache line的Tag來判斷是否命中。塊偏移字段（Block Offset）可以從cache line的數(shù)據(jù)塊中選擇期望數(shù)據(jù)。注意在這個過程中cache的index是不占空間的，它就類似于物理內(nèi)存的地址，對于物理內(nèi)存來說是通過地址去尋找數(shù)據(jù)，對于cache來說，是通過index來找到對應(yīng)的cache line，或者更通俗的講就是：cache line的地址對應(yīng)的就是物理內(nèi)存的index字段。

此時該cache的容量計算如下：每一個cache line的數(shù)據(jù)字段占4個字節(jié)，共23=8行，所以數(shù)據(jù)占據(jù)4×8=32個字節(jié)，一個cache line中tag字段和valid位占2+1=3bit，整個cache的tag+valid=3bit×8行=24bit=3Byte，通常情況下我們都是一cache中數(shù)據(jù)部分占的空間表示cache的容量，也就是32字節(jié)，但是實際上，它還額外多占用了3字節(jié)的存儲空間［4］。

圖5的分析是針對直接映射的cache進行的，對于組相聯(lián)或者全相連的cache的分析與之類似。如果是組相連的cache，每個組（set）里面包含多個行（line），通過內(nèi)存地址的index字段來尋址組，確定組之后再根據(jù)tag來確定是否命中；對于全相連的cache，就不需要index字段了，因為全相連的cache相當(dāng)于只有一個組的組相連cache。這是只需要根據(jù)要尋址的地址的tag來逐一與cache中的tag字段比較，如果有與之匹配的cache line，也就是cache hit了，如果遍歷整個cache，也沒有找到匹配的cache line，那就是cache miss了。

注：為了敘述的簡單性，省略了內(nèi)存地址通過TLB的的虛實轉(zhuǎn)換部分，由［1］可知，內(nèi)存地址的Tag部分其實是需要先經(jīng)過TLB的轉(zhuǎn)化才能夠去和cache line的tag部分去進行匹配的。