1、 計算機系統結構(第2版) 鄭偉明 湯志忠 編著清華大學出版社習題解答1 目錄1.1 第一章(P33)1.7-1.9（透明性概念），1.12-1.18（Amdahl定律），1.19、1.21、1.24（CPI/MIPS）1.2 第二章(P124)2.3、2.5、2.6（浮點數性能），2.13、2.15（指令編碼）1.3 第三章(P202)3.3（存儲層次性能），3.5（并行主存系統），3.15-3.15加1題（堆棧模擬），3.19中(3)(4)(6)(8)問（地址映象/替換算法-實存狀況圖）1.4 第四章(P250)4.5（中斷屏蔽字表/中斷過程示意圖），4.8（通道流量計算/通道時間圖）1.

2、5 第五章(P343)5.9（流水線性能/時空圖），5.15（2種調度算法）1.6 第六章(P391)6.6（向量流水時間計算），6.10（Amdahl定律/MFLOPS）1.7 第七章(P446)7.3、7.29（互連函數計算），7.6-7.14（互連網性質），7.4、7.5、7.26（多級網尋徑算法），7.27（尋徑/選播算法）1.8 第八章(P498)8.12（SISD/SIMD算法）1.9 第九章(P562)9.18（SISD/多功能部件/SIMD/MIMD算法）(注：每章可選1-2個主要知識點，每個知識點可只選1題。有下劃線者為推薦的主要知識點。)2 例, 習題2.1 第一章(P33

3、)例1.1,p10假設將某系統的某一部件的處理速度加快到10倍,但該部件的原處理時間僅為整個運行時間的40%，則采用加快措施后能使整個系統的性能提高多少？解：由題意可知：Fe=0.4, Se=10，根據Amdahl定律 例1.2,p10采用哪種實現技術來求浮點數平方根FPSQR的操作對系統的性能影響較大。假設FPSQR操作占整個測試程序執行時間的20%。一種實現方法是采用FPSQR硬件，使FPSQR操作的速度加快到10倍。另一種實現方法是使所有浮點數據指令的速度加快，使FP指令的速度加快到2倍，還假設FP指令占整個執行時間的50%。請比較這兩種設計方案。解：分別計算出這兩種設計方案所能得到的加

4、速比：Fe FPSQR=0.20,Se FPSQR=10Fe FP=0.50,Se FP=2例1.3,p11如果FP操作的比例為25%，FP操作的平均CPI=4.0，其它指令的平均CPI為1.33，FPSQR操作的比例為2%， FPSQR的CPI為20。假設有兩種設計方案，分別把FPSQR操作的CPI和所有FP操作的CPI減為2。試利用CPU性能公式比較這兩種設計方案哪一個更好(只改變CPI而時鐘頻率和指令條數保持不變)。解：原系統的CPIFP=4.0, =25%CPI2=1.33, =1-25%CPI原 = CPIFP + CPI2=4.025% + 1.3375%=2方案1（使FPSQR操

5、作的CPI為2）系統 CPI=CPI原 - CPIFPSQR原 + CPIFPSQR新=CPI原 - （CPIFPSQR原 - CPIFPSQR新）=2-2%（20-2）=1.64方案2（提高所有FP指令的處理速度, 使FPSQR操作的CPI為2）CPI=CPI原 - CPIFP原 + CPIFP新=CPI原 - （CPIFP原 - CPIFP新）=2-25% （4-2）=1.5我們也可以根據以下公式計算出方案2系統（同求CPI原）CPI= 75%1.33+25%2=1.5顯然，提高所有FP指令處理速度的方案要比提高FPSQR處理速度的方案要好。方案2的加速比=2/1.5=1.33例1.4假設

6、兩臺機器的指令系統中，執行條件轉移指令需2個時鐘周期，而其它指令只需1個時鐘周期。CPUA:采用一條比較指令來設置相應的條件碼，由緊隨其后的一條轉移指令對此條件碼進行測試，以確定是否進行轉移。顯然實現一次條件轉移要執行比較和測試兩條指令。條件轉移指令占總執行指令條數的20%。由于每條轉移指令都需要一條比較指令，所以比較指令也將占20%。CPUB采用比較功能和判別是否實現轉移功能合在一條指令的方法，這樣實現一條件轉移就只需一條指令就可以完成。由于CPUB在轉移指令中包含了比較功能，因此它的時鐘周期就比CPUA要慢25%。現在要問，采用不同轉移指令方案的CPUA和CPUB，那個工作速度會更快些？解

