《計算機系統(tǒng)結構》總復習-習題課件

1計算機系統(tǒng)結構總復習《計算機系統(tǒng)結構》總復習-習題2第一章基本概念（P1）本章介紹計算機系統(tǒng)結構的一些基本知識。包括定性知識和定量知識兩大組內(nèi)容。為了便于學習，本章各節(jié)重新編號，與教材編號不同。

定量知識：對計算機性能進行定量評價的幾個重要公式。《計算機系統(tǒng)結構》總復習-習題3本章重點

本章從定性知識和定量知識兩個方面介紹計算機系統(tǒng)結構的基本概念。有關重點如下：(1)Amdahl定律；(2)平均周期數(shù)CPI公式，程序執(zhí)行時間Te公式；(3)每秒百萬指令數(shù)MIPS公式，每秒百萬浮點數(shù)MFLOPS公式?！队嬎銠C系統(tǒng)結構》總復習-習題41.定量知識───3個性能公式1.1

Amdahl定律（加快經(jīng)常性事件原理，P9）其中：Sn──全局加速比；

To──原執(zhí)行時間（old）；Tn──新執(zhí)行時間（new）；Se──被改進部分的局部加速比；

Fe──被改進部分原執(zhí)行時間占原來總時間的百分比?！队嬎銠C系統(tǒng)結構》總復習-習題5Amdahl定律的推導《計算機系統(tǒng)結構》總復習-習題6Amdahl定律的圖形從圖1.2可以看出，增大Se和Fe對Sn都有提升作用；但當Fe固定時，一味增大Se對Sn的作用會越來越不顯著。《計算機系統(tǒng)結構》總復習-習題作1.12假定利用增加向量模塊來提高計算機的運算速度。計算機處理向量的速度比其通常的運算要快20倍，將可用向量處理部分所花費的時間占總時間的百分比稱為可向量化百分比。（1）求出加速比S和向量化百分比之間的關系式作1.13（2）當要得到加速比為2時的可向量化百分比F為多少？作1.14（3）為了獲得在向量模式所得到的最大加速比的一半，可向量化百分比F為多少？7《計算機系統(tǒng)結構》總復習-習題(2)由（1）式有解（1）：由Amdahl定律知(1)8《計算機系統(tǒng)結構》總復習-習題(3)由題意可知9《計算機系統(tǒng)結構》總復習-習題作1.17

假設高速緩存Cache工作速度為主存的5倍，且Cache被訪問命中的概率為90％，則采用Cache后，能使整個存儲系統(tǒng)獲得多高的加速比？解：fe=0.9，re=510《計算機系統(tǒng)結構》總復習-習題1.2CPI與程序執(zhí)行時間Te（P11）CPI是衡量CPU執(zhí)行指令效率的重要指標。讓我們先考慮一個標準測速程序的全部執(zhí)行時間Te和其中所有第i種指令的累計時間Ti，易知11《計算機系統(tǒng)結構》總復習-習題121.3每秒百萬指令數(shù)MIPS與每秒百萬浮點數(shù)MFLOPS（P11）例題：P10，例1.1~例1.5。

P33，題12，題13，題14?！队嬎銠C系統(tǒng)結構》總復習-習題例1.19

用一臺4OMHz處理機執(zhí)行標準測試程序，它含的混合指令數(shù)和相應所需的時鐘周期數(shù)如下：指令類型指令條數(shù)時鐘周期數(shù)整數(shù)運算450001數(shù)據(jù)傳送320002浮點運算

150002控制傳送

80002求有效CPI、MIPS速率和程序的執(zhí)行時間。13《計算機系統(tǒng)結構》總復習-習題解：依題意可知IN=105條，n=414《計算機系統(tǒng)結構》總復習-習題作1.20

某工作站采用時鐘頻率為15MHz、處理速率為10MIPS的處理機來執(zhí)行一個巳知混合程序。假定每次存儲器存取為1周期延遲、試問：

(1)

此計算機的有效CPI是多少?

(2)假定將處理機的時鐘提高到30MHz，但存儲器子系統(tǒng)速率不變。這樣，每次存儲器存取需要兩個時鐘周期。如果30％指令每條只需要一次存儲存取，而另外5％每條需要兩次存儲存取，還假定已知混合程序的指令數(shù)不變，并與原工作站兼容，試求改進后的處理機性能。解

(1)15《計算機系統(tǒng)結構》總復習-習題(2)依題意可知：30%的指令需要一次存儲存取，則這些指令在處理器提高時鐘頻率之后需要增加1個時鐘周期；另外5%的指令需要增加2個時鐘周期。

改進后性能提高情況可用CPU時間之比表示：

