簡述影響Cache命中率的因素

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

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

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

4、S的關(guān)系2、 Cache塊大小對命中率的影響當Cache的容量一定時，在采用組相聯(lián)映象和變換方式的Cache中，塊的大小對命中率的影響非常敏感。我們可以從下面的Cache映象邏輯表達式分析： 設(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ù)成反比。 因此，當Cache的塊容量很小，組的數(shù)目就多，主存中的某一塊可以映象到Cache中的塊數(shù)就少，所以此時，Cache的命中率低。隨著塊大小的增加，由于程序的空間局部性起主要作用，同一塊中數(shù)據(jù)的利用率比較高

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

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

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)方

8、式的對應(yīng)關(guān)系如圖所示。如果Cache的塊數(shù)為Cb，主存的塊數(shù)為Mb，則映象關(guān)系共有Cb×Mb種。   應(yīng)用全相聯(lián)的方式命中率比較高，Cache存儲空間利用率高。但是訪問相關(guān)存儲器時，每次都要與全部內(nèi)容比較，速度低，成本高，因而應(yīng)用少。2.直接相聯(lián)方式   地址映象規(guī)則： 主存儲器中一塊只能映象到Cache的一個特定的塊中。    (1) 主存與緩存分成相同大小的數(shù)據(jù)塊。    (2) 主存容量應(yīng)是緩存容量的整數(shù)倍，將主存空間按

9、緩存的容量分成區(qū)，主存中每一區(qū)的塊數(shù)與緩存的總塊數(shù)相等。    (3) 主存中某區(qū)的一塊存入緩存時只能存入緩存中塊號相同的位置。圖示出了直接相聯(lián)映象規(guī)則。 可見，主存中各區(qū)內(nèi)相同塊號的數(shù)據(jù)塊都可以分別調(diào)入緩存中塊號相同的地址中，但同時只能有一個區(qū)的塊存入緩存。由于主、緩存塊號相同，因此，目錄登記時，只記錄調(diào)入塊的區(qū)號即可。 應(yīng)用直接相聯(lián)的方式地址映象方式簡單，數(shù)據(jù)訪問時，只需檢查區(qū)號是否相等即可，因而可以得到比較快的訪問速度，硬件設(shè)備簡單。  但是使得替換操作頻繁，命中率比較低。3.組相聯(lián)映象方式 

10、60; 組相聯(lián)的映象規(guī)則：    (1) 主存和Cache按同樣大小劃分成塊。    (2) 主存和Cache按同樣大小劃分成組。   (3) 主存容量是緩存容量的整數(shù)倍，將主存空間按緩沖區(qū)的大小分成區(qū)，主存中每一區(qū)的組數(shù)與緩存的組數(shù)相同。  (4)  當主存的數(shù)據(jù)調(diào)入緩存時，主存與緩存的組號應(yīng)相等，也就是各區(qū)中的某一塊只能存入緩存的同組號的空間內(nèi)，但組內(nèi)各塊地址之間則可以任意存放， 即從主存的組到Cach

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

12、中率。常用算法如下：（1）隨機法（RAND法） 隨機替換算法就是用隨機數(shù)發(fā)生器產(chǎn)生一個要替換的塊號，將該塊替換出去，此算法簡單、易于實現(xiàn)，而且它不考慮Cache塊過去、現(xiàn)在及將來的使用情況，但是沒有利用上層存儲器使用的“歷史信息”、沒有根據(jù)訪存的局部性原理，故不能提高Cache的命中率，命中率較低。（2）先進先出法（FIFO法） 先進先出（First-In-First-Out，F(xiàn)IFO）算法。就是將最先進入Cache的信息塊替換出去。FIFO算法按調(diào)入Cache的先后決定淘汰的順序，選擇最早調(diào)入Cache的字塊進行替換，它不需要記錄各字塊的使用情況，比較容易實現(xiàn)，系統(tǒng)開銷小

13、，其缺點是可能會把一些需要經(jīng)常使用的程序塊（如循環(huán)程序）也作為最早進入Cache的塊替換掉，而且沒有根據(jù)訪存的局部性原理，故不能提高Cache的命中率。因為最早調(diào)入的信息可能以后還要用到，或者經(jīng)常要用到，如循環(huán)程序。此法簡單、方便，利用了主存的“歷史信息”， 但并不能說最先進入的就不經(jīng)常使用，其缺點是不能正確反映程序局部性原理，命中率不高，可能出現(xiàn)一種異?，F(xiàn)象。（3）近期最少使用法（LRU法） 近期最少使用（Least Recently Used，LRU）算法。這種方法是將近期最少使用的Cache中的信息塊替換出去。該算法較先進先出算法要好一些。但此法也

14、不能保證過去不常用將來也不常用。 LRU法是依據(jù)各塊使用的情況，總是選擇那個最近最少使用的塊被替換。這種方法雖然比較好地反映了程序局部性規(guī)律，但是這種替換方法需要隨時記錄Cache中各塊的使用情況，以便確定哪個塊是近期最少使用的塊。LRU算法相對合理，但實現(xiàn)起來比較復(fù)雜，系統(tǒng)開銷較大。通常需要對每一塊設(shè)置一個稱為計數(shù)器的硬件或軟件模塊，用以記錄其被使用的情況。結(jié)論：在Cache容量較小的情況下，隨機策略相對較好，而隨著Cache容量的增加，最近最少使用(LRU)和先進先出(FIFO)策略的效果較好。所以一般的計算機默認的采用LRU替換策略。由于主存中的塊比Cache中的要多，所以當要從主存調(diào)入一個塊到Cache中時，會出現(xiàn)該快