第03章流水線技術(shù)

1、1 1193193張晨曦 編著華中科技大學(xué) 計算機學(xué)院2 0 1 3 年 3 月2 2193193作業(yè)：作業(yè)：P91P913.83.83.103.103.113.113 31931933.2MIPS 的基本流水線3.3流水線中的相關(guān) MIPS MIPS 流水線流水線 流水線性能分析流水線性能分析 結(jié)構(gòu)相關(guān)結(jié)構(gòu)相關(guān) 數(shù)據(jù)相關(guān)數(shù)據(jù)相關(guān) 控制相關(guān)控制相關(guān)3.4MIPS R4000 流水線計算機3.1流水線(Pipeline)的基本概念第三章 流水線技術(shù)4 41931933.1流水線的基本概念3.1.1 基本概念 1. 產(chǎn)品生產(chǎn)流水線下面通過一個例子來說明流水線的好處下面通過一個例子來說明流水線的好處

2、: : 兩種方案兩種方案 兩種方案的工作過程對比兩種方案的工作過程對比第三章 流水線技術(shù)5 5193193一套機器一個工人一套機器一個工人 一套可分離工具一套可分離工具4 4個工人個工人6 6193193 流水線生產(chǎn)過程的抽象描述流水線生產(chǎn)過程的抽象描述 這種流水工作方式的主要特點：重疊這種流水工作方式的主要特點：重疊7 71931932. 指令流水線指令流水線（處理機級流水線）處理機級流水線）把指令的解釋過程分解為把指令的解釋過程分解為“分析分析”和和“執(zhí)行執(zhí)行”兩個子過程，并讓這兩個子過程分別用獨立的分兩個子過程，并讓這兩個子過程分別用獨立的分析部件和執(zhí)行部件來實現(xiàn)。析部件和執(zhí)行部件來實現(xiàn)

