處理器流水線的概念和相關(guān)技術(shù)

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

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

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

4、消除資源沖突而插入的流水線氣泡（Bubble）13解決辦法二設(shè)置相互獨立的指令存儲器和數(shù)據(jù)存儲器或設(shè)置相互獨立的指令Cache和數(shù)據(jù)Cache。142.3 數(shù)據(jù)冒險一條指令必須等到另一條指令的完成而造成的流水線暫停的情況叫做數(shù)據(jù)冒險。形如： add $s0, $t0, $t0 sub $t2, $s0 $t3 加法指令需要到WB階段后才寫回結(jié)果，減法指令此時才可以繼續(xù)執(zhí)行。在不任何干預(yù)的情況下，流水線白白浪費了三個時鐘周期。15AND,OR操作不會暫停，但是DSUB,XOR指令需要等待DADD在WB階段寫回數(shù)據(jù)后才可以執(zhí)行。162.4 數(shù)據(jù)冒險的解決辦法根據(jù)指令中讀寫訪問的順序，可以將數(shù)據(jù)冒險

5、分為三類。分別是:寫后讀（RAW）寫后寫 (WAW)讀后寫 (WAR) 17寫后讀冒險（RAW: Read After Write）在 i 寫入之前，j 先去讀。j 會錯誤的獲取舊值。這對應(yīng)“真數(shù)據(jù)相關(guān)”，為了確保j可以得到正確的i值，必須保持程序的順序。i: DSUB R1,R2,R3j: DADD R4,R1,R318寫后寫沖突（WAW: Write After Write）在 i 寫入之前，j 先寫。最后寫入的結(jié)果 i 是錯誤的。這對應(yīng)“輸出相關(guān)”，寄存器換名技術(shù)可以消除i: DSUB R1,R4,R3 j: DADD R1,R2,R3k: DMUL R6,R1,R7Cant happe

6、n in MIPS 5 stage pipeline because: - All instructions take 5 stages, and - Writes are always in stage 519讀后寫沖突（WAR: Write After Read）在 i 讀之前，j 先寫。i 讀出的內(nèi)容是錯誤的！這對應(yīng)“反相關(guān)” ，寄存器換名技術(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

7、stages, and- Reads are always in stage 2, and - Writes are always in stage 5讀后讀RAR不是數(shù)據(jù)冒險，讀操作不改變值20轉(zhuǎn)發(fā)（旁路）方式解決數(shù)據(jù)冒險 形如：add $s0, $t0, $t0 sub $t2, $s0 $t3，減法指令要等到加法指令寫回寄存器堆時才可以執(zhí)行指令，浪費了時間。轉(zhuǎn)發(fā)技術(shù)：在加法指令在ALU運算一結(jié)束就將結(jié)果送給減法指令的輸入項。這樣從內(nèi)部資源中直接提前得到缺少的運算項的過程叫做轉(zhuǎn)發(fā)。21 在原始的數(shù)據(jù)通路中用流水線寄存器將流水線各部分分開，這些寄存器可以存儲所有穿過它的數(shù)據(jù)，寄存器的寬度都足

8、夠大。目前流行的有128位，97位，64位。 有了流水線寄存器后，轉(zhuǎn)發(fā)就變的簡單了。在指令執(zhí)行的五個階段中間各加了個寄存器記錄流過的數(shù)據(jù)。22如圖所示，加法指令后面的取字指令沒有等到加法指令寫回R1后再執(zhí)行，而是提前就獲得了R1的數(shù)據(jù)，減少了等待時間。 23轉(zhuǎn)發(fā)技術(shù)不能解決所有的數(shù)據(jù)冒險當(dāng)一條指令試圖讀取一個由前一條裝載指令讀入的寄存器時，就無法使用轉(zhuǎn)發(fā)解決數(shù)據(jù)冒險問題了。24對于裝載指令的存在，我們采用了插入阻塞（氣泡，）方法解決問題。增加一個冒險檢測單元，一旦發(fā)現(xiàn)裝載指令后就在其他需要這個結(jié)果的指令前插入阻塞。直到可以使用轉(zhuǎn)發(fā)技術(shù)或指令可以得到結(jié)果為止。25編譯器調(diào)度（靜態(tài)調(diào)度）插入阻塞對

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

10、）分別和兩條Load指令（LW Rc，c和LW Rf，f）之間存在數(shù)據(jù)相關(guān)。為了保證流水線正確執(zhí)行調(diào)度前的指令序列，必須在指令執(zhí)行過程中插入兩個時鐘周期的暫停。但是考察調(diào)度后的指令序列不難發(fā)現(xiàn)，由于流水線允許轉(zhuǎn)發(fā)，就不必在指令執(zhí)行過程中插入任何暫停周期。 27LD Rb，BIFIDEXMEMWBLD Rc，CIFIDEXMEMWBADD Ra，Rb，Rc IFID停EXMEMWBSD Ra，AIF停IDEXMEMWBLD Re，EIFIDEXMEMWBLD Rf，F(xiàn)IFIDEXMEMWBSUB Rd，Re，RfIFID停EXMEMWBSD Rd，D IF停IDEXMEMWB調(diào)度前執(zhí)行情況（采用

11、了轉(zhuǎn)發(fā)技術(shù)）28LD Rb，BIFIDEXMEMWBLD Rc，CIFIDEXMEMWBLD Re，EIFIDEXMEMWBADD Ra，Rb，RcIFIDEXMEMWBLD Rf，F(xiàn)IFIDEXMEMWBSD Ra，AIFIDEXMEMWBSUB Rd，Re，RfIFIDEXMEMWBSD Rd，D IFIDEXMEMWB調(diào)度后執(zhí)行情況（采用了轉(zhuǎn)發(fā)技術(shù)）29動態(tài)調(diào)度有些信息在譯碼時難以確定，如是否發(fā)生異常、訪存操作需要多少周期等，靜態(tài)調(diào)度就不能完成。動態(tài)調(diào)度：硬件會重新安排指令的執(zhí)行順序以減少停頓并同時保持?jǐn)?shù)據(jù)流和異常行為。優(yōu)點：有些相關(guān)編譯無法檢測、編譯器更加簡單、程序性能對機(jī)器依賴少30

