計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)電子教案

第7章存儲(chǔ)層次（P188）

MemoryHirarchy長(zhǎng)期存在的問題：在合理的總價(jià)格限制下，單一型主存器件的速度跟不上CPU的發(fā)展，容量不能滿足軟件尺寸擴(kuò)大。本章學(xué)習(xí)提高主存系統(tǒng)性能/價(jià)格比的幾種結(jié)構(gòu)化方法，重點(diǎn)是“Cache-主存層次”，焦點(diǎn)問題是如何使流水線每拍完成一次訪存。本章基本公式：(1)平均時(shí)間T=P1×T1+P2×T2其中P1+P2=100%，并且T1和T2都可以再用該式迭代展開，復(fù)雜時(shí)，可用概率樹來(lái)表示（全概率公式）；(2)實(shí)際時(shí)間T=理想時(shí)間+P3

×每次額外開銷時(shí)間其中P3是不利事件發(fā)生概率。2014.2.171計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第1頁(yè)!7.1存儲(chǔ)層次原理及性能指標(biāo)（P188）7.1.1基本原理“存儲(chǔ)層次”的定義：（參見P189第3段）由2種或多種存儲(chǔ)部件構(gòu)成的復(fù)合存儲(chǔ)系統(tǒng)，通過內(nèi)部管理機(jī)構(gòu)的自動(dòng)更換機(jī)制，能夠不斷將大容量低速存儲(chǔ)部件中的活躍內(nèi)容復(fù)制到小容量高速存儲(chǔ)部件中（后者作為前者的局部副本）。它既能滿足CPU的快速存取需要，又有很大的存儲(chǔ)容量，平均單位價(jià)格也很低，等效于同時(shí)滿足3方面要求的理想單一存儲(chǔ)部件。依據(jù)：程序訪問的局部化原理（時(shí)間局部化，空間局部化）。模型：如右圖所示，存儲(chǔ)層次由n層組成，滿足3個(gè)不等式：TAi<TAi+1，ci>ci+1，Si<Si+1。2014.2.172計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第2頁(yè)!存儲(chǔ)層次的基本術(shù)語(yǔ)

邏輯地址（又稱為相對(duì)地址、虛地址）是程序員在編寫和編譯一個(gè)程序模塊時(shí)分配指令和數(shù)據(jù)的空間單位序號(hào)，總是從0開始（可以按字節(jié)編址、按CPU字編址等）。邏輯地址的取值范圍稱為邏輯地址空間、虛空間或虛存。

物理地址（又稱為絕對(duì)地址、實(shí)地址）是任一級(jí)存儲(chǔ)器為全部存儲(chǔ)單元分配的序號(hào)。物理地址的取值范圍稱為物理地址空間、實(shí)空間或?qū)嵈?。從M1到Mn各層都有自己的物理地址空間，而對(duì)當(dāng)前執(zhí)行的程序模塊來(lái)說(shuō)，邏輯地址空間只有一個(gè)。

地址映象方式指的是虛頁(yè)集合與實(shí)頁(yè)集合的對(duì)應(yīng)規(guī)則，或者說(shuō)是約束關(guān)系。

地址變換（又叫虛實(shí)變換）指邏輯地址到物理地址的變換過程或者算法。

頁(yè)失效指當(dāng)前被訪問存儲(chǔ)級(jí)中沒有所需的信息，也就是不命中現(xiàn)象。

實(shí)頁(yè)爭(zhēng)用又叫實(shí)頁(yè)沖突，指虛頁(yè)調(diào)入時(shí)，根據(jù)地址映象方式劃定的實(shí)空間范圍內(nèi)已沒有空閑實(shí)頁(yè)的狀況。

頁(yè)和塊：前者用于主-輔層次，后者用于Cache-主存層次，意義相同。2014.2.173計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第3頁(yè)!7.7.1存儲(chǔ)層次的管理方式(續(xù))(2)頁(yè)式管理。頁(yè)是系統(tǒng)規(guī)定的固定長(zhǎng)度單位。按頁(yè)劃分用戶文件可以避免上述零碎空間浪費(fèi)。我們把用戶文件劃分得到的一個(gè)長(zhǎng)度單位稱為“虛頁(yè)”，因?yàn)樗捻?yè)號(hào)是在虛地址空間中編排的；實(shí)地址空間按頁(yè)的大小劃分得到的一個(gè)長(zhǎng)度單位稱為“實(shí)頁(yè)”。頁(yè)式管理方法的主要缺點(diǎn)是按固定長(zhǎng)度分出來(lái)的同一頁(yè)內(nèi)常有不同屬性的信息，不便于信息保護(hù)的實(shí)現(xiàn)。頁(yè)式管理方法的虛實(shí)變換算法是查頁(yè)表。兩種層次都用此技術(shù)。(3)段頁(yè)式管理。它把上述兩種管理方式結(jié)合起來(lái)，首先將整個(gè)文件分段，然后在各段內(nèi)分頁(yè)，所以有一個(gè)段表和若干個(gè)頁(yè)表。其虛實(shí)變換算法是先查段表，查出該段的頁(yè)表起始地址再查相應(yīng)的頁(yè)表。段頁(yè)式管理的主要缺點(diǎn)是多查一次表，虛實(shí)變換費(fèi)時(shí)較多，占用空間也較大。它的實(shí)現(xiàn)最復(fù)雜，僅用于主存—輔存層次。段頁(yè)式管理方法的最小調(diào)度單位仍是頁(yè)，基本操作可歸于頁(yè)式管理。2014.2.174計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第4頁(yè)!課堂練習(xí)7.1（續(xù)）虛地址經(jīng)變址尋址和基址尋址(B)+(X)+D形成?，F(xiàn)有一個(gè)程序，出現(xiàn)下列訪問主存的操作：(1)列出產(chǎn)生主存頁(yè)面失效的操作序號(hào)。(2)如果不發(fā)生主存頁(yè)面失效的話，計(jì)算訪問主存的物理地址。(3)列出非法操作的序號(hào)。(4)列出被修改過的主存頁(yè)面號(hào)。2014.2.175計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第5頁(yè)!7.1.4存儲(chǔ)層次的基本問題(P192)①映象規(guī)則——一個(gè)虛塊（頁(yè)）被允許放到哪些實(shí)塊（頁(yè)）上；②查找算法——如何在實(shí)存中找到指定的虛塊（頁(yè)）（主要是虛實(shí)變換）；③替換算法——塊（頁(yè)）爭(zhēng)用時(shí)，調(diào)出哪個(gè)虛塊（頁(yè)）；④寫策略——寫存儲(chǔ)層次的具體操作。典型存儲(chǔ)層次（PC計(jì)算機(jī)，以Intel芯片組為例）2014.2.176計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第6頁(yè)!(3)速度

表現(xiàn)訪問速度的參數(shù)較多。命中率H：被訪問數(shù)據(jù)事先已在M1的概率不命中率F：不命中的概率，又稱失效率，F(xiàn)=1-H平均訪存時(shí)間：命中時(shí)的訪存時(shí)間為TA1，不命中時(shí)的訪存時(shí)間為TA2，平均訪存時(shí)間則是它們的概率均值其中TM是失效開銷，TM=TA2+TB22014.2.177計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第7頁(yè)!假設(shè)：TAi表示第i級(jí)器件讀/寫時(shí)間；TBi表示第i級(jí)向上級(jí)傳送時(shí)間。根據(jù)模型有：命中M1時(shí)：TA=TA1命中M2時(shí)：TA=TA1+TA2+TB2≈TA2……命中Mn時(shí)：TA=TA1+TA2+TB2+……+TAn+TBn≈Tan區(qū)別：?jiǎn)未卧L問總時(shí)間近似等于本次到達(dá)的最低一層的訪問時(shí)間，因?yàn)槊繉佣贾辉L問一次；大量訪問的平均時(shí)間則由各層訪問時(shí)間共同構(gòu)成，因?yàn)檩^高層的一次訪問時(shí)間雖短，但它們被訪問的百分比遠(yuǎn)遠(yuǎn)大于較低層。多級(jí)存儲(chǔ)層次的單次訪問時(shí)間2014.2.178計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第8頁(yè)!多級(jí)存儲(chǔ)層次的平均訪問時(shí)間1

M1103BTA1=1us103B

