1、1. 假設(shè)一條指令的執(zhí)行過(guò)程分為“取指令” 、 “分析”和“執(zhí)行”三段，每一 段的時(shí)間分別是t、2t 和 3t。在下列各種情況下，分別寫出連續(xù)執(zhí)行 n條指令所需要的時(shí)間表達(dá)式。 順序執(zhí)行方式。 僅“取指令”和“執(zhí)行”重疊。 “取指令” 、 “分析”和“執(zhí)行”重疊。 答： 順序執(zhí)行方式 1 2 . 1 2 1 2 T n 1i iii )ttt ( 執(zhí)行分析取址 n(t2t3t)6nt 僅“取指令”和“執(zhí)行”重疊 1 2 . 1 2 1 2 T6t 1 -n 1i ii )tt ( 執(zhí)行分析 6t(n-1)(2t3t)(5n1)t “取指令” 、 “分析”和“執(zhí)行”重疊 1 2 3 4 . 1

2、2 3 4 1 2 3 4 t 2t 3t t 2t 3t t 2t 3t T6t 1 -n 1i i) t ( 執(zhí)行 6t(n-1)(3t)(3n3)t 2. 一條線性流水線有 4 個(gè)功能段組成，每個(gè)功能段的延遲時(shí)間都相等，都為 t。開始 5 個(gè)任務(wù)，每間隔一個(gè)t 向流水線輸入一個(gè)任務(wù)，然后停頓 2 個(gè)t，如此重復(fù)。求流水線的實(shí)際吞吐率、加速比和效率。 答： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 . 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 2 3 4

3、5 6 7 8 9 10 11 12 13 14 15 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 我們可以看出，在（7n+1）t 的時(shí)間內(nèi)，可以輸出 5n個(gè)結(jié)果，如果指令的 序列足夠長(zhǎng)（n） ，并且指令間不存在相關(guān)，那么，吞吐率可以認(rèn)為滿足： )n( t7 5 t)n/17( 5 t) 1n7( n5 TP 加速比為： )n( 7 20 n/17 20 1n7 n20 t) 1n7( t4n5 S 從上面的時(shí)空?qǐng)D很容易看出，效率為： )n( 7 5 n/17 5 1n7 n5 t) 1n7(4 t4n5 E 3. 用

4、一條 5 個(gè)功能段的浮點(diǎn)加法器流水線計(jì)算 10 1i i AF。每個(gè)功能段的延遲 時(shí)間均相等，流水線的輸出端與輸入端之間有直接數(shù)據(jù)通路，而且設(shè)置有 足夠的緩沖寄存器。要求用盡可能短的時(shí)間完成計(jì)算，畫出流水線時(shí)空?qǐng)D， 計(jì)算流水線的實(shí)際吞吐率、加速比和效率。 答： 首先需要考慮的是“10 個(gè)數(shù)的和最少需要做幾次加法？” ，我們可以發(fā)現(xiàn)， 加法的次數(shù)是不能減少的：9 次；于是我們要盡可能快的完成任務(wù)，就只有考慮 如何讓流水線盡可能充滿，這需要消除前后指令之間的相關(guān)。由于加法滿足交換 律和結(jié)合律，我們可以調(diào)整運(yùn)算次序如以下的指令序列，我們把中間結(jié)果寄存器 稱為 R，源操作數(shù)寄存器稱為 A，最后結(jié)果寄存

5、器稱為 F，并假設(shè)源操作數(shù)已經(jīng) 在寄存器中，則指令如下： I1： R1A1+A2 I2： R2A3+A4 I3： R3A5+A6 I4： R4A7+A8 I5： R5A9+A10 I6： R6R1+R2 I7： R7R3+R4 I8： R8R5+R6 I9： FR7+R8 這并不是唯一可能的計(jì)算方法。假設(shè)功能段的延遲為t。時(shí)空?qǐng)D如下（圖 中的數(shù)字是指令號(hào)） ： 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 10 11 12 1

