【正文】 L R0 ， R2 ， R1 ；R0←(R2) (R1) k+2 ： ADD R0 ， R2 ，R3 ； R0← (R2)+ (R3)（1） 就程序本身而言，可能有哪幾種數(shù)據(jù)相關(guān)？（2） 在程序?qū)嶋H執(zhí)行過程中，有哪幾種數(shù)據(jù)相關(guān)會引起流水線停頓？（3） 畫出指令執(zhí)行過程的流水線時空圖，并計算執(zhí)行完這三條指令共使用了多少各時鐘周期？答：（1）K與K+1 ：先寫后讀相關(guān) K+1與K+2 ：寫寫相關(guān)（2） 由流水線時空圖看，K與K+1 ：先寫后讀相關(guān)在第4時鐘周期會引起流水線停頓，而K+1與K+2 ：寫寫相關(guān)在第8時鐘周期會引起流水線停頓。K+2K+1KIFID RREXEXWB*IFIDRR*EXEXEXWBIFIDRREXWB 1 2 3 4 5 6 7 8 9（3）由流水線時空圖看，共插入了3個時鐘周期的停頓，執(zhí)行完這三條指令共使用了11個時鐘周期。K+2K+1KIFID idleidleRREXEXidleWBIFIDidleidleRREXEXEXWBIFIDRREXWB 1 2 3 4 5 6 7 8 9 10 11一條線性流水線有4個功能段組成，每個功能段的延遲時間都相等，都為Δt。開始5個Δt，每間隔一個Δt向流水線輸入一個任務(wù)，然后停頓2個Δt，如此重復(fù)。求流水線的實際吞吐率、加速比和效率。[解答]流水線的時空圖如下： 我們可以看出，在（11n+1）Δt的時間內(nèi)，可以輸出5n個結(jié)果，如果指令的序列足夠長（n→∞），并且指令間不存在相關(guān)，那么，吞吐率可以認(rèn)為滿足：加速比為：從上面的時空圖很容易看出，效率為：用一條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+A2I2： R2←A3+A4I3： R3←A5+A6I4： R4←A7+A8I5： R5←A9+A10I6： R6←R1+R2I7： R7←R3+R4I8： R8←R5+R6I9： F←R7+R8 這并不是唯一可能的計算方法。假設(shè)功能段的延遲為Δt。時空圖如下，圖中的數(shù)字是指令號。 整個計算過程需要21Δt，所以吞吐率為：加速比為：效率為：一條線性靜態(tài)多功能流水線由6個功能段組成，加法操作使用其中的6功能段，乘法操作使用其中的6功能段，每個功能段的延遲時間均相等。流水線的輸入端與輸出端之間有直接數(shù)據(jù)通路，而且設(shè)置有足夠的緩沖寄存器?，F(xiàn)在用這條流水線計算：畫出流水線時空圖，并計算流水線的實際吞吐率、加速比和效率。為了取得較高的速度，我們需要一次將乘法作完，設(shè)源操作數(shù)存放在寄存器A、B中，中間結(jié)果存放在寄存器R中，最后結(jié)果存放在寄存器F中，則執(zhí)行的指令序列如下所示：I1： R1←A1*B1I2： R2←A2*B2I3： R3←A3*B3I4： R4←A4*B4I5： R5←A5*B5I6： R6←A6*B6I7： R7←R1+R2I8： R8←R3+R4I9： R9←R5+R6I10： R10←R7+R8I11： F←R9+R10這并不是唯一可能的計算方法。假設(shè)功能段的延遲為Δt。時空圖（不完全）如下，圖中的數(shù)字是指令號。整個計算過程需要22Δt，所以吞吐率為：加速比為：效率為：為了縮短運算時間，首先應(yīng)考慮“最少切換算法”，即先執(zhí)行完所有乘法（任務(wù)編號16）再執(zhí)行加法（任務(wù)編號711），其次在加法中采用“最少相關(guān)算法”（即二叉樹算法）。 記c1=A1B1，……，c6=A6B6，下圖(a)是加法的計算順序二叉樹，注意任務(wù)10應(yīng)該用前一級最早完成的任務(wù)7和8的結(jié)果，如果用任務(wù)9的結(jié)果則要推遲1拍啟動，使總時間增加1拍。F=c1+c2+c3+c4+c5+c6 6 1 2 3 4 5 6 7 8 9 10 11 5 1 2 3 4 5 6 7 8 9 4 1 2 3 4 5 6 3 7 8 9 10 11 10 2 7 8 9 10 11 1 1 2 3 4 5 6 7 8 9 10 11 11 0 1 2 3 4 5 6 7 8 9 12 14 15 18 22 (a) (b)根據(jù)時空圖(b)得 TP = 11/(22Δt) = 1/(2Δt) S = (64Δt + 54Δt)/(22Δt) = 2 E = (64Δt + 54Δt)/(622Δt) = 1/3一條有3個功能段的流水線如圖，每個功能段的延遲時間都相等，為△t 。功能段S2的輸出返回到它自己的輸入端循環(huán)一次。（1） 如果每隔一個△t向流水線輸入端連續(xù)輸入新任務(wù)，問這條流水線會發(fā)生什么情況？（2） 求這條流水線能夠正常工作的最大吞吐率。加速比和效率？（3） 有什么辦法能夠提高這條流水線的吞吐率？畫出新的流水線。S1S2S3輸入輸出△t△t△t一條4個功能段的非線性流水線，每個功能段的延遲時間都相等，都為20ns，它的預(yù)約表如下： (1)寫出流水線的禁止向量F和初始沖突向量C。(2)畫出調(diào)度流水線的狀態(tài)圖。(3)求流水線的最小啟動循環(huán)和最小平均啟動距離。(4)求平均啟動距離最小的恒定循環(huán)。(5)求流水線的最大吞吐率。（1） 照最小啟動循環(huán)連續(xù)輸入10個任務(wù)，求流水線的實際吞吐率。（2） 畫出該流水線各功能段之間的連接圖。答：解：(1)禁止向量F=(2，4，6)初始沖突向量C=(101010）(2)狀態(tài)圖(3)簡單循環(huán) 平均啟動距離(1，7) 4(3，7) 5(3，5，7) 5(5，7) 6(5) 5(7) 7最小平均啟動距離4最小啟動循環(huán)(1，7)(4)平均啟動距離最小的恒循環(huán)(5)(5)流水線的最大吞吐率假設(shè)用此流水線完成N個任務(wù)(N為偶數(shù)):TPMAX = N/(N/2*12*△T)=1/(6△T)其中：N/2 *12表示每執(zhí)行2個任務(wù)需要12個△T時間，平均每6個△T完成一個任務(wù)。假設(shè)用此流水線完成N個任務(wù)(N為奇數(shù)):TPMAX = N/ [((N1)/2*12+5)*△T]其中：(N1)/2 *12表示每執(zhí)行2個任務(wù)需要12個△T時間，5為最后一個任務(wù)多執(zhí)行的周期數(shù)。（1）禁止向量：（2，4，6），初始沖突向量： （101010） 。 （2）狀態(tài)圖1010101111111011117*15 1010117*3537*7*（3）簡單循環(huán) 平均啟動距離（1，7） 4（3，7） 5（3，5，7） 5（5，7） 6（5） 5（7） 7最小平均啟動距離 4最小啟動循環(huán) （1，7）（4）平均啟動距離最小的恒循環(huán) （5）（5）流水線的最大吞吐率 假設(shè)用此流水線完成N個任務(wù)（N為偶數(shù)）： TPMAX = N/（N/2*12*△T）=1/（6△T）其中：N/2 *12 表示每執(zhí)行2個任務(wù)需要12個△T時間，平均每6個△T完成一個任務(wù)。假設(shè)用此流水線完成N個任務(wù)（N為奇數(shù)）： TPMAX = N/ [（（N1）/2*12+5）*△T]其中：（N1）/2 *12 表示每執(zhí)行2個任務(wù)需要12個△T時間， 5 為最后一個任務(wù)多執(zhí)行的周期數(shù)。時 間功能段 1 2 3 4 56 7 8 91011 121314 151617S1╳△╳3△3S2╳╳△△33S3╳△3S4╳╳△△33一條3個功能段的非線性流水線及其預(yù)約表如圖： (1)寫出流水線的禁止向量和初始沖突向量，并畫出調(diào)度流水線的狀態(tài)轉(zhuǎn)換圖。(2)求流水線的最小啟動循環(huán)和最小平均啟動距離。(3)通過插入非計算延遲功能段使該流水線達(dá)到最優(yōu)調(diào)度，確定該流水線的最佳啟動循環(huán)及其最小平均啟動距離。(4)畫出插入非計算延遲功能段后的流水線連接圖及其預(yù)約表。(5)畫出插入非計算延遲功能段后的流水線狀態(tài)轉(zhuǎn)換圖。(6)在插入非計算延遲功能段前后，分別計算流水線的最大吞吐率，并計算最大吞吐率改進(jìn)的百分比。Δt=10ns=108秒(1)F={1，2，5}，C=(10011)(2)狀態(tài)轉(zhuǎn)移圖如下圖(a)所示。(3)最小啟動循環(huán)=（3）,最小平均啟動距離=3Δt。(4)插入2個延遲，最小啟動循環(huán)=（2）,最小平均啟動距離=2Δt。(5)新預(yù)約表如下圖(b)所示。 1 2 3 4 5 6 7 8 初態(tài) 4，6，≥8 S1 1 2 初態(tài) 3，4，≥6 S2 1 1 0 0 0 1 0 1 S3 4，6，≥8 4，6，≥8 1 0 0 1 1 S4 1 2 5 D1 1 0 1 0 1 0 1 1 0 0 0 1 1 1 D2 2 5 (a) (b) (c)(6)F={1，3，7}，C=(1000101)，狀態(tài)轉(zhuǎn)移圖如下圖(c)所示。(7)插入前TPmax = 1/3Δt = 1/30ns，插入后TPmax = 1/2Δt = 1/20ns。(8)插入前TP = 10/33Δt = 1/33ns，插入后TP = 10/26Δt = 1/26ns，如下圖所示。 S4 1 1 2 2 3 10 10 S3 1 2 3 ……… 10 S2 1 1 2 2 3 10 10 S1 1 2 1 3 2 10 10 3 t(a) 插入前 93 6 D2 1 2 3 11 D1 1 2 3 4 10 S4 1 1 2 2 3 3 ……… 10 10 S3 1 2 3 4 10 S2 1 2 1 3 2 4 3 5 10 10 S1 1 2 3 4 1 5 2 10 10 2 t(b) 插入后 92 8在下列不同結(jié)構(gòu)的處理機(jī)上運行88的矩陣乘法C=AB，計算所需要的最短時間。只計算乘法指令和加法指令的執(zhí)行時間，不計算取操作數(shù)、數(shù)據(jù)傳送和程序控制等指令的執(zhí)行時間。加法部件和