M2106BTA2=10usM3109BTA3=100us109B(a)(b)例7.0有一個(gè)109字節(jié)的程序被裝入右圖所示的M3準(zhǔn)備運(yùn)行。假定指令字長(zhǎng)=1字節(jié)，程序中無(wú)轉(zhuǎn)移指令和內(nèi)存讀/寫指令。忽略傳送時(shí)間TB。(1)按圖(a)求TA和e；(2)按圖(b)推導(dǎo)三層體系的TA公式；(3)按圖(b)求TA和e；(4)比較(1)(3)結(jié)果，有何結(jié)論？解：2014.2.179計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第9頁(yè)!多級(jí)存儲(chǔ)層次的平均訪問時(shí)間3(4)結(jié)論：插入中間層后，層間速度差減少，訪問效率提高。2014.2.1710計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第10頁(yè)!剛才推導(dǎo)中使用的不命中率都是局部不命中率。為了避免混淆，有必要分清兩種不命中率：全局不命中率是一個(gè)比局部不命中率更有意義的指標(biāo)，它指出了在CPU發(fā)出的所有訪存請(qǐng)求中，究竟有多大比例是穿過該級(jí)，到達(dá)下一級(jí)存儲(chǔ)器的。7.4.1局部不命中率與全局不命中率（P214）2014.2.1711計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第11頁(yè)!多級(jí)存儲(chǔ)層次的平均訪問時(shí)間公式重寫將這些局部不命中率、全局不命中率的定義式代入到前面的多級(jí)存儲(chǔ)層次平均訪問時(shí)間公式中，我們可以得到更容易記憶的公式形式：2014.2.1712計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第12頁(yè)!(2)TA＝TA1＋F1×(TA2＋F2×TM2)＝1＋4%×(10＋50%×100)＝1＋4%×60＝3.4個(gè)時(shí)鐘周期式中后面部分4%×60為每次訪存的平均停頓時(shí)間（即失效開銷）：每次訪存的平均停頓時(shí)間（即失效開銷）＝4%×60＝2.4由于平均每條指令訪存1.5次，所以：每條指令的平均停頓時(shí)間＝2.4×1.5＝3.6個(gè)時(shí)鐘周期習(xí)題7.9例7.3（續(xù)）2014.2.1713計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第13頁(yè)!地址映象問題的提出1.頁(yè)表占用空間過大問題頁(yè)表必須存放在實(shí)存M1里。實(shí)際上，命中情況下的訪存時(shí)間等于查表時(shí)間加上訪問目標(biāo)數(shù)據(jù)的時(shí)間，所以頁(yè)表不能放在M2。頁(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ù)和減少行寬兩類。2.相聯(lián)目錄表方法（又稱“實(shí)頁(yè)表”）/減少行數(shù)僅保留頁(yè)表中已裝入的虛頁(yè)記錄。為避免逐行比對(duì)，利用相聯(lián)存儲(chǔ)器存放此表，它具有并行比較功能，但價(jià)格遠(yuǎn)高于普通存儲(chǔ)器。P196圖7.10示意Cache中用多字并行比較方法實(shí)現(xiàn)的相聯(lián)目錄表。此法須嚴(yán)格限制字?jǐn)?shù)。3.快慢表方法（TLB）/減少行數(shù)4.改變地址映象/減少行寬2014.2.1714計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第14頁(yè)!全相聯(lián)的地址映象方式與地址變換原理示意圖(a)(b)2014.2.1715計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第15頁(yè)!(2)直接相聯(lián)(directmapped)直接相聯(lián)是一種最強(qiáng)的約束關(guān)系，它規(guī)定每個(gè)虛頁(yè)只對(duì)應(yīng)唯一的實(shí)頁(yè)。為了便于虛實(shí)變換，用求模運(yùn)算作為變換關(guān)系式：將虛頁(yè)號(hào)對(duì)實(shí)頁(yè)總數(shù)求模得到實(shí)頁(yè)號(hào)。實(shí)現(xiàn)起來(lái)非常簡(jiǎn)單，因?yàn)樵诙M(jìn)制中，任何數(shù)X對(duì)2的整次冪n求模等價(jià)于截取X的最低log2n位，如下頁(yè)示意圖(c)所示。例5.2已知虛頁(yè)號(hào)=7，實(shí)頁(yè)總數(shù)=4，用直接相聯(lián)求實(shí)頁(yè)號(hào)。解：可用十進(jìn)制形式求：7mod4=3；也可用二進(jìn)制形式求：由于n=4，所以log2n=2，取7的二進(jìn)制形式111B的最低2位，得11B，即3。直接相聯(lián)映象方式不需要借助頁(yè)表來(lái)進(jìn)行虛實(shí)變換，顯然大大節(jié)省了相應(yīng)的空間與時(shí)間（當(dāng)然頁(yè)表中的裝入位和修改位還得保留），但是由于每個(gè)虛頁(yè)的選擇范圍太小，實(shí)頁(yè)爭(zhēng)用的發(fā)生頻率較高，常出現(xiàn)明明實(shí)存有空閑空間卻不得不調(diào)出一個(gè)現(xiàn)有虛頁(yè)以騰出所在實(shí)頁(yè)的情況，這使系統(tǒng)的命中率和運(yùn)行效率下降。這種映象方式主要用于對(duì)實(shí)存價(jià)格、速度敏感的Cache-主存層次。直接相聯(lián)的“候選位置”為1個(gè)實(shí)頁(yè)，它又被簡(jiǎn)稱為“1路Cache”。2014.2.1716計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第16頁(yè)!(3)組相聯(lián)(setassociative，P194)組相聯(lián)映象方式是全相聯(lián)與直接相聯(lián)的一個(gè)折中方案，性能也是二者的折中。具體做法是先將實(shí)存分組，每組內(nèi)有若干實(shí)頁(yè)，然后將虛存空間也以同樣大小分組。所有虛組按照直接相聯(lián)方式映射到實(shí)組集合，對(duì)應(yīng)的虛實(shí)組之間各頁(yè)則用全相聯(lián)映射，如下頁(yè)示意圖(a)、(b)所示（設(shè)實(shí)組數(shù)為2）。由于包含了兩層不同的映射關(guān)系，頁(yè)表須按虛組劃分成許多子表。在虛實(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)。簡(jiǎn)記為“組號(hào)計(jì)算、組內(nèi)查表”。如圖(c)所示。采用組相聯(lián)映象方式時(shí)，每個(gè)虛頁(yè)在對(duì)應(yīng)實(shí)組范圍內(nèi)有若干映象實(shí)頁(yè)可供選擇，實(shí)頁(yè)爭(zhēng)用的發(fā)生頻率比直接相聯(lián)要低；另一方面，由于頁(yè)表內(nèi)原來(lái)存放的實(shí)頁(yè)號(hào)改成存組內(nèi)頁(yè)號(hào)，省略了實(shí)組號(hào)字段，所以頁(yè)表占用空間也減少了。當(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è)表空間的效果較差，反之亦然。實(shí)際使用中可根據(jù)性能要求選取合適參數(shù)。這種映象方式性價(jià)比較好，在Cache-主存層次中被普遍使用。實(shí)組內(nèi)頁(yè)數(shù)被稱為“路數(shù)”，又稱為“相聯(lián)度”（associativity）,它表明一個(gè)虛頁(yè)的選擇范圍。下頁(yè)圖示為2路組相聯(lián)（2-waysetassociative）。2014.2.1717計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第17頁(yè)!組相聯(lián)的地址映象方式與地址變換原理(c)2014.2.1718計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第18頁(yè)!位選擇組相聯(lián)的地址映象方式與地址變換原理(a)(b)2014.2.1719計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第19頁(yè)!(1)頁(yè)表法

