《計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》習(xí)題課及答案全套

1、 習(xí)題課習(xí)題課目錄目錄 返回總目錄基本要求：基本要求：）計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的基本概念，定量原理，指令的格式設(shè)計(jì)，CISC與RISC，虛擬存儲(chǔ)頁(yè)面替換算法，Cache映象，通道流量分析，數(shù)據(jù)相關(guān)，線性與非線性流水線技術(shù)及性能分析，互連網(wǎng)絡(luò)基本概念；學(xué)習(xí)重點(diǎn)：學(xué)習(xí)重點(diǎn)：）定量原理，指令格式設(shè)計(jì)，RISC，頁(yè)面替換算法，Cache映象，流水線性能分析；1 1計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的基本概念計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的基本概念1.11.1名詞解釋名詞解釋 返回目錄1. 1. 計(jì)算機(jī)體系結(jié)構(gòu)計(jì)算機(jī)體系結(jié)構(gòu)的定義：的定義：程序員所看到的計(jì)算機(jī)程序員所看到的計(jì)算機(jī)的屬性，即概念性結(jié)構(gòu)與功能特性。的屬性，即概念性結(jié)構(gòu)與功能特性。 A

2、mdahl提出的體系結(jié)構(gòu)：是指?jìng)鹘y(tǒng)機(jī)器級(jí)的體系提出的體系結(jié)構(gòu)：是指?jìng)鹘y(tǒng)機(jī)器級(jí)的體系結(jié)構(gòu)。即一般所說(shuō)的機(jī)器語(yǔ)言程序員所看到的傳統(tǒng)機(jī)結(jié)構(gòu)。即一般所說(shuō)的機(jī)器語(yǔ)言程序員所看到的傳統(tǒng)機(jī)器級(jí)所具有的屬性。器級(jí)所具有的屬性。 2. 2. 透明性透明性 在計(jì)算機(jī)技術(shù)中，對(duì)這種本來(lái)是存在的在計(jì)算機(jī)技術(shù)中，對(duì)這種本來(lái)是存在的 事物或?qū)傩?，但從某種角度看又好象不存在。事物或?qū)傩?，但從某種角度看又好象不存在。大概率事件優(yōu)先原則大概率事件優(yōu)先原則：即對(duì)于大概率事件（最常見(jiàn)事：即對(duì)于大概率事件（最常見(jiàn)事件），賦予它優(yōu)先的處理權(quán)和資源使用權(quán)，以獲得全局的最件），賦予它優(yōu)先的處理權(quán)和資源使用權(quán)，以獲得全局的最優(yōu)結(jié)果。優(yōu)結(jié)果。

3、Amdahl定律定律：加快某部件執(zhí)行速度所獲得的系統(tǒng)性能加：加快某部件執(zhí)行速度所獲得的系統(tǒng)性能加速比，受限于該部件在系統(tǒng)中所占的重要性。速比，受限于該部件在系統(tǒng)中所占的重要性。程序的局部性原理程序的局部性原理：程序在執(zhí)行時(shí)所訪問(wèn)地址的分布不：程序在執(zhí)行時(shí)所訪問(wèn)地址的分布不是隨機(jī)的，而是相對(duì)地簇聚；這種簇聚包括指令和數(shù)據(jù)兩部是隨機(jī)的，而是相對(duì)地簇聚；這種簇聚包括指令和數(shù)據(jù)兩部分。程序局部性包括程序的分。程序局部性包括程序的時(shí)間局部性時(shí)間局部性和和空間局部性空間局部性。時(shí)間局部性時(shí)間局部性：程序即將用到的信息很可能就是目前正在：程序即將用到的信息很可能就是目前正在使用的信息使用的信息空間局部性空間

4、局部性：程序即將用到的信息很可能與目前正在使：程序即將用到的信息很可能與目前正在使用的信息相鄰或臨近。用的信息相鄰或臨近。 1 1計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的基本概念計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的基本概念1.11.1名詞解釋名詞解釋系統(tǒng)加速比：系統(tǒng)改進(jìn)前與改進(jìn)后總執(zhí)行時(shí)間之比系統(tǒng)加速比：系統(tǒng)改進(jìn)前與改進(jìn)后總執(zhí)行時(shí)間之比CPI：指令周期數(shù)（：指令周期數(shù)（Cycles of Instruction)并行性：在同一時(shí)刻或同一時(shí)間間隔內(nèi)完成兩種或兩種并行性：在同一時(shí)刻或同一時(shí)間間隔內(nèi)完成兩種或兩種以上的性質(zhì)相同或不同的工作。以上的性質(zhì)相同或不同的工作。翻譯：先把翻譯：先把N1級(jí)程序全部變換成級(jí)程序全部變換成N級(jí)程序之后，再去級(jí)

5、程序之后，再去執(zhí)行執(zhí)行N級(jí)程序，在執(zhí)行過(guò)程中，級(jí)程序，在執(zhí)行過(guò)程中，N1級(jí)程序不再被訪問(wèn)級(jí)程序不再被訪問(wèn)（基于層次結(jié)構(gòu)）（基于層次結(jié)構(gòu)）解釋：每當(dāng)一條解釋：每當(dāng)一條N1級(jí)指令被譯碼后，就直接去執(zhí)行一級(jí)指令被譯碼后，就直接去執(zhí)行一串等效的串等效的N級(jí)指令，然后再去取下一條級(jí)指令，然后再去取下一條N1級(jí)指令，依級(jí)指令，依此重復(fù)進(jìn)行。此重復(fù)進(jìn)行。1 1計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的基本概念計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的基本概念1.11.1名詞解釋名詞解釋例例：設(shè)某程序中設(shè)某程序中FPFP操作占操作占20%20%，其平均，其平均CPI=4.0, CPI=4.0, FPSQRFPSQR操作的比例占操作的比例占4%4%，其平均，其平

6、均CPI=20.0, CPI=20.0, 其它指令平均其它指令平均CPI=1.20CPI=1.20，現(xiàn)采用兩種方法進(jìn)行優(yōu)化，現(xiàn)采用兩種方法進(jìn)行優(yōu)化: : a. a. 將將FPFP操作的操作的CPICPI減為減為2;2;b. b. 將將FPSQRFPSQR操作的操作的CPICPI減少為減少為12;12;問(wèn)問(wèn)1 1：哪一種方法更優(yōu)哪一種方法更優(yōu)? ?問(wèn)問(wèn)2 2：若同時(shí)采用若同時(shí)采用a a、b b方法，系統(tǒng)的加速比為多少？方法，系統(tǒng)的加速比為多少？1 1計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的基本概念計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的基本概念1.21.2問(wèn)問(wèn)1 1解解：比較：比較2方案的方案的CPI即可即可 CPIa =（1-20%-4%）

