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

1、1. 假設(shè)一條指令的執(zhí)行過程分為“取指令”、“分析”和“執(zhí)行”三段，每一 段的時(shí)間分別是 t、24t和34t。在下列各種情況下，分別寫出連續(xù)執(zhí)行n條指令所需要的時(shí)間表達(dá)式。順序執(zhí)行方式。 僅“取指令”和“執(zhí)行”重疊。 “取指令”、“分析”和“執(zhí)行”重疊答：順序執(zhí)行方式 TOC o 1-5 h z 121212 t27.n 3AtT=(t取址i t分析i 匕丸行1)=n( A + 2A + 3A) =6nAi 1 僅“取指令”和“執(zhí)行”重疊 TOC o 1-5 h z 12121 )2 t_2n3At 一T= 6At +(t分析it執(zhí)行i)=64t + (n-1)(2 At +3At) =(5n

2、 + 1)Ati 1i 1. 一條線性流水線有4個(gè)功能段組成，每個(gè)功能段的延遲時(shí)間都相等，都為 to開始5個(gè)任務(wù)，每間隔一個(gè) t向流水線輸入一個(gè)任務(wù)，然后停頓 2個(gè)如此重復(fù)。求流水線的實(shí)際吞吐率、加速比和效率123456789 10 11 12 13 14 15 16 17 18 19 20 21 22 23我們可以看出，在（7n+1） At的時(shí)間內(nèi)，可以輸出5n個(gè)結(jié)果，如果指令的 序列足夠長（n一8）,并且指令間不存在相關(guān)，那么，吞吐率可以認(rèn)為滿足：加速比為：從上面的時(shí)空圖很容易看出，效率為：10.用一條5個(gè)功能段的浮點(diǎn)加法器流水線計(jì)算 F Ai o每個(gè)功能段的延遲 i 1時(shí)間均相等，流水線

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

4、A8I5:R5-A9+A10I6:R6-R1+R2I7:R7-R3+R4I8:R8-R5+R6I9:FR7+R8這并不是唯一可能的計(jì)算方法。假設(shè)功能段的延遲為AtoI5:R5-A9+A10I6:R6-R1+R2I7:R7-R3+R4I8:R8-R5+R6I9:FR7+R8這并不是唯一可能的計(jì)算方法。假設(shè)功能段的延遲為Ato時(shí)空圖如下（圖2345678910 11 12 13 14 15 16 17 18 19 20 21整個(gè)計(jì)算過程需要21 At,所以吞吐率為:加速比為:效率為:4.B,一條線性靜態(tài)多功能流水線由6個(gè)功能段組成，加法操作使用其中的1、2、4.B,3、6功能段，乘法操作使用其中的

5、1、4、5、6功能段，每個(gè)功能段的延遲時(shí)間均相等。流水線的輸出端與輸入端之間有直接數(shù)據(jù)通路，而且設(shè)置有足夠的緩沖寄存器。用這條流水線計(jì)算向量點(diǎn)積 A B ai bi ,畫出流水線時(shí)空圖，計(jì)算流水線的實(shí)際吞吐率、加速比和效率。我們安排運(yùn)算次序如下：把中間結(jié)果寄存器稱為R,源操作數(shù)寄存器稱為A、 最后結(jié)果寄存器稱為F,并假設(shè)源操作數(shù)已經(jīng)在寄存器中，則指令如下:I1:R0A0*B0I8:R7- R0+R1I2:R1A1*B1I9:R8-R2+R3I3:R2A2*B2I10:R9- R4+R5I4:R3A3*B3I11 :R10-R6+R7I5 :R4A4*B4R11R8+R9I5 :R4A4*B4R

6、11R8+R9I6 :R5A5*B5I7 :R6A6*B6FR10+R11假設(shè)功能段白延遲為A to時(shí)空圖如下（圖中的數(shù)字是指令號(hào)）138138123456789 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24整個(gè)計(jì)算過程需要24 A t,所以吞吐率為:加速比為：效率為：5. 一條有三個(gè)功能段的流水線如下圖。每個(gè)功能段的延遲時(shí)間均相等，都為to其中功能段S2的輸出要返回到它自己的輸入端循環(huán)一次。輸出輸入輸出S1SS1S2S3如果每間隔一個(gè) t向流水線的輸入端連續(xù)輸入新任務(wù)，問這條流水線會(huì)發(fā)生什么情況?求這條流水線能夠正常工作的最大吞吐率、加速比和效率。