6、3 14 15 16 17 18 19 20 21 整個(gè)計(jì)算過(guò)程需要 21t，所以吞吐率為： t 43. 0 t7 3 t21 9 TP 加速比為： 1429. 2 7 15 t21 t59 S 效率為： 43. 0 7 3 t215 t59 E 4. 一條線性靜態(tài)多功能流水線由 6 個(gè)功能段組成，加法操作使用其中的 1、2、 3、6 功能段，乘法操作使用其中的 1、4、5、6 功能段，每個(gè)功能段的延遲 時(shí)間均相等。流水線的輸出端與輸入端之間有直接數(shù)據(jù)通路，而且設(shè)置有 足夠的緩沖寄存器。用這條流水線計(jì)算向量點(diǎn)積 i 6 0i i baBA ，畫出流 水線時(shí)空?qǐng)D，計(jì)算流水線的實(shí)際吞吐率、加速比和

7、效率。 答： 我們安排運(yùn)算次序如下： 把中間結(jié)果寄存器稱為 R， 源操作數(shù)寄存器稱為 A、 B，最后結(jié)果寄存器稱為 F，并假設(shè)源操作數(shù)已經(jīng)在寄存器中，則指令如下： I1： R0A0*B0 I8： R7R0+R1 I2： R1A1*B1 I9： R8R2+R3 I3： R2A2*B2 I10： R9R4+R5 I4： R3A3*B3 I11： R10R6+R7 I5： R4A4*B4 I12： R11R8+R9 I6： R5A5*B5 I13： FR10+R11 I7： R6A6*B6 假設(shè)功能段的延遲為t。時(shí)空?qǐng)D如下（圖中的數(shù)字是指令號(hào)） ： 1 2 3 4 5 6 7 8 9 10 11 1

8、2 13 1 2 3 4 5 6 7 1 2 3 4 5 6 7 8 9 10 11 12 13 8 9 10 11 12 13 1 2 3 4 5 6 7 8 9 10 11 12 13 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 整個(gè)計(jì)算過(guò)程需要 24t，所以吞吐率為： t 54. 0 t24 13 TP 加速比為： 17. 2 6 13 t24 t46t47 S 效率為： 36. 0 36 13 t246 t134 E 5. 一條有三個(gè)功能段的流水線如下圖。每個(gè)功能段的延遲時(shí)間均相等，都為 t。其中功能段

9、S2的輸出要返回到它自己的輸入端循環(huán)一次。 如果每間隔一個(gè)t 向流水線的輸入端連續(xù)輸入新任務(wù)，問(wèn)這條流水線會(huì)發(fā) 生什么情況？ 求這條流水線能夠正常工作的最大吞吐率、加速比和效率。 有什么辦法能夠提高這條流水線的吞吐率，畫出新的流水線。 答： 如果每間隔一個(gè)t 向流水線的輸入端連續(xù)輸入新任務(wù)， 流水線 S2 功能段存 在資源沖突。見(jiàn)下表： 時(shí)間 功能段 t1 t2 t3 t4 t5 S1 X1 X2 X3 X4 X5 S2 X1 X1,X2 X2,X3 X3,X4 S3 X1 X2 每間隔兩個(gè)t 向流水線的輸入端連續(xù)輸入新任務(wù)（如見(jiàn)下表所示）可獲得 最佳性能。 S1 S2 S3 輸入 輸出 t

