1、第 一 章 1.26 假設(shè)高速緩存Cache工作速度為主存的5倍，且Cache被訪問命中的概率為90，那么，采用Cache后能使整個存儲系統(tǒng)獲得多高的加速比? T0 1解：根據(jù)Amdahl定理有：Sn = = ；結(jié)合題意：Cache工作速度為 Tn （1 Fe）+ Fe / Se主存的5倍，相當于改進存儲器后獲得的加速比為5，即Se=5；Cache被訪問命中的概率為90，相當于訪問存儲器的時間有90化在Cache上，即Fe=0.9。 所以 Sn = 1/（1-0.9）+0.9/5 = 3.571.27 設(shè)計指令存儲器有兩種不同方案：一種是采用價格較貴的高速存儲器芯片，另一種是采用價格便宜的低速

2、存儲器芯片。采用后一方案時，用同樣的經(jīng)費可使存儲器總線帶寬加倍，從而每隔2個時鐘周期可取出2條指令(每條指令為單字長32位)。而采用前一方案時，每一個時鐘周期取出一條單字長指令。由于訪存局部性原理，當取出2個指令字時，通常這2個指令字都要使用，但仍有25的時鐘周期中，取出的2個指令字中僅有1個指令字是有用的。試問采用這兩種實現(xiàn)方案所構(gòu)成的存儲器帶寬是多少？ 解：帶寬是指單位時間內(nèi)處理的二進制位數(shù)，相當于頻率，用f表示。 采用方案A時，存取指令的CPIa = 1時鐘周期/指令字，即：fa = 1/CPIa ×指令字長 = 1×32 = 32位/時鐘周期。采用方案B時，存取指令

3、的CPIb = 0.75×2/2 + 0.25×2/1 = 1.25時鐘周期/指令字，即： fa = 1/CPIa ×指令字長 = 0.8×32 = 25.6位/時鐘周期。1.28 某工作站采用時鐘頻率為15MHz、處理速率為10MIPS的處理機來執(zhí)行一個測試程序。假定每次存儲器存取為1個時鐘周期，試問：(1)此計算機的有效CPI是多少?(2)假定將處理機的時鐘頻率提高到30MHz，但存儲器的工作速率不變，這樣，每次存儲器存取需要2個時鐘周期。如果30指令每條只需要一次存儲器存取操作，另外5指令每條需要二次存儲器存取操作，假定測試程序的指令數(shù)不變，并與原

4、工作站兼容，試求改進后的處理機CPI和MIPS。 解：（1）由MIPS = 時鐘頻率/（CPI×106），則有：CPIA =時鐘頻率/（MIPS×106）= 1.5。 （2）當時鐘頻率為15MHZ時，假設(shè)不進行存儲操作指令的CPI為x，則要進行一次存儲操作指令的CPI為1+ x，要進行二次存儲操作指令的CPI為2+ x，因此有： 1.5 = x×65% + （1+ x）×30% + （2+ x）×5% 解得x = 1.1當時鐘頻率為30MHZ時，不進行存儲操作指令的CPI不變?yōu)?.1，要進行一次存儲操作指令的CPI為2+ x = 3.1，要進行

5、二次存儲操作指令的CPI為4+ x = 5.1，因此平均CPI為： CPIB = 1.1×65% + 3.1×30% + 5.1×5% = 1.9所以 MIPSB = 時鐘頻率/（CPIB×106）=（30×106）/（1.9×106）= 15.8MIPS1.29 某計算機Cache能存放2000條指令。假設(shè)10%的指令承擔了90%時間的指令訪問，而且這10%指令中每條指令的執(zhí)行時間相同。如果要執(zhí)行的某程序共50000條指令，當計算機執(zhí)行該程序時，在Cache中能訪問到的指令的概率是多少？解：由題意可知：45000條指令承擔10%時間

