流水線(Pipeline)介紹

1、1處理器流水線相關技術報告人：Hardy2流水線技術v1.流水線的概念v2.流水線的冒險和冒險的解決辦法v3.多發(fā)射處理器31.流水線的概念v流水線技術：把一個重復的過程分解為若干個子過程，每個子過程由專門的功能部件來實現(xiàn)。將多個處理過程在時間上錯開，依次通過各功能段，這樣，每個子過程就可以與其他子過程并行進行。v流水線的描述：最常用的方法是時間-空間圖橫坐標：表示時間，即各個任務在流水線中所經(jīng)過的時間縱坐標：表示空間，即流水線的各個子過程，也稱為級、流水線深度(Stage)4流水線時間空間圖5v流水線技術應用到處理器中就是采用流水線方式執(zhí)行指令。一個MIPS指令包包含五個處理步驟： 1.取指

2、令周期（IF）2.指令譯碼/讀寄存器周期（ID）3.執(zhí)行操作/計算地址（EX）4.從數(shù)據(jù)存儲器中讀取操作數(shù)（MEM）5.將結果寫回寄存器堆（WB）6采用相同的功能模塊，指令順序執(zhí)行和按照流水線技術執(zhí)行，在時間上可以看出流水線指令的執(zhí)行速度提高了4倍。7流水線的基本作用 流水線增大了CPU的指令吞吐量即單位時間執(zhí)行指令的條數(shù)，但是它未減少指令各自的執(zhí)行時間。實際上流水線技術要對流水線附加一些控制，因而了增加開銷，使單條指令執(zhí)行時間略有增加。吞吐量的增大意味著程序運行的更快，總的執(zhí)行時間變短，盡管沒有一條指令的執(zhí)行變快。82.流水線的冒險v盡管流水線可以帶來處理器性能上的提高，但是不是所有的指令就

3、直接可以進行流水線操作，在指令執(zhí)行中的下一個周期中的下一條指令不能執(zhí)行，這種情況叫做冒險。有三類冒險：1.結構冒險2.數(shù)據(jù)冒險3.控制冒險流水線中的冒險會引起流水線停頓，部分指令就要延期執(zhí)行。92.1 結構冒險v結構沖突（資源沖突）：流水線中多條指令在同一時鐘周期內爭用同一功能部件的現(xiàn)象。即因硬件資源滿足不了指令重疊執(zhí)行的要求而發(fā)生的沖突。v常見的導致結構相關的原因：功能部件不是完全流水或者資源不夠用。功能部件不是完全流水或者資源不夠用。 例如訪存沖突例如訪存沖突10結構冒險112.2 結構冒險的解決辦法vMIPS指令集是為流水線設計的，在設計流水線過程中能夠很容易的避免結構冒險。v但是流水結

4、構中只有一個存儲器時，兩條指令同時在一個存儲器中預取指令就會發(fā)生結構冒險。12為消除資源沖突而插入的流水線氣泡（Bubble） 時時間間（時時鐘鐘周周期期） 1 2 3 4 5 6 M Reg ALU M Reg M Reg ALU M Reg M Reg ALU M Reg 7 8 load 指指令令 i+1 指指令令 i+2 暫暫 停停 M Reg ALU M 指指令令 i+3 氣氣泡泡 氣氣泡泡 氣氣泡泡 氣氣泡泡 氣氣泡泡 13解決辦法二v設置相互獨立的指令存儲器和數(shù)據(jù)存儲器或設置相互獨立的指令Cache和數(shù)據(jù)Cache。 IM Reg ALU DM Reg IF 段段 ID 段段 E

5、X段段 MEM 段段 WB 段段 流水線寄存器流水線寄存器 142.3 數(shù)據(jù)冒險v一條指令必須等到另一條指令的完成而造成的流水線暫停的情況叫做數(shù)據(jù)冒險。形如： add $s0, $t0, $t0 sub $t2, $s0 $t3 加法指令需要到WB階段后才寫回結果，減法指令此時才可以繼續(xù)執(zhí)行。在不任何干預的情況下，流水線白白浪費了三個時鐘周期。15 時間（時鐘周期） 1 2 3 4 5 6 IM Reg ALU DM Reg IM Reg ALU DM Reg IM Reg ALU DM IM Reg ALU DADD R1， R2， R3 DSUB R4，R1，R5 XOR R6，R1，R7