每個(gè)虛頁(yè)對(duì)應(yīng)1項(xiàng)，虛頁(yè)號(hào)就是項(xiàng)號(hào)，項(xiàng)內(nèi)存儲(chǔ)實(shí)頁(yè)號(hào)，如課堂練習(xí)7.2。這種方法原理簡(jiǎn)單，但是占用空間非常大。當(dāng)頁(yè)表尺寸超過1頁(yè)時(shí)，它本身還要按頁(yè)面尺寸分割成許多分散存放的子表，再造一個(gè)“表上表”來(lái)找到當(dāng)前需要的子表。進(jìn)一步發(fā)展就會(huì)形成“多級(jí)頁(yè)表”，導(dǎo)致虛實(shí)變換分多步進(jìn)行，時(shí)間大大延長(zhǎng)。7.2.3虛實(shí)變換基本方法（P195）2014.2.1720計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第20頁(yè)!(3)快慢表方法（P231）這是頁(yè)表法的一種加快方案。地址變換緩沖器TLB（TranslationLook-asideBuffer）是一個(gè)專用的高速緩沖器，用于存放近期經(jīng)常使用的頁(yè)表項(xiàng)副本，TLB利用程序的局部性原理，以小表代替大表，縮短查找時(shí)間。7.2.3虛實(shí)變換基本方法（續(xù)2）2014.2.1721計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第21頁(yè)!(5)單體多字存儲(chǔ)器＋多比較器查表方法（P196第2段）這是目錄表法的一種廉價(jià)方案，對(duì)組相聯(lián)非常適用。限制條件是組內(nèi)頁(yè)數(shù)不太多，下圖為4的情況。7.2.3虛實(shí)變換基本方法（續(xù)4）2014.2.1722計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第22頁(yè)!Cache─主存層次虛實(shí)變換實(shí)現(xiàn)（直接相聯(lián)）快命中方案：直接相聯(lián)，目錄表法（P196，圖7.9）舉例：為了方便用10進(jìn)制討論。設(shè)虛塊號(hào)=000～999，實(shí)塊號(hào)=0～9，于是有索引=0～9，而標(biāo)識(shí)=00～99。索引=0的實(shí)塊里裝的虛塊標(biāo)識(shí)可以是00，01，……，99，對(duì)應(yīng)的虛塊號(hào)就是000，010，020，030，……，990。2014.2.1723計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第23頁(yè)!7.3.5偽相聯(lián)（P209）優(yōu)點(diǎn)缺點(diǎn)直接映象組相聯(lián)命中時(shí)間小命中時(shí)間大不命中率高不命中率低“偽相聯(lián)”又稱“列相聯(lián)”，按原理還可稱為“伴生Cache”。(1)比較直接相聯(lián)、組相聯(lián)的優(yōu)缺點(diǎn)從例7.4我們將看到，直接相聯(lián)的命中時(shí)間較短，而多路組相聯(lián)的失效率較低，所以它們的平均訪問時(shí)間依兩個(gè)因素的作用大小而互有輸贏。有沒有什么方法取二者之長(zhǎng)呢？(2)偽相聯(lián)的優(yōu)點(diǎn)偽相聯(lián)就是直接相聯(lián)、組相聯(lián)的一種組合方案。優(yōu)點(diǎn)是命中時(shí)間短、不命中率還低，所以它的平均訪問時(shí)間往往比直接相聯(lián)、組相聯(lián)都短。2014.2.1724計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第24頁(yè)!(4)快速命中與慢速命中

要保證絕大多數(shù)命中都是快速命中，就是命中率要高。一種簡(jiǎn)單的辦法是在出現(xiàn)偽命中時(shí)，交換上下兩個(gè)區(qū)的內(nèi)容，因?yàn)楫?dāng)前在下區(qū)的塊很可能是“常用塊”。偽命中情況下需要增加2個(gè)額外的時(shí)鐘周期（其中1個(gè)周期是多找1次花去的，1個(gè)周期是交換操作所需）。(5)偽相聯(lián)的缺點(diǎn)：

它的多種命中時(shí)間使得CPU流水線上各指令之間的時(shí)間對(duì)齊變得困難，所以往往應(yīng)用在離CPU比較遠(yuǎn)的Cache上，比如L2-Cache。7.3.5偽相聯(lián)（續(xù)2）2014.2.1725計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第25頁(yè)!例7.3.5（補(bǔ)充，2版P198例5.6）

一個(gè)偽相聯(lián)Cache，當(dāng)在按直接映象找到的位置處沒有發(fā)現(xiàn)匹配、而在另一個(gè)位置才找到數(shù)據(jù)（偽命中）時(shí)需要增加2個(gè)額外的周期。其它已知條件如下表所示。(1)推導(dǎo)偽相聯(lián)平均訪存時(shí)間公式；(2)當(dāng)Cache容量分別為2KB和128KB時(shí)，直接映象、兩路組相聯(lián)和偽相聯(lián)這三種組織結(jié)構(gòu)中，哪一種的平均訪存時(shí)間最短？7.3.5偽相聯(lián)（續(xù)4）2014.2.1726計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第26頁(yè)!將后3式依次向前代入，得到所需公式：

平均訪存時(shí)間偽相聯(lián)＝命中時(shí)間1路＋(不命中率1路－不命中率2路)×2周期＋不命中率2路×不命中開銷1路(2)當(dāng)Cache容量為2KB時(shí)：平均訪存時(shí)間1路＝1.0＋0.098×50＝5.90平均訪存時(shí)間2路＝1.1＋0.076×50＝4.90平均訪存時(shí)間偽相聯(lián)，2KB＝1.0＋(0.098－0.076)×2＋(0.076×50)＝4.844當(dāng)Cache容量為128KB時(shí)：平均訪存時(shí)間1路＝1.0＋0.010×50＝1.50平均訪存時(shí)間2路＝1.1＋0.007×50＝1.45平均訪存時(shí)間偽相聯(lián)，128KB＝1.0＋(0.010－0.007)×2＋(0.007×50)＝1.356可見，對(duì)于這兩種Cache容量，偽相聯(lián)Cache都是速度最快的。7.3.5偽相聯(lián)（續(xù)6）2014.2.1727計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第27頁(yè)!各次作業(yè)應(yīng)交的內(nèi)容作業(yè)9（第10次課）7.112014.2.1728計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第28頁(yè)!所以在計(jì)算平均CPI時(shí)，應(yīng)該加上存儲(chǔ)器平均“不命中開銷”。本章僅考慮存儲(chǔ)器等待在平均CPI計(jì)算中的作用，暫時(shí)不考慮流水線因相關(guān)、沖突導(dǎo)致的延遲，所以上式簡(jiǎn)化寫為又被稱為以下是計(jì)算二者關(guān)系的幾組常用公式。7.2.7訪存時(shí)間對(duì)CPU性能的影響22014.2.1729計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第29頁(yè)!(4)程序執(zhí)行時(shí)間（即“CPU時(shí)間”）：a.b.c.d. (7.3)e. (7.1)f. (7.2)g.7.2.7訪存時(shí)間對(duì)CPU性能的影響42014.2.1730計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第30頁(yè)!例7.2（P204）

考慮兩種不同組織結(jié)構(gòu)的Cache：直接映象Cache和兩路組相聯(lián)Cache，

(1)理想Cache（命中率為100%）情況下的CPI為2.0，時(shí)鐘周期為2ns，平均每條指令訪存1.3次；

(2)兩種Cache容量均為64KB，塊大小都是32B；

(3)在組相聯(lián)Cache中，由于多路選擇器的存在而使CPU的時(shí)鐘周期增加到原來(lái)的1.10倍。這是因?yàn)閷?duì)Cache的訪問總是處于關(guān)鍵路徑上，對(duì)CPU的時(shí)鐘周期有直接的影響；

(4)這兩種結(jié)構(gòu)Cache的不命中開銷都是70ns（在實(shí)際應(yīng)用中，應(yīng)取整為整數(shù)個(gè)時(shí)鐘周期）；

(5)命中時(shí)間為1個(gè)時(shí)鐘周期，64KB直接映象Cache的不命中率為1.4%，相同容量的兩路組相聯(lián)Cache的不命中率為1.0%。

分別比較它們的平均訪存時(shí)間、CPU時(shí)間。2014.2.1731計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第31頁(yè)!例7.2（續(xù)2）(2)

CPU時(shí)間＝IC×（CPIexecution＋每條指令的平均訪存次數(shù)×不命中率×不命中開銷）×?xí)r鐘周期時(shí)間＝IC×（CPIexecution×?xí)r鐘周期時(shí)間＋每條指令的平均訪存次數(shù)×不命中率×不命中開銷×?xí)r鐘周期時(shí)間）代入?yún)?shù)得：CPU時(shí)間1路＝IC×(2.0×2＋(1.3×0.014×70))

＝5.27×ICCPU時(shí)間2路＝IC×(2.0×2×1.10＋(1.3×0.010×70))

＝5.31×IC直接映象Cache的CPU時(shí)間短一些。5.31×ICCPU時(shí)間1路─────＝─────＝1.015.27×ICCPU時(shí)間2路2014.2.1732計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第32頁(yè)!(1)L2-Cache采用直接相聯(lián)

平均訪問時(shí)間

＝10.0＋25%×50＝22.5

個(gè)時(shí)鐘周期(2)L2-Cache采用兩路組相聯(lián)

平均訪問時(shí)間