10、t t 時(shí)間 功能段 t1 t2 t3 t4 t5 t6 S1 X1 X2 X3 S2 X1 X1 X2 X2 X3 S3 X1 X2 我們可以看出：在（2n+2）t 的時(shí)間內(nèi)，可以輸出 n個(gè)結(jié)果，如果指令的 序列足夠長(zhǎng)（n） ，并且指令間不存在相關(guān)，那么，吞吐率為： )n( t2 1 t)n/22( 1 t)2n2( n TP 加速比為： )n(2 n/11 2 1n n2 t)2n2( t4n S 效率為： )n( 3 2 n/33 2 3n3 n2 t)2n2(3 t4n E 如要提高這條流水線的吞吐率，可采用：將功能段 S2 重復(fù)設(shè)置一次，見(jiàn)下 圖： 6. 一條有 4 個(gè)功能段的非線性

11、流水線，每個(gè)功能段的延遲時(shí)間都相等，都為 20ns，它的預(yù)約表如下： 時(shí)間 流水段 1 2 3 4 5 6 7 S1 S2 S3 S4 S1 S2 S2 輸入 t t t S3 輸出 t 寫出流水線的禁止向量和初始沖突向量。 畫出調(diào)度流水線的狀態(tài)圖。 求流水線的最小啟動(dòng)循環(huán)和最小平均啟動(dòng)距離。 求平均啟動(dòng)距離最小的恒定循環(huán)。 求流水線的最大吞吐率。 按照最小啟動(dòng)循環(huán)連續(xù)輸入 10 個(gè)任務(wù)，求流水線的實(shí)際吞吐率。 畫出該流水線各功能段之間的連接圖。 答： 禁止向量 F=（6,4,2） ；沖突向量 C=（101010） 。 簡(jiǎn)單循環(huán) 平均啟動(dòng)距離 1 1，7 7（C0C0- -C1C1- -C0C

12、0） 4 4 3 3，7 7（C0C0- -C2C2- -C0C0） 5 5 5 5，7 7（C0C0- -C C3 3- -C0C0） 6 6 3 3，5 5，7 7（C0C0- -C2C2- -C3C3- -C0C0） 5 5 3 3，5 5（C0C0- -C C2 2- -C3C3- -C2C2- -C3C3） 4 4 5 5，3 3，7 7（C0C0- -C C3 3- -C C2 2- -C0C0） 5 5 5 5，3 3（C0C0- -C3C3- -C C2 2- -C C3 3- -C2C2） 4 4 5 5（C0C0- -C C3 3- -C C3 3） 5 5 i=1 i7

13、i=3 i7 i=5 i=3 i7 i=5 i=5 i7 101010 111111 101111 101011 C0 C1 C2 C3 7 7（C0C0- -C C0 0） 7 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）為例： （其他類似，最大吞吐率皆相同） 當(dāng)任務(wù)數(shù)為偶數(shù) 2n時(shí)： )n( t4 1 tn8 n2 t7) 1n(tnt7 n2 TP 當(dāng)任務(wù)數(shù)為奇數(shù) 2n+1 時(shí)： )n( t4 1 n/

14、 t7t8 n/12 t7tn8 1n2 t7ntnt7 1n2 TP 流水線的最大吞吐率為：) s/(M5 .12 ns204 1 t4 1 任務(wù) 10 個(gè)任務(wù)的實(shí)際吞吐率： 利用上式可得 （偶數(shù)個(gè)任務(wù)） TP10=1/4t=12.5M(任 務(wù)/s)。 該流水線的連接圖為： 7. 一條由 4 個(gè)功能段組成的非線性流水線的預(yù)約表如下，每個(gè)功能段的延遲 時(shí)間都為 10ns。 時(shí)間 流水段 1 2 3 4 5 6 S1 S1 S2 S3 S4 1 2 3 4 5 6 7 輸入 輸出 S2 S3 S4 寫出流水線的禁止向量和初始沖突向量。 畫出調(diào)度流水線的狀態(tài)圖。 求流水線的最小啟動(dòng)循環(huán)和最小平均啟

15、動(dòng)距離。 在流水線中插入一個(gè)非計(jì)算延遲功能段后， 求該流水線的最佳啟動(dòng)循環(huán)及其 最小平均啟動(dòng)距離。 畫出插入一個(gè)非計(jì)算延遲功能段后的流水線預(yù)約表（5 行 8 列） 。 畫出插入一個(gè)非計(jì)算延遲功能段后的流水線狀態(tài)變換圖。 分別計(jì)算在插入一個(gè)非計(jì)算延遲功能段前、后的最大吞吐率。 如果連續(xù)輸入 10 個(gè)任務(wù)，分別計(jì)算在插入一個(gè)非計(jì)算延遲功能段前、后的 實(shí)際吞吐率。 答： 禁止向量 F=（5,2,1） ；沖突向量 C=（10011） 。 簡(jiǎn)單循環(huán) 平均啟動(dòng)距離 3 3 3 3 4 4 4 4 6 6 6 6 最小啟動(dòng)循環(huán)為（3） ，最小平均啟動(dòng)距離為 3。 插入一個(gè)非計(jì)算延遲功能段后，最小平均啟動(dòng)距離

16、為 2（因?yàn)轭A(yù)約表中每行 至多 2 個(gè)） ，相應(yīng)地可改進(jìn)最小啟動(dòng)循環(huán)為（2） 。 10011 i=3 i=4 C0 i6 時(shí)間時(shí)間 功能段功能段 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 S1S1 X X S2S2 X X S3S3 X S4S4 X X D D X X X X 流水線的禁止向量為（1，3，7） ，流水線的沖突向量為 1000101， 流水線的狀態(tài)圖如下： 簡(jiǎn)單循環(huán)簡(jiǎn)單循環(huán) 平均啟動(dòng)距離平均啟動(dòng)距離 2，4(C0-C1) 3 2，6(C0-C1) 4 2 2(C0(C0- -C1C1- -C1)C1) 2 2 4(C0-C0) 4 6(C0-C0) 6 5

