高速緩沖存儲(chǔ)器的功能、結(jié)構(gòu)與工作原理

1、高速緩沖存儲(chǔ)器是存在于主存與CPUs間的一級(jí)存儲(chǔ)器，由靜態(tài)存儲(chǔ)芯片(SRAM殂成,容量比較小但速度比主存高得多，接近于CPU勺速度。Cache的功能是用來存放那些近期需要運(yùn)行的指令與數(shù)據(jù)。目的是提高CPU寸存儲(chǔ)器的訪問速度。為此需要解決2個(gè)技術(shù)問題：一是主存地址與緩存地址的映象及轉(zhuǎn)換；二是按一定原則對(duì)Cache的內(nèi)容進(jìn)行替換。Cache的結(jié)構(gòu)和工作原理如圖2.3.1所示。主要由三大部分組成:Cache存儲(chǔ)體：存放由主存調(diào)入的指令與數(shù)據(jù)塊。地址轉(zhuǎn)換部件：建立目錄表以實(shí)現(xiàn)主存地址到緩存地址的轉(zhuǎn)換。替換部件：在緩存已滿時(shí)按一定策略進(jìn)行數(shù)據(jù)塊替換，并修改地址轉(zhuǎn)換部件。2.3.2地址映象與轉(zhuǎn)換地址映象是

2、指某一數(shù)據(jù)在內(nèi)存中的地址與在緩沖中的地址，兩者之間的對(duì)應(yīng)關(guān)系。下面介紹三種地址映象的方式。1 .全相聯(lián)方式地址映象規(guī)則：主存的任意一塊可以映象到Cache中的任意一塊(1)主存與緩存分成相同大小的數(shù)據(jù)塊。(2)主存的某一數(shù)據(jù)塊可以裝入緩存的任意一塊空間中。全相聯(lián)方式的又力關(guān)系如圖2.3.2所示。如果Cache的塊數(shù)為C-主存的塊數(shù)為M-則映象關(guān)系共有1xMb種圖2.3-2全相聯(lián)噢象方式圖2.3.3示出了目錄表的格式及地址變換規(guī)則。目錄表存放在相關(guān)（聯(lián)）存儲(chǔ)器中，其中包括三部分：數(shù)據(jù)塊在主存的塊地址、存入緩存后的塊地址、及有效位（也稱裝入位）。由于是全相聯(lián)方式，因此，目錄表的容量應(yīng)當(dāng)與緩存的塊數(shù)

3、相同。塊號(hào)£塊內(nèi)地址|主存地址1塊號(hào)b境內(nèi)畫kwCachti地址命中；TB主存塊號(hào)以Cache塊號(hào)b狎敢付目錄表（由相聯(lián)存儲(chǔ)器構(gòu)成，共備個(gè)字）®23.3全相豉地址轉(zhuǎn)換舉例：某機(jī)主存容量為1M,Cache的容量為32KB,每塊的大小為16個(gè)字（或字節(jié)）。劃出主、緩存的地址格式、目錄表格式及其容量。主存地址舞存地址容量：與緩沖塊數(shù)量相同即211=2048(或32Kz16=2048)優(yōu)點(diǎn)：命中率比較高Cache存儲(chǔ)空間利用率高。目錄表缺點(diǎn)：訪問相關(guān)存儲(chǔ)器時(shí)，每次都要與全部內(nèi)容比較，速度低，成本高，因而應(yīng)用少。2.直接相聯(lián)方式地址映象規(guī)則：主存儲(chǔ)器中一塊只能映象到Cache的一個(gè)特

4、定的塊中。(1)主存與緩存分成相同大小的數(shù)據(jù)塊。(2)主存容量應(yīng)是緩存容量的整數(shù)倍，將主存空間按緩存的容量分成區(qū)，主存中每一區(qū)的塊數(shù)與緩存的總塊數(shù)相等。(3)主存中某區(qū)的一塊存入緩存時(shí)只能存入緩存中塊號(hào)相同的位置。圖2.3.4示出了直接相聯(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)即可。塊7一1Cache，區(qū)0bE1塊2Cb-i塊Mb-CLU塊Mb-1總1塊”-c口塊CL至CJ1圖2.X4直接相聯(lián)映象方式圖2.3.5示出了主、緩沖地址格式、目錄表的格式及地址變換規(guī)則

5、。主、緩存塊號(hào)及塊內(nèi)地址兩個(gè)字段完全相同。目錄表存放在高速小容量存儲(chǔ)器中，其中包括二部分：數(shù)據(jù)塊在主存的區(qū)號(hào)和有效位。目錄表的容量與緩存的塊數(shù)相同區(qū)表存儲(chǔ)器圖215直接相康地址轉(zhuǎn)換地址變換過程：用主存地址中的塊號(hào)B去訪問目錄存儲(chǔ)器，把讀出來的區(qū)號(hào)與主存地址中的區(qū)號(hào)E進(jìn)行比較，比較結(jié)果相等，有效位為1,則Cache命中，可以直接用塊號(hào)及塊內(nèi)地址組成的緩沖地址到緩存中取數(shù)；比較結(jié)果不相等，有效位為1,可以進(jìn)行替換，如果有效位為0,可以直接調(diào)入所需塊。優(yōu)點(diǎn)：地址映象方式簡單，數(shù)據(jù)訪問時(shí)，只需檢查區(qū)號(hào)是否相等即可，因而可以得到比較快的訪問速度，硬件設(shè)備簡單。缺點(diǎn)：替換操作頻繁，命中率比較低。舉例：上例

6、中，主存容量為1M,Cache的容量為32KB,每塊的大小為16個(gè)字(或字節(jié))。劃出主、緩存的地址格式、目錄表格式及其容量。15151443主存地址緩存地址目錄表區(qū)號(hào)區(qū)內(nèi)塊號(hào)塊內(nèi)地址14430器存塊號(hào)塊內(nèi)地址510主存區(qū)號(hào)有敕位容量：與緩沖塊數(shù)量相同即211=2048(或32Kz16=2048)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ū)中的某一塊只能存入