12、動態(tài)調(diào)度的思想基本思想 ：把相關(guān)的解決盡量延遲到馬上就會出錯的時候 前面指令的stall不影響后面指令繼續(xù)前進(jìn)把譯碼分成兩個階段：發(fā)射和讀操作數(shù) 發(fā)射：指令譯碼，檢查結(jié)構(gòu)相關(guān) 讀操作數(shù)：檢查操作數(shù)是否準(zhǔn)備好，準(zhǔn)備好就 讀數(shù)，否則等待，當(dāng)一條指令在讀操作數(shù)階段 等待時，后面指令的發(fā)射可以繼續(xù)進(jìn)行亂序執(zhí)行： 指令進(jìn)入是有序的 執(zhí)行可以亂序，只要沒有相關(guān)就可執(zhí)行，多條 指令同時執(zhí)行 結(jié)束可以亂序，也可以有序（主要是精確例外 的需要），亂序結(jié)束會導(dǎo)致WAR相關(guān)（靜態(tài) 流水線中只有RAW和WAW相關(guān)）31Tomasulo算法IBM 360/91中首次使用，由Robert Tomasulo提出的一種支持亂

13、序執(zhí)行的高級方案。它會跟蹤指令的操作數(shù)何時可用，將RAW冒險降至最低，并在硬件中引入寄存器重命名功能，將WAW和WAR冒險降至最低?，F(xiàn)代處理器使用了該算法的各種變體，但是核心都是： 1.跟蹤指令相關(guān)以允許在操作數(shù)可用時立即執(zhí)行指令。 2.重命名寄存器以避免WAR和WAW冒險。3233Tomasulo算法的流水階段 1.發(fā)射：把操作隊列的指令根據(jù)操作類型送到保留站（如果保留站有空），發(fā)射過程中讀寄存器的值和結(jié)果狀態(tài)域 2.執(zhí)行：如果所需的操作數(shù)都準(zhǔn)備好，則執(zhí)行，否則偵聽結(jié)果總線并接收結(jié)果總線的值。 3.寫回：把結(jié)果送到結(jié)果總線，釋放保留站343536373839Tomasulo算法小結(jié)通過動態(tài)調(diào)