7、CPI其他其他+（20%CPIFP ） +（4%CPIFPSQR）CPIb =（1-20%-4%）CPI其他其他+（20%CPIFP ） +（4%CPIFPSQR） = 76% 1.20 + 20% 4 +4% 12 =2.3 所以，采用方法所以，采用方法a更優(yōu)。更優(yōu)。1 1計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的基本概念計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的基本概念1.21.2問(wèn)問(wèn)2 2解解： 加速比：加速比：4 . 112%42%2020. 1%7620%44%2020. 1%76%4%20%)4%201 (%4%20%)4%201 ()()()()()()( ICICURFPQSPFFPQSRFPCPICPICPICPICPICPI

8、CPICPICPICPICPCPUS其它其它新原時(shí)鐘周期長(zhǎng)新時(shí)鐘周期長(zhǎng)原新時(shí)間原時(shí)間1 1計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的基本概念計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的基本概念1.21.2例例：假設(shè)我們考慮條件分支指令的兩種不同設(shè)計(jì)方法如下：假設(shè)我們考慮條件分支指令的兩種不同設(shè)計(jì)方法如下： (1) CPU(1) CPUA A：通過(guò)比較指令設(shè)置條件碼，然后測(cè)試條件碼進(jìn)行分支：通過(guò)比較指令設(shè)置條件碼，然后測(cè)試條件碼進(jìn)行分支(2)(2) CPUCPUB B：在分支指令中包括比較過(guò)程：在分支指令中包括比較過(guò)程在兩種在兩種CPUCPU中，條件分支指令都占用中，條件分支指令都占用2 2個(gè)時(shí)鐘周期而所有其它指令個(gè)時(shí)鐘周期而所有其它指令占用占用1

9、 1個(gè)時(shí)鐘周期，對(duì)于個(gè)時(shí)鐘周期，對(duì)于CPUCPUA A，執(zhí)行的指令中分支指令占，執(zhí)行的指令中分支指令占20%20%；由于；由于每個(gè)分支指令之前都需要有比較指令，因此比較指令也占每個(gè)分支指令之前都需要有比較指令，因此比較指令也占20%20%。由。由于于CPUCPUB B在分支時(shí)需要比較，因此假設(shè)它的時(shí)鐘周期時(shí)間是在分支時(shí)需要比較，因此假設(shè)它的時(shí)鐘周期時(shí)間是CPUCPUA A的的1.251.25倍。倍。問(wèn)問(wèn)1 1：哪一個(gè)哪一個(gè)CPUCPU更快？更快？1 1計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的基本概念計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的基本概念1.31.3我們不考慮所有系統(tǒng)問(wèn)題，所以可用我們不考慮所有系統(tǒng)問(wèn)題，所以可用CPUCPU性能公式

10、。占用性能公式。占用2 2個(gè)時(shí)鐘周期的分支指令占總指令的個(gè)時(shí)鐘周期的分支指令占總指令的20%20%，剩下的指令占用，剩下的指令占用1 1個(gè)時(shí)鐘周期。所以個(gè)時(shí)鐘周期。所以 CPICPIA A = 20% = 20% 2 + 80% 2 + 80% 則則CPUCPU性能為：性能為： 總總CPUCPU時(shí)間時(shí)間A A = IC= ICA A 1.2 1.2 時(shí)鐘周期時(shí)鐘周期A A解解1：1 1計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的基本概念計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的基本概念1.31.3根據(jù)假設(shè)，有：根據(jù)假設(shè)，有： 時(shí)鐘周期時(shí)鐘周期B B = 1.25 = 1.25 時(shí)鐘周期時(shí)鐘周期A A在在CPUCPUB B中沒(méi)有獨(dú)立的比較指令，所以

11、中沒(méi)有獨(dú)立的比較指令，所以CPUCPUB B的程序量為的程序量為CPUCPUA A的的80%80%，分支指令的比例為：，分支指令的比例為： 20%/80% = 25%20%/80% = 25%這些分支指令占用這些分支指令占用2 2個(gè)時(shí)鐘周期，而剩下的個(gè)時(shí)鐘周期，而剩下的75%75%的指令占的指令占用用1 1個(gè)時(shí)鐘周期，因此：個(gè)時(shí)鐘周期，因此： CPICPIB B = 0.25 = 0.25 2 + 0.75 2 + 0.75 因?yàn)橐驗(yàn)镃PUCPUB B不執(zhí)行比較，故：不執(zhí)行比較，故： ICICB B = 0.8 = 0.8 IC ICA A解解1：1 1計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的基本概念計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的

12、基本概念1.31.3因此因此CPUCPUB B性能為：性能為： 總總CPUCPU時(shí)間時(shí)間B B = IC = ICB B CPI CPIB B 時(shí)鐘周期時(shí)鐘周期B B = 0.8 = 0.8 IC ICA A 1.25 1.25 (1.25 (1.25 時(shí)鐘周期時(shí)鐘周期A A) ) = 1.25 = 1.25 IC ICA A 時(shí)鐘周期時(shí)鐘周期A A在這些假設(shè)之下，盡管在這些假設(shè)之下，盡管CPUCPUB B執(zhí)行指令條數(shù)較少，執(zhí)行指令條數(shù)較少，CPUCPUA A因?yàn)橛兄痰臅r(shí)鐘周期，所以比因?yàn)橛兄痰臅r(shí)鐘周期，所以比CPUCPUB B快?？?。解解1：1 1計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的基本概念計(jì)算機(jī)系統(tǒng)結(jié)

13、構(gòu)的基本概念1.31.3 例例：我們分析一個(gè)用于：我們分析一個(gè)用于WebWeb服務(wù)器系統(tǒng)的處理器的性能。服務(wù)器系統(tǒng)的處理器的性能。假定采用某增強(qiáng)方式使新的假定采用某增強(qiáng)方式使新的CPUCPU處理處理WebWeb服務(wù)器應(yīng)用程序的運(yùn)服務(wù)器應(yīng)用程序的運(yùn)行速度是原來(lái)處理器中的行速度是原來(lái)處理器中的1010倍，同時(shí)假定此倍，同時(shí)假定此CPUCPU有有40%40%的時(shí)間的時(shí)間用于計(jì)算，另外用于計(jì)算，另外60%60%的時(shí)間用于的時(shí)間用于I/OI/O操作。那么增強(qiáng)性能后總操作。那么增強(qiáng)性能后總的加速比是多少？的加速比是多少？ 解解 增強(qiáng)加速比增強(qiáng)加速比 = 10= 10總加速比總加速比 = = 1 10.6

14、+0.6 +0.40.41010= =0.640.64= 1.56= 1.561 11 1計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的基本概念計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的基本概念1.41.4例例：設(shè)某計(jì)算機(jī)系統(tǒng)執(zhí)行程序中，可向量化部分最大可達(dá)：設(shè)某計(jì)算機(jī)系統(tǒng)執(zhí)行程序中，可向量化部分最大可達(dá)70%70%。一種實(shí)現(xiàn)方法是采用陳列多處理機(jī)即硬件方式實(shí)現(xiàn)，使一種實(shí)現(xiàn)方法是采用陳列多處理機(jī)即硬件方式實(shí)現(xiàn)，使60%60%的的向量化指令執(zhí)行速度加快到原來(lái)的向量化指令執(zhí)行速度加快到原來(lái)的1010倍，另一種方法是采用優(yōu)倍，另一種方法是采用優(yōu)化編譯系統(tǒng)的方法實(shí)現(xiàn)，使向量化程序可達(dá)化編譯系統(tǒng)的方法實(shí)現(xiàn)，使向量化程序可達(dá)70%70%，且速度可增，且速度可增