16《計算機系統(tǒng)結構》總復習-習題作1.21

假設在一臺40MHz處理機上運行200000條指令的目標代碼，程序主要由四種指令組成。根據(jù)程序跟蹤實驗結果，已知指令混合比和每種指令所需的指令數(shù)如下：指令類型CPI指令混合百分比算術和邏輯運算160%Cache命中的加載/存儲

218%轉移

412%Cache失效時訪問主存810%(1)計算在單處理機上用上述蹤數(shù)據(jù)運行程序的平均CPI(2)根據(jù)(1)所得CPI，計算相應的MIPS速率和程序的執(zhí)行時間17《計算機系統(tǒng)結構》總復習-習題解：依題意可知IN=2×105條，n=4，18《計算機系統(tǒng)結構》總復習-習題19第二章指令系統(tǒng)（P36）本章介紹指令系統(tǒng)設計中2個最基本的內(nèi)容：數(shù)據(jù)表示、操作碼優(yōu)化。本章重點

(1)Huffman編碼方法；(2)等長擴展編碼方法（15/15/15法，8/64/512法）；(3)編碼方法性能指標（平均碼長L，信息冗余量R）?！队嬎銠C系統(tǒng)結構》總復習-習題202.1Huffman壓縮編碼（P91）(1)Huffman壓縮概念（最佳編碼定理）：當用n個長度不等的代碼分別代表n種發(fā)生概率不等的事件時，按照短代碼給高概率事件、把長代碼給低概率事件的原則分配，可使平均碼長達到最低。(2)Huffman編碼方法

這種編碼方法由兩個過程組成。 頻度合并：將全部n個事件（在此即為n條指令）的頻度值排序，選取其中最小的2個頻度合并，然后將剩下的n-1個頻度再次排序，再合并最小的2個頻度，如此重復，直至剩下1個頻度為止。記錄所有的合并關系，形成一棵二叉樹──Huffman樹，所有原始頻度值充當樹葉，而最后剩下的總頻度1為樹根； 碼元分配：從樹根開始，對每個中間結點的左右2個分支邊各賦予一位代碼“0”和“1”（“0”在哪一側不限）。讀出從根結點到任一片樹葉的路徑上依次出現(xiàn)的代碼位就排成了這個事件（即指令）的完整編碼。由于頻度高的事件較晚被合并，它的編碼位數(shù)也就較少，符合Huffman壓縮原則。上面所說的頻度值就是各事件實際出現(xiàn)次數(shù)的百分比，它是理論出現(xiàn)概率的近似值?！队嬎銠C系統(tǒng)結構》總復習-習題21

平均碼長：各事件編碼長度的數(shù)學期望。

信息冗余量：它表明消息編碼中“無用成分”所占的百分比?！队嬎銠C系統(tǒng)結構》總復習-習題222.2擴展編碼方法（等長擴展法，P94-95）用碼長表示：例如4-8-12法。這并不能說明具體編碼方法，例如下面兩種編碼方法都是4-8-12法。用碼點數(shù)表示：例如15/15/15法，8/64/512法15/15/15法，每一種碼長都有4位可編碼位（前頭可以有相同的擴展標識前綴），可產(chǎn)生16個碼點（即編碼組合），但是至多只能使用其中15個來表示事件，留下1個或多個碼點組合作為更長代碼的擴展標識前綴。已經(jīng)用來表示事件的碼點組合不能再作為其它更長代碼的前導部分，否則接收者會混淆。這就是“非前綴原則”。8/64/512法，每一種碼長按4位分段，每一段中至少要留下1位或多位作為擴展標識。各段剩下的可編碼位一起編碼，所產(chǎn)生的碼點用來對應被編碼事件。每一段中的標識位指出后面還有沒有后續(xù)段?！队嬎銠C系統(tǒng)結構》總復習-習題10000001110.090.300.601.000.1510.0610.030.030.040.050.150.300.40

I7I6I5I4I3I2I1例2.1

某指令系統(tǒng)各指令使用頻度如下：I1I2I3I4I5I6I70.40.30.150.050.040.030.031.Huffman編碼23《計算機系統(tǒng)結構》總復習-習題由此可得到哈夫曼編碼如下：

I1:0I2:10I3:110I4:11100I5:11101I6:11110I7:11111

平均碼長L=0.4*1+0.3*2+0.15*3+0.05*5+0.04*5+0.03*5+0.03*5=2.20位

信息冗余量R=(2.20-2.17)/2.20=1.36%

