北理工計算機體系結(jié)構(gòu)習題解答

會計學1北理工計算機體系結(jié)構(gòu)習題解答2第1章基礎知識翻譯先用轉(zhuǎn)換程序?qū)⒏咭患墮C器級上的程序整個地變換成低一級機器級上可運行的等效程序，然后再在低一級機器級上去實現(xiàn)的技術第1頁/共139頁3第1章基礎知識解釋在低一級機器級上用它的一串語句或指令來仿真高一級機器上的一條語句或指令的功能，通過對高一級機器語言程序中的每條語句或指令逐條解釋來實現(xiàn)的技術第2頁/共139頁4第1章基礎知識計算機系統(tǒng)結(jié)構(gòu)程序員所看到的計算機的屬性，即程序員為編寫出能在機器上正確運行的程序所必須了解到的機器的概念性結(jié)構(gòu)和功能特性。從層次結(jié)構(gòu)出發(fā)，計算機系統(tǒng)結(jié)構(gòu)指層次結(jié)構(gòu)中傳統(tǒng)機器級的系統(tǒng)結(jié)構(gòu)，研究的是軟、硬件之間的功能分配，以及對傳統(tǒng)機器級界面的定義第3頁/共139頁5第1章基礎知識透明性本來存在的事物或?qū)傩?，從某個角度看卻好象不存在軟件兼容程序可以不加修改地運行在各檔機器上，區(qū)別僅在于運行時間不同它分為向上兼容和向下兼容，以及向前兼容和向后兼容第4頁/共139頁6第1章基礎知識模擬用一種機器(A)的機器語言解釋實現(xiàn)另一種機器(B)的指令系統(tǒng)，使A具有B的指令系統(tǒng)，從而實現(xiàn)軟件移植的方法。被模擬的機器稱為虛擬機，模擬用的機器稱為宿主機，解釋程序稱為模擬程序第5頁/共139頁7第1章基礎知識仿真用一種機器(A)的微程序直接解釋實現(xiàn)另一種機器(B)的指令系統(tǒng)，從而實現(xiàn)軟件移植的方法被仿真的機器稱為目標機，進行仿真的機器稱為宿主機，解釋微程序機器稱為仿真微程序第6頁/共139頁8第1章基礎知識并行性指可以同時進行運算或操作的特性，它有兩重含義：同時性：同一時刻發(fā)生并發(fā)性：同一時間間隔內(nèi)發(fā)生第7頁/共139頁9第1章基礎知識系列機同一廠家生產(chǎn)的具有相同系統(tǒng)結(jié)構(gòu)、但有不同組成和實現(xiàn)的一系列不同型號的機器兼容機不同廠家生產(chǎn)的具有相同系統(tǒng)結(jié)構(gòu)、但有不同組成和實現(xiàn)的一系列不同型號的機器第8頁/共139頁10第1章基礎知識緊耦合系統(tǒng)多臺計算機之間通過總線或高速開關互連，共享主存，并有較高的信息傳輸速率的多機系統(tǒng)時間重疊引入時間概念，讓多個處理過程輪流使用同一套硬件設備的各部分，基本上不需要重復設置硬件設備第9頁/共139頁11第1章基礎知識1-1第4級N3/M3*K秒第3級N2/M2*K秒（同理）第2級N/M*K秒(X/M*N*1/X*K=N/M*K秒)第1級K秒（設為X條，每條需要1/X*K秒）第10頁/共139頁12第1章基礎知識1-6透明的是： 指令緩沖器 時標發(fā)生器 乘法器 主存地址寄存器先行進位鏈 移位器第11頁/共139頁13第1章基礎知識1-8（1）可以。因為它雖然是屬于計算機系統(tǒng)結(jié)構(gòu)的內(nèi)容。新增加的數(shù)據(jù)類型和指令，不會影響到已有指令所寫的程序正確運行，只是現(xiàn)在用新增加的指令來寫程序，會使計算機的性能和效率變得更好。第12頁/共139頁14第1章基礎知識（2）不可以。中斷的分級和中斷的響應次序等中斷機構(gòu)都屬于計算機系統(tǒng)結(jié)構(gòu)的內(nèi)容。中斷分級由原來的4級增加到5級應當還是允許的，關鍵是重新調(diào)整了中斷響應的優(yōu)先次序，這就使原有程序的中斷響應次序發(fā)生了改變，會影響原有程序工作的正確性。第13頁/共139頁15第1章基礎知識 (3)可以。Cache存儲器屬于計算機組成，它不會改變原有的系統(tǒng)程序和應用程序，不會影響到它們的正確性。只是有了它之后，系統(tǒng)的性能會顯著的提高。 (4)可以。浮點數(shù)尾數(shù)的下溢處理不屬于計算機系統(tǒng)結(jié)構(gòu)，而是計算機組成設計所需要考慮的內(nèi)容。第14頁/共139頁16第1章基礎知識(5)不可以。指令的操作碼、字段格式、尋址方式等都是計算機系統(tǒng)結(jié)構(gòu)的內(nèi)容。如果將它們改變，就會直接影響以前編寫的程序不能正確運行。 (6)可以。數(shù)據(jù)通路寬度是計算機組成的內(nèi)容。第15頁/共139頁17第1章基礎知識 (7)可以。單總線改為多總線是計算機組成的內(nèi)容。 (8)不可以。通用寄存器的使用是屬于計算機系統(tǒng)結(jié)構(gòu)的內(nèi)容。0號通用寄存器改為堆棧指示器，將使原先程序中0號寄存器中的內(nèi)容改變直接影響到堆棧指針的位置發(fā)生變化，造成程序無法正常工作。第16頁/共139頁181-9如果某一計算任務用向量方式求解比用標量方式求解要快20倍，稱可用向量方式求解部分所花費時間占總的百分比為可向量化百分比。請寫出加速比與可向量化比例兩者的關系曲線。解：第17頁/共139頁19在習題1-9中，為達到加速比2，可向量化的百分比應為多少?解：第18頁/共139頁201-10用一臺40MHz處理機執(zhí)行標準測試程序，它含的混合指令數(shù)和相應所需的時鐘周期數(shù)如下：指令類型 指令數(shù) 時鐘周期數(shù) 整數(shù)運算 45000 1 數(shù)據(jù)傳送 32000 2 浮點 15000 2 控制傳送 8000 2 求有效CPI、MIPS速率和程序的執(zhí)行時間。第19頁/共139頁21[解答]CPI=＝(45000*1+32000*2+15000*2+8000*2)/

