流水線(Pipeline)介紹

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

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

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

4、構(gòu)中只有一個(gè)存儲器時(shí)，兩條指令同時(shí)在一個(gè)存儲器中預(yù)取指令就會發(fā)生結(jié)構(gòu)冒險(xiǎn)。12為消除資源沖突而插入的流水線氣泡（Bubble） 時(shí)時(shí)間間（時(shí)時(shí)鐘鐘周周期期） 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è)置相互獨(dú)立的指令存儲器和數(shù)據(jù)存儲器或設(shè)置相互獨(dú)立的指令Cache和數(shù)據(jù)Cache。 IM Reg ALU DM Reg IF 段段 ID 段段 E

5、X段段 MEM 段段 WB 段段 流水線寄存器流水線寄存器 142.3 數(shù)據(jù)冒險(xiǎn)v一條指令必須等到另一條指令的完成而造成的流水線暫停的情況叫做數(shù)據(jù)冒險(xiǎn)。形如： add $s0, $t0, $t0 sub $t2, $s0 $t3 加法指令需要到WB階段后才寫回結(jié)果，減法指令此時(shí)才可以繼續(xù)執(zhí)行。在不任何干預(yù)的情況下，流水線白白浪費(fèi)了三個(gè)時(shí)鐘周期。15 時(shí)間（時(shí)鐘周期） 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階段寫回?cái)?shù)據(jù)后才可以執(zhí)行。162.4 數(shù)據(jù)冒險(xiǎn)的解決辦法v根據(jù)指令中讀寫訪問的順序，可以將數(shù)據(jù)冒險(xiǎn)分為三類。分別是:v寫后讀（RAW）v寫后寫 (WAW)v讀后寫 (WAR) 17寫后讀冒險(xiǎn)（RAW: Read After Write）v在 i 寫入之前，j 先去讀。j 會錯(cuò)誤的獲取舊值。v這對應(yīng)“真數(shù)據(jù)相關(guān)”，為了確保j可以得到正確的i值，必須保持程序的順序。i: DSUB R1,R2,R3j: DADD R4,R1,R318寫后寫沖突（WAW: Wr

7、ite After Write）v在 i 寫入之前，j 先寫。最后寫入的結(jié)果 i 是錯(cuò)誤的。v這對應(yīng)“輸出相關(guān)”，寄存器換名技術(shù)可以消除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 讀出的內(nèi)容是錯(cuò)誤的！v這對應(yīng)“反相關(guān)” ，寄存

8、器換名技術(shù)可以消除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ù)冒險(xiǎn)，讀操作不改變值20轉(zhuǎn)發(fā)（旁路）方式解決數(shù)據(jù)冒險(xiǎn) 形如：add $s0, $t0, $t0 sub $t2, $s0 $t3，減法指令要等到加法指令寫回寄存器堆時(shí)才可

9、以執(zhí)行指令，浪費(fèi)了時(shí)間。轉(zhuǎn)發(fā)技術(shù)：在加法指令在ALU運(yùn)算一結(jié)束就將結(jié)果送給減法指令的輸入項(xiàng)。這樣從內(nèi)部資源中直接提前得到缺少的運(yùn)算項(xiàng)的過程叫做轉(zhuǎn)發(fā)。21 在原始的數(shù)據(jù)通路中用流水線寄存器將流水線各部分分開，這些寄存器可以存儲所有穿過它的數(shù)據(jù)，寄存器的寬度都足夠大。目前流行的有128位，97位，64位。 有了流水線寄存器后，轉(zhuǎn)發(fā)就變的簡單了。在指令執(zhí)行的五個(gè)階段中間各加了個(gè)寄存器記錄流過的數(shù)據(jù)。22如圖所示，加法指令后面的取字指令沒有等到加法指令寫回R1后再執(zhí)行，而是提前就獲得了R1的數(shù)據(jù)，減少了等待時(shí)間。 時(shí) 間 （ 時(shí) 鐘 周 期 ） 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轉(zhuǎn)發(fā)技術(shù)不能解決所有的數(shù)據(jù)冒險(xiǎn)當(dāng)一條指令試圖讀取一個(gè)由前一條裝載指令讀入的寄存器時(shí)，就無法使用轉(zhuǎn)發(fā)解決數(shù)據(jù)冒險(xiǎn)問題了。24v對于裝載指令的存在，我們采用了插入阻塞（氣泡，）方法解決問題。增加一個(gè)冒險(xiǎn)檢測單元，一旦發(fā)現(xiàn)裝載指令后就在其他需要這個(gè)結(jié)果的指令前插入阻塞。直到可以使用轉(zhuǎn)發(fā)技術(shù)或指令可以得到結(jié)果為止。25編譯器調(diào)度（靜態(tài)調(diào)度）v插入阻塞

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

12、期。個(gè)時(shí)鐘周期。兩條ALU指令（ADD Ra，Rb，Rc 和 SUB Rd，Re，Rf）分別和兩條Load指令（LW Rc，c和LW Rf，f）之間存在數(shù)據(jù)相關(guān)。為了保證流水線正確執(zhí)行調(diào)度前的指令序列，必須在指令執(zhí)行過程中插入兩個(gè)時(shí)鐘周期的暫停。但是考察調(diào)度后的指令序列不難發(fā)現(xiàn)，由于流水線允許轉(zhuǎ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調(diào)度前執(zhí)行情況（采用了轉(zhuǎn)發(fā)技術(shù)）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調(diào)度后執(zhí)行情況（采用了轉(zhuǎn)發(fā)技術(shù)）29動態(tài)調(diào)度v有些信息在譯碼時(shí)難以確定，如是否發(fā)生異常、訪存操作需要多少周期等，靜

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

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

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

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

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