高速緩沖存儲(chǔ)器基礎(chǔ)知識(shí)詳細(xì)介紹

　　高速緩沖存儲(chǔ)器（Cache）其原始意義是指存取速度比一般隨機(jī)存取記憶體（RAM）來得快的一種RAM，一般而言它不像系統(tǒng)主記憶體那樣使用DRAM技術(shù)，而使用昂貴但較快速的SRAM技術(shù)，也有快取記憶體的名稱。

　　高速緩沖存儲(chǔ)器是存在于主存與CPU之間的一級(jí)存儲(chǔ)器， 由靜態(tài)存儲(chǔ)芯片（SRAM）組成，容量比較小但速度比主存高得多， 接近于CPU的速度。在計(jì)算機(jī)存儲(chǔ)系統(tǒng)的層次結(jié)構(gòu)中，是介于中央處理器和主存儲(chǔ)器之間的高速小容量存儲(chǔ)器。它和主存儲(chǔ)器一起構(gòu)成一級(jí)的存儲(chǔ)器。高速緩沖存儲(chǔ)器和主存儲(chǔ)器之間信息的調(diào)度和傳送是由硬件自動(dòng)進(jìn)行的。

　　高速緩沖存儲(chǔ)器最重要的技術(shù)指標(biāo)是它的命中率。

　　高速緩沖存儲(chǔ)器是存在于主存與CPU之間的一級(jí)存儲(chǔ)器， 由靜態(tài)存儲(chǔ)芯片（SRAM）組成，容量比較小但速度比主存高得多， 接近于CPU的速度。

　　高速緩沖存儲(chǔ)器基礎(chǔ)知識(shí)

　　基于緩存的存儲(chǔ)器層次結(jié)構(gòu)

　　基于緩存的存儲(chǔ)器層次結(jié)構(gòu)行之有效，是因?yàn)檩^慢的存儲(chǔ)設(shè)備比較快的存儲(chǔ)設(shè)備更便宜，還因?yàn)槌绦蛲故揪植啃裕?/p>

　　時(shí)間局部性：被引用過一次的存儲(chǔ)器的位置很可能在不遠(yuǎn)的將來被再次引用。

　　空間局部性：如果一個(gè)存儲(chǔ)器位置被引用了一次，那么程序很可能在不遠(yuǎn)的將來引用附近的一個(gè)存儲(chǔ)器位置。

　　通用高速緩存存儲(chǔ)器結(jié)構(gòu)

　　一個(gè)通用的高速緩存存儲(chǔ)器會(huì)有S = 2 ^ s個(gè)set（組）

　　每個(gè)set含有E個(gè)line（既通常所說的cache line）

　　每個(gè)line又包含1位vaild bit、 t位tag、B = 2 ^ b bytes cache block（真正存儲(chǔ)數(shù)據(jù)的地方）。

　　通常我們說的cache line 64位 32位，實(shí)際上是說的cache line中cache block是64位32位。

　　假設(shè)我們的存儲(chǔ)器地址有m位，共M = 2^m個(gè)不同的地址。我們看一下各個(gè)變量之間的關(guān)系。

　　cache緩存數(shù)據(jù)的大小C = （sizeof set * number of set） = （size of block * lines a set） * number of set = B * E * S

　　內(nèi)存大小2^m Cache line大小2^b 內(nèi)存的cache line個(gè)數(shù)2^（m-b）

　　2^（m-b）個(gè)cache line分到2^s個(gè)set里， 每個(gè)set會(huì)有2^（m - b –s）個(gè)cache line，這個(gè)數(shù)字不是E，是指會(huì)有2^（m – b –s）個(gè)cache line落到這個(gè)set 里面，那么就需要有m-b-s位tag，標(biāo)記出當(dāng)前是哪個(gè)cache line落到這個(gè)set里面了。也就是說t = m - b –s。

　　如上圖所示，m位地址的內(nèi)存，需要s位做索引，選set，t位做tag，選cache line，然后b 位做偏移取具體地址的內(nèi)存。

　　高速緩存的映射

　　高速緩存確定一個(gè)請(qǐng)求是否命中，然后抽取出被請(qǐng)求的字的過程，分為三步1）組選擇2）行匹配3）字抽取。

　　直接映射

　　直接映射每個(gè)組只有一行E=1

　　選組

　　地址中取s bits選組

　　選行

　　地址中取t bits與cache line中t bits tag匹配，匹配則命中，不匹配則cache miss

　　字抽取

　　地址中的b bits就是cache line中偏移，在命中的cache line中的取字。

　　直接映射不命中時(shí)，不需要什么策略，直接把索引的組中的cache line替換掉即可。

　　組相連映射

　　組相連映射中，一個(gè)組包括多個(gè)cache line，目前常見的有四路組相連映射，16路組相連映射，即一個(gè)set中有4個(gè)或16個(gè)cache line。對(duì)比直接映射，set 個(gè)數(shù)要比直接映射的少。因此s會(huì)小，相應(yīng)的落到每個(gè)set中的cache line會(huì)多，因此t會(huì)大。

　　選組

　　組相連映射的組選擇與直接映射一致。

　　選行

　　cache line的選擇時(shí)，因?yàn)橐粋€(gè)set中有多個(gè)cache line，因此需要搜索set中的每個(gè)cache line的tag，對(duì)比檢查是否命中。