＝10.1＋20%×50＝20.1

個(gè)時(shí)鐘周期(3)兩路組相聯(lián)的命中時(shí)間之所以比直接相聯(lián)增加0.1個(gè)時(shí)鐘周期，是因?yàn)樘搶?shí)變換按組查表后要進(jìn)行多路選擇（P199圖7.12和P198第8段），需要額外增加時(shí)間。具體實(shí)現(xiàn)方案可以把時(shí)鐘周期調(diào)慢為1.01倍（這將使所有動(dòng)作都減慢1%，甚至主存訪問），或者僅在命中時(shí)增加1個(gè)時(shí)鐘周期。按增加1個(gè)時(shí)鐘周期的方案，L2-Cache的命中時(shí)間為11，有：

平均訪問時(shí)間＝11＋20%×50＝21.0

個(gè)時(shí)鐘周期(2)(3)情況下L2-Cache的平均訪問時(shí)間都比直接相聯(lián)小，所以L2-Cache采用兩路組相聯(lián)性能更好。注：教材中該例中說(shuō)“幸運(yùn)的話，取整為10個(gè)周期”，就是說(shuō)多路選擇動(dòng)作時(shí)間有可能“擠”進(jìn)原有的10周期中，習(xí)題中通常不這樣給條件。習(xí)題7.10例7.4（續(xù)）2014.2.1733計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第33頁(yè)!Windows2000使用基于分頁(yè)機(jī)制的虛擬內(nèi)存。每個(gè)進(jìn)程有4GB的虛擬地址空間。程序中使用的都是4GB地址空間中的虛擬地址。而訪問物理內(nèi)存，需要使用物理地址。物理內(nèi)存以字節(jié)（8位）為單位編址。物理內(nèi)存分頁(yè)，一個(gè)物理頁(yè)的大小為4K字節(jié)，第0個(gè)物理頁(yè)從物理地址0x00000000處開始。由于頁(yè)的大小為4KB，就是0x1000字節(jié)，所以第1頁(yè)從物理地址0x00001000處開始。第2頁(yè)從物理地址0x00002000處開始?？梢钥吹接捎陧?yè)的大小是4KB，所以只需要32bit的地址中高20bit來(lái)尋址物理頁(yè)。使用了分頁(yè)機(jī)制之后，4G的地址空間被分成了固定大小的頁(yè)，每一頁(yè)或者被映射到物理內(nèi)存，或者被映射到硬盤上的交換文件中，或者沒有映射任何東西。對(duì)于一般程序來(lái)說(shuō)，4G的地址空間，只有一小部分映射了物理內(nèi)存，大片大片的部分是沒有映射任何東西。物理內(nèi)存也被分頁(yè)，來(lái)映射地址空間。對(duì)于32bit的Win2k，頁(yè)的大小是4K字節(jié)。CPU用來(lái)把虛擬地址轉(zhuǎn)換成物理地址的信息存放在叫做頁(yè)目錄和頁(yè)表的結(jié)構(gòu)里。Windows2000虛擬存儲(chǔ)器12014.2.1734計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第34頁(yè)!物理地址的轉(zhuǎn)換，使用物理地址取出值，完成指令。對(duì)于IntelCPU來(lái)說(shuō)，分頁(yè)標(biāo)志位是寄存器CR0的第31位，為1表示使用分頁(yè)，為0表示不使用分頁(yè)。對(duì)于初始化之后的Win2k我們觀察CR0，發(fā)現(xiàn)第31位為1。表明Win2k是使用分頁(yè)的。

CPU把虛擬地址轉(zhuǎn)換成物理地址：一個(gè)虛擬地址，大小4個(gè)字節(jié)(32bit)，包含著找到物理地址的信息，分為3個(gè)部分：第22位到第31位這10位（最高10位）是頁(yè)目錄中的索引，第12位到第21位這10位是頁(yè)表中的索引，第0位到第11位這12位（低12位）是頁(yè)內(nèi)偏移。對(duì)于一個(gè)要轉(zhuǎn)換成物理地址的虛擬地址，CPU首先根據(jù)CR3中的值，找到頁(yè)目錄所在的物理頁(yè)。然后根據(jù)虛擬地址的第22位到第31位這10位（最高的10bit)的值作為索引，找到相應(yīng)的頁(yè)目錄項(xiàng)(PDE,pagedirectoryentry),頁(yè)目錄項(xiàng)中有這個(gè)虛擬地址所對(duì)應(yīng)頁(yè)表的物理地址。有了頁(yè)表的物理地址，根據(jù)虛擬地址的第12位到第21位這10位的值作為索引，找到該頁(yè)表中相應(yīng)的頁(yè)表項(xiàng)(PTE,pagetableentry),頁(yè)表項(xiàng)中就有這個(gè)虛擬地址所對(duì)應(yīng)物理頁(yè)的物理地址。最后用虛擬地址的最低12位，也就是頁(yè)內(nèi)Windows2000虛擬存儲(chǔ)器32014.2.1735計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第35頁(yè)!32bit的一個(gè)指針，可以尋址范圍0x00000000-0xFFFFFFFF，4GB大小。也就是說(shuō)一個(gè)32bit的指針可以尋址整個(gè)4GB地址空間的每一個(gè)字節(jié)。一個(gè)頁(yè)表項(xiàng)負(fù)責(zé)4K的地址空間和物理內(nèi)存的映射，一個(gè)頁(yè)表1024項(xiàng)，也就是負(fù)責(zé)1024*4k=4M的地址空間的映射。一個(gè)頁(yè)目錄項(xiàng)，對(duì)應(yīng)一個(gè)頁(yè)表。一個(gè)頁(yè)目錄有1024項(xiàng)，也就對(duì)應(yīng)著1024個(gè)頁(yè)表，每個(gè)頁(yè)表負(fù)責(zé)4M地址空間的映射。1024個(gè)頁(yè)表負(fù)責(zé)1024*4M=4G的地址空間映射。一個(gè)進(jìn)程有一個(gè)頁(yè)目錄。所以以頁(yè)為單位，頁(yè)目錄和頁(yè)表可以保證4G的地址空間中的每頁(yè)和物理內(nèi)存的映射。每個(gè)進(jìn)程都有自己的4G地址空間，從0x00000000-0xFFFFFFFF。通過每個(gè)進(jìn)程自己的一套頁(yè)目錄和頁(yè)表來(lái)實(shí)現(xiàn)。由于每個(gè)進(jìn)程有自己的頁(yè)目錄和頁(yè)表，所以每個(gè)進(jìn)程的地址空間映射的物理內(nèi)存是不一樣的。兩個(gè)進(jìn)程的同一個(gè)虛擬地址處（如果都有物理內(nèi)存映射）的值一般是不同的，因?yàn)樗麄兺鶎?duì)應(yīng)不同的物理頁(yè)。4G地址空間中低2G，0x00000000-0x7FFFFFFF是用戶地址空間，4G地址空間中高2G，0x80000000-0xFFFFFFFF是系統(tǒng)地址空間。訪問系統(tǒng)地址空間需要程序有ring0的權(quán)限。Windows2000虛擬存儲(chǔ)器52014.2.1736計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第36頁(yè)!7.2.5替換算法(P198)上面所講的地址映象方式是在虛頁(yè)調(diào)入時(shí)的“選址”規(guī)則，而地址變換方法則是命中時(shí)獲得實(shí)地址的手段。不命中時(shí)需要增加的操作就是首先調(diào)出一頁(yè)，調(diào)出之后再調(diào)入稱為“替換”。替換算法要解決的是選擇調(diào)出對(duì)象的問題。替換算法的目的是在發(fā)生實(shí)頁(yè)爭(zhēng)用（即根據(jù)地址映象方式，將要調(diào)入的虛頁(yè)被允許進(jìn)入的所有實(shí)頁(yè)均被其它虛頁(yè)占用）時(shí)，選擇將來(lái)不太可能使用或者使用最晚的虛頁(yè)作為調(diào)出對(duì)象，以騰出一個(gè)實(shí)頁(yè)來(lái)。2014.2.1737計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第37頁(yè)!從LFU到LRU的近似邏輯推理：近期最少使用LFU→最近一個(gè)單位時(shí)間內(nèi)使用次數(shù)最少→相鄰兩次使用的平均間隔時(shí)間最大→上次使用時(shí)間離現(xiàn)在最久→最久沒有使用LRU偶然偏差：使用稀疏的頁(yè)面有可能恰巧剛剛用過，離現(xiàn)在更近。統(tǒng)計(jì)性能：“現(xiàn)在”離“上次”使用時(shí)間的平均距離，應(yīng)為相鄰兩次使用時(shí)間距離的1/2，所以大多數(shù)情況下LRU與LFU的判斷結(jié)論應(yīng)該是一致的。2014.2.1738計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第38頁(yè)!課堂練習(xí)7.3（鄭緯民題3-19中3、4、6、8小問，稍改）假設(shè)在一個(gè)采用位選擇組相聯(lián)映象方式的Cache中，主存由B0～B7共8塊組成，Cache有2組，每組2塊，每塊的大小為16個(gè)字節(jié)，采用LRU塊替換算法。程序執(zhí)行過程中依次訪問這個(gè)Caehe的塊地址流如下：B6，B2，B4，B1，B4，B6，B3，B0，B4，B5，B7，B3(3)畫出主存與Cache之間各個(gè)塊的映象對(duì)應(yīng)關(guān)系。(4)Cache塊號(hào)記為C0、C1、C2和C3，列出程序執(zhí)行過程中Cache地址流。(6)計(jì)算Cache的塊命中率。(8)如果上述地址流中的每個(gè)塊號(hào)實(shí)際代表對(duì)該塊的連續(xù)16次訪問，計(jì)算在這種情況下的Cache命中率（也稱為存儲(chǔ)單元命中率）。2014.2.1739計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第39頁(yè)!7.2.4Cache的工作過程（P197）概況：塊大小32B，塊數(shù)256，直接映象，寫直達(dá)，采用不按寫分配2014.2.1740計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第40頁(yè)!Cache“寫”訪問2014.2.1741計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第41頁(yè)!(2)混合式（統(tǒng)一式）Cache在命中情況下，每次有效MEM操作都會(huì)迫使后面一條指令的IF停頓（結(jié)構(gòu)沖突）。分離式Cache與混合式Cache（續(xù)1）混合式Cache結(jié)構(gòu)示意圖IFIDWBMEMEX混合Cache下一級(jí)存儲(chǔ)器2014.2.1742計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第42頁(yè)!例7.5（2版P186例5.1）假設(shè)Cache的命中時(shí)間為1個(gè)時(shí)鐘周期，失效開銷為50個(gè)時(shí)鐘周期，在混合Cache中一次load或store操作訪問Cache的命中時(shí)間都要增加一個(gè)時(shí)鐘周期，根據(jù)上表所列的失效率，試問指令Cache和數(shù)據(jù)Cache容量均為16KB的分離Cache與容量為32KB的混合Cache相比，哪種Cache的失效率更低？又假設(shè)采用寫直達(dá)策略，且有一個(gè)寫緩沖器，并且忽略寫緩沖器引起的等待。請(qǐng)問上述兩種情況下平均訪存時(shí)間各是多少？解：(1)平均失效率測(cè)試表明，（經(jīng)驗(yàn)值）。平均失效率分離16KB+16KB＝(75%×0.64%)＋(25%×6.47%)＝2.10%

