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

1、1. 假設(shè)一條指令的執(zhí)行過(guò)程分為“取指令”、“分析”和“執(zhí)行”三段，每一段的時(shí)間 分別是2Zt和3Ato在下列各種情況下，分別寫(xiě)出連續(xù)執(zhí)行n條指令所需要的時(shí)間表 達(dá)式。（1）順序執(zhí)行方式。 僅“取指令”和“執(zhí)行”重疊。 “取指令”、“分析”和“執(zhí)行”重疊。 答：（1）順序執(zhí)行方式121212取址i+ t 分析 i + 丫 執(zhí)行 J =n(At + 2At + 3At) =6n2t僅“取指令”和“執(zhí)行”重疊12121I2僅供參考 t2 tT=%t+ 士(t分析i +1執(zhí)行J =6At+ (n-1) (2Zt + 3At) = (5n+l) Ati=l123412341I234t 2Zt3AtT=

2、6At+ 士(t執(zhí)行J =6At+ (n-1) (3At) = (3n+3) At “取指令”、“分析”和“執(zhí)行”重疊2. 一條線性流水線有4個(gè)功能段組成，每個(gè)功能段的延遲時(shí)間都相等，都為At。開(kāi)始5個(gè)任務(wù), 每間隔一個(gè)At向流水線輸入一個(gè)任務(wù)，然后停頓2個(gè)如此重復(fù)。求流水線的實(shí)際吞吐 率、加速比和效率。答:123456789101112131415123456789101112131415 123456789101112131415|1234567891011112131415123 4 5 67 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23我們

3、可以看出，在（7n+l） At的時(shí)間內(nèi)，可以輸出5n個(gè)結(jié)果，如果指令的序列足夠長(zhǎng)（n- g）,并且指令間不存在相關(guān)，那么，吞吐率可以認(rèn)為滿足：加速比為：從上面的時(shí)空?qǐng)D很容易看出，效率為：103. 用一條5個(gè)功能段的浮點(diǎn)加法器流水線計(jì)算F=£a每個(gè)功能段的延遲時(shí)間均相等，流水 i=l線的輸出端與輸入端之間有直接數(shù)據(jù)通路，而且設(shè)置有足夠的緩沖寄存器。要求用盡可能短 的時(shí)間完成計(jì)算，畫(huà)出流水線時(shí)空?qǐng)D，計(jì)算流水線的實(shí)際吞吐率、加速比和效率。答：首先需要考慮的是“10個(gè)數(shù)的和最少需要做幾次加法？ ”，我們可以發(fā)現(xiàn)，加法的次數(shù)是不 能減少的：9次；于是我們要盡可能快的完成任務(wù)，就只有考慮如何讓流

4、水線盡可能充滿，這需要 消除前后指令之間的相關(guān)。由于加法滿足交換律和結(jié)合律，我們可以調(diào)整運(yùn)算次序如以下的指令序 列，我們把中間結(jié)果寄存器稱(chēng)為R,源操作數(shù)寄存器稱(chēng)為A,最后結(jié)果寄存器稱(chēng)為F,并假設(shè)源操 作數(shù)己經(jīng)在寄存器中，則指令如下：11:R1-A1+A212：R2A3+A413：R3-A5+A614：R4A7+A815：R5-A9+A1016：R6-R1+R217：R7-R3+R418：R8-R5+R619：F-R7+R8這并不是唯一可能的計(jì)算方法。假設(shè)功能段的延遲為 to時(shí)空?qǐng)D如下（圖中的數(shù)字是指令號(hào)）:12345678912345678912345678912345678912345678

5、9123456789 10 11 12 13 14 15 16 17 18 19 20 21整個(gè)計(jì)算過(guò)程需要21At,所以吞吐率為：加速比為：效率為：4. 一條線性靜態(tài)多功能流水線由6個(gè)功能段組成，加法操作使用其中的1、2、3、6功能段，乘法操作使用其中的1、4、5、6功能段，每個(gè)功能段的延遲時(shí)間均相等。流水線的輸出端與輸 入端之間有直接數(shù)據(jù)通路，而且設(shè)置有足夠的緩沖寄存器。用這條流水線計(jì)算向量點(diǎn)積6AxB = £；aixb1,畫(huà)出流水線時(shí)空?qǐng)D，計(jì)算流水線的實(shí)際吞吐率、加速比和效率。i=0答：我們安排運(yùn)算次序如下：把中間結(jié)果寄存器稱(chēng)為R,源操作數(shù)寄存器稱(chēng)為A、B,最后結(jié)果寄存 器稱(chēng)為

