江西師大體系結(jié)構(gòu)劉老師上練習(xí)題參考解答

1、第 一 章 1.44 某工作站采用時鐘頻率為15MHz、處理速率為10MIPS的處理機來執(zhí)行一個測試程序。假定每次存儲器存取為1個時鐘周期，試問：(1)此計算機的有效CPI是多少?(2)假定將處理機的時鐘頻率提高到30MHz，但存儲器的工作速率不變，這樣，每次存儲器存取需要2個時鐘周期。如果30指令每條只需要一次存儲器存取操作，另外5指令每條需要二次存儲器存取操作，假定測試程序的指令數(shù)不變，并與原工作站兼容，試求改進后的處理機的CPI。解：（1）由MIPS = 時鐘頻率/（CPI×106），則有：CPIA =時鐘頻率/（MIPS×106）= 1.5。 （2）當(dāng)時鐘頻率為15

2、MHZ時，假設(shè)不進行存儲操作指令的CPI為x，則要進行一次存儲操作指令的CPI為1+ x，要進行二次存儲操作指令的CPI為2+ x，因此有： 1.5 = x×65% + （1+ x）×30% + （2+ x）×5% 解得x = 1.1當(dāng)時鐘頻率為30MHZ時，不進行存儲操作指令的CPI不變?yōu)?.1，要進行一次存儲操作指令的CPI為2+ x = 3.1，要進行二次存儲操作指令的CPI為4+ x = 5.1，因此平均CPI為： CPIB = 1.1×65% + 3.1×30% + 5.1×5% = 1.9所以 MIPSB = 時鐘頻率/（

3、CPIB×106）=（30×106）/（1.9×106）= 15.81.45 用一臺80MHz處理機執(zhí)行標(biāo)準(zhǔn)測試程序，它包含的指令數(shù)和相應(yīng)的平均時鐘周期數(shù)如表1-10所示，求該處理機的有效CPI、MIPS和程序執(zhí)行時間。表1-10 題1.46的指令數(shù)和相應(yīng)的平均周期數(shù)指令類型指令數(shù)平均周期數(shù)整數(shù)運算460001數(shù)據(jù)傳輸360002浮點運算140002控制指令90002解：該處理機指令的平均時鐘周期數(shù)CPI為： CPI = =46/105×1+36/105×2+14/105×2+9/105×2 = 1.6 所以 MIPS =

4、時鐘頻率/（CPIB×106）=（80×106）/（1.6×106）= 50 TCPU = IC/( MIPS×106) = 105000/(50×106) = 0.21(ms)1.46 某計算機Cache能存放2000條指令。假設(shè)10%的指令承擔(dān)了90%時間的指令訪問，而且這10%指令中每條指令的執(zhí)行時間相同。如果要執(zhí)行的某程序共50000條指令，當(dāng)計算機執(zhí)行該程序時，在Cache中能訪問到的指令的概率是多少？解：由題意可知：45000條指令承擔(dān)10%時間的指令訪問，5000條指令承擔(dān)90%時間的指令訪問。顯然5000條指令被頻繁使用，設(shè)平均

