高速緩沖存儲器

組成結(jié)構(gòu)

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

　　主要由三大部分組成：

　　Cache存儲體：存放由主存調(diào)入的指令與數(shù)據(jù)塊。

　　地址轉(zhuǎn)換部件：建立目錄表以實現(xiàn)主存地址到緩存地址的轉(zhuǎn)換。

　　替換部件：在緩存已滿時按一定策略進(jìn)行數(shù)據(jù)塊替換，并修改地址轉(zhuǎn)換部件。

工作原理

　　高速緩沖存儲器通常由高速存儲器、聯(lián)想存儲器、替換邏輯電路和相應(yīng)的控制線路組成。在有高速緩沖存儲器的計算機(jī)系統(tǒng)中，中央處理器存取主存儲器的地址劃分為行號、列號和組內(nèi)地址三個字段。于是，主存儲器就在邏輯上劃分為若干行；每行劃分為若干的存儲單元組；每組包含幾個或幾十個字。高速存儲器也相應(yīng)地劃分為行和列的存儲單元組。二者的列數(shù)相同，組的大小也相同，但高速存儲器的行數(shù)卻比主存儲器的行數(shù)少得多。

　　聯(lián)想存儲器用于地址聯(lián)想，有與高速存儲器相同行數(shù)和列數(shù)的存儲單元。當(dāng)主存儲器某一列某一行存儲單元組調(diào)入高速存儲器同一列某一空著的存儲單元組時，與聯(lián)想存儲器對應(yīng)位置的存儲單元就記錄調(diào)入的存儲單元組在主存儲器中的行號。

　　當(dāng)中央處理器存取主存儲器時，硬件首先自動對存取地址的列號字段進(jìn)行譯碼，以便將聯(lián)想存儲器該列的全部行號與存取主存儲器地址的行號字段進(jìn)行比較：若有相同的，表明要存取的主存儲器單元已在高速存儲器中，稱為命中，硬件就將存取主存儲器的地址映射為高速存儲器的地址并執(zhí)行存取操作；若都不相同，表明該單元不在高速存儲器中，稱為脫靶，硬件將執(zhí)行存取主存儲器操作并自動將該單元所在的那一主存儲器單元組調(diào)入高速存儲器相同列中空著的存儲單元組中，同時將該組在主存儲器中的行號存入聯(lián)想存儲器對應(yīng)位置的單元內(nèi)。

　　當(dāng)出現(xiàn)脫靶而高速存儲器對應(yīng)列中沒有空的位置時，便淘汰該列中的某一組以騰出位置存放新調(diào)入的組，這稱為替換。確定替換的規(guī)則叫替換算法，常用的替換算法有:最近最少使用算法（LRU）、先進(jìn)先出法（FIFO）和隨機(jī)法（RAND）等。替換邏輯電路就是執(zhí)行這個功能的。另外，當(dāng)執(zhí)行寫主存儲器操作時，為保持主存儲器和高速存儲器內(nèi)容的一致性，對命中和脫靶須分別處理。

存儲層次

　　主-輔存存儲層次 由于計算機(jī)主存容量相對于程序員所需要的容量來說總是太小，程序與數(shù)據(jù)從輔存調(diào)入主存是由程序員自己安排的，程序員必須花費(fèi)很大精力和時間把大程序預(yù)先分成塊，確定好這些程序塊在輔存中的位置和裝入主存的地址，而且還要預(yù)先安排好程序運(yùn)行時各塊如何和何時調(diào)入調(diào)出，因此存在存儲空間的分配問題。操作系統(tǒng)的形成和發(fā)展使得程序員盡可能擺脫主、輔存之間的地址定位，同時形成了支持這些功能的“輔助硬件”，通過軟件、硬件的結(jié)合，把主存和輔存統(tǒng)一成了一個整體，如圖所示。這時，由主存、輔存形成了一個存儲層次，即存儲系統(tǒng)。從整體看，其速度接近于主存的速度，其容量則接近于輔存的容量，而每位的平均價格也接近于廉價的慢速的輔存平均價格。這種系統(tǒng)不斷發(fā)展和完善，就逐步形成了現(xiàn)在廣泛使用的虛擬存儲系統(tǒng)。在系統(tǒng)中，應(yīng)用程序員可用機(jī)器指令地址碼對整個程序統(tǒng)一編址，如同程序員具有對應(yīng)這個地址碼寬度的全部虛存空間一樣。該空間可以比主存實際空間大得多，以致可以存得下整個程序。這種指令地址碼稱為虛地址（虛存地址、虛擬地址）或邏輯地址，其對應(yīng)的存儲容量稱為虛存容量或虛存空間；而把實際主存的地址稱為物理地址、實（存）地址，其對應(yīng)的存儲容量稱為主存容量、實存容量或?qū)崳ㄖ鳎┐婵臻g