3、。理想情況：理想情況：速度提高一倍速度提高一倍3.1 流水線的基本概念8 81931939 9193193分析分析執(zhí)行執(zhí)行時間時間 t t分析分析k k執(zhí)行執(zhí)行k kT=(p+qT=(p+q n n)t=2nt=2n t, p+q=2, p=0. p:t, p+q=2, p=0. p:重疊數(shù)重疊數(shù)T=(p+qT=(p+q n n)t=(1+n)t=(1+n) t, p+q=2, p=1t, p+q=2, p=1分析分析k+1k+1執(zhí)行執(zhí)行k+1k+13.1 流水線的基本概念10101931933. 浮點加法流水線浮點加法流水線（部件級流水線、部件級流水線、運算操作流水線）運算操作流水線）把浮點

4、加法的全過程分解為把浮點加法的全過程分解為“求階差求階差”、“對對階階”、“尾數(shù)相加尾數(shù)相加”、“規(guī)格化規(guī)格化”四個子過程，四個子過程，并讓并讓它們分別用各自獨立的部件來實現(xiàn)。它們分別用各自獨立的部件來實現(xiàn)。理想情況：理想情況：速度提高速度提高3 3倍倍 T=(p+qT=(p+q n n)t=(3+n)t=(3+n) t,p+q=4,p=3t,p+q=4,p=33.1 流水線的基本概念11111931933.1 流水線的基本概念12121931934. 時空圖時空圖時空圖時空圖從時間和空間兩個方面描述了流水從時間和空間兩個方面描述了流水線的工作過程。時空圖中，橫坐標(biāo)代表時間，線的工作過程。時空

5、圖中，橫坐標(biāo)代表時間，縱坐標(biāo)代表流水線的各個段?？v坐標(biāo)代表流水線的各個段。3.1 流水線的基本概念1313193193幾個“123”與坐標(biāo)解 流水線技術(shù)流水線技術(shù)流水線技術(shù)是指：將一個重復(fù)的時序過程分解是指：將一個重復(fù)的時序過程分解成為若干個子過程，而每個子過程都可有效地在成為若干個子過程，而每個子過程都可有效地在其專用功能段上與其他子過程同時執(zhí)行其專用功能段上與其他子過程同時執(zhí)行? ?6流水線技術(shù)的特點(1) (1) 流水過程由多個相聯(lián)系的子過程組成，每個流水過程由多個相聯(lián)系的子過程組成，每個子過程稱為流水線的子過程稱為流水線的“級級”或或“段段”?！岸味巍钡臄?shù)的數(shù)

6、目稱為流水線的目稱為流水線的“深度深度”。(2) (2) 每個子過程由專用的每個子過程由專用的功能段功能段實現(xiàn)；實現(xiàn)；3.1 流水線的基本概念1515193193(4) (4) 流水線需要有流水線需要有“通過時間通過時間”（第一個任務(wù)流出結(jié)果（第一個任務(wù)流出結(jié)果所所需的時間），在此之后流水過程才進入穩(wěn)定工作狀需的時間），在此之后流水過程才進入穩(wěn)定工作狀態(tài)，每一個時鐘周期（拍）流出一個結(jié)果；態(tài)，每一個時鐘周期（拍）流出一個結(jié)果；(3) (3) 各個功能段所需時間應(yīng)盡量相等，否則，時間長各個功能段所需時間應(yīng)盡量相等，否則，時間長的功能段將成為流水線的瓶頸，會造成流水線的的功能段將成為流水線的瓶頸，

7、會造成流水線的 “堵塞堵塞”和和“斷流斷流”。這個時間一般為一個時鐘。這個時間一般為一個時鐘周期周期（拍）；（拍）；(5) (5) 流水技術(shù)適合于大量重復(fù)的時序過程，只有輸入流水技術(shù)適合于大量重復(fù)的時序過程，只有輸入端能連續(xù)地提供任務(wù)，流水線的效率才能充分發(fā)端能連續(xù)地提供任務(wù)，流水線的效率才能充分發(fā)揮。揮。3.1 流水線的基本概念16161931933.1 流水線的基本概念分析分析k執(zhí)行執(zhí)行k分析分析k+1執(zhí)行執(zhí)行k+1分析分析k+2執(zhí)行執(zhí)行k+2為了盡量減少為了盡量減少瓶頸瓶頸損失，較好的辦法是緩沖技術(shù)。設(shè)置先行指令緩損失，較好的辦法是緩沖技術(shù)。設(shè)置先行指令緩沖棧，兩個工作時間不相等的功能部

8、件可以各自獨立地工作。這種沖棧，兩個工作時間不相等的功能部件可以各自獨立地工作。這種技術(shù)經(jīng)常被采用。技術(shù)經(jīng)常被采用。分析分析k執(zhí)行執(zhí)行k分析分析k+1執(zhí)行執(zhí)行k+1分析分析k+2執(zhí)行執(zhí)行k+2171719319318181931933.1.2 流水線的分類流水線可以按不同的觀點進行分類。流水線可以按不同的觀點進行分類。 單功能流水線：單功能流水線：只能完成一種固定功能的只能完成一種固定功能的 流水線。流水線。 多功能流水線：多功能流水線：流水線的各段可以進行不同的流水線的各段可以進行不同的 連接，從而實現(xiàn)不同的功能。連接，從而實現(xiàn)不同的功能。 例如：例如： TI ASCTI ASC的多功能流水

9、線的多功能流水線1按功能的多少來分3.1 流水線的基本概念19191931932020193193在靜態(tài)流水線中，只有當(dāng)輸入是一串相同在靜態(tài)流水線中，只有當(dāng)輸入是一串相同的運算操作時，流水的效率才能得到發(fā)揮。的運算操作時，流水的效率才能得到發(fā)揮。2按同一時間內(nèi)各段之間的連接方式來分 靜態(tài)流水線：靜態(tài)流水線：在同一時刻，流水線的各段只能在同一時刻，流水線的各段只能 按同一種功能的連接方式工作。按同一種功能的連接方式工作。 3.1 流水線的基本概念2121193193 動態(tài)流水線：動態(tài)流水線：在同一時刻，流水線的各段可以在同一時刻，流水線的各段可以 按不同功能的連接方式工作。按不同功能的連接方式工

10、作。 這樣就不是非得相同運算的一串操作才能這樣就不是非得相同運算的一串操作才能 流水處理。流水處理。 優(yōu)點：優(yōu)點：能提高流水線的效率能提高流水線的效率 缺點：缺點：會使流水線的控制變得復(fù)雜會使流水線的控制變得復(fù)雜3.1 流水線的基本概念2222193193 靜、動態(tài)流水線時空圖的對比靜、動態(tài)流水線時空圖的對比23231931933按照流水線的級別來分 部件級流水線部件級流水線（運算操作流水線）：把處理機的（運算操作流水線）：把處理機的 算術(shù)邏輯部件分段，使得各種數(shù)據(jù)類型的操作能算術(shù)邏輯部件分段，使得各種數(shù)據(jù)類型的操作能 夠進行流水夠進行流水( (求階差、對階、尾數(shù)加、規(guī)格化求階差、對階、尾數(shù)加

11、、規(guī)格化) )。 處理機級流水線處理機級流水線（指令流水線）：把指令的（指令流水線）：把指令的解釋解釋 執(zhí)行執(zhí)行過程按照流水方式進行處理。過程按照流水方式進行處理。 例如：例如：前面把指令解釋過程分解為：前面把指令解釋過程分解為： 分析分析和和執(zhí)行執(zhí)行 MIPSMIPS的基本流水線把指令解釋過程分解為：的基本流水線把指令解釋過程分解為： 取指令、指令譯碼、取指令、指令譯碼、執(zhí)行執(zhí)行、訪存、寫回。、訪存、寫回。3.1 流水線的基本概念24241931933.1 流水線的基本概念2525193193 處理機間流水線處理機間流水線（宏流水線）：它是指由兩個（宏流水線）：它是指由兩個 以上的處理機串行

12、地對同一數(shù)據(jù)流進行處理，以上的處理機串行地對同一數(shù)據(jù)流進行處理， 每個處理機完成一項任務(wù)。每個處理機完成一項任務(wù)。3.1 流水線的基本概念2626193193順序流動流水線：順序流動流水線：流水線輸出端任務(wù)流出的順流水線輸出端任務(wù)流出的順 序與輸入端任務(wù)流入的順序序與輸入端任務(wù)流入的順序相同相同。 異步流動流水線異步流動流水線（亂序流水線）：流水線輸出（亂序流水線）：流水線輸出 端任務(wù)流出的順序與輸入端任務(wù)流入的順序端任務(wù)流出的順序與輸入端任務(wù)流入的順序 不同不同。4. 按照流動是否可以亂序來分3.1 流水線的基本概念2727193193S1S1S2S2S3S3S4S4S5S5S6S6寄存器寄

13、存器 R0R0讀讀寫寫專用路徑專用路徑k: R0(R1) k+1: k+2:R2(R0)+(R3)k+3:k+4:k+5:ti+4 k+4 k+3 k+2空閑空閑空閑空閑空閑空閑ti+3 k+3 k+2空閑空閑空閑空閑空閑空閑k+1ti+2 k+3 k+2空閑空閑空閑空閑k+1kti+1 k+3 k+2空閑空閑k+1kk-1tik+3 k+2 k+1kk-1k-2 正常流動正常流動k+5 k+4 k+3 k+2 k+1k功能段功能段S1S2S3S4S5S62828193193ti+5k+8(k+7) k+6k+2k+5k+4k+3ti+4k+7(k+6) k+2k+5k+4k+3k+1ti+3

14、k+6k+5 (k+2) k+4k+3k+1 k ti+2k+5k+4 (k+2)k+3k+1 k k-1ti+1k+4k+3 (k+2)k+1 k k-1k-2tik+3(k+2) k+1 k k-1k-1k-3 正常流動正常流動k+5k+4k+3k+2k+1K功能段功能段S1S2S3S4S5S629291931935按照數(shù)據(jù)表示來分 向量處理機：向量處理機：具有向量指令和向量數(shù)據(jù)表示的具有向量指令和向量數(shù)據(jù)表示的 處理機。處理機。 例如：例如：TI ASC, TI ASC, CRAY-ICRAY-I 等等 標(biāo)量處理機：標(biāo)量處理機：不具有向量指令和向量數(shù)據(jù)表示，不具有向量指令和向量數(shù)據(jù)表示，

15、 僅對標(biāo)量進行流水處理的處理機。僅對標(biāo)量進行流水處理的處理機。 例如：例如：IBM360/91, Amdahl 470V/6IBM360/91, Amdahl 470V/6 等等6. 按照是否有反饋回路來分 線性流水線：線性流水線：流水線中的各段串行連接，沒流水線中的各段串行連接，沒 有反饋回路。有反饋回路。 非線性流水線：非線性流水線：流水線中的各段除有串行連接流水線中的各段除有串行連接 外，還有反饋回路。外，還有反饋回路。3.1 流水線的基本概念30301931933.1 流水線的基本概念3131193193 流水線的調(diào)度問題流水線的調(diào)度問題什么是沖突如何避開？什么是沖突如何避開？3232

16、193193非線性流水線的連接圖和預(yù)約表 P64-67 1 1 2 23 34 45 56 67 7S1S1 S2S2S3S3S4S4時間時間段段S1S2S3S4前饋線前饋線反饋線反饋線3333193193 1 1 2 23 34 45 56 67 78 89 910101111S1S11 11 1 2 2 1 1 2 2 3 32 2 3 3 4 4S2S21 11 1 2 22 2 3 33 3 4 4S3S31 12 21 13 32 24 4S4S41 12 23 3時間時間段段時間時間段段 1 1 2 23 34 45 56 67 78 89 910101111S1S11 12 21

17、 13 32 2 1 1 4 43 32 2 5 54 43 3 5 5S2S21 12 21 13 32 24 43 35 54 4S3S31 12 21 1 3 32 2 4 43 3 5 5S4S41 12 23 34 45 53434193193 1 1 2 23 34 45 56 67 78 89 910101111S1S11 11 1 2 2 1 1 2 2 3 32 2 3 3 4 4S2S21 11 1 2 22 2 3 33 3 4 4S3S31 12 21 13 32 24 4S4S41 12 23 3時間時間段段時間時間段段啟動周期啟動周期重復(fù)啟動周期重復(fù)啟動周期 1 1

18、 2 23 34 45 56 67 78 89 910101111S1S11 11 12 2 1 12 23 3S2S21 11 12 22 2S3S31 11 12 22 2S4S41 12 23535193193 1 1 2 23 34 45 56 67 78 89 9S1S1 S2S2 S3S3 S4S4 S5S5 時間時間段段1.1. 流水線的調(diào)度問題流水線的調(diào)度問題預(yù)約表與禁止表預(yù)約表與禁止表禁止表禁止表F (Forbidden)=1,5,6,8,F (Forbidden)=1,5,6,8, 同行相減同行相減, , 刪除相同刪除相同, , 無差不取無差不取3.1.3 非線性流水線的調(diào)

19、度3.1 流水線的基本概念36361931933.1 流水線的基本概念2.2. 流水線的調(diào)度問題流水線的調(diào)度問題禁止表與沖突向量禁止表與沖突向量C0C0C0=(Cn,Cn-1,C3,C2,C1)C0=(Cn,Cn-1,C3,C2,C1)Ci=1,Ci=1,若若i i屬于屬于F F，否則，否則Ci=0Ci=0由由F=F=1 1, ,5 5, 6 6, 8 得到?jīng)_突向量得到?jīng)_突向量CollisionCollision：C0=(C0=(1 10 01 11 10000001 1) )37371931933.1 流水線的基本概念3.3. 流水線的調(diào)度問題流水線的調(diào)度問題沖突向量與狀態(tài)轉(zhuǎn)換沖突向量與狀態(tài)

