簡述影響Cache命中率的因素

1、簡述影響Cache命中率的因素簡述影響Cache命中率的因素摘要：存儲(chǔ)器是計(jì)算機(jī)的核心部件之一。由于CPU和主存在速度上的存在著巨大差異，現(xiàn)代計(jì)算機(jī)都在CPU和主存之間設(shè)置一個(gè)高速、小容量的緩沖存儲(chǔ)器cache。Cache最重要的技術(shù)指標(biāo)是它的命中率。本文簡單討論了影響Cache命中率的幾個(gè)因素。關(guān)鍵字：cache容量，塊大小，替換算法，映射方式。一、引言在計(jì)算機(jī)技術(shù)發(fā)展過程中,主存儲(chǔ)器存取速度一直比中央處理器操作速度慢得多，使中央處理器的高速處理能力不能充分發(fā)揮，整個(gè)計(jì)算機(jī)系統(tǒng)的工作效率受到影響。有很多方法可用來緩和中央處理器和主存儲(chǔ)器之間速度不匹配的矛盾，如采用多個(gè)通用寄存器、多存儲(chǔ)體交叉

2、存取等，在存儲(chǔ)層次上采用高速緩沖存儲(chǔ)器也是常用的方法之一。很多大、中型計(jì)算機(jī)以及新近的一些小型機(jī)、微型機(jī)也都采用高速緩沖存儲(chǔ)器。高速緩沖存儲(chǔ)器的容量一般只有主存儲(chǔ)器的幾百分之一，但它的存取速度能與中央處理器相匹配。根據(jù)程序局部性原理，正在使用的主存儲(chǔ)器某一單元鄰近的那些單元將被用到的可能性很大。因而，當(dāng)中央處理器存取主存儲(chǔ)器某一單元時(shí)，計(jì)算機(jī)硬件就自動(dòng)地將包括該單元在內(nèi)的那一組單元內(nèi)容調(diào)入高速緩沖存儲(chǔ)器，中央處理器即將存取的主存儲(chǔ)器單元很可能就在剛剛調(diào)入到高速緩沖存儲(chǔ)器的那一組單元內(nèi)。于是，中央處理器就可以直接對高速緩沖存儲(chǔ)器進(jìn)行存取。在整個(gè)處理過程中，如果中央處理器絕大多數(shù)存取主存儲(chǔ)器的操作

3、能為存取高速緩沖存儲(chǔ)器所代替，計(jì)算機(jī)系統(tǒng)處理速度就能顯著提高。高速緩沖存儲(chǔ)器最重要的技術(shù)指標(biāo)是它的命中率。二、簡述影響cache命中率的因素1、 Cache容量對命中率的影響Cache的命中率隨它的容量的增加而提高，它們之間的關(guān)系曲線如圖所示。在Cache容量比較小的時(shí)候，命中率提高得非常快，但根據(jù)邊際效應(yīng)遞減原理隨著Cache容量的增加，命中率提高的速度逐漸降低。當(dāng)Cache的容量增加到無窮大時(shí)，命中率可望達(dá)到100%，但是這在實(shí)際是做不到的。在一般情況下，圖中的關(guān)系曲線可以近似地表示為H=1-S-0.5。因此，當(dāng)Cache的容量達(dá)到一定值之后，再增加Cache容量，命中率的提高很少。Cac

4、he命中率H與容量S的關(guān)系2、 Cache塊大小對命中率的影響當(dāng)Cache的容量一定時(shí)，在采用組相聯(lián)映象和變換方式的Cache中，塊的大小對命中率的影響非常敏感。我們可以從下面的Cache映象邏輯表達(dá)式分析： 設(shè)Cache的總量為S，組數(shù)為M，組內(nèi)塊數(shù)為N，塊大小為A。所以，有： S M*N*A 由上式可知，在Cache的容量S和Cache組內(nèi)塊數(shù)N（也可換成是組數(shù)M）固定不變時(shí)，Cache塊大小與組數(shù)成反比。 因此，當(dāng)Cache的塊容量很小，組的數(shù)目就多，主存中的某一塊可以映象到Cache中的塊數(shù)就少，所以此時(shí)，Cache的命中率低。隨著塊大小的增加，由于程序的空間局部性起主要作用，同一塊中