7、：CPIA=0.22+0.81=1.2TCPUA=ICA1.2tA= 1.2 ICAtACPUB轉移指令占20%80%=25%CPIB = 0.252+0.751=1.25由于CPUB中沒有比較指令，因此ICB = 0.8ICACPUB時鐘周期就比CPUA要慢25%tB = 1.25tATCPUB = ICBCPIBtB = 0.8 ICA1.251.25tA = 1.25 ICAtATCPUATCPUB所以CPUB比CPUA運行得更快些。例1.A1計算Pentium II 450(IPC2)處理機的運算速度。解：由于PentiumII 450處理機的IPC2 (或CPI0.5)Fz450MH

8、z，MIPSPentium II 450FzIPC450 MHz2900(MIPS)例1.A2我國最早研制的小型計算機DJS-130，定點16位，加法每秒50萬次，但沒有硬件乘法和除法指令,用軟件實現乘法和除法，速度低100倍左右。求等效速度。解：定點等效速度為：即每秒2萬次，由于乘法和除法用軟件實現，等效速度降低了25倍。例1.A3假設在程序中浮點開平方操作FPSQR的比例為2，它的CPI為100；其他浮點操作FP的比例為23，它的CPI 4.0；其余75指令的CPI1.33，計算該處理機的等效CPI。如果FPSQR操作的CPI也為4.0，重新計算等效CPI。解：等效CPI10024231.

9、33753.92等效CPI24251.33752.001.1解釋下列術語層次結構，計算機系統結構，計算機組成，計算機實現，透明性，由上而下設計，由下而上設計，由中間向兩邊設計，軟件兼容，向上兼容，固件，系列機，兼容機，模擬，仿真，虛擬機，宿主機，指令流，數據流，單指令流單數據流，多指令流多數據流，Amdahl定律，CPI，MIPS，MFLOPS。1.2每一級為了執行一條指令需要下一級的N條指令解釋，若執行第一級的一條指令需kns，那么執行第2級、第3級、第4級的指令需要多少時間？第1級 1條1級指令 k ns第2級 1條2級指令 N條1級指令 1Nk ns = Nk ns第3級 1條3級指令

10、N條2級指令 1NNk ns = N2k ns第4級 1條4級指令 N條3級指令 1NNNk ns = N3k ns1.4每一級指令能完成下一級的M條指令的工作量，且每一級指令需要下一級的N條指令解釋，若執行第一級的一條指令需kns，那么執行第2級、第3級、第4級的等效程序需要多少時間？第1級 1條1級指令 k ns第2級 等效程序為1/M條2級指令 需N/M條1級指令解釋 N/Mk ns第3級 等效程序為1/M/M條3級指令 需NN/M/M條1級指令解釋 N2/M2 ns第4級 等效程序為1/M/M/M條4級指令 需NNN/M/M/M條1級指令解釋 N3/M3 ns1.6試以實例說明計算機系

11、統結構、計算機組成與計算機實現之間的相互關系與相互影響。系統結構、組成和實現是三個不同的概念，它們各自包含不同的內容，但又有緊密的關系。以存儲系統為例，主存儲器容量和尋址方式的確定屬計算機系統結構，主存的速度應多高，在邏輯結構上采用什么措施屬計算機組成，而主存的物理實現，如存儲器采用什么樣器件，邏輯電路設計和微組裝技術則屬計算機實現。1.7什么是透明性概念？對計算機系統結構，下列哪些是透明的？哪些是不透明的？n 存貯器的模m交叉存取；透明（組成）n 浮點數據表示；不透明（系統結構）n I/O系統是采用通道方式還是I/O處理機方式；不透明n 數據總線寬度；透明（組成）n 陣列運算部件；透明（組成