20、轉(zhuǎn)換假設(shè)啟動周期為假設(shè)啟動周期為j j，得到新的沖突向量，得到新的沖突向量SHRSHR(j)(j)(C0): (C0): 表示右移表示右移j j位位并使之與并使之與C0C0做做“或或”運算運算SHRSHR(j)(j)(C0)(C0) (C0)(C0)假設(shè)當(dāng)前沖突向量是假設(shè)當(dāng)前沖突向量是CkCk，j j是允許的時間間隔，是允許的時間間隔，則得到新的沖突向量：則得到新的沖突向量：SHRSHR(j)(j)(Ck)(Ck) (C0)(C0)38381931933.1 流水線的基本概念3.3. 流水線的調(diào)度問題流水線的調(diào)度問題狀態(tài)轉(zhuǎn)換與新的沖突向量狀態(tài)轉(zhuǎn)換與新的沖突向量由禁止表由禁止表F=1,5,6,8

21、F=1,5,6,8得到后續(xù)任務(wù)的可用時間得到后續(xù)任務(wù)的可用時間間隔為間隔為j=2j=2、3 3、4 4、7 7j=2j=2：(00101100)(00101100) (10110001)(10110001)=(10111101)=(10111101)，可用可用2 2、7 7j=3j=3：(00010110)(00010110) (10110001)(10110001)=(10110111)=(10110111)，可用可用4 4、7 7j=4j=4：(00001011)(00001011) (10110001)(10110001)=(10111011)=(10111011)，可用可用3 3、7

22、7j=7j=7：(00000001)(00000001) (10110001)(10110001)=(10110001)=(10110001)，可用可用2 2、3 3、4 4、7 739391931933.1 流水線的基本概念3.3. 流水線的調(diào)度問題流水線的調(diào)度問題狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖40401931933.1 流水線的基本概念4.4. 流水線的調(diào)度問題流水線的調(diào)度問題平均延遲拍數(shù)與最優(yōu)調(diào)度平均延遲拍數(shù)與最優(yōu)調(diào)度調(diào)度策略平均延遲拍數(shù)調(diào)度策略平均延遲拍數(shù)(2,7)4.5(3,4,7)4.67(2,2,7)3.67(4,3,7)4.67(3,7)5(4,7)5.5(3,4)3.5(7)7(3,4

23、,3,7)4.254141193193 1 234567 S1 S1 S2 S2 S3 S3 S4 S4 時間時間段段3.1 流水線的基本概念補充練習(xí)題補充練習(xí)題已知如下預(yù)約表，已知如下預(yù)約表，求最優(yōu)調(diào)度方案求最優(yōu)調(diào)度方案42421931933.1 流水線的基本概念43431931933.2MIPS的基本流水線3.2.1 MIPS的一種簡單實現(xiàn)首先討論在不流水的情況下，如何實現(xiàn)首先討論在不流水的情況下，如何實現(xiàn)MIPSMIPS。1. 實現(xiàn)MIPS指令的一種簡單數(shù)據(jù)通路第三章 流水線技術(shù)444419319345451931932. 一條MIPS指令最多需要以下5個時鐘周期：（1 1） 取指令周期