(45000+32000+15000+8000)=1.55周期/指令

第20頁/共139頁221-11假設在一臺40MHz處理機上運行200,000條指令的目標代碼，程序主要由四種指令組成。根據(jù)程序跟蹤實驗結(jié)果，已知指令混合比和每種指令所需的指令數(shù)如下：指令類型 CPI 指令混合比 算術和邏輯 1 60% 高速緩存命中的加載/存儲2 18% 轉(zhuǎn)移 4 12% 高速存儲缺失的存儲器訪問8 10% (a)計算在單處理機上用上述跟蹤數(shù)據(jù)運行程序的平均CPI。(b)根據(jù)(a)所得的CPI,計算相應的MIPS速率。第21頁/共139頁23[解答](a)

=2.24(b)第一章第22頁/共139頁24第2章指令系統(tǒng)數(shù)據(jù)表示由硬件直接識別和引用的數(shù)據(jù)類型第23頁/共139頁25第2章指令系統(tǒng)動態(tài)再定位動態(tài)再定位采用基址尋址方法。當把程序裝入主存時，對程序不做任何修改（變換），直接裝入主存，同時將程序在主存中的起始地址a存入對應該道程序的基址寄存器。在執(zhí)行指令時，通過地址加法器將邏輯地址加上基址寄存器的內(nèi)容(程序基點地址)，形成物理地址，然后訪存第24頁/共139頁26第2章指令系統(tǒng)功能型指令真正執(zhí)行數(shù)據(jù)變換的指令，如加、減、乘、除等哈夫曼壓縮概念當各種事件發(fā)生的概率不均等時，使用概率高的事件用短代碼表示，使用概率低的事件用長代碼表示，就會使平均位數(shù)縮短。哈夫曼編碼是最優(yōu)化的編碼方法第25頁/共139頁27第2章指令系統(tǒng)CISC增強原有指令的功能，設置更為復雜、但功能更強的新指令以取代原先由軟件子程序完成的功能，實現(xiàn)軟件功能的硬化。按這種途徑和方向發(fā)展，會使機器的指令系統(tǒng)越來越龐大和復雜，因此稱采用這種途徑設計而成的CPU的計算機為復雜指令集計算機CISC第26頁/共139頁28第2章指令系統(tǒng)RISC減少指令總數(shù)，簡化指令功能，以降低硬件設計的復雜度，提高指令的執(zhí)行速度。按這種途徑和方向發(fā)展，會使機器的指令系統(tǒng)精煉簡單，因此稱采用這種途徑設計而成的CPU的計算機為精簡指令集計算機RISC第27頁/共139頁29第2章指令系統(tǒng)2-1數(shù)據(jù)表示是指由硬件直接識別和引用的數(shù)據(jù)類型數(shù)據(jù)結(jié)構(gòu)反映的是各種數(shù)據(jù)元素或信息單元之間的結(jié)構(gòu)關系第28頁/共139頁30第2章指令系統(tǒng)數(shù)據(jù)結(jié)構(gòu)是通過軟件映像成機器所具有的各種數(shù)據(jù)表示實現(xiàn)的數(shù)據(jù)表示是數(shù)據(jù)結(jié)構(gòu)的組成元素數(shù)據(jù)表示為數(shù)據(jù)結(jié)構(gòu)提供不同程度的支持，反映在效率和方便程度的不同因此，數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)表示是軟、硬交界面第29頁/共139頁31第2章指令系統(tǒng)習題2-41、等長二進制編碼