6、的指令訪問，5000條指令承擔90%時間的指令訪問。顯然5000條指令被頻繁使用，設(shè)平均使用次數(shù)為X；另外45000條指令僅使用一次。則有：45000 : 0.1 = 5000X : 0.9 解得 X = 81所以該程序執(zhí)行指令的條數(shù)為Y = 45000 + 5000×81 = 450000假設(shè)頻繁使用的5000條指令均勻分布于程序之中，即每次調(diào)入Cache的2000條指令有200條是頻繁使用的。另假設(shè)每次調(diào)入Cache的2000條指令中的1800條均被使用了一次。所以執(zhí)行該程序時Cache中能訪問到的指令的概率為: （450000 - 50000/2000）÷ 45000

7、0 100%1.30 有一臺計算機，不同類型指令在理想Cache（無訪問失敗）與實際Cache（有訪問失?。﹥煞N情況下的性能如下表。求理想Cache相對于實際Cache的加速比？指令類型 出現(xiàn)頻率 理想CacheCPI 實際CacheCPI運算指令 40% 1 3取數(shù)指令 20% 2 8存數(shù)指令 15% 2 8控制指令 25% 2 4解：理想Cache情況下指令的平均時鐘周期數(shù)CPI為： CPI理想 = =1×40%+2×20%+2×15%+2×25% = 1.6實際Cache情況下指令的平均時鐘周期數(shù)CPI為： CPI實際= =3×40%+8

8、×20%+8×15%+4×25% = 5.0S = 實際CacheCPU執(zhí)行時間/理想CacheCPU執(zhí)行時間=（IC×時鐘周期×CPI實際）/（IC×時鐘周期×CPI理想）= CPI/CPIA = 5.0/1.6 = 3.121.31 假設(shè)在一臺40MHz處理機上運行測試程序共有200000條指令，由4類指令組成。已知指令的CPI和所各占比例如下表。 指令類型 指令比例 CPI算邏運算 60% 1 Cache命中存取 18% 2 控制指令 12% 4 Cache末命中訪主存 10% 8 (1)計算處理機運行該程序的平均CP

9、I。(2)根據(jù)(1)所得CPI，計算相應(yīng)的MIPS速率。解: （1）CPI= =1×60% + 2×18% + 4×12% + 8×10% = 2.2（2）MIPS = 時鐘頻率/（CPI×106）= 40×106/（2.2×106）= 18.191.32 已知4個程序在A、B、C 三臺計算機上的執(zhí)行時間(秒)分別如下表，假設(shè)每個程序都有100×106條指令要執(zhí)行，計算這3臺計算機對每個程序的MIPS速率。根據(jù)這些速率值，你能否得出這3臺計算機相對性能的明確結(jié)論？你能否找到一種將它們排序的方法？試說明理由。 程序

10、計算機A 計算機B 計算機C程序1 1 10 20程序2 1000 100 20程序3 500 1000 50程序4 100 800 100 解：（1）由MIPS的定義有：MIPS = Ic/(Tcpu×106) = 100×106/(Tcpu×106) = 100/Tcpu。根據(jù)上表中列出的Tcpu則可計算出相應(yīng)的MIPS如下表所示。 程序 計算機A 計算機B 計算機C程序1 100 10 5程序2 0.1 1 5程序3 0.2 0.1 2程序4 1 0.125 1（2）由于MIPS與指令值、指令使用的頻率等有關(guān)，在同一臺機器上運行不同的程序，得出不同的速率MI

11、PS，因此不能僅用MIPS來評價計算機性能的優(yōu)劣。而應(yīng)用執(zhí)行程序的算術(shù)平均Tcpu來評價比較好。 TcpuA = （1+1000+500+100）/4 = 400.25 TcpuB = （10+100+1000+800）/4 = 477.5TcpuC = （20+20+50+100）/4 = 47.5所以性能排序為：C > A > B。第 二 章 2.25 浮點數(shù)系統(tǒng)使用的階碼基值re=2，階值位數(shù)q=2，尾數(shù)基值rm=10，尾數(shù)位數(shù)p=1，即按照使用的二進制位數(shù)來說，等價于p=4。計算在非負階、正尾數(shù)、規(guī)格化情況下的最小尾數(shù)值、最大尾數(shù)值、最大階值、可表示的最小值和最大值及可表示