平均失效率混合32KB＝1.99%（查表）

混合Cache較低。分離式Cache與混合式Cache（續(xù)3）2014.2.1743計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第43頁(yè)!平均訪存時(shí)間＝命中時(shí)間＋不命中率×不命中開銷可以從三個(gè)方面改進(jìn)Cache的性能：降低不命中率減少不命中開銷減少Cache命中時(shí)間本書介紹了17種Cache優(yōu)化技術(shù)（P223表7.5）8種用于降低不命中率5種用于減少不命中開銷4種用于減少命中時(shí)間本課堂內(nèi)只了解一下其中兩個(gè)概念，細(xì)節(jié)內(nèi)容不作深入了。7.2.8改進(jìn)Cache性能（P205）2014.2.1744計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第44頁(yè)!減少三種不命中的方法強(qiáng)制性不命中：增加塊大小，預(yù)取（本身很少）容量不命中：增加容量

（抖動(dòng)現(xiàn)象）沖突不命中：提高相聯(lián)度（理想情況：全相聯(lián)）許多降低不命中率的方法會(huì)增加命中時(shí)間或不命中開銷7.3.1三種類型的不命中（續(xù)）2014.2.1745計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第45頁(yè)!7.6并行主存系統(tǒng)（非層次技術(shù)，P223）本小節(jié)不在課堂講授，供需要的同學(xué)自學(xué)。并行存儲(chǔ)器技術(shù)可以提高主存系統(tǒng)的整體等效速度，實(shí)際應(yīng)用中，常將它與存儲(chǔ)層次技術(shù)組合使用，可以互為補(bǔ)充，獲得很高的性能。并行存儲(chǔ)器技術(shù)的基本思想是用多個(gè)獨(dú)立的存儲(chǔ)部件組成主存系統(tǒng)，讓它們并行工作，在一個(gè)存儲(chǔ)周期內(nèi)可以訪問到多個(gè)數(shù)據(jù)，從而實(shí)現(xiàn)較高的存取流量。教材P224～P224介紹了3種提高主存速度的技術(shù)：1.多字寬存儲(chǔ)器；2.多體交叉存儲(chǔ)器；3.避免體沖突的軟硬件方法。下面介紹提高訪問常用的低位多體交叉訪問存儲(chǔ)器。2014.2.1746計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第46頁(yè)!主存地址與結(jié)構(gòu)參數(shù)的換算（P225）：其中：n──存儲(chǔ)體個(gè)數(shù)，A──主存地址，

j──體內(nèi)地址，k──體序號(hào)（k=0，1，2，…，n-1）例5.1已知n=4，問主存地址13是在幾號(hào)體的幾號(hào)單元？解：由于n=4，體選譯碼信號(hào)使用主存地址的最低log2n=2位，所以地址13（其二進(jìn)制為1101B）對(duì)應(yīng)的體號(hào)k=1（即01B）、體內(nèi)地址j=3（即11B），也就是說(shuō)，地址13位于1號(hào)體的3號(hào)單元（參看前一頁(yè)插圖）。 根據(jù)上式，所有k值（即體號(hào)）相同的地址之間均相差n的整倍數(shù)，稱之為“模n同余”。2014.2.1747計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第47頁(yè)!

