cache結(jié)構(gòu)與工作原理
cache是ARM最難理解，也是最具有閃光點(diǎn)的地方之一，現(xiàn)在是解決他的時(shí)候了。
高速緩沖存儲(chǔ)器是存在于主存與CPU之間的一級(jí)存儲(chǔ)器， 由靜態(tài)存儲(chǔ)芯片（SRAM）組成，容量比較小但速度比主存高得多， 接近于CPU的速度。 Cache的功能是用來存放那些近期需要運(yùn)行的指令與數(shù)據(jù)。目的是提高CPU對(duì)存儲(chǔ)器的訪問速度。為此需要解決2個(gè)技術(shù)問題：一是主存地址與緩存地址的映象及轉(zhuǎn)換； 二是按一定原則對(duì)Cache的內(nèi)容進(jìn)行替換。
Cache是介于CPU與主內(nèi)存之間、或者主內(nèi)存與磁盤之間的高速緩沖器，其作用是解決系統(tǒng)中數(shù)據(jù)讀寫速度不匹配的問題。其中介于CPU與主內(nèi)存之間的緩沖器又稱為RAM Cache，而介于主內(nèi)存與磁盤驅(qū)動(dòng)器之間的緩沖器則稱之為Disk Cache，這里要討論的是前者，也就通常簡(jiǎn)稱的Cache。
cache結(jié)構(gòu)與工作原理首先，要想理解cache，先理解內(nèi)存。內(nèi)存的簡(jiǎn)單表示如下圖，內(nèi)存里面的內(nèi)容的查找是根據(jù)地址來進(jìn)行的，也就是說內(nèi)存包含兩點(diǎn)①地址②內(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ù)。圖中的一個(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)類似，也包含地址和內(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），用來標(biāo)記這個(gè)cache line是否保存著有效的數(shù)據(jù)）。一個(gè)tag和它對(duì)應(yīng)的數(shù)據(jù)組成的一行稱為一個(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)單起見，我們先選擇 直接映射的cache組成方式進(jìn)行下文的分析。
首先對(duì)于一段物理內(nèi)存（block），該物理內(nèi)存上的每個(gè)字節(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字段和該地址對(duì)應(yīng)的內(nèi)容放入對(duì)應(yīng)的cache line的tag字段和data字段，并把相應(yīng)的valid位置1。那么在之后進(jìn)行cache尋找的時(shí)候就可以根據(jù)cache line的tag字段來辨認(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)行地址劃分：地址的最高兩位為Tag字段；中間三位為index字段；最低兩位為Block Offset 字段；由于Block Offset是兩位，也就是一個(gè)block的大小是22=4個(gè)字節(jié)的數(shù)據(jù)，也就是一個(gè)cache line的data字段包含4個(gè)字節(jié)的數(shù)據(jù)；index為3位，說明cache共包含23=8個(gè)組（對(duì)于直接映射的cache，也稱為8個(gè)行）；很明顯，cache的一個(gè)行中只能存儲(chǔ)1 塊（Block ）=4字節(jié)的數(shù)據(jù)，但是按照?qǐng)D5的映射方式，會(huì)有2^（tag位數(shù)） = 2^2 = 4塊的數(shù)映射到同一個(gè)行，此時(shí)通過Tag字段的比較來辨別是不是我們要取數(shù)據(jù)的地址，如果不是的話，也就是發(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ā)出的訪存請(qǐng)求是訪問Block 0 的話，也就是發(fā)生了缺失。此時(shí)進(jìn)一步定量分析的話，共有4個(gè)數(shù)據(jù)塊競(jìng)爭(zhēng)使用cache 第0行的位置，也就是說cache的命中率為25%。
上面的過程總結(jié)起來就是：物理內(nèi)存的索引字段（Index）選擇cache 的行，通過對(duì)比物理內(nèi)存和cache line的Tag來判斷是否命中。塊偏移字段（Block Offset）可以從cache line的數(shù)據(jù)塊中選擇期望數(shù)據(jù)。注意在這個(gè)過程中cache的index是不占空間的，它就類似于物理內(nèi)存的地址，對(duì)于物理內(nèi)存來說是通過地址去尋找數(shù)據(jù)，對(duì)于cache來說，是通過index來找到對(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的分析與之類似。如果是組相連的cache，每個(gè)組（set）里面包含多個(gè)行（line），通過內(nèi)存地址的index字段來尋址組，確定組之后再根據(jù)tag來確定是否命中；對(duì)于全相連的cache，就不需要index字段了，因?yàn)槿噙B的cache相當(dāng)于只有一個(gè)組的組相連cache。這是只需要根據(jù)要尋址的地址的tag來逐一與cache中的tag字段比較，如果有與之匹配的cache line，也就是cache hit了，如果遍歷整個(gè)cache，也沒有找到匹配的cache line，那就是cache miss了。
注：為了敘述的簡(jiǎn)單性，省略了內(nèi)存地址通過TLB的的虛實(shí)轉(zhuǎn)換部分，由［1］可知，內(nèi)存地址的Tag部分其實(shí)是需要先經(jīng)過TLB的轉(zhuǎn)化才能夠去和cache line的tag部分去進(jìn)行匹配的。
Q:文檔中對(duì)于標(biāo)題的格式要求是什么？
A:使用 number signs (#) 表示標(biāo)題。
Q:列表項(xiàng)如何表示？
A:列表項(xiàng)以 dashes (-) 開頭。
Q:如何強(qiáng)調(diào)文本？
A:用 asterisks (*) 包裹強(qiáng)調(diào)的文本。
Q:代碼或命令怎么表示？
A:用 backticks (`) 包圍代碼或命令。
Q:引用文本如何表示？
A:使用 greater than signs (>)。
Q:鏈接怎么表示？
A:用 square brackets [] 包裹文本，后面跟 URL 在 parentheses ()。
Q:圖片如何表示？
A:用 square brackets [] 表示圖片的 alt 文本，后面跟圖片 URL 在 parentheses ()。