5、數(shù)據(jù)的利用率比較高。因此，Cache的命中率開始升高。但如果塊變得過大的話，會(huì)減少裝入Cache的總行數(shù)，而且，也會(huì)使得離所訪問的位置較遠(yuǎn)的塊被再次使用的概率變小。因此，這種增加趨勢在某一個(gè)“最佳塊大小”處使Cache命中率達(dá)到最大值。在這一點(diǎn)以后，命中率隨著塊大小的增加反而減小。因?yàn)閷?shí)際上，當(dāng)塊的容量變得比較大時(shí)（此時(shí)還是在組相聯(lián)映象中，并沒有蛻變成全相聯(lián)映象），進(jìn)入Cache中的許多數(shù)據(jù)可能根本用不上。而且，隨著塊大小的增加，程序時(shí)間局部性的作用就會(huì)逐漸減弱。最后，當(dāng)塊大小等于整個(gè)Cache的容量時(shí)（此時(shí)主存塊應(yīng)該是按成組的方式被調(diào)入Cache），命中率將趨近于零。所以，根據(jù)Cache塊的

6、容量由小到大的變化，可得Cache命中率的情況如圖所示 (1) 對于給定的Cache 容量，當(dāng)塊大小增加時(shí)，命中率開始時(shí)處于上升趨勢，后來反而會(huì)下降。(2) Cache容量越大，會(huì)使命中率達(dá)到最高的拐點(diǎn)的塊大小增大。在這里，導(dǎo)致命中率先上升后下降的原因在于增加塊大小產(chǎn)生雙重作用。一方面會(huì)減少強(qiáng)制性失效，因?yàn)槌绦蚓植啃栽?，增加塊大小增加了利用空間局部性的機(jī)會(huì)；另一方面，在容量一定情況下，增加塊大小會(huì)減少總的塊數(shù)目，會(huì)增加沖突失效，在Cache容量較小時(shí)，還可能增加容量失效。剛開始增加塊大小時(shí)，由于塊大小還不是很大，上述第一種作用超過第二種作用，使命中率上升。當(dāng)塊大小增加到一定程度時(shí)，第二種作用

7、會(huì)超過第一種作用，使命中率下降。綜上所述，塊的大小對Cache命中率的影響是顯而易見的；而Cache命中率對整個(gè)Cache存儲(chǔ)系統(tǒng)的存取效率的影響又是至關(guān)重要的。所以，對于系統(tǒng)體系結(jié)構(gòu)的設(shè)計(jì)人員，甚至是軟件開發(fā)人員來說，關(guān)于塊大小的最佳選擇都是值得研究的。3、 Cache中與主存映射方式對命中率的影響1.全相聯(lián)方式地址映象規(guī)則：主存的任意一塊可以映象到Cache中的任意一塊(1)主存與緩存分成相同大小的數(shù)據(jù)塊。(2)主存的某一數(shù)據(jù)塊可以裝入緩存的任意一塊空間中。全相聯(lián)方式的對應(yīng)關(guān)系如圖所示。如果Cache的塊數(shù)為Cb，主存的塊數(shù)為Mb，則映象關(guān)系共有CbMb種。 應(yīng)用全相聯(lián)的方式命中率比較高，

8、Cache存儲(chǔ)空間利用率高。但是訪問相關(guān)存儲(chǔ)器時(shí)，每次都要與全部內(nèi)容比較，速度低，成本高，因而應(yīng)用少。2.直接相聯(lián)方式地址映象規(guī)則：主存儲(chǔ)器中一塊只能映象到Cache的一個(gè)特定的塊中。(1)主存與緩存分成相同大小的數(shù)據(jù)塊。(2)主存容量應(yīng)是緩存容量的整數(shù)倍，將主存空間按緩存的容量分成區(qū)，主存中每一區(qū)的塊數(shù)與緩存的總塊數(shù)相等。(3)主存中某區(qū)的一塊存入緩存時(shí)只能存入緩存中塊號(hào)相同的位置。圖示出了直接相聯(lián)映象規(guī)則。可見，主存中各區(qū)內(nèi)相同塊號(hào)的數(shù)據(jù)塊都可以分別調(diào)入緩存中塊號(hào)相同的地址中，但同時(shí)只能有一個(gè)區(qū)的塊存入緩存。由于主、緩存塊號(hào)相同，因此，目錄登記時(shí)，只記錄調(diào)入塊的區(qū)號(hào)即可。 應(yīng)用直接相聯(lián)的方

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