17、(C0-C2-C2) 5 5，4(C0-C2) 4.5 5，6(C0-C2) 5.5 流水線的最小啟動(dòng)循環(huán)為（2） ，最小平均啟動(dòng)距離為 2。 插入前： 1000101 1010101 1000111 i=4,6 i8 i=4,6 i8 i=4,6 i8 i=2 i=2 i=5 C0 C1 C2 i=5 ) s/(1033. 3 ns103 1 t3 1 t3) 1n(t6 n TP 7 n maxlim 任務(wù)數(shù) 插入后： ) s/(105 ns102 1 t2 1 t2) 1n(t6 n TP 7 n maxlim 任務(wù)數(shù) 連續(xù)輸入 10 個(gè)任務(wù)，插入前的實(shí)際吞吐率為： ) s/(1003.

18、 3 ns1033 10 t33 10 t39t6 10 TP 7 任務(wù)數(shù) 連續(xù)輸入 10 個(gè)任務(wù)，插入后的實(shí)際吞吐率為： ) s/(1085. 3 ns1026 10 t26 10 t29t8 10 TP 7 任務(wù)數(shù) 8. 在流水線處理機(jī)中，有獨(dú)立的加法操作部件和乘法操作部件各一個(gè)，加法 操作部件為 4 段流水線，乘法操作部件 6 段流水線，都在第一段從通用寄 存器讀操作數(shù)，在最后一段把運(yùn)算結(jié)果寫到通用寄存器中。每段的時(shí)間長(zhǎng) 度都相等，都是一個(gè)時(shí)鐘周期。每個(gè)時(shí)鐘周期發(fā)出一條指令。問(wèn)可能發(fā)生 哪幾種數(shù)據(jù)相關(guān)?寫出發(fā)生相關(guān)的指令序列，分析相關(guān)發(fā)生的原因，并給出 解決相關(guān)的具體辦法。 答： 可能的

19、數(shù)據(jù)相關(guān)性有： “先寫后讀” （RAW）相關(guān) Read After 加法寫加法寫。原因：還沒(méi)有寫好就已經(jīng)讀取寄存器中的數(shù)據(jù)了。 DADD R1,R2,R3 ； （R2）（R3）（R1） DSUB R4,R1,R5 ； （R1）（R5）（R4） Read After 乘法寫乘法寫。原因：還沒(méi)有寫好已經(jīng)讀取寄存器中的數(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)最簡(jiǎn)單的方法；建立寄存 器之間的專用路徑。

20、“寫寫” （WAW）相關(guān) Write After 乘法寫乘法寫。原因：后寫的反而早執(zhí)行（乘法所化的時(shí)間長(zhǎng)，后面 一個(gè)寫任務(wù)反而先完成） ，使最后寫入的內(nèi)容不正確。 DMUL R1,R2,R3 ； （R2）（R3）（R1） DSUB R1,R4,R5 ； （R4）（R5）（R1） 本相關(guān)只有在流水線亂序執(zhí)行時(shí)才可能發(fā)生。解決的方法是：寄存器換名。 “先讀后寫” （WAR）相關(guān) Write After 任何讀任何讀。原因：前面的讀操作因?yàn)槟撤N原因被推遲，要讀的內(nèi) 容被后面的寫操作修改了。 DSUB R4,R1,R5 ； （R1）（R5）（R4） DADD R1,R2,R3 ； （R2）（R3）（R

