1

P108
有一條動態多功能流水線由5段組成(如圖3.35所示),加法用1、3、4、5段,乘法用1、2、5段,第2段的時間為2△t,其余各段的時間均為△t,而且流水線的輸出可以直接返回輸入端或暫存于相應的流水寄存器中。若在該流水線上計算${\sum }_i^4(A_i\times B_i)$,試計算其吞吐率、加速比和效率。

解：首先以表格形式給出時空圖
計算過程為先計算所有乘法，再計算$A_1\times B_1+A_2\times B_2$，再計算 $A_3\times B_3+A_4\times B_4$，最后相加

時鐘周期	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
段1	$\times$		$\times$		$\times$		$\times$	$+$			$+$				$+$
段2		$\times$	$\times$	$\times$	$\times$	$\times$	$\times$	$\times$	$\times$
段3									$+$			$+$				$+$
段4										$+$			$+$				$+$
段5				$\times$		$\times$		$\times$		$\times$	$+$			$+$				$+$

總共18個$\Delta t$，輸出了7個結果，故吞吐率為$\frac{7}{18}=0.389$
不用流水線，需要 $4\times (1+2+1)+3\times (1+1+1+1)=28\Delta t$，故加速比為 $\frac{28}{18}=1.56$
效率為加速比/流水線段數 = 0.312

2

有一個 5 段流水線，各段執行時間均為 $\Delta t$，其預約表如下：

(1)畫出流水線任務調度的狀態轉移圖。
(2)分別求出允許不等時間間隔調度和等時間間隔調度的兩種最優調度策略,計算這兩種調度策略的流水線最大吞吐率。
(3)若連續輸入10個任務,分別求采用這兩種調度策略的流水線的實際吞吐率和加速比?

解：
(1) 禁止表 F = { 6 , 3 , 1 , 3 , 1 } = { 1 , 3 , 6 } F = \{6, 3, 1, 3, 1\} = \{1, 3, 6\} F={6,3,1,3,1}={1,3,6}
所以沖突向量為 $C=100101$
狀態轉移圖如下：

(2)

• 等時間間隔：只有 (5)，故吞吐率為 $\frac{1}{5}=0.2$
• 不等時間間隔：有 (2, 5), (2, 2, 5), (4, 5)，所以最優調度為 (2, 2, 5)，平均延遲為 3，吞吐率為 $\frac{1}{3}=0.33$

(3)

• 等時間間隔：10個任務，需要 1 + 45 + 6 = 52 個 $\Delta t$，吞吐率為 $\frac{10}{52}=0.192$， 加速比為 $\frac{70}{52}=1.346$
• 不等時間間隔：10個任務，需要 1 + 27 + 6 = 34 個 $\Delta t$，吞吐率為 $\frac{10}{34}=0.294$， 加速比為 $\frac{70}{34}=2.059$

3

在 MIPS 流水線上運行以下代碼序列

LOOP:   LW     R1,0(R2)DADDIU R1,R1,#1SW     R1,0(R2)DADDIU R2,R2,#4DSUB   R4,R3,R2BNEZ   R4,LOOP

其中,R3的初值是R2+396。假設:在整個代碼序列的執行過程中,所有的存儲器訪問都是命中的,并且在一個時鐘周期中對同一個寄存器的寫操作和讀操作可以通過分別把它們安排在前半個時鐘周期和后半個時鐘周期來實現。請問:
(1) 在沒有任何其他定向(或旁路)硬件的支持下,請畫出該指令序列執行的流水線時空圖。假設采用排空流水線的策略處理分支指令,且所有的存儲器訪問都命中Cache,那么執行上述循環需要多少個時鐘周期?
(2) 假設該流水線有正常的定向路徑,請畫出該指令序列執行的流水線時空圖。假設采用預測分支失敗的策略處理分支指令,且所有的存儲器訪問都命中Cache,那么執行上述循環需要多少個時鐘周期?
(3) 假設該流水線有正常的定向路徑和一個單周期延遲分支,請對該循環中的指令進行調度,你可以重新組織指令的順序,也可以修改指令的操作數,但是注意不能增加指令的 條數。請畫出該指令序列執行的流水線時空圖,并計算執行上述循環所需要的時鐘周期數。

解：
(1)
這里我們采用最簡單的流水線，如下圖所示：

時鐘周期	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
LW	IF	ID	EX	M	WB
DADDIU		IF	S	S	ID	EX	M	WB
SW					IF	S	S	ID	EX	M	WB
DADDIU								IF	ID	EX	M	WB
DSUB									IF	S	S	ID	EX	M	WB
BNEZ												IF	S	S	ID	EX	M	WB
LW															IF	S	S	IF	ID	EX	M	WB

396/4 = 99
(注意在PC寄存器還需要一個clock，故在MEM段才能寫入)
總共需要 (17*98) + 18 = 1684 個時鐘周期

(2)
采用定向路徑，那么得分情況討論

• 若是ALU指令，那么在MEM段就能重定向到EX段
• 若是LW指令，那么強制令在WB段才能重定向到EX段

預測失敗即為每次都預測錯誤。

這里假設分支指令在M段解決（如上圖）：

時鐘周期	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
LW	IF	ID	EX	M	WB
DADDIU		IF	ID	S	EX	M	WB
SW			IF	S	ID	EX	M	WB
DADDIU					IF	ID	EX	M	WB
DSUB						IF	ID	EX	M	WB
BNEZ							IF	ID	EX	M	WB
LW								miss	miss	miss	IF	ID	EX	M	WB

總共需要 (10*98) + 11 = 991 個時鐘周期

(3)
調整為

LOOP:   LW     R1,0(R2)DADDIU R2,R2,#4DADDIU R1,R1,#1// change the orderDSUB   R4,R3,R2BNEZ   R4,LOOPSW     R1,-4(R2)// remember to change the offset

時鐘周期	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
LW	IF	ID	EX	M	WB
DADDIU		IF	ID	EX	M	WB
DADDIU			IF	ID	EX	M	WB
DSUB				IF	ID	EX	M	WB
BNEZ					IF	ID	EX	M	WB
SW						IF	ID	EX	M	WB
LW						miss	miss	miss	IF	ID	EX	M	WB

總共需要 (8*98) + 10 = 803 個時鐘周期