15、加加3 3倍。請(qǐng)比較這兩種方案哪種更優(yōu)。倍。請(qǐng)比較這兩種方案哪種更優(yōu)。解：解：通過(guò)計(jì)算加速比知，硬件方案較優(yōu)！通過(guò)計(jì)算加速比知，硬件方案較優(yōu)！53. 013/7 . 0%)701 (146. 0110/6 . 0%)601 (1編譯硬件SS1 1計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的基本概念計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的基本概念1.51.5Assume a simple load/store machine with the following instruction frequency:Instruction typeFrequencyCyclesLoads25%2Stores15%2Branches20%2ALU40%1co

16、nditional branches currently use simple test against 0Should we add complex comparison/branch combination (BEQ Rn,Rm,LOC orBNE Rn,Rm,LOC) -25% of branches can use the complex scheme and save(節(jié)省了）節(jié)省了） the preceding ALU instruction -The CPU cycle time(CCT) of the machine has to be 10% longer -Will thi

17、s increase CPU performance?1 1計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的基本概念計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的基本概念1.61.61 1計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的基本概念計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的基本概念1.61.6使用使用40MHz時(shí)鐘速率的處理機(jī)執(zhí)行一個(gè)測(cè)試程序，時(shí)鐘速率的處理機(jī)執(zhí)行一個(gè)測(cè)試程序，它的主要指令類型所執(zhí)行的指令數(shù)及所需的時(shí)鐘周期它的主要指令類型所執(zhí)行的指令數(shù)及所需的時(shí)鐘周期數(shù)如下，試計(jì)算執(zhí)行此程序的有效數(shù)如下，試計(jì)算執(zhí)行此程序的有效CPI，MIPS速率速率及總的及總的CPU時(shí)間。（時(shí)間。（p33習(xí)題習(xí)題1.19)指令類型指令數(shù)時(shí)鐘周期數(shù)整數(shù)算術(shù)450001數(shù)據(jù)傳送320002浮點(diǎn)150002控制轉(zhuǎn)移800

18、021 1計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的基本概念計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的基本概念1.71.7 p33p33習(xí)題習(xí)題1.19 1.19 總時(shí)鐘周期數(shù)總時(shí)鐘周期數(shù)=45000*1+32000*2+15000*2+8000*2=155000總指令數(shù)總指令數(shù)=45000+32000+15000+8000=100000總總CPU執(zhí)行時(shí)間執(zhí)行時(shí)間=155000/40* 10-6MIPS=總指令數(shù)總指令數(shù)*10-61 1計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的基本概念計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的基本概念1.71.7 p33p33習(xí)題習(xí)題1.19 1.19 1 1計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的基本概念計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的基本概念1.81.8 p33p33習(xí)題習(xí)題1.20 1.20 某

19、工作站采用時(shí)鐘頻率為某工作站采用時(shí)鐘頻率為15MHz，處理速率為，處理速率為10MIPS的處理機(jī)來(lái)執(zhí)行一個(gè)已知混合程序。假定的處理機(jī)來(lái)執(zhí)行一個(gè)已知混合程序。假定每次存儲(chǔ)器存取為每次存儲(chǔ)器存取為1周期延遲，試問(wèn)：周期延遲，試問(wèn)：（1）此計(jì)算機(jī)的有效）此計(jì)算機(jī)的有效CPI是多少？是多少？（2）時(shí)鐘提高到）時(shí)鐘提高到30MHz，但存儲(chǔ)器子系統(tǒng)速率不，但存儲(chǔ)器子系統(tǒng)速率不變。這樣，每次存儲(chǔ)器存取需要變。這樣，每次存儲(chǔ)器存取需要2個(gè)時(shí)鐘周期。如個(gè)時(shí)鐘周期。如果果30%指令每條只需要指令每條只需要1次存儲(chǔ)存取，而另外次存儲(chǔ)存取，而另外5%每條需要每條需要2次存儲(chǔ)存取，還假定已知混合程序的指次存儲(chǔ)存取，還假

20、定已知混合程序的指令數(shù)不變，并與原工作站兼容，試求改進(jìn)后的處理令數(shù)不變，并與原工作站兼容，試求改進(jìn)后的處理機(jī)性能。機(jī)性能。1 1計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的基本概念計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的基本概念1.81.8 p33p33習(xí)題習(xí)題1.20 1.20 解：解：（1）設(shè)該程序執(zhí)行時(shí)間為）設(shè)該程序執(zhí)行時(shí)間為t，則，則CPI=總時(shí)鐘周期數(shù)總時(shí)鐘周期數(shù)/總指令數(shù)總指令數(shù)=(t*15M)/(t*10M)（2） 公式：公式： CPUtime=IC*CPI*CCT 即有：即有： CPUtime=指令數(shù)指令周期數(shù)指令數(shù)指令周期數(shù)cpu周期時(shí)間周期時(shí)間1 1計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的基本概念計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的基本概念1.81.8 p33p33習(xí)

21、題習(xí)題1.20 1.20 1 1計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的基本概念計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的基本概念1.91.9 p34p34習(xí)題習(xí)題1.21 1.21 24. 21 . 0812. 0418. 026 . 01CPI86.171024. 2104010666CPIfMIPS 解：解：2 2指令系統(tǒng)指令系統(tǒng)2.12.1名詞解釋名詞解釋 CISC:CISC:復(fù)雜指令集計(jì)算機(jī)（復(fù)雜指令集計(jì)算機(jī)（Complex Instruction Complex Instruction Set ComputerSet Computer）。）。強(qiáng)化指令功能，設(shè)置一些功能復(fù)強(qiáng)化指令功能，設(shè)置一些功能復(fù)雜的指令，把一些原來(lái)由軟件實(shí)現(xiàn)的、

22、常用的功能雜的指令，把一些原來(lái)由軟件實(shí)現(xiàn)的、常用的功能改用硬件的指令系統(tǒng)來(lái)實(shí)現(xiàn)，基于這種指令集結(jié)構(gòu)改用硬件的指令系統(tǒng)來(lái)實(shí)現(xiàn)，基于這種指令集結(jié)構(gòu)而設(shè)計(jì)實(shí)現(xiàn)的計(jì)算機(jī)系統(tǒng)稱為而設(shè)計(jì)實(shí)現(xiàn)的計(jì)算機(jī)系統(tǒng)稱為CISCCISC計(jì)算機(jī)。計(jì)算機(jī)。RISC:RISC:精簡(jiǎn)指令集計(jì)算機(jī)（精簡(jiǎn)指令集計(jì)算機(jī)（Reduced Instruction Reduced Instruction Set ComputerSet Computer）。）。盡量簡(jiǎn)化指令功能，只保留那些盡量簡(jiǎn)化指令功能，只保留那些功能簡(jiǎn)單，能在一個(gè)周期內(nèi)執(zhí)行完成的指令，較復(fù)功能簡(jiǎn)單，能在一個(gè)周期內(nèi)執(zhí)行完成的指令，較復(fù)雜的功能用一段子程序來(lái)實(shí)現(xiàn)，這種計(jì)算機(jī)

23、系統(tǒng)稱雜的功能用一段子程序來(lái)實(shí)現(xiàn)，這種計(jì)算機(jī)系統(tǒng)稱為為RISCRISC計(jì)算機(jī)。計(jì)算機(jī)。 返回目錄2 2指令系統(tǒng)指令系統(tǒng)2.22.2簡(jiǎn)答簡(jiǎn)答 RISCRISC的關(guān)鍵技術(shù)有哪些？的關(guān)鍵技術(shù)有哪些？延時(shí)轉(zhuǎn)移技術(shù)延時(shí)轉(zhuǎn)移技術(shù)指令取消技術(shù)指令取消技術(shù)重疊寄存器窗口技術(shù)重疊寄存器窗口技術(shù)指令流調(diào)整技術(shù)指令流調(diào)整技術(shù)硬件為主，固件為輔硬件為主，固件為輔2 2指令系統(tǒng)指令系統(tǒng)2.32.3例例: 某計(jì)算機(jī)有某計(jì)算機(jī)有10條指令，它們的使用頻條指令，它們的使用頻率分別為率分別為(1) 用霍夫曼編碼對(duì)它們的操作碼進(jìn)行編碼，并用霍夫曼編碼對(duì)它們的操作碼進(jìn)行編碼，并計(jì)算平均代碼長(zhǎng)度。計(jì)算平均代碼長(zhǎng)度。(2) 用擴(kuò)展霍夫

24、曼編碼法對(duì)操作碼進(jìn)行編碼，限用擴(kuò)展霍夫曼編碼法對(duì)操作碼進(jìn)行編碼，限兩種操作碼長(zhǎng)度，并計(jì)算平均代碼長(zhǎng)度。兩種操作碼長(zhǎng)度，并計(jì)算平均代碼長(zhǎng)度。2 2指令系統(tǒng)指令系統(tǒng)2.32.30.151.000.390.190.100.060.030.310.610.010.020.030.040.070.080.090.160.200.30答：答：(1) 霍夫曼樹如下霍夫曼樹如下：2 2指令系統(tǒng)指令系統(tǒng)2.32.3霍夫曼編碼的結(jié)果以及各編碼的長(zhǎng)度如下所示：霍夫曼編碼的結(jié)果以及各編碼的長(zhǎng)度如下所示：11 01 101 001 1001 1000 0001 00001 000001 000002 2 3 3 4 4

25、 4 5 6 6平均代碼長(zhǎng)度為平均代碼長(zhǎng)度為2 2指令系統(tǒng)指令系統(tǒng)2.32.3(2) 用擴(kuò)展霍夫曼編碼法對(duì)操作碼進(jìn)行編碼，限兩種用擴(kuò)展霍夫曼編碼法對(duì)操作碼進(jìn)行編碼，限兩種操作碼長(zhǎng)度，采用長(zhǎng)度為操作碼長(zhǎng)度，采用長(zhǎng)度為2和長(zhǎng)度為和長(zhǎng)度為4兩種編碼：兩種編碼： 00 01 1000 1001 1010 1011 1100 1101 1110 111100 01 1000 1001 1010 1011 1100 1101 1110 1111平均代碼長(zhǎng)度為平均代碼長(zhǎng)度為2 2指令系統(tǒng)指令系統(tǒng)出現(xiàn)的概率出現(xiàn)的概率Huffman編碼編碼2/8擴(kuò)展碼擴(kuò)展碼3/7擴(kuò)展碼擴(kuò)展碼0.251000000.200001

26、010.151101000100.100101001110000.0801111010110010.0811101011110100.0501101100110110.04111101101111000.031111111110111010.02111110111111110解：解：2 2指令系統(tǒng)指令系統(tǒng)解：解：出現(xiàn)的概率出現(xiàn)的概率Huffman編碼編碼2/8擴(kuò)展碼擴(kuò)展碼3/7擴(kuò)展碼擴(kuò)展碼操作碼平均操作碼平均長(zhǎng)度長(zhǎng)度2.993.13.2操作碼的信操作碼的信息冗余量息冗余量n1iiilp平均長(zhǎng)度956635.2.log*12niiippH2 2指令系統(tǒng)指令系統(tǒng)解：解：度本編碼操作碼的平均長(zhǎng)編碼操

27、作碼的平均長(zhǎng)度最優(yōu)HHuffmanR1出現(xiàn)的概率出現(xiàn)的概率Huffman編碼編碼2/8擴(kuò)展碼擴(kuò)展碼3/7擴(kuò)展碼擴(kuò)展碼操作碼平均操作碼平均長(zhǎng)度長(zhǎng)度2.993.13.2操作碼的信操作碼的信息冗余量息冗余量1.10%4.61% 7.59%2 2指令系統(tǒng)指令系統(tǒng)2 2指令系統(tǒng)指令系統(tǒng)解解:（1）應(yīng)采用）應(yīng)采用Huffman編碼，構(gòu)造編碼，構(gòu)造Huffman樹如下：樹如下：2 2指令系統(tǒng)指令系統(tǒng)2 2指令系統(tǒng)指令系統(tǒng)2 2指令系統(tǒng)指令系統(tǒng)2 2指令系統(tǒng)指令系統(tǒng)2 2指令系統(tǒng)指令系統(tǒng)解解:（1）首先，我們可以根據(jù)指令地址的數(shù)量來(lái)決定各種指令）首先，我們可以根據(jù)指令地址的數(shù)量來(lái)決定各種指令在指令空間上的分布

28、：在指令空間上的分布：2 2指令系統(tǒng)指令系統(tǒng)2 2指令系統(tǒng)指令系統(tǒng)2 2指令系統(tǒng)指令系統(tǒng)解：解：START: MOVE AS, R1 MOVE NUM, R2LOOP: MOVE (R1), AD-AS(R1) INC R1 DEC R2 BGT LOOP HALTNUM: NHALT指令共取指令共取100次，但前次，但前99次都次都被取消。被取消。2 2指令系統(tǒng)指令系統(tǒng)解：解：(1)START: MOVE AS, R1 MOVE NUM, R2 MOVE (R1), AD-AS(R1)LOOP: INC R1 DEC R2 BGT LOOP _ _ MOVE (R1), AD-AS(R1)

29、_ _ HALTNUM: NMOVE指令共取指令共取100次，但前次，但前99次都被正常執(zhí)次都被正常執(zhí)行，只有最后行，只有最后1次被取消。次被取消。2 2指令系統(tǒng)指令系統(tǒng)解：解：(2)因?yàn)椴捎弥噶钊∠夹g(shù)前，取消指令次數(shù)為因?yàn)椴捎弥噶钊∠夹g(shù)前，取消指令次數(shù)為99次，次，而在采用指令取消技術(shù)后，取消指令次數(shù)為而在采用指令取消技術(shù)后，取消指令次數(shù)為1次，所次，所以節(jié)省的指令周期數(shù)為：以節(jié)省的指令周期數(shù)為：991982 2指令系統(tǒng)指令系統(tǒng)START: MOVE AS, R1 MOVE NUM, R2 MOVE (R1), AD-AS(R1) INC R1LOOP: DEC R2 BGT LOOP

