現(xiàn)代計(jì)算機(jī)系統(tǒng)以存儲器為中心3.1存儲系統(tǒng)原理3.2虛擬存

1、現(xiàn)代計(jì)算機(jī)系統(tǒng)以存儲器為中心現(xiàn)代計(jì)算機(jī)系統(tǒng)以存儲器為中心 3.1 存儲系統(tǒng)原理存儲系統(tǒng)原理 3.2 虛擬存儲器虛擬存儲器 3.3 高速緩沖存儲器高速緩沖存儲器(Cache) 3.4 三級存儲系統(tǒng)三級存儲系統(tǒng)第第3章章 存儲系統(tǒng)存儲系統(tǒng) 3.1 3.1 存儲系統(tǒng)原理存儲系統(tǒng)原理3.1.1 存儲系統(tǒng)的定義存儲系統(tǒng)的定義3.1.2 存儲系統(tǒng)的層次結(jié)構(gòu)存儲系統(tǒng)的層次結(jié)構(gòu)3.1.3 存儲系統(tǒng)的頻帶平衡存儲系統(tǒng)的頻帶平衡3.1.4 并行訪問存儲器并行訪問存儲器 3.1.5 交叉訪問存儲器交叉訪問存儲器 3.1.6 無沖突訪問存儲器無沖突訪問存儲器3.1.1 3.1.1 存儲系統(tǒng)的定義存儲系統(tǒng)的定義 在一臺

2、計(jì)算機(jī)中，通常有多種存儲器在一臺計(jì)算機(jī)中，通常有多種存儲器種類：種類：主存儲器、主存儲器、Cache、通用寄存器、緩沖、通用寄存器、緩沖存儲器、磁盤存儲器、磁帶存儲器、光盤存存儲器、磁盤存儲器、磁帶存儲器、光盤存儲器等儲器等材料工藝：材料工藝：ECL、TTL、MOS、磁表面、激、磁表面、激光，光，SRAM，DRAM訪問方式：訪問方式：隨機(jī)訪問、直接譯碼、先進(jìn)先出、隨機(jī)訪問、直接譯碼、先進(jìn)先出、 相聯(lián)訪問、相聯(lián)訪問、 塊傳送、文件組塊傳送、文件組 存儲器的主要性能：存儲器的主要性能：速度、容量、價格速度、容量、價格 速度速度用存儲器的訪問周期、讀出時間、頻帶寬度等表示。 容量容量用字節(jié)B、千字節(jié)

3、KB、兆字節(jié)MB和千兆字節(jié)GB等單位表示。 價格價格用單位容量的價格表示，例如：$C/bit。 組成存儲系統(tǒng)的關(guān)鍵：組成存儲系統(tǒng)的關(guān)鍵：把速度、容量和價格把速度、容量和價格不同的多個物理存儲器組織成一個存儲器，這不同的多個物理存儲器組織成一個存儲器，這個存儲器的速度最快，存儲容量最大，單位容個存儲器的速度最快，存儲容量最大，單位容量的價格最便宜。量的價格最便宜。1. 1. 存儲系統(tǒng)的定義存儲系統(tǒng)的定義 兩個或兩個以上速度、容量和價格各不相同的兩個或兩個以上速度、容量和價格各不相同的存儲器用硬件、軟件、或軟件與硬件相結(jié)合的方法存儲器用硬件、軟件、或軟件與硬件相結(jié)合的方法連接起來成為一個存儲系統(tǒng)。

4、這個存儲系統(tǒng)對應(yīng)用連接起來成為一個存儲系統(tǒng)。這個存儲系統(tǒng)對應(yīng)用程序員是透明的，并且，從應(yīng)用程序員看，它是一程序員是透明的，并且，從應(yīng)用程序員看，它是一個存儲器，這個存儲器的速度接近速度最快的那個個存儲器，這個存儲器的速度接近速度最快的那個存儲器，存儲容量與容量最大的那個存儲器相等，存儲器，存儲容量與容量最大的那個存儲器相等，單位容量的價格接近最便宜的那個存儲器。單位容量的價格接近最便宜的那個存儲器。虛擬存儲器系統(tǒng)：對應(yīng)用程序員透明虛擬存儲器系統(tǒng)：對應(yīng)用程序員透明Cache存儲系統(tǒng)：對系統(tǒng)程序員以上均透明存儲系統(tǒng)：對系統(tǒng)程序員以上均透明 從從外外部部看看 T Tm mi in n（T T1 1，

5、T T2 2，T Tn n） ，用用存存儲儲周周期期表表示示 S Sm ma ax x（S S1 1，S S2 2，S Sn n） ，用用M MB B或或G GB B表表示示 C Cm mi in n（C C1 1，C C2 2，C Cn n） ，用用每每位位的的價價格格表表示示1 1( (T T1 1, ,S S1 1, ,C C1 1) )2 2( (T T2 2, ,S S2 2, ,C C2 2) )n n( (T Tn n, ,S Sn n, ,C Cn n) )由多個存儲器構(gòu)成的存儲系統(tǒng)由多個存儲器構(gòu)成的存儲系統(tǒng) 系系 統(tǒng)統(tǒng) 程程 序序 員員 看看 ： 速速 度度 接接 近近 C

6、Ca ac ch he e 的的 速速 度度 ， 存存 儲儲 容容 量量 是是 主主 存存 的的 容容 量量 ， 每每 位位 價價 格格 接接 近近 主主 存存 儲儲 器器 。C Ca ac ch he e 存存 儲儲 系系 統(tǒng)統(tǒng)C Ca ac ch he e主主 存存 儲儲 器器 在一般計(jì)算機(jī)系統(tǒng)中，有兩種存儲系統(tǒng)：在一般計(jì)算機(jī)系統(tǒng)中，有兩種存儲系統(tǒng)：CacheCache存儲系統(tǒng)：由存儲系統(tǒng)：由CacheCache和主存儲器構(gòu)成和主存儲器構(gòu)成 主要目的：提高存儲器速度主要目的：提高存儲器速度 應(yīng)應(yīng)用用程程序序員員看看： 速速度度接接近近主主存存儲儲器器的的速速度度， 存存儲儲容容量量是是虛虛

7、擬擬地地址址空空間間， 每每位位價價格格接接近近磁磁盤盤存存儲儲器器。虛虛擬擬存存儲儲系系統(tǒng)統(tǒng)主主存存儲儲器器磁磁盤盤存存儲儲器器虛擬存儲系統(tǒng)：由主存儲器和硬盤構(gòu)成虛擬存儲系統(tǒng)：由主存儲器和硬盤構(gòu)成 主要目的：擴(kuò)大存儲器容量主要目的：擴(kuò)大存儲器容量2.2.存儲系統(tǒng)的容量存儲系統(tǒng)的容量要求：要求：提供盡可能大的地址空間提供盡可能大的地址空間能夠隨機(jī)訪問能夠隨機(jī)訪問方法有兩種：方法有兩種：只對系統(tǒng)中存儲容量最大的那個存儲器進(jìn)行編址，其他存儲器只在內(nèi)部編址或不編址 CacheCache存儲系統(tǒng)存儲系統(tǒng)另外設(shè)計(jì)一個容量很大的邏輯地址空間，把相關(guān)存儲器都映射這個地址空間中 虛擬存儲系統(tǒng)虛擬存儲系統(tǒng)3.3