平均碼長為[log214]+1=42、Huffman編碼 首先構(gòu)造Huffman樹第30頁/共139頁32第2章指令系統(tǒng)0.010.30.010.020.020.030.030.040.110.130.140.150.150.040.121.000.570.270.020.430.190.240.050.070.040.080.1236555553333436第31頁/共139頁33第2章指令系統(tǒng)

平均碼長為 ∑Pi*Li=(0.01+0.01)×6 +(0.02+0.02+0.03+0.03+0.04)×5 +0.04×4+(0.11+0.12+0.13 +0.14+0.15+0.15)×3 =3.38第32頁/共139頁34第2章指令系統(tǒng)3、只有兩種碼長的擴展操作碼編碼 使用頻度高的用短代碼表示。根據(jù)Huffman編碼和指令使用頻度，可以設計出具有3位和6位碼長的操作碼。操作碼編碼如下：第33頁/共139頁35第2章指令系統(tǒng)編碼指令使用頻度編碼指令使用頻度0000010100111001011100.150.150.140.130.120.110.041110001110011110101110111111001111011111100.040.030.030.020.020.010.01第34頁/共139頁36第2章指令系統(tǒng)

平均碼長為 ∑Pi*Li=(0.15+0.15+0.14+0.13 +0.12+0.11+0.04)×3 +(0.04+0.03+0.03+0.02 +0.02+0.01+0.01)×6 =3.48第35頁/共139頁37編碼指令使用頻度編碼指令使用頻度0000010100111001010.150.150.140.130.120.1111000110011101011011111001110111110111110.040.040.030.030.020.020.010.013-5位操作碼編碼如下：第36頁/共139頁38第2章指令系統(tǒng)

平均碼長為 ∑Pi*Li=(0.15+0.15+0.14+0.13 +0.12+0.11)×3 +(0.04+0.04+0.03+0.03+0.02 +0.02+0.01+0.01)×5 =3.40第37頁/共139頁392-5一個處理機共有10條指令，各指令在程序中出現(xiàn)的概率如下：指令概率Huffman2/8擴展3/7擴展

I10.25I20.20I30.15I40.10I50.08I60.08I70.05I80.04I90.03I100.02第38頁/共139頁40（1）計算這10條的操作碼最短平均長度。（2）采用Huffman編碼法編寫這10條指令的操作碼，并計算操作碼的平均長度和信息冗余量。（3）采用2/8擴展編碼法編寫這10條指令的操作碼，并計算操作碼的平均長度和信息冗余量。（4）采用3/7擴展編碼法編寫這10條指令的操作碼，并計算操作碼的平均長度和信息冗余量。第39頁/共139頁41第2章（1）最優(yōu)HuffmanH=-∑Pi×log2Pi=0.25×2+0.20×2.322+0.15×2.737+

……=2.96第40頁/共139頁420.151.000.430.570.030.020.080.050.040.230.170.320.130.090.050.080.250.200.1001I1I2I3I4I5I6I7I8I9I100101010101010101第41頁/共139頁43(2)采用最小概率合并法H’=∑Pi×Li=0.25×2+0.20×2+0.15×3+0.10×3+0.08×4+0.08×4+0.05×5+0.04×5+0.03×5+0.02×5=2.99信息冗余=1-2.96/2.99=1%第42頁/共139頁44指令概率HuffmanI10.2500I20.2010I30.15010I40.10110I50.080110I60.081110I70.0501110I80.0401111I90.0311110I100.0211111第43頁/共139頁450.151.000.430.570.030.020.080.050.040.230.170.320.130.090.050.080.250.200.1001I1I2I3I4I5I6I7I8I9I10第44頁/共139頁46(2)采用最小概率合并法H’=∑Pi×Li=0.25×2+0.20×2+0.15×3+0.10×3+0.08×4+0.08×4+0.05×4+0.04×5+0.03×6+0.02×6=2.99信息冗余=1-2.96/2.99=1%第45頁/共139頁47指令概率Huffman