Kg=010.0g=0.24.463.682.00g=0.51.00g=10110n并行存儲(chǔ)器平均加速倍數(shù)（西安電子科技大學(xué)李學(xué)干教材2版）1.只考慮取指地址序列（假設(shè)地址順序遞增，直至出現(xiàn)一條轉(zhuǎn)移指令）：其中g(shù)是指令序列中出現(xiàn)轉(zhuǎn)移指令的概率。此公式在右圖中用綠線表示。2.只考慮取數(shù)地址序列（假設(shè)地址完全隨機(jī)）此公式在右圖中用紅線表示。2014.2.1748計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第48頁(yè)!7.7.1存儲(chǔ)層次的管理方式(P230)根據(jù)程序的局部化性質(zhì)，存儲(chǔ)層次機(jī)構(gòu)對(duì)用戶文件的管理應(yīng)該劃分成較小的基本調(diào)度單位來(lái)進(jìn)行。依劃分標(biāo)準(zhǔn)不同，存在3種存儲(chǔ)層次管理方式。目前在主存—輔存層次實(shí)現(xiàn)中，具體機(jī)器可能采用3種方式中的某1種，而Cache-主存層次普遍只采用第2種，因?yàn)樗?jiǎn)單，便于硬件實(shí)現(xiàn)。(1)段式管理。段是程序中的一個(gè)邏輯單位，可以是一個(gè)程序模塊，或者是一個(gè)數(shù)據(jù)結(jié)構(gòu)。段的長(zhǎng)度不一，但段內(nèi)所有數(shù)據(jù)的信息屬性一般是相同的，便于統(tǒng)一進(jìn)行信息保護(hù)。每段使用獨(dú)立的邏輯地址空間，即都從0開始計(jì)算地址。段式管理方法的主要缺點(diǎn)是各段長(zhǎng)短不一，調(diào)進(jìn)調(diào)出之后容易形成大量不規(guī)則的零碎空間。段式管理方法的虛實(shí)變換算法是查段表。因其實(shí)現(xiàn)較復(fù)雜，僅用于主存—輔存層次。2014.2.1749計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第49頁(yè)!課堂練習(xí)7.1一個(gè)頁(yè)式虛擬存儲(chǔ)器按字節(jié)編址，頁(yè)面大小為1K字節(jié)，每個(gè)數(shù)據(jù)的字長(zhǎng)為4個(gè)字節(jié)?，F(xiàn)有一個(gè)程序的頁(yè)表如下：表中的裝入標(biāo)志為“1”表示該虛頁(yè)已經(jīng)裝入主存，為“0”則表示還未裝入主存。修改標(biāo)志為“0”表示該頁(yè)還沒有被修改過，為“1”則表示該頁(yè)已經(jīng)被修改過。訪問方式“RW”表示該頁(yè)可以讀可以寫，但不能作為指令來(lái)執(zhí)行；“R”表示該頁(yè)只能讀，不能寫和執(zhí)行；“X”表示該頁(yè)只能作為指令來(lái)執(zhí)行，不能讀和寫。2014.2.1750計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第50頁(yè)!7.1.3“主─輔”層次與“Cache─主存”層次的對(duì)比（P192表7.1，P231表7.7）“主存-輔存”層次目的：提高等效容量?；菊{(diào)度單位：頁(yè)，幾百Byte到幾千Byte。速度比：幾萬(wàn)倍。虛實(shí)轉(zhuǎn)換：頁(yè)表（以虛頁(yè)號(hào)為索引）“Cache-主存”層次目的：提高等效速度?；菊{(diào)度單位：塊，幾十Byte。速度比：幾倍。虛實(shí)轉(zhuǎn)換：目錄表（以實(shí)頁(yè)號(hào)為索引）2014.2.1751計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第51頁(yè)!7.1.2存儲(chǔ)層次的性能指標(biāo)（P189）先以2級(jí)存儲(chǔ)層次為例進(jìn)行公式推導(dǎo)，并且只考慮各級(jí)存儲(chǔ)器件自身的操作，忽略控制機(jī)構(gòu)的附加開銷。多級(jí)層次以及附加開銷留到以后討論。(1)容量：S=S2（理論上）(2)單價(jià)：（美分/bit）2014.2.1752計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第52頁(yè)!訪問效率e（補(bǔ)充）訪問效率e受H和r的影響（參見右圖）：

e是一個(gè)相對(duì)值，便于不同系統(tǒng)之間的比較。2014.2.1753計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第53頁(yè)!課堂練習(xí)7.2設(shè)計(jì)“Cache-主存”層次，Cache的容量有三種選擇，如上表所示。忽略平均訪存時(shí)間TA公式中的TB。(1)分別計(jì)算三種方案的等效訪問時(shí)間；(2)分別計(jì)算三種方案每KB的平均價(jià)格；(3)分別根據(jù)等效訪問時(shí)間、每KB的平均價(jià)格排序；(4)根據(jù)等效訪問時(shí)間和平均價(jià)格的乘積排序。2014.2.1754計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第54頁(yè)!多級(jí)存儲(chǔ)層次的平均訪問時(shí)間2由這2式合并得此公式參見教材P214倒數(shù)第12行。2014.2.1755計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第55頁(yè)!(1)問中，為什么？答：每當(dāng)CPU訪問M1不命中時(shí)，存儲(chǔ)系統(tǒng)會(huì)從M3裝入1000字節(jié)到M1，再?gòu)腗1取1個(gè)字節(jié)送給CPU，所以本次訪問結(jié)果為“失效”，但是緊接著的999次訪問將“命中”，以后又是如此重復(fù)，……。同學(xué)們不要把訪問“失效”理解為訪問“失敗”，認(rèn)為CPU在M1找不到數(shù)據(jù)就會(huì)放棄本次訪問?！笆А钡亩x是經(jīng)過等待后完成的訪問，而“命中”是不需要等待即完成的訪問，僅此不同。(3)問中，為什么？答：M2接受M1的數(shù)據(jù)請(qǐng)求，每次是1000字節(jié)。M2的初始狀態(tài)為“空”，對(duì)于M1的首次請(qǐng)求不能立即滿足，需要先從M3索取1000000字節(jié)數(shù)據(jù)填滿自己，再向M1提供所要的1000字節(jié)數(shù)據(jù)。這次訪問稱為“失效”。此后M1向M2發(fā)出的999次請(qǐng)求都能立即響應(yīng)，而再下一次請(qǐng)求又需要等待…。如此重復(fù)，所以H2=999/1000。例題說(shuō)明：2014.2.1756計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第56頁(yè)!因?yàn)椋核裕阂来祟愅?，…?.4.1局部不命中率與全局不命中率（續(xù)）2014.2.1757計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第57頁(yè)!例7.3考慮某一兩級(jí)Cache：級(jí)Cache為L(zhǎng)1，第二級(jí)Cache為L(zhǎng)2。(1)假設(shè)在1000次訪存中，Cache1的不命中是40次，Cache2的不命中是20次。求各種局部不命中率和全局不命中率；(2)假設(shè)Cache1的命中時(shí)間是1個(gè)時(shí)鐘周期，Cache2的命中時(shí)間是10個(gè)時(shí)鐘周期，不命中開銷是100時(shí)鐘周期，平均每條指令訪存1.5次，不考慮寫操作的影響。問：平均訪存時(shí)間是多少？每條指令的平均停頓時(shí)間（即失效開銷）是多少個(gè)時(shí)鐘周期？解：(1)級(jí)Cache的不命中率（全局和局部）是40/1000，即4%；第二級(jí)Cache的局部不命中率是20/40，即50%；第二級(jí)Cache的全局不命中率是20/1000，即2%。例7.32014.2.1758計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第58頁(yè)!各次作業(yè)應(yīng)交的內(nèi)容作業(yè)8（第9次課）7.92014.2.1759計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第59頁(yè)!7.2.2四種常見的地址映象方式（P193）(1)全相聯(lián)(fullyassociative)全相聯(lián)就是無(wú)約束對(duì)應(yīng)，或者說(shuō)是一個(gè)完全關(guān)系，意思就是一個(gè)虛頁(yè)可以調(diào)入任何一個(gè)實(shí)頁(yè)。這種關(guān)系可用下頁(yè)示意圖(a)、(b)表示。全相聯(lián)的虛實(shí)變換信息完全來(lái)自于變換表，查表過程如圖(c)所示。全相聯(lián)映象方式使虛頁(yè)調(diào)入有最大的選擇范圍，發(fā)生實(shí)頁(yè)爭(zhēng)用的可能性最小，調(diào)入/調(diào)出的操作開銷也最少，有利于命中率提高。但這種方式的頁(yè)表占用空間和查表時(shí)間開銷都比較大,也就是說(shuō)實(shí)現(xiàn)成本比較高，在命中情況下花費(fèi)在虛實(shí)變換上的時(shí)間也比較多。由于頁(yè)表必須常駐在實(shí)存中，而主存-輔存層次的實(shí)存（即主存）相對(duì)Cache-主存層次的實(shí)存（即Cache存儲(chǔ)器）容量大得多，所以全相聯(lián)映象方式一般用于主存-輔存層次。一個(gè)虛頁(yè)被允許進(jìn)入的實(shí)頁(yè)集合稱為“候選位置”（P195），全相聯(lián)的“候選位置”為整個(gè)實(shí)存。2014.2.1760計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第60頁(yè)!全相聯(lián)的地址映象方式與地址變換原理示意圖(c)2014.2.1761計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第61頁(yè)!直接相聯(lián)的地址映象方式與地址變換原理2014.2.1762計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第62頁(yè)!組相聯(lián)的地址映象方式與地址變換原理(a)(b)組相聯(lián)的“候選位置”為組內(nèi)頁(yè)數(shù)，即“路數(shù)”。2014.2.1763計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第63頁(yè)!(4)位選擇組相聯(lián)(P194圖7.7c)位選擇組相聯(lián)映象方式映象關(guān)系中，實(shí)存分組，虛存按實(shí)組數(shù)分區(qū)，區(qū)內(nèi)不分組。虛塊號(hào)與實(shí)組號(hào)之間是直接映象關(guān)系，而虛塊與該實(shí)組內(nèi)的各個(gè)實(shí)塊之間是全相聯(lián)映象方式。例如，虛塊0可以映象到實(shí)組0的任意一塊中。在一般組相聯(lián)映象方式中，一個(gè)虛組與一個(gè)實(shí)組之間是多個(gè)塊到多個(gè)塊的映象。而在位選擇組相聯(lián)映象方式中，改成了一個(gè)虛塊到實(shí)組中多個(gè)塊的映象。映象關(guān)系明顯簡(jiǎn)單，實(shí)現(xiàn)起來(lái)可以容易些。另外，從數(shù)據(jù)的分布情況看。對(duì)于一般組相聯(lián)映象方式，虛存中的幾個(gè)連續(xù)塊映象到實(shí)存中可能也是連續(xù)的，而對(duì)于位選擇組相聯(lián)映象方式，虛存中的連續(xù)塊映象到實(shí)存中肯定是不連續(xù)的，它們被分散到實(shí)存的各個(gè)組中。由于在虛存與實(shí)存之間是以塊為單位進(jìn)行調(diào)度的，而實(shí)存是以字為單位訪問的，只要實(shí)存中的一個(gè)字不跨越兩個(gè)塊，在實(shí)存內(nèi)部的塊與塊之間的分布是否連續(xù)對(duì)實(shí)存的正常工作是沒有關(guān)系的。由于虛存每個(gè)區(qū)中的塊數(shù)與實(shí)組數(shù)相等，而且它們之間采用直接映象方式，因此，虛存地址中的區(qū)內(nèi)塊號(hào)可以直接作為實(shí)組號(hào)。位選擇組相聯(lián)的地址變換過程比一般組相聯(lián)映象方式簡(jiǎn)單，而與全相聯(lián)映象方式基本相同。2014.2.1764計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第64頁(yè)!位選擇組相聯(lián)的地址映象方式與地址變換原理(c)2014.2.1765計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第65頁(yè)!(2)部分虛實(shí)表法（P195圖7.8）