8、.存儲系統(tǒng)的價格存儲系統(tǒng)的價格計(jì)算公式：當(dāng)S2S1時，CC2 S2與S1不能相差太大 （S S，C C，T T）由由兩兩個個存存儲儲器器構(gòu)構(gòu)成成的的存存儲儲系系統(tǒng)統(tǒng)M1（S1，C1，T1）M2（S2，C2，T2）CC SC SSS1122124. 4. 存儲系統(tǒng)的速度存儲系統(tǒng)的速度表示方法：表示方法：訪問周期、存取周期、存儲周期、存取時間等命中率定義：命中率定義：在在M1存儲器中訪問到的概率存儲器中訪問到的概率 其中：N1是對M1存儲器的訪問次數(shù) N2是對M2存儲器的訪問次數(shù)訪問周期與命中率的關(guān)系：訪問周期與命中率的關(guān)系： THT1(1H)T2 當(dāng)命中率H1時，TT1HNNN112存儲系統(tǒng)的訪

9、問效率：存儲系統(tǒng)的訪問效率：訪問效率主要與命中率和兩級存儲器的速度之訪問效率主要與命中率和兩級存儲器的速度之比有關(guān)比有關(guān)例例3.13.1：假設(shè)T2T，在命中率H為0.9和0.99兩種情況下，分別計(jì)算存儲系統(tǒng)的訪問效率。解：解：eTTTH TH THHf HTTTT11111122121()()(,)當(dāng)當(dāng)H H0.90.9時，時，e e1 11 1(0.9(0.95(15(10.9)0.9)0.720.72當(dāng)當(dāng)H H0.990.99時，時，e e2 21 1(0.99(0.995(15(10.99)0.99)0.960.96提高存儲系統(tǒng)速度的兩條途徑：提高存儲系統(tǒng)速度的兩條途徑：一是提高命中率一

10、是提高命中率H H，二是兩個存儲器的速度不要相差太大二是兩個存儲器的速度不要相差太大其中：第二條有時做不到(如虛擬存儲器)，這時，只能依靠提高命中率依靠提高命中率例例3.23.2：在虛擬存儲系統(tǒng)中，兩個存儲器的速度相差特別懸殊，例如：T2105 T。如果要使訪問效率到達(dá)e0.9，問需要有多高的命中率？解：解：0.9H90000(1-H)189999.1 H89999計(jì)算得：計(jì)算得： H0.999998888877777 0.9999990 9111 05.()HH5. 采用預(yù)取技術(shù)提高命中率采用預(yù)取技術(shù)提高命中率 方法：方法：不命中時，把不命中時，把M2存儲器中相鄰多個單存儲器中相鄰多個單元組

11、成的一個數(shù)據(jù)塊取出來送入元組成的一個數(shù)據(jù)塊取出來送入M1存儲器中。存儲器中。 計(jì)算公式：計(jì)算公式： 其中：H是采用預(yù)取技術(shù)之后的命中率 H是原來的命中率 n為數(shù)據(jù)塊大小與數(shù)據(jù)重復(fù)使用次數(shù)的乘積HHnn1例例3.33.3：在一個Cache存儲系統(tǒng)中，當(dāng)Cache的塊大小為一個字時，命中率H0.8；假設(shè)數(shù)據(jù)的重復(fù)利用率為5，T25T1。計(jì)算塊大小為個字時，Cache存儲系統(tǒng)的命中率？并分別計(jì)算訪問效率。99. 0201208 . 01 2nnHH0.558 .1/10.8)5(1(0.81e10.8H:Cache訪問效率為：，塊大小為一個字時當(dāng)0.9604. 1/10.99)5(1(0.991e2

12、 0.99H:4Cache2訪問效率為：，個字時塊大小為當(dāng)解：解：n4520， 采用預(yù)取技術(shù)之后，命中率提高到：)2.(.4096140968 .0 )1.(.105) 1 ( 19 .0mmHHH例例3.43.4：在一個虛擬存儲系統(tǒng)中，T2105 T，原來的命中率只有0.8，如果訪問磁盤存儲器的數(shù)據(jù)塊大小為4K字，并要求訪問效率不低于0.9，計(jì)算數(shù)據(jù)在主存儲器中的重復(fù)利用率至少為多少？解：解：假設(shè)數(shù)據(jù)在主存儲器中的重復(fù)利用率為m，根據(jù)前面給出的關(guān)系，有如下方程組：解方程組：解方程組： 由方程(1)得到：0.9H+90000-90000H=1)3.(.1 .8999989999:解這個方程得H

13、次。復(fù)利用率至少為數(shù)據(jù)在主存儲器中的重44mm4096140968 .0 1 .8999989999:)2()3(得到代入把2 . 01 .8999940961 .89999409689999mm82.179996 .409m 證明方法一：證明方法一： 采用預(yù)取技術(shù)之后， 不命中率不命中率(1-H)(1-H)降低倍：降低倍：nnHHnHH111 1因此：即：新的不命中率，新的命中率nH1 證明方法二證明方法二： 在原有命中率的計(jì)算公式中，把訪問次數(shù)擴(kuò)大到n倍。由于采用了預(yù)取技術(shù)，命中次數(shù)為：nN1(n-1)N2,不命中次數(shù)仍為N2，因此新的命中率為：nnHNNnNNnNnNNnNnNNnnNH

14、1)()()()1( 212121121213.1.2 3.1.2 存儲系統(tǒng)的層次結(jié)構(gòu)存儲系統(tǒng)的層次結(jié)構(gòu)多個層次的存儲器多個層次的存儲器： 第第1層：層：Register Files(寄存器堆寄存器堆) 第第2層：層： Buffers(Lookahead)(先行緩沖站先行緩沖站) 第第3層：層： Cache(高速緩沖存儲器高速緩沖存儲器) 第第4層：層： Main Memory(主存儲器主存儲器) 第第5層：層： Online Storage(聯(lián)機(jī)存儲器聯(lián)機(jī)存儲器) 第第6層：層： Off-line Storage(脫機(jī)存儲器脫機(jī)存儲器)用用i表示層數(shù)，表示層數(shù)，則有：工作周期工作周期TiTi

15、+1， 存儲容量：存儲容量：SiSi+1，單位，單位價格：價格：CiCi+1 第第 1 層層 第第 2 層層 第第 3 層層 第第 4 層層 第第 5 層層 第第 6 層層CPU內(nèi)內(nèi)部部通通用用寄寄存存器器堆堆聯(lián)聯(lián)機(jī)機(jī)外外部部存存儲儲器器（磁磁盤盤存存儲儲器器等等）脫脫機(jī)機(jī)外外部部存存儲儲器器（磁磁帶帶，光光盤盤存存儲儲器器等等）指指令令和和數(shù)數(shù)據(jù)據(jù)緩緩沖沖棧棧C Ca ac ch he e（靜靜態(tài)態(tài)隨隨機(jī)機(jī)存存儲儲器器）SRAM）主主存存儲儲器器（動動態(tài)態(tài)隨隨機(jī)機(jī)存存儲儲器器 DRAM）存存儲儲容容量量越越來來越越大大每每位位的的價價格格越越來來越越便便宜宜訪訪問問速速度度越越來來越越快快各

16、級存儲器的主要主要性能特性各級存儲器的主要主要性能特性 CPUCPU與主存儲器的速度差距越來越大與主存儲器的速度差距越來越大 目前相差目前相差兩個數(shù)量級 今后今后CPUCPU與主存儲器的速度差距會更大與主存儲器的速度差距會更大存存儲儲器器層層次次 通通用用寄寄存存器器 緩緩沖沖棧棧 C Ca ac ch he e 主主存存儲儲器器 磁磁盤盤存存儲儲器器 脫脫機(jī)機(jī)存存儲儲器器 存存儲儲周周期期 1 10 0n ns s 1 10 0n ns s 1 10 06 60 0n ns s 6 60 03 30 00 0n ns s 1 10 03 30 0m ms s 2 22 20 0m mi in

17、 n 存存儲儲容容量量 5 51 12 2B B 20002000字字 頁面大小應(yīng)該為頁面大小應(yīng)該為2K2K字。字。10P034 . 01H15Pn時時間間t t1 12 23 34 45 56 67 78 89 91 10 0實(shí)實(shí)際際頁頁地地址址流流P P1 1P P2 2P P1 1P P5 5P P4 4P P1 1P P3 3P P4 4P P2 2P P4 4命命中中次次數(shù)數(shù)1 11 11 11 1* *4 44 44 4* *4 4* *2 22 2先先進(jìn)進(jìn)先先出出算算法法2 22 22 22 2* *1 11 11 11 1* *4 4（F FI IF FO O 算算法法）5 5

18、5 55 5* *3 33 33 33 3* *調(diào)調(diào)入入 調(diào)調(diào)入入 命命中中 調(diào)調(diào)入入 替替換換 替替換換 替替換換 命命中中 替替換換 替替換換2 2 次次1 11 11 11 11 11 11 11 1* *2 22 2最最久久沒沒有有使使用用算算法法2 22 22 2* *4 44 44 4* *4 44 44 4（L LR RU U 算算法法）5 55 5* *5 5* *3 33 33 3* *3 3* *調(diào)調(diào)入入 調(diào)調(diào)入入 命命中中 調(diào)調(diào)入入 替替換換 命命中中 替替換換 命命中中 替替換換 命命中中4 4 次次1 11 11 11 11 11 1* *3 3* *3 3* *3

19、33 3最最優(yōu)優(yōu)替替換換算算法法2 22 22 22 2* *2 22 22 22 22 2（O OP PT T 算算法法）5 5* *4 44 44 44 44 44 4調(diào)調(diào)入入 調(diào)調(diào)入入 命命中中 調(diào)調(diào)入入 替替換換 命命中中 替替換換 命命中中 命命中中 命命中中5 5 次次三三種種頁頁面面替替換換算算法法對對同同一一個個頁頁地地址址流流的的調(diào)調(diào)度度過過程程例例3.10：一個循環(huán)程序，依次使用P1，P2，P3， P4頁面，分配給它的主存頁面數(shù)只有2個。在 FIFO和LRU算法中，發(fā)生“顛簸顛簸”現(xiàn)象。時時間間 t t1 12 23 34 45 56 67 78 8實(shí)實(shí)際際頁頁地地址址流流

20、P P1 1P P2 2P P3 3P P4 4P P1 1P P2 2P P3 3P P4 4命命中中次次數(shù)數(shù)1 11 11 1* *4 44 44 4* *3 33 3先先進(jìn)進(jìn)先先出出算算法法2 22 22 2* *1 11 11 1* *4 4（F FI IF FO O 算算法法）3 33 33 3* *2 22 22 2* *調(diào)調(diào)入入調(diào)調(diào)入入調(diào)調(diào)入入替替換換替替換換替替換換替替換換替替換換0 0 次次1 11 11 1* *4 44 44 4* *3 33 3最最久久沒沒有有使使用用算算法法2 22 22 2* *1 11 11 1* *4 4（L LR RU U 算算法法）3 33

21、33 3* *2 22 22 2* *調(diào)調(diào)入入調(diào)調(diào)入入調(diào)調(diào)入入替替換換替替換換替替換換替替換換替替換換0 0 次次1 11 11 11 11 1* *1 11 11 1最最優(yōu)優(yōu)替替換換算算法法2 22 22 22 22 2* *3 3* *3 3（O OP PT T 算算法法）3 3* *4 4* *4 44 44 44 4* *調(diào)調(diào)入入調(diào)調(diào)入入調(diào)調(diào)入入替替換換命命中中命命中中替替換換命命中中3 3 次次5. 5. 堆棧型替換算法堆棧型替換算法 定義：定義：對任意一個程序的頁地址流作兩次主對任意一個程序的頁地址流作兩次主存頁面數(shù)分配，分別分配存頁面數(shù)分配，分別分配 m 個主存頁面和個主存頁面和

22、 n 個個主存頁面，并且有主存頁面，并且有 mn。如果在任何時刻。如果在任何時刻 t，主存頁面數(shù)集合主存頁面數(shù)集合 Bt 都滿足關(guān)系：都滿足關(guān)系： Bt（m） Bt（n），），則這類算法稱為堆棧型替換算法。則這類算法稱為堆棧型替換算法。 堆棧型算法的基本特點(diǎn)是：堆棧型算法的基本特點(diǎn)是： 隨著分配給程序的主存頁面數(shù)增加，主存的隨著分配給程序的主存頁面數(shù)增加，主存的命中率也提高，至少不下降。命中率也提高，至少不下降。時時間間t t1 12 23 34 45 56 67 78 89 91 10 01 11 11 12 2實(shí)實(shí)際際頁頁地地址址流流P P1 1P P2 2P P3 3P P4 4P P1

23、 1P P2 2P P5 5P P1 1P P2 2P P3 3P P4 4P P5 5命命中中次次數(shù)數(shù)1 11 11 1* *4 44 44 4* *5 55 55 55 55 5* *5 5* *主主存存頁頁面面數(shù)數(shù)2 22 22 2* *1 11 11 1* *1 1* *1 1* *3 33 33 3N N3 33 33 33 3* *2 22 22 22 22 2* *4 44 4調(diào)調(diào)入入調(diào)調(diào)入入調(diào)調(diào)入入替替換換替替換換替替換換替替換換命命中中命命中中替替換換替替換換命命中中3 3次次1 11 11 11 11 1* *1 1* *5 55 55 55 5* *4 44 4主主存存頁

24、頁面面數(shù)數(shù)2 22 22 22 22 2* *2 2* *1 11 11 11 1* *5 5N N4 43 33 33 33 33 33 3* *2 22 22 22 2* *4 44 44 44 44 44 4* *3 33 33 3調(diào)調(diào)入入調(diào)調(diào)入入調(diào)調(diào)入入調(diào)調(diào)入入命命中中命命中中替替換換替替換換替替換換替替換換替替換換替替換換2 2次次F FI IF FO O算算法法在在主主存存頁頁面面數(shù)數(shù)增增加加時時命命中中率率反反而而下下降降3.2.5 3.2.5 提高主存命中率的方法提高主存命中率的方法影響主存命中率的主要因素：影響主存命中率的主要因素：(1)程序在執(zhí)行過程中的頁地址流分布情況。(

25、2)(2)所采用的頁面替換算法。所采用的頁面替換算法。(3)(3)頁面大小。頁面大小。(4)(4)主存儲器的容量主存儲器的容量(5)(5)所采用的頁面調(diào)度算法所采用的頁面調(diào)度算法 以下，對后三個因素進(jìn)行分析。以下，對后三個因素進(jìn)行分析。1.1.頁面大小與命中率的關(guān)系頁面大小與命中率的關(guān)系 頁面大小為某個值時，命中率達(dá)到最大。頁面大小為某個值時，命中率達(dá)到最大。頁面大小與命中率關(guān)系的解釋：頁面大小與命中率關(guān)系的解釋： 假設(shè)At和At+1是相鄰兩次訪問主存的邏輯地址， dAtAt+1。如果如果SpSp，隨著，隨著SpSp增大，增大，A At 和和 A At+1在同一頁在同一頁面的可能性增加，即隨著

26、面的可能性增加，即隨著SpSp的增大而提高。的增大而提高。如果如果SpSp，A At和和A At+1一定不在同一個頁面內(nèi)。一定不在同一個頁面內(nèi)。隨著隨著SpSp增大，主存頁面數(shù)減少，頁面替換更增大，主存頁面數(shù)減少，頁面替換更加頻繁。隨著加頻繁。隨著SpSp的增大而降低。的增大而降低。當(dāng)Sp比較小的時候，前一種情況是主要的，隨著Sp的增大而提高。當(dāng)Sp達(dá)到某一個最大值之后，后一種情況成為主要的，隨著Sp的增大而降低。當(dāng)頁面增大時，造 成的浪費(fèi)也要增加當(dāng)頁面減小時，頁 表和頁面表在主存 儲器中所占的比例 將增加頁面大小頁面大小 SP命中率命中率1S2 S2. 2. 主存容量與命中率的關(guān)系主存容量與

27、命中率的關(guān)系 主存命中率主存命中率H H隨著分配給該程序的主存容量隨著分配給該程序的主存容量S S的增加而單調(diào)上升。的增加而單調(diào)上升。 在S比較小的時候，H提高得非?？?。隨著S的逐漸增加，H提高的速度逐漸降低。當(dāng)S增加到某一個值之后，H幾乎不再提高。1.0命命中中率率H 主存容量 S3. 3. 頁面調(diào)度方式與命中率的關(guān)系頁面調(diào)度方式與命中率的關(guān)系 請求式：請求式：當(dāng)使用到的時候，再調(diào)入主存 預(yù)取式：預(yù)取式：在程序重新開始運(yùn)行之前，把上次在程序重新開始運(yùn)行之前，把上次 停止運(yùn)行前一段時間內(nèi)用到的頁面先調(diào)入到停止運(yùn)行前一段時間內(nèi)用到的頁面先調(diào)入到 主存儲器，然后才開始運(yùn)行程序。主存儲器，然后才開始

28、運(yùn)行程序。 預(yù)取式的主要優(yōu)點(diǎn)：預(yù)取式的主要優(yōu)點(diǎn)： 可以避免在程序開始運(yùn)行時，頻繁發(fā)生頁面 失效的情況。 預(yù)取式的主要缺點(diǎn)：預(yù)取式的主要缺點(diǎn)： 如果調(diào)入的頁面用不上，浪費(fèi)了調(diào)入的時間， 占用了主存的資源。3.3 3.3 高速緩沖存儲器高速緩沖存儲器3.3.1 基本工作原理基本工作原理3.3.2 地址映象與變換方法地址映象與變換方法3.3.3 Cache替換算法及其實(shí)現(xiàn)替換算法及其實(shí)現(xiàn)3.3.4 Cache存儲系統(tǒng)的加速比存儲系統(tǒng)的加速比3.3.5 Cache的一致性問題的一致性問題3.3.6 Cache的預(yù)取算法的預(yù)取算法Cache 存儲系統(tǒng)與虛擬存儲系統(tǒng)的比較存儲系統(tǒng)與虛擬存儲系統(tǒng)的比較 存儲

29、系統(tǒng)存儲系統(tǒng) Cache 存儲系統(tǒng)存儲系統(tǒng) 虛擬存儲虛擬存儲系統(tǒng)系統(tǒng) 要達(dá)到的目標(biāo)要達(dá)到的目標(biāo) 提高速度提高速度 擴(kuò)大容量擴(kuò)大容量 實(shí)現(xiàn)方法實(shí)現(xiàn)方法 全部硬件全部硬件 軟件為主軟件為主, 硬件為輔硬件為輔 兩級存儲器速度比兩級存儲器速度比 310 倍倍 105倍倍 頁（塊）大小頁（塊）大小 116 字字 1KB16KB 等效存儲容量等效存儲容量 主存儲器主存儲器 虛擬存儲器虛擬存儲器 透明性透明性 對系統(tǒng)和應(yīng)用程序員對系統(tǒng)和應(yīng)用程序員 僅對應(yīng)用程序員僅對應(yīng)用程序員 不命中時處理方式不命中時處理方式 等待主存儲器等待主存儲器 任務(wù)切換任務(wù)切換 主存儲器地址（來自主存儲器地址（來自 CPU） 塊號

30、塊號 B 塊內(nèi)地址塊內(nèi)地址 W 主存地址主存地址 未命中未命中 主存主存Cache 地址變換地址變換 命中命中 已滿已滿 未滿未滿 塊號塊號 b 塊內(nèi)地址塊內(nèi)地址 w Cache地址地址 Cache 替換策略替換策略 替換塊替換塊 裝入塊裝入塊 Cache 數(shù)據(jù)送數(shù)據(jù)送 CPU（一個字）（一個字） 主存儲器 3.3.1 3.3.1 基本工作原理基本工作原理3.3.2 3.3.2 地址映象與變換方法地址映象與變換方法 地址映象：地址映象： 把主存中的程序按照某種規(guī)則裝入到把主存中的程序按照某種規(guī)則裝入到Cache中，并中，并建立主存地址與建立主存地址與Cache地址之間的對應(yīng)關(guān)系。地址之間的對應(yīng)

31、關(guān)系。 地址變換：地址變換： 當(dāng)程序已經(jīng)裝入到當(dāng)程序已經(jīng)裝入到Cache之后，在程序運(yùn)行過程中，之后，在程序運(yùn)行過程中，把主存地址變換成把主存地址變換成Cache地址。地址。在選取地址映象方法要考慮的主要因素：在選取地址映象方法要考慮的主要因素： 地址變換的硬件實(shí)現(xiàn)容易、速度要快，地址變換的硬件實(shí)現(xiàn)容易、速度要快， 主存空間利用率要高，主存空間利用率要高， 發(fā)生塊沖突的概率要小。發(fā)生塊沖突的概率要小。1. 1. 全相聯(lián)映象及其變換全相聯(lián)映象及其變換 映象規(guī)則：映象規(guī)則：主存的任意主存的任意 一塊可以映象到一塊可以映象到Cache 中的任意一塊。中的任意一塊。（映象關(guān)系有CbMb種）塊塊 0塊塊

32、 1塊塊 0塊塊 1塊塊 i塊塊 Cb-1Cache塊塊 Mb-1主主存存儲儲器器 地址變換規(guī)則地址變換規(guī)則 用硬件實(shí)現(xiàn)非常復(fù)雜用硬件實(shí)現(xiàn)非常復(fù)雜 塊塊號號 B 塊塊內(nèi)內(nèi)地地址址W 主主存存地地址址 Cache 地地址址 塊塊號號 b 塊塊內(nèi)內(nèi)地地址址 w 相相聯(lián)聯(lián)比比較較 命命中中 B b 主主存存塊塊號號 B Cache 塊塊號號 b 有有效效位位 目目錄錄表表（由由相相聯(lián)聯(lián)存存儲儲器器構(gòu)構(gòu)成成，共共 Cb個個字字） 2. 2. 直接映象及其變換直接映象及其變換 映象規(guī)則：映象規(guī)則： 主存儲器中一塊只能映象到主存儲器中一塊只能映象到Cache的一個特的一個特定的塊中。定的塊中。 Cache

33、地址的計(jì)算公式：地址的計(jì)算公式： bB mod Cb 其中：b為Cache塊號， B是主存塊號， Cb是Cache塊數(shù)。 實(shí)際上，Cache地址與主存儲器地址的低位部地址與主存儲器地址的低位部分完全相同。分完全相同。 直接映象方式的地址映象規(guī)則直接映象方式的地址映象規(guī)則 塊塊 0 塊塊 1 區(qū)區(qū) 0 塊塊 Cb-1 塊塊 0 塊塊 Cb 塊塊 1 塊塊 Cb+1 區(qū)區(qū) 1 塊塊 Cb-1 塊塊 2Cb-1 Cache 塊塊 Mb-Cb 塊塊 Mb-Cb+1 區(qū)區(qū) Me-1 塊塊 Mb-1 主主存存儲儲器器 直接映象方式的地址變換過程：直接映象方式的地址變換過程：用主存地址中的塊號用主存地址中的

34、塊號B去訪問區(qū)號存儲器，把去訪問區(qū)號存儲器，把讀出來的區(qū)號與主存地址中的區(qū)號讀出來的區(qū)號與主存地址中的區(qū)號E進(jìn)行比進(jìn)行比較：較：比較結(jié)果相等，有效位為1，則Cache命中，否則該塊已經(jīng)作廢。比較結(jié)果不相等，有效位為1，Cache中的該塊是有用的，否則該塊是空的。 主主存存地地址址 區(qū)區(qū)號號 E 塊塊號號 B 塊塊內(nèi)內(nèi)地地址址W Cache 地地址址 塊塊號號 b 塊塊內(nèi)內(nèi)地地址址 w 塊塊失失效效 相相等等比比較較 比比較較相相等等且且有有效效為為 1 E 1 訪訪問問 Cache 區(qū)區(qū)號號 E（按按地地址址訪訪問問） 有有效效位位 區(qū)區(qū)表表存存儲儲器器 直接映象方式的地址變換規(guī)則直接映象方式

35、的地址變換規(guī)則 提高提高Cache速度的一種方法：速度的一種方法： 把區(qū)號存儲器與把區(qū)號存儲器與Cache合并成一個存儲器合并成一個存儲器 區(qū)區(qū)號號 E 塊塊號號 B 塊塊內(nèi)內(nèi)地地址址W Cache 地地址址 塊塊號號 b 塊塊內(nèi)內(nèi)地地址址 w 送送 CPU 訪訪問問主主存存 相相等等比比較較 相相等等 1/w 選選擇擇 1 E D0 D1 Dw-1 有有效效位位 區(qū)區(qū)號號 E 數(shù)數(shù)據(jù)據(jù) D0 數(shù)數(shù)據(jù)據(jù) D1 數(shù)數(shù)據(jù)據(jù) Dw-1 按按地地址址訪訪問問的的 Cache 2. 2. 直接映象及其變換的優(yōu)缺點(diǎn)直接映象及其變換的優(yōu)缺點(diǎn) 主要優(yōu)點(diǎn)：主要優(yōu)點(diǎn)： 硬件實(shí)現(xiàn)很簡單，不需要相聯(lián)訪問存儲器硬件實(shí)現(xiàn)

36、很簡單，不需要相聯(lián)訪問存儲器 訪問速度也比較快，實(shí)際上不需要進(jìn)行地訪問速度也比較快，實(shí)際上不需要進(jìn)行地址變換址變換 主要缺點(diǎn)：主要缺點(diǎn)： 塊的沖突率比較高。塊的沖突率比較高。3. 3. 組相聯(lián)映象及其變換組相聯(lián)映象及其變換 映象規(guī)則：映象規(guī)則： 主存和主存和Cache按同樣大小劃分成塊和組。按同樣大小劃分成塊和組。 主存和主存和Cache的組之間采用直接映象方式。的組之間采用直接映象方式。 在兩個對應(yīng)的組內(nèi)部采用全相聯(lián)映象方式。在兩個對應(yīng)的組內(nèi)部采用全相聯(lián)映象方式。 組相聯(lián)映象方式的優(yōu)點(diǎn)：組相聯(lián)映象方式的優(yōu)點(diǎn)： 塊的沖突概率比較低，塊的沖突概率比較低， 塊的利用率大幅度提高，塊的利用率大幅度提

37、高， 塊失效率明顯降低。塊失效率明顯降低。 組相聯(lián)映象方式的缺點(diǎn)：組相聯(lián)映象方式的缺點(diǎn)： 實(shí)現(xiàn)難度和造價要比直接映象方式高。實(shí)現(xiàn)難度和造價要比直接映象方式高。 塊塊 0 組組 0 Gb-1 Gb 組組 1 2Gb-1 區(qū)區(qū) 0 塊塊 0 GbCg-Gb 組組 0 組組 Cg-1 Gb-1 Cb-1=GbCg-1 Gb 1 2Gb-1 GbCg(Me-1) Cg(Me-1) GbCg(Me-1)+Gb-1 Cb-Gb=CgGb-Gb GbCg(Me-1)+Gb Cg-1 CgMe-Cg+1 Cb-1=CgGb-1 GbCg(Me-1)+2Gb-1 塊塊 2（ Cb-1） Me-1 Cache M

38、e-Gb=GbCgMe-Gb CgMe-1 Mb-1=GbCgMe-1 主主 存存 儲儲 器器 組組 相相 聯(lián)聯(lián) 映映 象象 方方 式式 組相聯(lián)映象的地址變換過程：組相聯(lián)映象的地址變換過程：用主存地址中的組號用主存地址中的組號G按地址訪問塊表存儲器。按地址訪問塊表存儲器。 把讀出來的一組區(qū)號和塊號與主存地址中的把讀出來的一組區(qū)號和塊號與主存地址中的區(qū)號和塊號進(jìn)行區(qū)號和塊號進(jìn)行相聯(lián)比較相聯(lián)比較。如果有相等的，表示Cache命中；如果全部不相等，表示Cache沒有命中。 區(qū)區(qū)號號 E 組組號號 G 組組內(nèi)內(nèi)塊塊號號 B 塊塊內(nèi)內(nèi)地地址址 W 主主存存地地址址 組組號號 g 組組內(nèi)內(nèi)塊塊號號 b 塊

39、塊內(nèi)內(nèi)地地址址 w Cache 地地址址 不不等等 相相聯(lián)聯(lián)比比較較 相相等等 相相聯(lián)聯(lián)比比較較(Gb個個塊塊) 區(qū)區(qū)號號 E,組組內(nèi)內(nèi)塊塊號號 B 組組內(nèi)內(nèi)塊塊號號 b 塊塊 表表 組相聯(lián)映象的地址變換組相聯(lián)映象的地址變換 提高提高Cache訪問速度的一種方法：訪問速度的一種方法： 用多個相等比較器來代替相聯(lián)訪問用多個相等比較器來代替相聯(lián)訪問區(qū)區(qū)號號 E區(qū)區(qū)內(nèi)內(nèi)組組號號 G組組內(nèi)內(nèi)塊塊號號 B塊塊內(nèi)內(nèi)地地址址 W 主主存存地地址址 塊塊失失效效組組號號 g組組內(nèi)內(nèi)塊塊號號 b塊塊內(nèi)內(nèi)地地址址 w 與與Cache 地地址址或或相相等等比比較較相相等等比比較較相相等等比比較較 E, B beE,

40、 Bb E, B be 塊塊表表(按按地地址址訪訪問問,讀讀出出的的多多個個字字段段進(jìn)進(jìn)行行相相聯(lián)聯(lián)比比較較,e 為為有有效效位位)組相聯(lián)映象方式組相聯(lián)映象方式典型機(jī)器的典型機(jī)器的 Cache 分組情況分組情況 機(jī)器型號機(jī)器型號 Cache 塊數(shù)塊數(shù) Cb 每組的塊數(shù)每組的塊數(shù) Gb Cache 組數(shù)組數(shù) Cg DEC VAX-11/780 1024 2 512 Amdahl 470/V6 512 2 256 Intel i860 D-Cache 256 2 128 Honeywell 66/60 512 4 128 Amdahl 470/V7 2048 4 512 IBM 370/168 1

41、024 8 128 IBM3033 1024 16 64 Motolola 88110 256 2 128 4. 4. 位選擇組相聯(lián)映象及其變換位選擇組相聯(lián)映象及其變換地址映象規(guī)則：地址映象規(guī)則：主存和主存和Cache都按同樣大小分塊，都按同樣大小分塊，Cache在分塊的基礎(chǔ)上再分組，在分塊的基礎(chǔ)上再分組，主存按照主存按照Cache的組容量分區(qū)。的組容量分區(qū)。主存的塊與主存的塊與Cache的組之間采用直接映象方式，的組之間采用直接映象方式，主存中的塊與主存中的塊與Cache中組內(nèi)部的各個塊之間采中組內(nèi)部的各個塊之間采用全相聯(lián)映象方式。用全相聯(lián)映象方式。與組相聯(lián)映象方式比較：與組相聯(lián)映象方式比較

42、： 映象關(guān)系明顯簡單，實(shí)現(xiàn)起來容易。映象關(guān)系明顯簡單，實(shí)現(xiàn)起來容易。 在塊表中存放和參與相聯(lián)比較的只有區(qū)號在塊表中存放和參與相聯(lián)比較的只有區(qū)號E 位選擇組相聯(lián)的地址映象規(guī)則位選擇組相聯(lián)的地址映象規(guī)則 塊塊 0 1 區(qū)區(qū) 0 塊塊 0 組組 0 Cg-1 Gb-1 Cg Gb Cg+1 組組 1 區(qū)區(qū) 1 2Gb-1 2Cg-1 Cb-Gb=CgGb-Gb Cg-1 Cg(Mb-1) Cb-1=CgGb-1 Cg(Mb-1)+1 Cache 區(qū)區(qū) Me-1 Mb-1=CgMe-1 主主存存儲儲器器 區(qū)區(qū)號號 E區(qū)區(qū)內(nèi)內(nèi)塊塊號號 B塊塊內(nèi)內(nèi)地地址址 W 主主存存地地址址 塊塊失失效效組組號號 g組

43、組內(nèi)內(nèi)塊塊號號 b塊塊內(nèi)內(nèi) w 與與Cache 地地址址或或相相等等比比較較相相等等比比較較 相相等等比比較較 E b E b E b區(qū)區(qū)號號E塊塊號號be區(qū)區(qū)號號E塊塊號號be區(qū)區(qū)號號E塊塊號號be塊塊表表(按按地地址址訪訪問問,讀讀出出的的多多個個區(qū)區(qū)號號進(jìn)進(jìn)行行相相聯(lián)聯(lián)比比較較,e 是是有有效效位位) 位選擇組相聯(lián)的地址變換規(guī)則位選擇組相聯(lián)的地址變換規(guī)則5. 5. 段相聯(lián)映象及其變換段相聯(lián)映象及其變換映象規(guī)則：映象規(guī)則： 主存和主存和Cache都按同樣大小分塊和段都按同樣大小分塊和段 段之間采用全相聯(lián)映象方式段之間采用全相聯(lián)映象方式 段內(nèi)部的塊之間采用直接映象方式段內(nèi)部的塊之間采用直接映

44、象方式地址變換過程：地址變換過程：用主存地址中的段號與段表中的主存段號進(jìn)行用主存地址中的段號與段表中的主存段號進(jìn)行相聯(lián)比較相聯(lián)比較如果有相等的，用主存地址的段內(nèi)塊號按地址如果有相等的，用主存地址的段內(nèi)塊號按地址訪問訪問Cache的段號部分。的段號部分。把讀出的段號s與主存地址的段內(nèi)塊號b及塊內(nèi)地址w拼接起來得到Cache地址； 段相聯(lián)映象地址映象規(guī)則段相聯(lián)映象地址映象規(guī)則 塊塊 0 段段 0 Sb-1 塊塊 0 Sb 段段 0 段段 1 Sb-1 2Sb-1 Sb 段段 1 2Sb-1 Cb-Sb=Sb(Cs-1) Cs-1 Cb-1=SbCs-1 Cache Mb-Sb=Sb(Ms-1) M

45、s-1 Mb-1=SbMs-1 主主 存存 儲儲 器器 主主 存存 地地 址址段段 號號 S段段 內(nèi)內(nèi) 塊塊 號號 B塊塊 內(nèi)內(nèi) 地地 址址 W段段 號號 s段段 內(nèi)內(nèi) 塊塊 號號 b塊塊 內(nèi)內(nèi) 地地 址址 wC ache 地地 址址相相 聯(lián)聯(lián) 比比 較較 段段 0 S 按按 地地 址址 訪訪 問問 段段 1s1 主主 存存 段段 號號 SC ache 段段 號號 s有有 效效 位位 Ms-1 段段 表表 （ 按按 地地 址址 和和 相相 聯(lián)聯(lián) 兩兩 種種 訪訪 問問 方方 式式 ）段段相相聯(lián)聯(lián)映映象象地地址址變變換換過過程程段相聯(lián)映象方式的優(yōu)缺點(diǎn)段相聯(lián)映象方式的優(yōu)缺點(diǎn)主要優(yōu)點(diǎn)：主要優(yōu)點(diǎn)： 段

46、表比較簡單，實(shí)現(xiàn)的成本低。段表比較簡單，實(shí)現(xiàn)的成本低。 例如：例如：一個容量為256KB的Cache，分成8個段，每段2048塊，每塊16B。 在段表存儲器中只需要存8個主存地址的段號, 而在塊表中要存儲8204816384個區(qū)號， 兩者相差2000多倍。主要缺點(diǎn)：主要缺點(diǎn)： 當(dāng)發(fā)生段失效時，要把本段內(nèi)已經(jīng)建立起來的所有映象關(guān)系全部撤消。3.3.3 Cache3.3.3 Cache替換算法及其實(shí)現(xiàn)替換算法及其實(shí)現(xiàn)使用的場合使用的場合： 直接映象方式實(shí)際上不需要替換算法直接映象方式實(shí)際上不需要替換算法 全相聯(lián)映象方式的替換算法最復(fù)雜全相聯(lián)映象方式的替換算法最復(fù)雜 主要用于主要用于組相聯(lián)組相聯(lián)、段

47、相聯(lián)等映象方式中、段相聯(lián)等映象方式中要解決的問題：要解決的問題：記錄每次訪問記錄每次訪問Cache的塊號的塊號在訪問過程中，對記錄的塊號進(jìn)行管理在訪問過程中，對記錄的塊號進(jìn)行管理根據(jù)記錄和管理結(jié)果，找出替換的塊號根據(jù)記錄和管理結(jié)果，找出替換的塊號主要特點(diǎn)：主要特點(diǎn)：全部用硬件實(shí)現(xiàn)全部用硬件實(shí)現(xiàn)1. 1. 輪換法及其實(shí)現(xiàn)輪換法及其實(shí)現(xiàn) 用于組相聯(lián)映象方式中，有兩種實(shí)現(xiàn)方法。方法一：每塊一個計(jì)數(shù)器方法一：每塊一個計(jì)數(shù)器在塊表內(nèi)增加一個替換計(jì)數(shù)器字段，在塊表內(nèi)增加一個替換計(jì)數(shù)器字段， 計(jì)數(shù)器的長度與Cache地址中的組內(nèi)塊號字段的長度相同。替換方法及計(jì)數(shù)器的管理規(guī)則：替換方法及計(jì)數(shù)器的管理規(guī)則：新裝

48、入或替換的塊，它的計(jì)數(shù)器清新裝入或替換的塊，它的計(jì)數(shù)器清0，同組其，同組其它塊的計(jì)數(shù)器都加它塊的計(jì)數(shù)器都加“1”。在同組中選擇計(jì)數(shù)器的值最大的塊作為被替換在同組中選擇計(jì)數(shù)器的值最大的塊作為被替換的塊。的塊。例例3.11：Solar-16/65小型機(jī)的Cache采用位選擇組相聯(lián)映象方式。Cache每組的塊數(shù)為4，因此，每塊用一個2位的計(jì)數(shù)器。 序列序列 初始值初始值 裝入塊裝入塊00 裝入塊裝入塊01 裝入塊裝入塊10 裝入塊裝入塊11 替換塊替換塊00 塊塊 00 00 00 01 10 11 00 塊塊 01 00 01 00 01 10 11 塊塊 10 00 01 10 00 01 10

49、 塊塊 11 00 01 10 11 00 01 方法二：每組一個計(jì)數(shù)器方法二：每組一個計(jì)數(shù)器替換規(guī)則和計(jì)數(shù)器的管理：替換規(guī)則和計(jì)數(shù)器的管理： 本組有替換時，計(jì)數(shù)器加本組有替換時，計(jì)數(shù)器加“1”， 計(jì)數(shù)器的值就是要被替換出去的塊號。計(jì)數(shù)器的值就是要被替換出去的塊號。例例3.12：NOVA3機(jī)的Cache采用組相聯(lián)映象方式，Cache每組的塊數(shù)為8，每組設(shè)置一個3位計(jì)數(shù)器。在需要替換時，計(jì)數(shù)器的值加“1”，用計(jì)數(shù)器的值直接作為被替換塊的塊號。輪換法的優(yōu)點(diǎn)：輪換法的優(yōu)點(diǎn)：實(shí)現(xiàn)比較簡單，能夠利用歷史實(shí)現(xiàn)比較簡單，能夠利用歷史上的塊地址流情況上的塊地址流情況輪換法的缺點(diǎn)：輪換法的缺點(diǎn)：沒有利用程序的局

50、部性特點(diǎn)沒有利用程序的局部性特點(diǎn)2. LRU2. LRU算法及其實(shí)現(xiàn)算法及其實(shí)現(xiàn)為每一塊設(shè)置一個計(jì)數(shù)器為每一塊設(shè)置一個計(jì)數(shù)器 計(jì)數(shù)器的長度與塊號字段的長度相同計(jì)數(shù)器的使用及管理規(guī)則：計(jì)數(shù)器的使用及管理規(guī)則：新裝入或替換的塊，計(jì)數(shù)器清新裝入或替換的塊，計(jì)數(shù)器清0，同組中其它，同組中其它塊的計(jì)數(shù)器加塊的計(jì)數(shù)器加1。命中塊的計(jì)數(shù)器清命中塊的計(jì)數(shù)器清0，同組的其它計(jì)數(shù)器中，同組的其它計(jì)數(shù)器中，凡計(jì)數(shù)器的值小于命中塊計(jì)數(shù)器原來值的加凡計(jì)數(shù)器的值小于命中塊計(jì)數(shù)器原來值的加1，其余計(jì)數(shù)器不變。，其余計(jì)數(shù)器不變。需要替換時，在同組的所有計(jì)數(shù)器中選擇計(jì)數(shù)需要替換時，在同組的所有計(jì)數(shù)器中選擇計(jì)數(shù)值最大的計(jì)數(shù)器，它

51、所對應(yīng)的塊被替換。值最大的計(jì)數(shù)器，它所對應(yīng)的塊被替換。LRU算法的優(yōu)缺點(diǎn)算法的優(yōu)缺點(diǎn)主要優(yōu)點(diǎn)：主要優(yōu)點(diǎn)： (1)命中率比較高，命中率比較高， (2)能夠比較正確地利用程序的局部性特點(diǎn)，能夠比較正確地利用程序的局部性特點(diǎn)， (3)充分地利用歷史上塊地址流的分布情況，充分地利用歷史上塊地址流的分布情況， (4)是一種堆棧型算法，隨著組內(nèi)塊數(shù)增加，是一種堆棧型算法，隨著組內(nèi)塊數(shù)增加，命中率單調(diào)上升。命中率單調(diào)上升。主要缺點(diǎn)：主要缺點(diǎn)： 控制邏輯復(fù)雜，控制邏輯復(fù)雜，因?yàn)樵黾恿伺袛嗪吞幚硎欠衩械那闆r。 例例3.13：IBM 370/165機(jī)的Cache采用組相聯(lián)映象方式。每組有4塊，為了實(shí)現(xiàn)LRU替換

52、算法，在塊表中為每一塊設(shè)置一個 2 位的計(jì)數(shù)器。在訪問Cache的過程中，塊的裝入、替換及命中時，計(jì)數(shù)器的工作情況如表：塊塊地地址址流流主主存存塊塊1主主存存塊塊2主主存存塊塊3主主存存塊塊4主主存存塊塊5主主存存塊塊4塊塊號號 計(jì)計(jì)數(shù)數(shù)器器 塊塊號號 計(jì)計(jì)數(shù)數(shù)器器 塊塊號號 計(jì)計(jì)數(shù)數(shù)器器 塊塊號號 計(jì)計(jì)數(shù)數(shù)器器 塊塊號號 計(jì)計(jì)數(shù)數(shù)器器 塊塊號號 計(jì)計(jì)數(shù)數(shù)器器Cache塊塊0100101110111500501Cache塊ache塊塊20110300301310310Cache塊塊3011011400401400裝裝入入裝裝入入裝裝入入裝裝入入替替換換命

53、命中中3. 3. 比較對法比較對法 以三個塊為例，分別稱為塊A、塊B、塊C 表示方法：表示方法：用TAB1表示 B塊比 A 塊更久沒有被訪問過。如果表示塊 C 最久沒有被訪問過： 每次訪問之后要改變觸發(fā)器的狀態(tài)每次訪問之后要改變觸發(fā)器的狀態(tài) 在訪問塊A之后：TAB1，TAC1 在訪問塊B之后：TAB0，TBC1 在訪問塊C之后：TAC0，TBC0ACBCACBCABACBCABLRUTTTTTTTTCBCABLRUACABLRUTTBTTA ALRU BLRUCLRU與門與門與門與門與門與門 0 1TAB 0 1TAC 0 1TBC R S R S R S 訪問訪問 A 訪問訪問 B 訪問訪問

54、 C 每組個塊的比較對法每組個塊的比較對法比較對法硬件需求量計(jì)算：比較對法硬件需求量計(jì)算：需要的觸發(fā)器個數(shù)為：與門個數(shù)為Gb，每個門的輸入端個數(shù)為Gb-1當(dāng)每組的塊數(shù)比較多時當(dāng)每組的塊數(shù)比較多時, 采用分級辦法實(shí)現(xiàn) 實(shí)質(zhì)上是用降低速度來換取節(jié)省器件。例例3.14：IBM 3033機(jī)的Cache，每組的塊數(shù)為16，分3級。從第1級到第3級分別為4、2、2。共需要觸發(fā)器個數(shù)為：64818。如果不分級則需要觸發(fā)器120個。bGbbCGG212() 每每組組塊塊數(shù)數(shù) 3 3 4 4 6 6 8 8 1 16 6 6 64 4 2 25 56 6 觸觸發(fā)發(fā)器器個個數(shù)數(shù) 3 3 6 6 1 15 5 2

55、28 8 1 12 20 0 2 20 01 16 6 3 32 26 64 40 0 與與門門個個數(shù)數(shù) 3 3 4 4 6 6 8 8 1 16 6 6 64 4 2 25 56 6 與與門門輸輸入入端端數(shù)數(shù) 2 2 3 3 5 5 7 7 1 15 5 6 63 3 2 25 55 5 比較對法中每組塊數(shù)與所需硬件的關(guān)系比較對法中每組塊數(shù)與所需硬件的關(guān)系4. 4. 堆棧法堆棧法堆棧法的管理規(guī)則：堆棧法的管理規(guī)則：把本次訪問的塊號與堆棧中保存的所有塊號進(jìn)把本次訪問的塊號與堆棧中保存的所有塊號進(jìn)行相聯(lián)比較。行相聯(lián)比較。如果有相等的，則如果有相等的，則Cache命中。把本次訪問塊號命中。把本次訪

56、問塊號從棧頂壓入，堆棧內(nèi)各單元中的塊號依次往從棧頂壓入，堆棧內(nèi)各單元中的塊號依次往下移，直至與本次訪問的塊號相等的那個單下移，直至與本次訪問的塊號相等的那個單元為止，再往下的單元直止棧底都不變。元為止，再往下的單元直止棧底都不變。如果沒有相等的，則Cache塊失效。本次訪問的塊號從棧頂壓入，堆棧內(nèi)各單元的塊號依次往下移，直至棧底，棧底單元中的塊號被移出堆棧，它就是要被替換的塊號。 本次訪問的塊號本次訪問的塊號 棧頂棧頂 最近訪問過的塊最近訪問過的塊 壓入過程到此為止壓入過程到此為止 與本次訪問的塊號與本次訪問的塊號相等相等 棧底棧底 最久沒有被訪問過最久沒有被訪問過的塊的塊 例如：例如：每組為

57、4塊，則堆棧有4個存儲單元， 每個單元2位。NAIAIANBIBIBNCICIC()()()()()()001100110011 每組每組4塊的堆棧法邏輯圖塊的堆棧法邏輯圖 I0 I1 CP D C A0 1 D C A1 1 NA 與門 D C B0 1 D C B1 1 NB 與門 D C C0 1 D C C1 1 NC 與門 D C D0 1 D C D1 1 D0 D1 堆棧法的主要優(yōu)點(diǎn)：堆棧法的主要優(yōu)點(diǎn)： 塊失效率比較低，因?yàn)樗捎昧藟K失效率比較低，因?yàn)樗捎昧薒RU算法。算法。 硬件實(shí)現(xiàn)相對比較簡單。硬件實(shí)現(xiàn)相對比較簡單。堆棧法的主要缺點(diǎn)：堆棧法的主要缺點(diǎn)： 速度比較低，因?yàn)樗?/p>

58、要進(jìn)行相聯(lián)比較。速度比較低，因?yàn)樗枰M(jìn)行相聯(lián)比較。堆棧法與比較對法所用觸發(fā)器的比例：堆棧法與比較對法所用觸發(fā)器的比例： 其中，Gb是Cache每一組的塊數(shù)。當(dāng)Gb大于8時，堆棧法所用的器件明顯少于比較對法。GGGGbbbb()log122：3.3.4 Cache3.3.4 Cache存儲系統(tǒng)的加速比存儲系統(tǒng)的加速比1. 1. 加速比與命中率的關(guān)系加速比與命中率的關(guān)系Cache存儲系統(tǒng)的加速比SP為： 其中：Tm為主存儲器的訪問周期， Tc為Cache的訪問周期， T為Cache存儲系統(tǒng)的等效訪問周期， H為命中率。提高加速比的最好途徑是提高命中率提高加速比的最好途徑是提高命中率STTTH T

59、H THHTTf HTTpmmcmcmmc()()(,)111 加速比加速比 SP 能夠接近于期望值是能夠接近于期望值是： 加速比加速比SP與命中率與命中率H的關(guān)系的關(guān)系SP期望值期望值1命中率命中率 HSP max=TmTcTTmc2. Cache2. Cache命中率與容量的關(guān)系命中率與容量的關(guān)系 Cache的命中率隨它的容量的增加而提高。的命中率隨它的容量的增加而提高。 關(guān)系曲線可以近似地表示為：容量容量 S命中率命中率 H1SH113. Cache3. Cache命中率與塊大小的關(guān)系命中率與塊大小的關(guān)系 在組相聯(lián)方式中在組相聯(lián)方式中, 塊大小對命中率非常敏感塊大小對命中率非常敏感 塊很

60、小時，命中率很低。 隨著塊大小增加命中率也增加, 有一個極大值有一個極大值 當(dāng)塊非常大時, 進(jìn)入Cache中的數(shù)據(jù)可能無用 當(dāng)塊大小等于Cache容量時, 命中率將趨近零4. Cache4. Cache命中率與組數(shù)的關(guān)系命中率與組數(shù)的關(guān)系 在組相聯(lián)方式中在組相聯(lián)方式中, 組數(shù)對命中率的影響很明顯組數(shù)對命中率的影響很明顯 隨著組數(shù)的增加，Cache的命中率要降低。 當(dāng)組數(shù)不太大時(小于512), 命中率的降低很少 當(dāng)組數(shù)超過一定數(shù)量時, 命中率的下降非常快 Cache命中率與塊大小的關(guān)系命中率與塊大小的關(guān)系塊大小命中率 H1初始 最 佳3.3.5 Cache3.3.5 Cache的一致性的一致性