21、1） 本相關(guān)只有在流水線亂序執(zhí)行時(shí)才可能發(fā)生。解決的方法是：寄存器換名。 9. 在下列不同結(jié)構(gòu)的處理機(jī)上運(yùn)行 88 的矩陣乘法 C=AB，計(jì)算所需要的 最短時(shí)間。只計(jì)算乘法指令和加法指令的執(zhí)行時(shí)間，不計(jì)算取操作數(shù)、數(shù) 據(jù)傳送和程序控制等指令的執(zhí)行時(shí)間。加法部件和乘法部件的延遲時(shí)間都 是 3 個(gè)時(shí)鐘周期，另外，加法指令和乘法指令還要經(jīng)過(guò)一個(gè)“取指令”和 “指令譯碼”的時(shí)鐘周期，每個(gè)時(shí)鐘周期為 20ns，C 的初始值為“0” 。各 操作部件的輸出端有直接數(shù)據(jù)通路連接到有關(guān)操作部件的輸入端，在操作 部件的輸出端設(shè)置有足夠容量的緩沖寄存器。 處理機(jī)內(nèi)只有一個(gè)通用操作部件，采用順序方式執(zhí)行指令。 單流水

22、線標(biāo)量處理機(jī)，有一條兩個(gè)功能的靜態(tài)流水線，流水線每個(gè)功能段的 延遲時(shí)間均為一個(gè)時(shí)鐘周期，加法操作和乘法操作各經(jīng)過(guò) 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è)流水級(jí)，加法部件和乘法部件的 延遲時(shí)間都為 6 個(gè)流水級(jí)

23、，每個(gè)時(shí)鐘周期能夠分時(shí)發(fā)射兩條指令，即每個(gè) 流水級(jí)能夠發(fā)射一條指令。 超標(biāo)量超流水線處理機(jī)，把一個(gè)時(shí)鐘周期分為兩個(gè)流水級(jí)，加法部件和乘法 部件延遲時(shí)間都為 6 個(gè)流水級(jí)，每個(gè)流水級(jí)能夠同時(shí)發(fā)射一條乘法指令和 一條加法指令。 答： 要完成上面的矩陣乘法， 需要完成的乘法數(shù)目為 888=512 次； 需要完成 的加法數(shù)目為 887=448 次； 下面分析處理機(jī)的結(jié)構(gòu)會(huì)給性能帶來(lái)什么樣的影 響。 通用操作部件采用順序方式執(zhí)行 順序執(zhí)行時(shí)， 每個(gè)乘法和加法指令都需要 5 個(gè)時(shí)鐘周期 （取指令、 指令分析、 指令執(zhí)行） ；所以所需要的時(shí)間為： s96ns96000ns205)448512(T 單流水線標(biāo)

24、量處理機(jī)，有一條兩個(gè)功能的靜態(tài)流水線 因?yàn)橛凶銐虻木彌_寄存器，所以我們可以首先把所有的乘法計(jì)算完，并通過(guò) 調(diào)度使加法流水線不出現(xiàn)停頓，所以所需要的時(shí)間為： 加 法 加 3 1 2 3 4 加 2 1 2 3 4 加 1 1 2 3 4 乘 法 乘 3 乘 2 乘 1 譯 碼 1 2 3 4 取 指 1 2 3 4 1 2 3 4 5 6 7 8 513 514 515 516 517 518 963 964 965 966 1=+、2=1+、3=2+、4=3+、5=4+、6=5+、7=6+ s32.19ns20)14483() 15123(2T 多操作部件處理機(jī)，只有一條指令流水線 由于只有一

25、條指令流水線，所以只能一個(gè)時(shí)鐘周期發(fā)射一條指令；由于操作 部件不采用流水線，對(duì)于結(jié)果 C 矩陣的第一個(gè)元素，首先執(zhí)行 2 次乘法，然后 乘法和加法并行執(zhí)行 7 次，此時(shí) C 矩陣的第一個(gè)元素出來(lái)了，然后加法運(yùn)算停 頓 3 個(gè)時(shí)鐘周期，再開始與乘法并行執(zhí)行運(yùn)算 7 次，如此下去，直到 C 的 64 個(gè) 元素都出來(lái)。故執(zhí)行時(shí)間為： s82.30ns30820ns20)733(63)7323(2T 單流水線標(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)。 因此， 最佳情況下的執(zhí)行時(shí)間為： 加 法 加 3 1 2 3 4 5 6 7 加 2 1