30、_ _ _ MOVE (R1), AD-AS(R1) _ _ _ INC R1 _ _ _ HALTNUM: N解：解：(3)3 3存儲(chǔ)系統(tǒng)存儲(chǔ)系統(tǒng)3.13.1名詞解釋名詞解釋 返回目錄存儲(chǔ)系統(tǒng)存儲(chǔ)系統(tǒng): :由多個(gè)不同性能的存儲(chǔ)器組成的有機(jī)的一由多個(gè)不同性能的存儲(chǔ)器組成的有機(jī)的一體化的存儲(chǔ)體。體化的存儲(chǔ)體。LRU:LRU:近期最少使用算法近期最少使用算法(Least Recently Used (Least Recently Used Algorithm)Algorithm)。一種頁(yè)面替換算法，這種算法選擇近一種頁(yè)面替換算法，這種算法選擇近期最少訪問(wèn)的頁(yè)面作為被替換的頁(yè)面。期最少訪問(wèn)的頁(yè)面作為

31、被替換的頁(yè)面。LFULFU：最久沒(méi)用使用的算法最久沒(méi)用使用的算法LFULFU（Least Least Frequently Used AlgorithmFrequently Used Algorithm）。一種頁(yè)面替換算法，。一種頁(yè)面替換算法，這種算法把近期最久沒(méi)有訪問(wèn)過(guò)的頁(yè)面作為被替換這種算法把近期最久沒(méi)有訪問(wèn)過(guò)的頁(yè)面作為被替換的頁(yè)面。的頁(yè)面。3 3存儲(chǔ)系統(tǒng)存儲(chǔ)系統(tǒng)3.13.1名詞解釋名詞解釋“顛簸顛簸”現(xiàn)象現(xiàn)象(thrashing)：下次就要使用的頁(yè)面本：下次就要使用的頁(yè)面本次被替換出去，這種現(xiàn)象稱為次被替換出去，這種現(xiàn)象稱為。全相聯(lián)映象全相聯(lián)映象：主存中的任一塊可以被放置到：主存中的任一