14、度緩解流水線阻塞：例如減少CACHE失效對性能的影響保留站：重命名寄存器+緩存源操作數(shù) 避免寄存器成為瓶頸 避免WAW和WAR阻塞缺點： 硬件復(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ù)提高流水效率，但也會不可避免的增加硬件復(fù)雜度和編譯器的復(fù)雜性。 而動態(tài)調(diào)度則可以以硬件的方式調(diào)整指令執(zhí)行順序，使不相關(guān)的后續(xù)指令得以不受暫停的影響而繼續(xù)執(zhí)行，可以在降低編譯器復(fù)雜度的同時處理一些編譯階段

15、無法知道的相關(guān)，在出現(xiàn)數(shù)據(jù)冒險是盡量避免出現(xiàn)流水暫停。412.5 控制冒險也叫分支冒險，指因為程序的執(zhí)行方向可能被改變而引起的流水線暫停叫做控制冒險。 執(zhí)行分支指令，程序計數(shù)器PC值兩種情況：PC值改變?yōu)槟繕?biāo)地址（轉(zhuǎn)移成功）PC值保持正常（轉(zhuǎn)移失敗，順序執(zhí)行），PC+4。PC值不定，所以流水線需要暫停，直到確定了新的PC值為止42由于分支指令在MEM階段才確定是否執(zhí)行分支，分支后面的三個指令都要被取回并執(zhí)行。432.6 控制冒險的解決辦法1. 處理分支指令最簡單的方法:一旦檢測到分支指令(在ID段)，就暫停執(zhí)行其后的指令，直到分支指令到達(dá)MEM段，確定出新的PC值為止。特點：簡單但是速度非常慢

16、。442.縮短分支延遲確定分支目標(biāo)地址越早，需要清除的指令就越少。將分支執(zhí)行提前到ID級。首先計算分支目標(biāo)地址：在IF/ID流水線寄存器中就有了PC值和立即數(shù)，增加一個加法器就可以得到目標(biāo)地址。分支判斷：判斷從ID級取到的兩個寄存器的值是否相等，對應(yīng)的位進(jìn)行異或操作即可。453.延遲分支：把分支開銷為n 的分支指令看成是延遲長度為n 的分支指令，其后緊跟有n 個延遲槽。流水線遇到分支指令時，按正常方式處理，順帶執(zhí)行延遲槽中的指令（不影響分支的一條指令），從而減少分支開銷。特點：對于每個時鐘周期發(fā)射一條指令的五級流水線處理器而言，延遲分支簡單有效。但是隨著處理器向著更深流水線發(fā)展和單周期多指令方

17、向發(fā)展。延遲分支作用不大。464.預(yù)測分支不發(fā)生假設(shè)分式不發(fā)生，繼續(xù)執(zhí)行順序的指令流。如果分支發(fā)生了，就丟棄已經(jīng)讀取并譯碼的指令，按照分支目標(biāo)繼續(xù)執(zhí)行。特點：如果分支發(fā)生的可能性較大，并且丟棄指令的代價很小的話，這種優(yōu)化方法可以減小控制冒險的損失。475. 預(yù)測分支成功 假設(shè)分支轉(zhuǎn)移成功，并開始從分支目標(biāo)地址處取指令執(zhí)行。 起作用的前題：先知道分支目標(biāo)地址，后知道分支是否成功。特點：因為在5段流水線中總是先得到轉(zhuǎn)移的結(jié)果，后得到目標(biāo)的地址，所以不適用于5段流水。適合那些隱含條件碼和更強(qiáng)功能轉(zhuǎn)移條件的機(jī)器中，轉(zhuǎn)移的目標(biāo)地址比其結(jié)果更早產(chǎn)生，這時采用預(yù)測轉(zhuǎn)移被選中的方法比較合適。486.動態(tài)分支預(yù)測：假設(shè)分支是否發(fā)生是一種粗略的預(yù)測分支方法。一種策略是通過查找指令的地址觀察上一次執(zhí)行該指令時分支是否發(fā)生，如果上次執(zhí)行時分支發(fā)生就從上次分支發(fā)生的地方開始取新的指令，這種技術(shù)叫做動態(tài)分支預(yù)測。實現(xiàn)方式：使用分支預(yù)測緩存或分支歷史記錄表。緩存是一小塊按照分支指令的地址地位索引的存儲器區(qū)，包括了一位或多位數(shù)據(jù)用以說明最近是否發(fā)生過分支。特點