24、取指令周期（IFIF） IR MemPC NPC PC4操作：根據(jù)操作：根據(jù)PCPC值從存儲器中取出指令，并送入值從存儲器中取出指令，并送入指令寄存器指令寄存器IRIR；PCPC增值增值4 4，指向下一條指令，并將，指向下一條指令，并將下一條指令的地址放入臨時寄存器下一條指令的地址放入臨時寄存器NPCNPC3.2 MIPS的基本流水線46461931934747193193（2 2）指令譯碼）指令譯碼/ /讀寄存器周期讀寄存器周期（IDID） A RegsIR6 .10 B RegsIR11 .15 Imm (IR16)16 # IR16 .31 操作操作 指令譯碼和讀寄存器是并行進行的。之所

25、指令譯碼和讀寄存器是并行進行的。之所 以能做到這一點，是因為在以能做到這一點，是因為在MIPSMIPS指令格式中，指令格式中， 操作碼在固定位置。這種技術(shù)也稱為操作碼在固定位置。這種技術(shù)也稱為固定字段固定字段 譯碼。譯碼。A A、B B、ImmImm、LMD LMD 臨時寄存器。臨時寄存器。3.2 MIPS的基本流水線4848193193 I 類型指令 6 5 5 16 操作碼 rs rt 立即值 字節(jié)、半字、字的載入和儲存； rtrs op 立即值。分支指令: RegsrtRegsrs+immediate R 類型指令 6 5 5 5 5 6 操作碼 rs rt rd shamt Func

26、寄存器寄存器 ALU 操作：rdrs func rt； 函數(shù)對數(shù)據(jù)的操作進行編碼：加、減、； 對特殊寄存器的讀/寫和移動。 J 類型指令 6 26 操作碼 與 PC 相加的偏移量 跳轉(zhuǎn)，跳轉(zhuǎn)并鏈接，從異常（exception）處自陷和返回。 圖 2.10 MIPS 的指令格式布局 各種類型指令的格式ABAB49491931935050193193（3 3）執(zhí)行執(zhí)行/ /有效地址計算周期有效地址計算周期（EXEX） 在這個周期，不同的指令有不同的操作。在這個周期，不同的指令有不同的操作。3.2 MIPS的基本流水線5151193193 存儲器訪問存儲器訪問 ALUOutput AImm 操作操作

27、5252193193 寄存器寄存器寄存器寄存器 ALU ALU 操作操作 ALUOutput A op B 操作操作5353193193 寄存器寄存器立即值立即值 ALU ALU 操作操作 ALUOutput A op Imm 操作操作5454193193 分支操作分支操作(P63) (P63) BEQZ R4,nameBEQZ R4,name ALUOutput NPCImm Cond (A op 0) 操作操作?5555193193（4 4）存儲器訪問存儲器訪問/ /分支完成周期分支完成周期（MEMMEM） 在該周期處理的在該周期處理的MIPSMIPS指令只有指令只有LoadLoad、St

28、oreStore和和 分支指令。分支指令。這里，將有效地址計算周期和執(zhí)行周期合并這里，將有效地址計算周期和執(zhí)行周期合并為一個時鐘周期，這是由為一個時鐘周期，這是由 MIPSMIPS指令集結(jié)構(gòu)本指令集結(jié)構(gòu)本身的特點所允許的，因為在身的特點所允許的，因為在MIPSMIPS指令集結(jié)構(gòu)指令集結(jié)構(gòu)中，沒有任何指令需要同時中，沒有任何指令需要同時計算計算數(shù)據(jù)的存儲數(shù)據(jù)的存儲器地址器地址、計算計算分支指令的目標(biāo)地址分支指令的目標(biāo)地址和和進行進行數(shù)數(shù)據(jù)處理據(jù)處理。3.2 MIPS的基本流水線5656193193 存儲器訪問存儲器訪問 LMD MemALUOutput 或或 Mem ALUOutput B操作操

29、作SW 500(R4), SW 500(R4), R3R3LW LW R1R1, 30(R2), 30(R2) R1R1 MemALUOutput 能否，為什么能否，為什么? ?3.2 MIPS的基本流水線57571931935858193193 分支操作分支操作 if (cond) PC ALUOutput else PC NPC操作操作5959193193 BEQZ R4,nameBEQZ R4,name6060193193（5 5）寫回周期）寫回周期（WBWB） 不同指令在該周期完成的工作也不一樣。不同指令在該周期完成的工作也不一樣。 寄存器寄存器寄存器型寄存器型 ALU ALU 指令指

30、令 (R)(R) RegsIR16 .20 ALUOutput操作操作 寄存器寄存器立即值型立即值型 ALU ALU 指令指令 (I)(I) RegsIR11 .15 ALUOutput操作操作 LoadLoad 指令指令(I)(I) RegsIR11 .15 LMD 操作操作3.2 MIPS的基本流水線6161193193寄存器寄存器寄存器型寄存器型 ALU ALU 指令指令 ADD R1, R2, R3 (P60)ADD R1, R2, R3 (P60) RegsIR16 .20 ALUOutput6262193193寄存器寄存器立即值型立即值型 ALU ALU 指令指令 ADD R8,R