5、使用次數(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）/450000 100%1.49 有一臺計算機，不同類型指令在理想Cache（無訪問失?。┡c實際Cache（有訪問

6、失?。﹥煞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×20%+8×15%+4×25% = 5.0S = 實際CacheCPU

7、執(zhí)行時間/理想CacheCPU執(zhí)行時間=（IC×時鐘周期×CPI實際）/（IC×時鐘周期×CPI理想）= CPI/CPIA = 5.0/1.6 = 3.12第 二 章 2.13 在一臺單流水線多操作部件的處理機上執(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： AD

8、D R0，R2，R3 ；R0 (R2)+(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)會引起流水線停頓

9、。一是“先寫后讀”相關(guān)，k指令對R1的寫在程序執(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í)行

10、開始后的第八個時鐘。不能在同一時鐘周期內(nèi)寫寫同一寄存器，因此k+2指令應(yīng)推遲一個時鐘進入流水線，產(chǎn)生了流水線停頓。另外，可分析“先讀后寫”相關(guān)不會產(chǎn)生流水線的停頓。 （3）由題意可認(rèn)位該指令流水線由六個功能段取指、譯碼、取數(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 92.23 有一條

11、5個功能段的線性動態(tài)多功能流水線如圖所示，其中1235功能段組成加法流水線，145功能段組成乘法流水線，設(shè)每個功能段的延遲時間均相等為t。用這條流水線計算F=，畫出流水線時空圖，并計算流水線的實際吞吐率、加速比和效率。S1S2S3S5S4XYZ解：由于該流水線為動態(tài)雙功能流水線，計算要求先加后乘，因此應(yīng)先設(shè)置加法功能，連續(xù)計算出（a1+b1）、（a2+b2）、（a3+b3）、（a4+b4）四個加法后；再設(shè)置乘法功能，而且按(a1+b1)×(a2+b2)×(a3+b3)×(a4+b4)順序做3個乘法。因此可畫出該流水線的時空圖如圖所示，圖中A=a1+b1，B=a2+

12、b2，C=a3+b3，D=a4+b4?？臻gS5S4S3S2S11234三一二一二一二1234ABCDA·B C·D(A·B)×(C·D) t7t13a1b1a2b2a3b3a4b4ABCDA·BC·D時間12341234三三由時空圖可以看出，在總共12個t的時間內(nèi)輸出7個結(jié)果，所以有：TP = n/Tn = 7/12t而當(dāng)用串行方法完成操作時，需要四次加法和三次乘法，完成一次加法需要4t，完成一次乘法需要3t，完成該運算總共需要時間為：T0 = 4×4t+3×3t = 25t所以 S = T0/Tn =

13、2.08E = 有效時空區(qū)面積/全部時空區(qū)面積 = (4×4t+3×3t)/(5×12t) = 0.422.24 有一條3個功能段的流水線如下圖所示，每個功能段的延遲時間均為t，但是，功能段S2的輸出要返回到它自己的輸入端循環(huán)執(zhí)行一次。S1S2S3 輸入 輸出 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í)行時間

14、2t流入任務(wù)，才不會發(fā)生沖突現(xiàn)象，否則會發(fā)生流水線的阻塞。 （2）若連續(xù)輸入n個任務(wù)，則流水線的實際吞吐率、加速比和效率分別為： TP = n/（4t +2（n1）t）= n/2（n + 1）t 1/2tS = 4nt/（4t +2（n1）t）= 2n/（n + 1）2 E = 4nt/3（4t +2（n1）t）= 2n/3（n + 1）2/3（3）為提高流水線的吞吐率，可重復(fù)設(shè)置段S2，并使兩個段S2串連在一起，從而消除瓶頸段S2，而且各段執(zhí)行時間相等為t，流水線的段數(shù)為4。流水線的結(jié)構(gòu)如下圖所示。S3S2S2S1 輸入 輸出 t t t t2.25 在一個5段的流水線處理機上需經(jīng)9t才能完

15、成一個任務(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

16、，5，6，8。由F可得到初始沖突向量為： C =（10110001） （2）根據(jù)后繼沖突向量的遞推規(guī)則Cj = SHR（k）（Ci）C0則可得出所有的后繼狀態(tài)，具體有：10110001 C0C0四個后繼狀態(tài)：C1 =SHR（2）（C0）C0 = 10111101 7 C2 =SHR（3）（C0）C0 = 10110111 C3 =SHR（4）（C0）C0 = 10111011 3 2C4 =SHR（7）（C0）C0 = 10110001=C0 7 4 710111101 C110110111 C2C1二個后繼狀態(tài)：C5 =SHR（2）（C1）C0 = 10111111 C6 =SHR（7）（C

17、1）C0 = 10110001=C0 7C2二個后繼狀態(tài)：C7 =SHR（4）（C2）C0 = 10111011=C3 3 4 7 210111011 C310111111 C5C8 =SHR（7）（C2）C0 = 10110001=C0C3二個后繼狀態(tài)：C9 =SHR（3）（C3）C0 = 10110111=C2C10=SHR（7）（C3）C0 = 10110001=C0C5一個后繼狀態(tài)：C11=SHR（7）（C5）C0 = 10110001=C0 由后繼狀態(tài)和引起狀態(tài)轉(zhuǎn)移的時間間隔可得到狀態(tài)有向圖如上圖所示。 （3）由狀態(tài)轉(zhuǎn)移有向圖可得到無沖突的任務(wù)調(diào)度策略及其平均延遲時間，如下表所示。調(diào)

18、度策略 平均延遲時間 特別地，從C0出發(fā)的3，（4，3）也是一個（2，2，7） （2+2+7）t/3 = 3.67t 任務(wù)調(diào)度策略，除第一條有向弧外，第二、三條 （2，7） （2+7）t/2 = 4.5t 有向組成一個環(huán)路，該調(diào)度策略為（4，3）。從表 （3，4，7） （3+4+7）t/3 = 4.67t 中可以得到平均延遲時間最小的調(diào)度策略為（4， （3，7） （3+7）t/2 = 5t 3），該調(diào)度策略則為最優(yōu)調(diào)度策略，相應(yīng)的最小（4，3，7） （4+3+7）t/3 = 4.67t 平均延遲時間為3.5t，所以流水線的最大吞吐（4，7） （4+7）t/2 = 5.5t 率為：（7） 7t

19、TPmax = 1/（3.5t）= 0.286/t3，（4，3） （4+3）t/2 = 3.5t （4）按最優(yōu)調(diào)度策略3，（4，3）連續(xù)輸入8個任務(wù)時，流水線的實際吞吐率為： TP = 8/（3 + 4 + 3 + 4 + 3 + 4 + 3 + 9）t = 0.24/t第 三 章3.26 設(shè)16個處理器編號分別為0，1，15，要用單級互連網(wǎng)絡(luò)，當(dāng)互連函數(shù)分別為：（1）Cube3（Cube1） （5）Butterfly（Butterfly） （8） （9） （13）時，第13號處理器分別與哪一個處理器相連?解：（1）因為Cube3（Cube1(X3X2X1X0)）= Cube3(X3X2X1X

20、0)= X3X2X1X0所以13 Cube3（Cube1(1101)）= 0100 4 （5）因為Butterfly（Butterfly(X3X2X1X0)）=Butterfly（X0X2X1X3）=X3X2X1X0所以13 Butterfly（Butterfly (1101)）= 1101 13 （8）因為(X3X2X1X0)= X0X3X2X1 所以13 (1101)= 1110 14 （9）因為(X3X2X1X0)= X3X2X0X1 所以13 (1101)= 1110 14 （13）因為(X3X2X1X0)= X1X2X3X0 所以13 (1101)= 0111 73.30 在有16個

21、處理器的均勻洗牌網(wǎng)絡(luò)中，若要使第0號處理器與第15號處理器相連，需要經(jīng)過多少次均勻洗牌和交換置換。解：0（0000B）號處理器與15（1111B）號處理器相連要對四位取反。交換置換一次只能對一位取反，所以要四次交換置換。交換置換每次取反只對最低位，要有三次移位，所以要四次均勻洗牌置換。即變換為0000(E) 0001() 0010(E) 0011() 0110(E) 0111()1110(E) 1111。3.34 在編號分別為0，1，2，9的16個處理器之間，要求按下列配對通信：(B、1)，(8、2)，(7、D)，(6、C)，(E、4)，(A、0)，(9、3)，(5、F)。試選擇所用互連網(wǎng)絡(luò)類

22、型、控制方式，并畫出該互連網(wǎng)絡(luò)的拓撲結(jié)構(gòu)和各級的交換開關(guān)狀態(tài)圖。解：16個處理機通過N = 16的互連網(wǎng)絡(luò)互聯(lián)，通信配對連接的二進制編號為：(0、A)：0000-1010 (8、2)：1000-0010(1、B)：0001-1011 (9、3)：1001-0011(2、8)：0010-1000 (A、0)：1010-0000(3、9)：0011-1001 (B、1)：1011-0001(4、E)：0100-1110 (C、6)：1100-0110(5、F)：0101-1111 (D、7)：1101-0111(6、C)：0110-1100 (E、4)：1110-0100(7、D)：0111-11

23、01 (F、5)：1111-0101顯然要求互連網(wǎng)絡(luò)實現(xiàn)的互聯(lián)函數(shù)為f（X3X2X1X0）= X3X2X1X0，為多重方體置換。N = 16的STARAN網(wǎng)絡(luò)在級控方式下實現(xiàn)的是方體置換，且當(dāng)級控信號為F = f3f2f1f0 = 1010時，實現(xiàn)的互聯(lián)函數(shù)是Cube3（Cube1（X3X2X1X0）= X3X2X1X0。所以采用N = 16的STARAN網(wǎng)絡(luò)在級控方式且級控信號F = 1010時，可實現(xiàn)要求配對通信。0123456789ABCDEF0123456789ABCDEF3.41 寫出N=8的蝶式置換的互連函數(shù)，如采用Omega網(wǎng)絡(luò)，則需幾次通過才能完成此變換？畫出Omega網(wǎng)絡(luò)實現(xiàn)

24、此變換的控制狀態(tài)圖。 解：（1）N=8的蝶式置換的互連函數(shù)為：（X2X1X0）= X0X1X2（2）根據(jù)Omega網(wǎng)絡(luò)采用單元控制終端標(biāo)記法尋徑方法，蝶式交換的連接關(guān)系及用N=8的Omega網(wǎng)絡(luò)實現(xiàn)該連接的開關(guān)要求如下表所示。 S D d2 d1 d0 K2級開關(guān) K1級開關(guān) K0級開關(guān) 0 0 0 0 0 與K21上輸出端連接 與K11上輸出端連接 與K01上輸出端連接 1 4 1 0 0 與K22下輸出端連接 與K14上輸出端連接 與K03上輸出端連接 2 2 0 1 0 與K23上輸出端連接 與K11下輸出端連接 與K02上輸出端連接 3 6 1 1 0 與K24下輸出端連接 與K14下

25、輸出端連接 與K04上輸出端連接 4 1 0 0 1 與K21上輸出端連接 與K11上輸出端連接 與K01下輸出端連接 5 5 1 0 1 與K22下輸出端連接 與K14上輸出端連接 與K03下輸出端連接 6 3 0 1 1 與K23上輸出端連接 與K11下輸出端連接 與K02下輸出端連接 7 7 1 1 1 與K24下輸出端連接 與K14下輸出端連接 與K04下輸出端連接 由表可見，當(dāng)實現(xiàn)八個結(jié)點對連接時，對K2級開關(guān)的要求將發(fā)生下列爭用開關(guān)輸出端的沖突： 0 0 和 4 1 爭用開關(guān)K21上輸出端 1 4 和 5 5 爭用開關(guān)K22下輸出端 2 2 和 6 3 爭用開關(guān)K23上輸出端 3

26、6 和 7 7 爭用開關(guān)K24下輸出端因此，為避免K2級開關(guān)輸出端的沖突，八個結(jié)點對連接分兩次實現(xiàn)。第一次實現(xiàn)：0 0、1 4、2 2、3 6；第二次實現(xiàn)：4 1、5 5、6 3、7 7。分兩次實現(xiàn)連接也避免K1級開關(guān)K11和K14輸出端的沖突，K0級四個開關(guān)沒有輸出端的沖突。（3）Omega網(wǎng)絡(luò)分2次連接的開關(guān)狀態(tài)如下圖。0123456701234567 第一次0123456701234567 第二次3.55 對于4方體網(wǎng)絡(luò)見圖3-65，從結(jié)點0000到結(jié)點1111，有多少條最短路徑？為什么？用E立方維序?qū)剿惴ㄕ页銎渲幸粭l最短路徑。 解：（1）當(dāng)源節(jié)點與目的節(jié)點的海明距離為h，則有h!條最

27、短路徑。結(jié)點0000到結(jié)點1111的海明距離為4，所以有1×2×3×4=24條最短路徑。 （2）方向位向量R = SD = 00001111 = 1111，V = S = 0000（源節(jié)點）r1=1，V = V2i-1 = 00000001 = 0001；r2=1，V = V2i-1 = 00010010 = 0011；r3=1，V = V2i-1 = 00110100 = 0111；r4=1，V = V2i-1 = 01111000 = 1111（目的結(jié)點）。所以，0000與1111有一條最短路徑為：S=00000001001101111111=D。第 四 章

28、4.52 浮點數(shù)系統(tǒng)使用的階碼基值re=2，階值位數(shù)q=2，尾數(shù)基值rm=10，尾數(shù)位數(shù)p=1，即按照使用的二進制位數(shù)來說，等價于p=4。計算在非負階、正尾數(shù)、規(guī)格化情況下的最小尾數(shù)值、最大尾數(shù)值、最大階值、可表示的最小值和最大值及可表示數(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 = 2

29、2×101（10-1）/10 = 364.53 一臺機器要求浮點數(shù)的字長的精度不低于10-7.2，表數(shù)的范圍正數(shù)不小于1038，且正負對稱。尾數(shù)用原碼、純小數(shù)表示，階碼用移碼、整數(shù)表示。設(shè)計這種浮點數(shù)的格式。解 依題意，取表數(shù)范圍N =1038，表數(shù)精度=10-7.2。由式（4-4）得： = 6.99，上取整，得到階碼字長q=7。由式（4-5）得：，上取整，得到尾數(shù)字長p=24。從而加上一個尾數(shù)符號位和一個階碼符號位，浮點數(shù)的總字長為：p+q+2=24+7+2=33。實際浮點數(shù)總字長應(yīng)為8的倍數(shù)，故取浮點數(shù)總字長為40位。多出的7位可以加到尾數(shù)字長p中用于提高浮點數(shù)的表數(shù)精度，也可以

30、加到階碼字長q中來擴大浮點數(shù)的表數(shù)范圍。暫且讓p增加6位，q增加1位，即p=30，q=8。如圖4-8所示是設(shè)計出來的浮點數(shù)格式。長度 1 p=30 1 q=8位序 39 38 9 8 7 0尾符S 尾數(shù)M 階符F 階碼E圖4-8 例4.2浮點數(shù)的設(shè)計格式4.58 用于文字處理的某專用機，每個文字符用4位十進制數(shù)字（09）編碼表示，空格用表示。在對傳送的文字符和空格進行統(tǒng)計后，得出它們的使用頻度如下：0.20 0:0.17 1:0.06 2: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è)計編碼

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

32、（位）若波特率為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）當(dāng)采用四位定長編碼時，則需要傳輸二進制位數(shù)為：106×4（41）=2×107（位），傳輸時間為：2×107/（56×103）=357（s）。 1 0 1 0 1 0 1 0 1 0 1 0 3 7 0 5 1 6 4 2IiPiHuffman編碼Li0201020017

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

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

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

36、：ADD（加） 30% SUB（減） 24% JOM（按負轉(zhuǎn)移）6% STO（存） 7%JMP（轉(zhuǎn)移）7% SHR（右移）2% CIL（循環(huán)左移）3% CLA（清除）20%STP（停機）1%要求有兩種指令字長，都按雙操作數(shù)指令格式編排，采用擴展操作碼，并限制只能有兩種操作碼碼長。設(shè)該機有若干通用寄存器，主存為16位寬，按字節(jié)編址，采用按整數(shù)邊界存儲，任何指令都在一個主存周期中取得，短指令為寄存器-寄存器型，長指令為寄存器-主存型，主存地址應(yīng)能變址尋址。（1）僅根據(jù)使用頻度，不考慮其它要求，設(shè)計出全Huffman操作碼，計算其平均碼長；（2）考慮題目全部要求，設(shè)計優(yōu)化實用的操作碼形式，并計算其操

37、作碼的平均碼長；（3）該機允許使用多少可編址的通用寄存器？（4）畫出該機兩種指令字格式，標(biāo)出各字段之位數(shù)；（5）指出訪存操作數(shù)地址尋址的最大相對位移量為多少個字節(jié)？解：（1）根據(jù)給出的使用頻度，在構(gòu)造Huffman樹的過程中，有兩個結(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（

38、位）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)iPiHuffman編碼Li2-5編碼（3/6）LiADDI1030012002SUBI2024112012CLAI3020102102STOI400700114110015JMPI500700104110105JOMI600600014110115CILI7003000015111005SHRI80020000016111015STPI90010000006111105 STP SHR （2

39、）任何指令都在一個主存周期中取得，那么短指令字長為8位，長指令字長為16位。又指令都是二地址指令，所以短指令寄存器-寄存器型的格式為：操作碼（2位）寄存器1（3位）寄存器2（3位）長指令為寄存器-主存型的格式為：操作碼（5位）寄存器（3位）變址寄存器（3位）相對位移（5位）由題意可知：指令操作碼采用擴展編碼，且只能有兩種碼長。從指令使用頻度來看，ADD、SUB和CLA三條指令的使用頻度與其它指令的使用頻度相差較大，所以用兩位操作碼的三個碼點來表示三條指令，一個碼點作為擴展碼點，且擴展三位來表示六條指令，即采用2-4擴展編碼構(gòu)成3/6編碼，2-4擴展編碼如表所示。 2-4擴展編碼（3/6）的平均

40、長度為：l=×li=2.78（3）（4）由短指令寄存器-寄存器型的格式可知，寄存器號字段長度為3位，寄存器個數(shù)為8個。則各字段長度如圖格式所標(biāo)識。而對于長指令寄存器-主存型，一般變址寄存器是某通用寄存器，則變址寄存器號的字段長度為3位，則各字段長度如圖格式所標(biāo)識。（5）由于相對位移字段長度為5位，因此訪存地址尋址的最大相對位移量為25=32字節(jié)。4.79 下面是一段數(shù)據(jù)塊搬家程序。在RISC處理機中，為了提高指令流水線的執(zhí)行效率，通常要采用指令取消技術(shù)。START：MOVE AS，R1 ；把源數(shù)組的起始地址送入變址寄存器R1MOVE NUM，R2 ；把傳送的數(shù)據(jù)個數(shù)送入R2LOOP：

41、 MOVE （R1），ADAS（R1） ；ADAS為地址偏移量，在匯編過程中計算INC R1 ；增量變址寄存器DEC R2 ；剩余數(shù)據(jù)個數(shù)減1BGT LOOP ；測試N個數(shù)據(jù)是否傳送完成HALT ；停機NUM： N ；需要傳送的數(shù)據(jù)總數(shù)（1）如果一條指令的執(zhí)行過程分解為“取指令”和“分析”兩個階段，并采用兩級流水線。為了采用指令取消技術(shù)，請修改上面的程序。（2）如果N=100，采用指令取消技術(shù)后，在程序執(zhí)行過程中，能夠節(jié)省多少個指令周期？（3）如果把一條指令的執(zhí)行過程分解為“取指令”、“分析”（包括譯碼和取操作數(shù)等）和“執(zhí)行”（包括運算和寫回結(jié)果等）三個階段，并采用三級流水線。仍然要采用指令取

42、消技術(shù)，請修改上面的程序。 解：（1）START：MOVE AS，R1MOVE NUM，R2MOVE （R1），ADAS（R1）LOOP：INC R1DEC R2BGT LOOPMOVE （R1），ADAS（R1）HALTNUM：N （2）解決轉(zhuǎn)移指令引起的流水線斷流可插入一條無效的空操作指令（NOP）?？詹僮髦噶钜惨加靡粋€機器周期，又不執(zhí)行任何實際的操作。當(dāng)N=100時，則要浪費100個機器周期（50個指令周期）。采用指令取消技術(shù)后，僅在轉(zhuǎn)移不成功時取消指令，浪費1個機器周期（0.5個指令周期）。因此可節(jié)省49.5個指令周期。（3）START：MOVE AS，R1MOVE NUM，R2MO

43、VE （R1），ADAS（R1）INC R1LOOP：DEC R2BGT LOOPMOVE （R1），ADAS（R1）INC R1HALTNUM：N 第 五 章5.34 在一個采用組相聯(lián)映象方式的Cache存儲系統(tǒng)中，主存由B0B7共8塊組成，Cache有2組，每組2塊，每塊大小為16B。在一個程序執(zhí)行過程中，訪存的主存塊地址流為：B6，B2，B4，B1，B4，B6，B3，B0，B4，B5，B7，B3。(1)寫出主存地址的格式，并標(biāo)出各字段的長度。(2)寫出Cache地址的格式，并標(biāo)出各字段的長度。(3)指出主存與Cache之間各個塊的映象關(guān)系。(4)若Cache的4個塊號為C0、C1、C2和C3，列出程序執(zhí)行過程中的Cache塊地址流。(5)若采用FIFO替換算法，計算Cache的塊命中率。(6)若采用LRU替換算法，計算Cache的塊命中率。(7)若改為全相聯(lián)映象方式，再做(5)和(6)。(8)若在程序執(zhí)行過程中，每從主存裝入一塊到Cache，平均