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

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

1、1.假設(shè)一條指令的執(zhí)行過程分為“取指令”、“分析”和“執(zhí)行”三段，每一段的時(shí)間分別是^t、2z\t和3Ato在下列各種情況下，分別寫出連續(xù)執(zhí)行 n條指令所需要的時(shí)間表達(dá)式。 ⑴順序執(zhí)行方式。 ⑵僅“取指令”和“執(zhí)行”重疊。 ⑶“取指令”、“分析”和“執(zhí)行”重疊 答： ⑴順序執(zhí)行方式 12 12 12 △t2At3At n T=(t取址it分析it執(zhí)行i)=ngt+2A+3z\t)=6nz\t i1 ⑵僅“取指令”和“執(zhí)行”重疊 2At 3At n-1 T=6At+(t分析it執(zhí)行i)=6A+(n-1)(2z\t+3z\t)=(5n+1

2、)A i1 △ t 2At 3At  T= 6At + n-1 (t執(zhí)行i)=6At+(n-1)(341)=(3n+3)Ati1 2 .一條線性流水線有4個(gè)功能段組成，每個(gè)功能段的延遲時(shí)間都相等，都為 △to開始5個(gè)任務(wù)，每間隔一個(gè)△t向流水線輸入一個(gè)任務(wù)，然后停頓2 個(gè)At,如此重復(fù)。求流水線的實(shí)際吞吐率、加速比和效率。 我們可以看出，在（7n+1） At的時(shí)間內(nèi)，可以輸出5n個(gè)結(jié)果，如果指令 t (7 1/n) t 5 (n 7 t S （7n 1） t 從上面的時(shí)空圖很容易看出, 5n 4 t 20n 7n 1 效率為: 5

3、n E 4 (7n 1) t 7n 1 20 1/n 20/ Y(n 7 1/n 5 7(n 的序列足夠長（n一^）,并且指令間不存在相關(guān)，那么，吞吐率可以認(rèn)為滿足: 5n TP (7n1) 加速比為: 10 3 .用一條5個(gè)功能段的浮點(diǎn)加法器流水線計(jì)算FAio每個(gè)功能段的延遲 i1 時(shí)間均相等，流水線的輸出端與輸入端之間有直接數(shù)據(jù)通路，而且設(shè)置有足夠的緩沖寄存器。要求用盡可能短的時(shí)間完成計(jì)算，畫出流水線時(shí)空圖，計(jì)算流水線的實(shí)際吞吐率、加速比和效率。 首先需要考慮的是“10個(gè)數(shù)的和最少需要做幾次加法”，我們可以發(fā)現(xiàn)，加 法的次數(shù)是不能減少的：9

4、次；于是我們要盡可能快的完成任務(wù)，就只有考慮如 何讓流水線盡可能充滿，這需要消除前后指令之間的相關(guān)。由于加法滿足交換律 和結(jié)合律，我們可以調(diào)整運(yùn)算次序如以下的指令序列， 我們把中間結(jié)果寄存器稱 為R,源操作數(shù)寄存器稱為 A,最后結(jié)果寄存器稱為F,并假設(shè)源操作數(shù)已經(jīng)在 寄存器中，則指令如下: 11: R1-A1+A2 12: R2^ A3+A4 13: R3- A5+A6 14: R4- A7+A8 15: R-A9+A10 16: RA R1+R2 17: R7- R3+R4 18: R8- R5+R6 19: F— R7+R8 這并不是唯一可能的

5、計(jì)算方法。假設(shè)功能段的延遲為A to時(shí)空圖如下（圖 中的數(shù)字是指令號(hào)）： 8 9 10 11 12 13 14 15 16 17 18 19 20 21 整個(gè)計(jì)算過程需要 21 At,所以吞吐率為: TP -9 21 t 0.43 加速比為: S ? 21 t 15 2.1429 效率為: 4. B, 9 5 t 3 E 0.43 5 21 t 7 一條線性靜態(tài)多功能流水線由6個(gè)功能段組成，加法操作使用其中的1、2、 3、6功能段，乘法操作使用其中的1、4、5、6功能段，每個(gè)功能段的延遲 時(shí)間均相等。流水線的輸出端

6、與輸入端之間有直接數(shù)據(jù)通路，而且設(shè)置有 足夠的緩沖寄存器。用這條流水線計(jì)算向量點(diǎn)積 A B 水線時(shí)空圖，計(jì)算流水線的實(shí)際吞吐率、加速比和效率。 ai bi ,畫出流 i 0 我們安排運(yùn)算次序如下：把中間結(jié)果寄存器稱為R,源操作數(shù)寄存器稱為A、 最后結(jié)果寄存器稱為F,并假設(shè)源操作數(shù)已經(jīng)在寄存器中，則指令如下: 11: Rg A0*B0 I8: R7- R0+R1 12: R1—A1*B1 I9: R8- R2+R3 13: R2^ A2*B2 110: RA R4+R5 I4: RA A3*B3 111: R14 R6+R7 I5: R- A4*B

7、4 112: R11-R8+R9 I6: R5^ A5*B5 113: F―R10+R11 I7: RA A6*B6 假設(shè)功能段白延遲為A t 時(shí)空圖如下（圖中的數(shù)字是指令號(hào)） 13 10 10 11 12 11 12 13 10 11 12 13 123456789101112131415161718192021222324 整個(gè)計(jì)算過程需要24At,所以吞吐率為: 5. 加速比為: 效率為: TP 13 0.54 24 t c 7 4 t 6 4 S 24 t 13 2.17 6 E 4 13 t 6 2

8、4 t 13 0.36 36 一條有三個(gè)功能段的流水線如下圖。每個(gè)功能段的延遲時(shí)間均相等，都為 △to其中功能段S2的輸出要返回到它自己的輸入端循環(huán)一次。 于S1 S2 S3 輸出 輸入 如果每間隔一個(gè)^t向流水線的輸入端連續(xù)輸入新任務(wù)，問這條流水線會(huì)發(fā) 生什么情況 求這條流水線能夠正常工作的最大吞吐率、加速比和效率。 有什么辦法能夠提高這條流水線的吞吐率，畫出新的流水線。 如果每間隔一個(gè)^t向流水線的輸入端連續(xù)輸入新任務(wù)，流水線S2功能段存 每間隔兩個(gè)△t向流水線的輸入端連續(xù)輸入新任務(wù)（如見下表所示）可獲得 最佳性能。 寸間功能隆、

9、t1 t2 t3 t4 t5 t6  S1 X1 X2 X3 S2 X1 X1 X2 X2 X3 S3 X1 X2 我們可以看出：在（2n+2）At的時(shí)間內(nèi)，可以輸出n個(gè)結(jié)果，如果指令的 序列足夠長（n一8）,并且指令間不存在相關(guān)，那么，吞吐率為: TP n (2n 2) t 1 (2 2/n) t (n 加速比為: n 4 t (2n 2) t 2n 2 n 1 1 1 /n 2(n 效率為: 3 (2n 2) t 2n 2 2, (n 3n 3 3 3

10、/n 3 圖: 如要提高這條流水線的吞吐率，可采用：將功能段 S2重復(fù)設(shè)置一次，見下 ⑴寫出流水線的禁止向量和初始沖突向量 ⑵ 畫出調(diào)度流水線的狀態(tài)圖。 6. 一條有4個(gè)功能段的非線性流水線，每個(gè)功能段的延遲時(shí)間都相等，都為 流水》\ 1 2 3 4 5 6 7 S X X 及 X X X X X 20ns,它的預(yù)約表如下: 0  ⑶求流水線的最小啟動(dòng)循環(huán)和最小平均啟動(dòng)距離⑷求平均啟動(dòng)距離最小的恒定循環(huán)。 ⑸求流水線的最大

11、吞吐率。 ⑹按照最小啟動(dòng)循環(huán)連續(xù)輸入10個(gè)任務(wù)，求流水線的實(shí)際吞吐率 ⑺畫出該流水線各功能段之間的連接圖。 答： ⑴ 禁止向量F=（6,4,2）;沖突向量C=（101010）。 ⑵ 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-。3 4 5,3,7(C0-C3-C2-C0 5 5,3(C0-C3-C2-C3-。2 4 5(C0-C3-C3 5 7(C0-CO 7 流水線的最小啟動(dòng)循環(huán)為：（1,7）或（3,5）或（5,3

12、）,最小平均啟動(dòng)距 離為4。 由上表可知：平均啟動(dòng)距離最小的恒定循環(huán)為（5）。 采用最小平均啟動(dòng)距離為4的最小啟動(dòng)循環(huán)可獲得流水線的最大吞吐率, (1 7）為例：（其他類似，最大吞吐率皆相同） 當(dāng)任務(wù)數(shù)為偶數(shù)2n時(shí): TP 2n 7 t n t 當(dāng)任務(wù)數(shù)為奇數(shù)2n+1時(shí)： (n 1) 7 t 2n 8n t 六(n (6) 流水線的最大吞吐率為: 2n 1 8n t 7 t 1 4 t 4 20ns 1/n 8 t 7 t/n 六(n ) 12.5M(任務(wù) /s) 10個(gè)任務(wù)的實(shí)際吞吐率: 利用上式可得（偶數(shù)個(gè)任務(wù)）TPio=1/4At=1

13、2.5M（任 務(wù)⑸。 該流水線的連接圖為: 輸入 S1 輸出 S2 S3 S4 7. 一條由4個(gè)功能段組成的非線性流水線的預(yù)約表如下，每個(gè)功能段的延遲 時(shí)間都為10區(qū) \^寸問 流水1\ 1 2 3 4 5 6 Si X X S2 X X S3 X ⑴寫出流水線的禁止向量和初始沖突向量。 ⑵畫出調(diào)度流水線的狀態(tài)圖。 ⑶求流水線的最小啟動(dòng)循環(huán)和最小平均啟動(dòng)距離。 ⑷在流水線中插入一個(gè)非計(jì)算延遲功能段后，求該流水線的最佳啟動(dòng)循環(huán)及其最小平均啟動(dòng)距離。 ⑸畫出插入一個(gè)非計(jì)算延遲功能段

14、后的流水線預(yù)約表（5行8歹I」）。 ⑹畫出插入一個(gè)非計(jì)算延遲功能段后的流水線狀態(tài)變換圖。 ⑺分別計(jì)算在插入一個(gè)非計(jì)算延遲功能段前、后的最大吞吐率。 ⑻如果連續(xù)輸入10個(gè)任務(wù)，分別計(jì)算在插入一個(gè)非計(jì)算延遲功能段前、后的實(shí)際吞吐率。 答： ⑴ 禁止向量F=（5,2,1）;沖突向量C=（10011）。 ⑵ i=4 i=3 3 3 4 4 6 6 最小啟動(dòng)循環(huán)為（3）,最小平均啟動(dòng)距離為3。 ⑷ 插入一個(gè)非計(jì)算延遲功能段后，最小平均啟動(dòng)距離為2（因?yàn)轭A(yù)約表中每行至多2個(gè)X）,相應(yīng)地可改進(jìn)最小啟動(dòng)循環(huán)為（2）。 ⑸ 1 2 3 4 5 6

15、 7 8  S1 X X S2 X X S3 X S4 X X D X X （6） 流水線的禁止向量為（1, 3, 7）,流水線的沖突向量為1000101, 流水線的狀態(tài)圖如下： 2, 4(C0-C1) 3 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) 5,

16、 6(C0-C2) 流水線的最小啟動(dòng)循環(huán)為（2）,最小平均啟動(dòng)距離為2 插入前: TPmax lim 'm' 6 t (n 1) 3 t ——1一3.33107(任務(wù)數(shù)/s) 3t310ns 插入后: TP max lim n 6 t (n 1) 2 t 2 10ns 5 107(任務(wù)數(shù)/s) 連續(xù)卒&入10個(gè)任務(wù)，插入前的實(shí)際吞吐率為： 1010107, TP3.03107(任務(wù)數(shù)/s) 6t93t33t3310ns 連續(xù)卒&入10個(gè)任務(wù)，插入后的實(shí)際吞吐率為： TP 10 8 t 9 2

17、t 10 10 3.85 26 t 26 10ns 107(任務(wù)數(shù)/s) 8. 在流水線處理機(jī)中，有獨(dú)立的加法操作部件和乘法操作部件各一個(gè)，加法 操作部件為4段流水線，乘法操作部件6段流水線，都在第一段從通用寄存器讀操作數(shù)，在最后一段把運(yùn)算結(jié)果寫到通用寄存器中。每段的時(shí)間長度都相等，都是一個(gè)時(shí)鐘周期。每個(gè)時(shí)鐘周期發(fā)出一條指令。問可能發(fā)生哪幾種數(shù)據(jù)相關(guān)寫出發(fā)生相關(guān)的指令序列，分析相關(guān)發(fā)生的原因，并給出解決相關(guān)的具體辦法。 答： 可能的數(shù)據(jù)相關(guān)性有： ⑴“先寫后讀”(RAW)相關(guān) ReadAfter加法寫。原因：還沒有寫好就已經(jīng)讀取寄存器中的數(shù)據(jù)了。 DADDR1

18、,R2,R3;(R2)+(R3)一(R1) DSUBR4,R1,R5;(R1)—(R5)一(R4) ReadAfter乘法寫。原因：還沒有寫好已經(jīng)讀取寄存器中的數(shù)據(jù)了。 DMULR1,R2,R3;(R2)X(R3)—(R1) DSUBR4,R1,R5;(R1)—(R5)一(R4) 本相關(guān)在流水線順序執(zhí)行和亂序執(zhí)行時(shí)都可能發(fā)生。解決的方法是：利用編譯程序調(diào)整指令的次序方法；延遲執(zhí)行是避免數(shù)據(jù)相關(guān)最簡單的方法；建立寄存器之間的專用路徑。 ⑵“寫一寫"(WAW)相關(guān) WriteAfter乘法寫。原因：后寫的反而早執(zhí)行(乘法所化的時(shí)間長，后面 一個(gè)寫任務(wù)反而先完成)，使最后寫入的內(nèi)容不

19、正確。 DMULR1,R2,R3;(R2)X(R3)—(R1) DSUBR1,R4,R5；(R4)—(R5)—(R1) 本相關(guān)只有在流水線亂序執(zhí)行時(shí)才可能發(fā)生。解決的方法是：寄存器換名。 ⑶“先讀后寫”(WAR)相關(guān) WriteAfter任何讀。原因：前面的讀操作因?yàn)槟撤N原因被推遲，要讀的內(nèi) 容被后面的寫操作修改了。 DSUBR4,R1,R5;(R1)—(R5)—(R4) DADDR1,R2,R3;(R2)+(R3)—(R1) 本相關(guān)只有在流水線亂序執(zhí)行時(shí)才可能發(fā)生。解決的方法是：寄存器換名。 9. 在下列不同結(jié)構(gòu)的處理機(jī)上運(yùn)行8X8的矩陣乘法C=AXB,計(jì)算所需要的 最

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

21、機(jī)，處理機(jī)內(nèi)有獨(dú)立的乘法部件和加法部件，兩個(gè)操作部件 可以并行工作。只有一個(gè)指令流水線，操作部件不采用流水線結(jié)構(gòu)。 ⑷單流水線標(biāo)量處理機(jī)，處理機(jī)內(nèi)有兩條獨(dú)立的操作流水線，流水線每個(gè)功能 段的延遲時(shí)間均為一個(gè)時(shí)鐘周期。 ⑸超標(biāo)量處理機(jī)，每個(gè)時(shí)鐘周期同時(shí)發(fā)射一條乘法指令和一條加法指令，處理 機(jī)內(nèi)有兩條獨(dú)立的操作流水線，流水線的每個(gè)功能段的延遲時(shí)間均為一個(gè) 時(shí)鐘周期。 ⑹超流水線處理機(jī)，把一個(gè)時(shí)鐘周期分為兩個(gè)流水級(jí)，加法部件和乘法部件的 延遲時(shí)間都為6個(gè)流水級(jí)，每個(gè)時(shí)鐘周期能夠分時(shí)發(fā)射兩條指令，即每個(gè)流水級(jí)能夠發(fā)射一條指令。 ⑺超標(biāo)量超流水線處理機(jī)，把一個(gè)時(shí)鐘周期分為兩個(gè)流水級(jí)，

22、加法部件和乘法部件延遲時(shí)間都為6個(gè)流水級(jí)，每個(gè)流水級(jí)能夠同時(shí)發(fā)射一條乘法指令和一條加法指令。 答： 要完成上面的矩陣乘法，需要完成的乘法數(shù)目為8X8X8=512次；需要完成的加法數(shù)目為8X8X7=448次；下面分析處理機(jī)的結(jié)構(gòu)會(huì)給性能帶來什么樣的影響。 ⑴通用操作部件采用順序方式執(zhí)行 順序執(zhí)行時(shí)，每個(gè)乘法和加法指令都需要5個(gè)時(shí)鐘周期（取指令、指令分析、指令執(zhí)行）；所以所需要的時(shí)間為： T(512448)520ns96000ns96s ⑵單流水線標(biāo)量處理機(jī)，有一條兩個(gè)功能的靜態(tài)流水線 因?yàn)橛凶銐虻木彌_寄存器，所以我們可以首先把所有的乘法計(jì)算完，并通過 調(diào)度使加法流水線不出現(xiàn)停頓，

23、所以所需要的時(shí)間為: 加3 加 12 3 4 1 2 3 4 ??? 1 2 3 4 ??? 加2 法 力口 1 譯碼 取指①②③④⑤⑥⑦⑧ 12 3 4 1 2 3 4 - 513514515516517518963964965966 1=?+@、2=1鉉、3=2短、4=3+⑤、5=4喳、6=50、7=6+? T[2(35121)(34481)]20ns19.32s ⑶多操作部件處理機(jī)，只有一條指令流水線 由于只有一條指令流水線，所以只能一個(gè)時(shí)鐘周期發(fā)射一條指令；由于操作部件不采用流水線，對于2果C矩陣的第一個(gè)元素，首先執(zhí)行2次乘法，然后乘法和加法并行

24、執(zhí)行7次，此時(shí)C矩陣的第一個(gè)元素出來了，然后加法運(yùn)算停頓3個(gè)時(shí)鐘周期，再開始與乘法并行執(zhí)行運(yùn)算7次，如此下去，直到C的64個(gè)元素都出來。故執(zhí)行時(shí)間為： T[2(3237)63(337)]20ns30820ns30.82s ⑷單流水線標(biāo)量處理機(jī)，處理機(jī)內(nèi)有兩條獨(dú)立的操作流水線 由于只有一條指令流水線，所以只能一個(gè)時(shí)鐘周期發(fā)射一條指令；對于乘法運(yùn)算不存在數(shù)據(jù)相關(guān)，對于加法運(yùn)算有數(shù)據(jù)相關(guān)，由于存在足夠的緩沖寄存器, 加3 加 加2 法 力口 1 我們可以通過合適的調(diào)度消除加法的數(shù)據(jù)相關(guān)。因此，最佳情況下的執(zhí)行時(shí)間為: 1234567 1234567 1234567 譯碼①②③④

25、⑤⑥①⑧1234567①②③④… 取指①②③④⑤⑥⑦⑧1234567①②③④?… 12345678910111213141516171819202122 1=?+@、2=1鉉、3=2短、4=3+⑤、5=4+(?、6=50、7=6+? T[23(512448)1]20ns19280ns19.28s ⑸超標(biāo)量處理機(jī) 同一時(shí)鐘周期可以有一條乘法指令和一條加法指令同時(shí)發(fā)射，對于乘法運(yùn)算不存在數(shù)據(jù)相關(guān)性，對于加法運(yùn)算有數(shù)據(jù)相關(guān)性，由于存在足夠的緩沖寄存器,當(dāng)運(yùn)算完所有的乘法運(yùn)算后，還要做一次加法運(yùn)算。因此執(zhí)行時(shí)間為: 加3 加加2 法力口1 123456712345?? 1 23

26、456789 10111213141516171819202122 1=? +@、2=1鉉、3=2位、 4=3+⑤、5=4喳、6=5+0、7=6+@ T[23(5121)3]20ns10380ns10.38s (6)超流水線處理機(jī) 每個(gè)時(shí)鐘周期發(fā)射兩條指令，加法部件和乘法部件都為6個(gè)流水級(jí)。事實(shí)上相當(dāng)于將時(shí)鐘周期變成了10ns,而加法和乘法流水線變成了6級(jí)。因此執(zhí)行時(shí)問為： T[46(512448)1]10ns9690ns9.69s ⑺超標(biāo)量超流水線處理機(jī) 一個(gè)時(shí)鐘周期分為兩個(gè)流水級(jí)，加法部件和乘法部件都為6個(gè)流水級(jí)，每個(gè)流水級(jí)能同時(shí)發(fā)射一條加法和一條乘法指令。綜合⑸和⑹的分析，我們可以知道，執(zhí)行時(shí)間為： T[46(5121)6]10ns5270ns5.27s