32、塊可以被放置到CacheCache中中的任意一個(gè)位置。的任意一個(gè)位置。直接映象直接映象：主存中的每一塊只能被放置到：主存中的每一塊只能被放置到CacheCache中唯中唯一的一個(gè)位置。一的一個(gè)位置。 組相聯(lián)組相聯(lián)：主存中的每一塊可以被放置到：主存中的每一塊可以被放置到CacheCache中唯一中唯一的一個(gè)組中的任何一個(gè)位置。的一個(gè)組中的任何一個(gè)位置。3 3存儲(chǔ)系統(tǒng)存儲(chǔ)系統(tǒng)3.13.1名詞解釋名詞解釋寫寫直達(dá)法：直達(dá)法：執(zhí)行執(zhí)行“寫寫”操作時(shí)，不僅寫入操作時(shí)，不僅寫入CacheCache，而，而且也寫入下一級(jí)存儲(chǔ)器。且也寫入下一級(jí)存儲(chǔ)器。寫回法：寫回法：執(zhí)行執(zhí)行“寫寫”操作時(shí)，只寫入操作時(shí)，只寫

33、入CacheCache。僅當(dāng)。僅當(dāng)CacheCache中相應(yīng)的塊被替換時(shí)，才寫回主存。中相應(yīng)的塊被替換時(shí)，才寫回主存。按寫分配按寫分配( (寫時(shí)取寫時(shí)取) )：寫失效時(shí)，先把所寫單元所在寫失效時(shí)，先把所寫單元所在的塊調(diào)入的塊調(diào)入CacheCache，再行寫入，再行寫入. .不按寫分配不按寫分配( (繞寫法繞寫法) )：寫失效時(shí)，直接寫入下一級(jí)寫失效時(shí)，直接寫入下一級(jí)存儲(chǔ)器而不調(diào)塊。存儲(chǔ)器而不調(diào)塊。3 3存儲(chǔ)系統(tǒng)存儲(chǔ)系統(tǒng)3.23.2簡(jiǎn)答簡(jiǎn)答常用的頁(yè)面替換算法有哪些？常用的頁(yè)面替換算法有哪些？隨機(jī)算法隨機(jī)算法RAND算法算法(random Algorithm)FIFO算法算法（first in f

34、irst out Algorithm)近期最少使用近期最少使用LRU算法算法(Least Recently Used Algorithm)最久沒(méi)用使用的算法最久沒(méi)用使用的算法LFU（Least Frequently Used Algorithm）最優(yōu)替換算法，即最優(yōu)替換算法，即OPT算法算法（Optional Replacement algorithm）3 3存儲(chǔ)系統(tǒng)存儲(chǔ)系統(tǒng)3.23.2簡(jiǎn)答簡(jiǎn)答虛擬存儲(chǔ)器中，影響主存命中率的主要因素有？虛擬存儲(chǔ)器中，影響主存命中率的主要因素有？程序在執(zhí)行過(guò)程中的頁(yè)地址流的分布情況；程序在執(zhí)行過(guò)程中的頁(yè)地址流的分布情況；所采用的頁(yè)面替換算法；所采用的頁(yè)面替換算法

35、；頁(yè)面的大小頁(yè)面的大小主存容量主存容量頁(yè)面調(diào)度算法頁(yè)面調(diào)度算法3 3存儲(chǔ)系統(tǒng)存儲(chǔ)系統(tǒng)3.23.2簡(jiǎn)答簡(jiǎn)答簡(jiǎn)要介紹簡(jiǎn)要介紹CacheCache與主存的三種地址映象方式，并舉例與主存的三種地址映象方式，并舉例加以說(shuō)明？加以說(shuō)明？(略略)3 3存儲(chǔ)系統(tǒng)存儲(chǔ)系統(tǒng)解：解：(1)頁(yè)地頁(yè)地址流址流p2p3p2p1p5p2p4p5p3p2p5p2命中命中次數(shù)次數(shù)3個(gè)個(gè)主存主存頁(yè)面頁(yè)面FIFO222255553333333332222255111444442調(diào)調(diào)入入調(diào)調(diào)入入命命中中調(diào)調(diào)入入替替換換替替換換替替換換命命中中替替換換命命中中替替換換替替換換3 3存儲(chǔ)系統(tǒng)存儲(chǔ)系統(tǒng)解：解：(1)頁(yè)地頁(yè)地址流址流p2p3

36、p2p1p5p2p4p5p3p2p5p2命中命中次數(shù)次數(shù)3個(gè)個(gè)主存主存頁(yè)面頁(yè)面LFU222222223333533355555555111444222調(diào)調(diào)入入調(diào)調(diào)入入命命中中調(diào)調(diào)入入替替換換命命中中替替換換命命中中替替換換替替換換命命中中命命中中3 3存儲(chǔ)系統(tǒng)存儲(chǔ)系統(tǒng)解：解：(1)頁(yè)地頁(yè)地址流址流p2p3p2p1p5p2p4p5p3p2p5p2命中命中次數(shù)次數(shù)3個(gè)個(gè)主存主存頁(yè)面頁(yè)面OPT222222444222633333333333155555555調(diào)調(diào)入入調(diào)調(diào)入入命命中中調(diào)調(diào)入入替替換換命命中中替替換換命命中中命命中中替替換換命命中中命命中中3 3存儲(chǔ)系統(tǒng)存儲(chǔ)系統(tǒng)解：解：(2)FIFO頁(yè)面

37、替換算法的頁(yè)命中率：頁(yè)面替換算法的頁(yè)命中率：3/12LFU頁(yè)面替換算法的頁(yè)命中率：頁(yè)面替換算法的頁(yè)命中率：5/12OPT頁(yè)面替換算法的頁(yè)命中率：頁(yè)面替換算法的頁(yè)命中率：6/123 3存儲(chǔ)系統(tǒng)存儲(chǔ)系統(tǒng)解：解：(1)可能的最高頁(yè)命中率出現(xiàn)在可能的最高頁(yè)命中率出現(xiàn)在: :頁(yè)地址流中每一種都可以單獨(dú)占一個(gè)頁(yè)面時(shí)，頁(yè)地址流中每一種都可以單獨(dú)占一個(gè)頁(yè)面時(shí)，因?yàn)閷?duì)于各種頁(yè)地址流，都是第一次因?yàn)閷?duì)于各種頁(yè)地址流，都是第一次“調(diào)入調(diào)入”，其后，其后各次都是各次都是“命中命中”。在此例中，需。在此例中，需5 5個(gè)頁(yè)面。因此：個(gè)頁(yè)面。因此：可能的最高頁(yè)命中率可能的最高頁(yè)命中率（頁(yè)地址流個(gè)數(shù)頁(yè)地址流種數(shù)）（頁(yè)地址流個(gè)

38、數(shù)頁(yè)地址流種數(shù)）/ /頁(yè)地址流個(gè)數(shù)頁(yè)地址流個(gè)數(shù)（12125 5）/12/12= 7/12= 7/123 3存儲(chǔ)系統(tǒng)存儲(chǔ)系統(tǒng)解：解：(1)或通過(guò)或通過(guò)“堆棧模擬法堆棧模擬法”，求得命中次數(shù)隨主存頁(yè)數(shù)變化的函，求得命中次數(shù)隨主存頁(yè)數(shù)變化的函數(shù)關(guān)系。下圖就是數(shù)關(guān)系。下圖就是“堆棧模擬圖堆棧模擬圖”，其中，其中“”表示命中。表示命中。 Hmax=7/1258.3%Hmax=7/1258.3%3 3存儲(chǔ)系統(tǒng)存儲(chǔ)系統(tǒng)解：解：(2)至少分配至少分配4 4個(gè)個(gè)頁(yè)面才能獲得最高的命中率頁(yè)面才能獲得最高的命中率7/12 .7/12 .3 3存儲(chǔ)系統(tǒng)存儲(chǔ)系統(tǒng)解：解：(3)訪問(wèn)存儲(chǔ)單元的命中率訪問(wèn)存儲(chǔ)單元的命中率命中