31、2,#3 (P62)ADD R8,R2,#3 (P62) RegsIR11 .15 ALUOutput6363193193LoadLoad 指令指令 RegsIR11 .15 LMD64641931933. 分支指令需要4個時鐘周期, 其它指令需要5個時鐘周期 假設(shè)分支指令占總指令數(shù)的假設(shè)分支指令占總指令數(shù)的1212, , 則則: : CPICPI4 4* *0.12+50.12+5* *0.88 = 4.880.88 = 4.88 上述實現(xiàn)無論在性能上，還是在硬件開銷上，上述實現(xiàn)無論在性能上，還是在硬件開銷上，都不是優(yōu)化的。都不是優(yōu)化的。3.2 MIPS的基本流水線65651931933.2

32、.2 基本的MIPS流水線我們可以把我們可以把3.2.13.2.1中的數(shù)據(jù)通路流水化：中的數(shù)據(jù)通路流水化：每個時鐘周期啟動一條新的指令。每個時鐘周期啟動一條新的指令。這樣，該數(shù)據(jù)通路中的每一個周期就成這樣，該數(shù)據(jù)通路中的每一個周期就成了一個流水段。了一個流水段。1. 一種簡單的 MIPS 流水線2. 簡單MIPS流水線的流水過程第一種描述第一種描述（類似于時空圖）（類似于時空圖）第二種描述第二種描述（按時間錯開的數(shù)據(jù)通路序列）（按時間錯開的數(shù)據(jù)通路序列）3.2 MIPS的基本流水線66661931933.2 MIPS的基本流水線類似于時空圖類似于時空圖6767193193按時間錯開的數(shù)據(jù)通路序

33、列按時間錯開的數(shù)據(jù)通路序列68681931933. 采用流水技術(shù)還應(yīng)解決好以下幾個問題：上述簡單上述簡單MIPSMIPS流水線中：流水線中： 指令存儲器指令存儲器（IMIM）和）和數(shù)據(jù)存儲器數(shù)據(jù)存儲器（DMDM）分）分 開，避免了訪存沖突。開，避免了訪存沖突。 IDID段和段和WBWB段都要訪問同一寄存器文件。段都要訪問同一寄存器文件。 IDID段：讀段：讀WBWB段：寫段：寫 如何解決對如何解決對同一寄存器同一寄存器的訪問沖突？的訪問沖突？（1 1）應(yīng)保證不會在同一個時鐘周期內(nèi)在同一數(shù)據(jù)）應(yīng)保證不會在同一個時鐘周期內(nèi)在同一數(shù)據(jù) 通路資源上做不同的操作。通路資源上做不同的操作。 例如，不能要求

34、一個例如，不能要求一個ALUALU同時既做有效同時既做有效 地址計算，又做減法操作。地址計算，又做減法操作。Add R1,30(R2)?Add R1,30(R2)?3.2 MIPS的基本流水線69691931933.2 MIPS的基本流水線讀寫讀寫寄存器沖突：寄存器沖突：R PC R PC NPCNPC等等7070193193 沒有考慮沒有考慮 PC PC 問題問題流水線為了能夠每個時鐘周期啟動一條流水線為了能夠每個時鐘周期啟動一條新的指令，就必須在每個時鐘周期進行新的指令，就必須在每個時鐘周期進行PCPC值值的加的加4 4操作，并保留新的操作，并保留新的PCPC值。這種值。這種操作必操作必須

35、在須在IFIF段段完成完成，以便為取下一條指令做好準(zhǔn)，以便為取下一條指令做好準(zhǔn)備。備。3.2 MIPS的基本流水線71711931937272193193但分支指令也可能改變但分支指令也可能改變PCPC的值，而且是的值，而且是在在MEMMEM段進行，這會導(dǎo)致段進行，這會導(dǎo)致( (PCPC) )沖突沖突。73731931937474193193為解決問題，我們?yōu)榻鉀Q問題，我們重新組織數(shù)據(jù)通路重新組織數(shù)據(jù)通路，把所有改變，把所有改變PCPC值的值的操作都放在操作都放在IFIF段進行。段進行。但分支指令如何處理？但分支指令如何處理？ 7575193193（2 2）每一流水段內(nèi)的操作都必須在一個時鐘周

36、期）每一流水段內(nèi)的操作都必須在一個時鐘周期 內(nèi)完成內(nèi)完成 流水線各段之間需設(shè)置流水線寄存器流水線各段之間需設(shè)置流水線寄存器 （也稱為（也稱為鎖存器鎖存器） 流水線寄存器組及其所含寄存器的流水線寄存器組及其所含寄存器的命名命名 例如，例如，IDID段和段和EXEX段之間的流水線寄存段之間的流水線寄存 器組中的器組中的IRIR寄存器的名稱為寄存器的名稱為: :ID/EX.IRID/EX.IR 流水線寄存器的作用流水線寄存器的作用 把數(shù)據(jù)和控制信息從一個流水段傳把數(shù)據(jù)和控制信息從一個流水段傳 送到下一個流水段。送到下一個流水段。（3 3）流水線寄存器流水線寄存器（組）（組）3.2 MIPS的基本流水

37、線76761931937777193193 流水線寄存器的構(gòu)成流水線寄存器的構(gòu)成 LMDLMD作用，在第作用，在第5 5拍寫回拍寫回, , 避免相關(guān)？避免相關(guān)？78781931934. MIPS流水線的操作對于流水線中的指令來說，在任一時刻，它對于流水線中的指令來說，在任一時刻，它僅在流水線中的某一段內(nèi)執(zhí)行操作。僅在流水線中的某一段內(nèi)執(zhí)行操作。因此，只要知道因此，只要知道某條指令在某條指令在每一流水段進每一流水段進行何種操作，就知道了行何種操作，就知道了它在它在整個流水線的操作。整個流水線的操作。( (表表3.1)3.1)給出了給出了MIPSMIPS流水線各段的操作。流水線各段的操作。 3.2

38、 MIPS的基本流水線7979193193流水段流水段表3.1 MIPS流水線的每個流水段的操作任何指令類型任何指令類型ALU 指令指令Load/Store 指令指令分支指令分支指令I(lǐng)FIDEXIF/ID.IR MemPCIF/ID.NPC,PC (if EX/MEM.cond EX/MEM.ALUout else PC+4);ID/EX.A RegsIF/ID.IR6.10; ID/EX.B RegsIF/ID.IR11.15;ID/EX.NPC IF/ID.NPC; ID/EX.IR IF/ID.IR;ID/EX.Imm (IR16)16#IR16.31;EX/MEM.IR ID/EX.I