6、F,并假設(shè)源操作數(shù)己經(jīng)在寄存器中，則指令如下：11：R0-A0*B018：R7-R0+R112：R1-A1*B119：R8-R2+R313：R2A2*B2no：R9-R4+R514：R3-A3*B3Ill:R10-R6+R715：R4A4*B4112：R11-R8+R916：R5-A5*B5113：F-R10+R1117：R6A6*B6假設(shè)功能段的延遲為At。時(shí)空?qǐng)D如下（圖中的數(shù)字是指令號(hào)）:2hl5HI78 9 10123456712345678910111389101112131】23!5!78910111213123 4 5 67 8 9 10 11 12 13 14 15 16 17

7、18 19 20 21 22 23 24整個(gè)計(jì)算過(guò)程需要24 At,所以吞吐率為：加速比為：效率為：5. 一條有三個(gè)功能段的流水線如下圖。每個(gè)功能段的延遲時(shí)間均相等，都為At。其中功能段S：的輸出要返回到它自己的輸入端循環(huán)一次。輸入S1>s2Ss輸出AtAtAt 如果每間隔一個(gè)At向流水線的輸入端連續(xù)輸入新任務(wù)，問(wèn)這條流水線會(huì)發(fā)生什么情況？求這條流水線能夠正常工作的最大吞吐率、加速比和效率。有什么辦法能夠提高這條流水線的吞吐率，畫(huà)出新的流水線。答：(1)如果每間隔一個(gè)At向流水線的輸入端連續(xù)輸入新任務(wù)，流水線S2功能段存在資源沖突。見(jiàn)下表：間tlt2t3t4t5S1XIX2X3X4X5S

8、2XIXI,X2X2,X3X4S3XIX2每間隔兩個(gè)At向流水線的輸入端連續(xù)輸入新任務(wù)(如見(jiàn)下表所示)可獲得最佳性能。打可功自'潑、flt2t3t4t5t6S1XIX2X3S2XIXIX2X2X3S3XIX2我們可以看出：在(2n+2) At的時(shí)間內(nèi)，可以輸出n個(gè)結(jié)果，如果指令的序列足夠長(zhǎng)(n- g),并且指令間不存在相關(guān)，那么，吞吐率為：加速比為：效率為：如亞胃哥這條流水線的吞吐率，可釆用：將功能段S2重復(fù)設(shè)置一次，見(jiàn)下圖：輸入 II lH4>1輸出AtAtAt>間 流 z|1234567s：XXS2XXS3XS4XX6.如下:(1)寫(xiě)出流水線的禁止向量和初始沖突向量。一