39、次數(shù)命中次數(shù)/ /總訪問(wèn)次數(shù)總訪問(wèn)次數(shù)(12(121024-5)/(121024-5)/(121024)1024)12283/1228812283/1228899.96% 99.96% 分析：分析：頁(yè)頁(yè)“不命中不命中”時(shí)，僅第時(shí)，僅第1 1次不命中，其它次不命中，其它10231023次次都是命中的。而在頁(yè)都是命中的。而在頁(yè)“命中命中”時(shí)，時(shí)，10241024次都是命中的。次都是命中的。所以總訪問(wèn)次數(shù)為所以總訪問(wèn)次數(shù)為1212* *10241024，不命中次數(shù)為，不命中次數(shù)為5 53 3存儲(chǔ)系統(tǒng)存儲(chǔ)系統(tǒng)解：（解：（1）主存地址）主存地址區(qū)號(hào)區(qū)號(hào)組號(hào)組號(hào)塊號(hào)塊號(hào)塊內(nèi)地址塊內(nèi)地址6 6 5 5 4

40、4 3 3 0 0 組號(hào)組號(hào)塊號(hào)塊號(hào)塊內(nèi)地址塊內(nèi)地址5 5 4 4 3 3 0 0 解：（解：（2）緩存地址）緩存地址3 3存儲(chǔ)系統(tǒng)存儲(chǔ)系統(tǒng)解：（解：（3）主存與）主存與Cache的塊映象關(guān)系的塊映象關(guān)系C0C1C2C3B0B1B2B3B4B5B6B7Cache主存主存3 3存儲(chǔ)系統(tǒng)存儲(chǔ)系統(tǒng)解：（解：（3）主存與）主存與Cache的塊映象關(guān)系的塊映象關(guān)系3 3存儲(chǔ)系統(tǒng)存儲(chǔ)系統(tǒng)解：（解：（4）通過(guò)作通過(guò)作“實(shí)存狀況圖實(shí)存狀況圖”模擬各虛塊的調(diào)度模擬各虛塊的調(diào)度情況，可獲得情況，可獲得CacheCache的塊地址流序列。的塊地址流序列。此問(wèn)最容易出錯(cuò)的地方是忽略此問(wèn)最容易出錯(cuò)的地方是忽略“組相聯(lián)組

41、相聯(lián)”地址約束，地址約束，將虛頁(yè)裝錯(cuò)實(shí)組。另外沒(méi)有及時(shí)標(biāo)注將虛頁(yè)裝錯(cuò)實(shí)組。另外沒(méi)有及時(shí)標(biāo)注“* *”號(hào)也容易號(hào)也容易導(dǎo)致淘汰對(duì)象錯(cuò)誤。導(dǎo)致淘汰對(duì)象錯(cuò)誤。 3 3存儲(chǔ)系統(tǒng)存儲(chǔ)系統(tǒng)解：（解：（5）采用采用LFULFU替換算法，命中率為替換算法，命中率為4/124/12頁(yè)地頁(yè)地址流址流B6B2B4B1B4B6B3B0B4B5B7B3命中命中率率C0C1C2C344444444441111005554/126 6666666667722222333333調(diào)調(diào)入入調(diào)調(diào)入入調(diào)調(diào)入入調(diào)調(diào)入入命命中中命命中中替替換換替替換換命命中中替替換換替替換換命命中中3 3存儲(chǔ)系統(tǒng)存儲(chǔ)系統(tǒng)解：（解：（6）采用采用FIFO

42、FIFO替換算法，命中率為替換算法，命中率為3/123/12頁(yè)地頁(yè)地址流址流B6B2B4B1B4B6B3B0B4B5B7B3命中命中率率C0C1C2C344444005541111144453/126 6666633333322222222277調(diào)調(diào)入入調(diào)調(diào)入入調(diào)調(diào)入入調(diào)調(diào)入入命命中中命命中中替替換換替替換換替替換換替替換換替替換換命命中中3 3存儲(chǔ)系統(tǒng)存儲(chǔ)系統(tǒng)解：（解：（7）1采用采用LFULFU替換算法替換算法( (全相聯(lián)全相聯(lián)) )，命中率，命中率3/123/12頁(yè)地頁(yè)地址流址流B6B2B4B1B4B6B3B0B4B5B7B3命中命中率率C0C1C2C36 666666665552222

43、23333773/124444444444111100003調(diào)調(diào)入入調(diào)調(diào)入入調(diào)調(diào)入入調(diào)調(diào)入入命命中中命命中中替替換換替替換換命命中中替替換換替替換換替替換換3 3存儲(chǔ)系統(tǒng)存儲(chǔ)系統(tǒng)解：（解：（7）2采用采用FIFOFIFO替換算法替換算法( (全相聯(lián)全相聯(lián)) )，命中率，命中率4/124/12頁(yè)地頁(yè)地址流址流B6B2B4B1B4B6B3B0B4B5B7B3命中命中率率C0C1C2C36 66666333333222222000004/124444444477111111555調(diào)調(diào)入入調(diào)調(diào)入入調(diào)調(diào)入入調(diào)調(diào)入入命命中中命命中中替替換換替替換換命命中中替替換換替替換換替替換換3 3存儲(chǔ)系統(tǒng)存儲(chǔ)系統(tǒng)解：

44、（解：（8）訪問(wèn)存儲(chǔ)單元的命中率訪問(wèn)存儲(chǔ)單元的命中率命中次數(shù)命中次數(shù)/ /總訪問(wèn)次數(shù)總訪問(wèn)次數(shù)(12(1216-8)/(1216-8)/(1216)16)184/192184/19295.8% 95.8% 分析：分析：頁(yè)頁(yè)“不命中不命中”時(shí)，僅第時(shí)，僅第1 1次不命中，其它次不命中，其它1515次都是次都是命中的。而在頁(yè)命中的。而在頁(yè)“命中命中”時(shí)，時(shí)，1616次都是命中的。所以次都是命中的。所以總訪問(wèn)次數(shù)為總訪問(wèn)次數(shù)為1212* *1616，不命中次數(shù)為，不命中次數(shù)為8 84 4輸入輸出系統(tǒng)輸入輸出系統(tǒng)4.14.1名詞解釋名詞解釋通道處理機(jī)：通道處理機(jī)：一種能夠執(zhí)行有限輸入輸出指令，并一種能

45、夠執(zhí)行有限輸入輸出指令，并且能夠被多臺(tái)外圍設(shè)備共享的小型且能夠被多臺(tái)外圍設(shè)備共享的小型DMADMA專用處理機(jī)。專用處理機(jī)。4 4輸入輸出系統(tǒng)輸入輸出系統(tǒng)4.24.2簡(jiǎn)答簡(jiǎn)答通道的分類？通道的分類？4 4輸入輸出系統(tǒng)輸入輸出系統(tǒng)解：解：（1 1）字節(jié)多路通道的實(shí)際工作流量為：字節(jié)多路通道的實(shí)際工作流量為：f fBYTEBYTE=100+33.3+33.3+20+10=196.6(KB/s)=100+33.3+33.3+20+10=196.6(KB/s)（2 2）在設(shè)計(jì)最大通道流量時(shí)，應(yīng)留有一定的余量，在設(shè)計(jì)最大通道流量時(shí)，應(yīng)留有一定的余量，對(duì)于字節(jié)多路通道，通道的最大流量應(yīng)略大于所有連對(duì)于字節(jié)多

46、路通道，通道的最大流量應(yīng)略大于所有連接在這個(gè)通道上的設(shè)備的流量之和。因此設(shè)計(jì)：接在這個(gè)通道上的設(shè)備的流量之和。因此設(shè)計(jì)：a) a) 通道的最大流量通道的最大流量f fMAXMAXBYTEBYTE=200(KB/s)=200(KB/s)b) b) 通道的工作周期通道的工作周期T T1/200 000=5us/byte1/200 000=5us/byte4 4輸入輸出系統(tǒng)輸入輸出系統(tǒng)（3 3）由于通道工作在最大流量，故工作周期為由于通道工作在最大流量，故工作周期為5us,5us,由時(shí)間關(guān)系圖可知，通道處理完各臺(tái)設(shè)備的第一次數(shù)由時(shí)間關(guān)系圖可知，通道處理完各臺(tái)設(shè)備的第一次數(shù)據(jù)服務(wù)請(qǐng)求的時(shí)刻如下：據(jù)服務(wù)

