計算機系統(tǒng)結(jié)構(gòu)第四章習(xí)題解答

《計算機系統(tǒng)結(jié)構(gòu)第四章習(xí)題解答》由會員分享，可在線閱讀，更多相關(guān)《計算機系統(tǒng)結(jié)構(gòu)第四章習(xí)題解答（20頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、. 1. 假設(shè)一條指令的執(zhí)行過程分為“取指令”、“分析”和“執(zhí)行”三段，每一段的時間分別是△t、2△t和3△t。在下列各種情況下，分別寫出連續(xù)執(zhí)行n條指令所需要的時間表達式。 ⑴　順序執(zhí)行方式。 ⑵　僅“取指令”和“執(zhí)行”重疊。 ⑶　“取指令”、“分析”和“執(zhí)行”重疊。 答： ⑴　順序執(zhí)行方式 △t 2△t 3△t 1 2 ...... 1 2 1 2 T＝＝n(△t＋2△t＋3△t)＝6n△t ⑵　僅“取指令”和“執(zhí)行”重疊 △t 2△t 3△

2、t 1 2 ...... 1 2 1 2 T＝6△t＋＝6△t＋(n-1)(2△t＋3△t)＝(5n＋1)△t ⑶　“取指令”、“分析”和“執(zhí)行”重疊 精品 . △t 2△t 3△t 1 2 3 4 ...... 1 2 3 4 1 2 3 4 T＝6△t＋＝6△t＋(n-1)(3△t)＝(3n＋3)△t 2. 一條線性流水線有4個功能段組成，每個功能

3、段的延遲時間都相等，都為△t。開始5個任務(wù)，每間隔一個△t向流水線輸入一個任務(wù)，然后停頓2個△t，如此重復(fù)。求流水線的實際吞吐率、加速比和效率。 答： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ... 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 2 3 4 5

4、 6 7 8 9 10 11 12 13 14 15 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 我們可以看出，在（7n+1）Δt的時間內(nèi)，可以輸出5n個結(jié)果，如果指令的序列足夠長（n→∞），并且指令間不存在相關(guān)，那么，吞吐率可以認為滿足： 加速比為： 精品 . 從上面的時空圖很容易看出，效率為： 3. 用一條5個功能段的浮點加法器流水線計算。每個功能段的延遲時間均相等，流水線的輸出端與輸

5、入端之間有直接數(shù)據(jù)通路，而且設(shè)置有足夠的緩沖寄存器。要求用盡可能短的時間完成計算，畫出流水線時空圖，計算流水線的實際吞吐率、加速比和效率。 答： 首先需要考慮的是“10個數(shù)的和最少需要做幾次加法？”，我們可以發(fā)現(xiàn)，加法的次數(shù)是不能減少的：9次；于是我們要盡可能快的完成任務(wù)，就只有考慮如何讓流水線盡可能充滿，這需要消除前后指令之間的相關(guān)。由于加法滿足交換律和結(jié)合律，我們可以調(diào)整運算次序如以下的指令序列，我們把中間結(jié)果寄存器稱為R，源操作數(shù)寄存器稱為A，最后結(jié)果寄存器稱為F，并假設(shè)源操作數(shù)已經(jīng)在寄存器中，則指令如下： I1： R1←A1+A2 I2： R2←A3+A4 I3：

6、 R3←A5+A6 I4： R4←A7+A8 I5： R5←A9+A10 I6： R6←R1+R2 I7： R7←R3+R4 I8： R8←R5+R6 精品 . I9： F←R7+R8 這并不是唯一可能的計算方法。假設(shè)功能段的延遲為Δt。時空圖如下（圖中的數(shù)字是指令號）： 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8

7、 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 整個計算過程需要21Δt，所以吞吐率為： 加速比為： 效率為： 4. 一條線性靜態(tài)多功能流水線由6個功能段組成，加法操作使用其中的1、2、3、6功能段，乘法操作使用其中的1、4、5、6功能段，