12、數(shù)的個數(shù)。解: 最小尾數(shù)值：rm-1 = 10-1 = 0.1最大尾數(shù)值：1- rm-p =1-10-1 = 0.9最大階值：2q-1=3可表示數(shù)的最小值：1×rm-1 = 10-1 = 0.1可表示數(shù)的最大值：rm2q-1×（1- rm-p）=103（1-10-1）= 900可表示數(shù)的個數(shù)：2q×rmp（rm-1）/rm = 22×101（10-1）/10 = 362.26 一個處理機有I1I10共10條指令，經(jīng)統(tǒng)計，各指令在程序中出現(xiàn)的概率如下：I1：0.25 I2：0.20 I3：0.15 I4：0.10 I5：0.08I6：0.08 I7：0.0

13、5 I8：0.04 I9：0.03 I10：0.02（1）計算這10條指令的操作碼最短平均長度。（2）寫出這10條指令的Huffman編碼，并計算操作碼編碼的平均長度和信息冗余量。（3）采用3/7擴展編碼法和2/8擴展編碼法編寫這10條指令的操作碼。并分別計算編碼的平均長度和信息冗余量。說明哪一種擴展編碼較好的理由。解：（1）操作碼編碼的最短平均長度為：H=-×log2pi H= (0.25log20.250.20log20.200.15log20.150.10log20.100.08log20.080.08log20.080.05log20.050.04log20.040.03lo

14、g20.030.02log20.02) =2.96（位） （2）根據(jù)給出的使用頻度，在構(gòu)造Huffman樹的過程中，有兩個結(jié)點可供合并，因此可生成不同的Huffman樹，其中給出一棵如圖所示，相應(yīng)的Huffman編碼如表所示。1.00 1 0 1 0 1 00.150.080.050.570.320.170.090.040.250.20 I2 I10.10 1 0 1 00.080.430.230.130.05 1 0 I4 1 0 I30.030.02 1 0 I6 1 0 I5 I10 I9 I8 I7IiPiHuffman編碼Li2-5編碼（3/7）Li2-4編碼（2/8）LiI1025

15、002002002I2020102012012I3015010310210004I4010110311000510014I50080110411001510104I60081110411010510114I700501110511011511004I800401111511100510014I900311110511101511104I1000211111511110511114 Huffman編碼的平均長度為：l=×lil = 0.25×20.20×20.15×30.10×30.08×40.08×40.05×50

16、.04×50.03×50.02×5 = 2.99（位） Huffman編碼的信息冗余量為：R = 1-H/l =（12.96/ 2.99）×100% = 1.0%（3）3/7擴展編碼和2/8擴展編碼如表所示。3/7擴展編碼要求短碼碼點數(shù)為3，長碼碼點數(shù)為7。所以短碼長取2位，有碼點22=4個，用一個作擴展標志；長碼長取3位，有碼點23=8個，有一個未被利用，即有一個 余碼點。編碼的平均長度為：l = (0.250.200.15)×2(0.100.080.080.050.040.030.02)×5 = 3.2（位）3/7擴展編碼的信息冗

17、余量為：R = 1H/l =（12.96/ 3.2）×100% = 7.5%2/8擴展編碼要求短碼碼點數(shù)為2，長碼碼點數(shù)為8。所以短碼長取2位，有碼點22=4個，用二個作擴展標志；長碼長取2位，有碼點22×2=8個，碼點全部被利用，即沒有多余碼點。l = (0.250.20)×2(0.150.100.080.080.050.040.030.02)×4 = 3.1（位）2/8擴展編碼的信息冗余量為：R = 1H/l =（12.96/ 3.1）×100% = 4.5% 可見，2/8擴展編碼優(yōu)于3/7擴展編碼。2.27 經(jīng)統(tǒng)計，某種處理機14條指令的