47、請(qǐng)求的時(shí)刻如下：D1D1：5us5usD2D2：10us10usD3D3：20us20usD4D4：30us30usD5D5：90us90us通道分時(shí)為各臺(tái)設(shè)備服務(wù)的時(shí)間關(guān)系圖通道分時(shí)為各臺(tái)設(shè)備服務(wù)的時(shí)間關(guān)系圖（略）（略）解：解：4 4輸入輸出系統(tǒng)輸入輸出系統(tǒng)解：解：（1 1）字節(jié)多路通道的實(shí)際工作流量為：字節(jié)多路通道的實(shí)際工作流量為：f fBYTEBYTE=1/10+1/75+1/15+1/50=200(KB/s)=1/10+1/75+1/15+1/50=200(KB/s)通道的工作周期為：通道的工作周期為：T T1/200 000=5us/byte1/200 000=5us/byte4 4

48、輸入輸出系統(tǒng)輸入輸出系統(tǒng)解：解：（2 2）Ts+Td=5usTs+Td=5us，通道時(shí)間圖如下。，通道時(shí)間圖如下。作圖時(shí)注意：至少要作圖時(shí)注意：至少要畫到最慢設(shè)備的第二次請(qǐng)求出現(xiàn)，才能確定是否丟失數(shù)據(jù)畫到最慢設(shè)備的第二次請(qǐng)求出現(xiàn)，才能確定是否丟失數(shù)據(jù)（因?yàn)轫憫?yīng)優(yōu)先級(jí)低的設(shè)備較易丟失數(shù)據(jù)）。（因?yàn)轫憫?yīng)優(yōu)先級(jí)低的設(shè)備較易丟失數(shù)據(jù)）。 4 4輸入輸出系統(tǒng)輸入輸出系統(tǒng)解：解：（3 3）5 5，160160，2020，4040；（4 4）D2D2丟失第一次請(qǐng)求的數(shù)據(jù)；丟失第一次請(qǐng)求的數(shù)據(jù)； （5 5）可用以下三種方法解決：（見(jiàn)可用以下三種方法解決：（見(jiàn)P245P245）增加通道的最大流量，保證連接在通道

49、上的所有設(shè)備的增加通道的最大流量，保證連接在通道上的所有設(shè)備的數(shù)據(jù)傳送請(qǐng)求能夠及時(shí)得到通道的響應(yīng)。數(shù)據(jù)傳送請(qǐng)求能夠及時(shí)得到通道的響應(yīng)。動(dòng)態(tài)改變?cè)O(shè)備的優(yōu)先級(jí)。動(dòng)態(tài)改變?cè)O(shè)備的優(yōu)先級(jí)。增加一定數(shù)量的數(shù)據(jù)緩沖器，特別是對(duì)優(yōu)先級(jí)比較低的增加一定數(shù)量的數(shù)據(jù)緩沖器，特別是對(duì)優(yōu)先級(jí)比較低的設(shè)備。如例中，為設(shè)備。如例中，為D5D5增加一數(shù)據(jù)緩沖器，則其第一次數(shù)增加一數(shù)據(jù)緩沖器，則其第一次數(shù)據(jù)傳送請(qǐng)求可以在第據(jù)傳送請(qǐng)求可以在第8585微秒處得到通道的響應(yīng)，第二次微秒處得到通道的響應(yīng)，第二次在在145145微秒處響應(yīng)。所有設(shè)備的數(shù)據(jù)都不會(huì)丟失。微秒處響應(yīng)。所有設(shè)備的數(shù)據(jù)都不會(huì)丟失。 5 5標(biāo)量處理機(jī)標(biāo)量處理機(jī)5.1

50、5.1名詞解釋名詞解釋流水線技術(shù)：流水線技術(shù)：指將一個(gè)重復(fù)的時(shí)序過(guò)程分解成為若指將一個(gè)重復(fù)的時(shí)序過(guò)程分解成為若干個(gè)子過(guò)程，而每個(gè)子過(guò)程都可有效地在其專用功干個(gè)子過(guò)程，而每個(gè)子過(guò)程都可有效地在其專用功能段上與其他子過(guò)程同時(shí)執(zhí)行能段上與其他子過(guò)程同時(shí)執(zhí)行。靜態(tài)流水線：靜態(tài)流水線：在同一時(shí)刻，流水線的各段只能按同在同一時(shí)刻，流水線的各段只能按同一種功能的連接方式工作。一種功能的連接方式工作。動(dòng)態(tài)流水線：動(dòng)態(tài)流水線：在同一時(shí)刻，流水線的各段可以按不在同一時(shí)刻，流水線的各段可以按不同功能的連接方式工作。同功能的連接方式工作。5 5標(biāo)量處理機(jī)標(biāo)量處理機(jī)5.15.1名詞解釋名詞解釋吞吐率：吞吐率：吞吐率是指

51、單位時(shí)間內(nèi)流水線所完成的任吞吐率是指單位時(shí)間內(nèi)流水線所完成的任務(wù)數(shù)或輸出結(jié)果的數(shù)量。務(wù)數(shù)或輸出結(jié)果的數(shù)量。通過(guò)時(shí)間：通過(guò)時(shí)間：第第1 1個(gè)任務(wù)從進(jìn)入流水線到流出流水線的個(gè)任務(wù)從進(jìn)入流水線到流出流水線的時(shí)間稱為通過(guò)時(shí)間。時(shí)間稱為通過(guò)時(shí)間。排空時(shí)間：排空時(shí)間：最后最后1 1個(gè)任務(wù)從進(jìn)入流水線到流出流水線個(gè)任務(wù)從進(jìn)入流水線到流出流水線的時(shí)間稱為排空時(shí)間。的時(shí)間稱為排空時(shí)間。5.25.2簡(jiǎn)答簡(jiǎn)答5 5標(biāo)量處理機(jī)標(biāo)量處理機(jī)衡量流水線性能的主要指標(biāo)有哪些？衡量流水線性能的主要指標(biāo)有哪些？吞吐率、加速比和效率。吞吐率、加速比和效率。吞吐率是指單位時(shí)間內(nèi)流水線所完成的任務(wù)數(shù)或吞吐率是指單位時(shí)間內(nèi)流水線所完成的

52、任務(wù)數(shù)或輸出結(jié)果的數(shù)量。輸出結(jié)果的數(shù)量。加速比是指流水線的速度與等功能非流水線的速度加速比是指流水線的速度與等功能非流水線的速度之比。之比。效率是指流水線的設(shè)備利用率效率是指流水線的設(shè)備利用率。5.25.2簡(jiǎn)答簡(jiǎn)答5 5標(biāo)量處理機(jī)標(biāo)量處理機(jī)流水線各段執(zhí)行時(shí)間不相等時(shí)，消除瓶頸的方法？流水線各段執(zhí)行時(shí)間不相等時(shí)，消除瓶頸的方法？數(shù)據(jù)相關(guān)有哪幾類？數(shù)據(jù)相關(guān)有哪幾類？l 細(xì)分瓶頸段細(xì)分瓶頸段 l 重復(fù)設(shè)置瓶頸段重復(fù)設(shè)置瓶頸段l 寫后讀寫后讀 l 讀后寫讀后寫l 寫寫寫寫5 5標(biāo)量處理機(jī)標(biāo)量處理機(jī) 在靜態(tài)流水線上計(jì)算在靜態(tài)流水線上計(jì)算 求：吞吐率，加速比，效率。求：吞吐率，加速比，效率。41iiiBA