I10.25 00

I20.20 10

I30.15 010

I40.10 110

I50.08 0110

I60.08 1111

I70.05 1110

I80.04 01110

I90.03 011111

I100.02 011110

第46頁/共139頁48（3）采用2/8擴展法

H=∑Pi×Li=(0.25+0.20)×2+(0.15+0.10+0.08+0.08+0.05+0.04+0.03+0.02)×4=3.1

信息冗余=1-2.96/3.1=4.5%第47頁/共139頁49指令概率 2/8擴展

I10.25 00

I20.20 01

I30.15 1000

I40.10 1001

I50.08

1010

I60.081011

I70.051100

I80.04

1101

I90.031110

I100.021111

第48頁/共139頁50（4）采用3/7擴展法

H=∑Pi×Li=(0.25+0.20+0.15)×2+(0.10+0.08+0.08+0.05+0.04+0.03+0.02)×5=3.2

信息冗余=1-2.96/3.2=7.5%第49頁/共139頁51指令概率3/7擴展

I10.25

00I20.20

01I30.15

10I40.10

11000I50.08

11001I60.08

11010I70.05

11011I80.04

11100I90.03

11101I100.02

11110第50頁/共139頁52指令概率Huffman2/8擴展3/7擴展

I10.2500000000I20.2010100101I30.15010010100010I40.10110110100111000I50.0801100110101011001I60.0811101111101111010I70.05011101110110011011I80.040111101110110111100I90.0311110011111111011101I100.0211111011110111111110第51頁/共139頁53第2章指令系統(tǒng)習題2-6已知指令字長為12位，地址碼長為3位則三地址指令的操作碼碼長為3位，單地址指令的操作碼碼長為9位，零地址指令的操作碼碼長為12位因此，只要按3-9-12擴展操作碼進行編碼，看是否能容納所有指令即可。一種可能的編碼方案如下：第52頁/共139頁54第2章指令系統(tǒng)000…011100000000…111111101111111110000…111111110111111111111000…1111111111114條254條8條8條16條第53頁/共139頁55第2章指令系統(tǒng)可以看出，三地址指令和零地址指令不存在問題，但無法容納255條單地址指令。但能容納254條單地址指令第54頁/共139頁56第3章總線、中斷、輸入輸出系統(tǒng)3-3根據(jù)題意， TS=9.8μs,TD=0.2μs

因此，該通道的極限流量為

1/TS+TD

=1/9.8+0.2=100KBps

低速設備每隔500μs發(fā)送一個字節(jié)數(shù)據(jù)傳送請求，因此，每個設備的實際流量為 1/500=2KBps單位第55頁/共139頁57第3章總線、中斷、輸入輸出系統(tǒng)根據(jù)fmax>=f實際，該通道最多可以連接 100/2=50臺 這樣的低速設備第56頁/共139頁58第3章總線、中斷、輸入輸出系統(tǒng)根據(jù)題意，該通道的極限流量為

fmax=1024/9.8+1024*0.2=1/0.2096

對比給出的數(shù)據(jù)傳送請求的時間間隔，可以確定：

B、C、E、F可以掛在此通道上， A、D不可以（比0.2096快）第57頁/共139頁593-8一個字節(jié)多路通道連接有5臺設備，它們的數(shù)據(jù)傳輸率如下表：設備名稱D1D2D3D4D5數(shù)據(jù)傳輸速率（KB/S）10033.333.32010服務優(yōu)先級12345第58頁/共139頁60（1）計算這個字節(jié)多路通道的實際工作流量。（2）為了使通道能夠正常工作，請設計通道的最大流量和工作周期。（3）當這個字節(jié)多路通道工作在最大流量時，5臺設備都在0時刻同時向通道發(fā)出第一次傳送數(shù)據(jù)的請求，并在以后的時間里按照各自的數(shù)據(jù)傳輸速率連續(xù)工作。畫出通道分時為各臺設備服務的時間關系圖，并計算這個字節(jié)多路通道處理完各臺設備的第一次數(shù)據(jù)服務請求的時刻。第59頁/共139頁61解：（1）實際工作流量fBYTE=100+33.3+33.3+20+10=196.6KB/s（2）最大流量=200KB/s