這是一種統(tǒng)稱，指表項(xiàng)數(shù)少于虛頁(yè)數(shù)的情形，下面要介紹的3種方法都屬于這一類。（與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ù)的原因。

表項(xiàng)數(shù)少于虛頁(yè)數(shù)的做法既是節(jié)省成本的需要，也符合任何時(shí)刻只有少部分虛頁(yè)占用實(shí)存的實(shí)際，問題是每個(gè)表項(xiàng)必須說(shuō)明它當(dāng)前記錄的是一組共享虛頁(yè)中的哪一個(gè)的信息，這就要用到“標(biāo)識(shí)”字段。虛頁(yè)號(hào)里用于計(jì)算表內(nèi)地址的部分稱為“索引”index，用來(lái)與查表內(nèi)容相比較的部分稱為“標(biāo)識(shí)”tag。下圖以組相聯(lián)為例說(shuō)明“標(biāo)識(shí)”的意義，它有16個(gè)虛頁(yè)，只用4個(gè)表項(xiàng)。7.2.3虛實(shí)變換基本方法（續(xù)1）2014.2.1766計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第66頁(yè)!(4)目錄表法（P196第1段）

只對(duì)已經(jīng)裝入實(shí)存的虛頁(yè)造表，其項(xiàng)數(shù)比頁(yè)表少得多。為避免逐行比對(duì)，須使用相聯(lián)存儲(chǔ)器來(lái)存放，通過并行比較實(shí)現(xiàn)一次查遍，器件價(jià)格遠(yuǎn)高于普通存儲(chǔ)器。7.2.3虛實(shí)變換基本方法（續(xù)3）2014.2.1767計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第67頁(yè)!主─輔層次虛實(shí)變換實(shí)現(xiàn)主流方案：全相聯(lián)，頁(yè)表法（P232）2014.2.1768計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第68頁(yè)!Cache─主存層次虛實(shí)變換實(shí)現(xiàn)（組相聯(lián)）低失效方案：位選擇組相聯(lián)（2路），目錄表法（P196，圖7.9）2014.2.1769計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第69頁(yè)!(3)基本思想及工作原理

在邏輯上把直接相聯(lián)Cache的空間分為上、下兩個(gè)區(qū)。對(duì)于任何一次訪問，偽相聯(lián)Cache先按直接相聯(lián)Cache的方式去處理。若命中，則其訪問過程與直接相聯(lián)Cache的情況一樣。若不命中，則再到另一區(qū)相應(yīng)的位置去查找。若找到，則發(fā)生了偽命中。再找不到就只好訪問下一級(jí)存儲(chǔ)器。

顯然偽相聯(lián)的“候選位置”=2，與2路組相聯(lián)相同。

每次訪問時(shí)間有3種可能：正常命中（快速命中）偽命中（慢速命中）不命中7.3.5偽相聯(lián)（續(xù)1）2014.2.1770計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第70頁(yè)!7.3.5偽相聯(lián)（續(xù)3）折中方案：偽相聯(lián)（2路），目錄表法（P209）2014.2.1771計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第71頁(yè)!解：(1)首先按通用形式寫出偽相聯(lián)的平均訪存時(shí)間公式：平均訪存時(shí)間偽相聯(lián)＝平均命中時(shí)間偽相聯(lián)＋不命中率偽相聯(lián)×不命中開銷偽相聯(lián)

然后根據(jù)偽相聯(lián)原理，可以寫出其中的：

平均命中時(shí)間偽相聯(lián)＝命中時(shí)間1路＋偽命中率偽相聯(lián)×2周期

由于偽相聯(lián)不命中時(shí)，就是2個(gè)候選位置都不命中，所以：

不命中率偽相聯(lián)＝不命中率2路

又由于偽相聯(lián)的2個(gè)候選位置命中率之和等于2路組相聯(lián)，所以：

偽命中率偽相聯(lián)＝命中率2路－命中率1路

＝(1－不命中率2路)－(1－不命中率1路)

＝不命中率1路－不命中率2路7.3.5偽相聯(lián)（續(xù)5）2014.2.1772計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第72頁(yè)!結(jié)論：從不命中率看，F(xiàn)2路=F偽相聯(lián)<F1路，偽相聯(lián)因不命中帶來(lái)的平均延時(shí)與2路一樣短（1路較長(zhǎng)）；從命中時(shí)間看，偽相聯(lián)在正常命中時(shí)與1路一樣短（2路較長(zhǎng)），偽命中時(shí)要增加2拍，后者概率=H2路–H1路。這種情況下1路要增加50拍。代入2KB、128KB容量的數(shù)據(jù)，算出平均訪存時(shí)間TA都是偽相聯(lián)最短。缺點(diǎn)：多種命中時(shí)間習(xí)題：7.117.3.5偽相聯(lián)（續(xù)7）2014.2.1773計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第73頁(yè)!衡量訪存時(shí)間是否合適的主要標(biāo)準(zhǔn)是處理機(jī)速度，具體說(shuō)是處理機(jī)分配來(lái)讀/寫存儲(chǔ)器的時(shí)間長(zhǎng)短。處理機(jī)速度越高要求訪存時(shí)間越短。衡量處理機(jī)速度的常用標(biāo)準(zhǔn)是CPI，因?yàn)樗c程序執(zhí)行時(shí)間成正比。

對(duì)順序執(zhí)行的處理機(jī)，CPI定義為每條指令執(zhí)行所需的平均周期數(shù)。對(duì)流水執(zhí)行的處理機(jī)，CPI定義為相鄰兩條指令啟動(dòng)時(shí)間相差的平均周期數(shù)。我們現(xiàn)在只關(guān)心流水處理機(jī)。

下圖說(shuō)明訪存等待（不命中）會(huì)延長(zhǎng)瞬時(shí)CPI。7.2.7訪存時(shí)間對(duì)CPU性能的影響1（P203）IFIDEXMemWBstallIFIDEXMemWBIFIDEXMemWBIFIDEXMemWBIFIDEXMemWBCPI=1CPI=22014.2.1774計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第74頁(yè)!(1)第i級(jí)的不命中率：特殊地，F(xiàn)1又可以記為F，因?yàn)镸1被訪問次數(shù)就是CPU的總訪存次數(shù)。(2)存儲(chǔ)系統(tǒng)的平均訪問時(shí)間（從CPU看）：其中H1～Hn是來(lái)自互斥事件的完備群，它們滿足關(guān)系式：注意該公式忽略了各級(jí)之間的傳送時(shí)間。(3)第i級(jí)的平均訪問時(shí)間：其中Ti是第i級(jí)的命中時(shí)間，TMi是第i級(jí)的失效開銷時(shí)間。7.2.7訪存時(shí)間對(duì)CPU性能的影響32014.2.1775計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第75頁(yè)!例7.1（P204）