8、每個功能段的延遲時間均相等。流水線的輸出端與輸入端之間有直接數(shù)據(jù)通路，而且設(shè)置有足夠的緩沖寄存器。用這條流水線計算向量點積，畫出流水線時空圖，計算流水線的實際吞吐率、加速比和效率。 精品 . 答： 我們安排運算次序如下：把中間結(jié)果寄存器稱為R，源操作數(shù)寄存器稱為A、B，最后結(jié)果寄存器稱為F，并假設(shè)源操作數(shù)已經(jīng)在寄存器中，則指令如下： I1： R0←A0*B0 I8： R7←R0+R1 I2： R1←A1*B1 I9： R8←R2+R3 I3： R2←A2*B2 I10： R9←R4+R5 I4： R3←A3*B3 I11： R10←R6+R7 I5：

9、 R4←A4*B4 I12： R11←R8+R9 I6： R5←A5*B5 I13： F←R10+R11 I7： R6←A6*B6 假設(shè)功能段的延遲為Δt。時空圖如下（圖中的數(shù)字是指令號）： 1 2 3 4 5 6 7 8 9 10 11 12 13 1 2 3 4 5 6 7 1 2 3 4 5 6 7

10、 8 9 10 11 12 13 8 9 10 11 12 13 1 2 3 4 5 6 7 8 9 10 11 12 13 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 整個計算過程需要24Δt，所以吞吐率為： 精品 . 加速比為： 效率為：

11、 5. 一條有三個功能段的流水線如下圖。每個功能段的延遲時間均相等，都為△t。其中功能段S2的輸出要返回到它自己的輸入端循環(huán)一次。 輸出 輸入 S3 S2 S1 △t △t △t ⑴　如果每間隔一個△t向流水線的輸入端連續(xù)輸入新任務(wù)，問這條流水線會發(fā)生什么情況？ ⑵　求這條流水線能夠正常工作的最大吞吐率、加速比和效率。 ⑶　有什么辦法能夠提高這條流水線的吞吐率，畫出新的流水線。 答： ⑴　 如果每間隔一個△t向流水線的輸入端連續(xù)輸入新任務(wù)，流水線S2功能段存在資源沖突。見下表： 時間 功能段 t1 t2 t3 t4 t5 S1

12、 X1 X2 X3 X4 X5 S2 X1 X1,X2 X2,X3 X3,X4 S3 X1 X2 ⑵　 精品 . 每間隔兩個△t向流水線的輸入端連續(xù)輸入新任務(wù)（如見下表所示）可獲得最佳性能。 時間 功能段 t1 t2 t3 t4 t5 t6 S1 X1 X2 X3 S2 X1 X1 X2 X2 X3 S3 X1 X2 我們可以看出：在（2n+2）Δt的時間內(nèi)，可以輸出n個結(jié)果，如果指令的序列足夠長（n→∞），并且指令間不存在相關(guān)，那么，吞吐率為： 加速比為：

13、 效率為： ⑶　 如要提高這條流水線的吞吐率，可采用：將功能段S2重復(fù)設(shè)置一次，見下圖： 輸出 S3 △t △t △t 輸入 S2 S2 S1 △t 6. 一條有4個功能段的非線性流水線，每個功能段的延遲時間都相等，都為20ns，它的預(yù)約表如下： 精品 . 時間 流水段 1 2 3 4 5 6 7 S1 × × S2 × × S3 × S4 × ×

14、 ⑴ 寫出流水線的禁止向量和初始沖突向量。 ⑵ 畫出調(diào)度流水線的狀態(tài)圖。 ⑶ 求流水線的最小啟動循環(huán)和最小平均啟動距離。 ⑷ 求平均啟動距離最小的恒定循環(huán)。 ⑸ 求流水線的最大吞吐率。 ⑹ 按照最小啟動循環(huán)連續(xù)輸入10個任務(wù)，求流水線的實際吞吐率。 ⑺ 畫出該流水線各功能段之間的連接圖。 答： ⑴ 禁止向量F=（6,4,2）；沖突向量C=（101010）。 ⑵ i=1 i≥7 i=3 i≥7 i=5 i=3 i≥7 i=5 i=5 i≥7 101010 111111 101111 101011 C0 C1 C2 C3

15、 精品 . ⑶ 簡單循環(huán) 平均啟動距離 1，7（C0-C1-C0） 4 3，7（C0-C2-C0） 5 5，7（C0-C3-C0） 6 3，5，7（C0-C2-C3-C0） 5 3，5（C0-C2-C3-C2-C3） 4 5，3，7（C0-C3-C2-C0） 5 5，3（C0-C3-C2-C3-C2） 4 5（C0-C3-C3） 5 7（C0-C0） 7 ∴ 流水線的最小啟動循環(huán)為：（1，7）或（3，5）或（5，3），最小平均啟動距離為4。 ⑷ 由上表可知：平均啟動距離最小的恒定循環(huán)為（5）。 ⑸ 采用最小平均啟動距