指令長度個數(shù)=424《計算機系統(tǒng)結構》總復習-習題2.擴展哈夫曼編碼I1,I2,I3用兩位:00,01,10I4,I5,I6,I7用四位:1100,1101,1110,1111L=(0.4+0.3+0.15)*2+(0.05+0.04+0.03+0.03)*4=2.30位信息冗余量=(2.30-2.20)/2.30=0.0565=5.65%25《計算機系統(tǒng)結構》總復習-習題411115111110.03I7411105111100.03I6411015111010.04I5411005111000.05I421031100.15I32012100.30I2200100.40I1OP長度lihuffman擴展編碼OP長度li操作碼OP使用哈夫曼編碼

頻度（Pi）

指令操作碼的擴展（等長擴展）平均碼長：2.22.326《計算機系統(tǒng)結構》總復習-習題作2.13采用最優(yōu)Huffman編碼法（信息熵）的操作碼最短平均長度為：

27《計算機系統(tǒng)結構》總復習-習題28《計算機系統(tǒng)結構》總復習-習題例2.2

指令系統(tǒng)共有42種指令，前15種使用頻率平均為0.05，中間13種使用頻率平均為0.015，最后14種使用頻率平均為0.004。如何編碼？0000

：15種111011110000

：：15種11111110111111110000

：：：15種111111111110解：因頻率分布有三種，故碼長可有三種；

因每段指令數(shù)基本相同，故可采用等長擴展(4-8-12位)，保留特征碼的每段指令數(shù)相同(15-15-15)方法。結果如圖所示；

結果：采用15-15-15擴展方法，最后一種編碼用于擴展，每段0000～1110用于編碼，1111用于擴展。29《計算機系統(tǒng)結構》總復習-習題例2.3

某模型機有9條指令，其使用頻率為：ADD（加）30%

SUB（減）24%JOM（按負轉移）6%

STO（存）7%JMP（轉移）7%

SHR（右移）2%CIL（循環(huán)左移）3%

CLA（清加）20%STP（停機）1%

要求有兩種指令字長，都按雙操作數(shù)指令格式編,采用擴展操作碼，并限制只能有兩種操作碼碼長。設該機有若干個通用寄存器，主存為16位寬，按字節(jié)編址，采用整數(shù)邊界存貯，任何指令都在一個主存周期中取得，短指令為寄存器－寄存器型，長指令為寄存器－主存型，主存地址應能變址尋址。30《計算機系統(tǒng)結構》總復習-習題

解：(1)Huffman樹的形式如圖所示。0.010.020.03010.030.06010.060.12010.070.070.14010.260100.300.200.240.44010.561001131《計算機系統(tǒng)結構》總復習-習題由上圖可得到的Huffman編碼為：

ADD(加)30%01SUB(減)24%11CLA(清加)20%10JOM(按負轉移)6%0001STO(存)7%0011JMP(轉移)7%0010CIL(循環(huán)左移)3%00001SHR(右移)2%000001STP(停機)1%000000因此，操作碼的平均碼長為：32《計算機系統(tǒng)結構》總復習-習題(2)采用2-5擴展的操作碼編碼為：

ADD(加)30%00SUB(減)24%01CLA(清加)20%10JOM(按負轉移)6%11000STO(存)7%11001JMP(轉移)7%11010SHR(右移)2%11011CIL(循環(huán)左移)3%11100STP(停機)1%11101因此，操作碼的平均碼長為：33《計算機系統(tǒng)結構》總復習-習題(3)該機允許使用的可編址的通用寄存器個數(shù)為23=8個(4)短指令為寄存器-寄存器型，格式如下：OP(2位)R1(3位)R2(3位)OP(5位)R1(3位)X(2位)相對位移d(6位)(5)訪主存操作數(shù)地址尋址的最大相對位移量為64個字節(jié)(-32~+31個字節(jié))長指令為寄存器-主存型，格式如下：34《計算機系統(tǒng)結構》總復習-習題作2.14一臺模型機共有7條指令，各指令的使用頻度分別是35％、25％、20％、10％、5％、3％、2％，有8個通用數(shù)據(jù)寄存器，2個變址寄存器。(1)要求操作碼的平均長度最短，請設計操作碼的編碼，并計算所設計操作碼的平均長度。(2)設計8位字長的寄存器－寄存器型指令3條，16位字長的寄存器－存儲器型變址尋址方式指令4條，變址范圍不小于正、負127。請設計指令格式，并給出各字段的長度和操作碼的編碼。。