18、使用頻度分別為：0.01，0.15，0.12，0.03,0.02,0.04,0.02,0.04,0.01,0.13,0.15,0.14，0.11,0.03。分別給出它們的定長碼、Huffman編碼、只能有兩種碼長且平均長度盡可能短的擴展編碼，并分別計算三種編碼的平均長度。0.15 0.15 0.14 0.13 0.12 0.11 0.04 0.04 0.03 0.03 0.02 0.02 0.01 0.012.28 用于文字處理的某專用機，每個文字符用4位十進制數(shù)字（09）編碼表示，空格用表示。在對傳送的文字符和空格進行統(tǒng)計后，得出它們的使用頻度如下：0.20 0:0.17 1:0.06 2:

19、0.08 3:0.11 4:0.085: 0.05 6:0.08 7:0.13 8:0.03 9:0.01（1）若對數(shù)字09和空格采用二進制編碼，試設(shè)計編碼平均長度最短的編碼。（2）若傳送106個文字符號，且每個文字符號后均自動跟一個空格，按最短的編碼，共需傳送多少個二進制位？若傳送波特率為9600bPS，共需傳送多少時間？（3）若對數(shù)字09和空格采用4位定長碼編碼，重新計算問題（2）。解：（1）操作碼編碼的平均長度最短為Huffman編碼，生成的Huffman樹，如圖所示，相應(yīng)的Huffman編碼如表所示。l=×li = 3.23（位）。（2）根據(jù)題意，每個字符的二進制碼的平均長度

20、為：3.23×（41）=16.15（位）。若要傳輸106個字符，則要傳輸二進制位數(shù)為：106×16.15 =1.615×107（位）若波特率為56Kb/s，則傳輸時間為：1.615×107/（56×103）=288（s）。1.000.010.040.090.200.400.030.050.110.200.080.060.140.270.600.160.080.130.330.170.08（3）當采用四位定長編碼時，則需要傳輸二進制位數(shù)為：106×4（41）=2×107（位），傳輸時間為：2×107/（56×

21、;103）=357（s）。 1 0 1 0 1 0 1 0 1 0 1 0 3 7 0 5 1 6 4 2IiPiHuffman編碼Li02010200170003701301033011110320080010440080011460080110410060111450051110480031111059001111115 9 82.29 一臺模型機共有7條指令，各指令的使用頻度分別為：35%，25%，20%，10%，5%，3%，2%，有8個通用數(shù)據(jù)寄存器，2個變址寄存器。（1）要求操作碼的平均長度最短，請設(shè)計操作碼的編碼，并計算操作碼編碼的平均長度。（2）設(shè)計8位字長的寄存器寄存器型指令3

22、條，16位字長的寄存器一存儲器型變址尋址方式指令4條，變址范圍不小于正、負127。請設(shè)計指令格式，并給出指令各字段的長度和操作碼的編碼。2.30 一臺模型機共有7條指令，各指令的使用頻度分別為：35%，25%，20%，10%，5%，3%，2%，有8個通用數(shù)據(jù)寄存器，2個變址寄存器。（1）要求操作碼的平均長度最短，請設(shè)計操作碼的編碼，并計算操作碼編碼的平均長度。（2）設(shè)計8位字長的寄存器寄存器型指令3條，16位字長的寄存器一存儲器型變址尋址方式指令4條，變址范圍不小于正、負127。請設(shè)計指令格式，并給出指令各字段的長度和操作碼的編碼。1.000.020.050.100.200.400.030.0

23、50.100.200.250.600.35解：（1）操作碼編碼的平均長度最短為Huffman編碼，生成的Huffman樹如圖所示，相應(yīng)的Huffman編碼如表所示。l=×li = 2.35（位）IiPiHuffman編碼Li2-4編碼（3/4）LiI1035002002I2025012012I3020102102I4010110311004I50051110411014I600311110511104I700211111511114（2）由于通用寄存器有8個，則指令中通用寄存器字段應(yīng)為3位；操作碼字段2位可有4個碼點，用三個碼點表示三條指令，另一個碼點則作為擴展標志。所以3條8位長的