39、R; EX/MEM.ALUOutput ID/EX.A op ID/EX.B 或EX/MEM.ALUOutput ID/EX.A op ID/EX.Imm;EX/MEM.cond 0;EX/MEM.IR ID/EX.IR; EX/MEM.ALUOutput ID/EX.A + ID/EX.Imm;EX/MEM.ALUOutput ID/EX.NPC + ID/EX.Imm;EX/MEM.cond (ID/EX.A op 0);8080193193流水段流水段任何指令類型任何指令類型ALU 指令指令Load/Store 指令指令分支指令分支指令MEMWBMEM/WB.IR EX/MEM.IR;

40、MEM/WB.ALUOutput EX/MEM.ALUOutput;MEM/WB.IR EX/MEM.IR; MEM/WB.LMD MemEX/MEM.ALUOutput;或MemEX/MEM.ALUOutput EX/MEM.B;RegsMEM/WB.IR16.20 MEM/WB.ALUOutput;或RegsMEM/WB.IR11.15 MEM/WB.ALUOutput;I?RRegsMEM/WB.IR11.15 MEM/WB.LMD;MIPS流水線的每個流水段的操作81811931935MIPS流水線的控制主要是確定如何主要是確定如何控制那四個多路選擇器控制那四個多路選擇器。828219

41、31933.2.3 流水線性能分析吞吐率吞吐率是指單位時間內(nèi)流水線所完成的任是指單位時間內(nèi)流水線所完成的任務(wù)數(shù)或輸出結(jié)果的數(shù)量。務(wù)數(shù)或輸出結(jié)果的數(shù)量。1. 吞吐率(1) (1) 最大吞吐率最大吞吐率TPTPmaxmax 最大吞吐率最大吞吐率是指流水線在連續(xù)流動達(dá)到是指流水線在連續(xù)流動達(dá)到穩(wěn)定穩(wěn)定狀態(tài)后所得到的吞吐率。狀態(tài)后所得到的吞吐率。 若流水線各段的時間相等，均為若流水線各段的時間相等，均為t t0 0 ， 則：則： TPmax 1 /t0MIPS的基本流水線8383193193 若流水線各段的時間不等，則：若流水線各段的時間不等，則： 最大吞吐率取決于流水線中最慢的一段所最大吞吐率取決于

42、流水線中最慢的一段所 需的時間，這段就成了流水線的瓶頸。需的時間，這段就成了流水線的瓶頸。 消除瓶頸的方法消除瓶頸的方法l 細(xì)分瓶頸段細(xì)分瓶頸段 l 重復(fù)設(shè)置瓶頸段重復(fù)設(shè)置瓶頸段1 1maxmaxt ti i TPmax 3.2 MIPS的基本流水線8484193193白色表示空閑白色表示空閑8585193193重復(fù)設(shè)置瓶頸段重復(fù)設(shè)置瓶頸段( (時時- -空圖舉例空圖舉例) )8686193193 第一種情況：各段時間第一種情況：各段時間相等相等（設(shè)為（設(shè)為t t0 0） 假設(shè)流水線由假設(shè)流水線由 m m 段組成，完成段組成，完成 n n 個任務(wù)。個任務(wù)。l 時空圖時空圖l 完成完成 n n

43、個任務(wù)所需的時間個任務(wù)所需的時間 T T流水流水m mt t0 0( (n n1)1)t t0 0 ( (說明說明) )(2) (2) 實際吞吐率實際吞吐率TPTP 流水線的實際吞吐率小于最大吞吐率。流水線的實際吞吐率小于最大吞吐率。3.2 MIPS的基本流水線8787193193通過時間通過時間8888193193完成完成 n n 個任務(wù)所需的時間個任務(wù)所需的時間8989193193l 實際吞吐率實際吞吐率TP TP T T流水流水n nm mt t0 0( (n n) )t t0 0n n(1(1 ) )t t0 0 m m1 11 1TPTPmaxmaxn n 1 1n nm m1 1T

44、P TP TPTPmaxmax當(dāng)當(dāng)n n m m 時，時，TP TP TPTPmaxmax 第二種情況：各段時間第二種情況：各段時間不等不等l 時空圖時空圖3.2 MIPS的基本流水線90901931933.2 MIPS的基本流水線9191193193 l 完成完成 n n 個任務(wù)所需的時間個任務(wù)所需的時間 T T流水流水t ti i( (n n1)1)t tj j t tj jmaxmaxt ti i l 實際吞吐率實際吞吐率TP TP t ti i( (n n1)1)t tj jm mi=1i=1n ni=1i=1m m3.2 MIPS的基本流水線9292193193加速比加速比是指流水線

45、的速度與等功能非流水是指流水線的速度與等功能非流水線的速度之比。線的速度之比。2. 加速比S S ST T非流水非流水T T流水流水（其中（其中T T流水流水和和T T非流水非流水分別為按流水和按非流水分別為按流水和按非流水方式處理方式處理 n n 個任務(wù)所需的時間）個任務(wù)所需的時間） 若流水線為若流水線為 m m 段，且各段時間相等，均段，且各段時間相等，均為為t t0 0 ，則：，則： T T非流水非流水n mn mt t0 0 T T流水流水m mt t0 0( (n n1)1)t t0 0 3.2 MIPS的基本流水線93931931933.2 MIPS的基本流水線9494193193

46、可以看出：可以看出：當(dāng)當(dāng)n n m m 時，時，S S m m想一想：想一想：m m 越大越好？單周期指令？越大越好？單周期指令？效率效率是指流水線的設(shè)備是指流水線的設(shè)備( (空間空間) )利用率利用率(utility)(utility)。(1) (1) 由于流水線有由于流水線有通過時間和排空時間通過時間和排空時間，所以，所以 流水線的各段并不是一直滿負(fù)荷地工作。流水線的各段并不是一直滿負(fù)荷地工作。 故：故：E E 1 1S S T T非流水非流水T T流水流水nmnmt t0 0m mt t0 0( (n n1 1) )t t0 0mnmnm mn n1 1m mn n1 1 m m1 1