35《計算機系統(tǒng)結構》總復習-習題答:(1)要使得到的操作碼長度最短，應采用Huffman編碼，Huffman樹構造如下36《計算機系統(tǒng)結構》總復習-習題由此可以得到7條指令的編碼分別如下：37這樣，Huffman編碼法得到的操作碼的平均長度為：l=2×(0.35+0.25+0.20)+3×0.10+4×0.05+5×(0.03+0.02)=1.6+0.3+0.2+0.25=2.35指令號 出現(xiàn)的頻率 編碼1 35% 002 25% 013 20% 104 10% 1105 5% 11106 3% 111107 2% 11111《計算機系統(tǒng)結構》總復習-習題38《計算機系統(tǒng)結構》總復習-習題作2.14(改）

一臺模擬機共有7條指令，各指令的使用頻度分別為35%，25%，20%，10%，5%，3%，2%。該模擬機有8位和16位兩種指令長，采用2-4擴展操作碼，8位字長指令為寄存器-寄存器（R-R）二地址類型，16位字長指令為寄存器-存貯器（R-M）二地址變址尋址（-128≤變址范圍≤127）類型。(1)計算操作碼的平均碼長

(2)該機允許使用多少個可編址的通用寄存器，多少個變址寄存器？

設計該機的兩種指令格式，標出各字段位數(shù)并給出操作碼編碼。

39《計算機系統(tǒng)結構》總復習-習題

擴展碼有2種方案（下圖）00 0001 3條 01 2條10 10001100 10011101 4條 1010 5條1110 10111111 1100(3-7型）（2-8型）簡版40《計算機系統(tǒng)結構》總復習-習題2-4擴展碼有2種方案（上圖）前一種方案里短指令占的比例較大，應該選用它。平均碼長/L=(0.35+0.25+0.20)×2+(0.1+0.05+0.03+0.02)×4=2.4

用R代表寄存器編號，A代表變址偏移量。題目未指明R-R型R-M型誰是短碼，所以先列出2種方案：41《計算機系統(tǒng)結構》總復習-習題428位:操作碼2,寄存器（8-2)/2=3（右邊為操作碼4位）16位：操作碼2,寄存器3，變址尋址（-128≤變址范圍≤127）：27=128，

符號1位，共8位，變址器：16-4-3-8=1《計算機系統(tǒng)結構》總復習-習題432.2.2操作數(shù)優(yōu)化───尋址方式比較（P95）指令中操作數(shù)占用的位數(shù)由操作數(shù)的個數(shù)與尋址方式?jīng)Q定。按操作數(shù)的個數(shù)劃分，有零操作數(shù)指令、一操作數(shù)指令、二操作數(shù)指令、三操作數(shù)指令共四種形式。應該按機器用途來選擇（P99，表2.20）?？s短操作數(shù)長度的常用方法是間址和變址（P99頁末）?！队嬎銠C系統(tǒng)結構》總復習-習題作2.15

某處理機的指令字長為16位，有雙地址指令、單地址指令和零地址指令三類，并假設每個地址字段的長度為6位。（1）如果雙地址指令有15條，單地址和零地址指令的條數(shù)基本相同，問單地址指令和零地址指令各有多少條？并且為這三類指令分配操作碼。（2）如果三類指令的比例為1：9：9，問雙地址指令、單地址指令和零地址指令各有多少條？并且為這三類指令分配操作碼。44《計算機系統(tǒng)結構》總復習-習題45《計算機系統(tǒng)結構》總復習-習題解：（1）雙地址指令15條，

地址碼：0000～1110

單地址指令26－1＝63條，地址碼：11110000001111111110零地址指令64條，地址碼：1111111111000000111111111111111146《計算機系統(tǒng)結構》總復習-習題47《計算機系統(tǒng)結構》總復習-習題48第三章存儲系統(tǒng)（P130）長期存在的問題：在合理的總價格限制下，單純性主存設備的速度跟不上CPU的發(fā)展，容量不能滿足軟件尺寸擴大。本章學習兩種提高主存系統(tǒng)性能/價格比的結構化方法：并行存儲器與存儲層次技術。后者為主?！队嬎銠C系統(tǒng)結構》總復習-習題例3.1假設高速緩存Cache工作速度為主存的5倍，且Cache被訪問命中的概率為90％，則采用Cache后，能使整個存儲系統(tǒng)獲得多高的加速比？

解：49《計算機系統(tǒng)結構》總復習-習題例3.2假設高速緩存Cache的訪問周期為50ns，主存的訪問周期為400ns，且Cache被訪問命中的概率為95％，則采用Cache后，能使整個存儲系統(tǒng)等效的訪問周期為多少？獲得多高的加速比？

解：50《計算機系統(tǒng)結構》總復習-習題51第四章輸入輸出系統(tǒng)（P208）