工作周期t=1/fBYTE=1/200K=5μs第3章第60頁/共139頁62（3）第3章D1D2D3D4D5ttttt0102030405060708090100通道處理完各臺設備的第一次數(shù)據(jù)服務請求的時刻分別為：5μs，10μs，20μs，30μs，90μs。第61頁/共139頁633-9一個字節(jié)多路通道連接有4臺設備，每臺設備發(fā)出輸入輸出服務請求的時間間隔、它們的服務優(yōu)先級和發(fā)出第一次服務請求的時刻如下表：設備名稱D1D2D3D4發(fā)服務請求間隔10μs75μs15μs50μs服務優(yōu)先級1423發(fā)出第一次請求時間0μs70μs10μs20μs第62頁/共139頁64（1）計算這個字節(jié)多路通道的實際流量和工作周期。（2）在數(shù)據(jù)傳送期間，如果通道選擇一次設備的時間為3μs，傳送一個字節(jié)的時間為2μs，畫出這個字節(jié)多路通道響應各設備請求和為設備服務的時間關系圖。（3）從（2）時間關系圖中，計算通道處理完成各設備第一次服務請求的時刻。（4）從（2）時間關系圖中看，這個字節(jié)多路通道能否正常工作？（5）在設計一個字節(jié)多路通道的工作流量時，可以采用哪些措施來保證通道能夠正常工作？第63頁/共139頁65解：（1）數(shù)據(jù)傳輸率D1=1/10=100KB/sD2=1/75=13.3KB/sD3=1/15=66.7KB/sD4=1/50=20KB/s實際工作流量fBYTE=100+13.3+66.7+20=200KB/s

工作周期t=1/fBYTE=1/200K=5μs第64頁/共139頁66（2）第3章D1D2D3D4tttt0102030405060708090100120130140150160110（3）通道處理完各臺設備的第一次數(shù)據(jù)服務請求的時刻分別為：5μs，160μs，20μs，40μs。第65頁/共139頁67（4）此字節(jié)多路通道不能正常工作，因為D2的第一次服務請求被響應之前，設備已經(jīng)發(fā)出第二次服務請求，這就可能導致丟失數(shù)據(jù)。（5）可以采用3種措施來保證通道能夠正常工作：增加通道的最大流量。動態(tài)改變設備的優(yōu)先級。增加一定的數(shù)據(jù)緩沖器。第66頁/共139頁68第4章存儲體系地址的變換程序按某種地址映象關系裝入主存后，運行時如何把多用戶虛地址變換成實地址第67頁/共139頁69第4章存儲體系存儲層次（體系）利用多種不同的存儲器，形成M1至Mn的不同層次的存儲器系統(tǒng)。并利用I/O處理機和操作系統(tǒng)、硬件等技術，由增設的輔助軟、硬件自動完成地址變換、程序定位等工作，使這些存儲器形成一個整體。第68頁/共139頁70第4章存儲體系存儲層次（體系）從整體上看，速度接近M1，容量是Mn的，位價格接近廉價的Mn。將這樣的存儲器系統(tǒng)稱為存儲體系。第69頁/共139頁71第4章存儲體系程序局部性程序在執(zhí)行時所用到的指令和數(shù)據(jù)的分布不是隨機的，而是相對地簇聚成塊或頁。它包括時間局部性和空間局部性。第70頁/共139頁72第4章存儲體系時間局部性是指最近的未來要用到的信息可能就是當前正在使用的信息—這是由程序的循環(huán)造成的空間局部性是指最近的未來要用到的信息可能就是當前信息的相鄰信息—這是由程序的順序執(zhí)行造成的第71頁/共139頁73第4章存儲體系4-1在頁式虛擬存儲器中，若所要訪問的虛頁不在主存，我們稱此現(xiàn)象為頁面失效。把兩個或兩個以上的虛頁想進入主存中的同一頁面位置的現(xiàn)象稱為頁面爭用或?qū)嶍摏_突。第72頁/共139頁74第4章存儲體系 當所要訪問的虛頁不在主存，而所要進入主存中的頁面又未被占用時，兩者不會同時發(fā)生 若所要進入主存中的頁面已經(jīng)被占用，則兩者會同時發(fā)生。對全相聯(lián)映象，只有主存全被占滿時才會同時發(fā)生第73頁/共139頁754-2對于一個由兩個存儲器M1和M2構(gòu)成的存儲系統(tǒng)，設M1的命中率為h，兩個存儲器的存儲容量分別為s1和s2，訪問速度分別為t1和t2，每千字節(jié)的價格分別為c1和c2？（1）在什么條件下，整個存儲系統(tǒng)的每千字節(jié)平均價格會接近于c2？（2）寫出這個存儲系統(tǒng)的等效訪問時間ta的表達式。（3）假設存儲系統(tǒng)的訪問效率e=t1/ta，兩個存儲器的速度比r=t2/t1。試以速度比r和命中率h來表示訪問效率e。