47、3效率 EMIPS的基本流水線9595193193MIPS的基本流水線9696193193(2) (2) 若各段時間相等，則各段的效率若各段時間相等，則各段的效率e ei i相等，即相等，即 e e1 1e e2 2 e e3 3 e em mn nt t0 0T T流水流水 ( (解釋解釋) ) 整個流水線的效率為整個流水線的效率為: :當(dāng)當(dāng) n n m m 時，時，E E 1 1E E n nt t0 0T T流水流水n nm mn n1 11n n1 m1(3) (3) 從時空圖上看，效率實際上就是從時空圖上看，效率實際上就是 n n 個任務(wù)所個任務(wù)所占的時空區(qū)與占的時空區(qū)與 m m 個

48、段總的時空區(qū)個段總的時空區(qū)之比，即：之比，即： n n 個任務(wù)占用的時空區(qū)個任務(wù)占用的時空區(qū)E E ( (解釋解釋) ) m m 個段個段總的總的時空區(qū)時空區(qū)3.2 MIPS的基本流水線97971931939898193193(4) (4) 提高流水線效率所采取的措施對于提高提高流水線效率所采取的措施對于提高 吞吐率也有好處。吞吐率也有好處。TP=E/TP=E/t t0 04流水線性能分析舉例 P62 先加再乘例例3.13.1 在在靜態(tài)流水線靜態(tài)流水線上計算上計算 A Ai iB Bi i ， 求：吞吐率，加速比，效率。求：吞吐率，加速比，效率。4 4i i=1=13.2 MIPS的基本流水線

49、99991931933.2 MIPS的基本流水線3 3次加法，次加法，4 4次乘法。非流水：次乘法。非流水：3 36+46+44=344=34100100193193解解：( (1) 1) 確定適合于流水處理的確定適合于流水處理的計算過程計算過程(2) (2) 畫時空圖畫時空圖 (3) (3) 計算性能計算性能 吞吐率吞吐率 TPTP7 7(20(20t t) ) 加速比加速比 S S(34(34t t) )(20(20t t) )1.71.7 效率效率 E E(4(44 43 36)6)(8(820)20)0.210.213.2 MIPS的基本流水線101101193193102102193

50、1931031031931933.2 MIPS的基本流水線nTPT流水104104193193可以看出，在求解此問題時，該流水線的效率可以看出，在求解此問題時，該流水線的效率不高。不高。( (原因原因) )動態(tài)流水線的時空圖動態(tài)流水線的時空圖 舉例舉例 3.2 MIPS的基本流水線105105193193舉例舉例 : : 這樣行不行？正確答案這樣行不行？正確答案3.2 MIPS基本流水線106106193193例例3.23.2 假設(shè)前面假設(shè)前面MIPSMIPS非流水線實現(xiàn)的時鐘周期時為非流水線實現(xiàn)的時鐘周期時為10ns10ns，ALUALU和分支指令需要和分支指令需要4 4個時鐘周期，訪問存?zhèn)€

51、時鐘周期，訪問存儲器指令需儲器指令需5 5個時鐘周期，上述指令在程序中出現(xiàn)個時鐘周期，上述指令在程序中出現(xiàn)的相對頻率分別是：的相對頻率分別是：40%40%、20%20%和和40%40%。在基本的。在基本的MIPSMIPS流水線中，假設(shè)由于時鐘扭曲和寄存器建立流水線中，假設(shè)由于時鐘扭曲和寄存器建立延遲等原因，流水線要在其時鐘周期時間上附加延遲等原因，流水線要在其時鐘周期時間上附加1ns1ns的額外開銷?，F(xiàn)忽略任何其他延遲因素的影響，的額外開銷?，F(xiàn)忽略任何其他延遲因素的影響，請問：相對于非流水實現(xiàn)而言，基本的請問：相對于非流水實現(xiàn)而言，基本的MIPSMIPS流水流水線執(zhí)行指令的加速比是多少？線執(zhí)行

52、指令的加速比是多少？3.2 MIPS的基本流水線107107193193解：解：當(dāng)非流水執(zhí)行指令時，指令的平均執(zhí)行時當(dāng)非流水執(zhí)行指令時，指令的平均執(zhí)行時 間為間為 TPITPI非流水非流水 = 10ns= 10ns(40%+20%)(40%+20%)4 440%40%5)5) = 10ns = 10ns4.4 = 44ns4.4 = 44ns 在流水實現(xiàn)中，指令執(zhí)行的平均時間在流水實現(xiàn)中，指令執(zhí)行的平均時間 是最慢一段的執(zhí)行時間加上額外開銷，即是最慢一段的執(zhí)行時間加上額外開銷，即 TPITPI流水流水 = 10ns+1ns = 11ns= 10ns+1ns = 11ns 所以基本的所以基本的M

53、IPSMIPS流水線執(zhí)行指令的加速比為流水線執(zhí)行指令的加速比為S S = =TPITPI非流水非流水TPITPI流水流水44ns44ns11ns11ns= = 4= 43.2 MIPS的基本流水線108108193193例例3.3 (bottleneck)3.3 (bottleneck) 假設(shè)在假設(shè)在MIPSMIPS的非流水實現(xiàn)和基本流水線中，的非流水實現(xiàn)和基本流水線中，5 5個個功能單元的時間為：功能單元的時間為：1010，8 8，1010，1010，7 7（nsns），流水），流水額外開銷為：額外開銷為：1ns1ns，求求加速比加速比S S。解解：T T非流水非流水10108 810101

54、0107 745 (ns)45 (ns) T T流水流水 10101 111 (ns)11 (ns) S S 454511114.14.13.2 MIPS的基本流水線109109193193例例3.4 3.4 用一條用一條4 4段浮點加法器流水線計算段浮點加法器流水線計算8 8個浮點數(shù)的和個浮點數(shù)的和Z=A+B+C+D+E+F+G+HZ=A+B+C+D+E+F+G+H，求流水線的吞吐率，加速比和效率。，求流水線的吞吐率，加速比和效率。TP=n/Tk=7/15t=0.47/t, S=T0/Tk=4TP=n/Tk=7/15t=0.47/t, S=T0/Tk=47t/15t=1.87, 7t/15t