6、 AND R8，R1，R9 IM Reg OR R10，R1，R11 AND,OR操作不會暫停，但是DSUB,XOR指令需要等待DADD在WB階段寫回數(shù)據(jù)后才可以執(zhí)行。162.4 數(shù)據(jù)冒險的解決辦法v根據(jù)指令中讀寫訪問的順序，可以將數(shù)據(jù)冒險分為三類。分別是:v寫后讀（RAW）v寫后寫 (WAW)v讀后寫 (WAR) 17寫后讀冒險（RAW: Read After Write）v在 i 寫入之前，j 先去讀。j 會錯誤的獲取舊值。v這對應“真數(shù)據(jù)相關”，為了確保j可以得到正確的i值，必須保持程序的順序。i: DSUB R1,R2,R3j: DADD R4,R1,R318寫后寫沖突（WAW: Wr

7、ite After Write）v在 i 寫入之前，j 先寫。最后寫入的結果 i 是錯誤的。v這對應“輸出相關”，寄存器換名技術可以消除i: DSUB R1,R4,R3 j: DADD R1,R2,R3k: DMUL R6,R1,R7Cant happen in MIPS 5 stage pipeline because: - All instructions take 5 stages, and - Writes are always in stage 519讀后寫沖突（WAR: Write After Read）v在 i 讀之前，j 先寫。i 讀出的內容是錯誤的！v這對應“反相關” ，寄存

8、器換名技術可以消除i: DSUB R4,R1,R3 j: DADD R1,R2,R3k: DMUL R6,R1,R7Cant happen in MIPS 5 stage pipeline because:- All instructions take 5 stages, and- Reads are always in stage 2, and - Writes are always in stage 5讀后讀RAR不是數(shù)據(jù)冒險，讀操作不改變值20轉發(fā)（旁路）方式解決數(shù)據(jù)冒險 形如：add $s0, $t0, $t0 sub $t2, $s0 $t3，減法指令要等到加法指令寫回寄存器堆時才可

9、以執(zhí)行指令，浪費了時間。轉發(fā)技術：在加法指令在ALU運算一結束就將結果送給減法指令的輸入項。這樣從內部資源中直接提前得到缺少的運算項的過程叫做轉發(fā)。21 在原始的數(shù)據(jù)通路中用流水線寄存器將流水線各部分分開，這些寄存器可以存儲所有穿過它的數(shù)據(jù)，寄存器的寬度都足夠大。目前流行的有128位，97位，64位。 有了流水線寄存器后，轉發(fā)就變的簡單了。在指令執(zhí)行的五個階段中間各加了個寄存器記錄流過的數(shù)據(jù)。22如圖所示，加法指令后面的取字指令沒有等到加法指令寫回R1后再執(zhí)行，而是提前就獲得了R1的數(shù)據(jù)，減少了等待時間。 時 間 （ 時 鐘 周 期 ） 1 2 3 4 5 6 IM Reg ALU DM Re

10、g IM Reg ALU DM Reg IM Reg ALU DM IM Reg ALU ADD R1， R2， R3 SUB R4， R1， R5 XOR R6， R1， R7 AND R8，R1，R9 IM Reg OR R10， R1， R11 23轉發(fā)技術不能解決所有的數(shù)據(jù)冒險當一條指令試圖讀取一個由前一條裝載指令讀入的寄存器時，就無法使用轉發(fā)解決數(shù)據(jù)冒險問題了。24v對于裝載指令的存在，我們采用了插入阻塞（氣泡，）方法解決問題。增加一個冒險檢測單元，一旦發(fā)現(xiàn)裝載指令后就在其他需要這個結果的指令前插入阻塞。直到可以使用轉發(fā)技術或指令可以得到結果為止。25編譯器調度（靜態(tài)調度）v插入阻塞