16、離為4的最小啟動循環(huán)可獲得流水線的最大吞吐率，以（1，7）為例：（其他類似，最大吞吐率皆相同） 當任務(wù)數(shù)為偶數(shù)2n時： 當任務(wù)數(shù)為奇數(shù)2n+1時： 精品 . ∴ 流水線的最大吞吐率為： ⑹ 10個任務(wù)的實際吞吐率：利用上式可得（偶數(shù)個任務(wù)）TP10=1/4△t=12.5M(任務(wù)/s)。 ⑺ 該流水線的連接圖為： S1 S2 S3 S4 1 2 3 4 5 6 7 輸入 輸出 7. 一條由4個功能段組成的非線性流水線的預(yù)約表如下，每個功能段的延遲時間都為10ns。 時間 流水段 1 2 3 4

17、5 6 S1 × × S2 × × S3 × S4 × × ⑴　寫出流水線的禁止向量和初始沖突向量。 ⑵　畫出調(diào)度流水線的狀態(tài)圖。 ⑶　求流水線的最小啟動循環(huán)和最小平均啟動距離。 精品 . ⑷　在流水線中插入一個非計算延遲功能段后，求該流水線的最佳啟動循環(huán)及其最小平均啟動距離。 ⑸　畫出插入一個非計算延遲功能段后的流水線預(yù)約表（5行8列）。 ⑹　畫出插入一個非計算延遲功能段后的流水線狀態(tài)變換圖。 ⑺　分別計算在插入一

18、個非計算延遲功能段前、后的最大吞吐率。 ⑻　如果連續(xù)輸入10個任務(wù)，分別計算在插入一個非計算延遲功能段前、后的實際吞吐率。 答： ⑴　 禁止向量F=（5,2,1）；沖突向量C=（10011）。 ⑵　 10011 i=3 i=4 C0 i≥6 ⑶　 簡單循環(huán) 平均啟動距離 3 3 4 4 6 6 最小啟動循環(huán)為（3），最小平均啟動距離為3。 ⑷　 插入一個非計算延遲功能段后，最小平均啟動距離為2（因為預(yù)約表中每行至多2個×），相應(yīng)地可改進最小啟動循環(huán)為（2）。 精品 . ⑸　 時間 功能段 1 2 3 4 5 6 7

19、 8 S1 X X S2 X X S3 X S4 X X D X X ⑹　 流水線的禁止向量為（1，3，7），流水線的沖突向量為1000101， 流水線的狀態(tài)圖如下： 1000101 1010101 1000111 i=4,6 i≥8 i=4,6 i≥8 i=4,6 i≥8 i=2 i=2 i=5 C0 C1 C2 i=5 簡單循環(huán) 平均啟動距離 2，4(C0-C1) 3

20、2，6(C0-C1) 4 2(C0-C1-C1) 2 4(C0-C0) 4 6(C0-C0) 6 精品 . 5(C0-C2-C2) 5 5，4(C0-C2) 4.5 5，6(C0-C2) 5.5 流水線的最小啟動循環(huán)為（2），最小平均啟動距離為2。 ⑺　 插入前： 插入后： ⑻　 連續(xù)輸入10個任務(wù)，插入前的實際吞吐率為： 連續(xù)輸入10個任務(wù)，插入后的實際吞吐率為： 8. 在流水線處理機中，有獨立的加法操作部件和乘法操作部件各一個，加法操作部件為4段流水線，乘法操作部件6段流水線，都在第一段從通用寄存器讀操作數(shù)，在最后一

21、段把運算結(jié)果寫到通用寄存器中。每段的時間長度都相等，都是一個時鐘周期。每個時鐘周期發(fā)出一條指令。問可能發(fā)生哪幾種數(shù)據(jù)相關(guān)?寫出發(fā)生相關(guān)的指令序列，分析相關(guān)發(fā)生的原因，并給出解決相關(guān)的具體辦法。 精品 . 答： 可能的數(shù)據(jù)相關(guān)性有： ⑴　“先寫后讀”（RAW）相關(guān) Ø Read After 加法寫。原因：還沒有寫好就已經(jīng)讀取寄存器中的數(shù)據(jù)了。 DADD R1,R2,R3 ；（R2）＋（R3）→（R1） DSUB R4,R1,R5 ；（R1）－（R5）→（R4） Ø Read After 乘法寫。原因：還沒有寫好已經(jīng)讀取寄存器中的數(shù)據(jù)了。 DMUL R1