10、的方式塊的沖突概率比較低，塊的利用率大幅度提高，塊失效率明顯降低。但是實(shí)現(xiàn)難度和造價(jià)要比直接映象方式高。4、 Cache的替換算法對命中率的影響當(dāng)新的主存塊需要調(diào)入Cache并且它的可用空間位置又被占滿時(shí)，需要替換掉Cache的數(shù)據(jù)，這就產(chǎn)生了替換策略（算法）問題。根據(jù)程序局部性規(guī)律可知：程序在運(yùn)行中，總是頻繁地使用那些最近被使用過的指令和數(shù)據(jù)。這就提供了替換策略的理論依據(jù)。替換算法目標(biāo)就是使Cache獲得最高的命中率。Cache替換算法是影響代理緩存系統(tǒng)性能的一個(gè)重要因素，一個(gè)好的Cache替換算法可以產(chǎn)生較高的命中率。常用算法如下：（1）隨機(jī)法（RAND法）隨機(jī)替換算法就是用隨機(jī)數(shù)發(fā)生器產(chǎn)

11、生一個(gè)要替換的塊號(hào)，將該塊替換出去，此算法簡單、易于實(shí)現(xiàn)，而且它不考慮Cache塊過去、現(xiàn)在及將來的使用情況，但是沒有利用上層存儲(chǔ)器使用的“歷史信息”、沒有根據(jù)訪存的局部性原理，故不能提高Cache的命中率，命中率較低。（2）先進(jìn)先出法（FIFO法）先進(jìn)先出（First-In-First-Out，F(xiàn)IFO）算法。就是將最先進(jìn)入Cache的信息塊替換出去。FIFO算法按調(diào)入Cache的先后決定淘汰的順序，選擇最早調(diào)入Cache的字塊進(jìn)行替換，它不需要記錄各字塊的使用情況，比較容易實(shí)現(xiàn)，系統(tǒng)開銷小，其缺點(diǎn)是可能會(huì)把一些需要經(jīng)常使用的程序塊（如循環(huán)程序）也作為最早進(jìn)入Cache的塊替換掉，而且沒有根

12、據(jù)訪存的局部性原理，故不能提高Cache的命中率。因?yàn)樽钤缯{(diào)入的信息可能以后還要用到，或者經(jīng)常要用到，如循環(huán)程序。此法簡單、方便，利用了主存的“歷史信息”，但并不能說最先進(jìn)入的就不經(jīng)常使用，其缺點(diǎn)是不能正確反映程序局部性原理，命中率不高，可能出現(xiàn)一種異?，F(xiàn)象。（3）近期最少使用法（LRU法）近期最少使用（LeastRecentlyUsed，LRU）算法。這種方法是將近期最少使用的Cache中的信息塊替換出去。該算法較先進(jìn)先出算法要好一些。但此法也不能保證過去不常用將來也不常用。LRU法是依據(jù)各塊使用的情況，總是選擇那個(gè)最近最少使用的塊被替換。這種方法雖然比較好地反映了程序局部性規(guī)律，但是這種替換方法需要隨時(shí)記錄Cache中各塊的使用情況，以便確定哪個(gè)塊是近期最少使用的塊。LRU算法相對合理，但實(shí)現(xiàn)起來比較復(fù)雜，系統(tǒng)開銷較大。通常需要對每一塊設(shè)置一個(gè)稱為計(jì)數(shù)器的硬件或軟件模塊，用以記錄其被使用的情況。結(jié)論：在Cache容量較小的情況下，隨機(jī)策略相對較好，而隨著Cache容量的增加，最近最少使用(LRU)和先進(jìn)先出(FIFO)策略的效果較好。所以一般的計(jì)算機(jī)默認(rèn)的采用LRU替換策略。由于主存中的塊比Cache中的要多，所以當(dāng)要從主存調(diào)入一個(gè)塊到Cache中時(shí)，會(huì)出現(xiàn)該快所映像到的一組Cache塊已被占用的情況。這是需要強(qiáng)制其中