7、有什么辦法能夠提高這條流水線的吞吐率，畫出新的流水線。答：如果每間隔一個(gè) t向流水線的輸入端連續(xù)輸入新任務(wù)，流水線S2功能段存S1X1X2X3X4X5S2X1X1, X2X2 ,X3X3,X4S3X1X2每間隔兩個(gè)t向流水線的輸入端連續(xù)輸入新任務(wù)（如見下表所示）可獲得最佳性能。我們可以看出：在（2n+2） At的時(shí)間內(nèi)，可以輸出n個(gè)結(jié)果，如果指令的 序列足夠長（n一8）,并且指令間不存在相關(guān)，那么，吞吐率為：加速比為:效率為:圖:如要提高這條流水線的吞吐率，可采用：將功能段S2重復(fù)設(shè)置一次，見下輸入叵圖:如要提高這條流水線的吞吐率，可采用：將功能段S2重復(fù)設(shè)置一次，見下輸入叵t6.一條有4個(gè)功

8、能段的非線性流水線，每個(gè)功能段的延遲時(shí)間都相等，都為6.20ns,它的預(yù)約表如下：流水徽、1234567S1XXS2XXS3XS4XX寫出流水線的禁止向量和初始沖突向量 畫出調(diào)度流水線的狀態(tài)圖。求流水線的最小啟動(dòng)循環(huán)和最小平均啟動(dòng)距離。 求平均啟動(dòng)距離最小的恒定循環(huán)。求流水線的最大吞吐率。(6)按照最小啟動(dòng)循環(huán)連續(xù)輸入10個(gè)任務(wù)，求流水線的實(shí)際吞吐率 畫出該流水線各功能段之間的連接圖。答：禁止向量F= (6,4,2);沖突向量 C= (101010)。C0i101010降7C3i=5i7101011i 7i=3i=5=5i=310111C1i=1C211111C0i101010降7C3i=5i

9、7101011i 7i=3i=5=5i=310111C1i=1C2111111 , 7 (C0-C1-C0)43, 7 (C0-C2-C0)55, 7 (C0-C3-C0)63, 5, 7 (C0-C2-C3-C0)53, 5 (C0-C2-C3-C2-C3)45, 3, 7 (C0-C3-C2-C0)55, 3 (C0-C3-C2-C3-C2)45 (C0-C3-C3)57 (C0-C0)7流水線的最小啟動(dòng)循環(huán)為：（1, 7）或（3, 5）或（5, 3）,最小平均啟動(dòng)距 離為4。由上表可知：平均啟動(dòng)距離最小的恒定循環(huán)為（5）。采用最小平均啟動(dòng)距離為4的最小啟動(dòng)循環(huán)可獲得流水線的最大吞吐率，以

10、（1, 7）為例：（其他類似，最大吞吐率皆相同）當(dāng)任務(wù)數(shù)為偶數(shù)2n時(shí)：當(dāng)任務(wù)數(shù)為奇數(shù)2n+1時(shí)： 流水線的最大吞吐率為： 1一 12.5M（任務(wù)/s）4 t 4 20ns（6）10個(gè)任務(wù)的實(shí)際吞吐率：利用上式可得（偶數(shù)個(gè)任務(wù)）TP10=1/4At=12.5M（任務(wù)/s）。該流水線的連接圖為：輸出一條由4個(gè)功能段組輸入一條由4個(gè)功能段組輸入1 S2 _S3 二 S4 5寸問 流水亂123456S1XXS2XXS3XS4XX74成的非線性流水線的預(yù)約表如下，每個(gè)功能段的延遲時(shí)間都為10ns寫出流水線的禁止向量和初始沖突向量 畫出調(diào)度流水線的狀態(tài)圖求流水線的最小啟動(dòng)循環(huán)和最小平均啟動(dòng)距離。在流水線中

11、插入一個(gè)非計(jì)算延遲功能段后，求該流水線的最佳啟動(dòng)循環(huán)及其 最小平均啟動(dòng)距離。 畫出插入一個(gè)非計(jì)算延遲功能段后的流水線預(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）334466最小啟動(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）。功能小、12345678S1XXS2XX

12、S3XS4XXDXX流水線的禁止向量為（1, 3, 7）,流水線的沖突向量為1000101, 流水線的狀態(tài)圖如下：C010001013i=2i=4,6i C010001013i=2C1C14(C0-C0)4i=j6(C0-C0)65(C0-C2-C2)55, 4(C0-C2)4.55, 6(C0-C2)5.510101011-C1)i=4,6 i 81000111流水線的最小啟動(dòng)循環(huán)為（2）,最小平均啟動(dòng)距離為2插入前:插入后:連續(xù)卒&入10個(gè)任務(wù)，插入前的實(shí)際吞吐率為：連續(xù)卒&入10個(gè)任務(wù)，插入后的實(shí)際吞吐率為：在流水線處理機(jī)中，有獨(dú)立的加法操作部件和乘法操作部件各一個(gè)，加法 操作部件為4段

13、流水線，乘法操作部件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)? Read After加法寫。原因：還沒有寫好就已經(jīng)讀取寄存器中的數(shù)據(jù)了。 TOC o 1-5 h z DADD R1,R2,R3;(R2)+(R3)( R1)DSUB R4,R1,R5;(R1)(R5)( R4)? Read After乘法寫。原因：還沒有寫好已經(jīng)讀取寄存器中

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