輸入輸出系統(tǒng)是計算機系統(tǒng)中實現(xiàn)各種輸入輸出任務的資源總稱。它包括各種輸入輸出設備、相關的管理軟件等等。由于輸入輸出設備的特殊工作性質(zhì)使其數(shù)據(jù)吞吐率通常遠低于主機，設計輸入輸出系統(tǒng)就是要建立數(shù)據(jù)交換的最佳方案，使雙方都能高效率地工作。本章重點是中斷優(yōu)先級管理、通道流量設計?！队嬎銠C系統(tǒng)結構》總復習-習題524.1基本輸入輸出方式(P212)4.1.1程序控制I/O方式4.1.2中斷I/O方式4.1.3DMA方式4.1.4通道方式4.1.5I/O處理機方式《計算機系統(tǒng)結構》總復習-習題534.2中斷優(yōu)先級管理(P219)中斷是為實時任務優(yōu)先獲得處理機資源而采用的一種調(diào)度技術，當系統(tǒng)中存在多個中斷源時必須根據(jù)實時性強弱設定優(yōu)先順序，這也被稱為中斷的分級。為了兼顧中斷響應的時效與配置的靈活，通常采用兩套機制結合組成中斷優(yōu)先序管理體系。(1)硬件響應優(yōu)先序：未被屏蔽的幾個中斷源同時提出申請時，CPU選擇服務對象的順序。它由硬件電路實現(xiàn)，用戶不能修改。如P226圖4.11所示。(2)軟件服務優(yōu)先序：在各中斷服務程序開頭，用軟件設置自己的中斷屏蔽字（在主程序中也設置）。以此改變實際服務順序(P230)。例如某個硬件響應優(yōu)先級高的中斷源，其中斷服務程序執(zhí)行中屏蔽了自身，而開放了某個硬件響應優(yōu)先級比它低的中斷源，后者就可以在前者剛開放中斷時就打斷它，從而在實際上先得到服務。中斷服務過程示意圖如P231圖4.14所示。由于常規(guī)用戶主程序?qū)μ幚頇C的需求緊迫性最低，所以它的中斷屏蔽字是“全部開放”。(3)實例分析：屏蔽字表、中斷服務過程圖。例4.1（P230倒數(shù)第8行開始）《計算機系統(tǒng)結構》總復習-習題

作業(yè)4.5已知中斷服務請求次序為1-2-3-4，現(xiàn)改為3-2-4-1，（1）設計中斷屏蔽碼

（2）處理機運行主程序時，同時D1和D2 q請求中斷，而在運行中斷源D2時，D3和D4又同時請求，請畫出程序運行過程示意圖

解：(1)中斷屏蔽字表如下圖；(令1對應屏蔽，0對應開放)

54《計算機系統(tǒng)結構》總復習-習題(2)中斷過程示意圖如下圖。55《計算機系統(tǒng)結構》總復習-習題例4.1設中斷級屏蔽位為“0”對應于開放，1對應于屏蔽，各級中斷處理程序的中斷級屏蔽位設置如下：

(1)當中斷響應的優(yōu)先次序為1、2、3、4，其中斷處理次序是什么？

(2)所有的中斷處理各需要3個單位時間，當正在運行用戶程序時，同時出現(xiàn)第2、3級中斷請求，過2個單位時間，又同時出現(xiàn)第1、4級中斷請求，請畫出程序運行過程示意圖。中斷處理程序級別中斷級屏蔽位第1級第2級第3級第4級1級2級3級4級1111100111000110《計算機系統(tǒng)結構》總復習-習題【解答】

(1)當中斷響應的優(yōu)先次序為1、2、3、4，其中斷處理次序是1、3、4、2。

(2)運行過程示意圖如下：用戶程序中斷處理程序中斷請求t41123432《計算機系統(tǒng)結構》總復習-習題584.3通道處理機(P233)(1)定義：

通道處理機（簡稱"通道"）是隸屬于主處理機的輸入輸出專用協(xié)處理機。(2)特點：有一套輸入輸出功能很強的專用指令系統(tǒng)；與主處理機共享主存，存放相應的程序和數(shù)據(jù)；一個通道可以連接多臺外部設備；主處理機可用"啟動I/O"指令來啟動一個通道；當通道訪存與主處理機沖突時，存控部件賦予通道較高的優(yōu)先權；通道程序執(zhí)行完畢自動轉入休眠狀態(tài)，同時向主處理機發(fā)出一個特定的中斷申請，通知該事件。(3)地位：從屬于主處理機。《計算機系統(tǒng)結構》總復習-習題59

字節(jié)多路通道：以字節(jié)為單位交叉為多臺設備傳輸。子通道的概念。

選擇通道：完成一臺設備的全部傳輸再去為另一臺設備服務。

