Cache基礎(chǔ)知識(shí)介紹

1、什么是cache Cache又叫高速緩沖存儲(chǔ)器，位于CPU與內(nèi)存之間，是一種特殊的存儲(chǔ)器子系統(tǒng)。 目前比較常見的是兩極cache結(jié)構(gòu)，即cache系統(tǒng)由一級(jí)高速緩存L1 cache和二級(jí)高速緩存L2 cache組成，L1 cache通常又分為數(shù)據(jù)cache（I-Cache）和指令cache（D-Cache），它們分別用來存放數(shù)據(jù)和執(zhí)行這些數(shù)據(jù)的指令。 兩極cache相比較而言，L1 cache的容量小，但數(shù)據(jù)存取速度較快，L2 cache的容量大，但數(shù)據(jù)存取速度較慢。部分系統(tǒng)中也存在三級(jí)cache的結(jié)構(gòu)。Cache的作用是什么 Cache的作用就是為了提高CPU對(duì)存儲(chǔ)器的訪問速度。 電腦的內(nèi)存

2、是以系統(tǒng)總線的時(shí)鐘頻率工作的，這個(gè)頻率通常也就是CPU的外頻。但是，CPU的工作頻率(主頻)是外頻與倍頻因子的乘積。這樣一來，內(nèi)存的工作頻率就遠(yuǎn)低于CPU的工作頻率了。這樣造成的直接結(jié)果是：CPU在執(zhí)行完一條指令后，常常需要“等待”一些時(shí)間才能再次訪問內(nèi)存，極大降了CPU工作效率。在這樣一種情況下，cache就應(yīng)運(yùn)而生了。 指令地址 96loop: ADD r2, r1, r1 100 SUBI r3, r3, #1 104 BNEZ r3, loop 108 112典型的內(nèi)存訪問模式 Cache的工作原理 CPU運(yùn)行程序是一條指令一條指令地執(zhí)行的，而且指令地址往往是連續(xù)的，意思就是說CPU在

3、訪問內(nèi)存時(shí)，在較短的一段時(shí)間內(nèi)往往集中于某個(gè)局部，這時(shí)候可能會(huì)碰到一些需要反復(fù)調(diào)用的子程序。系統(tǒng)在工作時(shí)，把這些活躍的子程序存入比主存快得多的cache 中。 CPU在訪問內(nèi)存時(shí)，首先判斷所要訪問的內(nèi)容是否在cache中，如果在，則稱為命中（hit），此時(shí)CPU直接從cache中調(diào)用該內(nèi)容；否則稱為未命中（miss）， CPU會(huì)通過cache對(duì)主存中的相應(yīng)內(nèi)容進(jìn)行操作。Cache的地址映射方式Cache與主存之間可以采取的地址映射方式有以下三種： 全相聯(lián)映射方式 直接相聯(lián)映射方式 組組相聯(lián)映射方式 全相聯(lián)方式全相聯(lián)方式 地址映射規(guī)則：主存的任意一塊可以映射到cache中的任意一塊 (1) 主存

4、與cache分成相同大小的數(shù)據(jù)塊。 (2) 主存的某一數(shù)據(jù)塊可以裝入cache的任意一塊空間中。 優(yōu)點(diǎn)：命中率比較高，cache存儲(chǔ)空間利用率高。 缺點(diǎn)：訪問相關(guān)存儲(chǔ)器時(shí)，每次都要與全部內(nèi)容比較，速度低，成本高，因而應(yīng)用少。 直接相聯(lián)方式直接相聯(lián)方式 地址映射規(guī)則： 主存儲(chǔ)器中一塊只能映射到cache的一個(gè)特定的塊中。 (1) 主存與cache分成相同大小的數(shù)據(jù)塊。 (2) 主存容量應(yīng)是cache容量的整數(shù)倍，將主存空間按cache的容量分成區(qū)，主存中每一區(qū)的塊數(shù)與cache的總塊數(shù)相等。 (3) 主存中某區(qū)的一塊存入cache時(shí)只能存入緩存中塊號(hào)相同的位置。 優(yōu)點(diǎn)：地址映射方式簡單，數(shù)據(jù)訪問

5、時(shí)，只需檢查區(qū)號(hào)是否相等即可，因而可以得到比較快的訪問速度，硬件設(shè)備簡單。 缺點(diǎn)：替換操作頻繁，命中率比較低。 組相聯(lián)映射方式組相聯(lián)映射方式 地址映射規(guī)則： (1) 主存和cache按同樣大小劃分成塊。 (2) 主存和cache按同樣大小劃分成組。 (3) 主存容量是cache容量的整數(shù)倍，將主存空間按cache區(qū)的大小分成區(qū)，主存中每一區(qū)的組數(shù)與cache的組數(shù)相同。 (4) 當(dāng)主存的數(shù)據(jù)調(diào)入cache時(shí)，主存與cache的組號(hào)應(yīng)相等，也就是各區(qū)中的某一塊只能存入cache的同組號(hào)的空間內(nèi)，但組內(nèi)各塊地址之間則可以任意存放， 即從主存的組到cache的組之間采用直接映射方式；在兩個(gè)對(duì)應(yīng)的組內(nèi)