第74頁/共139頁76（4）如果r=100，為了使訪問效率e>0.95，要求命中率h是多少？（5）對于（4）所要求的命中率實際上很難達到。假設實際的命中率只能達到0.96。現(xiàn)采用一種緩沖技術來解決這個問題。當訪問M1不命中時，把包括被訪問數(shù)據(jù)在內(nèi)的一個數(shù)據(jù)塊都從M2取到M1中，并假設被取到M1中的每個數(shù)據(jù)平均可以被重復訪問5次。請設計緩沖深度（即每次從M2取到M1中的數(shù)據(jù)塊的大小）。第75頁/共139頁77S2>>S1時,C≈C24-2解：（1）（2）ta=h×t1+(1-h)×t2第76頁/共139頁78（3）（4）r=100時，第4章0.95=1/(100-99h)h=0.99947第77頁/共139頁79n=75.475m=nm=15.1（5）重復訪問必考第78頁/共139頁804-3在頁式虛擬存儲器中，一個程序由P1～P5共5個頁面組成。在程序執(zhí)行過程中依次訪問到的頁面如下：P2,P3,P2,P1,P5,P2,P4,P5,P3,P2,P5,P2假設系統(tǒng)分配給這個程序的主存有3個頁面，分別采用FIFO、LRU和OPT三種頁面替換算法對這3頁主存進行調(diào)度。（1）畫出主存頁面調(diào)入、替換和命中的情況表。（2）統(tǒng)計三種頁面替換算法的頁命中率。第79頁/共139頁814-3解：（1）FIFO22225555333333332222255111444442123456789101112232152453252中***中*中**第4章第80頁/共139頁82（2）LRU22335555555532222223333111444222123456789101112232152453252中*中*中**中中第4章第81頁/共139頁83（2）LRU堆棧法23215245325223215245325321524533123456789101112232152453252中*中*中**中中第82頁/共139頁84（3）OPT222222*4*4*4*2223333*33333331*55555555123456789101112232152453252中*中*中中*中中第4章第83頁/共139頁85（2）FIFO算法頁H=3/12=25%LRU算法頁H=5/12=41.7%OPT算法頁H=6/12=50%第4章第84頁/共139頁864-4假設在一個采用組相聯(lián)映象方式的Cache中，主存由B0~B7共8塊組成，Cache有兩組，每組兩塊，每塊的大小為16個字節(jié)，采用LRU塊替換算法。在一個程序執(zhí)行過程中依次訪問這個Cache的塊地址流如下：B6,B2,B4,B1,B4,B6,B3,B0,B4,B5,B7,B3（1）寫出主存地址的格式，并標出各字段的長度。（2）寫出Cache地址的格式，并標出各字段的長度?！仨氂脮系乃惴ǖ?5頁/共139頁87（3）畫出主存與Cache之間各個塊的映象對應關系。（4）采用LRU替換算法，計算Cache的塊命中率。（5）如果改為全相聯(lián)映象方式，再做（4），可以得出什么結(jié)論？（6）如果在程序執(zhí)行過程中，每從主存裝入一塊到Cache，則平均要對這個塊訪問16次。請計算在這種情況下的Cache命中率。第86頁/共139頁88第4章4-4解：標記組號塊內(nèi)地址組號組內(nèi)塊號塊內(nèi)地址（1）主存地址格式2111（2）Cache地址格式44‘先寫cache地址第87頁/共139頁89(3)012301234567組0組1組間直接映象組內(nèi)全相聯(lián)映象Cache主存標記00標記01標記10標記11第88頁/共139頁9062444660444462224460000

111333573

1113571234567891011

1262414630457

3*中******（4） LRU利用堆棧法塊命中率H=1/12=8.3%第89頁/共139頁9166666666655522222333377

4444444444

