席紅旗

(河南教育學院信息技術系，河南鄭州 450046)

計算機高速緩沖存儲器(Cache)命中率的分析

席紅旗

(河南教育學院信息技術系，河南鄭州 450046)

從Cache的容量、空間邏輯組織結(jié)構(gòu)的組大小、塊大小、數(shù)據(jù)的替換算法和寫入Cache的數(shù)據(jù)地址流對Cache命中率的影響進行分析，選擇合適的參數(shù)可提高Cache的命中率，有效地提高計算機的運算速度.

存儲器;Cache命中率;組大小;塊大小;替換算法

0 引言

提高計算機的存取速度除了從計算機硬件介質(zhì)上解決外，更多的是從數(shù)據(jù)存取方法上不斷地提出新的方法.處在計算機多級存儲層次的計算機高速緩沖存儲器(Computer Cache Memory，以下簡稱Cache)，直接解決了CPU和主存速度不匹配的問題，Cache的大小、容量的組織方式、訪問方法等直接影響了CPU處理數(shù)據(jù)的速度.

1 計算機存儲器體系層的次結(jié)構(gòu)介紹

計算機的存儲體系是為了滿足人們對計算機存儲器“容量大、速度快、價格低”的要求而設計的.存儲體系的層次結(jié)構(gòu)如圖1所示，其中M1，M2，M3，…，Mn為不同技術實現(xiàn)的存儲器.最靠近CPU的M1速度最快，但單位存儲容量的價格最高.Mn離CPU最遠，這一層的存儲器速度最慢，容量最大，單位容量價格最低.存儲體系在工作時，以塊或者頁面為單位進行數(shù)據(jù)傳遞.對用戶來說，使用計算機時，存儲數(shù)據(jù)的速度接近M1，而存儲容量相當于Mn，整體的存儲器的價格相對較低，這就滿足了最初存儲體系設計目的.在當前的計算機存儲系統(tǒng)中，通常為三級存儲器體系，即高速緩沖存儲器(Cache)、主存和外存.

2 高級緩沖存儲器的工作原理

高級緩沖存儲器是存在于CPU和主存之間的存儲體，用于彌補主存速度的不足.從CPU看來，整個存儲體系的速度接近Cache，而容量卻接近主存.CPU在取數(shù)據(jù)時，先從Cache中尋找數(shù)據(jù)，如果要找的數(shù)據(jù)存在于Cache中，就稱為命中，否則稱為不命中.命中的次數(shù)與總的訪問次數(shù)的比稱為命中率［1］.此時CPU把數(shù)據(jù)從Cache中取出進行處理.如果沒有在Cache中找到需要的數(shù)據(jù)，就直接到主存中查找，然后對找到的數(shù)據(jù)進行處理，同時把這些數(shù)據(jù)回寫到Cache中，以備下次使用時直接從Cache中取數(shù)據(jù).因為Cache的存取速度比主存的存取速度高得多，所以提高了存儲數(shù)據(jù)的速度.如果CPU從Cache中查找數(shù)據(jù)的命中次數(shù)提高，也就是命中率高，就可大大地提高計算機的存儲速度，從而提高計算的性能.

圖1 存儲器的層次結(jié)構(gòu)Fig.1Hierarchical structure of memory

3 影響Cache命中率的因素分析

Cache命中率的高低主要與Cache中塊的大小、組的大小、Cache容量和Cache中數(shù)據(jù)的替換算法和地址流的簇聚性有關.

3.1 Cache命中率與Cache容量的關系

如果CPU每次需要訪問的數(shù)據(jù)都存在于Cache中，也就是每次訪問Cache都命中，那么Cache的容量就要足夠大，如果容量達到和存儲體系末端存儲體的容量一樣大，那么CPU每次都能在Cache中找到需要的數(shù)據(jù)，Cache的命中率是100%.而事實上Cache的容量不可能有這么大，因為它違背了存儲體系“容量大、速度快、價格低”的設計中“價格低”的要求，目前市場上的計算機的Cache大小為幾十MB.但我們可以看到，Cache容量的大小直接影響到Cache的命中率，命中率的大小與Cache的容量的關系如圖2所示，Hc為命中率，s為Cache的容量，它符合關系式

3.2 Cache命中率與Cache中塊的大小的關系

為了存取方便，把Cache的存儲空間分為若干大小相等的小空間，這些小的空間就稱為塊.當CPU訪問Cache時，查找需要的數(shù)據(jù)是否存在于塊內(nèi)，如果存在，則命中該塊.由于Cache的設計是基于存儲器數(shù)據(jù)的局部性［2］而設計的，如果塊的空間過小，存放數(shù)據(jù)過少，造成部分數(shù)據(jù)不存在，存儲空間的局部性就沒有得到很好的利用，命中率就不會很高.這樣，當塊達到一定大小的時候，塊內(nèi)存儲的數(shù)據(jù)能滿足CPU的需求，命中率就會提高，當塊的大小繼續(xù)擴大時，Cache內(nèi)包括的總塊數(shù)就會減少，這也降低了CPU對Cache塊的命中率，所以存在一個平衡點，在該平衡點附近，Cache的命中率最高，命中率和塊的大小關系如圖3所示.

