計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)第5章存儲(chǔ)系統(tǒng).ppt

,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),第五章 存儲(chǔ)系統(tǒng),5.1 存儲(chǔ)系統(tǒng)介紹,存儲(chǔ)系統(tǒng) 指計(jì)算機(jī)中由存放程序和數(shù)據(jù)的各種存儲(chǔ)設(shè)備、控制部件及管理信息調(diào)度的設(shè)備（硬件）和算法（軟件）所組成的系統(tǒng)。 計(jì)算機(jī)系統(tǒng)中，一般使用具有層次結(jié)構(gòu)的存儲(chǔ)系統(tǒng)，主要可分為三個(gè)存儲(chǔ)層面：高速緩沖存儲(chǔ)器、主存儲(chǔ)器和輔助存儲(chǔ)器。 高速緩沖存儲(chǔ)器主要用于改善主存儲(chǔ)器與中央處理器（CPU）的速度匹配問題，而輔助存儲(chǔ)器則主要用于擴(kuò)大計(jì)算機(jī)系統(tǒng)的存儲(chǔ)空間。,5.1.1 存儲(chǔ)系統(tǒng)的層次結(jié)構(gòu),層次存儲(chǔ)系統(tǒng)是指把各種不同存儲(chǔ)容量、存取速度、訪問方式和單位存儲(chǔ)價(jià)格的存儲(chǔ)器，按照一定的層次結(jié)構(gòu)組成多層存儲(chǔ)器，并通過管理軟件和輔助硬件有機(jī)組合成統(tǒng)一的存儲(chǔ)體系，使計(jì)算機(jī)系統(tǒng)中使用到的各種程序和數(shù)據(jù)層次的分布到各個(gè)存儲(chǔ)器中。,圖5-1 主/輔存結(jié)構(gòu),5.1.1 存儲(chǔ)系統(tǒng)的定義,在一臺(tái)計(jì)算機(jī)中，通常有多種存儲(chǔ)器 種類：主存儲(chǔ)器、Cache、通用寄存器、緩沖存儲(chǔ)器、磁盤存儲(chǔ)器、磁帶存儲(chǔ)器、光盤存儲(chǔ)器等 材料工藝：ECL、TTL、MOS、磁表面、激光，SRAM，DRAM 訪問方式：隨機(jī)訪問、直接譯碼、先進(jìn)先出、 相聯(lián)訪問、 塊傳送、文件組,存儲(chǔ)器的主要性能：速度、容量、價(jià)格 速度用存儲(chǔ)器的訪問周期、讀出時(shí)間、頻帶寬度等表示。 容量用字節(jié)B、千字節(jié)KB、兆字節(jié)MB和千兆字節(jié)GB等單位表示。 價(jià)格用單位容量的價(jià)格表示，例如：$C/bit。 組成存儲(chǔ)系統(tǒng)的關(guān)鍵：把速度、容量和價(jià)格不同的多個(gè)物理存儲(chǔ)器組織成一個(gè)存儲(chǔ)器，這個(gè)存儲(chǔ)器的速度最快，存儲(chǔ)容量最大，單位容量的價(jià)格最便宜。,1. 存儲(chǔ)系統(tǒng)的定義 兩個(gè)或兩個(gè)以上速度、容量和價(jià)格各不相同的存儲(chǔ)器用硬件、軟件、或軟件與硬件相結(jié)合的方法連接起來成為一個(gè)存儲(chǔ)系統(tǒng)。這個(gè)存儲(chǔ)系統(tǒng)對(duì)應(yīng)用程序員是透明的，并且，從應(yīng)用程序員看，它是一個(gè)存儲(chǔ)器，這個(gè)存儲(chǔ)器的速度接近速度最快的那個(gè)存儲(chǔ)器，存儲(chǔ)容量與容量最大的那個(gè)存儲(chǔ)器相等，單位容量的價(jià)格接近最便宜的那個(gè)存儲(chǔ)器。 虛擬存儲(chǔ)器系統(tǒng)：對(duì)應(yīng)用程序員透明（通過操作系統(tǒng)的存儲(chǔ)管理系統(tǒng)調(diào)度） Cache存儲(chǔ)系統(tǒng)：對(duì)系統(tǒng)程序員及以上均透明（全部用硬件調(diào)度）,由多個(gè)存儲(chǔ)器構(gòu)成的存儲(chǔ)系統(tǒng),在一般計(jì)算機(jī)系統(tǒng)中，有兩種存儲(chǔ)系統(tǒng)： Cache存儲(chǔ)系統(tǒng)：由Cache和主存儲(chǔ)器構(gòu)成 主要目的：提高存儲(chǔ)器速度,虛擬存儲(chǔ)系統(tǒng)：由主存儲(chǔ)器和硬盤構(gòu)成 主要目的：擴(kuò)大存儲(chǔ)器容量,2.存儲(chǔ)系統(tǒng)的容量 對(duì)存儲(chǔ)系統(tǒng)進(jìn)行編址的要求： 提供盡可能大的地址空間 能夠隨機(jī)訪問 方法有兩種： 只對(duì)系統(tǒng)中存儲(chǔ)容量最大的那個(gè)存儲(chǔ)器進(jìn)行編址，其他存儲(chǔ)器只在內(nèi)部編址或不編址 Cache存儲(chǔ)系統(tǒng) 另外設(shè)計(jì)一個(gè)容量很大的邏輯地址空間，把相關(guān)存儲(chǔ)器都映射這個(gè)地址空間中 虛擬存儲(chǔ)系統(tǒng),3.存儲(chǔ)系統(tǒng)的價(jià)格 計(jì)算公式： 當(dāng)S2S1時(shí)，CC2 S2與S1不能相差太大,4. 存儲(chǔ)系統(tǒng)的速度 表示方法：訪問周期、存取周期、存儲(chǔ)周期、存取時(shí)間等 命中率定義：在M1存儲(chǔ)器中訪問到的概率 其中：N1是對(duì)M1存儲(chǔ)器的訪問次數(shù) N2是對(duì)M2存儲(chǔ)器的訪問次數(shù) 訪問周期與命中率的關(guān)系： THT1(1H)T2 當(dāng)命中率H1時(shí)，TT1,存儲(chǔ)系統(tǒng)的訪問效率： 訪問效率主要與命中率和兩級(jí)存儲(chǔ)器的速度之比有關(guān) 例3.1：假設(shè)T2T，在命中率H為0.9和0.99兩種情況下，分別計(jì)算存儲(chǔ)系統(tǒng)的訪問效率。 解：,當(dāng)H0.9時(shí)， e11(0.95(10.9)0.72,當(dāng)H0.99時(shí)， e21(0.995(10.99)0.96,提高存儲(chǔ)系統(tǒng)速度的兩條途徑： 一是提高命中率H， 二是兩個(gè)存儲(chǔ)器的速度不要相差太大 其中：第二條有時(shí)做不到(如虛擬存儲(chǔ)器)，這時(shí)，只能依靠提高命中率 例5.2：在虛擬存儲(chǔ)系統(tǒng)中，兩個(gè)存儲(chǔ)器的速度相差特別懸殊，例如：T2105 T。如果要使訪問效率到達(dá)e0.9，問需要有多高的命中率？,解：,0.9H90000(1-H)1 89999.1 H89999 計(jì)算得： H0.999998888877777 0.999999,5. 采用預(yù)取技術(shù)提高命中率 方法：不命中時(shí)，把M2存儲(chǔ)器中相鄰多個(gè)單元組成的一個(gè)數(shù)據(jù)塊取出來送入M1存儲(chǔ)器中。,計(jì)算公式： 其中：H是采用預(yù)取技術(shù)之后的命中率 H是原來的命中率 n為數(shù)據(jù)塊大小與數(shù)據(jù)重復(fù)使用次數(shù)的乘積,例5.3：在一個(gè)Cache存儲(chǔ)系統(tǒng)中， T25T1。當(dāng)Cache的塊大小為一個(gè)字時(shí)，命中率H0.8。假設(shè)數(shù)據(jù)的重復(fù)利用率為5，Cache塊大小為個(gè)字，Cache存儲(chǔ)系統(tǒng)的命中率？并分別計(jì)算訪問效率。,解：n4520， 采用預(yù)取技術(shù)之后，命中率提高到：,例5.4：在一個(gè)虛擬存儲(chǔ)系統(tǒng)中，T2105 T，原來的命中率只有0.8，如果訪問磁盤存儲(chǔ)器的數(shù)據(jù)塊大小為4K字，并要求訪問效率不低于0.9，計(jì)算數(shù)據(jù)在主存儲(chǔ)器中的重復(fù)利用率至少為多少？ 解：假設(shè)數(shù)據(jù)在主存儲(chǔ)器中的重復(fù)利用率為m，根據(jù)前面給出的關(guān)系，有如下方程組：,解方程組： 由方程(1)得到：0.9H+90000-90000H=1,5.1.2 存儲(chǔ)系統(tǒng)的層次結(jié)構(gòu),多個(gè)層次的存儲(chǔ)器： 第1層：Register Files(寄存器堆) 第2層： Buffers(Lookahead)(先行緩沖站) 第3層： Cache(高速緩沖存儲(chǔ)器) 第4層： Main Memory(主存儲(chǔ)器) 第5層： Online Storage(聯(lián)機(jī)存儲(chǔ)器) 第6層： Off-line Storage(脫機(jī)存儲(chǔ)器) 用i表示層數(shù)，則有：工作周期TiTi+1， 存儲(chǔ)容量：SiSi+1，單位價(jià)格：CiCi+1,各級(jí)存儲(chǔ)器的主要主要性能特性 CPU與主存儲(chǔ)器的速度差距越來越大 目前相差兩個(gè)數(shù)量級(jí) 今后CPU與主存儲(chǔ)器的速度差距會(huì)更大,5.1.3 存儲(chǔ)系統(tǒng)的頻帶平衡,例5.5：Pentium4的指令執(zhí)行速度為8GIPS，CPU取指令8GW/s，訪問數(shù)據(jù)16GW/s，各種輸入輸出設(shè)備訪問存儲(chǔ)器1GW/s，三項(xiàng)相加，要求存儲(chǔ)器的頻帶寬度不低于25GW/s。 如果采用PC133內(nèi)存，主存與CPU速度差188倍 如果采用PC266內(nèi)存，主存與CPU速度差94倍 解決存儲(chǔ)器頻帶平衡方法 (1)多個(gè)存儲(chǔ)器并行工作 (2)設(shè)置各種緩沖存儲(chǔ)器 (3)采用存儲(chǔ)系統(tǒng),5.1.4 并行訪問存儲(chǔ)器,方法：把m字w位的存儲(chǔ)器改變成為m/n字nw位的存儲(chǔ)器 邏輯實(shí)現(xiàn)：把地址碼分成兩個(gè)部分，一部分作為存儲(chǔ)器的地址另一部分負(fù)責(zé)選擇數(shù)據(jù) 主要缺點(diǎn)：訪問沖突大 (1)取指令沖突 (2)讀操作數(shù)沖突 (3)寫數(shù)據(jù)沖突 (4)讀寫沖突,并行訪問存儲(chǔ)器結(jié)構(gòu)框圖,1. 高位交叉訪問存儲(chǔ)器 主要目的：擴(kuò)大存儲(chǔ)器容量 實(shí)現(xiàn)方法：用地址碼的高位部分區(qū)分存儲(chǔ)體號(hào) 參數(shù)計(jì)算方法: m：每個(gè)存儲(chǔ)體的容量， n：總共的存儲(chǔ)體個(gè)數(shù)， j：存儲(chǔ)體的體內(nèi)地址，j0，1，2，.，m-1 k：存儲(chǔ)體的體號(hào)，k0，1，2，.，n-1 存儲(chǔ)器的地址：Amkj 存儲(chǔ)器的體內(nèi)地址：AjA mod m。 存儲(chǔ)器的體號(hào)： Ak,5.1.5 交叉訪問存儲(chǔ)器,高位交叉訪問存儲(chǔ)器結(jié)構(gòu)框圖,2. 低位交叉訪問存儲(chǔ)器 主要目的：提高存儲(chǔ)器訪問速度 實(shí)現(xiàn)方法：用地址碼的低位部分區(qū)分存儲(chǔ)體號(hào) 參數(shù)計(jì)算: m：每個(gè)存儲(chǔ)體的容量， n：總共的存儲(chǔ)體個(gè)數(shù)， j：存儲(chǔ)體的體內(nèi)地址，j0，1，2，.，m-1 k：存儲(chǔ)體的體號(hào)，k0，1，2，.，n-1 存儲(chǔ)器地址A的計(jì)算公式為：Anjk 存儲(chǔ)器的體內(nèi)地址：Aj 存儲(chǔ)器的體號(hào)：AkA mod n,低位交叉訪問存儲(chǔ)器結(jié)構(gòu)框圖,地址是編碼方法： 由8個(gè)存儲(chǔ)體構(gòu)成的低位交叉編址方式,n個(gè)存儲(chǔ)體分時(shí)啟動(dòng) 一種采用流水線方式工作的并行存儲(chǔ)器 每存儲(chǔ)體的啟動(dòng)間隔為：t 其中： Tm為每個(gè)存儲(chǔ)體的訪問周期, n為存儲(chǔ)體個(gè)數(shù)。,訪問沖突 共有n個(gè)存儲(chǔ)體，每個(gè)存儲(chǔ)周期只能取到k個(gè)有效字,其余n-k個(gè)存儲(chǔ)體有沖突。 假設(shè)p(k)是k的概率密度函數(shù)，即p(1)是k1的概率，p(2)是k2的概率，,p(n)是kn的概率。k的平均值為： N是每個(gè)存儲(chǔ)周期能夠訪問到的平均有效字的個(gè)數(shù)。 通常把 N稱為并行存儲(chǔ)器的加速比。,定義轉(zhuǎn)移概率為g，即讀出的是轉(zhuǎn)移指令，且轉(zhuǎn)移成功的概率。這時(shí)有： p(1)g p(2)(1-p(1)g(1-g)g p(3)(1-p(1)-p(2)g(1-g)2g p(k)(1-g)k-1g (k1,2,n1) p(n)(1-g)n-1,g(1-g)g(1-g)2g(1-g)n-2g (1-g)g(1-g)2g(1-g)n-2g (1-g)2g(1-g)n-2g (1-g)n-2g n(1-g)n-1 以上共n行，前n-2行分別為等比級(jí)數(shù) 把n-1行拆分成2項(xiàng),則：1g2(1-g)g3(1-g)2g (n-1)(1-g)n-2gn(1-g)n-1,1-(1-g)n-1 (1-g)-(1-g)n-1 (1-g)2-(1-g)n-1 (1-g)n-2-(1-g)n-1 n(1-g)n-1,1(1-g)(1-g)2(1-g)n-2(1-g)n-1,例5.7：Star-100巨型機(jī)存儲(chǔ)系統(tǒng)采用并行和交叉相結(jié)合的方式工作，有32個(gè)存儲(chǔ)體低位交叉，每次并行讀寫512位，存儲(chǔ)周期為1280ns，處理機(jī)字長(zhǎng)32位，計(jì)算它的速度提高多少倍？和頻帶寬度Bm。,解：因?yàn)椋簄32，w512，Tm1280ns， Bmnw/tm32512b/1280ns 12.8Gb/s1.6GB/s400MW/s 提高512倍 實(shí)際速度的提高要遠(yuǎn)遠(yuǎn)小于這個(gè)數(shù)字,5.1.6 無沖突訪問存儲(chǔ)器,1. 一維數(shù)組(向量)的無沖突訪問存儲(chǔ)器 按連續(xù)地址訪問，沒有沖突， 位移量為2的變址訪問，速度降低一倍，,具體方法： 存儲(chǔ)體的個(gè)數(shù)取質(zhì)數(shù)，且n向量長(zhǎng)度。 原因：變址位移量必然與存儲(chǔ)體個(gè)數(shù)互質(zhì) 例如： Burroughs公司巨型科學(xué)計(jì)算機(jī)BSP 存儲(chǔ)體個(gè)數(shù)為17 向量長(zhǎng)度16 我國研制的銀河巨型向量機(jī) 存儲(chǔ)體的個(gè)數(shù)為37 向量長(zhǎng)度32,2. 二維數(shù)組的無沖突訪問存儲(chǔ)器 要求：一個(gè)nn的二維數(shù)組，按行、列、對(duì)角線和反對(duì)角線訪問，并且在不同的變址位移量情況下，都能實(shí)現(xiàn)無沖突訪問。 順序存儲(chǔ)：按行、對(duì)角線訪問沒有沖突，但按列訪問每次沖突,錯(cuò)位存儲(chǔ)： 按行、按列訪問無沖突， 但按對(duì)角線訪問有沖突,nn二維數(shù)組無沖突訪問存儲(chǔ)方案 ( P Budnik 和 D J Kuck提出 ) ： 并行存儲(chǔ)體的個(gè)數(shù)mn，并且取質(zhì)數(shù)，同時(shí)還要在行、列方向上錯(cuò)開一定的距離存儲(chǔ)數(shù)組元素。 設(shè)同一列相鄰元素在并行存儲(chǔ)器中錯(cuò)開d1個(gè)存儲(chǔ)體存放，同一行相鄰元素在并行存儲(chǔ)器中錯(cuò)開d2個(gè)存儲(chǔ)體存放。當(dāng)m22p1（p為任意自然數(shù)）時(shí)，能夠同時(shí)實(shí)現(xiàn)按行、按列、按對(duì)角線和按反對(duì)角線無沖突訪問的充要條件是：d12P，d21。,例如：44的二維數(shù)組，取并行存儲(chǔ)體的個(gè)數(shù)m5，由關(guān)系式m22P1，解得到p1，計(jì)算得到： d1212 d21,45,nn數(shù)組中的任意一個(gè)元素aij在無沖突并行存儲(chǔ)器中的體號(hào)地址和體內(nèi)地址的計(jì)算公式： 體號(hào)地址：(2P ijk) MOD m 體內(nèi)地址：i 其中：0in1， 0jn1， k是數(shù)組的第一個(gè)元素a00所在體號(hào)地址， m是并行存儲(chǔ)體的個(gè)數(shù)，要求mn且為質(zhì)數(shù)， p是滿足m22P1關(guān)系的任意自然數(shù)。 主要缺點(diǎn)：浪費(fèi)存儲(chǔ)單元 對(duì)于nn數(shù)組,有(m-n) m個(gè)存儲(chǔ)單元浪費(fèi) 主要優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單 列元素順序存儲(chǔ)，行元素按地址取模順序存儲(chǔ),3. 二維數(shù)組的無沖突訪問存儲(chǔ)器(之二) 規(guī)則：對(duì)于任意一個(gè)nn的數(shù)組，如果能夠找到滿足n22P關(guān)系的任意自然數(shù)p，則這個(gè)二維數(shù)組就能夠使用n個(gè)并行存儲(chǔ)體實(shí)現(xiàn)按行、列、對(duì)角線和反對(duì)角線的無沖突訪問。 44數(shù)組用4個(gè)存儲(chǔ)體的無訪問沖突存儲(chǔ)方案,實(shí)現(xiàn)方法： 假設(shè)aij是44數(shù)組中的任意一個(gè)元素，下標(biāo)i和j都可以用兩位二進(jìn)制表示。假設(shè)i和j的高位和低位分別為iH、iL、jH和jL，則aij在無沖突并行存儲(chǔ)器中的體號(hào)地址和體內(nèi)地址如下： 體號(hào)地址：2(iL jH)(iH iL jL) 體內(nèi)地址：j 其中：0i3，0j3 主要優(yōu)點(diǎn)：沒有浪費(fèi)的存儲(chǔ)單元， 主要缺點(diǎn)：在執(zhí)行并行讀和寫操作時(shí)需要借助比較復(fù)雜的對(duì)準(zhǔn)網(wǎng)絡(luò)。,5.2 高速緩沖存儲(chǔ)器Cache,計(jì)算機(jī)系統(tǒng)為改善CPU與主存儲(chǔ)器之間的速度匹配問題，在CPU和主存儲(chǔ)器之間加入一個(gè)高速、小容量的緩沖存儲(chǔ)器Cache，構(gòu)成Cache主存儲(chǔ)器的存儲(chǔ)系統(tǒng)，使得存儲(chǔ)系統(tǒng)對(duì)CPU而言，速度接近于高速緩沖存儲(chǔ)器Cache，存儲(chǔ)容量接近于主存儲(chǔ)器。 Cache存儲(chǔ)器主要由三個(gè)部分組成： (1)Cache存儲(chǔ)器，用于存放由主存儲(chǔ)器調(diào)入的指令與數(shù)據(jù)塊； (2)地址轉(zhuǎn)換部件，用于實(shí)現(xiàn)主存儲(chǔ)器地址到Cache存儲(chǔ)器地址的轉(zhuǎn)換； (3)替換部件，當(dāng)緩存滿時(shí)根據(jù)指定策略進(jìn)行數(shù)據(jù)塊替換，并對(duì)地址轉(zhuǎn)換部件做對(duì)應(yīng)修改。,Cache工作原理,Cache工作原理(續(xù)1),系統(tǒng)工作時(shí)，地址轉(zhuǎn)換部件維護(hù)一個(gè)映射表，用于確定Cache存儲(chǔ)器中是否有所要訪問的塊，以及確定其位置。該映射表中的每一項(xiàng)對(duì)應(yīng)于Cache存儲(chǔ)器的一個(gè)分塊，用于指出當(dāng)前該塊中存放的信息對(duì)應(yīng)于主存儲(chǔ)器的哪個(gè)分塊。 為提高CPU對(duì)Cache存儲(chǔ)器的訪問命中率，Cache存儲(chǔ)器的工作原理是基于程序訪問局部性原理的，它不斷地將與當(dāng)前指令集相關(guān)聯(lián)的一部分后繼指令集從主存儲(chǔ)器讀取到Cache存儲(chǔ)器，以供CPU訪問，從而達(dá)到存儲(chǔ)系統(tǒng)與CPU速度匹配的目的。,5.2.2 地址映象與變換方法,地址映象是將主存儲(chǔ)器中的數(shù)據(jù)分塊按某種規(guī)則裝入Cache存儲(chǔ)器中，并建立主存儲(chǔ)器地址與Cache存儲(chǔ)器地址之間的對(duì)應(yīng)關(guān)系。 地址變換是指當(dāng)主存儲(chǔ)器中的分塊按照地址映象方法裝入Cache存儲(chǔ)器后，在實(shí)際運(yùn)行過程中，主存儲(chǔ)器地址如何轉(zhuǎn)換成為相應(yīng)的Cache存儲(chǔ)器地址。 地址的映象和變換是緊密相關(guān)的，采用什么樣的地址映象方法，就有與這種映象方法相對(duì)應(yīng)的地址變換方法。,5.2.2 地址映象與變換方法,在選取地址映象方法要考慮的主要因素： 地址變換的硬件容易實(shí)現(xiàn)，地址變換的速度要快， Cache空間利用率要高， 發(fā)生塊沖突的概率要小。 一般可分為以下幾種類型： (1)全相聯(lián)映象及其變換方法 (2)直接映象及其變換方法 (3)組相聯(lián)映象及其變換方法,(1)全相聯(lián)映象及其變換方法,全相聯(lián)映象是指主存儲(chǔ)器中的任意分塊可以被放置到Cache存儲(chǔ)器中的任意一個(gè)位置。其中，主存儲(chǔ)器與Cache存儲(chǔ)器的分塊大小相同。,映像規(guī)則,(1)全相聯(lián)映象及其變換方法,主存儲(chǔ)器塊號(hào)與Cache存儲(chǔ)器塊號(hào)的映象關(guān)系存放在一個(gè)用高速緩存實(shí)現(xiàn)的目錄表中，目錄表中的存儲(chǔ)單元由三部分組成：主存儲(chǔ)器塊號(hào)、Cache存儲(chǔ)器塊號(hào)，以及有效位。,(2)直接映象及其變換方法,直接映象是指將主存儲(chǔ)器中的某一分塊在Cache存儲(chǔ)器中都有唯一對(duì)應(yīng)的位置。主存儲(chǔ)器按Cache大小分成若干區(qū)，在區(qū)內(nèi)進(jìn)行分塊，分塊大小與Cache存儲(chǔ)器中分塊大小相等，主存儲(chǔ)器中每個(gè)區(qū)包含分塊的個(gè)數(shù)與Cache存儲(chǔ)器中分塊的個(gè)數(shù)相等。 Cache地址的計(jì)算公式： bB mod Cb 其中：b為Cache塊號(hào)，B是主存塊號(hào)， Cb是Cache塊數(shù)。 實(shí)際上，Cache地址與主存儲(chǔ)器地址的低位完全部分相同,(2)直接映象及其變換方法,地址映像規(guī)則,(2)直接映象及其變換方法,7/16/2019,地址變換過程： 用主存地址中的塊號(hào)B去訪問區(qū)號(hào)存儲(chǔ)器，把讀出來的區(qū)號(hào)與主存地址中的區(qū)號(hào)E進(jìn)行比較 比較結(jié)果相等，有效位為1，則Cache命中，否則該塊已經(jīng)作廢。 比較結(jié)果不相等，有效位為1，Cache中的該塊被其他塊占用，否則該塊是空的。,(2)直接映象及其變換方法,直接映像地址變換規(guī)則,(2)直接映象及其變換方法,提高Cache速度的一種方法： 把區(qū)號(hào)存儲(chǔ)器與Cache合并成一個(gè)存儲(chǔ)器,(2)直接映象及其變換方法,7/16/2019,直接映象及其變換的優(yōu)缺點(diǎn)： 主要優(yōu)點(diǎn)： 硬件實(shí)現(xiàn)很簡(jiǎn)單，不需要相聯(lián)訪問存儲(chǔ)器 訪問速度也比較快，實(shí)際上不需要進(jìn)行地址 變換。 主要缺點(diǎn)： 塊的沖突率比較高。,(3)組相聯(lián)映象及其變換方法,組相聯(lián)映象把主存儲(chǔ)器和Cache按同樣大小劃分成塊，再將主存儲(chǔ)器和Cache按同樣大小劃分成組，每一組由相同的塊數(shù)組成，然后將主存儲(chǔ)器按Cache大小分成區(qū)，主存儲(chǔ)器每個(gè)區(qū)的組數(shù)與Cache的組數(shù)相同。 組相聯(lián)映象在各組之間是直接映象，但組內(nèi)各塊之間是全相聯(lián)映象。,(3)組相聯(lián)映象及其變換方法,映像規(guī)則,(3)組相聯(lián)映象及其變換方法,7/16/2019,地址變換過程： 用主存地址中的組號(hào)G按地址訪問塊表存儲(chǔ)器。把讀出來的一組區(qū)號(hào)和塊號(hào)與主存地址中的區(qū)號(hào)和塊號(hào)進(jìn)行相聯(lián)比較。 如果有相等的，表示Cache命中；否則表示Cache沒有命中。,(3)組相聯(lián)映象及其變換方法(續(xù)1),地址變換規(guī)則,(3)組相聯(lián)映象及其變換方法, 組相聯(lián)映象方式的優(yōu)點(diǎn)： 塊的沖突概率比較低， 塊的利用率大幅度提高， 塊失效率明顯降低。 組相聯(lián)映象方式的缺點(diǎn)： 實(shí)現(xiàn)難度和造價(jià)要比直接映象方式高。,(3)組相聯(lián)映象及其變換方法,7/16/2019,提高Cache訪問速度的一種方法： 把塊表存儲(chǔ)器中一個(gè)相聯(lián)比較的組按塊方向展開存放。 用多個(gè)相等比較器來代替相聯(lián)訪問，加塊查表的速度。,(3)組相聯(lián)映象及其變換方法,7/16/2019,5.2.3 Cache替換算法及實(shí)現(xiàn),當(dāng)CPU讀Cache時(shí)，有兩種可能： (一) 需要的數(shù)據(jù)已在Cache中，那么只需直接訪問Cache； (二)是需要的數(shù)據(jù)尚未裝入Cache，則CPU從主存儲(chǔ)器中讀取信息的同時(shí)，需按所需的映象規(guī)則將該地址所在的那塊存儲(chǔ)內(nèi)容從主存儲(chǔ)器拷貝到Cache中。 對(duì)于第二種情況，若該塊所映象的Cache塊位置已全部被占滿，則必須選擇將Cache中的某一塊替換出去，需要Cache替換算法解決如何選擇被換出塊的問題。,Cache替換算法,隨機(jī)替換算法 隨機(jī)法是Cache替換算法中最簡(jiǎn)單的一種。這種方法是隨機(jī)地選擇可以被替換的一塊進(jìn)行替換。有些系統(tǒng)設(shè)置一個(gè)隨機(jī)數(shù)產(chǎn)生器，依據(jù)所產(chǎn)生的隨機(jī)數(shù)選擇替換塊，進(jìn)行替換。 先進(jìn)先出替換算法(FIFO) 這種策略總是把最先調(diào)入的Cache塊作為被替換的塊替換出去。 最近最少使用替換算法(LRU) LRU法是依據(jù)各塊的使用情況，總是選擇最近最久沒被使用的塊作為被替換的塊進(jìn)行替換。因?yàn)槟壳盀橹棺罹脹]有被訪問的塊，很可能也是將來最少訪問的塊。,Cache替換算法,堆棧替換算法 堆棧替換算法使用棧頂?shù)綏５赘黜?xiàng)的先后次序來記錄Cache中或Cache中同一組內(nèi)各個(gè)塊被訪問的先后順序。棧頂恒存放近期最近被訪問過的塊的塊號(hào)，棧底恒存放近期最久沒有被訪問過的塊的塊號(hào)，即準(zhǔn)備被替換掉的塊的塊號(hào)（LRU堆棧實(shí)現(xiàn)）。 比較對(duì)替換算法 LRU算法用一組硬件的邏輯電路記錄同一組中各個(gè)塊使用的時(shí)間和次數(shù)， 然后按照各個(gè)塊被訪問過的時(shí)間順序排序，從中找出最久沒有被訪問過的塊。用一個(gè)兩態(tài)的觸發(fā)器的狀態(tài)來表示兩個(gè)塊之間的先后順序，再經(jīng)過門電路就可以找到LRU塊。,Cache替換算法,比較對(duì)法 以三個(gè)塊為例，三個(gè)塊分別稱為塊A、B、C 表示方法： 用TAB1表示 B塊比 A 塊更久沒有被訪問過。 如果要表示塊 C 最久沒有被訪問過： 從最近到最遠(yuǎn)分別是：A、B、C 或 B、A、C,Cache替換算法,7/16/2019,即： 每次訪問之后要改變觸發(fā)器的狀態(tài)。 在訪問塊A之后：TAB1，TAC1 在訪問塊B之后：TAB0，TBC1 在訪問塊C之后：TAC0，TBC0,Cache替換算法,7/16/2019,每組個(gè)塊的比較對(duì)法,Cache替換算法,7/16/2019,硬件需求量計(jì)算： 需要的觸發(fā)器個(gè)數(shù)為： 與門的個(gè)數(shù)為Gb個(gè)，每個(gè)與門的輸入端個(gè)數(shù)為Gb-1個(gè), 其中：Gb為每組的塊數(shù)。 當(dāng)每組的塊數(shù)比較多時(shí) 采用分級(jí)的辦法實(shí)現(xiàn)。 實(shí)質(zhì)上是用降低速度來換取節(jié)省器件。,Cache替換算法,7/16/2019,比較對(duì)法中每組數(shù)與所需硬件的關(guān)系,Cache替換算法,7/16/2019,例如：IBM 3033機(jī)的Cache，每組的塊數(shù)為16，分3級(jí)。從第1級(jí)到第3級(jí)分別為4、2、2。共需要觸發(fā)器個(gè)數(shù)為：64818。 如果不分級(jí)則需要觸發(fā)器120個(gè)。,Cache替換算法,7/16/2019,堆棧法的管理規(guī)則： 把本次訪問的塊號(hào)與堆棧中保存的所有塊號(hào)進(jìn)行相聯(lián)比較。 如果有相等的，則Cache命中。把本次訪問的塊號(hào)從棧頂壓入，堆棧內(nèi)各單元中的塊號(hào)依次往下移，直至與本次訪問的塊號(hào)相等的那個(gè)單元為止，再往下的單元直止棧底都不變。,Cache替換算法,7/16/2019,如果沒有相等的，則Cache塊失效。本次訪問的塊號(hào)從棧頂壓入，堆棧內(nèi)各單元的塊號(hào)依次往下移，直至棧底，棧底單元中的塊號(hào)被移出堆棧，它就是要被替換的塊號(hào)。,Cache替換算法,7/16/2019,堆棧法的主要優(yōu)點(diǎn)： 塊失效率比較低，因?yàn)樗捎昧薒RU算法。 硬件實(shí)現(xiàn)相對(duì)比較簡(jiǎn)單。 堆棧法的主要缺點(diǎn)： 速度比較低，因?yàn)樗枰M(jìn)行相聯(lián)比較。,Cache替換算法,各種Cache替換算法的優(yōu)缺點(diǎn) (1)隨機(jī)替換算法： 優(yōu)點(diǎn)是簡(jiǎn)單，容易實(shí)現(xiàn)；缺點(diǎn)是沒有考慮到Cache塊的使用歷史情況，沒有利用程序的局部性特點(diǎn)，從而命中率較低，失效率較高。 (2)FIFO替換算法： 優(yōu)點(diǎn)是由于它不需記錄各個(gè)塊的使用情況，實(shí)現(xiàn)起來也較容易；缺點(diǎn)是雖然考慮到了各塊進(jìn)入Cache的先后順序這一使用“歷史”，但還不能正確地反映程序的局部性特點(diǎn)。 (3) LRU替換算法： LRU算法較好地反映了程序的局部性特點(diǎn)，失效率較低，但LRU算法比較復(fù)雜，硬件實(shí)現(xiàn)較困難，特別是當(dāng)組的大小增加時(shí)，LRU的實(shí)現(xiàn)代價(jià)將越來越高。,5.2.4 cache一致性問題,由于Cache中保存的是主存儲(chǔ)器的一部分副本，則有可能在一段時(shí)間內(nèi)，主存儲(chǔ)器中某單元的內(nèi)容與Cache中對(duì)應(yīng)單元的內(nèi)容出現(xiàn)不一致。 例如： （1）CPU在寫入Cache時(shí)，修改了Cache中某單元的內(nèi)容，而主存儲(chǔ)器中對(duì)于單元的內(nèi)容卻可能沒有改變，還是原來的。此時(shí)，如果I/O處理器或其他處理器要用到主存儲(chǔ)器中的數(shù)據(jù)，則可能會(huì)出現(xiàn)主存儲(chǔ)器內(nèi)容跟不上Cache對(duì)應(yīng)內(nèi)容的變化而造成的數(shù)據(jù)不一致性錯(cuò)誤。 （2）I/O處理機(jī)或其他處理機(jī)已修改了主存儲(chǔ)器某個(gè)單元的內(nèi)容，而Cache中對(duì)于單元的副本內(nèi)容卻可能沒有改變。這時(shí)，如果CPU訪問Cache并讀取數(shù)據(jù)，也可能會(huì)出現(xiàn)Cache內(nèi)容跟不上主存儲(chǔ)器對(duì)于內(nèi)容的變化而產(chǎn)生的不一致性錯(cuò)誤。,5.2.4 cache一致性問題,對(duì)于Cache中的副本與主存儲(chǔ)器中的內(nèi)容能否保持一致，是Cache能否可靠工作的一個(gè)關(guān)鍵問題。要解決這個(gè)問題，首先要選擇合適的Cache更新算法。 對(duì)Cache不一致性問題的解決，主要是需要更新主存儲(chǔ)器內(nèi)容，一般有兩種常用更新算法：,83,(1) 寫直達(dá)法:又稱寫通過法，WT（Write-through） CPU在執(zhí)行寫操作時(shí)，把數(shù)據(jù)同時(shí)寫入Cache和主存。 (2) 寫回法:又稱為抵觸修改法，WB（Write-Back） CPU的數(shù)據(jù)只寫入Cache，不寫入主存。 僅當(dāng)替換時(shí)，才把修改過的Cache塊寫回到主存。,5.2.4 cache一致性問題,84,寫回法與寫直達(dá)法的優(yōu)缺點(diǎn)比較： (1)寫回法較寫直達(dá)法速度要快； (2)在可靠性方面，寫回法不如寫直達(dá)法； (3)寫直達(dá)法的控制較比寫回法簡(jiǎn)單； (4)寫直達(dá)法易于實(shí)現(xiàn)，但硬件實(shí)現(xiàn)代價(jià)相對(duì)較大。,5.2.4 cache一致性問題,85,5.2.4 cache一致性問題,例如：寫操作占總訪存次數(shù)的20，Cache的命中率為99，每塊為4個(gè)字。當(dāng)Cache發(fā)生塊替換時(shí)，有30塊需要寫回到主存，其余的塊因?yàn)闆]有被修改過而不必寫回主存。試比較寫回法與寫直達(dá)法的訪存通信量。則對(duì)于寫直達(dá)法，寫主存次數(shù)占總訪存次數(shù)的20,而對(duì)于寫回法，(199)3041.2。 因此，與主存的通信量，寫回法要比寫直達(dá)法少10多倍。,5.2.4 cache一致性問題,進(jìn)行“寫”操作時(shí)，也可能出現(xiàn)寫不命中。由于“寫”操作并不需要訪問該單元中的所有的數(shù)據(jù)，在出現(xiàn)Cache寫不命中時(shí)，無論寫回法還是寫直達(dá)法，都需要考慮在寫操作的同時(shí)是否將其調(diào)入Cache，一般有兩種選擇： (1)按寫分配法：寫失效時(shí)，除了完成寫入主存儲(chǔ)器外，還把該寫地址單元所在的塊由主存儲(chǔ)器調(diào)入Cache。 (2)不按寫分配法：寫失效時(shí)，只完成寫入主存儲(chǔ)器，而不把該寫地址單元所在的塊從主存儲(chǔ)器調(diào)入Cache。,5.2.5 Cache性能分析,評(píng)價(jià)Cache存儲(chǔ)器，主要是看Cache命中率的高低，命中率主要與下面幾個(gè)因素有關(guān)： (1)程序在執(zhí)行過程中的地址流分布情況，其中地址流的分布情況是由程序本身決定的；可通過編寫適應(yīng)Cache的代碼； (2)當(dāng)發(fā)生Cache塊失效時(shí)，所采用的替換算法； (3)Cache的容量，塊的大小、塊的總數(shù)； (4)采用組相聯(lián)時(shí)組的大小等。,5.2.5 Cache性能分析(續(xù)1),Cache命中率與容量的關(guān)系 Cache的容量越大，則Cache的命中率將越高。,5.2.5 Cache性能分析(續(xù)2),Cache命中率與塊大小的關(guān)系 在采用組相聯(lián)映象方式的Cache中，當(dāng)Cache的容量一定時(shí)，塊的大小也會(huì)影響命中率。,5.2.5 Cache性能分析(續(xù)3),Cache命中率與組數(shù)的關(guān)系 當(dāng)Cache的容量一定時(shí)，分組的數(shù)目對(duì)于Cache命中率的影響也是很明顯的：組數(shù)分得越多，命中率會(huì)下降，命中率會(huì)隨著組數(shù)的增加而下降；當(dāng)組數(shù)不太大時(shí)，命中率降低得相當(dāng)少；當(dāng)組數(shù)超過一定數(shù)量時(shí)，命中率下降非?？?。 Cache系統(tǒng)加速定義：,5.2.5 Cache性能分析(續(xù)4),從Cache系統(tǒng)加速比定義可以看出，Cache系統(tǒng)的加速比與Cache的命中率H和主存儲(chǔ)器訪問周期Tm及Cache訪問周期Tc有關(guān)，而Cache系統(tǒng)中，主存儲(chǔ)器的訪問周期和Cache的訪問周期一般是一定的，所以只要提高Cache的命中率，就可以獲得較高的Cache系統(tǒng)加速比，提高存儲(chǔ)系統(tǒng)的速度。,5.3 Cache性能的優(yōu)化,除加速比定義衡量Cache存儲(chǔ)系統(tǒng)性能外，Cache存儲(chǔ)器的平均訪問時(shí)間是測(cè)評(píng)存儲(chǔ)系統(tǒng)性能的一種更好的指標(biāo)： 平均訪問時(shí)間 = 命中時(shí)間 + 失效率*失效開銷 從平均訪問時(shí)間這一指標(biāo)來看，還可以從3個(gè)方面對(duì)Cache的性能進(jìn)行優(yōu)化： （1）降低Cache失效率 （2）減少失效開銷 （3）減少命中時(shí)間,5.3.1降低Cache失效率的方法,Cache失效的原因分析： (1)強(qiáng)制性失效：對(duì)塊第一次訪問，該塊不在Cache中，需從主存儲(chǔ)器中將該塊調(diào)入Cache中。 (2)容量失效：如果程序執(zhí)行時(shí)，Cache容納不了所需的所有塊，則會(huì)發(fā)生容量失效。當(dāng)某些塊被替換后，可能隨后重新訪問又被調(diào)入。 (3)沖突失效：在組相聯(lián)映象或直接相聯(lián)映象中，如果太多的沖突塊映象到同一組中，產(chǎn)生沖突，則可能會(huì)出現(xiàn)某個(gè)塊剛被替換出去，隨后又重新訪問而被再次調(diào)入。,5.3.1降低Cache失效率的方法(續(xù)1),增加Cache塊大小 Cache命中率和塊大小的關(guān)系：在Cache容量一定時(shí)，當(dāng)塊大小開始增加時(shí)，命中率也開始增加，但當(dāng)增加到一定程度后，命中率反而開始下降。 失效率和命中率是兩個(gè)相關(guān)的概念，命中率增加時(shí)，失效率下降；命中率下降時(shí)，失效率反而增加。另外，Cache容量越大，則使失效率達(dá)到最低的塊大小就越大。,5.3.1降低Cache失效率的方法(續(xù)2),增加Cache容量 Cache容量越大，命中率越高，相關(guān)，失效率則越低。但增加Cache容量不僅會(huì)增加成本，而且也可能會(huì)因?yàn)閺?fù)雜的電路結(jié)構(gòu)等而增加Cache的訪問時(shí)間。 指令和數(shù)據(jù)硬件預(yù)取 指令和數(shù)據(jù)硬件預(yù)取是指在處理器訪問指令和數(shù)據(jù)之前，就把它們預(yù)取到Cache中或預(yù)取到可以比存儲(chǔ)器訪問速度更快的外部緩沖區(qū)中。 指令預(yù)取一般有恒預(yù)取和不命中預(yù)取兩種方法。,5.3.1降低Cache失效率的方法(續(xù)3),編譯器控制預(yù)取 硬件預(yù)取的一種替代方法是在編譯時(shí)加入預(yù)取指令，在數(shù)據(jù)被使用之前發(fā)出預(yù)取請(qǐng)求。有以下兩種方式： (1)寄存器預(yù)?。簩?shù)據(jù)預(yù)取到寄存器中。 (2)Cache預(yù)?。褐粚?shù)據(jù)預(yù)取到Cache中，并不放入寄存器。 編譯器優(yōu)化以降低Cache失效率 這種方法是采用軟件方法來優(yōu)化Cache性能，試圖通過優(yōu)化編譯時(shí)間來改善Cache性能： (1)程序代碼和數(shù)據(jù)重組 (2)循環(huán)交換 (3)分塊,5.3.2 減少Cache失效開銷,與降低失效率一樣，減少Cache失效開銷同樣可以縮短Cache存儲(chǔ)器的平均訪問時(shí)間并提高Cache的性能。 (1)采用兩級(jí)Cache：在原Cache和存儲(chǔ)器之間增加一級(jí)Cache，構(gòu)成兩級(jí)Cache。其中第一級(jí)Cache可以讓它小到足以與快速的處理器運(yùn)行時(shí)鐘周期相匹配，而第二級(jí)Cache則讓它大到足以捕獲到對(duì)內(nèi)存進(jìn)行的大多數(shù)訪問，從而有效地降低了失效開銷。 (2)讓讀失效優(yōu)先于寫：提高寫直達(dá)Cache性能最重要的方法是設(shè)置一個(gè)容量適中的寫緩存。然而寫緩存中可能包含讀失效時(shí)所需單元的最新值，這個(gè)值尚未寫入存儲(chǔ)器，導(dǎo)致了存儲(chǔ)器訪問的復(fù)雜化。解決方法是讓讀失效等待，直至寫緩存為空。,5.3.2 減少Cache失效開銷(續(xù)1),合并寫緩沖區(qū) 采用寫直達(dá)法的Cache要有一個(gè)寫緩沖區(qū)，如果寫緩沖區(qū)為空，就把被替換的數(shù)據(jù)和相應(yīng)地址寫入緩沖區(qū)。 請(qǐng)求字處理技術(shù) 處理器在同一時(shí)刻只需要調(diào)入塊中的一個(gè)字(即請(qǐng)求字)，不必等到全部的塊調(diào)入Cache，就可以將該字送往處理器并重新啟動(dòng)處理器進(jìn)行訪問，一般有以下兩種策略： (1)請(qǐng)求字優(yōu)先：調(diào)塊時(shí)，先向存儲(chǔ)器請(qǐng)求處理器所要的請(qǐng)求字。一旦該請(qǐng)求字到達(dá)即送往處理器，讓處理器繼續(xù)執(zhí)行，同時(shí)可以從存儲(chǔ)器中調(diào)入該塊的其他字。 (2)提前重啟動(dòng)：在請(qǐng)求字沒到達(dá)處理器時(shí)，處理器處于等待狀態(tài)。,5.3.3 減少命中時(shí)間,除了通過降低失效率和減少失效開銷來優(yōu)化Cache性能的方法以外，還可通過減少命中時(shí)間來優(yōu)化Cache的性能。命中時(shí)間也是平均訪問時(shí)間的一個(gè)組成部分，它的重要性在于它會(huì)影響處理器的時(shí)鐘頻率。 (1)小而簡(jiǎn)單的Cache減少命中時(shí)間 采用容量小、結(jié)構(gòu)簡(jiǎn)單的Cache，這樣快表較小，查表的速度較快，從而有效地提高了Cache的訪問速度。 (2)路預(yù)測(cè)減少命中時(shí)間 路預(yù)測(cè)要求Cache中預(yù)留特殊的比較位，用來預(yù)測(cè)下一次訪問Cache時(shí)可能會(huì)用到的路或塊。,5.3.3 減少命中時(shí)間(續(xù)1),(3)蹤跡Cache(Trace Cache)減少命中時(shí)間 蹤跡Cache中存儲(chǔ)的是處理器所執(zhí)行的動(dòng)態(tài)指令序列，而不是用于存儲(chǔ)主存儲(chǔ)器中給出的靜態(tài)指令序列。例如，在Pentium4處理器的蹤跡Cache中由于使用了譯碼微操作，從而節(jié)省了譯碼時(shí)間。 (4)流水線Cache訪問 流水線Cache訪問方法是將流水線、Cache訪問以及使一級(jí)Cache命中時(shí)的有效時(shí)延分散到幾個(gè)時(shí)鐘周期。它實(shí)際上并不能真正減少Cache命中時(shí)間，但可以提供較短的周期時(shí)間和高寬帶。,5.4 主存儲(chǔ)器及性能優(yōu)化,主存儲(chǔ)器也即主存，是存儲(chǔ)層次中緊接著Cache下面的一個(gè)層次。它是計(jì)算機(jī)硬件的一個(gè)重要部件，其作用是存放指令和數(shù)據(jù)，并能由中央處理器直接隨機(jī)存取。 它既被用來滿足Cache的請(qǐng)求，也被用作I/O接口。 主存的性能指標(biāo)主要是存儲(chǔ)容量、存取時(shí)間、存儲(chǔ)周期和存儲(chǔ)器帶寬。 存儲(chǔ)容量是指在一個(gè)存儲(chǔ)器中可以容納的存儲(chǔ)單元總數(shù)；存取時(shí)間是指從啟動(dòng)到完成一次存儲(chǔ)器操作所經(jīng)歷的時(shí)間；存儲(chǔ)周期是指連續(xù)啟動(dòng)兩次操作所需間隔的最小時(shí)間；存儲(chǔ)器帶寬是指單位時(shí)間里存儲(chǔ)器所存取的信息量。,5.4.1 主存儲(chǔ)器,目前，就主存的速度來看，仍不能滿足CPU的要求，這是因?yàn)橹鞔嫠俣鹊母倪M(jìn)跟不上CPU速度的提高。 Cache的引入，在很大程度上彌補(bǔ)了主存和CPU速度上的巨大差距。 主存的延遲因影響Cache的失效開銷而成為Cache主要關(guān)心的問題，另外，隨著第二級(jí)Cache的廣泛應(yīng)用，主存帶寬對(duì)于Cache來說也越來越重要了。 在有Cache的存儲(chǔ)層次中，主存的性能主要是用主存的延遲和帶寬來衡量的。,5.4.2 主存儲(chǔ)器性能優(yōu)化,增加存儲(chǔ)器的寬度 增加數(shù)據(jù)帶寬可以增加同時(shí)訪問的數(shù)據(jù)量，提高數(shù)據(jù)的吞吐量，最簡(jiǎn)單的方法是增加存儲(chǔ)器的寬度。 第一級(jí)Cache的寬度通常為一個(gè)字，因?yàn)镃PU大部分的訪存都是一個(gè)字的寬度的。在不具有第二級(jí)Cache的計(jì)算機(jī)系統(tǒng)中，主存的寬度一般與Cache的寬度相同。因此，可以將Cache和主存的寬度同時(shí)增加為原來寬度的兩倍或以上，從而增加了主存的寬度。,5.4.2 主存儲(chǔ)器性能優(yōu)化(續(xù)1),多體交叉存儲(chǔ)器 采用模m多體交叉編址，利用多體潛在的并行性進(jìn)行并行存取。其中每個(gè)存儲(chǔ)體的寬度一般為一個(gè)字的寬度，通過同時(shí)向多個(gè)個(gè)體發(fā)送地址對(duì)它們同時(shí)進(jìn)行訪問，從而一次可以讀或者寫多個(gè)字。 有兩種基本的多體交叉方法：高位多體交叉方法和低位多體交叉方法。,5.4.2 主存儲(chǔ)器性能優(yōu)化(續(xù)2),高位多體交叉方法 高位交叉存儲(chǔ)器的地址高位部分用于區(qū)分不同的存儲(chǔ)體，低位部分用于選擇一個(gè)存儲(chǔ)體體內(nèi)不同的存儲(chǔ)單元。,5.4.2 主存儲(chǔ)器性能優(yōu)化(續(xù)3),低位多體交叉方法 低位交叉存儲(chǔ)器的地址位使用方法與高位交叉存儲(chǔ)器剛好相反：低位部分用于區(qū)分不同的存儲(chǔ)體，高位部分用于選擇一個(gè)存儲(chǔ)體體內(nèi)不同的存儲(chǔ)單元。,5.5 虛擬存儲(chǔ)器,虛擬存儲(chǔ)器是由主存和聯(lián)機(jī)的外存共同組成的，在主存的容量不能滿足要求時(shí)，數(shù)據(jù)可存放在外存中，但在程序中仍按地址進(jìn)行訪問外存空間。 在虛擬存儲(chǔ)器中，應(yīng)用程序員是直接用機(jī)器指令的地址碼對(duì)整個(gè)程序統(tǒng)一編址的，虛擬存儲(chǔ)器的空間大小取決于它能產(chǎn)生的地址位數(shù)。 從程序員的角度看，存儲(chǔ)空間擴(kuò)大了，并可以放得下整個(gè)程序，程序不必作任何修改就可以以接近于實(shí)際主存的速度在這個(gè)虛擬存儲(chǔ)器上運(yùn)行。,108,5.5 虛擬存儲(chǔ)器,$1 虛擬存儲(chǔ)器工作原理 把主存儲(chǔ)器、磁盤存儲(chǔ)器和虛擬存儲(chǔ)器都劃分成固定大小的頁， 主存儲(chǔ)器的頁稱為實(shí)頁，虛擬存儲(chǔ)器中的頁稱為虛頁。,109,5.5 虛擬存儲(chǔ)器,內(nèi)部地址變換：多用戶虛擬地址Av變換成主存實(shí)地址A 多用戶虛擬地址中的頁內(nèi)偏移D直接作為主存實(shí)地址中的頁內(nèi)偏移d，主存實(shí)頁號(hào)p與它的頁內(nèi)偏移d直接拼接起來就得到主存實(shí)地址A。 外部地址變換： 首先查外頁表得到磁盤存儲(chǔ)器的實(shí)地址，把磁盤存儲(chǔ)器的實(shí)地址和主存儲(chǔ)器的實(shí)頁號(hào)送入輸入輸出處理機(jī)，把要訪問數(shù)據(jù)所在的一整頁都從磁盤存儲(chǔ)器調(diào)入到主存儲(chǔ)器。,110,5.5 虛擬存儲(chǔ)器,111,5.5 虛擬存儲(chǔ)器,$2 地址的映象和變換方法 三種地址空間：虛擬地址空間 主存儲(chǔ)器地址空間 輔存地址空間 地址映象：把虛擬地址空間映象到主存地址空間 地址變換：在程序運(yùn)行時(shí)，把虛地址變換成主存實(shí)地址,112,5.5 虛擬存儲(chǔ)器,因地址映象和變換方法不同，有三種虛擬存儲(chǔ)器： 頁式虛擬存儲(chǔ)器 段式虛擬存儲(chǔ)器 段頁式虛擬存儲(chǔ)器,113,5.5 虛擬存儲(chǔ)器,1、段式虛擬存儲(chǔ)器 地址映象方法：每個(gè)程序段都從0地址開始編址，長(zhǎng)度可長(zhǎng)可短，可以在程序執(zhí)行過程中動(dòng)態(tài)改變程序段的長(zhǎng)度。,114,5.5 虛擬存儲(chǔ)器,115,5.5 虛擬存儲(chǔ)器,地址變換方法： 由用戶號(hào)找到基址寄存器，從基址寄存器中讀出段表起始地址， 把起始地址與多用戶虛地址中段號(hào)相加得到段表地址， 把段表中的起始地址與段內(nèi)偏移D相加就能得到主存實(shí)地址。,116,第三節(jié) 虛擬存儲(chǔ)器,117,5.5 虛擬存儲(chǔ)器,主要優(yōu)點(diǎn)： (1) 程序的模塊化性能好。 (2) 便于程序和數(shù)據(jù)的共享。 (3) 程序的動(dòng)態(tài)鏈接和調(diào)度比較容易。 (4) 便于實(shí)現(xiàn)信息保護(hù)。,118,5.5 虛擬存儲(chǔ)器,主要缺點(diǎn)： (1) 地址變換所花費(fèi)的時(shí)間比較長(zhǎng)，做兩次加法運(yùn)算。 (2) 主存儲(chǔ)器的利用率往往比較低。 (3) 對(duì)輔存（磁盤存儲(chǔ)器）的管理比較困難。,119,5.5 虛擬存儲(chǔ)器,2、頁式虛擬存儲(chǔ)器 地址映象方法,120,5.5 虛擬存儲(chǔ)器,地址變換方法,121,5.5 虛擬存儲(chǔ)器,主要優(yōu)點(diǎn)： (1)主存儲(chǔ)器的利用率比較高 (2)頁表相對(duì)比較簡(jiǎn)單 (3)地址變換的速度比較快 (4)對(duì)磁盤的管理比較容易,122,5.5 虛擬存儲(chǔ)器,主要缺點(diǎn)： (1)程序的模塊化性能不好 (2)頁表很長(zhǎng)，需要占用很大的存儲(chǔ)空間 例如：虛擬存儲(chǔ)空間4GB，頁大小1KB，則頁表的容量為4M字，16MB。,123,5.5 虛擬存儲(chǔ)器,3、段頁式虛擬存儲(chǔ)器 用戶按照段來編寫程序，每個(gè)段分成幾個(gè)固定大小的頁。 地址映象方法： 每個(gè)程序段在段表中占一行， 在段表中給出該程序段的頁表長(zhǎng)度和頁表的起始地址， 頁表中給出這個(gè)程序段的每一頁在主存儲(chǔ)器中的實(shí)頁號(hào)。,124,5.5 虛擬存儲(chǔ)器,125,5.5 虛擬存儲(chǔ)器,地址變換方法： 先查段表，得到該程序段的頁表起始地址和頁表長(zhǎng)度， 再查頁表找到要訪問的主存實(shí)頁號(hào)， 最后把實(shí)頁號(hào)p與頁內(nèi)偏移d拼接得到主存的實(shí)地址。,126,5.5 虛擬存儲(chǔ)器,127,5.5 虛擬存儲(chǔ)器,地址變換方法： 先查段表，得到該程序段的頁表起始地址和頁表長(zhǎng)度， 再查頁表找到要訪問的主存實(shí)頁號(hào)， 最后把實(shí)頁號(hào)p與頁內(nèi)偏移d拼接得到主存的實(shí)地址。,128,5.5 虛擬存儲(chǔ)器,4、外部地址變換 在操作系統(tǒng)中，把頁面失效當(dāng)作一種異常故障來處理。 每個(gè)用戶程序都有一張外頁表，虛擬地址空間中的每一頁或每個(gè)程序段，在外頁表中都有對(duì)應(yīng)的一個(gè)存儲(chǔ)字。,129,5.5 虛擬存儲(chǔ)器,130,5.5 虛擬存儲(chǔ)器,$3 加快內(nèi)部地址變換速度的方法 造成虛擬存儲(chǔ)器速度降低的主要原因： (1) 要訪問主存儲(chǔ)器必須先查段表或頁表， (2) 可能需要多級(jí)頁表。 頁表級(jí)數(shù)的計(jì)算公式： 其中： Nv為虛擬存儲(chǔ)空間大小， Np為頁面的大小， Nd為一個(gè)頁表存儲(chǔ)字的大小,131,5.5 虛擬存儲(chǔ)器,例如：虛擬存儲(chǔ)空間大小Nv4GB，頁的大小Np1KB，每個(gè)頁表存儲(chǔ)字占用4個(gè)字節(jié)。計(jì)算得到頁表的級(jí)數(shù)： 通常僅把1級(jí)頁表和2、3級(jí)頁表中的一小部分駐留在主存中,132,5.5 虛擬存儲(chǔ)器,1、目錄表 基本思想：用一個(gè)小容量高速存儲(chǔ)器存放頁表。,133,5.5 虛擬存儲(chǔ)器, 基本思想： 用一個(gè)小容量高速存儲(chǔ)器存放頁表。 地址變換過程： 把多用戶虛地址中U與P拼接，相聯(lián)訪問目錄表。讀出主存實(shí)頁號(hào)p，把p與多用戶虛地址中的D拼接得到主存實(shí)地址。如果相聯(lián)訪問失敗，發(fā)出頁面失效請(qǐng)求。,134, 主要優(yōu)點(diǎn)： 與頁表放在主存中相比，查表速度快。 主要缺點(diǎn)： 可擴(kuò)展性比較差, 主存儲(chǔ)器容量大時(shí)，目錄表造價(jià)高，速度低。,5.5 虛擬存儲(chǔ)器,135,2、快慢表,5.5 虛擬存儲(chǔ)器,136,快表： TLB(Translation Lookaside Buffer)： 小容量(幾幾十個(gè)字)， 高速硬件實(shí)現(xiàn)， 采用相聯(lián)方式訪問。,5.5 虛擬存儲(chǔ)器,137,5.5 虛擬存儲(chǔ)器,慢表： 當(dāng)快表中查不到時(shí)，從存放在主存中的慢表中查找； 慢表按地址訪問； 用軟件實(shí)現(xiàn)。,138,快表與慢表實(shí)際上也構(gòu)成了一個(gè)兩級(jí)存儲(chǔ)系統(tǒng)。 主要存在問題：相聯(lián)訪問實(shí)現(xiàn)困難，速度比較低。,5.5 虛擬存儲(chǔ)器,139,3、散列函數(shù) 目的：把相聯(lián)訪問變成按地址訪問，從而加大快表容量 散列（Hashing）函數(shù)：AhH（Pv），20位左右68位,5.5 虛擬存儲(chǔ)器,140,5.5 虛擬存儲(chǔ)器,141, 采用散列變換實(shí)現(xiàn)快表按地址訪問 避免散列沖突：采用相等比較器 地址變換過程：相等比較與訪問存儲(chǔ)器同時(shí)進(jìn)行,5.5 虛擬存儲(chǔ)器,142,5.5 虛擬存儲(chǔ)器,143,4、虛擬存儲(chǔ)器舉例 例5.8：IMB370/168計(jì)算機(jī)的虛擬存儲(chǔ)器中的快表結(jié)構(gòu)及地址變換過程。 虛擬地址長(zhǎng)48位，頁面大小為4KB，每個(gè)用戶最多占用4K 個(gè)頁面，最多允許16G個(gè)用戶，但同時(shí)上機(jī)的用戶數(shù)一般不超過6個(gè)。,5.5 虛擬存儲(chǔ)器,144,采用了兩項(xiàng)新的措施： (1) 采用兩個(gè)相等比較器，以減少散列沖突。 (2) 用一個(gè)相聯(lián)寄存器組，把24位用戶號(hào) U 壓縮成 3 位，以縮短快表的長(zhǎng)度。,5.5 虛擬存儲(chǔ)器,145,5.5 虛擬存儲(chǔ)器,146,$4 頁面替換算法及其實(shí)現(xiàn)方法 頁面替換發(fā)生時(shí)間： 當(dāng)發(fā)生頁面失效時(shí)，要從磁盤中調(diào)入一頁到主存。 如果主存儲(chǔ)器的所有頁面都已經(jīng)被占用，必須從主存儲(chǔ)器中淘汰掉一個(gè)不常使用的頁面，以便騰出主存空間來存放新調(diào)入的頁面。 評(píng)價(jià)頁面替換算法好壞的標(biāo)準(zhǔn)： 一是命中率要高，二是算法要容易實(shí)現(xiàn)。,5.5 虛擬存儲(chǔ)器,147,頁面替換算法的使用場(chǎng)合： (1) 虛擬存儲(chǔ)器中，主存頁面的替換，一般用軟件實(shí)現(xiàn)。 (2) Cache中的塊替換，一般用硬件實(shí)現(xiàn)。 (3) 虛擬存儲(chǔ)器的快慢表中，快表存儲(chǔ)字的替換，用硬件實(shí)現(xiàn)。 (4) 虛擬存儲(chǔ)器中，用戶基地址寄存器的替換，用硬件實(shí)現(xiàn)。 (5) 在有些虛擬存儲(chǔ)器中，目錄表的替換。,5.5 虛擬存儲(chǔ)器,148,5.5 虛擬存儲(chǔ)器,1、頁面替換算法 (1)隨機(jī)算法（RAND random algorithm） 算法簡(jiǎn)單，容易實(shí)現(xiàn)。沒有利用歷史信息，沒有反映程序的局部性，命中率低。 (2)先進(jìn)先出算法（FIFO first-in first-out algorithm） 比較容易實(shí)現(xiàn)，利用了歷史信息，沒有反映程序的局部性。 最先調(diào)入主存的頁面，很可能也是經(jīng)常要使用的頁面。,149,(3)近期最少使用算法(LFU least frequently used algorithm) 既充分利用了歷史信息，又反映了程序的局部性 實(shí)現(xiàn)起來非常困難。 (4)最久沒有使用算法（LRU least recently used algorithm） 把LFU算法中的“多”與“少”簡(jiǎn)化成“有”與“無”，實(shí)現(xiàn)比較容易,5.5 虛擬存儲(chǔ)器,150,(5)最優(yōu)替換算法（OPT optimal replacement algorithm）： 是一種理想算法,僅用作評(píng)價(jià)其它頁面替換算法好壞的標(biāo)準(zhǔn) 在虛擬存儲(chǔ)器中,實(shí)際上可能采用的只有FIFO和LRU兩種算法,5.5 虛擬存儲(chǔ)器,151,例5.9：一個(gè)程序共有5個(gè)頁面組成，在程序執(zhí)行過程中，頁面地址流如下： P1，P2，P1，P5，P5，P1，P3，P4，P3，P4 假設(shè)在程序執(zhí)行過程中分配給這個(gè)程序的主存儲(chǔ)器只有3個(gè)頁面。,5.5 虛擬存儲(chǔ)器,152,(1)給出用 FIFO、LRU和OPT 三種頁面替換算法對(duì)這3個(gè)主存的調(diào)度情況表，并統(tǒng)計(jì)頁面命中次數(shù)。 (2)計(jì)算這LRU頁面替換算法的頁面命中率。 (3)假設(shè)每個(gè)數(shù)據(jù)平均被訪問20次，為了使LRU算法的頁面失效率小于10-5，計(jì)算頁面大小至少應(yīng)該為多少？,5.5 虛擬存儲(chǔ)器,153,解：(1)FIFO、LRU和OPT的頁面命中次數(shù)分別為2次、4次和5次 (2)LRU頁面替換算法的頁面命中率為：Hp4/100.4 (3) 解得 P 3000字,5.5 虛擬存儲(chǔ)器,154,5.5 虛擬存儲(chǔ)器,155,例5.10：一個(gè)循環(huán)程序，依次使用P1，P2，P3，P4四個(gè)頁面，分配給這個(gè)程序的主存頁面數(shù)為3個(gè)。 在FIFO和LRU算法中，總是發(fā)生下次將要使用的頁面在本次被替換出去的情況，這就是“顛簸