11110000312345678910

11

12624146304573中中**中***(5)LRU塊命中率H=3/12=25%第90頁/共139頁9262414630457362414630457

6221463045

662146304123456789101112624146304573中中**中***(5)LRU利用堆棧法塊命中率H=3/12=25%第91頁/共139頁93（6）=1-(1-0.25)/(16*16)=0.997命中率的兩個公式必考對應不同的情況一個是

“重環(huán)”？？注意n的含義第92頁/共139頁94第4章存儲體系4-5頁式虛擬存儲器采用全相聯(lián)地址映象與變換會發(fā)生頁面失效的虛頁號有：2，3，5，7第93頁/共139頁95第4章存儲體系虛地址虛頁號裝入位頁內(nèi)地址實地址0372810231024205578004096680003012746101100110失效10230失效失效06563072無40951024無無2048656裝入位為1才可以變第94頁/共139頁96第4章存儲體系4-6第95頁/共139頁97第4章存儲體系4-7地址字段及其對應關系組號塊號塊內(nèi)地址標記組號塊內(nèi)地址11121cache地址主存地址第96頁/共139頁98第4章存儲體系012301234567組0組1組間直接映象組內(nèi)全相聯(lián)映象Cache主存第97頁/共139頁99第4章存儲體系24444002246442222244002466411113771155557713377111155123456789101112131415124137012546472時刻地址流0123命中替換替換替換替換替換命中替換替換替換替換第98頁/共139頁100第4章存儲體系 塊失效同時又發(fā)生塊爭用的時刻是：‘（條件必考，什么情況下才發(fā)生） 6，7，8，9，10，11，12，14，15 Cache的命中率為

2/15=13.3%第99頁/共139頁101第5章重疊、流水、向量處理機流水線吞吐率指流水線單位時間內(nèi)能處理的指令條數(shù)或能輸出的結(jié)果數(shù)流水線效率指流水線中的設備實際使用時間占整個運行時間之比，也稱為流水線的設備時間利用率第100頁/共139頁102第5章重疊、流水、向量處理機全局性相關由轉(zhuǎn)移指令引起的相關，會影響后續(xù)指令和指緩中的指令。它對流水線的影響是全局的，指緩中的指令可能要全部作廢，流水線會斷流，使吞吐率和效率下降等。我們把由轉(zhuǎn)移造成的指令之間關聯(lián)稱為全局性相關第101頁/共139頁103第5章重疊、流水、向量處理機局部性相關指令相關、主存操作數(shù)相關、通用寄存器組操作數(shù)相關和通用寄存器組基址或變址值相關等只影響相關的兩條或幾條指令，并不會改變已經(jīng)預取到指令緩沖器中指令，其影響是局部的，因此稱之為局部性相關第102頁/共139頁104第5章重疊、流水、向量處理機先寫后讀相關機器同時解釋執(zhí)行多條指令時，這些指令對同一存儲單元要求先寫入而后讀出的關聯(lián)第103頁/共139頁105第5章重疊、流水、向量處理機向量處理機向量適合于流水處理。一般將向量數(shù)據(jù)表示與流水處理方式結(jié)合在一起，構(gòu)成向量流水處理機，也稱其為向量處理機，以提高主要面向向量數(shù)組計算類應用的計算機的速度性能第104頁/共139頁1065-1假設一條指令的執(zhí)行過程分為“取指令”、“分析”和“執(zhí)行”三段，每一段的時間分別為Δt、2Δt和3Δt。在以下各種情況下，分別寫出連續(xù)執(zhí)行n條指令所需要的時間表達式。（1）順序執(zhí)行方式。（2）僅“取指令”和“執(zhí)行”重疊。（3）“取指令”、“分析”和“執(zhí)行”重疊?！乜加X得難的話先畫圖第105頁/共139頁1075-1解：第5章第106頁/共139頁108（1）

(t取指+t分析+t執(zhí)行)×nT=(Δt+2Δt+3Δt)×n=6nΔt（2）t取指+n×t分析+(n-1)×max{t取指,t執(zhí)行}+t執(zhí)行

T=Δt+(2Δt+3Δt)×n=(1+5n)Δt（3）t取指+max{t取指,t分析}+(n-2)×max{t取指,t分析,t執(zhí)行}+max{t分析,t執(zhí)行}+t執(zhí)行