7、緩存的同組號(hào)的空間內(nèi)，但組內(nèi)各塊地址之間則可以任意存放，即從主存的組到Cache的組之間采用直接映象方式；在兩個(gè)對(duì)應(yīng)的組內(nèi)部采用全相聯(lián)映象方式。主存儲(chǔ)器圖2.36蛆相聯(lián)地址映象區(qū)號(hào)E組號(hào)G組內(nèi)塊號(hào)B塊內(nèi)地址W|主存地址V1QQ出萬g組內(nèi)塊號(hào)卜塊內(nèi)地址WCache地址不等F相聯(lián)比較一相等1A-相聯(lián)比較（Gd個(gè)塊）區(qū)號(hào)E,組內(nèi)坎號(hào)B組內(nèi)塊號(hào)b塊表圖237組相聯(lián)映象的地址轉(zhuǎn)換圖2.3.6示出了組相聯(lián)的映象關(guān)系，圖中緩存共分Cg個(gè)組，每組包含有Gb塊；主存是緩存的Me倍，所以共分有Me個(gè)區(qū),每個(gè)區(qū)有Cg組，每組有Gb塊。那么，主存地址格式中應(yīng)包含4個(gè)字段：區(qū)號(hào)、區(qū)內(nèi)組號(hào)、組內(nèi)塊號(hào)和塊內(nèi)地址。而緩存中包

8、含3個(gè)字段：組號(hào)、組內(nèi)塊號(hào)、塊內(nèi)地址。主存地址與緩存地址的轉(zhuǎn)換有兩部分，組地址是按直接映象方式，按地址進(jìn)行訪問，而塊地址是采用全相聯(lián)方式，按內(nèi)容訪問。組相聯(lián)的地址轉(zhuǎn)換部件也是采用相關(guān)存儲(chǔ)器實(shí)現(xiàn)，見圖2.3.7o相關(guān)存儲(chǔ)器中每個(gè)單元包含有：主存地址中的區(qū)號(hào)E與組內(nèi)塊號(hào)B,兩者結(jié)合在一起，其對(duì)應(yīng)的字段是緩存塊地址bo相關(guān)存儲(chǔ)器的容量，應(yīng)與緩存的塊數(shù)相同。當(dāng)進(jìn)行數(shù)據(jù)訪問時(shí)，先根據(jù)組號(hào)，在目錄表中找到該組所包含的各塊的目錄，然后將被訪數(shù)據(jù)的主存區(qū)號(hào)與組內(nèi)塊號(hào)，與本組內(nèi)各塊的目錄同時(shí)進(jìn)行比較。如果比較相等，而且有效位為“1則命中?？蓪⑵鋵?duì)應(yīng)的緩存塊地址b送到緩存地址寄存器的塊地址字段，與組號(hào)及塊內(nèi)地址組