22、,R2,R3 ；（R2）×（R3）→（R1） DSUB R4,R1,R5 ；（R1）－（R5）→（R4） 本相關(guān)在流水線順序執(zhí)行和亂序執(zhí)行時都可能發(fā)生。解決的方法是：利用編譯程序調(diào)整指令的次序方法；延遲執(zhí)行是避免數(shù)據(jù)相關(guān)最簡單的方法；建立寄存器之間的專用路徑。 ⑵ “寫—寫”（WAW）相關(guān) Write After 乘法寫。原因：后寫的反而早執(zhí)行（乘法所化的時間長，后面一個寫任務(wù)反而先完成），使最后寫入的內(nèi)容不正確。 DMUL R1,R2,R3 ；（R2）×（R3）→（R1） DSUB R1,R4,R5 ；（R4）－（R5）→（R1） 本相關(guān)只有在流水

23、線亂序執(zhí)行時才可能發(fā)生。解決的方法是：寄存器換名。 ⑶ “先讀后寫”（WAR）相關(guān) Write After 任何讀。原因：前面的讀操作因為某種原因被推遲，要讀的內(nèi)容被后面的寫操作修改了。 精品 . DSUB R4,R1,R5 ；（R1）－（R5）→（R4） DADD R1,R2,R3 ；（R2）＋（R3）→（R1） 本相關(guān)只有在流水線亂序執(zhí)行時才可能發(fā)生。解決的方法是：寄存器換名。 9. 在下列不同結(jié)構(gòu)的處理機上運行8×8的矩陣乘法C=A×B，計算所需要的最短時間。只計算乘法指令和加法指令的執(zhí)行時間，不計算取操作數(shù)、數(shù)據(jù)傳送和程序控制等指令的執(zhí)

24、行時間。加法部件和乘法部件的延遲時間都是3個時鐘周期，另外，加法指令和乘法指令還要經(jīng)過一個“取指令”和“指令譯碼”的時鐘周期，每個時鐘周期為20ns，C的初始值為“0”。各操作部件的輸出端有直接數(shù)據(jù)通路連接到有關(guān)操作部件的輸入端，在操作部件的輸出端設(shè)置有足夠容量的緩沖寄存器。 ⑴　處理機內(nèi)只有一個通用操作部件，采用順序方式執(zhí)行指令。 ⑵　單流水線標量處理機，有一條兩個功能的靜態(tài)流水線，流水線每個功能段的延遲時間均為一個時鐘周期，加法操作和乘法操作各經(jīng)過3個功能段。 ⑶　多操作部件處理機，處理機內(nèi)有獨立的乘法部件和加法部件，兩個操作部件可以并行工作。只有一個指令流水線，操作部件不采用流水線

25、結(jié)構(gòu)。 ⑷　單流水線標量處理機，處理機內(nèi)有兩條獨立的操作流水線，流水線每個功能段的延遲時間均為一個時鐘周期。 ⑸　超標量處理機，每個時鐘周期同時發(fā)射一條乘法指令和一條加法指令，處理機內(nèi)有兩條獨立的操作流水線，流水線的每個功能段的延遲時間均為一個時鐘周期。 精品 . ⑹　超流水線處理機，把一個時鐘周期分為兩個流水級，加法部件和乘法部件的延遲時間都為6個流水級，每個時鐘周期能夠分時發(fā)射兩條指令，即每個流水級能夠發(fā)射一條指令。 ⑺　超標量超流水線處理機，把一個時鐘周期分為兩個流水級，加法部件和乘法部件延遲時間都為6個流水級，每個流水級能夠同時發(fā)射一條乘法指令和一條加法指令。 答： 要