24、寄存器寄存器型指令格式如下：操作碼（2位）寄存器1（3位）寄存器2（3位）由于變址寄存器有2個，則指令中變址寄存器字段應(yīng)為1位；變址范圍-127+127，則指令中相對位移字段應(yīng)為8位；操作碼字段前2位可有4個碼點，用三個碼點表示三條指令，另一個碼點則作為擴展標志。擴展2位正好可表示四條指令，操作碼字段則為4位。所以4條16位長的寄存器存儲器型指令格式如下：操作碼（4位）寄存器（3位）變址寄存器（1位）相對位移（8位）特別地，當采用3/4擴展編碼時，使用頻度高的用短碼表示，使用頻度低的用長碼表示，其相應(yīng)的編碼如表所示。2.31 某處理機的指令字長為16位，有二地址指令、一地址指令和零地址指令3類

25、，每個地址字段的長度均為6位。（1）如果二地址指令有15條，一地址指令和零地址指令的條數(shù)基本相等。問一地址指令和零地址指令各有多少條？并為這3類指令分配操作碼。（2）如果指令系統(tǒng)要求這3類指令條數(shù)的比例大致為1：9：9，問這3類指令各有多少條？并為這3類指令分配操作碼。解：（1）操作碼字段取4位可有24=16個碼點，用15個碼點（00001110）表示15條二地址指令，另一個碼點（1111）則作為擴展標志。所以15條二地址指令格式如下：操作碼（4位）地址碼1（6位）地址碼2（6位）由于要求一地址指令和零地址指令的條數(shù)基本相等。所以地址碼1字段6位擴展有26=64個碼點，用63個碼點（11110

26、000001111111110）表示63條一地址指令，另一個碼點（1111111111）則作為擴展標志。而用地址碼2字段6位擴展有26=64個碼點，64個碼點都用來表示零地址指令，共有64條。（2）在一中指令條數(shù)的比例大約1：4.2：4.2，因此若使一地址指令和零地址指令加大一倍，則三類指令條數(shù)的比例大約1：9：9。操作碼字段取4位時的16個碼點，用14個碼點（00001101）表示14條二地址指令，另二個碼點（1110與1111）則作為擴展標志。擴展標志（1110）擴展地址碼1字段6位的64個碼點（11100000001110111111）全部用來表示一地址指令，有64條。擴展標志（1111

27、）擴展地址碼1字段6位的64個碼點，用62個碼點（11110000001111111101）表示62條一地址指令，另二個碼點（1111111110與1111111111）則作為擴展標志。這樣一地址指令，共有126條。擴展標志（1111111110與1111111111）擴展地址碼2字段6位，各有64個碼點全部用來表示零地址指令，則有128條零地址指令。2.32 某模型機9條指令使用頻度為：ADD（加） 30% SUB（減） 24% JOM（按負轉(zhuǎn)移）6% STO（存） 7%JMP（轉(zhuǎn)移）7% SHR（右移）2% CIL（循環(huán)左移）3% CLA（清除）20% STP（停機）1%要求有兩種指令字長

28、，都按雙操作數(shù)指令格式編排，采用擴展操作碼，并限制只能有兩種操作碼碼長。設(shè)該機有若干通用寄存器，主存為16位寬，按字節(jié)編址，采用按整數(shù)邊界存儲，任何指令都在一個主存周期中取得，短指令為寄存器-寄存器型，長指令為寄存器-主存型，主存地址應(yīng)能變址尋址。（1）僅根據(jù)使用頻度，不考慮其它要求，設(shè)計出全Huffman操作碼，計算其平均碼長；（2）考慮題目全部要求，設(shè)計優(yōu)化實用的操作碼形式，并計算其操作碼的平均碼長；（3）該機允許使用多少可編址的通用寄存器？（4）畫出該機兩種指令字格式，標出各字段之位數(shù)；（5）指出訪存操作數(shù)地址尋址的最大相對位移量為多少個字節(jié)？解：（1）根據(jù)給出的使用頻度，在構(gòu)造Huff