　　主-輔存存儲層次

CACHE-主存存儲層次

　　當(dāng)用虛地址訪問主存時，機(jī)器自動地把它經(jīng)輔助軟件、硬件變換成主存實地址。查看這個地址所對應(yīng)的單元內(nèi)容是否已經(jīng)裝入主存，如果在主存就進(jìn)行訪問，如果不在主存內(nèi)就經(jīng)輔助軟件、硬件把它所在的那塊程序和數(shù)據(jù)由輔存調(diào)入主存，而后進(jìn)行訪問。這些操作都不必由程序員來安排，也就是說，對應(yīng)用程員員是透明的。 主-輔存層次解決了存儲器大容量要求和低成本之間的矛盾。 在速度方面，計算機(jī)的主存和CPU直保持了大約一個數(shù)量級的差距。顯然這個差距限制了CPU速度潛力的發(fā)揮。為了彌合這個差距，僅采用一種工藝的單一存儲器是行不通的，必須進(jìn)一步從計算機(jī)系統(tǒng)結(jié)構(gòu)和組織上去研究。設(shè)置高速緩沖存儲器（Cache）是解決存取速度的重要方法。在CPU和主存中間設(shè)置高速緩沖存儲器，構(gòu)成高速緩存（Cache）-主存層次，要求Cache在速度上能跟得上CPU的要求。Cache-主存間的地址映象和調(diào)度吸取了比它較早出現(xiàn)的主-輔存存儲層次的技術(shù)，不同的是因其速度要求高，不是由軟、硬件結(jié)合而完全由硬件來實現(xiàn)，如圖所示。

地址映象與轉(zhuǎn)換

　　地址映象是指某一數(shù)據(jù)在內(nèi)存中的地址與在緩沖中的地址，兩者之間的對應(yīng)關(guān)系。下面介紹三種地址映象的方式。

　　1.全相聯(lián)方式

　　地址映象規(guī)則：主存的任意一塊可以映象到Cache中的任意一塊

　　(1) 主存與緩存分成相同大小的數(shù)據(jù)塊。

　　(2) 主存的某一數(shù)據(jù)塊可以裝入緩存的任意一塊空間中。如果Cache的塊數(shù)為Cb，主存的塊數(shù)為Mb，則映象關(guān)系共有Cb×Mb種。

　　目錄表存放在相關(guān)（聯(lián)）存儲器中，其中包括三部分：數(shù)據(jù)塊在主存的塊地址、存入緩存后的塊地址、及有效位（也稱裝入位）。由于是全相聯(lián)方式，因此，目錄表的容量應(yīng)當(dāng)與緩存的塊數(shù)相同。

　　優(yōu)點：命中率比較高，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ū)的一塊存入緩存時只能存入緩存中塊號相同的位置。

　　主存中各區(qū)內(nèi)相同塊號的數(shù)據(jù)塊都可以分別調(diào)入緩存中塊號相同的地址中，但同時只能有一個區(qū)的塊存入緩存。由于主、緩存塊號相同，因此，目錄登記時，只記錄調(diào)入塊的區(qū)號即可。主、緩存塊號及塊內(nèi)地址兩個字段完全相同。目錄表存放在高速小容量存儲器中，其中包括二部分：數(shù)據(jù)塊在主存的區(qū)號和有效位。目錄表的容量與緩存的塊數(shù)相同。

　　優(yōu)點：地址映象方式簡單，數(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)映象方式。

　　主存地址與緩存地址的轉(zhuǎn)換有兩部分，組地址是按直接映象方式，按地址進(jìn)行訪問，而塊地址是采用全相聯(lián)方式，按內(nèi)容訪問。組相聯(lián)的地址轉(zhuǎn)換部件也是采用相關(guān)存儲器實現(xiàn)。

　　優(yōu)點：塊的沖突概率比較低，塊的利用率大幅度提高，塊失效率明顯降低。

　　缺點：實現(xiàn)難度和造價要比直接映象方式高。

替換策略

　　1. 根據(jù)程序局部性規(guī)律可知：程序在運(yùn)行中，總是頻繁地使用那些最近被使用過的指令和數(shù)據(jù)。這就提供了替換策略的理論依據(jù)。綜合命中率、實現(xiàn)的難易及速度的快慢各種因素，替換策略可有隨機(jī)法、先進(jìn)先出法、最近最少使用法等。