9、條有4個(gè)功能段的非線性流水線，每個(gè)功能段的延遲時(shí)間都相等，都為20ns,它的預(yù)約表 畫(huà)出調(diào)度流水線的狀態(tài)圖。求流水線的最小啟動(dòng)循環(huán)和最小平均啟動(dòng)距離。求平均啟動(dòng)距離最小的恒定循環(huán)。求流水線的最大吞吐率。 按照最小啟動(dòng)循環(huán)連續(xù)輸入10個(gè)任務(wù)，求流水線的實(shí)際吞吐率。(7)畫(huà)出該流水線各功能段之間的連接圖。答：禁止向量F二（6,4,2）；沖突向量C二（101010）。簡(jiǎn)單循環(huán)平均啟動(dòng)距離1, 7 (C0-C1-C0)43, 7 (C0-C2-C0)55, 7 (C0-C3-C0)63, 5, 7 (CO-C2-C3-CO)53, 5 (C0-C2-C3-C2-C3)45, 3, 7 (CO-C3-C

10、2-CO)55, 3 (C0-C3-C2-C3-C2)45 (C0-C3-C3)57 (CO-CO)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)可獲得流水線的最大吞吐率，以（1,7）為例：（其 他類(lèi)似，最大吞吐率皆相同）當(dāng)任務(wù)數(shù)為偶數(shù)2n時(shí)：當(dāng)任務(wù)數(shù)為奇數(shù)2n+l時(shí)：° 流水線的最大吞吐率為：= 12.5M（任務(wù)/ s）4At 4 x 20ns(7)7.(7)答:10個(gè)任務(wù)的實(shí)際吞吐率：利用上式可得(偶數(shù)個(gè)任務(wù))TP10=l/4At=12. 5M(任務(wù)/

11、s)。該流水線的連接圖為:輸入輸出一條由4個(gè)功能段組成的非線性流水線的預(yù)約表 如下，每個(gè)功能段的延遲時(shí)間都為10ns。間流7忌123456SiXXS2XXS3Xs.tXX74寫(xiě)出流水線的禁止向量和初始沖突向量。畫(huà)出調(diào)度流水線的狀態(tài)圖。求流水線的最小啟動(dòng)循環(huán)和最小平均啟動(dòng)距離。在流水線中插入一個(gè)非計(jì)算延遲功能段后，求該流水線的最佳啟動(dòng)循環(huán)及其最小平均啟動(dòng)距 離。畫(huà)出插入一個(gè)非計(jì)算延遲功能段后的流水線預(yù)約表(5行8列)。畫(huà)出插入一個(gè)非計(jì)算延遲功能段后的流水線狀態(tài)變換圖。分別計(jì)算在插入一個(gè)非計(jì)算延遲功能段前、后的最大吞吐率。如果連續(xù)輸入10個(gè)任務(wù)，分別計(jì)算在插入一個(gè)非計(jì)算延遲功能段前、后的實(shí)際吞吐率

12、。禁止向量F二(5,2, 1):沖突向量C二(10011) o簡(jiǎn)單循環(huán)平均啟動(dòng)距離最小啟動(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） o時(shí)間功能12345678S1XXS2XXS3XS4XXDXX流水線的禁止向量為（1, 3, 7）,流水線的沖突向量為1000101,流水線的狀態(tài)圖如下：6 (C0-C0)65 (C0-C2-C2)55, 4(C0-C2)4.55, 6(C0-C2)5.5流水線的最小啟動(dòng)循環(huán)為(2),最小平均啟動(dòng)距離為2。(7)插入前：插入后：連續(xù)輸入10個(gè)任務(wù)，插入前的

13、實(shí)際吞吐率為：連續(xù)輸入10個(gè)任務(wù)，插入后的實(shí)際吞吐率為：8. 在流水線處理機(jī)中，有獨(dú)立的加法操作部件和乘法操作部件各一個(gè)，加法操作部件為4段流水線，乘法操作部件6段流水線，都在第一段從通用寄存器讀操作數(shù)，在最后一段把運(yùn)算結(jié) 果寫(xiě)到通用寄存器中。每段的時(shí)間長(zhǎng)度都相等，都是一個(gè)時(shí)鐘周期。每個(gè)時(shí)鐘周期發(fā)出一條 指令。問(wèn)可能發(fā)生哪幾種數(shù)據(jù)相關(guān)?寫(xiě)出發(fā)生相關(guān)的指令序列，分析相關(guān)發(fā)生的原因，并給出 解決相關(guān)的具體辦法。答：可能的數(shù)據(jù)相關(guān)性有：(1) “先寫(xiě)后讀”(RAW)相關(guān)> Read After加法寫(xiě)。原因：還沒(méi)有寫(xiě)好就己經(jīng)讀取寄存器中的數(shù)據(jù)了。DADD R1,R2,R3；(R2)+(R3)(R

14、1)DSUB R4, Rl, R5；(Rl)-(R5)(R4)> Read After乘法寫(xiě)。原因：還沒(méi)有寫(xiě)好己經(jīng)讀取寄存器中的數(shù)據(jù)了。DMUL R1,R2,R3；(R2)X(R3)(R1)DSUB R4, Rl, R5；(R1)-(R5)(R4)本相關(guān)在流水線順序執(zhí)行和亂序執(zhí)行時(shí)都可能發(fā)生。解決的方法是：利用編譯程序調(diào)整指令的 次序方法；延遲執(zhí)行是避免數(shù)據(jù)相關(guān)最簡(jiǎn)單的方法；建立寄存器之間的專(zhuān)用路徑。“寫(xiě)一寫(xiě)”(WAW)相關(guān)Write After乘法寫(xiě)。原因：后寫(xiě)的反而早執(zhí)行(乘法所化的時(shí)間長(zhǎng)，后面一個(gè)寫(xiě)任務(wù)反而 先完成)，使最后寫(xiě)入的內(nèi)容不正確。DMUL R1,R2,R3； (R2)

15、X (R3)(Rl)DSUB R1,R4, R5； (R4) 一 (R5)(Rl)本相關(guān)只有在流水線亂序執(zhí)行時(shí)才可能發(fā)生。解決的方法是：寄存器換名?！跋茸x后寫(xiě)”(WAR)相關(guān)Write After任何讀。原因：前面的讀操作因?yàn)槟撤N原因被推遲，要讀的內(nèi)容被后面的寫(xiě)操 作修改了。DSUB R4, Rl, R5； (R1) - (R5)(R4)DADD R1,R2,R3； (R2) + (R3)(Rl)本相關(guān)只有在流水線亂序執(zhí)行時(shí)才可能發(fā)生。解決的方法是：寄存器換名。9. 在下列不同結(jié)構(gòu)的處理機(jī)上運(yùn)行8X8的矩陣乘法C二AXB,計(jì)算所需要的最短時(shí)間。只計(jì)算乘法指令和加法指令的執(zhí)行時(shí)間，不計(jì)算取操作數(shù)

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