　　字抽取

　　與直接映射一致

　　組相連映射對(duì)于一個(gè)index就會(huì)有多個(gè)行與之相對(duì)應(yīng)，比較每行的tag是否與想要的地址相符合，這樣就會(huì)大大增加命中的幾率，避免了一小段程序中頻繁cache失效的問題。

　　組相連映射不命中時(shí)，由于索引到的組中會(huì)有多個(gè)cache line，因此會(huì)有多種算法選擇到底替換哪個(gè)cache line。

　　全相連映射

　　全相連映射就是組相連映射只有一個(gè)組的情況。

　　選組

　　全相連映射組選擇很簡單，只有一個(gè)組，不需要組索引，s = 0，地址只被劃分為一個(gè)標(biāo)記tag，和一個(gè)偏移。

　　選行

　　全相連映射cache line選擇時(shí)，需要多緩存中的所有cache line進(jìn)行搜索對(duì)比。

　　字抽取

　　與之前一致

　　全相連映射需要大量的搜索cache line進(jìn)行對(duì)比，導(dǎo)致構(gòu)造一個(gè)又大又快的全相連高速緩存很困難，而且很昂貴。因此全相連緩存只適合做小的高速緩存，比如TLB。

　　Core i7的高速緩存特性

　　以上內(nèi)容來自《深入理解計(jì)算機(jī)系統(tǒng)》6.4

　　以下內(nèi)容來自互聯(lián)網(wǎng)

　　幾種cache方式

　　Virtual index virtual tagged

　　邏輯cache，Virtual index virtual tagged是純粹用虛擬地址來尋址，邏輯地址索引邏輯地址tag，這種方式帶來了很多的問題，每一行數(shù)據(jù)在原有tag的基礎(chǔ)上都要將進(jìn)程標(biāo)識(shí)加上以區(qū)分多個(gè)進(jìn)程之間的相同地址，而在 處理共享內(nèi)存時(shí)也比較麻煩，共享內(nèi)存在不同的進(jìn)程中的虛擬地址不相同，如何同步是個(gè)問題。

　　Physical index physical tagged

　　物理cache，Physical index physical tagged，物理地址索引和物理地址tag，是一種最容易理解的操作方式，cache針對(duì)物理地址進(jìn)行操作，簡單粗暴，而且不會(huì)有歧義。但是這種方式的缺陷也很明顯，在多進(jìn)程操作系統(tǒng) 中，每個(gè)進(jìn)程擁有自己獨(dú)立的地址空間，指令和代碼都是以虛擬地址的方式存在，cpu發(fā)出的memory access的指令都是以虛擬地址的方式發(fā)出，這樣的話，對(duì)于每一個(gè)memory access的操作，都要先等待MMU將虛擬地址翻譯為物理地址，這是一種串行的方式，效率較低。

　　virtual index physical tagged

　　現(xiàn)在比較多的是采用virtual index physical tagged的方式，virtual index的含義是當(dāng)cpu發(fā)出一個(gè)地址請(qǐng)求之后，低位地址去和cache中的index匹配， physical tagged是指虛擬地址的高位地址去和mmu中的頁表匹配以拿到物理地址（index和取物理地址這兩個(gè)過程是并行的），然后用從mmu中取到的物理地 址作為tag（或者tag的一部分）去和cache line的tag位匹配，這樣既保證了同一地址在cache中的唯一性（有個(gè)例外，cache alias）又能將mmu和cache并行工作，提高了效率。

　　這種方式帶來的唯一問題就是cache alias，即一個(gè)物理地址緩存到兩個(gè)cache line中。當(dāng)進(jìn)程間通過共享內(nèi)存方式通信，或者一個(gè)進(jìn)程通過mmap的方式內(nèi)核與應(yīng)用層共享內(nèi)存，就會(huì)出現(xiàn)同同一塊物理內(nèi)存，以多個(gè)虛擬地址訪問的情況。就容易導(dǎo)致一塊物理內(nèi)存緩存到兩個(gè)cache line中。

　　由于共享內(nèi)存是頁對(duì)其的，因此多個(gè)進(jìn)程空間的共享內(nèi)存，或者內(nèi)核態(tài)用戶態(tài)的共享內(nèi)存，其物理地址不同，但其頁偏移是相同的。

　　假如頁大小為P = 2^p 字節(jié)，cache line為 C = 2^c 字節(jié)，那么共享內(nèi)存的不同虛擬地址其低p位是一致的，假如地址0 -》 c位用于block offset，c -》 p 位用于set index，那么就可以避免cache alias的問題。

　　但如果set index 位數(shù) 》 p -c ，那肯定會(huì)出現(xiàn)cache alias的問題，因?yàn)橥粔K物理內(nèi)存，不同的虛擬地址，其set index不同。

　　針對(duì)于cache alias問題，目前的方案是由操作系統(tǒng)來保證，對(duì)于同一物理地址在不同進(jìn)程空間的虛擬地址，要保證他們index相同，落在同一個(gè)set，就需要保證他們虛擬地址的差值是cache大小的整數(shù)倍。同時(shí)已經(jīng)有些cpu廠商在開發(fā)監(jiān)視模塊，試圖在硬件層面解決類似的同步問題。