6、部采用全相聯(lián)映射方式。 優(yōu)點(diǎn)：塊的沖突概率比較低，塊的利用率大幅度提高，塊失效率明顯降低。缺點(diǎn)：實(shí)現(xiàn)難度和造價(jià)要比直接映射方式高。 塊:塊是cache與主存的傳輸單位。 路（way）: 路是組相聯(lián)映射方式的cache結(jié)構(gòu)中的基本存儲(chǔ)單位，每一路存儲(chǔ)一個(gè)塊的數(shù)據(jù)。 組（entry）:組是組相聯(lián)映射方式的cache對(duì)塊進(jìn)行管理的單位。 區(qū) （tag） :塊的地址對(duì)應(yīng)的主存儲(chǔ)器中的區(qū)。 塊內(nèi)偏移地址（offset）: 用來標(biāo)示塊內(nèi)一個(gè)字節(jié)的地址。 組相聯(lián)映射方式下主存儲(chǔ)器的地址空間由，區(qū)，組和塊內(nèi)偏移地址組成。 組相聯(lián)映射方式下cache的內(nèi)部結(jié)構(gòu)。Cache的替換算法Cache可以采用的替換算法主

7、要有以下幾種： 先入后出(FILO)算法 隨機(jī)替換(RAND)算法 先入先出(FIFO)算法 近期最少使用(LRU)算法 隨機(jī)(RAND)法是隨機(jī)地確定替換的存儲(chǔ)塊。設(shè)置一個(gè)隨機(jī)數(shù)產(chǎn)生器，依據(jù)所產(chǎn)生的隨機(jī)數(shù)，確定替換塊。這種方法簡單、易于實(shí)現(xiàn)，但命中率比較低。 先進(jìn)先出(FIFO)法是選擇那個(gè)最先調(diào)入的那個(gè)塊進(jìn)行替換。當(dāng)最先調(diào)入并被多次命中的塊，很可能被優(yōu)先替換，因而不符合局部性規(guī)律。這種方法的命中率比隨機(jī)法好些，但還不滿足要求。 近期最少使用(LRU)法是依據(jù)各塊使用的情況，總是選擇那個(gè)最近最少使用的塊被替換。這種方法比較好地反映了程序局部性規(guī)律，命中率最高。如何提高cache的性能 提高c

8、ache的性能也就是要降低主存的平均存取時(shí)間 主存平均存取時(shí)間=命中時(shí)間+未命中率*未命中懲罰 提高cache的性能有以下三種方法：減少命中時(shí)間，減少未命中率，減少未命中懲罰。影響命中率的硬件因素主要有以下四點(diǎn)： Cache的容量。 Cache與主存儲(chǔ)器交換信息的單位量（cache line size）。 Cache的組織方式 Cache的替換算法代碼段Afor(i=0;i1024;i+) for(j=0;j4;j+) sum += xij代碼段Bfor(j=0;j4;j+) for(i=0;i1024;i+) sum += xij 通過優(yōu)化代碼提高cache命中率 對(duì)數(shù)組int x10244

9、進(jìn)行求和代碼段A：對(duì)于數(shù)組元素xi0（i=01024）的訪問是miss的，但對(duì)于xi1， xi2， xi3的訪問是hit的，因此miss的總次數(shù)為1024次。代碼段B：對(duì)于數(shù)組元素xi0， xi1， xi2， xi3 （i=01024）的訪問都是miss的，他們被xi+40 ， xi+41， xi+42，xi+43所替換，因此miss的總次數(shù)為4096次。 當(dāng)需要對(duì)大量數(shù)據(jù)訪問的時(shí)候，一定要注意對(duì)內(nèi)存的訪問要盡量是連續(xù)而且循環(huán)內(nèi)層的訪問接近c(diǎn)ache的塊大小，以提高cache的命中率，從而提高程序的運(yùn)行效率。 Cache的一致性問題 在采用cache的系統(tǒng)中，同樣一個(gè)數(shù)據(jù)可能既存在于cache

10、中，也存在于主存中，兩者數(shù)據(jù)相同則具有一致性，數(shù)據(jù)不相同就叫做不一致。 Cache主要有兩種寫策略寫直達(dá)法（write through）和寫回法（write back） 寫直達(dá)法（write through）方法：在對(duì)cache進(jìn)行寫操作的同時(shí)，也將內(nèi)容寫到主存中。優(yōu)點(diǎn)：可靠性較高，操作過程比較簡單。缺點(diǎn)：寫操作速度得不到改善，與寫主存的速度相同。 寫回法（write back）方法：在CPU執(zhí)行寫操作時(shí)，只寫入cache，不寫入主存。優(yōu)點(diǎn)：速度較高。缺點(diǎn)：可靠性較差，控制操作比較復(fù)雜。 對(duì)于多個(gè)主設(shè)備的共享存儲(chǔ)總線系統(tǒng)，如帶有DMA的系統(tǒng)，或者多處理器系統(tǒng)，由于其他的主設(shè)備也可以改變主存的內(nèi)容，而這種改變是cache無法得知的，因此必須對(duì)cache的一致性問題進(jìn)行處理。 可以將主存中的一塊地址空間設(shè)置為非cache訪問，CPU對(duì)這部分地址