17、流水線，操作部件不采用流水線結(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ā)射一條指令。(7)超標(biāo)量超流水線處理機(jī)，把一個(gè)時(shí)鐘周期分為兩個(gè)流水級(jí)，加法部件和乘法部件延遲時(shí)間都為 6個(gè)流水級(jí)，每個(gè)流水級(jí)能夠同時(shí)發(fā)射一條乘法指令和一條加法指令。答：要完成上面

18、的矩陣乘法，需要完成的乘法數(shù)目為8X8X8=512次；需要完成的加法數(shù)目為8X8X7=448次；下面分析處理機(jī)的結(jié)構(gòu)會(huì)給性能帶來(lái)什么樣的影響。通用操作部件釆用順序方式執(zhí)行順序執(zhí)行時(shí)，每個(gè)乘法和加法指令都需要5個(gè)時(shí)鐘周期（取指令、指令分析、指令執(zhí)行）；所以所需要的時(shí)間為：?jiǎn)瘟魉€標(biāo)量處理機(jī)，有一條兩個(gè)功能的靜態(tài)流水線因?yàn)橛凶銐虻木彌_寄存器，所以我們可以首先把所有的乘法計(jì)算完，并通過(guò)調(diào)度使加法流水線不出現(xiàn)停頓，所以所需要的時(shí)間為：加31 2 3 4 -加加21 2 3 4 -法加11 2 3 4 -乘3乘乘2法乘1譯碼1 2 3 4取指1 2 3 412345678513 514 515 516

19、517 518963 964 965 9661 二+、2二 1+、3=2+®. 4二3+、5=4+©> 6二5+、7二6+多操作部件處理機(jī)，只有一條指令流水線由于只有一條指令流水線，所以只能一個(gè)時(shí)鐘周期發(fā)射一條指令；由于操作部件不釆用流水線, 對(duì)于結(jié)果C矩陣的第一個(gè)元素，首先執(zhí)行2次乘法，然后乘法和加法并行執(zhí)行7次，此時(shí)C矩陣的 第一個(gè)元素出來(lái)了，然后加法運(yùn)算停頓3個(gè)時(shí)鐘周期，再開(kāi)始與乘法并行執(zhí)行運(yùn)算7次，如此下去, 直到C的64個(gè)元素都出來(lái)。故執(zhí)行時(shí)間為：?jiǎn)瘟魉€標(biāo)量處理機(jī)，處理機(jī)內(nèi)有兩條獨(dú)立的操作流水線由于只有一條指令流水線，所以只能一個(gè)時(shí)鐘周期發(fā)射一條指令；對(duì)于乘法運(yùn)算不存在數(shù)據(jù)相 關(guān)，對(duì)于加法運(yùn)算有數(shù)據(jù)相關(guān)，由于存在足夠的緩沖寄存器，我們可以通過(guò)合適的調(diào)度消除加法的 數(shù)據(jù)相關(guān)。因此