29、man樹的過程中，有兩個結(jié)點可供合并，因此可生成不同的Huffman樹，其中給出一棵如圖所示，相應(yīng)的Huffman編碼如表所示。 Huffman編碼的平均長度為：l=×lil=0.3×20.24×20.2×20.07×40.07×40.06×40.03×50.02×60.01×6=2.61（位）0.560.010.030.060.120.260.020.030.060.070.141.000.200.070.440.240.30 ADD CLA SUB J0M JMP STO CIL 指令I(lǐng)iP

30、iHuffman編碼Li2-5編碼（3/6）LiADDI1030012002SUBI2024112012CLAI3020102102STOI400700114110015JMPI500700104110105JOMI600600014110115CILI7003000015111005SHRI80020000016111015STPI90010000006111105 STP SHR （2）任何指令都在一個主存周期中取得，那么短指令字長為8位，長指令字長為16位。又指令都是二地址指令，所以短指令寄存器-寄存器型的格式為：操作碼（2位）寄存器1（3位）寄存器2（3位）長指令為寄存器-主存型的格式

31、為：操作碼（5位）寄存器（3位）變址寄存器（3位）相對位移（5位）由題意可知：指令操作碼采用擴展編碼，且只能有兩種碼長。從指令使用頻度來看，ADD、SUB和CLA三條指令的使用頻度與其它指令的使用頻度相差較大，所以用兩位操作碼的三個碼點來表示三條指令，一個碼點作為擴展碼點，且擴展三位來表示六條指令，即采用2-4擴展編碼構(gòu)成3/6編碼，2-4擴展編碼如表所示。 2-4擴展編碼（3/6）的平均長度為：l=×li=2.78（3）（4）由短指令寄存器-寄存器型的格式可知，寄存器號字段長度為3位，寄存器個數(shù)為8個。則各字段長度如圖格式所標識。而對于長指令寄存器-主存型，一般變址寄存器是某通用寄

32、存器，則變址寄存器號的字段長度為3位，則各字段長度如圖格式所標識。（5）由于相對位移字段長度為5位，因此訪存地址尋址的最大相對位移量為25=32字節(jié)。第 三 章 習(xí) 題3.8 在一臺單流水線多操作部件的處理機上執(zhí)行下面的程序，每條指令的取指令、指令譯碼需要一個時鐘周期，MOVE、ADD和MUL操作分別需要2個、3個和4個時鐘周期，每個操作都在第一個時鐘周期從通用寄存器中讀操作數(shù)，在最后一個時鐘周期把運算結(jié)果寫到通用寄存器中。k： MOVE R1，R0 ；R1 (R0)k+1： MUL R0，R2，R1 ；R0 (R2)×(R1)k+2： ADD R0，R2，R3 ；R0 (R2)+(

33、R3)(1)就程序本身而言，可能有哪幾種數(shù)據(jù)相關(guān)?(2)在程序?qū)嶋H執(zhí)行過程中，哪幾種數(shù)據(jù)相關(guān)會引起流水線停頓?(3)畫出指令執(zhí)行過程的流水線時空圖，并計算完成這3條指令共需要多少個時鐘周期？解：（1）就程序本身而言，可能有三種數(shù)據(jù)相關(guān)。若3條指令順序流動，則k指令對R1寄存器的寫與k+1指令對R1寄存器的讀形成的“先寫后讀”相關(guān)。若3條指令異步流動，則k指令對R0寄存器的讀與k+1指令對R0寄存器的寫形成的“先讀后寫”相關(guān)，k+2指令對R0寄存器的寫與k+1指令對R0寄存器的寫形成的“寫寫”相關(guān)。（2）在程序?qū)嶋H執(zhí)行過程中，二種數(shù)據(jù)相關(guān)會引起流水線停頓。一是“先寫后讀”相關(guān)，k指令對R1的寫在