55、=1.87, E=T0/(kE=T0/(kTk)=4Tk)=47t/(47t/(4 15T)=0.47 15T)=0.47周期周期12345678910 11 12 13 14 15規(guī)格化規(guī)格化1234567尾數(shù)加尾數(shù)加1234567對階對階1234567求階差求階差1234567加數(shù)加數(shù)A C E GA+BE+FX加數(shù)加數(shù)B D F HC+DG+HY結(jié)果結(jié)果A+BC+DE+FG+HXYZ1101101931935有關(guān)流水線性能的若干問題(1) (1) 流水線并不能減少流水線并不能減少( (而且一般是增加而且一般是增加) )單條指單條指 令的執(zhí)行時間，但卻能提高吞吐率。令的執(zhí)行時間，但卻能提高

56、吞吐率。(2) (2) 增加流水線的深度增加流水線的深度( (段數(shù)段數(shù)) )可以提高流水線的可以提高流水線的 性能。性能。(3) (3) 流水線的深度受限于流水線的延遲和流水線流水線的深度受限于流水線的延遲和流水線 的額外開銷。的額外開銷。(4) (4) 流水線的額外開銷包括：流水線的額外開銷包括： 流水寄存器的延遲流水寄存器的延遲( (建立時間和傳輸延遲建立時間和傳輸延遲) ) 時鐘扭曲時鐘扭曲3.2 MIPS的基本流水線111111193193(5) (5) 當(dāng)時鐘周期小到與額外開銷相同時，流水已沒意當(dāng)時鐘周期小到與額外開銷相同時，流水已沒意 義。因為這時在每一個時鐘周期中已沒有時間來義。

57、因為這時在每一個時鐘周期中已沒有時間來 做有用的工作。做有用的工作。(6) (6) 需用高速的鎖存器來作為流水寄存器。需用高速的鎖存器來作為流水寄存器。 EarleEarle鎖存器鎖存器(1965)(1965)的三個特點的三個特點: : 對時鐘扭曲不太敏感（相對而言）對時鐘扭曲不太敏感（相對而言） 其延遲為常數(shù)：其延遲為常數(shù)：2 2個門級延遲，避免了數(shù)據(jù)通個門級延遲，避免了數(shù)據(jù)通 過鎖存器時的扭曲。過鎖存器時的扭曲。3.2 MIPS的基本流水線112112193193(7) (7) 相關(guān)問題相關(guān)問題 如果流水線中的指令相互獨立，則可以充分如果流水線中的指令相互獨立，則可以充分 發(fā)揮流水線的性能

58、。但在實際中，指令間可能會發(fā)揮流水線的性能。但在實際中，指令間可能會 是相互依賴，這會降低流水線的性能。下一節(jié)介是相互依賴，這會降低流水線的性能。下一節(jié)介 紹如何解決相關(guān)問題。紹如何解決相關(guān)問題。 鎖存器中可以進行兩級邏輯運算而不增延遲時鎖存器中可以進行兩級邏輯運算而不增延遲時 間。這樣每個流水段中的兩級邏輯可以與鎖存間。這樣每個流水段中的兩級邏輯可以與鎖存 器重疊，從而能隱藏鎖存器開銷的絕大部分。器重疊，從而能隱藏鎖存器開銷的絕大部分。3.2 MIPS的基本流水線1131131931933.3流水線中的相關(guān)1相關(guān)的概念 流水線中的相關(guān)流水線中的相關(guān)是指相鄰或相近的兩條指是指相鄰或相近的兩條指

59、令因存在某種關(guān)聯(lián)，后一條指令不能在原指定令因存在某種關(guān)聯(lián)，后一條指令不能在原指定的時鐘周期開始執(zhí)行的時鐘周期開始執(zhí)行。 結(jié)構(gòu)相關(guān)結(jié)構(gòu)相關(guān) 當(dāng)硬件資源滿足不了同時重疊執(zhí)行的指當(dāng)硬件資源滿足不了同時重疊執(zhí)行的指 令的要求，而發(fā)生資源沖突時，就發(fā)生令的要求，而發(fā)生資源沖突時，就發(fā)生了結(jié)了結(jié) 構(gòu)相關(guān)。構(gòu)相關(guān)。2相關(guān)的分類第三章 流水線技術(shù)114114193193 數(shù)據(jù)相關(guān)數(shù)據(jù)相關(guān) 當(dāng)一條指令需要用到前面某條指令的結(jié)當(dāng)一條指令需要用到前面某條指令的結(jié) 果，從而不能重疊執(zhí)行時，就發(fā)生了果，從而不能重疊執(zhí)行時，就發(fā)生了數(shù)據(jù)相數(shù)據(jù)相 關(guān)關(guān)。 控制相關(guān)控制相關(guān) 當(dāng)流水線遇到分支指令和其他能夠改變當(dāng)流水線遇到分支

60、指令和其他能夠改變 PCPC值的指令時，就會發(fā)生值的指令時，就會發(fā)生控制相關(guān)控制相關(guān)。3幾個問題 相關(guān)有可能會使流水線停頓。相關(guān)有可能會使流水線停頓。3.3 流水線中的相關(guān)115115193193在本章中，我們在本章中，我們約定：約定： 當(dāng)一條指令被暫停時，暫停在其后發(fā)射（流出）的指令，但繼續(xù)執(zhí)行在其前發(fā)射的 指令。暫停期間，流水線不會取新指令。 消除相關(guān)的消除相關(guān)的基本方法：基本方法： 讓流水線中的某些指令暫停，而讓其它讓流水線中的某些指令暫停，而讓其它 指令繼續(xù)執(zhí)行。指令繼續(xù)執(zhí)行。3.3 流水線中的相關(guān)1161161931933.3.1 流水線中的結(jié)構(gòu)相關(guān)2. 如果某種指令組合因資源沖突而