【正文】 只計算乘法指令和加法指令的執(zhí)行時間，不計算取操作數(shù)、數(shù)據(jù)傳送和程序控制等指令的執(zhí)行時間。(8)插入前TP = 10/33Δt = 1/33ns，插入后TP = 10/26Δt = 1/26ns，如下圖所示。 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)所示。(4)插入2個延遲，最小啟動循環(huán)=（2）,最小平均啟動距離=2Δt。Δt=10ns=108秒(1)F={1，2，5}，C=(10011)(2)狀態(tài)轉(zhuǎn)移圖如下圖(a)所示。(5)畫出插入非計算延遲功能段后的流水線狀態(tài)轉(zhuǎn)換圖。(3)通過插入非計算延遲功能段使該流水線達到最優(yōu)調(diào)度，確定該流水線的最佳啟動循環(huán)及其最小平均啟動距離。時 間功能段 1 2 3 4 56 7 8 91011 121314 151617S1╳△╳3△3S2╳╳△△33S3╳△3S4╳╳△△33一條3個功能段的非線性流水線及其預約表如圖： (1)寫出流水線的禁止向量和初始沖突向量，并畫出調(diào)度流水線的狀態(tài)轉(zhuǎn)換圖。 （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）流水線的最大吞吐率 假設用此流水線完成N個任務（N為偶數(shù)）： TPMAX = N/（N/2*12*△T）=1/（6△T）其中：N/2 *12 表示每執(zhí)行2個任務需要12個△T時間，平均每6個△T完成一個任務。假設用此流水線完成N個任務(N為奇數(shù)):TPMAX = N/ [((N1)/2*12+5)*△T]其中：(N1)/2 *12表示每執(zhí)行2個任務需要12個△T時間，5為最后一個任務多執(zhí)行的周期數(shù)。（2） 畫出該流水線各功能段之間的連接圖。(5)求流水線的最大吞吐率。(3)求流水線的最小啟動循環(huán)和最小平均啟動距離。S1S2S3輸入輸出△t△t△t一條4個功能段的非線性流水線，每個功能段的延遲時間都相等，都為20ns，它的預約表如下： (1)寫出流水線的禁止向量F和初始沖突向量C。（1） 如果每隔一個△t向流水線輸入端連續(xù)輸入新任務，問這條流水線會發(fā)生什么情況？（2） 求這條流水線能夠正常工作的最大吞吐率。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 。整個計算過程需要22Δt，所以吞吐率為：加速比為：效率為：為了縮短運算時間，首先應考慮“最少切換算法”，即先執(zhí)行完所有乘法（任務編號16）再執(zhí)行加法（任務編號711），其次在加法中采用“最少相關算法”（即二叉樹算法）。假設功能段的延遲為Δt?，F(xiàn)在用這條流水線計算：畫出流水線時空圖，并計算流水線的實際吞吐率、加速比和效率。 整個計算過程需要21Δt，所以吞吐率為：加速比為：效率為：一條線性靜態(tài)多功能流水線由6個功能段組成，加法操作使用其中的6功能段，乘法操作使用其中的6功能段，每個功能段的延遲時間均相等。假設功能段的延遲為Δt。我們可以發(fā)現(xiàn)，加法的次數(shù)是不能減少的：9次；于是我們要盡可能快的完成任務，就只有考慮如何讓流水線盡可能充滿，這需要消除前后指令之間的相關。要求用盡可能短的時間完成計算，畫出流水線時空圖，并計算流水線的實際吞吐率、加速比和效率。求流水線的實際吞吐率、加速比和效率。K+2K+1KIFID idleidleRREXEXidleWBIFIDidleidleRREXEXEXWBIFIDRREXWB 1 2 3 4 5 6 7 8 9 10 11一條線性流水線有4個功能段組成，每個功能段的延遲時間都相等，都為Δt。 k ： MOVE R1 ， R0 ； R1←（R0） k+1 ： MUL R0 ， R2 ， R1 ；R0←(R2) (R1) k+2 ： ADD R0 ， R2 ，R3 ； R0← (R2)+ (R3)（1） 就程序本身而言，可能有哪幾種數(shù)據(jù)相關？（2） 在程序?qū)嶋H執(zhí)行過程中，有哪幾種數(shù)據(jù)相關會引起流水線停頓？（3） 畫出指令執(zhí)行過程的流水線時空圖，并計算執(zhí)行完這三條指令共使用了多少各時鐘周期？答：（1）K與K+1 ：先寫后讀相關 K+1與K+2 ：寫寫相關（2） 由流水線時空圖看，K與K+1 ：先寫后讀相關在第4時鐘周期會引起流水線停頓，而K+1與K+2 ：寫寫相關在第8時鐘周期會引起流水線停頓。[解答]順序方式：執(zhí)行n 條指令的時間=n (t取指+t分析+t執(zhí)行)??“執(zhí)行”和“取指”重疊：執(zhí)行n 條指令的時間= t取指+n t分析+ (n1) MAX {t取指, t執(zhí)行} + t執(zhí)行“執(zhí)行”、“分析”和“取指”重疊：執(zhí)行n 條指令的時間= t取指+MAX {t取指, t分析} +(n2) MAX {t取指, t分析, t執(zhí)行} + MAX {t分析, t執(zhí)行} + t執(zhí)行??先行控制：執(zhí)行n 條指令的時間= t取指+ t分析+ n t執(zhí)行（1）順序執(zhí)行需要的時間如下：（2）取指令和執(zhí)行重疊，即一次重疊執(zhí)行方式，我們假設第n+1條指令的取指令和第n條指令的執(zhí)行同時結束，那么所需要的時間為：（3）采用先行控制以后：在一臺單流水線多操作部件上執(zhí)行下面的程序，取指令、指令譯碼各需要一個時鐘周期，MOVE、ADD和MUL操作各需要2個、3個、和4個時鐘周期。（2）僅“取指令”和“執(zhí)行”重疊。在下列各種情況下，分別寫出連續(xù)執(zhí)行n條指令所需要的時間表達式。 (4) 計算此流水線在執(zhí)行8個任務時的吞吐率、加速比和利用率。 (2) 畫出該流水線狀態(tài)圖，確定其最佳調(diào)度方案以及最小平均流水速率。采用預留調(diào)度算法的預約表時 間12345678功能段S1?S2?S3?S4延遲D1注：?表示由D1延遲一個時鐘周期增加了一個非計算延遲流水段D1的流水線連接圖 輸出輸入S1S2S3S4D1有非計算延遲的流水線狀態(tài)圖8１０１0１０08 81 2 4 6 8１１１１１１0１０１0１0１ 12 4 6１１１１１１１按照最小啟動循環(huán)（2）工作的流水線預約表時間123456789101112…功S1X1X2X3X4X1X5X2X6X3…能S2X1X2X3X1X4X2X5X3X5…段S3X1X2X1X3X2X4X3X5X4…S4X1X2X3X4X5…延D1X1X2X3X4…某單功能非線性流水線的預約表如下圖所示。為此，S2行的第2個“”也要向后延遲一個周期，從周期6延遲到周期7；S1行的第2個“”也要向后延遲一個周期，從周期7延遲到周期8。檢查每一行中與第1個“”的距離為2的倍數(shù)的位置都要預留出來。最小啟動循環(huán)(3,5)的流水線工作狀態(tài)時間功能段123456789101112131415…S1X1X2X1X3X2X4X3…S2X1X2X1X2X3X4X3…S3X1X1X2X2X3X3X4…S4X1X2X3X4…啟動周期重復啟動周期最小啟動循環(huán)(1,7)的流水線工作狀態(tài)時間功能段123456789101112131415…S1X1X2X1X2X3X4X3…S2X1X2X1X2X3X4X3X4…S3X1X2X1X2X3X4X3X4…S4X1X2X3X4…啟動周期重復啟動周期恒定啟動循環(huán)(5)的流水線工作狀態(tài)時間功能段123456789101112131415…S1X1X2X1X3X2…S2X1X1X2X2X3…S3X1X1X2X2X3X3…S4X1X2X3…啟動周期重復啟動周期采用預留調(diào)度算法SSS3對應的行有2個“”， 因此，最小平均啟動距離為2。其平均啟動距離為 4。由簡單循環(huán)可以計算出平均啟動距離。 簡單循環(huán)：狀態(tài)圖中各種沖突向量只經(jīng)過一次的啟動循環(huán)。 (0)7(0)中間沖突向量101111右移5位之后：000001v101010=101011 (2)5(3)中間沖突向量101011右移3位之后：000101