數(shù)組多路通道：以數(shù)組為單位交叉為多臺設備傳輸。(5)通道傳輸過程的時間分配(P241，其中P是設備臺數(shù))：字節(jié)多路通道： ，其中n是單臺設備的數(shù)據(jù)傳輸量；選擇通道：數(shù)組多路通道： ，其中k是塊尺寸， 。(4)分類(P238)：《計算機系統(tǒng)結構》總復習-習題60(6)通道流量分析(P243)：

通道最大能力流量：《計算機系統(tǒng)結構》總復習-習題61

通道實際最大負荷流量：

通道正常工作條件：《計算機系統(tǒng)結構》總復習-習題62實例分析：通道時間關系圖P243例4.1倒數(shù)第2行開始《計算機系統(tǒng)結構》總復習-習題(1)在上表中填出設備相應二次請求傳送字節(jié)的間隔時間。(2)當所有設備同時要傳送數(shù)據(jù)時，求其對通道要求的總流量fbyte設備號123456傳送速率(B/ms)505040252510二次請求的間隔時間(μS)

例4.1某字節(jié)交叉多路通道連接6臺設備，其數(shù)據(jù)傳送速率如下表所示。63《計算機系統(tǒng)結構》總復習-習題(3)讓通道以極限流量fmax.byte=fbyte的工作周期工作，通道的工作周期(即TS+TD的時間間隔)是多少？(4)讓通道中所掛設備速率越高的數(shù)據(jù)傳送請求被響應的優(yōu)先級越高。畫出6臺設備同時發(fā)送請求到下次同時發(fā)送請求期間里，通道響應和處理完各設備請求時刻的示意圖。哪個設備丟失了信息？提出一種不丟失信息的解決辦法。64《計算機系統(tǒng)結構》總復習-習題設備號123456傳送速率(B/ms)505040252510二次請求的間隔時間(μS)

2020

25

40

40

100

解：(1)(2)總容量(3)

傳送周期TS+TD=1ms/200B=5μS1234566號設備丟失了一次數(shù)據(jù)20us65《計算機系統(tǒng)結構》總復習-習題方法1：增加通道的最大流量，保證連接在通道上的所有設備的數(shù)據(jù)傳送請求能夠及時得到通道的響應方法2：動態(tài)改變設備的優(yōu)先級方法3：增加一定數(shù)量的數(shù)據(jù)緩沖器，特別是對優(yōu)先級比較低的設備66《計算機系統(tǒng)結構》總復習-習題例4.2

印字機各占一個子通道，0號打印機、1號打印機和0號光電輸入機合用一個子通道。假定數(shù)據(jù)傳送期內(nèi)高速印字機每隔25us發(fā)一個請求，低速打印機每隔150us發(fā)一個字節(jié)請求，光電輸入機每隔800us發(fā)一個字節(jié)請求，則這5臺設備要求通道的實際流量為多少？字節(jié)多路通道0子通道2子通道1子通道0號高速印字機1號高速印字機0號打印機1號打印機0號光電輸入機67《計算機系統(tǒng)結構》總復習-習題解：5臺設備要求通道的數(shù)據(jù)流量為：可將該通道設計成0.1MB/s，即所設計的工作周期為：這樣各設備的請求就能及時得到響應和處理，不會丟失信息。68《計算機系統(tǒng)結構》總復習-習題0號印字機通道工作周期0us50us100us150us1號印字機0號打印機1號打印機0號光電機

表示設備提出申請的時刻表示通道處理完設備申請的時刻優(yōu)先級次序：0號印字機、1號印字機、0號打印機、1號打印機、0號光電機69《計算機系統(tǒng)結構》總復習-習題例4.3設通道在數(shù)據(jù)傳送期中，選擇設備需4.9μS，傳送一個字節(jié)數(shù)據(jù)需0.lμS。（1）其低速設備每隔250μS發(fā)出一個字節(jié)數(shù)據(jù)傳送請求，問最多可接多少臺這種設備？（2）若有A～E共5種高速設備，要求字節(jié)傳送的間隔時間如下表所示，其時間單位為μS。若一次通信傳送的字節(jié)數(shù)不少于1024個字節(jié)，問哪些設備可掛在此通道上？哪些則不能？設備ABCDE時間間隔(μS)0.130.10.110.20.370《計算機系統(tǒng)結構》總復習-習題其中，n≥1024，應使

select

i≤

max