34、程序執(zhí)行開始后的第四個時鐘；k+1指令對R1的讀對指令本身是第三個時鐘，但k+1指令比k指令晚一個時鐘進入流水線，則在程序執(zhí)行開始后的第四個時鐘要讀R1。不能在同一時鐘周期內(nèi)讀寫同一寄存器，因此k+1指令應(yīng)推遲一個時鐘進入流水線，產(chǎn)生了流水線停頓。二是“寫寫”相關(guān)，k+1指令對R0的寫對指令本身是第六個時鐘，而要求該指令進入流水線應(yīng)在程序執(zhí)行開始后的第三個時鐘，所以對R0的寫是在程序執(zhí)行開始后的第八個時鐘。k+2指令對R0的寫對指令本身是第五個時鐘，而k+2指令比k+1指令晚一個時鐘進入流水線，則在程序執(zhí)行開始后的第四個時鐘，所以對R0的寫是在程序執(zhí)行開始后的第八個時鐘。不能在同一時鐘周期內(nèi)寫

35、寫同一寄存器，因此k+2指令應(yīng)推遲一個時鐘進入流水線，產(chǎn)生了流水線停頓。另外，可分析“先讀后寫”相關(guān)不會產(chǎn)生流水線的停頓。 （3）由題意可認位該指令流水線由六個功能段取指、譯碼、取數(shù)、運一、運二和存數(shù)等組成，則程序指令執(zhí)行過程的流水線時空圖如下圖所示。若3條指令順序流動，共需要9個時鐘周期。 空間存數(shù) K存數(shù) K+1存數(shù) K+2存數(shù) 運二 K+1運二 運一 K+1運一 K+2運一 取數(shù) K取數(shù) K+1取數(shù) K+2取數(shù) 譯碼 K譯碼 K+1譯碼 K+2譯碼 取指 K取指 K+1取指 K+2取指 時間 0 1 2 3 4 5 6 7 8 93.9 某流水線由4個功能部件組成，每個功能部件的執(zhí)行時間

36、都為t。當輸入10個數(shù)據(jù)后，停頓5t，又輸入10個數(shù)據(jù)，如此重復(fù)。計算流水線的實際吞吐率、加速比和效率，并畫出時空圖。解：該題中的流水線的任務(wù)是非連續(xù)流入的，因此不能直接應(yīng)用公式直接計算，要利用時空圖。題意的流水線時空圖如下圖所示。 空間 S4 1 2 3 4 5 6 7 8 9 10 1 2 S3 1 2 3 4 5 6 7 8 9 10 1 2 S2 1 2 3 4 5 6 7 8 9 10 1 2 S1 1 2 3 4 5 6 7 8 9 10 1 2 時間 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 TP = 10/15t = 0.67

37、/t S = T0/TK = 10×4t/15t = 2.67 E = 4×10t/4×15t = 0.673.11 有一個四段指令流水線為取指（IF）、譯碼（ID）、執(zhí)行（EX）、寫回（WB），分支指令在第二個時鐘周期未決定是不是條件失敗分支，在第三個時鐘周期未決定是不是成功分支，還假定第一個時鐘周期的操作和條件分支無關(guān)，并略去其它流水線停頓。要求： （1）分別畫出無條件分支、發(fā)生的條件分支、不發(fā)生的條件分支時指令執(zhí)行的時空圖。 （2）假設(shè)條件分支指令占所有指令的20%，且其中60%指令可能執(zhí)行，無條件分支占5%，問實際的流水線加速比是多少。解：（1）根據(jù)題意，

38、分支指令采用的是流水線停頓的方法來處理。而判斷條件分支指令讓流水線停頓，應(yīng)在取指功能段后設(shè)計一個“指令分析器”來判斷流水線是否停頓。顯然，無條件分支指令與條件成功（發(fā)生條件）分支是一樣的，需要在第三個時鐘周期未決定下一條指令的地址，因此流水線要停頓二個時鐘周期。對于條件失?。l件不成功）分支，需要在第二個時鐘周期未決定下一條指令的地址，因此流水線要停頓一個時鐘周期。 （2）串行執(zhí)行N條指令的時間為：T1=N·k·t， 流水線方式執(zhí)行N條指令的時間為：Tn=（k-1）t+（N+N·5%·2+N·20%·60%·1.5）t Sn

