浅谈指令流水线
??指令流水線作為計算機組成原理中一個重要的組成部分，弄清指令流水線的操作步驟對制作CPU有著很大的幫助。本文主要講述下指令流水線的相關知識。
??指令流水線是較單周期指令和多周期指令更有效率的一種方式。指令流水線并沒有減少每條指令執行的時間，反而可能增加一定的時間（原因下文解釋），指令流水線改變的是指令的吞吐量，從而加快指令的執行速率。對于指令流水線的介紹可分為三部分：數據通路設計、控制器設計、冒險處理。本文先以緒論為引導，再以三部分為主線，介紹指令流水線。
??注：作者學習的教材是《計算機組成與系統結構（第二版）》由袁春風老師主編，清華大學出版社出版。本書中設計的指令體系結構是MIPS體系結構，本文所有內容都是圍繞MIPS體系結構進行介紹。
緒論：
?? 先介紹一下什么是流水線？
??在此舉一個簡單的例子（一看就懂）：洗衣服分為三步：洗、烘干、疊。三部分都有獨立的三臺機器進行操作。所謂流水線就是當第一批衣服洗完進入烘干時，可以放第二批衣服進入洗的環節。因為各個步驟相互獨立，不會有影響。等到第一批衣服進入疊的環節時，第二批衣服進入烘干，第三批衣服進入洗的環節。確保了在絕大多數時間，三臺機器在同時工作。提高了吞吐率，這個方法就叫做流水線。流水線的名字因三個環節叫做三級流水線。
??再介紹一下為什么指令可適用于流水線？
??在執行指令的過程中，可將過程拆分為5個步驟：取指、譯碼、取操作數、計算、寫回。這五個步驟分別可有不同的部件進行實施，滿足了流水線的基本要求。既然流水線可提高指令的執行速度，那何樂而不為呢？
??再解釋一下為什么指令流水線可能增加每條指令的執行時間？
??在流水線設計中，為達到吞吐量提高的目的，在同一時間段不同部件執行不同的命令。這對部件執行的規整性提出了要求，所謂規整性就是任何部件完成任何一個操作的時間都是相同的。類似于短板效應的原理，每個階段的時間都要選擇最長的，加起來單條指令的時間就多了起來。
數據通路設計：
??根據單周期指令的執行和MIPS體系結構的特點可知，在所有指令中load指令包含5個步驟，使用時間最長。故以其為基礎設計五級流水線。
??五級流水線數據通路基本框架如下圖（以下將對此圖進行介紹，以理解數據通路的設計）：
??對該圖做一個基本的介紹：上文說過五級流水線分為五個步驟，體現在圖中即為IF、ID、EX、Mem、Wr五階段。在每兩個階段之間有長方形（例如IF/ID,ID/EX等）代表流水段寄存器，記錄上階段傳入下階段的一些數據和控制信息。本圖中控制信息使用虛直線代表。為了更好的執行指令，使用時鐘周期的方式統一控制，寫操作發生在時鐘周期的下降沿。
??下面分別對五個階段進行介紹：
1)Ifetch(IF)段：
??IF段主要內容是進行取指操作，集成在取指令部件IUnit進行。指令取出后需要改變PC的值，順序情況下PC直接加4或者加1（取決于是以字節編址還是以字編址，以字編址加1，以字節編址加4。因為一個字等于四個字節）。但在branch和jump指令中PC需要跳轉，則PC加4后直接改變為跳轉的地址。
??如上圖，進入PC的地址由一多路選擇器決定來源，正常指令使用PC+4，branch或jump使用額外指定地址。
??解釋IUnit通往IF/ID流水段寄存器兩條線的意義：第一條線保存的是PC+4的地址，第二條線保存的是取出的指令。
??在此解釋一下保存PC+4的原因：在大部分情況中，beq指令用于函數調用，函數調用過后需要返回原來跳轉的位置繼續執行下面的內容，所以提前保存PC+4的值，保證跳轉后還能回到原位置。
1） Reg/Dec(ID)段:
??ID段進行指令的譯碼，以及取操作數。根據不同類型的指令（R型，I型，J型）對指令進行切分，從不同的位置得到操作數地址。這里的操作數地址理解為操作數所在寄存器的編號。
??如上圖，RFile代表寄存器組，在MIPS體系結構中共32個寄存器。所以Rs、Rt、Rd都是用5位表示（2^5 = 32）
??解釋各條線的含義：譯碼結束后，已知指令類型操作數位置。PC+4原因與IF段相同，imm16用于I型指令時，Rs和Rt(上面的)，用于R型指令，從寄存器組中取出兩個源操作數，目的地址Rd需要等指令執行完之后采用，先傳入下一流水段寄存器。Rt(下面的)代表I型指令的目的寄存器，指令執行完采用，所以傳入下一流水段寄存器。Rw、Di、WE是Wr階段才用到，后面進行解釋。
??目前為止，ID/EX流水段寄存器中包含操作數，并且已知操作類型，下一步可進行指定操作的計算。
3） Exec(EX)段：
??本段主要進行運算，不同指令操作數的源地址不同。
??如上圖，Exec Unit是運算執行部件。不單單是一個加法器（因為會支持or/and等操作）
??依次解釋各線的內容：（Exec Unit左，從上到下）PC+4內容與IF段相同。無論I型還是R型busA的來源是相同的（指令中的rs）,但對于busB來說I型來源是imm16經過擴展和的結果，R型是之前的rt地址中取出的操作數，這個會通過多選器進行選擇。RegDst是經過ALU計算后的目的地址，R型指令送到rd中，I型指令送到rt中，二者選其一放入Ex/Mem流水段寄存器。（Exec Unit右，從上到下）PC+4依舊，第二根是zero信號用于判斷是否進行branch跳轉。第三根是16位立即數，無論是branch跳轉還是jump都需要對16位立即數做修改得到跳轉地址。第四根代表ALU運算的結果。busB引出一根進入Ex/Mem流水段寄存器是為了在sw指令中，busB輸出的是需要存入存儲器的數據。
4）Mem段
??關于Mem段是訪問存儲器，在MIPS中，只有sw/sh/sb/lw/lh/lb兩類指令可以訪問存儲器，在其他類型指令中是不需要有這步的。為了規整性設計，在數據通路設計中也設計了旁路。
??解釋一下各線的內容：Data Mem左側第一根線是寫回的PC+4。下面一根Zero代表是否為零，在beq指令中，只有zero信號有效（為1）才會跳轉。Overflow代表是否溢出，只有在有符號操作中才涉及是否溢出。例如在加法指令中可能存在操作數結果溢出的情況。這時需要引發異常。（對于異常的介紹不在本文的范圍內）RA/WA即為ALU運算的結果，作為讀/寫存儲器的讀地址/寫地址。Di是sw指令中待存的數據，Do是lw指令中待取的數據，與RA/WA相同，直接進入Mem/Wr流水段寄存器的線代表當指令是非訪存存儲器類型的時，ALU計算出的結果就是要寫到寄存器中的內容。下面兩個流水段寄存器之間的直達線代表的是上一階段選出的目的地址。
5） Wr段
??Wr段就是將得到的結果寫回寄存器，兩根線分別對應于寫回的數據訪存存儲器獲得還是通過ALU運算獲得。
控制器設計：
??帶控制器通路圖如下所示：
??流水線的控制器設計類似于單周期。控制信號的來源是指令，所以只有在指令譯碼后才會產生控制信號，也即在流水線前兩個階段的時候是沒有控制信號的，所有指令是通用的。控制信號在流水段寄存器中相互傳遞，并在合適的階段作用于數據通路的各個模塊，大多是各個模塊的多選器。可以簡化控制信號的傳遞過程如下圖：
??其中控制信號的全拼可在我另一篇博客中查看（網址為：https://blog.csdn.net/gls_nuaa/article/details/106200686）link
??在此對各個控制信號的作用地點做一下說明：
??ExtOp：當指令為I型/J型時，需要進行擴展。擴展分為兩類，分別是符號擴展和零擴展。在R型指令中不需要擴展。MIPS指令中只有andi/ori/xori需要進行零擴展，其余I型指令都是符擴展。
??ALUSrc：代表ALU操作數運算的來源，在R型指令中操作數來源于寄存器，I型指令中操作數來源于擴展器
??ALUOp：代表ALU運算的種類（加法/減法/異或/。。。），是ALU-control模塊的輸出。同時ALU-control模塊的來源是指令，對于I型指令來說是opcode(31:26)，對于R型指令來說需要結合funcode(5:0)。
??RegDst：代表結果存儲的位置，R型指令存于rd，I型指令存于rt。
??R-type：是否是R型指令，關乎到ALUOp等控制信號是否取決于后六位指令。
??MemWr：是否需要向存儲器中寫，在所有指令中只有sw類指令該控制信號有效（為1），其余都是無效（為0）
??Branch：Branch是由beq類信號決定，并結合zero信號，最終決定下個pc的數值。
??MemToReg：該信號是決定寫回寄存器數值的來源，來源分為兩種：由ALU計算得到或者從存儲器取得。
??RegWr：該信號決定是否向寄存器中寫，需要寫的時候為1，不需要寫的時候為0。
??值得注意的是在有些指令中，部分控制信號不起到作用（選哪個都可以）。這類控制信號可記為x，但在是否寫例如MemWr/ RegWr這種是必須嚴格決定是0或是1的。
冒險（沖突/Hazard）處理：
??如果說單周期相較于流水線有優勢的地方可能就是單周期不需要關注是否有冒險產生的問題。冒險可以理解為前后指令執行過程中與流水線結構所產生的沖突。大致分為三類：結構冒險、數據冒險、控制冒險。
1. 結構冒險：
??所謂結構冒險就是在同一時間，不同指令處于不同階段，但對寄存器/存儲器又讀又寫。（寄存器一臉懵：我到底該干嘛？）。如下圖所示：
??解決辦法：
???簡單的想法是：只要保證不在同一時間讀寫即可。可以通過優化指令的執行順序，讓指令之間在不同階段讀寫即可。但沒有一萬，也有萬一。萬一無法做出這樣的優化怎么辦呢？所以我們需要一種更為通用的辦法：將讀寫端口分開，在寄存器/存儲器設計中加入時鐘，在時鐘下降沿（前半周期）寫數據，上升沿（后半周期）讀數據。這樣就完美解決了二者之間的矛盾。而且一定要注意是先寫后讀。同時對于存儲器中劃分指令存儲器和數據存儲器也是為了解決結構冒險的問題。
2. 數據冒險
??下面舉一個例子引入數據冒險：
???add $t1 $t2 $t3
???sub $t4 $t1 $t2
??觀察這個例子，把2和3中相加，結果放到1中。再用1減去2，結果放在4中。根據我們對于流水線的簡單了解可以知道，指令只有在完成五個階段后（即Wr階段）才可以被寫回使用，但sub指令執行的時候，在Reg/Dec（第二個階段）就需要讀出1的值。在流水線中相鄰指令相差的是一個階段。如果不做處理，那么sub讀出的就會是1的舊值。那計算不就是錯了嘛！
??問題總會有解決的辦法，在MIPS中解決的辦法就是使用轉發/forwarding（也叫旁路/bypass）。轉發就是改動數據通路，提前將結果拿出做操作。
??轉發的原理如下：看上面的例子，在add指令執行過程中在Exe階段就已經算出1的新值。如果這個時候把結果移到Reg/Dec階段去執行sub指令。剛好滿足階段相差1的流水線特性。由于要實現過程轉發，就需要從硬件上解決問題。
??那么接下來的問題就轉移為了：什么時候使用轉發，并且如何控制轉發?
??如下圖所示，可能有兩種情況需要轉發（圖中的兩個add指令，分別是下面一條指令/兩條指令發生數據冒險），這個時候我們就可以使用轉發。但不同的需要階段決定了轉發的階段也不同。在綠色中ALU以后需要轉發，在紅色中可以ALU隔一個階段再轉發。
??以上解釋了轉發的兩種可能性，那么數據通路的設計就需要適應兩種可能性。當檢測到滿足轉發條件的時候，通過以上兩條通路進行轉發。
??那么問題來了:**轉發條件是什么呢?**下面一起來看看吧，對以上圖做以下標注（C1(a)/C1(b)/C2(a)/C2(b)）。如下圖所示:
??對于轉發檢測，可簡單做以下規定：
??如果本條指令源操作數和只上條指令的目的寄存器一樣，而與其他指令間無冒險關系，則有以下公式:
??如果本條指令源操作數和上條指令的目的寄存器一樣，且和上上條指令也有數據冒險沖突，則不轉發上上條指令的結果，那么有如下公式：
??但轉發是萬能的嗎？看看下面這個例子：
??轉發的克星：load-use冒險
???lw r3，100(r1)
???or r6，r3，r1
?? lw的目的寄存器是or操作的操作數寄存器。但lw指令中r3只有在mem階段（第四階段）之后才會得到。但or指令第二階段就需要。由前面的轉發可知轉發最多提前一個階段，所以在這種情況中光靠轉發是不行的。這種情況就叫Load-use冒險。解決的方法就是中間再引入一個阻塞（no
operation/bubble）來延遲一個周期再使用轉發。
3. 控制冒險
??所謂控制冒險是指在beq/jump等跳轉指令或異常指令中，在第四階段才能夠知道是否跳轉。不跳的話一切正常，跳的話后兩條指令都已經被讀入。需要被清空以執行跳轉后的指令。最簡單的方法是直接清空前面的流水段寄存器。（但是簡單的方法必定沒有效率）。由于控制冒險只發生在轉移指令中，所以可以通過分支預測的方法來判斷下一條指令是否是跳轉指令。如果符合跳轉指令則按照直接清空的方法處理。既然是預測，那么結果就會有兩種：預測正確和預測錯誤。
??分支預測分為兩種：靜態分支預測（也叫簡單分支預測）和動態分支預測。
??靜態分支預測：類似于轉發的思想，講分支指令提前。在譯碼階段的時候就直接判斷是否轉移，原因是此時已經知道指令是什么并結合運算可決定是否轉移。這樣降低了損失（3條指令減低為1條指令）。
??動態分支預測：記錄預測的結果，并結合之前的記錄和當前的指令預測結果改變預測下條指令的結果（類似于算法中動態規劃的填表思想，當前的操作受之前的結果影響）。
??動態分支預測可分為一位和兩位（當然還有多位，不過課本上只介紹了比較簡單的）
??一位分支預測是假定開始預測指令不轉移，如果預測正確則下條指令繼續保持該預測，若預測錯誤則下條指令預測相反的結果。對于預測失敗的指令，則從失敗的下條指令開始預測相反結果。狀態轉移圖如下：
??兩位分支預測是給兩次機會。錯了一次（第一次）先不變狀態，看再下一次（第二次）的情況，如果第二次仍是錯的那么就改變狀態，第二次是對的就恢復第一次的狀態。狀態轉移圖如下：
??在現實應用中，動態預測精度更高，得到更廣闊的應用。但不同處理器可能使用不同的動態預測方法（預測位數不同，如Pentium 4使用4位預測位）
??流水線的學習就告一段落，但學到的大多都是理想情況。關于各種特殊情況的處理，希望在以后的學習過程中慢慢完善。
ACKNOWLEAGEMENTS：
The author would like to thank Prof. Xiangping Bryce Zhai,a teacher of computer composition principles, for his careful teaching and Prof. Chunfeng Yuan for compiling excellent textbooks to enhance understanding.
本文作者水平有限，如有不足之處，請在下方評論區指正，謝謝！
新人創作打卡挑戰賽發博客就能抽獎！定制產品紅包拿不停！總結