select由此可得出通道工作周期為：T≈0.1048(us)所以，只有A、C、D、E可掛在此通道上，B則不行。解：(1)低速設備應接字節(jié)多路通道n＝250/5=50臺，所以，n≤50臺，即最多可接50臺這種設備(2)根據(jù)題意，此通道為選擇通道71《計算機系統(tǒng)結構》總復習-習題72本章小結(1)5種I/O方式；(2)中斷優(yōu)先級管理（屏蔽字表、中斷服務過程圖）；(3)3種通道處理機的特點；(4)3種通道最大能力流量；(5)3種通道實際最大負荷流量；(6)通道正常工作條件；(7)通道時間關系圖（字節(jié)多路通道）；習題：P250，題5，題8?！队嬎銠C系統(tǒng)結構》總復習-習題73第五章標量流水線技術(P253)本章學習標量計算機上使用的流水加速技術。主要內(nèi)容有流水技術的分類、流水線性能指標計算、非線性流水線的調(diào)度算法。

標量計算機指只能直接進行標量運算的計算機，與能夠直接進行向量運算的向量計算機相對應。

流水處理方式的特征，是讓多個依次啟動的任務，盡量同時使用系統(tǒng)的不同部件，通過時間重疊來提高處理速率。這種技術理論上不增加成本。

標量計算機上使用的流水加速技術屬于指令級并行技術。每條指令的處理過程，可以劃分為取指、譯碼、取數(shù)、運算、送結果5個子過程，也可以分得更細或更粗一些。劃分的原則是各部分時間長度大致相等、并使用CPU中不同的部件，這樣才有利于多任務重疊處理。《計算機系統(tǒng)結構》總復習-習題745.2流水處理與邏輯相關的概念

CPU中的各個部件按流水處理順序連接起來，就稱為一條流水線。5.2.1流水線工作原理

處理機解釋程序的方式有順序方式、重疊方式、流水方式等。順序方式是解釋完一條指令再開始解釋下一條(P254)；流水方式是把一個重復的過程分解為若干個子過程，每個子過程可以與其它子過程同時進行，以此提高單位時間內(nèi)解釋指令的數(shù)目(P277)；重疊方式是一種簡單的流水方式，它把指令分成2個子過程，每條指令只與下一條指令相重疊(P255)?！队嬎銠C系統(tǒng)結構》總復習-習題75流水線結構圖(P278)流水線工作時空圖(P278—P279)《計算機系統(tǒng)結構》總復習-習題76《計算機系統(tǒng)結構》總復習-習題775.2.2邏輯相關(P263-276)相關的定義：(P263倒數(shù)第4段)一條指令必須等待前一條指令解釋完成才能開始解釋。相關的分類及其對策1.全局性相關/局部性相關(P312、P269/P263、P303)；2.指令相關/數(shù)相關(P264/P263)；3.主存數(shù)相關/寄存器數(shù)相關(P265/P266)；4.數(shù)值相關/變址值相關(P266/P268)?！队嬎銠C系統(tǒng)結構》總復習-習題785.3流水技術的分類(P280)線性/非線性(P280)：部件級/處理機級/處理機間級（宏流水線）(P281)：單功能/多功能(P282)：靜態(tài)/動態(tài)(P283)：標量/向量(P285)：同步/異步(P285)：順序/亂序(P285、P304)：《計算機系統(tǒng)結構》總復習-習題795.4.1吞吐率TP(P285)

吞吐率（TP───ThroughPut）指流水線在單位時間內(nèi)執(zhí)行的任務數(shù)，可以用輸入任務數(shù)或輸出任務數(shù)表示。 ，其中k表示流水線劃分的段數(shù)。當滿足 條件時，有 。5.4線性流水線性能分析(P285)《計算機系統(tǒng)結構》總復習-習題80其中5.4.2加速比(P288)《計算機系統(tǒng)結構》總復習-習題81段效率： ， 各段平均效率：其中表示第i段設備量占整條流水線全部設備量的百分比。當滿足 條件時，有：5.4.3效率（設備利用率，P289）《計算機系統(tǒng)結構》總復習-習題1234

t

t3

t

t例5.1

帶有瓶頸部件的4功能段流水線,△t1=△t2=△t4=△t,△t3=3△t,4個任務、10個任務時TP，E、SP

。（1）分析法:各段時間不等TP=nΣ△ti+(n-1)△tmaxi=1m82《計算機系統(tǒng)結構》總復習-習題STS1S2S3S4t1t2t3t4t5t6t7t8t9t10t12t13t14t151234t11123412341234輸出=Sp=n*Σ△timi=1Σ△ti+(n-1)*△tjmI=14*6△t15△t=2415=1.6E=n個任務實際占用的時-空區(qū)M各段總的時-空區(qū)（2）時空圖法83《計算機系統(tǒng)結構》總復習-習題例5.

