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

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

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

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

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

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

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

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

圖2 cache的三種組成方式

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

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

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

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

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

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

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

圖5 cache的查找過(guò)程

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

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

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

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

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

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