11、對于流水線來說仍然是暫停了流水線的執(zhí)行。既然轉發(fā)技術無法消除指令序列中所包含的這種暫停，那么能否讓編譯器在進行代碼生成時就消除這些潛在的暫停呢？ v實際上，編譯器的確可以通過重新組織代碼順序來消除這種暫停。通常稱這種重新組織代碼順序消除暫停的技術為 指令調度（instruction scheduling）。v原理：相關不一定引起阻塞，只要隔開足夠遠在一個流水線上引起阻塞，在另一個流水線上不一定引起阻塞，編譯優(yōu)化與機器有關26 例例1 請為下列表達式生成沒有暫停的流水線請為下列表達式生成沒有暫停的流水線v 指令序列：指令序列：v abc ；v def ；v 假設載入延遲為假設載入延遲為1個時鐘周

12、期。個時鐘周期。兩條ALU指令（ADD Ra，Rb，Rc 和 SUB Rd，Re，Rf）分別和兩條Load指令（LW Rc，c和LW Rf，f）之間存在數(shù)據(jù)相關。為了保證流水線正確執(zhí)行調度前的指令序列，必須在指令執(zhí)行過程中插入兩個時鐘周期的暫停。但是考察調度后的指令序列不難發(fā)現(xiàn)，由于流水線允許轉發(fā)，就不必在指令執(zhí)行過程中插入任何暫停周期。 27LD RbLD Rb，B BIFIFIDIDEXEXMEMEM MWBWBLD RcLD Rc，C CIFIFIDIDEXEX MEMMEM WBWBADD RaADD Ra，RbRb，RcRc IFIFIDID 停停EXEX MEMMEM WBWBSD

13、 RaSD Ra，A AIFIF 停停IDIDEXEX MEMMEM WBWBLD ReLD Re，E EIFIFIDIDEXEX MEMMEM WBWBLD RfLD Rf，F(xiàn) FIFIFIDIDEXEX MEMMEM WBWBSUB RdSUB Rd，ReRe，RfRfIFIFIDID停停EXEX MEMMEM WBWBSD RdSD Rd，D D IFIF停停IDIDEXEX MEMMEM WBWB調度前執(zhí)行情況（采用了轉發(fā)技術）28LD RbLD Rb，B BIFIFIDIDEXEX MEMMEM WBWBLD RcLD Rc，C CIFIFIDIDEXEX MEMMEM WBWBLD

14、 ReLD Re，E EIFIFIDIDEXEX MEMMEM WBWBADD RaADD Ra，RbRb，RcRcIFIFIDIDEXEX MEMMEM WBWBLD RfLD Rf，F(xiàn) FIFIFIDIDEXEX MEMMEM WBWBSD RaSD Ra，A AIFIFIDIDEXEX MEMMEM WBWBSUB RdSUB Rd，ReRe，RfRfIFIFIDIDEXEX MEMMEM WBWBSD RdSD Rd，D D IFIFIDIDEXEX MEMMEM WBWB調度后執(zhí)行情況（采用了轉發(fā)技術）29動態(tài)調度v有些信息在譯碼時難以確定，如是否發(fā)生異常、訪存操作需要多少周期等，靜

15、態(tài)調度就不能完成。v動態(tài)調度：硬件會重新安排指令的執(zhí)行順序以減少停頓并同時保持數(shù)據(jù)流和異常行為。v優(yōu)點：有些相關編譯無法檢測、編譯器更加簡單、程序性能對機器依賴少30動態(tài)調度的思想v基本思想 ：把相關的解決盡量延遲到馬上就會出錯的時候 前面指令的stall不影響后面指令繼續(xù)前進v把譯碼分成兩個階段：發(fā)射和讀操作數(shù) 發(fā)射：指令譯碼，檢查結構相關 讀操作數(shù)：檢查操作數(shù)是否準備好，準備好就 讀數(shù)，否則等待，當一條指令在讀操作數(shù)階段 等待時，后面指令的發(fā)射可以繼續(xù)進行v亂序執(zhí)行： 指令進入是有序的 執(zhí)行可以亂序，只要沒有相關就可執(zhí)行，多條 指令同時執(zhí)行 結束可以亂序，也可以有序（主要是精確例外 的需要