3.3 Cache命中率與Cache中組數(shù)的關系

Cache中的組是指把Cache中的連續(xù)的塊組合在一起，形成一個新的邏輯存儲空間，這些空間就是稱為Cache的組.在Cache和主存映射關系中，組與組的映射關系是一種很重要的映射關系，也是存儲體系實現(xiàn)“容量大、速度快、價格低”的方法.在組相連映射方式中，如果Cache的組數(shù)過多，就像塊分得越多一樣，組的空間就會越小，直接映像的成分增加，映射到Cache中的塊數(shù)減少，命中率下降;反之，命中率增加［3］.

3.4 Cache命中率與替換算法的關系

由于Cache的容量是有限的，主存中的內(nèi)容不可能全部映射到Cache中，為了利用存儲器數(shù)據(jù)的局部性，采用一種方法把某時間段內(nèi)常用的數(shù)據(jù)存放到Cache中，替換掉原來的數(shù)據(jù)，這就是Cache數(shù)據(jù)的替換算法，常見的替換算法有隨機法(Random，RAND)、先進先出(First-In-First-Out，F(xiàn)IFO)算法、最近最少使用(Least Recently Used，LRU)算法［1，4］.隨機法沒有固定規(guī)律可循，隨機替換掉Cache中的數(shù)據(jù)，高的命中率很難保證;先進先出算法不能突出存儲器數(shù)據(jù)的局部性，即使使用頻率不高的數(shù)據(jù)也會被新調(diào)用的數(shù)據(jù)替換掉，命中率也不會高;最近最少使用算法最能突出存儲器數(shù)據(jù)的局部性，在某一時段內(nèi)，用新的數(shù)據(jù)把使用次數(shù)最少的數(shù)據(jù)替換掉，這樣Cache中存儲的數(shù)據(jù)總是最近使用頻率最高的數(shù)據(jù)，CPU在調(diào)用數(shù)據(jù)時在Cache中找到的幾率也會高，也就是命中率較高.

3.5 Cache命中率與地址流的關系

地址流是指寫入Cache中的數(shù)據(jù)地址的集合.在寫入Cache的過程中，如果地址流具有局部性，即有些數(shù)據(jù)反復寫入Cache，特別是在LRU替換方法下，具有較高局部性的地址流能夠有效提高Cache的命中率.如果地址流的數(shù)量過小，也就是Cache的塊容量過大的情況下，就不能很好地體現(xiàn)出地址流的局部性，此時Cache的命中率就會降低.所以地址流對Cache命中率的影響是在Cache的替換方法和塊大小確定的情況下才能夠衡量.

通過以上分析，Cache命中率和Cache容量的大小、組的大小、塊的大小、替換算法和地址流的簇聚性都有關系.只有選擇合適的參數(shù)，才能提高Cache的命中率，有效地提高計算機的運算速度.

4 小結(jié)

Cache命中率的高低直接影響到計算機處理數(shù)據(jù)的速度，不僅用邏輯方法從數(shù)據(jù)的處理上提高Cache的命中率，比如數(shù)據(jù)的替換方法等，還可以從物理上改進Cache存儲器的存取速度，比如Cache的材質(zhì)、存取電路的改進等，從而進一步提高計算機的性能.

［1］陳建鐸.計算機系統(tǒng)結(jié)構(gòu)教程［M］.北京:電子工業(yè)出版社，2006.

［2］陸鑫達，翁楚良.計算機系統(tǒng)結(jié)構(gòu)［M］.2版.北京:高等教育出版社，2008.

［3］李學干.計算機系統(tǒng)結(jié)構(gòu)［M］.西安:西安交通大學出版社，2006.

［4］NULL L，LOBUR J.計算機組成與體系結(jié)構(gòu)［M］.黃河，譯.北京:機械工業(yè)出版社，2006.

Analysis on Hit Rate of Computer Cache Memory(Cache)

XI Hong-qi

(Department of Information Technology，Henan Institute of Education，Zhengzhou 450046，China)

The factors affecting the hit ratio of Cache，which include the capacity of Cache，the group size，block size of logic of space structure，data replacement algorithm and address stream of writing data to Cache，were analyzed.The proper parameter was selected to raise the hit ratio of Cache，and the computer operation speed can be raised.

memory;hit ratio of Cache;group size;block size;replacement algorithm

O172.2

A

1007－0834(2012)03－0031－02

10.3969/j.issn.1007－0834.2012.03.010

2011－11－24

席紅旗(1975—)，男，河南葉縣人，河南教育學院信息技術系講師.