12、）n 通道是采用結合型的還是獨立型的；透明（組成）n PDP-11系列中的單總線結構；不透明（系統結構）n 訪問方式保護；不透明（系統結構）n 程序性中斷；不透明（系統結構）n 串行、重疊還是流水控制方式；透明（組成）n 堆棧指令；存貯最小編址單位；不透明（系統結構）n Cache存貯器。透明（組成）(1)從指定角度來看，不必要了解的知識稱為透明性概念。(2)見下表，“”為透明性概念。模m交叉，浮點數據，P4通道與I/O處理機，P4總線寬度，陣列運算部件，結合型與獨立型通道，單總線，訪問保護，中斷，指令控制方式，堆棧指令，最小編址單位，Cache存儲器，1.8從機器（匯編）語言程序員看，以下哪

13、些是透明的？n 指令地址寄存器；指令緩沖器；時標發生器；條件碼寄存器；乘法器；主存地址寄存器；磁盤外設；先行進位鏈；移位器；通用寄存器；中斷字寄存器。見下表，“”為透明性概念指令地址寄存器，指令緩沖器，時標發生器，條件碼寄存器，乘法器，主存地址寄存器，磁盤，先行進位鏈，移位器，通用寄存器 ，中斷字寄存器，1.9見下表，“”表示都透明，“應”表示僅對應用程序員透明，“”表示都不透明。數據通路寬度，虛擬存儲器，應，Cache存儲器，程序狀態字，“啟動I/O”指令，應，“執行”指令，指令緩沖寄存器，1.12如果某一計算任務用向量方式求解比用標量方式求解要快20倍，稱可用向量方式求解部分所花費時間占總

14、的時間的百分比為可向量化百分比。請畫出加速比與可向量化比例兩者關系的曲線。解：可向量化百分比為Fe, Se=20，根據Amdahl定律 將Se代入Amdahl定律得1.13在題1.12中，為達到加速比2， 可向量化的百分比應為多少？=2則可向量化的百分比Fe=0.5261.14在題1.12中，為獲得采用向量方式最大加速比的半值（即10）時，所需可向量化的百分比為多少。=10則可向量化的百分比Fe=0.9471.15在題1.12中，如果某程序可向量化部分為70%，硬件設計組認為可以通過加大工程投資，使向量處理速度加倍來進一步增加性能；而編譯程序編寫組認為只需設法增加向量工作方式的百分比就同樣可使

15、性能得到相同的提高，問：此時需使可向量化成分再增加多少百分比就可實現。你認為上述硬、軟件兩種方法中，哪一種方法更好？(1)用硬件組方法，已知Se=2 X 20 =40，Fe=0.7解出Sn=40/12.73.1496(2)用軟件組方法，已知Se=20，得到硬件組方法的相同性能Sn=40/12.7解出Fe=27.3/380.7184(3)結論：軟件組方法更好。因為硬件組需要將Se再提高100%（2040），而軟件組只需將Fe再提高1.84%（0.70.7184）。1.16某計算機的高速小容量存儲器能存儲2000條指令。假設10的指令承擔了90%的指令訪問且對這10的指令的使用是均勻的（即其中每條

16、指令的執行時間相同）。如果要執行的某程序共有50 000條指令且已知其中的10%是頻繁使用的，則當該計算機執行該程序時，在高速小容量存儲器中能訪問到的指令會占多少百分比？解: 對該應用程序來說，在90%的時間里，只有50000*10%=5000條指令在運行，其他的45000條指令的平均運行次數很少，因此，可以假設對它們來說，Cache總是缺失的 對頻繁訪問的這10%的指令，假設它們訪問均勻，這樣，Cache的行為便可以認為是均勻覆蓋了這些指令所以，10的指令承擔了90%的指令訪問, 指令訪問次數(50000*10%)/90%命中次數2000Cache的命中率為：H=2000/(50000*10

17、%)/90%=0.361.17假設高速緩存Cache 工作速度為主存的5倍，且Cache被訪問命中的概率為90%，則采用Cache后，能使整個存儲系統獲得多高的加速比？解：1.18設計指令存儲器有兩種不同方案：一是采用價格較貴的高速存儲器芯片，另一是采用價格便宜的低速存儲芯片。采用后一方案時，用同樣的經費可使存儲器總線帶寬加倍，從而每隔2個時鐘周期就可取出2條指令（每條指令為單字長32位）；而采用前一方案時，每個時鐘周期存儲器總線僅取出1條單字長指令。由于訪存空間局部性原理，當取出2個指令字時，通常這2個指令字都要使用，但仍有25%的時鐘周期中，取出的2個指令字中僅有1個指令字是有用的。試問采