26、完成上面的矩陣乘法，需要完成的乘法數(shù)目為8×8×8=512次；需要完成的加法數(shù)目為8×8×7=448次；下面分析處理機的結(jié)構(gòu)會給性能帶來什么樣的影響。 ⑴　通用操作部件采用順序方式執(zhí)行 順序執(zhí)行時，每個乘法和加法指令都需要5個時鐘周期（取指令、指令分析、指令執(zhí)行）；所以所需要的時間為： ⑵　單流水線標量處理機，有一條兩個功能的靜態(tài)流水線 因為有足夠的緩沖寄存器，所以我們可以首先把所有的乘法計算完，并通過調(diào)度使加法流水線不出現(xiàn)停頓，所以所需要的時間為： 加法 加3 1 2 3

27、 4 … 加2 1 2 3 4 … 加1 1 2 3 4 … 乘法 乘3 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ … 乘2 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ … 精品 . 乘1 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ …

28、 譯碼 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ … 1 2 3 4 … 取指 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ … 1 2 3 4 … 1 2 3 4 5 6 7 8 513 514 515 516 517 518 963 964 965 966 1=①+②、2=1+③、3=2+④、4=3+⑤、5=4+⑥、6=5+⑦、7=6+⑧ ⑶　多操作部件處理機，只有一條指令流水線 由于只有一條指令流水線，所以只

29、能一個時鐘周期發(fā)射一條指令；由于操作部件不采用流水線，對于結(jié)果C矩陣的第一個元素，首先執(zhí)行2次乘法，然后乘法和加法并行執(zhí)行7次，此時C矩陣的第一個元素出來了，然后加法運算停頓3個時鐘周期，再開始與乘法并行執(zhí)行運算7次，如此下去，直到C的64個元素都出來。故執(zhí)行時間為： ⑷　單流水線標量處理機，處理機內(nèi)有兩條獨立的操作流水線 由于只有一條指令流水線，所以只能一個時鐘周期發(fā)射一條指令；對于乘法運算不存在數(shù)據(jù)相關(guān)，對于加法運算有數(shù)據(jù)相關(guān)，由于存在足夠的緩沖寄存器，我們可以通過合適的調(diào)度消除加法的數(shù)據(jù)相關(guān)。因此，最佳情況下的執(zhí)行時間為： 加法 加3

30、 1 2 3 4 5 6 7 加2 1 2 3 4 5 6 7 加1 1 2 3 4 5 6 7 乘法 乘3 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ① ② ③ 精品 . 乘2 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ① ② ③ ④ 乘1 ① ② ③ ④ ⑤ ⑥

31、 ⑦ ⑧ ① ② ③ ④ … 譯碼 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ 1 2 3 4 5 6 7 ① ② ③ ④ … 取指 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ 1 2 3 4 5 6 7 ① ② ③ ④ … 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 1=①+②、2=1+③、3=2+④、4=3+⑤、5=4+⑥、6=5+⑦、7=6+

32、⑧ ⑸　超標量處理機 同一時鐘周期可以有一條乘法指令和一條加法指令同時發(fā)射，對于乘法運算不存在數(shù)據(jù)相關(guān)性，對于加法運算有數(shù)據(jù)相關(guān)性，由于存在足夠的緩沖寄存器，當運算完所有的乘法運算后，還要做一次加法運算。因此執(zhí)行時間為： 加法 加3 1 2 3 4 5 6 7 1 2 3 4 5 … 加2 1 2 3 4 5 6 7 1 2 3 4 5 … 加1 1 2 3 4 5 6 7 1 2 3 4 5 …

33、 譯碼 1 2 3 4 5 6 7 1 2 3 4 5 … 取指 1 2 3 4 5 6 7 1 2 3 4 5 … 乘法 乘3 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ … 乘2 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ … 乘1 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ① ② ③

34、④ ⑤ ⑥ ⑦ ⑧ … 譯碼 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ … 取指 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ … 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 精品 . 1=①+②、2=1+③、3=2+④、4=3+⑤、5=4+⑥、6=5+⑦、7=6+⑧ ⑹　超流水線處理機 每個時鐘周期發(fā)射兩條指令，加法部件和乘法部件都為6個流水級。事實上相當于將時鐘周期變成了10ns，而加法和乘法流水線變成了6級。因此執(zhí)行時間為： ⑺　超標量超流水線處理機 一個時鐘周期分為兩個流水級，加法部件和乘法部件都為6個流水級，每個流水級能同時發(fā)射一條加法和一條乘法指令。綜合⑸和⑹的分析，我們可以知道，執(zhí)行時間為： 如有侵權(quán)請聯(lián)系告知刪除，感謝你們的配合！ 精品