15、的方法是：寄存器換名?！跋茸x后寫”(WAR)相關(guān)Write After任何讀。原因：前面的讀操作因?yàn)槟撤N原因被推遲，要讀的內(nèi) 容被后面的寫操作修改了。DSUB R4,R1,R5; (R1) ( R5) ( R4)DADD R1,R2,R3; (R2) + ( R3) ( R1)本相關(guān)只有在流水線亂序執(zhí)行時(shí)才可能發(fā)生。解決的方法是：寄存器換名。在下列不同結(jié)構(gòu)的處理機(jī)上運(yùn)行 8X8的矩陣乘法C=AXB,計(jì)算所需要的最短時(shí)間。只計(jì)算乘法指令和加法指令的執(zhí)行時(shí)間，不計(jì)算取操作數(shù)、數(shù) 據(jù)傳送和程序控制等指令的執(zhí)行時(shí)間。加法部件和乘法部件的延遲時(shí)間都 是3個(gè)時(shí)鐘周期，另外，加法指令和乘法指令還要經(jīng)過一個(gè)“

16、取指令”和“指令譯碼”的時(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è)功能段。 多操作部件處理機(jī)，處理機(jī)內(nèi)有獨(dú)立的乘法部件和加法部件， 兩個(gè)操作部件 可以并行工作。只有一個(gè)指令流水線，操作部件不采用流水線結(jié)構(gòu)。 單流水線標(biāo)量處理機(jī)，處理機(jī)內(nèi)有兩條獨(dú)立的操作流水線，流水線每個(gè)功能 段的延遲時(shí)間均為一個(gè)時(shí)鐘周

17、期。 超標(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í)，加法部件和乘法 部件延遲時(shí)間都為6個(gè)流水級(jí)，每個(gè)流水級(jí)能夠同時(shí)發(fā)射一條乘法指令和 一條加法指令。答：要完成上面的矩陣乘法，需要完成的乘法數(shù)目為8X8X8=512次；需要完成的加法數(shù)目為8 X 8 X 7=448次;下面分析處理機(jī)的結(jié)構(gòu)會(huì)給

18、性能帶來什么樣的影 響。通用操作部件采用順序方式執(zhí)行順序執(zhí)行時(shí)，每個(gè)乘法和加法指令都需要5個(gè)時(shí)鐘周期（取指令、指令分析、 指令執(zhí)行）；所以所需要的時(shí)間為： 單流水線標(biāo)量處理機(jī)，有一條兩個(gè)功能的靜態(tài)流水線因?yàn)橛凶銐虻木彌_寄存器，所以我們可以首先把所有的乘法計(jì)算完， 并通過 調(diào)度使加法流水線不出現(xiàn)停頓，所以所需要的時(shí)間為：加加 31 2 3 4 法力口 212 3 4譯碼 取指法力口 212 3 4譯碼 取指12 3 41 2 3 4 513 514 515 516 517 518963 964 965 9661= +、2=1鉉、3=2+-、4=3短、5=4喳、6=50、7=6+ 多操作部件處理機(jī)，只有一條指令流水線由于只有一條指令流水線，所以只能一個(gè)時(shí)鐘周期發(fā)射一條指令；由于操作 部件不采用流水線，對于結(jié)果 C矩陣的第一個(gè)元素，首先執(zhí)行 2次乘法，然后 乘法和加法并行執(zhí)行7次，此時(shí)C矩陣的第一個(gè)元素出來了，然后加法運(yùn)算停 頓3個(gè)時(shí)鐘周期，再開始與乘法并行執(zhí)行運(yùn)算 7次，如此下去，直到C的64個(gè) 元素都出來。故執(zhí)行時(shí)間為： 單流水線標(biāo)量處理機(jī)，處理機(jī)內(nèi)有兩條獨(dú)立的操作流水線由于只有一條指令流水線，所以只能一個(gè)時(shí)鐘周期發(fā)射一條指令；對于乘法 運(yùn)算不存在數(shù)據(jù)相