T=Δt+2Δt+3Δt×n=(3+3n)Δt第5章第107頁/共139頁109第5章重疊、流水、向量處理機5-2假設指令的解釋分取指、分析和執(zhí)行3步，每步的時間相應為t取指、t分析、t執(zhí)行，(1)分別計算下列幾種情況下，執(zhí)行完100條指令所需時間的一般關系式：①順序方式；②僅“執(zhí)行k”與“取指k+1”重疊；③僅“執(zhí)行k”、“分析k+1”、“取指k+2”重疊。(2)分別在t取指=t分析=2、t執(zhí)行=1及t取指=t執(zhí)行=5、t分析=2兩種情況下，計算出上述各結(jié)果。第108頁/共139頁110第5章重疊、流水、向量處理機第109頁/共139頁111第5章重疊、流水、向量處理機(1)執(zhí)行100條指令所需的時間：①100×(t取指+t分析+t執(zhí)行)②t取指+100×t分析+99×max{t取指,t執(zhí)行}+t執(zhí)行③t取指+max{t取指,t分析}+98×max{t取指,t分析,t執(zhí)行}+max{t分析,t執(zhí)行}+t執(zhí)行

(2)當t取指=t分析=2、t執(zhí)行=1時，可求得執(zhí)行100條指令所需時間：①500②401③203

t取指=t執(zhí)行=5、t分析=2時，可求得執(zhí)行100條指令所需時間：①1200②705③510第110頁/共139頁112第5章重疊、流水、向量處理機5-3

流水線由4個功能部件組成，每個功能部件的延遲時間為Δt。當輸入10個數(shù)據(jù)后，間歇5Δt，又輸入10個數(shù)據(jù)，如此周期性地工作，求此時流水線的吞吐率，并畫出時空圖。第111頁/共139頁113第5章重疊、流水、向量處理機TP=10/14Δt=5/7Δt注意從哪里開始停，10的哪個位置第112頁/共139頁114第5章重疊、流水、向量處理機5-41122334412341234部件時間IVI

IIIII248121416182022610第113頁/共139頁115第5章重疊、流水、向量處理機實際吞吐率

TP=4/22Δt=2/11Δt效率

η=(3×4×2Δt+4×4Δt)/4×22Δt =40Δt/88Δt=5/11=45.5%這一章必須會畫圖會計算第114頁/共139頁116第5章重疊、流水、向量處理機為加快流水，使流水線每隔2Δt流出一個結(jié)果，應減少Ⅲ段的經(jīng)過時間至Δt。此時，流水線的實際吞吐率和效率為：‘（瓶頸的解決辦法） TP=4/14Δt=2/7Δt η=(3×4×2Δt+8×1Δt)/4×14Δt =32Δt/56Δt=4/7=57%第115頁/共139頁1175-5一條線性流水線由4個流水段組成，每個流水段的延遲時間都相等，都為Δt。開始5個Δt，每隔一個Δt向流水線輸入一個任務，然后停頓2個Δt，如此重復。求流水線的實際吞吐率、加速比和效率。‘注意

間隔

。。停頓。。

2個

第116頁/共139頁1185-5解：113335

13

241246789101135空間時間

S4S1

S2

S312224544556666777889第5章第117頁/共139頁119TP=5/(7Δt)=0.714/ΔtS=(5×4Δt+2Δt)/7Δt=22Δt/(7Δt)=3.14E=4×5Δt/(4×7Δt)=0.714=71.4%第5章第118頁/共139頁120第5章重疊、流水、向量處理機5-6為提高流水線效率可采用哪兩種主要途徑來克服速度瓶頸？現(xiàn)有3段流水線，各段經(jīng)過時間依次為Δt、3Δt、Δt。(1)分別計算在連續(xù)輸入3條指令時和30條指令時的吞吐率和效率。(2)按兩種途徑之一改進，畫出流水線結(jié)構(gòu)示意圖，同時計算連續(xù)輸入3條指令和30條指令時的吞吐率和效率。第119頁/共139頁121(1)連續(xù)輸入3條指令時的吞吐率TP3=3/(5△t+(3-1)*3△t)=3/11Δt效率η3=(3*5△t)/(3*11△t)=5/11=45.5%連續(xù)輸入30條指令時的吞吐TP30=30/(5△t+(30-1)*3△t)=15/46Δt效率η30=(30*5△t)/(3*92△t)=25/46=54.3%第120頁/共139頁122

為提高流水線效率，可采取瓶頸段再細分和瓶頸段并聯(lián)兩種途徑。連續(xù)輸入3條指令和30條指令時的吞吐率和效率分別為TP3=3/(5△t+(3-1)△t)=3