簡述影響Cache命中率的因素

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

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

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

4、he命中率H與容量S的關(guān)系2、 Cache塊大小對命中率的影響當(dāng)Cache的容量一定時，在采用組相聯(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）固定不變時，Cache塊大小與組數(shù)成反比。 因此，當(dāng)Cache的塊容量很小，組的數(shù)目就多，主存中的某一塊可以映象到Cache中的塊數(shù)就少，所以此時，Cache的命中率低。隨著塊大小的增加，由于程序的空間局部性起主要作用，同一塊中

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

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

7、會超過第一種作用，使命中率下降。綜上所述，塊的大小對Cache命中率的影響是顯而易見的；而Cache命中率對整個Cache存儲系統(tǒng)的存取效率的影響又是至關(guān)重要的。所以，對于系統(tǒng)體系結(jié)構(gòu)的設(shè)計人員，甚至是軟件開發(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存儲空間利用率高。但是訪問相關(guān)存儲器時，每次都要與全部內(nèi)容比較，速度低，成本高，因而應(yīng)用少。2.直接相聯(lián)方式地址映象規(guī)則：主存儲器中一塊只能映象到Cache的一個特定的塊中。(1)主存與緩存分成相同大小的數(shù)據(jù)塊。(2)主存容量應(yīng)是緩存容量的整數(shù)倍，將主存空間按緩存的容量分成區(qū)，主存中每一區(qū)的塊數(shù)與緩存的總塊數(shù)相等。(3)主存中某區(qū)的一塊存入緩存時只能存入緩存中塊號相同的位置。圖示出了直接相聯(lián)映象規(guī)則?？梢姡鞔嬷懈鲄^(qū)內(nèi)相同塊號的數(shù)據(jù)塊都可以分別調(diào)入緩存中塊號相同的地址中，但同時只能有一個區(qū)的塊存入緩存。由于主、緩存塊號相同，因此，目錄登記時，只記錄調(diào)入塊的區(qū)號即可。 應(yīng)用直接相聯(lián)的方

9、式地址映象方式簡單，數(shù)據(jù)訪問時，只需檢查區(qū)號是否相等即可，因而可以得到比較快的訪問速度，硬件設(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)入緩存時，主存與緩存的組號應(yīng)相等，也就是各區(qū)中的某一塊只能存入緩存的同組號的空間內(nèi)，但組內(nèi)各塊地址之間則可以任意存放，即從主存的組到Cache的組之間采用直接映象方式；在兩個對應(yīng)的組內(nèi)部采用全相聯(lián)映象方式。 應(yīng)用組相聯(lián)

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

11、生一個要替換的塊號，將該塊替換出去，此算法簡單、易于實現(xiàn)，而且它不考慮Cache塊過去、現(xiàn)在及將來的使用情況，但是沒有利用上層存儲器使用的“歷史信息”、沒有根據(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)行替換，它不需要記錄各字塊的使用情況，比較容易實現(xiàn)，系統(tǒng)開銷小，其缺點是可能會把一些需要經(jīng)常使用的程序塊（如循環(huán)程序）也作為最早進(jìn)入Cache的塊替換掉，而且沒有根

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