假設(shè)Cache不命中開銷為50個(gè)時(shí)鐘周期，當(dāng)不考慮存儲(chǔ)器停頓時(shí)，所有指令的執(zhí)行時(shí)間都是2.0個(gè)時(shí)鐘周期，訪問Cache不命中率為2%，平均每條指令訪存1.33次。比較有Cache與無(wú)Cache情況下的CPU時(shí)間。解：已知TA1=2.0，即理想CPI=2.0，TA2=50，F(xiàn)=2%，平均每條指令訪存1.33次CPU時(shí)間有cache＝IC×（CPIexecution＋每條指令的平均訪存次數(shù)×不命中率×不命中開銷）×?xí)r鐘周期時(shí)間＝IC×（2.0＋1.33×2%×50）×?xí)r鐘周期時(shí)間＝IC×3.33×?xí)r鐘周期時(shí)間從此式知，實(shí)際CPI＝2.0＋1.33×2%×50＝3.33，是理想情況下的3.33/2.0＝1.67(倍)，換言之，CPU時(shí)間是理想情況下的1.67倍。

若不采用Cache，則每次訪存增加50個(gè)時(shí)鐘周期，每條指令的周期數(shù)為：CPI無(wú)cache＝2.0＋1.33×50＝68.5，是理想情況下的68.5/2.0＝34.25倍！2014.2.1776計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第76頁(yè)!例7.2（續(xù)1）解：摘要：理想CPI=2，不命中開銷=70ns，每條指令訪存1.3次，F(xiàn)直接=1.4%，F(xiàn)組=1.0%，Cycle直接=2ns，Cycle組=2.2ns。比較直接映象Cache（即1路）與2路組相聯(lián)Cache的平均訪存時(shí)間、CPU時(shí)間。(1)平均訪存時(shí)間為：平均訪存時(shí)間＝命中時(shí)間＋不命中率×不命中開銷因此，兩種結(jié)構(gòu)的平均訪存時(shí)間分別是：

平均訪存時(shí)間1路＝2.0＋（0.014×70）＝2.98ns

平均訪存時(shí)間2路＝2.0×1.10＋（0.010×70）＝2.90ns

兩路組相聯(lián)Cache的平均訪存時(shí)間短一些。2014.2.1777計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第77頁(yè)!

欲設(shè)計(jì)一個(gè)L2-Cache，已知它的不命中開銷L2＝50個(gè)時(shí)鐘周期，問下列兩種映像方式對(duì)不命中開銷有何影響。

(1)L2-Cache采用直接相聯(lián)，局部不命中率L2＝25%，命中時(shí)間L2＝10個(gè)時(shí)鐘周期；

(2)L2-Cache采用兩路組相聯(lián)，局部不命中率L2＝20%，命中時(shí)間L2＝10.1個(gè)時(shí)鐘周期。解：（此例與P204的例7.2參數(shù)相似，注意區(qū)別）

題目已經(jīng)給出了L2-Cache恒定的“不命中開銷L2”，那么它的不同映像方式影響的只能是L1-Cache的不命中開銷，根據(jù)多級(jí)存儲(chǔ)層次原理，TM1＝M2的平均訪問時(shí)間。所以本題實(shí)質(zhì)上是問哪種映像方式下L2-Cache的平均訪問時(shí)間較小。

另外，在不使用L3-Cache情況下，“不命中開銷L2＝50個(gè)時(shí)鐘周期”意思是“主存平均訪問時(shí)間＝50個(gè)時(shí)鐘周期”。例7.4（P216）2014.2.1778計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第78頁(yè)!各次作業(yè)應(yīng)交的內(nèi)容作業(yè)10（第11次課）7.102014.2.1779計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第79頁(yè)!頁(yè)表———一個(gè)頁(yè)表的大小為4K字節(jié)，放在一個(gè)物理頁(yè)中。由1024個(gè)4字節(jié)的頁(yè)表項(xiàng)組成。頁(yè)表項(xiàng)的大小為4個(gè)字節(jié)(32bit)，所以一個(gè)頁(yè)表中有1024個(gè)頁(yè)表項(xiàng)。頁(yè)表中的每一項(xiàng)的內(nèi)容（每項(xiàng)4個(gè)字節(jié),32bit）高20bit用來(lái)放一個(gè)物理頁(yè)的物理地址，低12bit放著一些標(biāo)志。頁(yè)目錄———一個(gè)頁(yè)目錄大小為4K字節(jié)，放在一個(gè)物理頁(yè)中。由1024個(gè)4字節(jié)的頁(yè)目錄項(xiàng)組成。頁(yè)目錄項(xiàng)的大小為4個(gè)字節(jié)(32bit)，所以一個(gè)頁(yè)目錄中有1024個(gè)頁(yè)目錄項(xiàng)。頁(yè)目錄中的每一項(xiàng)的內(nèi)容（每項(xiàng)4個(gè)字節(jié)）高20bit用來(lái)放一個(gè)頁(yè)表（頁(yè)表放在一個(gè)物理頁(yè)中）的物理地址，低12bit放著一些標(biāo)志。對(duì)于x86系統(tǒng)，頁(yè)目錄的物理地址放在CPU的CR3寄存器中。如果CPU寄存器中的分頁(yè)標(biāo)志位被設(shè)置，那么執(zhí)行內(nèi)存操作的機(jī)器指令時(shí)，CPU會(huì)自動(dòng)根據(jù)頁(yè)目錄和頁(yè)表中的信息，把虛擬地址轉(zhuǎn)換成物理地址，完成該指令。比如moveax,004227b8h，這是把地址004227b8h處的值賦給寄存器的匯編代碼，004227b8這個(gè)地址就是虛擬址。CPU在執(zhí)行這行代碼時(shí)，發(fā)現(xiàn)寄存器中的分頁(yè)標(biāo)志位已經(jīng)被設(shè)定，就自動(dòng)完成虛擬地址到Windows2000虛擬存儲(chǔ)器22014.2.1780計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第80頁(yè)!偏移，加上這個(gè)物理頁(yè)的物理地址，就得到了該虛擬地址所對(duì)應(yīng)的物理地址。一個(gè)頁(yè)目錄有1024項(xiàng)，虛擬地址最高的10bit剛好可以索引1024項(xiàng)（2的10次方等于1024）。一個(gè)頁(yè)表也有1024項(xiàng)，虛擬地址中間部分的10bit，剛好索引1024項(xiàng)。虛擬地址最低的12bit（2的12次方等于4096），作為頁(yè)內(nèi)偏移，剛好可以索引4KB，也就是一個(gè)物理頁(yè)中的每個(gè)字節(jié)。一個(gè)虛擬地址轉(zhuǎn)換成物理地址的計(jì)算過程就是，處理器通過CR3找到當(dāng)前頁(yè)目錄所在物理頁(yè)，取虛擬地址的高10bit,然后把這10bit右移2bit（因?yàn)槊總€(gè)頁(yè)目錄項(xiàng)4個(gè)字節(jié)長(zhǎng)，右移2bit相當(dāng)于乘4）得到在該頁(yè)中的地址，取出該地址處PDE（4個(gè)字節(jié)），就找到了該虛擬地址對(duì)應(yīng)頁(yè)表所在物理頁(yè)，取虛擬地址第12位到第21位這10位，然后把這10bit右移2bit（因?yàn)槊總€(gè)頁(yè)表項(xiàng)4個(gè)字節(jié)長(zhǎng)，右移2bit相當(dāng)于乘4）得到在該頁(yè)中的地址，取出該地址處的PTE（4個(gè)字節(jié)），就找到了該虛擬地址對(duì)應(yīng)物理頁(yè)的地址，最后加上12bit的頁(yè)內(nèi)偏移得到了物理地址。Windows2000虛擬存儲(chǔ)器42014.2.1781計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第81頁(yè)!Windows2000虛實(shí)變換示意圖2014.2.1782計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第82頁(yè)!幾種常用的替換算法(1)隨機(jī)算法RAND──在比較范圍內(nèi)任取一頁(yè)作為淘汰頁(yè)；(2)先進(jìn)先出算法FIFO──在比較范圍內(nèi)選取調(diào)入最早的一頁(yè)作為淘汰頁(yè)；(3)最不經(jīng)常使用算法LFU──在比較范圍內(nèi)選取最近一個(gè)單位時(shí)間內(nèi)使用次數(shù)最少的一頁(yè)作為淘汰頁(yè)；(4)最不接近使用算法LRU──在比較范圍內(nèi)選取最后一次使用離現(xiàn)在最久的一頁(yè)作為淘汰頁(yè)。2014.2.1783計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案共94頁(yè)，您現(xiàn)在瀏覽的是第83頁(yè)!算法模擬：實(shí)存狀況圖(清華教材圖3.32)以下是FIFO、L