　?。?）.隨機(jī)法（RAND法）

　　隨機(jī)法是隨機(jī)地確定替換的存儲塊。設(shè)置一個隨機(jī)數(shù)產(chǎn)生器，依據(jù)所產(chǎn)生的隨機(jī)數(shù)，確定替換塊。這種方法簡單、易于實現(xiàn)，但命中率比較低。

　?。?）.先進(jìn)先出法（FIFO法）

　　先進(jìn)先出法是選擇那個最先調(diào)入的那個塊進(jìn)行替換。當(dāng)最先調(diào)入并被多次命中的塊，很可能被優(yōu)先替換，因而不符合局部性規(guī)律。這種方法的命中率比隨機(jī)法好些，但還不滿足要求。先進(jìn)先出方法易于實現(xiàn)，

　?。?）.最近最少使用法（LRU法）

　　LRU法是依據(jù)各塊使用的情況， 總是選擇那個最近最少使用的塊被替換。這種方法比較好地反映了程序局部性規(guī)律。 實現(xiàn)LRU策略的方法有多種。

　　2 在多體并行存儲系統(tǒng)中，由于 I/O 設(shè)備向主存請求的級別高于 CPU 訪存，這就出現(xiàn)了 CPU 等待 I/O 設(shè)備訪存的現(xiàn)象，致使 CPU 空等一段時間，甚至可能等待幾個主存周期，從而降低了 CPU 的工作效率。為了避免 CPU 與 I/O 設(shè)備爭搶訪存，可在 CPU 與主存之間加一級緩存，這樣，主存可將 CPU 要取的信息提前送至緩存，一旦主存在與 I/O 設(shè)備交換時， CPU 可直接從緩存中讀取所需信息，不必空等而影響效率。

　　3 目前提出的算法可以分為以下三類（第一類是重點要掌握的）：

　?。?）傳統(tǒng)替換算法及其直接演化，其代表算法有 ：①LRU（ Least Recently Used）算法：將最近最少使用的內(nèi)容替換出Cache ；②LFU（ Lease Frequently Used）算法：將訪問次數(shù)最少的內(nèi)容替換出Cache；③如果Cache中所有內(nèi)容都是同一天被緩存的，則將最大的文檔替換出Cache，否則按LRU算法進(jìn)行替換 。④FIFO( First In First Out)：遵循先入先出原則，若當(dāng)前Cache被填滿，則替換最早進(jìn)入Cache的那個。

　?。?）基于緩存內(nèi)容關(guān)鍵特征的替換算法，其代表算法有：①Size替換算法：將最大的內(nèi)容替換出Cache②LRU— MIN替換算法：該算法力圖使被替換的文檔個數(shù)最少。設(shè)待緩存文檔的大小為S，對Cache中緩存的大小至少是S的文檔，根據(jù)LRU算法進(jìn)行替換；如果沒有大小至少為S的對象，則從大小至少為S/2的文檔中按照LRU算法進(jìn)行替換；③LRU—Threshold替換算法：和LRU算法一致，只是大小超過一定閾值的文檔不能被緩存；④Lowest Lacency First替換算法：將訪問延遲最小的文檔替換出Cache。

　?。?）基于代價的替換算法，該類算法使用一個代價函數(shù)對Cache中的對象進(jìn)行評估，最后根據(jù)代價值的大小決定替換對象。其代表算法有：①Hybrid算法：算法對Cache中的每一個對象賦予一個效用函數(shù)，將效用最小的對象替換出Cache；②Lowest Relative Value算法：將效用值最低的對象替換出Cache；③Least Normalized Cost Replacement（LCNR）算法：該算法使用一個關(guān)于文檔訪問頻次、傳輸時間和大小的推理函數(shù)來確定替換文檔；④Bolot等人 提出了一種基于文檔傳輸時間代價、大小、和上次訪問時間的權(quán)重推理函數(shù)來確定文檔替換；⑤Size—Adjust LRU（SLRU）算法：對緩存的對象按代價與大小的比率進(jìn)行排序，并選取比率最小的對象進(jìn)行替換。

作用介紹

　　在計算機(jī)技術(shù)發(fā)展過程中,主存儲器存取速度一直比中央處理器操作速度慢得多，使中央處理器的高速處理能力不能充分發(fā)揮，整個計算機(jī)系統(tǒng)的工作效率受到影響。有很多方法可用來緩和中央處理器和主存儲器之間速度不匹配的矛盾，如采用多個通用寄存器、多存儲體交叉存取等，在存儲層次上采用高速緩沖存儲器也是常用的方法之一。很多大、中型計算機(jī)以及新近的一些小型機(jī)、微型機(jī)也都采用高速緩沖存儲器。

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