18、用這兩種實現方案所構成的存儲器帶寬為多少？解：方案一：采用高速緩沖存儲器，使每個時鐘周期存儲器總線取出1條指令，則 存儲器帶寬=1字/時鐘周期=32位/時鐘周期方案二：使存儲器總線帶寬加倍，從而每隔2個時鐘周期就可取出2條指令（每條指令為單字長32位），但仍有25%的時鐘周期中，取出的2個指令字中僅有1個指令字是有用的，則1.19用一臺40MHz處理機執行標準測試程序，它含的混合指令數和相應所需的時鐘周期數如下：指令類型 指令數 時鐘周期數 整數運算 45000 1數據傳送 32000 2浮點 15000 2控制傳送 8000 2求有效CPI、MIPS速率和程序的執行時間。1.20某工作站采用

19、時鐘頻率為15MHz、處理速率為10MIPS的處理機來執行一個已知混合程序。假定每次存儲器存取為1周期延遲、試問：(a) 此計算機的有效CPI是多少？(b) 假定將處理機的時鐘提高到30MHz，但存儲器子系統速率不變。這樣，每次存儲器存取需要兩個時鐘周期。如果30%指令每條只需要一次存儲存取，而另外5%每條需要兩次存儲存取，還假定已知混合程序的指令數不變，并與原工作站兼容，試求改進后的處理機性能。 解：(a) f=15MHz , MIPS=10, 每次存取時間為2個時鐘周期(b)30%指令每條只需要一次存儲存取，改進前共需1周期，改進后共需2周期而另外5%每條需要兩次存儲存取，改進前共需2周期

20、，改進后共需4周期1.21假設在一臺40MHz處理機上運行200000條指令的目標代碼，程序主要由四種指令組成。根據程序跟蹤實驗結果，已知指令混合比和每種指令所需的指令數如下：指令類型 CPI 指令混合比算術和邏輯 1 60%高速緩存命中的加載/存儲 2 18%轉移 4 12%高速緩存缺失的存儲器訪問 8 10%(a) 計算在單處理機上用上述跟蹤數據運行程序的平均CPI(b) 根據(a)所得CPI，計算相應的MIPS速率。解：(1)(2)1.24假定你是一個計算機設計者，對高級語言結構的使用研究表明，過程調用是最常用的操作之一。你已設想了一個優化設計方案，它能減少過程調用和返回所需的取/存指令

21、次數。為了進行驗證，對未加優化和已優化的方案進行實驗測試，假定所使用的是相同的優化編譯器。實驗測得的結果如下：(1)未優化的時鐘周期比優化的快5%；(2)未優化方案中的取/存指令數占總指令數的30%；(3)優化方案中的取/存指令數比未優化的少1/3，對于其他指令，兩種方案的動態執行數沒有變化；(4)所有指令，包括取/存指令，均只需要1個時鐘周期。要求你定量地判斷，哪一種設計方案的計算機工作速度更快。解：記新方案時鐘周期為Tc，已知CPI = CPIi = 1原時間 = CPI IC 0.95Tc = 0.95ICTc新時間 = （0.32/3+0.7） IC Tc = 0.9ICTc二者比較，

22、新時間較短。1.A1某臺計算機只有Load/Store 指令能對存儲器進行讀/寫操作，其它指令只對寄存器進行操作。根據程序跟蹤實驗結果，已知每種指令所占的比例及CPI數如下：指令類型 指令所占比例 CPI 算邏指令 43 1 Load指令 21 2 Store指令 12 2 轉移指令 24 2 (1) 求上述情況下的平均CPI。(2) 假設程序有M條指令組成。算邏運算中25%的指令的兩個操作數中的一個已在寄存器中，另一個必須在算邏指令執行前用Load指令從存儲器取到寄存器。因此有人建議增加另一種算邏指令，其特點是一個操作數取自寄存器，另一個操作數取自存儲器，即寄存器存儲器類型，假設這種指令的C

