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

1.假設(shè)一條指令的執(zhí)行過程分為“取指令”、“分析”和“執(zhí)行”三段，每一段的時(shí)間分別是t、2zt和3Ato在下列各種情況下，分別寫出連續(xù)執(zhí)行n條指令所需要的時(shí)間表達(dá)式。順序執(zhí)行方式。僅“取指令”和“執(zhí)行”重疊?！叭≈噶睢薄ⅰ胺治觥焙汀皥?zhí)行”重疊答：順序執(zhí)行方式121212t2At3AtnT=(t取址it分析it執(zhí)行i)=ngt+2A+3zt)=6nzti1僅“取指令”和“執(zhí)行”重疊2At3Atn-1T=6At+(t分析it執(zhí)行i)=6A+(n-1)(2zt+3zt)=(5n+1)Ai1 t2At3AtT= 6At +n-1(t執(zhí)行i)=6At+(n-1)(341)=(3n+3)Ati12 .一條線性流水線有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) t5(n7 tS（7n 1） t從上面的時(shí)空圖很容易看出,5n 4 t20n7n 1效率為:5nE 4 (7n 1) t 7n 1201/n20/Y(n7 1/n57(n的序列足夠長（n一）,并且指令間不存在相關(guān)，那么，吞吐率可以認(rèn)為滿足:5nTP(7n1)加速比為:103 .用一條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次；于是我們要盡可能快的完成任務(wù)，就只有考慮如何讓流水線盡可能充滿，這需要消除前后指令之間的相關(guān)。由于加法滿足交換律和結(jié)合律，我們可以調(diào)整運(yùn)算次序如以下的指令序列， 我們把中間結(jié)果寄存器稱為R,源操作數(shù)寄存器稱為 A,最后結(jié)果寄存器稱為F,并假設(shè)源操作數(shù)已經(jīng)在寄存器中，則指令如下:11:R1-A1+A212:R2 A3+A413:R3- A5+A614:R4- A7+A815:R-A9+A1016:RA R1+R217:R7- R3+R418:R8- R5+R619:F R7+R8這并不是唯一可能的計(jì)算方法。假設(shè)功能段的延遲為Ato時(shí)空圖如下（圖中的數(shù)字是指令號）：8910 11 12 13 1415 16 17 18 19 20 21整個(gè)計(jì)算過程需要21 At,所以吞吐率為:TP -921 t0.43加速比為:S »21 t152.1429效率為:4.B,9 5 t3E0.435 21 t7一條線性靜態(tài)多功能流水線由6個(gè)功能段組成，加法操作使用其中的1、2、3、6功能段，乘法操作使用其中的1、4、5、6功能段，每個(gè)功能段的延遲時(shí)間均相等。流水線的輸出端與輸入端之間有直接數(shù)據(jù)通路，而且設(shè)置有足夠的緩沖寄存器。用這條流水線計(jì)算向量點(diǎn)積 A B水線時(shí)空圖，計(jì)算流水線的實(shí)際吞吐率、加速比和效率。aibi ,畫出流i 0我們安排運(yùn)算次序如下：把中間結(jié)果寄存器稱為R,源操作數(shù)寄存器稱為A、最后結(jié)果寄存器稱為F,并假設(shè)源操作數(shù)已經(jīng)在寄存器中，則指令如下:11:Rg A0*B0I8:R7- R0+R112:R1A1*B1I9:R8- R2+R313:R2 A2*B2110:RA R4+R5I4:RA A3*B3111:R14 R6+R7I5:R- A4*B4112:R11-R8+R9I6:R5 A5*B5113:FR10+R11I7:RA A6*B6假設(shè)功能段白延遲為A t時(shí)空圖如下（圖中的數(shù)字是指令號）131010111211121310111213123456789101112131415161718192021222324整個(gè)計(jì)算過程需要24At,所以吞吐率為:5.加速比為:效率為:TP130.5424 tc 7 4 t 6 4S 24 t132.176E 4 13 t6 24 t130.3636一條有三個(gè)功能段的流水線如下圖。每個(gè)功能段的延遲時(shí)間均相等，都為to其中功能段S2的輸出要返回到它自己的輸入端循環(huán)一次。于S1S2S3輸出輸入如果每間隔一個(gè)t向流水線的輸入端連續(xù)輸入新任務(wù)，問這條流水線會發(fā)生什么情況求這條流水線能夠正常工作的最大吞吐率、加速比和效率。有什么辦法能夠提高這條流水線的吞吐率，畫出新的流水線。如果每間隔一個(gè)t向流水線的輸入端連續(xù)輸入新任務(wù)，流水線S2功能段存每間隔兩個(gè)t向流水線的輸入端連續(xù)輸入新任務(wù)（如見下表所示）可獲得最佳性能。寸間功能隆、t1t2t3t4t5t6S1X1X2X3S2X1X1X2X2X3S3X1X2我們可以看出：在（2n+2）At的時(shí)間內(nèi)，可以輸出n個(gè)結(jié)果，如果指令的序列足夠長（n一8）,并且指令間不存在相關(guān)，那么，吞吐率為:TPn(2n 2) t1(2 2/n) t(n加速比為:n 4 t(2n 2) t2n 2n 11 1 /n2(n效率為:3 (2n 2) t2n 22, (n3n 3 3 3/n 3圖:如要提高這條流水線的吞吐率，可采用：將功能段S2重復(fù)設(shè)置一次，見下寫出流水線的禁止向量和初始沖突向量 畫出調(diào)度流水線的狀態(tài)圖。6. 一條有4個(gè)功能段的非線性流水線，每個(gè)功能段的延遲時(shí)間都相等，都為流水1234567SXX及XXXXX20ns,它的預(yù)約表如下:0求流水線的最小啟動循環(huán)和最小平均啟動距離求平均啟動距離最小的恒定循環(huán)。求流水線的最大吞吐率。按照最小啟動循環(huán)連續(xù)輸入10個(gè)任務(wù)，求流水線的實(shí)際吞吐率畫出該流水線各功能段之間的連接圖。答：禁止向量F=（6,4,2）;沖突向量C=（101010）。1,7(C0-C1-C043,7(C0-C2-C055,7(C0-C3-C063,5,7(C0-C2-C3-C053,5(C0-C2-C3-C2-。345,3,7(C0-C3-C2-C055,3(C0-C3-C2-C3-。245(C0-C3-C357(C0-CO7流水線的最小啟動循環(huán)為：（1,7）或（3,5）或（5,3）,最小平均啟動距離為4。由上表可知：平均啟動距離最小的恒定循環(huán)為（5）。采用最小平均啟動距離為4的最小啟動循環(huán)可獲得流水線的最大吞吐率,(17）為例：（其他類似，最大吞吐率皆相同）當(dāng)任務(wù)數(shù)為偶數(shù)2n時(shí):TP 2n7 t n t當(dāng)任務(wù)數(shù)為奇數(shù)2n+1時(shí)：(n 1) 7 t2n8n t六(n(6)流水線的最大吞吐率為:2n 18n t 7 t14 t 4 20ns1/n8 t 7 t/n六(n )12.5M(任務(wù) /s)10個(gè)任務(wù)的實(shí)際吞吐率:利用上式可得（偶數(shù)個(gè)任務(wù)）TPio=1/4At=12.5M（任務(wù)。該流水線的連接圖為:輸入S1輸出S2S3S47. 一條由4個(gè)功能段組成的非線性流水線的預(yù)約表如下，每個(gè)功能段的延遲時(shí)間都為10區(qū)寸問流水1123456SiXXS2XXS3X寫出流水線的禁止向量和初始沖突向量。畫出調(diào)度流水線的狀態(tài)圖。求流水線的最小啟動循環(huán)和最小平均啟動距離。在流水線中插入一個(gè)非計(jì)算延遲功能段后，求該流水線的最佳啟動循環(huán)及其最小平均啟動距離。畫出插入一個(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）。i=4i=3334466最小啟動循環(huán)為（3）,最小平均啟動距離為3。插入一個(gè)非計(jì)算延遲功能段后，最小平均啟動距離為2（因?yàn)轭A(yù)約表中每行至多2個(gè)X）,相應(yīng)地可改進(jìn)最小啟動循環(huán)為（2）。12345678S1XXS2XXS3XS4XXDXX（6）流水線的禁止向量為（1, 3, 7）,流水線的沖突向量為1000101, 流水線的狀態(tài)圖如下：2, 4(C0-C1)32, 6(C0-C1)42(C0-C1-C1)24(C0-C0)46(C0-C0)65(C0-C2-C2)55, 4(C0-C2)5, 6(C0-C2)流水線的最小啟動循環(huán)為（2）,最小平均啟動距離為2插入前:TPmax lim 'm' 6 t (n 1) 3 t1一3.33107(任務(wù)數(shù)/s)3t310ns插入后:TPmaxlimn6 t (n 1) 2 t2 10ns5 107(任務(wù)數(shù)/s)連續(xù)卒&入10個(gè)任務(wù)，插入前的實(shí)際吞吐率為：1010107,TP3.03107(任務(wù)數(shù)/s)6t93t33t3310ns連續(xù)卒&入10個(gè)任務(wù)，插入后的實(shí)際吞吐率為：TP108 t 9 2t1010 3.8526 t 26 10ns107(任務(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,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)最簡單的方法；建立寄存器之間的專用路徑?！皩懸粚?quot;(WAW)相關(guān)WriteAfter乘法寫。原因：后寫的反而早執(zhí)行(乘法所化的時(shí)間長，后面一個(gè)寫任務(wù)反而先完成)，使最后寫入的內(nèi)容不正確。DMULR1,R2,R3;(R2)X(R3)(R1)DSUBR1,R4,R5；(R4)(R5)(R1)本相關(guān)只有在流水線亂序執(zhí)行時(shí)才可能發(fā)生。解決的方法是：寄存器換名?！跋茸x后寫”(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ì)算所需要的最短時(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è)功能段。多操作部件處理機(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è)流水級，加法部件和乘法部件的延遲時(shí)間都為6個(gè)流水級，每個(gè)時(shí)鐘周期能夠分時(shí)發(fā)射兩條指令，即每個(gè)流水級能夠發(fā)射一條指令。超標(biāo)量超流水線處理機(jī)，把一個(gè)時(shí)鐘周期分為兩個(gè)流水級，加法部件和乘法部件延遲時(shí)間都為6個(gè)流水級，每個(gè)流水級能夠同時(shí)發(fā)射一條乘法指令和一條加法指令。答：要完成上面的矩陣乘法，需要完成的乘法數(shù)目為8X8X8=512次；需要完成的加法數(shù)目為8X8X7=448次；下面分析處理機(jī)的結(jié)構(gòu)會給性能帶來什么樣的影響。通用操作部件采用順序方式執(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)停頓，所以所需要的時(shí)間為:加3加123412 34123 4加2法力口 1譯碼取指12 3 41 2 3 4 -5135145155165175189639649659661=®+、2=1鉉、3=2短、4=3+、5=4喳、6=50、7=6+®T2(35121)(34481)20ns19.32s多操作部件處理機(jī)，只有一條指令流水線由于只有一條指令流水線，所以只能一個(gè)時(shí)鐘周期發(fā)射一條指令；由于操作部件不采用流水線，對于2果C矩陣的第一個(gè)元素，首先執(zhí)行2次乘法，然后乘法和加法并行執(zhí)行7次，此時(shí)C矩陣的第一個(gè)元素出來了，然后加法運(yùn)算停頓3個(gè)時(shí)鐘周期，再開始與乘法并行執(zhí)行運(yùn)算7次，如此下去，直到C的64個(gè)元素都出來。故執(zhí)行時(shí)間為：T2(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í)間為:123456712345671234567譯碼1234567取指1234567123456789101112131415161718192021221=®+、2=1鉉、3=2短、4=3+、5=4+(©、6=50、7=6+®T23(512448)120ns19280ns19.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法力口1123456712345123456789101112131415161718192021221=® +、2=1鉉、3=2位、4=3+、5=4喳、6=5+0、7=6+T23(5121)320ns10380ns10.38s(6)超流水線處理機(jī)每個(gè)時(shí)鐘周期發(fā)射兩條指令，加法部件和乘法部件都為6個(gè)流水級。事實(shí)上相當(dāng)于將時(shí)鐘周期變成了10ns,而加法和乘法流水線變成了6級。因此執(zhí)行時(shí)問為：T46(512448)110ns9690ns9.69s超標(biāo)量超流水線處理機(jī)一個(gè)時(shí)鐘周期分為兩個(gè)流水級，加法部件和乘法部件都為6個(gè)流水級，每個(gè)流水級能同時(shí)發(fā)射一條加法和一條乘法指令。綜合和的分析，我們可以知道，執(zhí)行時(shí)間為：T46(5121)610ns5270ns5.27s