讀取命中率

　　CPU在Cache中找到有用的數(shù)據(jù)被稱為命中，當(dāng)Cache中沒有CPU所需的數(shù)據(jù)時（這時稱為未命中），CPU才訪問內(nèi)存。從理論上講，在一顆擁有2級Cache的CPU中，讀取L1Cache的命中率為80%。也就是說CPU從L1Cache中找到的有用數(shù)據(jù)占數(shù)據(jù)總量的80%，剩下的20%從L2Cache讀取。由于不能準(zhǔn)確預(yù)測將要執(zhí)行的數(shù)據(jù)，讀取L2的命中率也在80%左右（從L2讀到有用的數(shù)據(jù)占總數(shù)據(jù)的16%）。那么還有的數(shù)據(jù)就不得不從內(nèi)存調(diào)用，但這已經(jīng)是一個相當(dāng)小的比例了。在一些高端領(lǐng)域的CPU中，我們常聽到L3Cache，它是為讀取L2Cache后未命中的數(shù)據(jù)設(shè)計的—種Cache，在擁有L3Cache的CPU中，只有約5%的數(shù)據(jù)需要從內(nèi)存中調(diào)用，這進(jìn)一步提高了CPU的效率。

　　為了保證CPU訪問時有較高的命中率，Cache中的內(nèi)容應(yīng)該按一定的算法替換。一種較常用的算法是“最近最少使用算法”（LRU算法），它是將最近一段時間內(nèi)最少被訪問過的行淘汰出局。因此需要為每行設(shè)置一個計數(shù)器，LRU算法是把命中行的計數(shù)器清零，其他各行計數(shù)器加1。當(dāng)需要替換時淘汰行計數(shù)器計數(shù)值最大的數(shù)據(jù)行出局。這是一種高效、科學(xué)的算法，其計數(shù)器清零過程可以把一些頻繁調(diào)用后再不需要的數(shù)據(jù)淘汰出Cache，提高Cache的利用率。

　　Cache的替換算法對命中率的影響。 當(dāng)新的主存塊需要調(diào)入Cache并且它的可用空間位置又被占滿時，需要替換掉Cache的數(shù)據(jù)，這就產(chǎn)生了替換策略（算法）問題。根據(jù)程序局部性規(guī)律可知：程序在運(yùn)行中，總是頻繁地使用那些最近被使用過的指令和數(shù)據(jù)。這就提供了替換策略的理論依據(jù)。 替換算法目標(biāo)就是使Cache獲得最高的命中率。Cache替換算法是影響代理緩存系統(tǒng)性能的一個重要因素，一個好的Cache替換算法可以產(chǎn)生較高的命中率。常用算法如下：

　?。?）隨機(jī)法（RAND法） 隨機(jī)替換算法就是用隨機(jī)數(shù)發(fā)生器產(chǎn)生一個要替換的塊號，將該塊替換出去，此算法簡單、易于實現(xiàn)，而且它不考慮Cache塊過去、現(xiàn)在及將來的使用情況，但是沒有利用上層存儲器使用的“歷史信息”、沒有根據(jù)訪存的局部性原理，故不能提高Cache的命中率，命中率較低。

　?。?）先進(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的塊替換掉，而且沒有根據(jù)訪存的局部性原理，故不能提高Cache的命中率。因為最早調(diào)入的信息可能以后還要用到，或者經(jīng)常要用到，如循環(huán)程序。此法簡單、方便，利用了主存的“歷史信息”， 但并不能說最先進(jìn)入的就不經(jīng)常使用，其缺點是不能正確反映程序局部性原理，命中率不高，可能出現(xiàn)一種異常現(xiàn)象。

　　（3）近期最少使用法（LRU法） 近期最少使用（Least Recently Used，LRU）算法。這種方法是將近期最少使用的Cache中的信息塊替換出去。該算法較先進(jìn)先出算法要好一些。但此法也不能保證過去不常用將來也不常用。 LRU法是依據(jù)各塊使用的情況，總是選擇那個最近最少使用的塊被替換。這種方法雖然比較好地反映了程序局部性規(guī)律，但是這種替換方法需要隨時記錄Cache中各塊的使用情況，以便確定哪個塊是近期最少使用的塊。LRU算法相對合理，但實現(xiàn)起來比較復(fù)雜，系統(tǒng)開銷較大。通常需要對每一塊設(shè)置一個稱為計數(shù)器的硬件或軟件模塊，用以記錄其被使用的情況。