9、裝即形成緩存地址。如果比較不相等，說明沒命中，所訪問的數(shù)據(jù)塊尚沒有進(jìn)入緩存，則進(jìn)行組內(nèi)替換；如果有效位為0,則說明緩存的該塊尚未利用，或是原來數(shù)據(jù)作廢，可重新調(diào)入新塊。優(yōu)點(diǎn)：塊的沖突概率比較低，塊的利用率大幅度提高，塊失效率明顯降低。缺點(diǎn)：實(shí)現(xiàn)難度和造價(jià)要比直接映象方式高。2.3.3 替換策略根據(jù)程序局部性規(guī)律可知：程序在運(yùn)行中，總是頻繁地使用那些最近被使用過的指令和數(shù)據(jù)。這就提供了替換策略的理論依據(jù)。綜合命中率、實(shí)現(xiàn)的難易及速度的快慢各種因素，替換策略可有隨機(jī)法、先進(jìn)先出法、最近最少使用法等。.隨機(jī)法（RAND法）隨機(jī)法是隨機(jī)地確定替換的存儲(chǔ)塊。設(shè)置一個(gè)隨機(jī)數(shù)產(chǎn)生器，依據(jù)所產(chǎn)生的隨機(jī)數(shù)，確定

10、替換塊。這種方法簡單、易于實(shí)現(xiàn)，但命中率比較低。.先進(jìn)先出法（FIFO法）先進(jìn)先出法是選擇那個(gè)最先調(diào)入的那個(gè)塊進(jìn)行替換。當(dāng)最先調(diào)入并被多次命中的塊，很可能被優(yōu)先替換，因而不符合局部性規(guī)律。這種方法的命中率比隨機(jī)法好些，但還不滿足要求。先進(jìn)先出方法易于實(shí)現(xiàn)，例如Solar16/65機(jī)Cache采用組相聯(lián)方式，每組4塊，每塊都設(shè)定一個(gè)兩位的計(jì)數(shù)器，當(dāng)某塊被裝入或被替換時(shí)該塊的計(jì)數(shù)器清為0,而同組的其它各塊的計(jì)數(shù)器均加1,當(dāng)需要替換時(shí)就選擇計(jì)數(shù)值最大的塊被替換掉。.最近最少使用法（LRU法）LRU法是依據(jù)各塊使用的情況，總是選擇那個(gè)最近最少使用的塊被替換。這種方法比較好地反映了程序局部性規(guī)律。實(shí)現(xiàn)L

11、RU策略的方法有多種。下面簡單介紹計(jì)數(shù)器法、寄存器棧法及硬件邏輯比較對(duì)法的設(shè)計(jì)思路。計(jì)數(shù)器方法：緩存的每一塊都設(shè)置一個(gè)計(jì)數(shù)器，計(jì)數(shù)器的操作規(guī)則是：(1)被調(diào)入或者被替換的塊，其計(jì)數(shù)器清“0”，而其它的計(jì)數(shù)器則加“1”。(2)當(dāng)訪問命中時(shí)，所有塊的計(jì)數(shù)值與命中塊的計(jì)數(shù)值要進(jìn)行比較，如果計(jì)數(shù)值小于命中塊的計(jì)數(shù)值，則該塊的計(jì)數(shù)值加“1”;如果塊的計(jì)數(shù)值大于命中塊的計(jì)數(shù)值，則數(shù)值不變。最后將命中塊的計(jì)數(shù)器清為0。(3)需要替換時(shí)，則選擇計(jì)數(shù)值最大的塊被替換。例如舊M370/65機(jī)的Cache用組相聯(lián)方式，每組4塊，每一塊設(shè)置一個(gè)2位的計(jì)數(shù)器，其工作狀態(tài)如表2.3.1。表2.3.1計(jì)數(shù)器法實(shí)現(xiàn)LRU策略

12、主存塊地址塊4塊2塊3塊5塊號(hào)計(jì)數(shù)器塊毛;計(jì)數(shù)器塊號(hào)計(jì)數(shù)器塊號(hào)計(jì)數(shù)器Cache塊0110111111500Cache塊1301310300301Cache塊2400401410411Cache塊3空XX200201210操作起始狀態(tài)調(diào)入命中替換寄存器棧法：設(shè)置一個(gè)寄存器棧，其容量為Cache中替換時(shí)參與選擇的塊數(shù)。如在組相聯(lián)方式中，則是同組內(nèi)的塊數(shù)。堆棧由棧頂?shù)綏５滓来斡涗浿鞔鏀?shù)據(jù)存入緩存的塊號(hào)，現(xiàn)以一組內(nèi)4塊為例說明其工作情況，如表2.3.2所示，表中14為緩存中的一組的4個(gè)塊號(hào)。2.3.4 Cache的一致性問題Cache的內(nèi)容是主存內(nèi)容的一部分，是主存的副本，內(nèi)容應(yīng)該與主存一致。由于:CPU寫Cache,沒有立即寫主存；I/O處理機(jī)或I/O設(shè)備寫主存。從而造成Cache與主存內(nèi)容的不一致，如圖2.3.8所示(a)CPU寫Cache(b)I/O寫主存圖工ISCache與主存不一致的兩種情況對(duì)Cac