16、），亂序結束會導致WAR相關（靜態(tài) 流水線中只有RAW和WAW相關）31Tomasulo算法vIBM 360/91中首次使用，由Robert Tomasulo提出的一種支持亂序執(zhí)行的高級方案。它會跟蹤指令的操作數(shù)何時可用，將RAW冒險降至最低，并在硬件中引入寄存器重命名功能，將WAW和WAR冒險降至最低。v現(xiàn)代處理器使用了該算法的各種變體，但是核心都是： 1.跟蹤指令相關以允許在操作數(shù)可用時立即執(zhí)行指令。 2.重命名寄存器以避免WAR和WAW冒險。3233Tomasulo算法的流水階段 1.發(fā)射：把操作隊列的指令根據(jù)操作類型送到保留站（如果保留站有空），發(fā)射過程中讀寄存器的值和結果狀態(tài)域 2.

17、執(zhí)行：如果所需的操作數(shù)都準備好，則執(zhí)行，否則偵聽結果總線并接收結果總線的值。 3.寫回：把結果送到結果總線，釋放保留站343536373839Tomasulo算法小結v通過動態(tài)調度緩解流水線阻塞：例如減少CACHE失效對性能的影響v保留站：重命名寄存器+緩存源操作數(shù) 避免寄存器成為瓶頸 避免WAW和WAR阻塞v缺點： 硬件復雜性 結果總線成為瓶頸，多條結果總線增加硬件復雜度40 流水線技術一直是提高處理器速度的最有效技術之一。但目前的在相關處插入阻塞，轉發(fā)技術，編譯器調度都是盡量分離相關問題的指令，使他們不會導致沖突，從而減少暫停的影響。雖然都會相應的顯著減少數(shù)據(jù)相關的次數(shù)提高流水效率，但也會

18、不可避免的增加硬件復雜度和編譯器的復雜性。 而動態(tài)調度則可以以硬件的方式調整指令執(zhí)行順序，使不相關的后續(xù)指令得以不受暫停的影響而繼續(xù)執(zhí)行，可以在降低編譯器復雜度的同時處理一些編譯階段無法知道的相關，在出現(xiàn)數(shù)據(jù)冒險是盡量避免出現(xiàn)流水暫停。412.5 控制冒險v也叫分支冒險，指因為程序的執(zhí)行方向可能被改變而引起的流水線暫停叫做控制冒險。 v執(zhí)行分支指令，程序計數(shù)器PC值兩種情況：PC值改變?yōu)槟繕说刂罚ㄞD移成功）PC值保持正常（轉移失敗，順序執(zhí)行），PC+4。vPC值不定，所以流水線需要暫停，直到確定了新的PC值為止42由于分支指令在MEM階段才確定是否執(zhí)行分支，分支后面的三個指令都要被取回并執(zhí)行。

19、432.6 控制冒險的解決辦法v1. 處理分支指令最簡單的方法:v一旦檢測到分支指令(在ID段)，就暫停執(zhí)行其后的指令，直到分支指令到達MEM段，確定出新的PC值為止。v特點：簡單但是速度非常慢。44v2.縮短分支延遲v確定分支目標地址越早，需要清除的指令就越少。將分支執(zhí)行提前到ID級。v首先計算分支目標地址：在IF/ID流水線寄存器中就有了PC值和立即數(shù)，增加一個加法器就可以得到目標地址。v分支判斷：判斷從ID級取到的兩個寄存器的值是否相等，對應的位進行異或操作即可。45v3.延遲分支：把分支開銷為n 的分支指令看成是延遲長度為n 的分支指令，其后緊跟有n 個延遲槽。流水線遇到分支指令時，按正常方式處理，順帶執(zhí)行延遲槽中的指令（不影響分支的一條指令），從而減少分支開銷。v特點：對于每個時鐘周期發(fā)射一條指令的五級流水線處理器而言，延遲分支簡單有效。但是隨著處理器向著更深流水線發(fā)展和單周期多指令方向發(fā)展。延遲分支作用不大。46v4.預測分支不發(fā)生v假設分式不發(fā)生，繼續(xù)執(zhí)行順序的指令流。如果分支發(fā)生了，就丟棄已經(jīng)讀取并譯碼的指令，按照分支目標繼續(xù)執(zhí)行。v特點：如果分支發(fā)生的可能性較大，并且丟棄指令的代價很小的話，這種優(yōu)化方法可以減小