23、PI等于2。同時，轉移指令的CPI變為3。求新指令系統的平均CPI。解：(1)CPI舊(0.4310.2120.122+0.242)=1.57 (2)原算邏指令中的25變成了寄存器存儲器型指令，所以算邏指令(寄存器寄存器型)少了(0.250.43)M 條，Load指令少了(0.250.43)M 條，而(0.250.43)M 條的新指令為寄存器存儲器型指令。指令總數少了(0.2543%)M條。設執行算邏指令(寄存器寄存器型) 、 Load指令、算邏指令(寄存器存儲器型) 、 Store指令和轉移指令的周期總數分別為C1，C2，C3，C4，C5，所以:C1=(0.43-(0.250.43)M1=0

24、.3225MC2=(0.21-(0.250.43)M2=0.205MC3=(0.250.43)M2=0.215MC4=0.12M2=0.24MC5=0.243M=0.72M新指令總數N=（1-(0.250.43)）M=0.892CPI新=（C1+C2+C3+C4+C5）/ N=1.7025M/0.8925M=1.9081.A2計算機系統中有三個部件可以改進，這三個部件的部件加速比如下：部件加速比1=30部件加速比2=20部件加速比3=10（1）如果部件1和部件2的可改進比例均為30%，那么當部件3的可改進比例為多少時，系統加速比才可以達到10？（2）如果三個部件的可改進比例分別為30%、30%

25、和20%，三個部件同時改進，那么系統中不可加速部分的執行時間在總執行時間中占的比例是多少？（3）如果相對某個測試程序三個部件的可改進比例分別為20%，20%和70%，要達到最好改進效果，僅對一個部件改進時，要選擇哪個部件？如果允許改進兩個部件，又如何選擇？1.A3在某個程序中，簡單指令占80%，復雜指令占20%，在CISC機中簡單指令執行需4個機器周期，復雜指令執行需8個機器周期。RISC機中簡單指令執行只需1個機器周期，而復雜指令要通過一串指令來實現。假定復雜指令平均需要14條簡單指令，即需要14個周期，若該程序中需要執行的總指令數為1 000 000，Tc為100ns，那么（1）RISC機

26、需執行的指令數為多少？（2）CISC和RISC機的CPU時間分別為多少？（3）RISC機對CISC的加速比為多少？2.2 第二章(P124)2.3忽略P124倒1行 P125第8行文字，以簡化題意）已知2種浮點數，求性能指標。 此題關鍵是分析階碼、尾數各自的最大值、最小值。 原圖為數據在內存中的格式，階碼的小數點在其右端，尾數的小數點在其左端，遵守規格化要求。 由于尾數均為原碼，原碼的絕對值與符號位無關，所以最大正數與最小負數的絕對值相同，可用“最大絕對值”回答；最小正數與最大負數的絕對值相同，可用“最小絕對值”回答。 第1小問中，階碼全部位數為8，作無符號數看待真值為0255，作移-127碼

27、看待真值為-127+128；尾數（不計符號位）有23位小數，另加1位整數隱藏位，所以尾數絕對值為1.02.0 2-23，有效位數p=24； 第2小問中，階碼全部位數為11，作無符號數看待真值為02047，作移-1023碼看待真值為-1023+1024；尾數（不計符號位）有52位小數，另加1位整數隱藏位，所以尾數絕對值為1.02.0 2-52，有效位數p=53。 最大絕對值為最大階碼與最大尾數絕對值的組合，最小絕對值為最小階碼與最小尾數絕對值的組合。代入相關公式后得最終結果如下表。32位64位最大絕對值(1-2-24)2129(1-2-53)21025最小絕對值2-1272-1023表數精度2-

28、242-53表數效率100%100%2.5(1) rm = 2，re = 2，p = 24（隱藏最高位）,q = 7。(2) Nmax = 1.71038，-|N|min = -1.4710-39 5.9610-8 10-7.22， = 100%2.61位7位6位00111111333333(1) 0.2 = 0.333333H160 設階碼為移-63碼（即-26+1，原題未指明）0.2 = 0.110011001100110011001101B2-2 1位8位23位00111110110011001100110011001101（其中最高有效位需隱藏）階碼為移-127碼（即-27+1）(2)

29、 符號位不變，（階碼 63）4 + 127；尾數左規，除去最高位；(3) 符號位不變，（階碼 127）/ 4 + 63；尾數補最高位，按除法余數右移若干位，左補0。2.13已知10條指令使用頻度，求3種編碼方法的平均碼長與信息冗余量。(1)此問中的“最優Huffman編碼法”實際是指碼長下限，即信源的平均信息量熵，代公式得H=2.9566。(2)Huffman編碼性能如下表；(3)2/8擴展編碼是8/64/512法的變種，第一組2條指令，碼長為2（1位擴展標志，1位編碼）,第二組8條指令，碼長為4（1位擴展標志，與第一組區別，加3位編碼），編碼性能如下表；(4)3/7擴展編碼是15/15/15

30、法的變種，第一組3條指令，碼長為2（共有4種組合，其中3種組合分別代表3條指令，留1種組合作為擴展前綴標志）,第二組7條指令，碼長為5（2位固定的前綴擴展標志，與第一組區別，加3位編碼，只用其中7種組合），編碼性能如下表。Huffman編碼2/8擴展編碼3/7擴展編碼平均碼長L2.993.13.2信息冗余量R1.10%4.61%7.59%2.14一臺模型機共有7條指令，各指令的使用頻率分別為35%，25%，20%，10%，5%，3%和2%，有8個通用數據寄存器，2個變址寄存器。(1)要求操作碼的平均長度最短，請設計操作碼的編碼，并計算所設計操作碼的平均長度。(2)設計8字長的寄存器-寄存器型指

31、令3條，16位字長的寄存器-存儲器型變址尋址方式指令4條，變址范圍不小于127。請設計指令格式，并給出各字段的長度和操作碼的編碼。解：(1)要使得到的操作碼長度最短，應采用Huffman編碼，構造Huffman樹如下：由此可以得到7條指令的編碼分別如下：這樣，采用Huffman編碼法得到的操作碼的平均長度為：H = 2(0.35+0.25+0.20) + 30.10 + 4 0.05 + 5(0.03 + 0.02) = 1.6+0.3+0.2+0.25 =2.35(2)設計8位字長的寄存器-寄存器型變址尋址方式指令如下，因為只有8個通用寄存器，所以寄存器地址需3位，操作碼只有兩位，設計格式如

32、下：三條指令的操作碼分別為00，01，10設計16位字長的寄存器-存儲器型變址尋址方式指令如下：四條指令的操作碼分別為1100，1101，1110，11112.15某處理機的指令字長為16位，有雙地址指令、單地址指令和零地址指令三類，并假設每個地址字段的長度均為6位。(1)如果雙地址指令有15條，單地址指令和零地址指令的條數基本相同，問單地址指令和零地址指令各有多少條？并且為這三類指令分配操作碼。(2)如果要求三類指令的比例大致為1：9：9，問雙地址指令、單地址指令和零地址指令各有多少條？并且為這三類指令分配操作碼。解：(1) 15條/63條/64條(2) 14條/126條/128條(1)根據

33、指令地址的數量來決定各種指令在指令空間上的分布：如果我們按照從小到大的順序分配操作碼，這樣，按照指令數值從小到大的順序，分別為雙地址指令、單地址指令和零地址指令。其次可以根據指令的條數來大致的估計操作碼的長度：雙指令15條，需要4位操作碼來區分，剩下的12位操作碼平均分給單地址和零地址指令，每種指令可以用6位操作碼來區分，這樣，各指令的條數為：雙地址指令15條，操作碼：00001110；單地址指令26-1=63條，操作碼：1111 0000001111 111110；零地址指令64條，操作碼：1111 111111 0000001111 111111 111111。 (2)與上面的分析相同，可

34、以得出答案：雙地址指令14條，操作碼：00001101；單地址指令26 x 2-2 = 126條，1110 0000001110 111110，1111 0000001111 111110；零地址指令128條1110 111111 0000001110 111111 111111,1111 111111 0000001111 111111 111111(2)B雙地址指令同上,14條，操作碼：00001101；單地址指令64 + 62 = 126條，64 條單地址指令操作碼1110 0000001110 111111，62 條單地址指令操作碼1111 0000001111 111101；零地址指

35、令128條1111 111110 0000001110 111110 111111,1111 111111 0000001111 111111 1111112.3 第三章(P202)例3.1假設T25T1，在命中率H為0.9和0.99兩種情況下，分別計算存儲系統的訪問效率。解：當H0.9時，e11(0.95(10.9)0.72當H0.99時，e21(0.995(10.99)0.96 提高存儲系統速度的兩條途徑： 一是提高命中率H二是兩個存儲器的速度不要相差太大其中：第二條有時做不到(如虛擬存儲器)，因此，主要依靠提高命中率例3.2在虛擬存儲系統中，兩級存儲器的速度相差特別懸殊T2105 T。如

36、果要使訪問效率e0.9，問需要有多高的命中率？解： 0.9H90000(1H)1 89999.1H89999 計算得H0.9999988888777770.999999例3.3在一個Cache存儲系統中，當Cache的塊大小為一個字時，命中率為H0.8；假設數據的重復利用率為5，計算Cache的塊大小為4個字時，Cache存儲系統的命中率是多少？假設T2T，分別計算訪問效率。解：n4520，采用預取技術之后，命中率提高到：Cache的塊大小為一個字時，H0.8，訪問效率為：e11(0.85(10.8)0.55Cache的塊大小為4個字時，H0.99，訪問效率為：e21(0.995(10.99)

37、0.96例3.4在一個虛擬存儲系統中，T2105 T，原來的命中率只有0.8，現采用預取技術，訪問磁盤存儲器的數據塊大小為4K字，如果要求訪問效率不低于0.9，計算數據在主存儲器中的重復利用率至少為多少？解：假設數據在主存儲器中的重復利用率為m，根據前面的給出關系：解這個方程組，得到m44，即數據在主存儲器中的重復利用率至少為44次。例3.6Star-100巨型機存儲系統采用并行和交叉相結合的方式工作，有32個存儲體低位交叉，每次并行讀寫512位，存儲周期為1.28um(磁心存儲器)，處理機字長32位，計算它的頻帶寬度Bm和峰值速度T。解：因為：n32，w512，Tm1280ns， Bmn w

38、/tm32512b/1280ns 12.8Gb/s 1.6GB/s 400MW/s T2.5ns， 與Tm相比，峰值速度提高512倍。例3.8一個程序共有5個頁面組成，分別為P1P5。程序執行過程中的頁地址流（即程序執行中依次用到的頁面）如下：P1，P2，P1，P5，P5，P1，P3，P4，P3，P4假設分配給這個程序的主存儲器共有3個頁面。給出FIFO、LRU和OPT三種頁面替換算法對這3頁主存的使用情況，包括調入、替換和命中等。時間t12345678910實際頁地址流P1P2P1P5P4P1P3P4P2P4命中次數1111*444*4*22先進先出算法2222*1111*4（FIFO算法）

39、555*3333*調入調入命中調入替換替換替換命中替換替換2次11111111*22最久沒有使用算法222*444*444（LRU算法）55*5*333*3*調入調入命中調入替換命中替換命中替換命中4次111111*3*3*33最優替換算法2222*22222（OPT算法）5*444444調入調入命中調入替換命中替換命中命中命中5次三種頁面替換算法對同一個頁地址流的調度過程例3.9一個循環程序，依次使用P1，P2，P3，P4四個頁面，分配給這個程序的主存頁面數為3個。FIFO、LRU和OPT三種頁面替換算法對主存頁面的調度情況如下圖所示。在FIFO和LRU算法中，總是發生下次就要使用的頁面本次

40、被替換出去的情況，這就是“顛簸”現象。時間t12345678實際頁地址流P1P2P3P4P1P2P3P4命中次數111*444*33先進先出算法222*111*4（FIFO算法）333*222*調入調入調入替換替換替換替換替換0次111*444*33最久沒有使用算法222*111*4（LRU算法）333*222*調入調入調入替換替換替換替換替換0次11111*111最優替換算法22222*3*3（OPT算法）3*4*4444*調入調入調入替換命中命中替換命中3次頁面調度中的顛簸現象3.1由三個訪問速度、存儲容量和每位價格都不相同的存儲器構成一個存儲體系。其中，M1靠近CPU，回答下列問題： M

41、1(T1,S1,C1) M2(T2,S2,C2) M3(T3,S3,C3)（1） 寫出這個三級存儲體系的等效訪問時間T，等效存儲容量S和等效每位價格C的表達式。（2）在什么條件下，整個存儲體系的每位價格接近于C3？3.3直接代公式計算存儲層次性能指標。(1)74ns，38ns，23.6ns(2)0.258，0.315，0.424(3)T256K T128K c128K c64K(4)19.092，11.97，10.0064。答案是256K方案最優。3.5已知，其中g=0.1依題意有整理得0.9n0.2，解出，向下取整，得15；按另一種題意理解是向上取整，得16，也對。3.7方式1：16個模塊高

42、位交叉方式2：16個模塊并行訪問 方式3：16個模塊低位交叉 方式4：2路高位交叉8路低位交叉16個存儲模塊每8個組成一個大的模塊：方式5：4路高位交叉4路低位交叉16個存儲模塊每4個組成一個大的模塊：方式6：4路并行訪問4路低位交叉（1）這幾種存儲器都能夠并行工作，因此可以提高頻帶寬度。總的來說，并行訪問存儲器的優點是實現簡單、容易，缺點是訪問沖突大；高位交叉訪問存儲器的優點是擴充方便，缺點是訪問效率不高；低位交叉訪問存儲器可以用分時的方法來提高速度，但擴充不方便。（2）各種存儲器的頻帶寬度和他們的工作頻率有關，在不考慮沖突的情況下，如果有足夠多的獨立控制電路和寄存器，那么，他們的頻帶寬度是

43、相同的。（3）存儲器的邏輯示意圖略。注意，并行訪問存儲器和低位交叉訪問存儲器很相象，只不過，并行訪問存儲器使用存儲模塊號（存儲體號）來對已經輸出的結果進行選擇，而低位交叉訪問存儲器則用來生成對存儲模塊（存儲體）的片選信號，他通過流水的方式來提高訪問的速度。3.14在頁式虛擬存儲器中，一個程序由P1P5共5個虛頁組成。在程序執行過程中依次訪問到的頁面如下： P2 ，P3，P2，P1 ，P5 ，P2 ，P4 ，P5 ，P3 ，P2 ，P5 ，P2 假設系統分配給這個程序的主存有3個頁面，分別采用FIFO、LRU和OPT三種替換算法對這三頁主存進行調度。（1）畫出主存頁面調入、替換和命中的情況表。（

44、2）統計三種頁面替換算法的頁命中率。3.15（1）在分配的主存頁面數目大于等于5的情況下，這時，除了第一次調入不命中，以后的訪問均命中，可以達到最高的頁面命中率：實際命中的次數為7次，所以可能達到的最高頁面命中率為：（2）由于在頁面數大于等于5的情況下，肯定可以達到最高命中率，所以我們來看頁面數小于5時能否達到該命中率：分配的主存頁面數等于4時，調度過程如下： LFU算法44444*11111*11命中7次555*55555*5553333*33*333*32222*22222調入調入調入調入命中調入命中命中命中命中命中命中此時也可以達到最高命中率；分配的主存頁面等于3時，調度過程如下： LF

45、U算法444*222*33*333*3命中3次555*555*222*11333*1111*555調入調入調入調入命中調入調入調入命中調入調入命中此時不能達到最高命中率。所以至少應該分配4個主存頁面。（3) 我們假設程序每次只訪問一個存儲單元，這樣，對每一個特定頁面的訪問過程可以描述如下：因為第一次總是不命中的，而平均起來，隨后的1023次總是命中的，然后再次被調出主存，并再次重復先前的過程。所以訪問存儲單元的命中率為： 欲知可能的最高命中率及所需的最少主存頁數，較好的辦法是通過“堆棧模擬法”，求得命中次數隨主存頁數變化的函數關系。下圖就是“堆棧模擬圖”，其中“”表示命中。P=453251323513命中次數4532513235134532513235145325112354432551224444444n=10n=21n=33n=47n=57(1)Hmax=7/1258.3%(2)n=4(3)當1次頁面訪問代表連續1024次該頁內存儲單元訪問時，后1023次單元訪問肯定是命中的，而