【正文】 行數(shù) =2P 行數(shù) = 塊數(shù) 8b 塊數(shù) =2p 正常命中： 偽命中（增加 2 拍）： AF IF ID EX ME WB AF IF ID EX ME WB AF IF ID EX ME WB AF IF ID EX ME WB AF IF ID EX ME WB AF IF ID EX ME WB 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 49 例 （補(bǔ)充， 2版 P198例 ） 一個(gè)偽相聯(lián) Cache，當(dāng)在按直接映象找到的位置處沒有發(fā)現(xiàn)匹配、而在另一個(gè)位置才找到數(shù)據(jù)（偽命中）時(shí)需要增加 2個(gè)額外的周期。偽命中情況下 需要增加 2個(gè)額外的 時(shí)鐘 周期（其中 1個(gè)周期是多找 1次花去的， 1個(gè)周期是交換操作所需）。 每次訪問時(shí)間有 3種可能： ? 正常命中（快速命中） ? 偽命中（慢速命中） ? 不命中 偽相聯(lián)（續(xù) 1） 索引 至 CPU 取出數(shù)據(jù)送往 CPU 偽相聯(lián)組 … … 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 47 (4) 快速命中與慢速命中 要保證絕大多數(shù)命中都是快速命中，就是命中率要高。再找不到就只好訪問下一級(jí)存儲(chǔ)器。若不命中，則再到另一區(qū)相應(yīng)的位置去查找。對(duì)于任何一次訪問，偽相聯(lián) Cache先按直接 相聯(lián) Cache的方式去處理。優(yōu)點(diǎn)是命中時(shí)間短、 不命中 率還低，所以它的平均訪問時(shí)間往往比直接相聯(lián)、組相聯(lián)都短 。 (1) 比較直接相聯(lián)、組相聯(lián)的優(yōu)缺點(diǎn) 從例 ，直接相聯(lián)的命中時(shí)間較短，而多路組相聯(lián)的失效率較低，所以它們的平均訪問時(shí)間依兩個(gè)因素的作用大小而互有輸贏。 索引 =0的實(shí)塊里裝的虛塊標(biāo)識(shí)可以是 00， 01， …… ， 99，對(duì)應(yīng)的虛塊號(hào)就是 000， 010， 020，030， …… ， 990。 虛實(shí)變換基本方法（續(xù) 4） 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 42 主 ─輔層次虛實(shí)變換實(shí)現(xiàn) 主流方案：全相聯(lián)，頁(yè)表法（ P232） P 位 S 位 虛地址 虛頁(yè)號(hào) 偏移 p 位 實(shí)地址 實(shí)存 頁(yè)表 1 頁(yè) =2S 實(shí)頁(yè)號(hào) 標(biāo)志位 裝入？ ∶ ∶ 行數(shù) =2P 行數(shù) 頁(yè)數(shù) 8b 頁(yè)數(shù) =2p 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 43 Cache ─ 主存層次虛實(shí)變換實(shí)現(xiàn)（直接相聯(lián)） 快命中方案：直接相聯(lián)，目錄表法（ P196， 圖 ） P 位 S 位 虛地址 虛塊號(hào) 偏移 標(biāo)識(shí)段 索引段 （ p 位 ） p 位 實(shí)地址 實(shí)存 目錄表 1 塊 =2S 標(biāo)識(shí) 實(shí)塊號(hào) 標(biāo)志位 裝入？ 比較 命中？ ∶ ∶ 行數(shù) =2P 行數(shù) = 塊數(shù) 8b 塊數(shù) =2p 舉例：為了方便用 10進(jìn)制討論。 虛實(shí)變換基本方法（續(xù) 3） 從 2g組中 選擇一組 h 位 g 位 標(biāo)識(shí) 索引 相聯(lián)比較 … … 總?cè)萘浚?2g n 項(xiàng) 組內(nèi)塊地址（ log 2 n 位） n 個(gè)項(xiàng) 標(biāo)識(shí)存儲(chǔ)器 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 41 (5) 單體多字存儲(chǔ)器＋多比較器查表方法（ P196第 2段 ） 這是 目錄表 法的一種廉價(jià)方案，對(duì)組相聯(lián)非常適用。 虛實(shí)變換基本方法（續(xù) 2） 虛擬地址 〈 36 〉 〈 12 〉 虛頁(yè)號(hào) 頁(yè)內(nèi)位移 物理地址 〈 1 〉 V R/W ① ② ③ ④ ? U/S D A 〈 1 〉 〈 1 〉 〈 36 〉 標(biāo)識(shí) 〈 28 〉 ? ? 40 選 1 多路選擇器 ? 〈 28 〉 〈 12 〉 40 位 物理地址 （ 低 12 位地址 ） （ 高 28 位地址 ） 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 40 (4) 目錄表法（ P196第 1段） 只對(duì)已經(jīng)裝入實(shí)存的虛頁(yè)造表，其項(xiàng)數(shù)比頁(yè)表少得多。 虛實(shí)變換基本方法（續(xù) 1） 虛頁(yè)號(hào) 項(xiàng)號(hào) 標(biāo)識(shí) 實(shí)頁(yè)號(hào) 裝入標(biāo)志 其它標(biāo)志 標(biāo)識(shí) 11 索引 10 00 11 01 1 ? 01 00 00 0 ? 10 01 11 1 ? 11 10 10 1 ? 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 39 (3) 快慢表方法（ P231） 這是頁(yè)表法的一種加快方案。 虛頁(yè)號(hào)里用于計(jì)算表內(nèi)地址的部分稱為 “ 索引 ” index ， 用來與查表內(nèi)容相比較的部分稱為 “ 標(biāo)識(shí) ” tag。（與 Hash查表有點(diǎn)相似） 表項(xiàng)數(shù)少于虛頁(yè)數(shù)意味著查表時(shí)會(huì)有多個(gè)虛頁(yè)查到表中同一項(xiàng)的情況發(fā)生，另外也意味著區(qū)分表中項(xiàng)號(hào)的地址位數(shù)少于虛頁(yè)號(hào)的位數(shù)，虛頁(yè)號(hào)中未用的位數(shù)正是造成重復(fù)的原因。進(jìn)一步發(fā)展就會(huì)形成“多級(jí)頁(yè)表” ， 導(dǎo)致虛實(shí)變換分多步進(jìn)行，時(shí)間大大延長(zhǎng)。這種方法原理簡(jiǎn)單，但是占用空間非常大。 1 虛 3 √ √ 虛 區(qū) 2 4 位選擇組相聯(lián)的地址變換過程比一般組相聯(lián)映象方式簡(jiǎn)單 ， 而與全相聯(lián)映象方式基本相同 。 由于在虛存與實(shí)存之間是以塊為單位進(jìn)行調(diào)度的 ， 而實(shí)存是以字為單位訪問的 ， 只要實(shí)存中的一個(gè)字不跨越兩個(gè)塊 ， 在實(shí)存內(nèi)部的塊與塊之間的分布是否連續(xù)對(duì)實(shí)存的正常工作是沒有關(guān)系的 。 另外 ， 從數(shù)據(jù)的分布情況看。 而在位選擇組相聯(lián)映象方式中 ， 改成了一個(gè)虛塊到實(shí)組中多個(gè)塊的映象 。 例如 ， 虛塊 0可以映象到實(shí)組 0的任意一塊中 。 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 33 組相聯(lián)的地址映象方式與地址變換原理 (c) 虛地址 虛組號(hào) 1 0 組內(nèi)頁(yè)號(hào) 1 頁(yè)內(nèi)偏移量 D實(shí)地址 實(shí)組號(hào) 0 組內(nèi)頁(yè)號(hào) 0 頁(yè)內(nèi)偏移量 d0 組子表 項(xiàng) 0 ： ： ： 項(xiàng) 1 ： ： ：1 組子表 項(xiàng) 0 ： ： ： 項(xiàng) 1 ： ： ：2 組子表 項(xiàng) 0 ： ： ： 項(xiàng) 1 0 裝入位 1 ：3 組子表 項(xiàng) 0 ： ： ： 項(xiàng) 1 ： ： ：( c ) 求模運(yùn)算與分組查表結(jié)合進(jìn)行虛實(shí)變換示例 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 34 (4) 位選擇組相聯(lián) (P194圖 ) 位選擇組相聯(lián)映象方式映象關(guān)系中 ， 實(shí)存分組 ， 虛存按實(shí)組數(shù)分區(qū) ， 區(qū)內(nèi)不分組 。 2 實(shí)組 1 頁(yè) 4 √ √ 5 0 實(shí)組 0 2 √ √ 3 下頁(yè)圖示為 2路組相聯(lián) （ 2way set associative）。 這種映象方式性價(jià)比較好 ， 在 Cache主存層次中被普遍使用 。 當(dāng)然這兩方面優(yōu)點(diǎn)是互相抵觸的：組內(nèi)頁(yè)數(shù)越多 ， 實(shí)存空間劃分的組數(shù)就越少 ， 實(shí)組號(hào)字段所占位數(shù)也少 ， 這時(shí)改善實(shí)頁(yè)爭(zhēng)用現(xiàn)象的效果較好 ， 而節(jié)省頁(yè)表空間的效果較差 ， 反之亦然 。 如圖 (c)所示 。 在虛實(shí)變換時(shí) ， 首先根據(jù)虛頁(yè)號(hào)所在的虛組號(hào) ， 通過求模運(yùn)算確定實(shí)組號(hào) ， 再按虛組號(hào)在相應(yīng)的子表內(nèi)讀出組內(nèi)頁(yè)號(hào) ， 拼接在一起就是實(shí)頁(yè)號(hào) 。 所有虛組按照直接相聯(lián)方式映射到實(shí)組集合 ， 對(duì)應(yīng)的虛實(shí)組之間各頁(yè)則用全相聯(lián)映射 ， 如下頁(yè)示意圖 (a)、 (b)所 示 （ 設(shè)實(shí)組數(shù)為 2） 。 6 √ 7 7 √( a ) 虛頁(yè)集合與實(shí)頁(yè)集合的對(duì)應(yīng)關(guān)系 ( b) 對(duì)應(yīng)關(guān)系表 （ √ 為有關(guān)系）虛地址 虛頁(yè)號(hào) 1 1 1 頁(yè)內(nèi)偏移量 D實(shí)地址 實(shí)頁(yè)號(hào) 1 1 頁(yè)內(nèi)偏移量 d( c ) 通過 求模運(yùn)算進(jìn)行虛實(shí)變換示例 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 31 (3) 組相聯(lián) (set associative， P194) 組相聯(lián)映象方式是全相聯(lián)與直接相聯(lián)的一個(gè)折中方案 ， 性能也是二者的折中 。 2 頁(yè) 4 √ 5 0 2 √ 3 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 30 直接相聯(lián)的地址映象方式與地址變換原理 虛存 實(shí)頁(yè) 0 1 2 3 0 0 √ 1 這種映象方式主要用于對(duì)實(shí)存價(jià)格 、 速度敏感的 Cache主存層次 。 解： 可用十進(jìn)制形式求： 7 mod 4 = 3； 也可用二進(jìn)制形式求：由于 n = 4， 所以 log2n = 2， 取 7的二進(jìn)制形式 111B的最低 2位 ， 得 11B， 即 3。 實(shí)現(xiàn)起來非常簡(jiǎn)單 ， 因?yàn)樵诙M(jìn)制中 ， 任何數(shù) X對(duì) 2的整次冪 n求模等價(jià)于截取 X的最低 log2n位 ， 如下頁(yè)示意圖 (c)所示 。 3 5 √ √ √ √ 6 6 √ √ √ √ 7 7 √ √ √ √( a ) 虛頁(yè)集合與實(shí)頁(yè)集合的對(duì)應(yīng)關(guān)系 ( b) 對(duì)應(yīng)關(guān)系表 （ √ 為有關(guān)系） 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 28 全相聯(lián)的地址映象方式與地址變換原理示意圖 (c) 虛地址 虛頁(yè)號(hào) P 頁(yè)內(nèi)偏移量 D實(shí)地址 實(shí)頁(yè)號(hào) p 頁(yè)內(nèi)偏移量 d實(shí)頁(yè)號(hào) 裝入位 修改位表項(xiàng) 0 ： ： ： ： ： ： ：表項(xiàng) P p 1 0 ： ： ： ：表項(xiàng) 7 ： ： ：( c ) 通過 查表進(jìn)行虛實(shí)變換 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 29 (2) 直接相聯(lián) (direct mapped) 直接相聯(lián)是一種最強(qiáng)的約束關(guān)系 ， 它規(guī)定每個(gè)虛頁(yè)只對(duì)應(yīng)唯一的實(shí)頁(yè) 。 1 虛 3 √ √ √ √ 4 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 27 全相聯(lián)的地址映象方式與地址變換原理示意圖 (a)(b) 虛存 實(shí)頁(yè) 0 1 2 3 0 0 √ √ √ √ 1 實(shí)存 1 √ √ √ √ 2 由于頁(yè)表必須常駐在實(shí)存中 ， 而主存 輔存層次的實(shí)存 （ 即主存 ） 相對(duì)Cache主存層次的實(shí)存 （ 即 Cache存儲(chǔ)器 ） 容量大得多 ， 所以全相聯(lián)映象方式一般用于主存 輔存層次 。 全相聯(lián)映象方式使虛頁(yè)調(diào)入有最大的選擇范圍 ， 發(fā)生實(shí)頁(yè)爭(zhēng)用的可能性最小 ， 調(diào)入 /調(diào)出的操作開銷也最少 ， 有利于命中率提高 。 這種關(guān)系可用下頁(yè)示意圖 (a)、 (b)表示 。 此法須嚴(yán)格限制字?jǐn)?shù) 。 為避免逐行比對(duì) ， 利用相聯(lián)存儲(chǔ)器存放此表 ， 它具有并行比較功能 ， 但價(jià)格遠(yuǎn)高于普通存儲(chǔ)器 。 頁(yè)表 占用空間 = 頁(yè)表行數(shù) 每行寬度 其中 ， 頁(yè)表行數(shù) = 虛存容量 / 頁(yè)面大小 以 Win2K為例 ， 虛存頁(yè)表 = 4 4G / 4K = 22 232 / 212 = 222 = 4MB Cache主存層次的頁(yè)表 = 4 4G / 16 = 230 = 1GB， 而 Cache1只有 32K 減少頁(yè)表空間的思路分 減少行數(shù) 和 減少行寬 兩類 。 例 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 23 (2) TA＝ TA1＋ F1 (TA2＋ F2 TM2) ＝ 1＋ 4% (10＋ 50% 100) ＝ 1＋ 4% 60＝ 式中后面部分 4% 60為每次訪存的平均停頓時(shí)間（即 失效開銷 ）： 每次訪存的平均停頓時(shí)間（即 失效開銷 ）＝ 4% 60＝ 由于平均每條指令訪存 ，所以： 每條指令的平均停頓時(shí)間＝ ＝ 習(xí)題 例 （續(xù)） 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 24 各次作業(yè)應(yīng)交的內(nèi)容 作業(yè) 8（第 9次課） 2 月 19 日 1. 10 ( 改 ) ， 1. 7 ， 1. 1 1( 2 解法 ) 4 月 9 日 7. 14 ( 難題 ) ， 7. 12 ( 難題 ) 2 月 26 日 2. 14 ( 補(bǔ)充 ) ，實(shí)驗(yàn) 1 ， 3. 8 ， 3. 10 4 月 16 日 8. 12 ( 補(bǔ) ) ， 8. 1 1( 改 ) ( 難題 ) 3 月 5 日 3. 1 1( 改 ) ，實(shí)驗(yàn) 2 ， 5. 1 1 ， 5. 8 ， 5. 9 4 月 23 日 9. 9( 改 ) ， 9. 13 3 月 12 日 6. 8( 改 ) ， 6. 7 ， 7. 9 4 月 30 日 10 .6 ， 10 .9 ( 難題 ) 4 月 2 日 7. 1 1 ， 7. 10 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 25 地址映象問題的提出 頁(yè)表必須存放在實(shí)存 M1里 。求各種局部不命中率和全局不命中率； (2) 假設(shè) Cache1的命中時(shí)間是 1個(gè)時(shí)鐘周期， Cache2的命中時(shí)間是 10個(gè)時(shí)鐘周期，不命中開銷是 100時(shí)鐘周期，平均每條指令訪存 ，不考慮寫操作的影響。 局部不命中率與全局不命中率（ P214） 級(jí)訪問次數(shù)到達(dá)第級(jí)不命中次數(shù)第局部不命中率i