53、5 5標(biāo)量處理機(jī)標(biāo)量處理機(jī)用教材用教材P283P283圖圖5.325.32所示的所示的TI-ASCTI-ASC計(jì)算機(jī)的多功能靜態(tài)流水線計(jì)算計(jì)算機(jī)的多功能靜態(tài)流水線計(jì)算. .5 5標(biāo)量處理機(jī)標(biāo)量處理機(jī)解：解：(1) (1) 確定適合于流水處理的計(jì)算過(guò)程確定適合于流水處理的計(jì)算過(guò)程(2) (2) 畫時(shí)空?qǐng)D畫時(shí)空?qǐng)D (3) (3) 計(jì)算性能計(jì)算性能 吞吐率吞吐率 TPTP7 7(20(20t t) ) 加速比加速比 S S(34(34t t) )(20(20t t 效率效率 E E5 5標(biāo)量處理機(jī)標(biāo)量處理機(jī)5 5標(biāo)量處理機(jī)標(biāo)量處理機(jī)5 5標(biāo)量處理機(jī)標(biāo)量處理機(jī)5 5標(biāo)量處理機(jī)標(biāo)量處理機(jī) 在用一條在用一

54、條4 4段浮點(diǎn)加法器流水線計(jì)算段浮點(diǎn)加法器流水線計(jì)算8 8個(gè)個(gè)浮點(diǎn)浮點(diǎn)數(shù)的和：浮點(diǎn)浮點(diǎn)數(shù)的和：Z ZA AB BC CD DE EF FG GH H 求：求：吞吐率，加速比，效率。吞吐率，加速比，效率。5 5標(biāo)量處理機(jī)標(biāo)量處理機(jī)5 5標(biāo)量處理機(jī)標(biāo)量處理機(jī)5.55.55 5標(biāo)量處理機(jī)標(biāo)量處理機(jī)5.55.55 5標(biāo)量處理機(jī)標(biāo)量處理機(jī)5.55.55 5標(biāo)量處理機(jī)標(biāo)量處理機(jī)5.55.55 5標(biāo)量處理機(jī)標(biāo)量處理機(jī)5.65.65 5標(biāo)量處理機(jī)標(biāo)量處理機(jī)一個(gè)流水線由四段組成，其中每當(dāng)流經(jīng)第三段時(shí)，一個(gè)流水線由四段組成，其中每當(dāng)流經(jīng)第三段時(shí)，總要在該段循環(huán)一次才能流到第四段。如果每段總要在該段循環(huán)一次才能流到

55、第四段。如果每段經(jīng)過(guò)一次的時(shí)間都是經(jīng)過(guò)一次的時(shí)間都是t t，問(wèn)：，問(wèn)：n當(dāng)在流水線的輸入端每當(dāng)在流水線的輸入端每t t時(shí)間輸入任務(wù)時(shí)，該流水線會(huì)時(shí)間輸入任務(wù)時(shí)，該流水線會(huì)發(fā)生什么情況？發(fā)生什么情況？n此流水線的最大吞吐率為多少？如果每此流水線的最大吞吐率為多少？如果每2 2t t輸入一個(gè)任務(wù)，輸入一個(gè)任務(wù)，連續(xù)處理連續(xù)處理1010個(gè)任務(wù)的實(shí)際吞吐率和效率是多少？個(gè)任務(wù)的實(shí)際吞吐率和效率是多少？當(dāng)每段時(shí)間不變時(shí)，如何提高該流水線的吞吐率？仍連續(xù)當(dāng)每段時(shí)間不變時(shí)，如何提高該流水線的吞吐率？仍連續(xù)處理處理1010個(gè)任務(wù)個(gè)任務(wù) 時(shí)，其吞吐率提高多少？時(shí)，其吞吐率提高多少？題：題：5.65.65 5標(biāo)量

56、處理機(jī)標(biāo)量處理機(jī)解：解：（1）會(huì)發(fā)生流水線阻塞情況。）會(huì)發(fā)生流水線阻塞情況。 5.65.65 5標(biāo)量處理機(jī)標(biāo)量處理機(jī)解：解：5.65.65 5標(biāo)量處理機(jī)標(biāo)量處理機(jī)解：解：StageStageTimeTime12341111122222333334444455555666667777788888999991010101010t 23t21TPmax5.65.65 5標(biāo)量處理機(jī)標(biāo)量處理機(jī)解：解：54.35%925045TPE2310TnTp23TpipelinepipelinetttStageStageTimeTime1234111112222233333444445555566666777778

57、8888999991010101010t 235.65.65 5標(biāo)量處理機(jī)標(biāo)量處理機(jī)解：解：（3 3）重復(fù)設(shè)置部件）重復(fù)設(shè)置部件 1 2 3_1 3_2 4 t t t t t 5.65.65 5標(biāo)量處理機(jī)標(biāo)量處理機(jī)解：解：S St ta ag ge eT Ti im me e1123_13_24111122222333334444455555666667777788888999991010101010t14tt751410TnTPpipelinett231075吞吐率提高倍數(shù)吞吐率提高倍數(shù)5 5標(biāo)量處理機(jī)標(biāo)量處理機(jī)題：題：5 5標(biāo)量處理機(jī)標(biāo)量處理機(jī)解：解：（1 1）順序執(zhí)行方式：）順序執(zhí)行方

58、式：tnttttttTniniiii6)32()(11執(zhí)行分析取指令5 5標(biāo)量處理機(jī)標(biāo)量處理機(jī)解：解：（2 2）僅）僅“取指令取指令”和和“執(zhí)行執(zhí)行”重疊：重疊：tntntT) 15(5) 1(65 5標(biāo)量處理機(jī)標(biāo)量處理機(jī)解：解：（2 2）僅）僅“取指令取指令”和和“執(zhí)行執(zhí)行”重疊：重疊：tntntT)33(3) 1(65 5標(biāo)量處理機(jī)標(biāo)量處理機(jī)題：題：5 5標(biāo)量處理機(jī)標(biāo)量處理機(jī)解：解：段段時(shí)間時(shí)間4 43 32 21 10 1 2 3 4 5 6 7 8 9 100 1 2 3 4 5 6 7 8 9 101111t t任務(wù)輸入周期任務(wù)輸入周期5 5標(biāo)量處理機(jī)標(biāo)量處理機(jī)解：（下面圖片中的所有

59、解：（下面圖片中的所有11均改為均改為7）5 5標(biāo)量處理機(jī)標(biāo)量處理機(jī)題：題：5 5標(biāo)量處理機(jī)標(biāo)量處理機(jī)解：解：5 5標(biāo)量處理機(jī)標(biāo)量處理機(jī)解：解：5 5標(biāo)量處理機(jī)標(biāo)量處理機(jī)解：解：5 5標(biāo)量處理機(jī)標(biāo)量處理機(jī)解：解：5 5標(biāo)量處理機(jī)標(biāo)量處理機(jī)解：解：為了縮短運(yùn)算時(shí)間，首先應(yīng)考慮為了縮短運(yùn)算時(shí)間，首先應(yīng)考慮“最少切換算法最少切換算法”，即先執(zhí)行完所有乘法（任務(wù)編號(hào)即先執(zhí)行完所有乘法（任務(wù)編號(hào)1-61-6）再執(zhí)行加法（）再執(zhí)行加法（任務(wù)編號(hào)任務(wù)編號(hào)7-117-11），其次在加法中采用），其次在加法中采用“最少相關(guān)算法最少相關(guān)算法”（即二叉樹算法）。（即二叉樹算法）。記記c1=A1c1=A1B1B1，c6=A6c6=A6B6B6，下圖，下圖(a)(a)是加法的是加法的計(jì)算順序二叉樹，注意任務(wù)計(jì)算順序二叉樹，