39、=T1/Tn=k/1.283.13 用一條5個功能段的浮點加法器流水線計算F=，每個功能段的延遲時間，每個功能段的延遲時間均相等，流水線的輸出端與輸入端之間有直接數(shù)據(jù)通路，而且設(shè)置有足夠的緩沖寄存器。要求用盡可能短的時間完成計算，畫出流水線時空圖，計算流水線的實際吞吐率、加速比和效率。 解：為使計算過程充分利用流水線的性能，避免“先寫后讀”相關(guān)，需要將計算的算法改為： （A1 + A2）+（A3 + A4）+（A9 + A10）+（A5 + A6）+（A7 + A9）且按括號的優(yōu)先次序計算九次加法，相應(yīng)的流水線時空圖如下圖所示。 空間 S5 1 2 3 4 5 6 7 8 9 S4 1 2 3

40、 4 5 6 7 8 9 S3 1 2 3 4 5 6 7 8 9 S2 1 2 3 4 5 6 7 8 9 S1 1 2 3 4 5 6 7 8 9 時間 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 TP = 9/21t = 0.429/t S = T0/TK = 9×5t/21t = 2.143 E = 5×9t/5×21t = 0.4293.15 有一條3個功能段的流水線如下圖所示，每個功能段的延遲時間均為t，但是，功能段S2的輸出要返回到它自己的輸入端循環(huán)執(zhí)行一次。S2S3S1 輸入 輸出

41、 t t t（1）如果每隔一個t向流水線連續(xù)輸入任務(wù)，這條流水線會發(fā)生什么問題？（2）求這條流水線能夠正常工作的實際吞吐率、加速比和效率。 （3）可用什么辦法來提高流水線的吞吐率，畫出改進后的流水線結(jié)構(gòu)。解：（1）每個任務(wù)在段S2要反饋循環(huán)一次，執(zhí)行時間為2t，其它各段的執(zhí)行時間為t，因此應(yīng)按瓶頸段的執(zhí)行時間2t流入任務(wù)，才不會發(fā)生沖突現(xiàn)象，否則會發(fā)生流水線的阻塞。 （2）若連續(xù)輸入n個任務(wù)，則流水線的實際吞吐率、加速比和效率分別為： TP = n/（4t +2（n1）t）= n/2（n + 1）t S = 4nt/（4t +2（n1）t）= 2n/（n + 1） E = 4nt/3（4t +

42、2（n1）t）= 2n/3（n + 1）（3）為提高流水線的吞吐率，可重復(fù)設(shè)置段S2，并使兩個段S2串連在一起，從而消除瓶頸段S2，而且各段執(zhí)行時間相等為t，流水線的段數(shù)為4。流水線的結(jié)構(gòu)如下圖所示。S3S2S2S1 輸入 輸出 t t t t3.16 在一個5段的流水線處理機上需經(jīng)9t才能完成一個任務(wù)，其預(yù)約表為： 時間 1 2 3 4 5 6 7 8 9流水段S1 × ×S2 × × ×S3 ×S4 × ×S5 × ×延遲D2 × （1）寫出流水線的初始沖突向量。（2）畫出流水線任務(wù)調(diào)度的狀態(tài)有向圖。（3）求出流水線的最優(yōu)調(diào)度策略及最小平均延遲時間和流水線的最大吞吐率。（4）按最優(yōu)調(diào)度策略連續(xù)輸入8個任務(wù)時，流水線的實際吞吐率是多少? 解：（1）根據(jù)初始沖突向量的構(gòu)成方法，對預(yù)約表各行中打“×”的拍數(shù)求出差值，除去重復(fù)的后匯集在一起，即得到延遲禁止表為F =1，5，6，8。由F可得到初始沖突向量為： C =（10110001） （2）根據(jù)后繼沖突向量的遞推規(guī)則Cj = SHR（k）（Ci）C0則可得出所有的后繼狀態(tài)，具體有：