2以浮點加法運算為例（四段流水線）各段時間相等，求吞吐率、效率。求Z=A+B+C+D+E+F+G+H，TP、E、Sp(注意有相關)Z=A+B+C+D+E+F+G+H1234567TP=7/15△tE=7*4/(15*4)=7/15＝46%Sp=4*7/15=28/15=1.87解:流水線的效率不高，原因在于存在著數(shù)據(jù)相關,有空閑功能段。時間空間111122223333444455556666777712345678910111213141584《計算機系統(tǒng)結構》總復習-習題例5.3ASC計算機多功能算術運算流水線各段時間相等，6次浮點加、5次定點乘的吞吐率，效率，加速比m=8，n=11分析：T加=6+(6-1)*1=11(△t)T乘=4+(5-1)*1=8(△t)則TP=（6+5）/(11+8)△t=11/19△tE=(6*6+5*4)△t/(19*8△t)=36.8%Sp=(6*6+5*4)△t/19△t=56/19=2.9412345612345612345612345612345867123456123456時間浮加定點乘一二三四五一二三四五一二三四五一二三四五1234567891011121314151617181985《計算機系統(tǒng)結構》總復習-習題作業(yè)5.7p343一條線性流水線有4個功能段組成，每個功能段的延遲時間都相等，都為Δt。開始5個Δt，每間隔一個Δt向流水線輸入一個任務，然后停頓2個Δt，如此重復。求流水線的實際吞吐率、加速比和效率。[解答]流水線的時空圖如下：86《計算機系統(tǒng)結構》總復習-習題我們可以看出，在（11n+1）Δt的時間內(nèi)，可以輸出5n個結果，如果指令的序列足夠長（n→∞），并且指令間不存在相關，那么，吞吐率可以認為滿足：加速比為：從上面的時空圖很容易看出，效率為：87《計算機系統(tǒng)結構》總復習-習題作業(yè)5.8

用一條5個功能段的浮點加法器流水線計算每個功能段的延遲時間均相等，流水線的輸出端和輸入端之間有直接數(shù)據(jù)通路，而且設置有足夠的緩沖寄存器。要求用盡可能短的時間完成計算，畫出流水線時空圖，并計算流水線的實際吞吐率、加速比和效率。[解答]首先需要考慮的是，10個數(shù)的的和最少需要做幾次加法。我們可以發(fā)現(xiàn)，加法的次數(shù)是不能減少的：9次；于是我們要盡可能快的完成任務，就只有考慮如何讓流水線盡可能充滿，這需要消除前后指令之間的相關。由于加法滿足交換率和結合率，我們可以調(diào)整運算次序如以下的指令序列，我們把中間結果寄存器稱為R，源操作數(shù)寄存器稱為A，最后結果寄存器稱為F，并假設源操作數(shù)已經(jīng)在寄存器中，則指令如下：88《計算機系統(tǒng)結構》總復習-習題I1： R1←A1+A2I2： R2←A3+A4I3： R3←A5+A6I4： R4←A7+A8I5： R5←A9+A10I6： R6←R1+R2I7： R7←R3+R4I8： R8←R5+R6I9： F←R7+R8這并不是唯一可能的計算方法。假設功能段的延遲為Δt。時空圖如下，圖中的數(shù)字是指令號。89《計算機系統(tǒng)結構》總復習-習題321

41111222233334444555556666677777888889999921Δt部件m15432R1=A1+A2R2=A3+A4R3=A5+A6R4=A7+A8R5=A9+A10R6=R1+R2R7=R3+R4R8=R5+R6F=R7+R8R1R3R5R6R7R8FR2R490《計算機系統(tǒng)結構》總復習-習題整個計算過程需要21Δt，所以吞吐率為：加速比為：效率為：91《計算機系統(tǒng)結構》總復習-習題

作業(yè)5.9(類似題5.8)一條線性靜態(tài)多功能流水線由6個功能段組成，加法操作使用其中的1、2、3、6功能段，乘法操作使用其中的1、4、5、6功能段，每個功能段的延遲時間均相等。流水線的輸入端與輸出端之間有直接數(shù)據(jù)通路，而且設置有足夠的緩沖寄存器?，F(xiàn)在用這條流水線計算：畫出流水線時空圖，并計算流水線的實際吞吐率、加速比和效率。92《計算機系統(tǒng)結構》總復習-習題解：為了取得較高的速度，我們需要一次將乘法作完，設源操作數(shù)存放在寄存器A、B中，中間結果存放在寄存器R中，最后結果存放在寄存器F中，則執(zhí)行的指令序列如下所示：I1： R1←A1*B1I2： R2←A2*B2I3： R3←A3*B3I4： R4←A4*B4I5： R5←A5*B5I6： R6←A6*