計算機系統(tǒng)結(jié)構(gòu)：第三章 流水線技術(shù)

1、第三章 流水線技術(shù)主要介紹：流水線的基本概念，包括流水線的基本概念和分類；流水線中的相關(guān)及其處理，包括流水線的結(jié)構(gòu)相關(guān)、數(shù)據(jù)相關(guān)和控制相關(guān)；向量的流水處理機，包括向量處理方式、向量的流水處理機結(jié)構(gòu)原理和主要技術(shù)。第三章 流水線技術(shù)流水線的基本概念流水線的基本概念 流水線技術(shù)，是指將一個重復(fù)的時序過程，成為分解若干個子過程，而每一個子過程都可有效地在其專用功能段上與其他子過程同時執(zhí)行。 描述流水線的工作過程，常采用時-空圖的方法。在時-空圖中，橫坐標(biāo)表示時間，從坐標(biāo)代表空間（即流水線的各段），圖中的數(shù)字代表各次任務(wù)在流水線中流動的過程。第三章 流水線技術(shù)流水線的基本概念浮點加法流水線求階差對階尾

2、數(shù)相加規(guī)格化入出tttt7654321765432176543217654321求階差對階尾數(shù)加規(guī)格化空間時間t10t9t8t7t6t5t4t3t2t1第三章 流水線技術(shù)流水線的基本概念流水線技術(shù)具有如下特點：（1）流水過程由多個相聯(lián)系的子過程組成，每個子過程稱為流水線的“極”或“段”。流水線的段數(shù)也稱為流水線的“深度”或“流水深度”。（2）每個子過程由專用的功能段實現(xiàn)。（3）各個功能段所需時間應(yīng)盡量相等，否則，時間長的功能段將成為流水線的瓶頸，會造成流水線的“堵塞”或“斷流”。這個時間一般為一個時鐘周期（拍）或一個機器周期。第三章 流水線技術(shù)流水線的基本概念流水線技術(shù)具有如下特點：（4）流水

3、線需要有“通過時間”（第一個任務(wù)流出結(jié)果所需的時間），在此之后，流水過程才進入穩(wěn)定工作狀態(tài)，每一個時鐘周期（拍）流出一個結(jié)果。（5）流水技術(shù)適合于大量重復(fù)的時序過程，只有輸入端能連續(xù)地提供任務(wù)，流水線的效率才能充分發(fā)揮。第三章 流水線技術(shù)流水線的基本概念流水線分類（1）單功能流水線與多功能流水線單功能流水線：只能完成一種固定功能的流水線。多功能流水線：流水線的各段可以進行不同的連接，從而使流水線在不同時間，或者在同一時間完成不同的功能。第三章 流水線技術(shù)流水線的基本概念輸入減階對階移位相加規(guī)格化相乘累加輸出12345678輸入1減階2對階移位3相加4規(guī)格化5輸出8輸入1相乘6累加7輸出8第三章

4、 流水線技術(shù)流水線的基本概念流水線分類（2）靜態(tài)流水線和動態(tài)流水線靜態(tài)流水線：在同一時間內(nèi)，流水線的各段只能按同一種功能的連接方式工作。動態(tài)流水線：在同一時間內(nèi)，當(dāng)某些段正在實現(xiàn)某種運算時，另一些段可以實現(xiàn)另一種運算。第三章 流水線技術(shù)流水線的基本概念靜態(tài)流水線四三二一n211n212n213n214n215四三二一6四三二一7三二一n218段號時間浮點加定點乘第三章 流水線技術(shù)流水線的基本概念動態(tài)流水線七七六五四三二一n211n212n213n214n215七六五四三二一6七六五四三二一7六五四三二一n218段號時間第三章 流水線技術(shù)流水線的基本概念流水線分類（3）部件級、處理機級和處理機間

5、流水部件級流水：運算操作流水線，把處理機的算術(shù)邏輯部件分段，為各種數(shù)據(jù)類型進行流水操作。處理機級流水：解釋指令的過程按照流水方式處理，重疊地解釋多條指令。處理機間流水：宏流水線，由兩個以上的處理機串行地對同一數(shù)據(jù)流進行處理，每個處理機完成一項任務(wù)。第三章 流水線技術(shù)流水線的基本概念宏流水線處理機1存儲器任務(wù)1處理機2存儲器任務(wù)1處理機n存儲器任務(wù)1數(shù)據(jù)流第三章 流水線技術(shù)流水線的基本概念流水線分類（4）標(biāo)量流水處理機和向量流水處理機標(biāo)量流水處理機：處理機不具有向量數(shù)據(jù)表示，僅對標(biāo)量數(shù)據(jù)進行流水處理。向量流水處理機：處理機具有向量數(shù)據(jù)表示，通過向量指令對向量的各元素進行流水處理。第三章 流水線技

6、術(shù)流水線的基本概念流水線分類（5）線性流水線和非線性流水線線性流水線：流水線的各段串行連接，沒有反饋回路。非線性流水線：流水線的各段除有串行連接的通路外，還有反饋回路，某些段還有可能被跳過。第三章 流水線技術(shù)流水線的基本概念非線性流水線S1S2S3S4入出第三章 流水線技術(shù)流水線的基本概念非線性流水線的調(diào)度 對于線性流水線而言，在執(zhí)行每個任務(wù)的過程中，每個任務(wù)只通過各段一次，所以每拍都可以送入一個新的任務(wù)進入流水線。 對于非線性流水線而言，一個任務(wù)在流水的過程中，可能會多次通過同一段或越過某些段，如果每拍向流水線送入一個新的任務(wù)，就會發(fā)生幾個任務(wù)爭用同一個功能段。所以要確定每隔多少拍送入一個新

7、的任務(wù)，這就是流水線調(diào)度。第三章 流水線技術(shù)流水線的基本概念單功能非線性流水線調(diào)度根據(jù)預(yù)約表進行調(diào)度拍號123456789段號12345第三章 流水線技術(shù)流水線的基本概念根據(jù)預(yù)約表得到延遲禁止表在上述例子中，每隔8拍輸入一個任務(wù)，就會爭用第1段，每隔1拍輸入一個任務(wù)，就會爭用第2段、第4段和第5段，每隔5拍或6拍輸入一個任務(wù)，就會爭用第2段。所以延遲禁止表為1，5，6，8。根據(jù)延遲禁止表確定初始沖突向量沖突向量的位數(shù)為一個任務(wù)通過流水線的拍數(shù)減1，上述例子中沖突向量的位數(shù)為8。初始沖突向量為（10110001）。第三章 流水線技術(shù)流水線的基本概念畫出流水線的狀態(tài)圖101100011011011

8、1101111011011101110111111初始狀態(tài)24374377277第三章 流水線技術(shù)流水線的基本概念 產(chǎn)生新的沖突向量：按當(dāng)前允許的拍數(shù)向流水線輸入新的任務(wù)后，下一個任務(wù)間隔多少拍輸入呢？這就需要產(chǎn)生新的沖突向量，當(dāng)前沖突向量右移特定的拍數(shù)之后再與初始沖突向量進行或操作，即得到新的沖突向量。右移的拍數(shù)是在當(dāng)前沖突向量的情況下，輸入新任務(wù)的間隔拍數(shù)。第三章 流水線技術(shù) DLX的基本流水線指令存儲器NPCPCIR寄存器ABImm符號位擴展MUXMUX=0？ALUoutputCondMUX數(shù)據(jù)存儲器LMDMUX41632取指令指令譯碼/取寄存器執(zhí)行/有效地址計算存儲器訪問寫回ADDAL

9、U第三章 流水線技術(shù) DLX的基本流水線DLX的一種簡單實現(xiàn)1. 取指令周期（IF）IRMemPCNPCPC+42. 指令譯碼/取寄存器周期（ID）ARegsIR6.10BRegsIR11.15Imm(IR16)16#IR16.31)第三章 流水線技術(shù) DLX的基本流水線3. 執(zhí)行/有效地址計算周期（EX）（1）存儲器訪問ALUoutputA+Imm（2）寄存器-寄存器ALU操作ALUoutputA op B（3）寄存器-立即值A(chǔ)LU操作ALUoutputA op Imm（4）分支操作ALUoutputNPC+ImmCond(A op 0)第三章 流水線技術(shù) DLX的基本流水線4. 存儲器訪問

10、/分支完成周期（MEM）（1）存儲器訪問操作LMDMemALUoutput或 MemALUoutputB（2）分支操作if (Cond) PCALUoutput else PCNPC第三章 流水線技術(shù) DLX的基本流水線5. 寫回周期（WB）（1）寄存器-寄存器型ALU指令RegsIR16.20ALUoutput（2）寄存器-立即值型ALU指令RegsIR11.15ALUoutput（3）Load指令RegsIR11.15LMD第三章 流水線技術(shù) DLX的基本流水線基本的DLX流水線時鐘周期123456789指令iIFIDEXMEMWB指令i+1IFIDEXMEMWB指令i+2IFIDEXME

11、MWB指令i+3IFIDEXMEMWB指令i+4IFIDEXMEMWB注意的問題：在指令重疊時，不存在任何流水線資源沖突問題，也就是確保流水線的各段不會在同一時鐘周期內(nèi)使用相同的數(shù)據(jù)通路資源。第三章 流水線技術(shù) DLX的基本流水線IMRegALUDMRegIMRegALUDMRegIMRegALUDMRegIMRegALUDMReg時間（時鐘周期）IMRegALUDMRegCC1CC2CC3CC4CC5CC6CC7CC8CC9程序執(zhí)行順序第三章 流水線技術(shù) DLX的基本流水線上圖的解釋：（1）同一個時鐘周期內(nèi)，每條指令所使用的功能單元不同，沒有資源沖突。（2）將指令存儲器（IM）和數(shù)據(jù)存儲器（

12、DM）分隔開，避免取指令操作和訪問數(shù)據(jù)操作之間存在訪問存儲器沖突。（3）流水線中的ID段和WB段都要使用存儲器文件：在ID段對寄存器文件讀，在WB段對寄存器文件寫。如果讀操作和寫操作對同一個寄存器進行，如何處理？（4）圖中沒有考慮PC，流水線為了在每個時鐘周期啟動一條新的指令，必須在每個時鐘完成PC值的增值操作，并保存增值后的PC值。第三章 流水線技術(shù) DLX的基本流水線上圖的解釋：（5）當(dāng)流水線執(zhí)行分支指令時，會出現(xiàn)新的問題。分支指令可能會改變PC的值，但是，只有在MEM段結(jié)束時才能完成改變PC值的操作。所以需要了解如何處理分支指令的問題。總之，前面所介紹的串行執(zhí)行的數(shù)據(jù)通路不適合流水執(zhí)行，

13、需要改進。第三章 流水線技術(shù) DLX的基本流水線指令存儲器PC寄存器符號位擴展MUXMUX=0？MUX數(shù)據(jù)存儲器MUX41632ADDALUIRIR6.10IR6.10IF/IDID/EXEX/MEMMEM/WB第三章 流水線技術(shù) DLX的基本流水線上圖說明：（1）PC值多路選擇器被移到了IF段，保證對PC值的寫操作只會在一個流水段內(nèi)出現(xiàn)，否則當(dāng)分支轉(zhuǎn)移成功的時候，流水線中兩條指令都會在不同的流水段寫PC值，從而發(fā)生寫沖突。（2）設(shè)置了一些流水線寄存器文件，其命名為IF/ID、ID/EX、EX/MEM、MEM/WB。如指令寄存器IR是IF/ID的一個域，記為IF/ID.IR。如果串行執(zhí)行中只設(shè)

14、置很少量的寄存器，那么這些寄存器中所保存的臨時值可能會被流水線中的其他指令所重寫。（3）流水線寄存器文件的作用。保存從一個流水線段傳送到下一個流水線段的所有數(shù)據(jù)和控制信息。第三章 流水線技術(shù) DLX的基本流水線上圖說明：（4）如何控制四個多路器。（a）IF段的多路器選擇增長以后的PC值還是選擇EX/MEM.NPC的值（分支的目標(biāo)地址）作為下一條指令的地址，該多路器由EX/MEM.cond來控制。（b）ALU輸入端的兩個多路器由ID/EX.IR所指出的指令類型來控制。上面一個ALU多路器的輸入由當(dāng)前指令是否為分支指令來確定，下面一個ALU多路器的輸入由當(dāng)前指令是R-R型ALU指令，還是其他類型的

15、指令來控制。（c）WB段的多路器是由在WB段的指令是Load指令還是ALU指令來控制。第三章 流水線技術(shù) DLX的基本流水線DLX流水線的每個流水線的操作1. IF段的操作IF/ID.IRMemPC;IF/ID.NPC,PC(if EX/MEM.cond EX/MEM.NPC else PC+4);2. ID段的操作ID/EX.ARegsIF/ID.IR6.11;ID/EX.B RegsIF/ID.IR11.15;ID/EX.NPCIF/ID.NPC; ID/EX.IRIF/ID.IR;ID/EX.Imm(IF/ID.IR16)16#IF/ID.IR16.31;第三章 流水線技術(shù) DLX的基本

16、流水線3. EX段操作ALU指令EX/MEM.IRID/EX.IR;EX/MEM.ALUoutputID/EX.A op ID/EX.B 或EX/MEM.ALUoutputID/EX.A op ID/EX.Imm；EX/MEM.cond0;Load/Store指令EX/MEM.IRID/EX.IR;EX/MEM.ALUoutputID/EX.A + ID/EX.Imm；第三章 流水線技術(shù) DLX的基本流水線分支指令 EX/MEM.ALUoutputID/EX.NPC + ID/EX.Imm; EX/MEM.cond(ID/EX.A op 0);4. MEM段操作ALU指令MEM/WB.IREX

17、/MEM.IR;MEM/WB.ALUoutputEX/MEM.ALUoutput;第三章 流水線技術(shù) DLX的基本流水線Load/Store指令MEM/WB.IREX/MEM.IR;MEM/WB.LMDMemEX/MEM.ALUoutput;或MemEX/MEM.ALUoutputEX/MEM.B;5. WB段操作ALU指令RegsMEM/WB.IR16.20MEM/WB.ALUoutput;或RegsMEM/WB.IR11.15MEM/WB.ALUoutput;Load/Store指令RegsMEM/WB.IR11.15MEM/WB.LMD;第三章 流水線技術(shù) DLX的基本流水線流水線性能分

18、析n4321n4321n4321n4321S1S2S3S4段時間123121nt0mt0(n-1)t0(m-1)t0TT流水第三章 流水線技術(shù) DLX的基本流水線一些概念：“通過時間”：mt0“排空時間”：(m-1)t0“流水時間”：T流水、流水線可以增加系統(tǒng)的吞吐率，但是它并不會減少每條指令總的執(zhí)行時間。第三章 流水線技術(shù) DLX的基本流水線流水線性能參數(shù)：1. 吞吐率單位時間內(nèi)流水線所完成的任務(wù)數(shù)或輸出結(jié)果的數(shù)量。（1）最大吞吐率TPmax流水線在連續(xù)流動達到穩(wěn)定狀態(tài)后所得到的吞吐率，如果流水線各段時間t都相等，即t=t0，則有： TPmax=1/t0。第三章 流水線技術(shù) DLX的基本流水

19、線s1s2s3s4123n123n123n123nt2=3t1=3t3=3t4=3t0ti(n-1)t2TPmax=1/3 t0s1s2s3s4段時間第三章 流水線技術(shù) DLX的基本流水線s1S2-1s3s4S2-2S2-3消除瓶頸方法1：段細(xì)分消除瓶頸方法2：段重復(fù)s1S2-1S2-2S2-3s3s4123456789123456789369258147123456789s1S2-1S2-2S2-3s3s4第三章 流水線技術(shù) DLX的基本流水線（2）實際吞吐率如果每段時間相等如果各段時間不等第三章 流水線技術(shù) DLX的基本流水線2. 加速比S如果各段時間相同如果各段時間不等第三章 流水線技術(shù)

20、 DLX的基本流水線3. 流水線的效率如果各段時間相等所以有：E=S/m 或 S=mEE=TP*t0 或 TP=E/t0 第三章 流水線技術(shù) DLX的基本流水線如果流水線各段時間不等第三章 流水線技術(shù) 流水線中的相關(guān)流水線相關(guān)的三種類型：1. 結(jié)構(gòu)相關(guān)：當(dāng)指令在重疊執(zhí)行過程中，硬件資源滿足不了指令重疊執(zhí)行的要求，發(fā)生資源沖突時將產(chǎn)生“結(jié)構(gòu)相關(guān)”；2. 數(shù)據(jù)相關(guān)：當(dāng)一條指令需要用到前面指令的執(zhí)行結(jié)果，而這些指令均在流水線中重疊執(zhí)行時，就可能引起“數(shù)據(jù)相關(guān)”；3. 控制相關(guān)：當(dāng)流水線遇到分支指令和其他會改變PC值的指令時就會發(fā)生“控制相關(guān)”。第三章 流水線技術(shù) 流水線中的相關(guān)消除相關(guān)的基本方法：

21、讓流水線暫停執(zhí)行某些指令，而繼續(xù)執(zhí)行其他一些指令。 當(dāng)一條指令被暫停時，在該暫停指令之后發(fā)射的所有指令都要被暫停，而在該暫停指令之前發(fā)射的指令則可繼續(xù)執(zhí)行，在暫停期間，流水線不會取新的指令。第三章 流水線技術(shù) MIPS的基本流水線指令存儲器NPCPCIR寄存器ABImm符號位擴展MUXMUX=0？ALUoutputCondMUX數(shù)據(jù)存儲器LMDMUX41632取指令指令譯碼/取寄存器執(zhí)行/有效地址計算存儲器訪問寫回ADDALU第三章 流水線技術(shù) MIPS基本流水線的改進指令存儲器PC寄存器符號位擴展MUXMUX=0？MUX數(shù)據(jù)存儲器MUX41632ADDALUIRIR6.10IR6.10IF/

22、IDID/EXEX/MEMMEM/WB第三章 流水線技術(shù) 流水線中的相關(guān)流水線的結(jié)構(gòu)相關(guān)如果某些指令組合在流水線中重疊執(zhí)行時，產(chǎn)生資源沖突，則稱該流水線有結(jié)構(gòu)相關(guān)。處理方法：1. 插入暫停周期（“氣泡”）；2. 采用資源重復(fù)的方法； 第三章 流水線技術(shù) 流水線中的相關(guān)結(jié)構(gòu)相關(guān)示例圖（存儲器訪問沖突）IMRegALUDMRegIMRegALUDMRegIMRegALUDMRegIMRegALUDMReg時間（時鐘周期）IMRegALUDMRegCC1CC2CC3CC4CC5CC6CC7CC8CC9指令0指令1指令2指令3指令4第三章 流水線技術(shù) 流水線中的相關(guān)為消除結(jié)構(gòu)相關(guān)而插入流水線氣泡IMR

23、egALUDMRegIMRegALUDMRegIMRegALUDMReg時間（時鐘周期）IMRegALUDMRegCC1CC2CC3CC4CC5CC6CC7CC8CC9指令0指令1指令2暫停指令3氣泡氣泡氣泡氣泡氣泡第三章 流水線技術(shù) 流水線中的相關(guān)引入暫停后流水線的時空圖時鐘周期123456789指令iIFIDEXMEMWB指令i+1IFIDEXMEMWB指令i+2IFIDEXMEMWB指令i+3StallIFIDEXMEMWB指令i+4IFIDEXMEM指令i+5IFIDEX指令i+6IFID第三章 流水線技術(shù) 流水線中的相關(guān)采用資源重復(fù)消除結(jié)構(gòu)相關(guān)引入的暫停會影響流水線的性能。采用資源重

24、復(fù)的方法處理上述情況：（1）在流水線機器中設(shè)置相互獨立的指令存儲器和數(shù)據(jù)存儲器；（2）將Cache分割成指令Cache和數(shù)據(jù)Cache。為什么流水線機器有時允許結(jié)構(gòu)相關(guān)存在？（1）減少硬件代價；（2）減少功能單元的延遲。第三章 流水線技術(shù) 流水線中的相關(guān)數(shù)據(jù)相關(guān)的分類：1. 寫后讀相關(guān)：指令j的執(zhí)行要用到指令i的計算結(jié)果，但是當(dāng)其在流水線中重疊執(zhí)行時，j可能在i寫入其計算結(jié)果之前就先行對保存該結(jié)果的寄存器進行讀操作，從而得到錯誤的值。2. 寫后寫相關(guān)：j和i的目的操作數(shù)一樣，但是當(dāng)其在流水線中重疊執(zhí)行時，j可能在i寫入其結(jié)果之前就先行對保存該結(jié)果的寄存器進行寫操作，從而導(dǎo)致寫入順序錯誤，在目的

25、寄存器中留下的是i寫入的值，而不是j寫入的值。第三章 流水線技術(shù) 流水線中的相關(guān)3. 讀后寫相關(guān)：j可能在i讀取某個源寄存器的內(nèi)容之前就先對該寄存器進行寫操作，導(dǎo)致i后來讀取到的值是錯誤的。需要暫停的數(shù)據(jù)相關(guān)定向技術(shù)用于消除由于數(shù)據(jù)相關(guān)帶來的暫停。但是，并不是所有數(shù)據(jù)相關(guān)帶來的暫停都可以通過定向技術(shù)消除。第三章 流水線技術(shù) 流水線中的相關(guān)流水線的數(shù)據(jù)相關(guān)當(dāng)指令在流水線中重疊執(zhí)行時，流水線有可能改變指令讀/寫操作數(shù)的順序，使得讀/寫操作順序不同于它們非流水實現(xiàn)時的順序，這將導(dǎo)致數(shù)據(jù)相關(guān)。例如：I1: ADDR1,R2,R3I2: SUBR4,R1,R5I3: ANDR6,R1,R7I4: ORR

26、8,R1,R9I5: XORR10,R1,R11第三章 流水線技術(shù) 流水線中的相關(guān)IMRegALUDMRegI1IMRegALUDMRegI2IMRegALUDMIMRegALUIMRegI3I4I5CC6CC1CC2CC3CC4CC5第三章 流水線技術(shù) 流水線中的相關(guān)流水線的數(shù)據(jù)相關(guān)的處理方法：1. 周期分半的方法（解決I4相關(guān)）；2. 插入暫停周期（無定向時解決I2相關(guān)） ； 3. 采用定向技術(shù)（解決I3、 I2相關(guān)） 。 第三章 流水線技術(shù) 流水線中的相關(guān)通過定向技術(shù)減少數(shù)據(jù)相關(guān)帶來的暫停在某條指令產(chǎn)生一個計算結(jié)果之前，其他指令并不真正需要該計算結(jié)果，如果能夠?qū)⒃撚嬎憬Y(jié)果從其產(chǎn)生的地方直

27、接送到其他指令需要它的地方，那么就可以避免暫停。定向技術(shù)可以歸納為：1. 寄存器文件EX/MEM中的ALU的運算結(jié)果總是回送到ALU的輸入寄存器。2. 當(dāng)定向硬件檢測到前一個ALU運算結(jié)果的寫入寄存器就是當(dāng)前ALU操作的源寄存器時，那么控制邏輯將前一個ALU運算結(jié)果定向到ALU的輸入端，后一個ALU操作就不必從源寄存器中讀取操作數(shù)。推廣：將一個結(jié)果直接傳輸?shù)剿行枰墓δ軉卧５谌?流水線技術(shù) 流水線中的相關(guān)IMRegALUDMRegI1IMRegALUDMRegI2IMRegALUDMIMRegALUIMRegI3I4I5CC6CC1CC2CC3CC4CC5第三章 流水線技術(shù) 流水線中的

28、相關(guān)IMRegALUDMRegI1IMRegALUDMRegI2IMRegALUDMI3CC6CC1CC2CC3CC4CC5I1: ADDR1,R2,R3I2: LWR4,0(R1)I3:SW12(R1),R4第三章 流水線技術(shù) 流水線中的相關(guān)需要暫停的數(shù)據(jù)相關(guān)定向技術(shù)用于消除由于數(shù)據(jù)相關(guān)帶來的暫停。但是，并不是所有數(shù)據(jù)相關(guān)帶來的暫停都可以通過定向技術(shù)消除。第三章 流水線技術(shù) 流水線中的相關(guān)IMRegALUDMRegI1IMRegALUDMRegI2IMRegALUDMIMRegALUI3I4CC6CC1CC2CC3CC4CC5I1: LW R1, 0(R2)I2: SUB R4, R1, R

29、5I3: AND R6, R1, R7I4: OR R8, R1, R9LW指令不能將結(jié)果定向到SUB指令第三章 流水線技術(shù) 流水線中的相關(guān)IMRegALUDMRegI1IMRegI2IMI3IMRegI4CC6CC1CC2CC3CC4CC5I1: LW R1, 0(R2)I2: SUB R4, R1, R5I3: AND R6, R1, R7I4: OR R8, R1, R9流水線互鎖插入暫停ALUDM氣泡RegALU氣泡氣泡第三章 流水線技術(shù) 流水線中的相關(guān)對數(shù)據(jù)相關(guān)的編譯器調(diào)度方法下面A=B+C的實現(xiàn)代碼LW R1, BIFIDEXMEMWBLW R2, CIFIDEXMEMWBADD

30、R3,R1,R2IFIDstallEXMEMWBSW A, R3IFstallIDEXMEMWB編譯器可以通過重新組織代碼順序來消除這種暫停。這種重新組織代碼順序消除暫停的技術(shù)稱為“流水線調(diào)度”或“指令調(diào)度”。第三章 流水線技術(shù) 流水線中的相關(guān)例如計算a=b+c; d=e-f;調(diào)度前代碼調(diào)度后代碼LW Rb, bLW Rc, cADD Ra, Rb, RcSW a, RaLW Re, eLW Rf, fSUB Rd, Re, RfSW d, RdLW Rb, bLW Rc, cLW Re, e ADD Ra, Rb, RcLW Rf, fSW a, RaSUB Rd, Re, RfSW d,

31、Rd通過指令調(diào)度后，上述程序執(zhí)行過程中就不必插入暫停周期。第三章 流水線技術(shù) 流水線中的相關(guān)對流水線控制的實現(xiàn)指令發(fā)射：讓一條指令從流水線的指令譯碼段（ID）移動到執(zhí)行段（EX）的過程。已發(fā)射的指令：經(jīng)過指令發(fā)射過程的指令。（1）所有的數(shù)據(jù)相關(guān)均可以在流水線的ID段檢測到，如果存在數(shù)據(jù)相關(guān)，指令在其發(fā)射之前就會被暫停?；蛘呖梢栽贗D段決定需要什么樣的定向，然后設(shè)置相應(yīng)的控制。（2）另外在使用一個操作數(shù)的時鐘周期開始（EX和MEM段的開始）檢測相關(guān)，確定必須的定向。第三章 流水線技術(shù) 流水線中的相關(guān)流水線相關(guān)檢測硬件可以檢測到的各種相關(guān)相關(guān)情況指令序列范例動作需要暫停的相關(guān)LW R1, 45(R

32、2)ADD R5, R1, R7SUB R8, R6, R7OR R9, R6, R7比較器檢測到ADD指令中使用了寄存器R1，并在ADD指令開始EX周期之前暫停ADD指令（同時也暫停了SUB指令和OR指令）通過定向消除的相關(guān)LW R1, 45(R2)ADD R5, R6, R7SUB R8, R1, R7OR R9, R6, R7比較器檢測到SUB指令中使用了寄存器R1，并在SUB指令的EX周期開始時將載入的結(jié)果定向到ALU按順序訪問的相關(guān)LW R1, 45(R2)ADD R5, R6, R7SUB R8, R6, R7OR R9, R1, R7不需要任何動作，因為OR指令在ID段的后半個周

33、期讀R1，LW指令已經(jīng)在WB段的前半個周期將載入數(shù)據(jù)寫入了R1。第三章 流水線技術(shù) 流水線中的相關(guān)如果某條指令和Load指令有一個RAW相關(guān)時，該指令處于ID段，Load指令處于EX段。該指令在ID段為檢測是否需啟動流水線鎖而進行的比較如下：ID/EX段的操作碼域(ID/EX.IR0.5)ID/EX段的操作碼域(ID/EX.IR0.5)匹配操作數(shù)域LoadR-R ALUID/EX.IR11.15=IF/ID.IR6.10LoadR-R ALUID/EX.IR11.15=IF/ID.IR11.15LoadLoad、Store、ALU立即值或分支ID/EX.IR11.15=IF/ID.IR6.10

34、一旦硬件檢測到上述RAW相關(guān)，流水線互鎖必須在流水線中插入暫停周期，使處于IF和ID段的指令不再前進。另外，還必須暫停向前傳送IF/ID寄存器組的內(nèi)容，使得流水線能夠保持被暫停的指令。第三章 流水線技術(shù) 流水線中的相關(guān)定向目標(biāo)是ALU輸入時，所需進行的比較和定向操作包含定向源的流水線寄存器定向源相應(yīng)指令的操作碼包含定向目標(biāo)的流水寄存器定向目標(biāo)相應(yīng)指令的操作碼定向的目標(biāo)比較操作（如果相等就定向）EX/MEMR-R ALUID/EXR-R ALU、ALU立即值、Load、Store、分支ALU上面的輸入EX/MEM.IR16.20=ID/EX.IR6.10EX/MEMR-R ALUID/EXR-R

35、 ALUALU下面的輸入EX/MEM.IR16.20=ID/EX.IR11.15MEM/WBR-R ALUID/EXR-R ALU、ALU立即值、Load、Store、分支ALU上面的輸入MEM/B.IR16.20=ID/EX.IR6.10MEM/WBR-R ALUID/EXR-R ALUALU下面的輸入MEM/B.IR16.20=ID/EX.IR11.15EX/MEMALU立即值ID/EXR-R ALU、ALU立即值、Load、Store、分支ALU上面的輸入EX/MEM.IR11.15=ID/EX.IR6.10第三章 流水線技術(shù) 流水線中的相關(guān)定向目標(biāo)是ALU輸入時，所需進行的比較和定向操

36、作（續(xù)）包含定向源的流水線寄存器定向源相應(yīng)指令的操作碼包含定向目標(biāo)的流水寄存器定向目標(biāo)相應(yīng)指令的操作碼定向的目標(biāo)比較操作（如果相等就定向）EX/MEMALU立即值ID/EXR-R ALUALU下面的輸入EX/MEM.IR11.15=ID/EX.IR11.15MEM/WBALU立即值ID/EXR-R ALU、ALU立即值、Load、Store、分支ALU上面的輸入MEM/WB.IR11.15=ID/EX.IR6.10MEM/WBALU立即值ID/EXR-R ALUALU下面的輸入MEM/B.IR11.15=ID/EX.IR11.15MEM/WBLoadID/EXR-R ALU、ALU立即值、Lo

37、ad、Store、分支ALU上面的輸入MEM/B.IR11.15=ID/EX.IR6.10MEM/WBLoadID/EXR-R ALUALU下面的輸入EX/MEM.IR11.15=ID/EX.IR11.15第三章 流水線技術(shù) 流水線中的相關(guān)MIPS中處理數(shù)據(jù)相關(guān)時流水線增設(shè)的定向路徑 (Fig.3.45)MUXMUX=0？數(shù)據(jù)存儲器ALUEX/MEMID/EXMEM/WB第三章 流水線技術(shù) 流水線中的相關(guān)流水線的控制相關(guān)在DLX流水線上執(zhí)行分支指令時，PC值有兩種可能的變化情況：（1）PC值發(fā)生改變（分支轉(zhuǎn)移的目標(biāo)地址）；（2）PC值保持正常（當(dāng)前PC值加4）。處理分支指令的最簡單方法（分支延

38、遲）：一旦在流水線中檢測到某條指令為分支指令時，就暫停執(zhí)行該分支指令之后的所有指令，直到分支指令到達流水線的MEM段，確定了新的PC值為止。第三章 流水線技術(shù) 流水線中的相關(guān)簡單處理分支指令的方法及其流水時空圖分支指令iIFIDEXMEMWB指令i+1IFstallstallIFIDEXMEMWB指令i+2IFIDEXMEMWB指令i+3IFIDEXMEM指令i+4IFIDEX指令i+5IFID指令i+6IF第三章 流水線技術(shù) 流水線中的相關(guān)減少流水線處理分支指令時的暫停時鐘周期數(shù)有如下兩種途徑：（1）在流水線中盡早判斷出分支轉(zhuǎn)移是否成功；（2）盡早計算出分支轉(zhuǎn)移成功時的PC值（即分支的目標(biāo)地

39、址）。如何從硬件上改進流水線達到上述目標(biāo)：（1）把測試分支條件寄存器的操作提前到ID段完成，從而使得在ID段周期末就完成分支轉(zhuǎn)移成功與否的檢測；（2）盡早計算出兩個PC值（分支轉(zhuǎn)移成功和失敗時的PC值），將計算分支目標(biāo)地址的操作移到ID段完成。 BEQZ & BENZ第三章 流水線技術(shù) 流水線中的相關(guān)為處理控制相關(guān)，改進后的流水線數(shù)據(jù)通路指令存儲器PC寄存器符號位擴展MUX=0？MUX數(shù)據(jù)存儲器MUX41632ADDALUIRIR6.10IR6.10IF/IDID/EXEX/MEMMEM/WBADD第三章 流水線技術(shù) 流水線中的相關(guān)改進后流水線的分支操作流水段分支指令操作IFIF/ID.IRM

40、emPC;IF/ID.NPC,PC(if ID/EX.cond ID/EX.NPC else PC+4);IDID/EX.ARegsIF/ID.IR6.10; ID/EX.BRegsIF/ID.IR11.15;ID/EX.NPCIF/ID.NPC+(IR16)16#IR16.31;ID/EX.IRIF/ID.IR; ID/EX.cond(RegsIF/ID.IR6.10 op 0);ID/EX.Imm(IR16)16#IR16.31;EXMEMWB第三章 流水線技術(shù) 流水線中的相關(guān)程序中分支行為的特點：（1）分支指令中，無條件分支指令的執(zhí)行頻率非常低（2）整型基準(zhǔn)程序條件分支頻率在14%16%

41、,浮點型基準(zhǔn)程序條件分支頻率在3%12%；（3）向前分支指令的執(zhí)行頻率大約是向后分支指令執(zhí)行頻率的13倍；（4）向前條件分支指令分支轉(zhuǎn)移成功的概率約為60%，向后條件分支指令分支轉(zhuǎn)移成功的概率約為85%。第三章 流水線技術(shù) 流水線中的相關(guān)降低流水線分支損失的方法：（1）“凍結(jié)”或“排空”流水線的方法：保持或清除流水線在分支指令之后讀入的任何指令，直到知道分支指令的目標(biāo)地址以及分支轉(zhuǎn)移是否成功為止。（2）“預(yù)測分支失敗”的方法。當(dāng)流水線譯碼到一條分支指令時，流水線繼續(xù)取指令，并允許該分支指令后的指令繼續(xù)在流水線中流動。當(dāng)流水線確定分支轉(zhuǎn)移成功與否以及分支的目標(biāo)地址之后，如果分支轉(zhuǎn)移成功，流水線必

42、須將在分支指令之后取出的所有指令轉(zhuǎn)化為空操作，并在分支的目標(biāo)地址處重新取出有效的指令；如果分支轉(zhuǎn)移失敗，那么可以將分支指令看作是一條普通的指令，流水正常流動，無需將在分支指令之后取出的指令轉(zhuǎn)化為空操作。第三章 流水線技術(shù) 流水線中的相關(guān)失敗分支指令iIFIDEXMEMWB指令i+1IFIDEXMEMWB指令i+2IFIDEXMEMWB指令i+3IFIDEXMEMWB指令i+4IFIDEXMEMWB成功分支指令iIFIDEXMEMWB指令i+1IFidleidleidleidle分支目標(biāo)jIFIDEXMEMWB分支目標(biāo)j+1IFIDEXMEMWB分支目標(biāo)j+2IFIDEXMEMWB“預(yù)測分支失敗

43、”的方法:第三章 流水線技術(shù) 流水線中的相關(guān)降低流水線分支損失的方法：（3）“預(yù)測分支成功”的方法：一旦流水線譯碼到一條指令是分支指令，且完成了分支目標(biāo)地址的計算，就假設(shè)分支轉(zhuǎn)移成功，并開始在分支目標(biāo)地址處取指令執(zhí)行。這種方法對降低流水線分支損失沒有任何好處？（4）“延遲分支”的方法：其主要思想是從邏輯上“延長”分支指令的執(zhí)行時間。其方法是將若干條指令調(diào)度到分支指令之后，這些指令稱為處于延遲分支槽中。（5）BENZ變結(jié)果為1取分支（編譯解決，無延遲）延遲長度為n的分支指令的執(zhí)行順序為：分支指令延遲分支指令1延遲分支指令2延遲分支指令n分支目標(biāo)處指令（如果分支成功）第三章 流水線技術(shù) 流水線中的

44、相關(guān)分支延遲槽第三章 流水線技術(shù) 流水線中的相關(guān)只需具有一拍延遲的延遲分支槽失敗分支指令iIFIDEXMEMWB延遲分支指令i+1IFIDEXMEMWB指令i+2IFIDEXMEMWB指令i+3IFIDEXMEMWB指令i+4IFIDEXMEMWB成功分支指令iIFIDEXMEMWB延遲分支指令i+1IFIDEXMEMWB分支目標(biāo)jIFIDEXMEMWB分支目標(biāo)j+1IFIDEXMEMWB分支目標(biāo)j+2IFIDEXMEMWB第三章 流水線技術(shù) 流水線中的相關(guān)選擇什么指令放入延遲分支槽中？有三種選擇方法或稱三種指令調(diào)度技術(shù)：ADD R1,R2,R3If R2=0 then延遲槽If R2=0 t

45、henADD R1,R2,R3從前調(diào)度SUB R4,R5,R6ADD R1,R2,R3If R2=0 then延遲槽SUB R4,R5,R6ADD R1,R2,R3If R2=0 thenSUB R4,R5,R6從目標(biāo)處調(diào)度ADD R1,R2,R3If R1=0 then延遲槽SUB R4,R5,R6ADD R1,R2,R3If R1=0 thenSUB R4,R5,R6從失敗處調(diào)度調(diào)度后調(diào)度后調(diào)度后第三章 流水線技術(shù) 流水線中的相關(guān)調(diào)度分支延遲指令的三種方法的特點及其局限性調(diào)度策略對調(diào)度的要求對流水線性能改善的影響從前調(diào)度分支必須不依賴于被調(diào)度的指令總是可以有效提高流水線性能從目標(biāo)處調(diào)度如果

46、分支轉(zhuǎn)移失敗，必須保證被調(diào)度的指令對程序的執(zhí)行沒有影響，可能需要復(fù)制被調(diào)度指令分支轉(zhuǎn)移成功時，可以提高流水線性能。但由于復(fù)制指令，可能加大程序空間從失敗處調(diào)度如果分支轉(zhuǎn)移成功，必須保證被調(diào)度的指令對程序的執(zhí)行沒有影響分支轉(zhuǎn)移失敗時，可以提高流水線性能第三章 流水線技術(shù) 流水線中的相關(guān) 結(jié)論：調(diào)度延遲分支指令的方法可以降低流水線的分支損失，但是它受限于被調(diào)度進入分支延遲槽中的指令，以及編譯器預(yù)測分支轉(zhuǎn)移是否成功的能力。 為了提高編譯器填充分支延遲槽的能力，許多流水線機器引入了“取消”或“作廢”分支。對取消分支而言，分支指令包含了預(yù)測的分支方向，當(dāng)實際的分支方向和事先所預(yù)測的一樣，執(zhí)行分支延遲槽中

47、的指令，流水線正常工作；當(dāng)實際分支方向和事先所預(yù)測的不同，就將分支延遲槽中的指令轉(zhuǎn)化成一個空操作。第三章 流水線技術(shù) 流水線中的相關(guān)取消分支的行為依賴于實際的分支方向失敗分支指令iIFIDEXMEMWB延遲分支指令i+1IFidleidleidleidle指令i+2IFIDEXMEMWB指令i+3IFIDEXMEMWB指令i+4IFIDEXMEMWB成功分支指令iIFIDEXMEMWB延遲分支指令i+1IFIDEXMEMWB分支目標(biāo)jIFIDEXMEMWB分支目標(biāo)j+1IFIDEXMEMWB分支目標(biāo)j+2IFIDEXMEMWB第三章 流水線技術(shù) 流水線計算機MIPS R4000R4000有8個

48、流水段：（1）IF段，取指令的前半部分操作，主要完成選擇PC值和指令Cache的啟動工作；（2）IS段，取指令的后半部分操作，主要完成訪問指令Cache的操作；（3）RF段，完成譯碼、取寄存器和相關(guān)檢測等操作，并檢測指令Cache命中情況；（4）EX段，執(zhí)行段，包括計算有效地址、ALU操作、計算分支目標(biāo)地址和檢測分支條件；第三章 流水線技術(shù) 流水線計算機MIPS R4000R4000有8個流水段：（5）DF段，完成取數(shù)據(jù)操作，是訪問數(shù)據(jù)Cache的前半部分；（6）DS段，是訪問數(shù)據(jù)Cache的后半部分；（7）TC段，完成Cache標(biāo)記檢測，以確定訪問數(shù)據(jù)Cache是否命中；（8）WB段，寫回讀

49、出的數(shù)據(jù)或寄存器-寄存器操作的結(jié)果。第三章 流水線技術(shù) 流水線計算機MIPS R4000ALU指令存儲器數(shù)據(jù)存儲器RegRegIFISRFEXDFDSTCWBR4000流水線結(jié)構(gòu)由于R4000流水線段數(shù)較多，稱這種類型的流水是“超級流水”（superpipelining）。第三章 流水線技術(shù) 流水線計算機MIPS R4000指令在R4000流水線中重疊執(zhí)行LW R1指令1指令2ADD R2,R1CC1CC2CC3CC4CC5CC6CC7CC8CC9CC10CC11R4000的載入延遲為2個時鐘周期，所以R4000的流水線具有較長的載入和分支延遲。第三章 流水線技術(shù) 流水線計算機MIPS R40

50、00指令序列時鐘周期123456789LW R1IFISRFEXDFDSTCWBADD R2, R1IFISRFstallstallEXDFDSSUB R3, R1IFISstallstallRFEXDFOR R4, R1IFstallstallISRFEXR4000流水線的定向路徑比DLX流水線要多。在R4000的流水線中，到ALU輸入有四個定向源：EX/DF、DF/DS、DS/TC和TC/WB。第三章 流水線技術(shù) 流水線計算機MIPS R4000BZ指令1指令2指令3CC1CC2CC3CC4CC5CC6CC7CC8CC9CC10CC11目標(biāo)第三章 流水線技術(shù) 流水線計算機MIPS R400

51、0指令序列時鐘周期123456789分支指令I(lǐng)FISRFEXDFDSTCWB延遲槽IFISRFEXDFDSTCWB暫停stallstallstallstallstallstallstall暫停stallstallstallstallstallstall目標(biāo)IFISRFEXDF指令序列時鐘周期123456789分支指令I(lǐng)FISRFEXDFDSTCWB延遲槽(分支指令+1)IFISRFEXDFDSTCWB分支指令+2IFISRFEXDFDSTC分支指令+3IFISRFEXDFDS第三章 流水線技術(shù) 向量處理機向量處理方式對于如下程序DO 10 i=1,N10di=ai*(bi+ci)有如下執(zhí)行方式

52、：（1）水平（橫向）處理方式：逐個求的di的方式。不適合流水處理。 特點： N次數(shù)據(jù)相關(guān) 2N次功能切換第三章 流水線技術(shù) 向量處理機（2）垂直（縱向）處理方式：將整個向量按相同的運算處理完畢后，再去執(zhí)行別的運算。可用兩條向量指令完成上述程序：K=B+C （先做向量加）D=K*A （后做向量乘） 特點： 1次數(shù)據(jù)相關(guān) 1次功能切換 處理機結(jié)構(gòu)是M-M型操作的運算流水線 要設(shè)置較寬的通信帶寬第三章 流水線技術(shù) 向量處理機（3）分組（縱橫）處理方式：把長度為N的向量分成若干組，每組長度為n，組內(nèi)按縱向方式處理，依次處理各組。若N=s*n+r，r為余數(shù)，則共有s+1組。 特點： 組內(nèi)1次數(shù)據(jù)相關(guān) 每

53、組2次功能切換 可使用R-R型操作的運算流水線（圖3.44） 評價向量處理機速度：（1）使用MFLOPS而不是MIPS（2）機間比較法第三章 流水線技術(shù) 向量處理機CRAY-1向量處理機（圖3.48）（1）6個功能部件：整數(shù)加、邏輯運算、移位、浮點加、浮點乘、浮點迭代求倒數(shù)。（2）6個功能部件可并行工作。（3）向量寄存器組512個64位，分8向量塊（Vi塊），每個Vi塊可存放一個向量（向量元素不超過64個）。（4）每個Vi塊都有獨立的數(shù)據(jù)線和功能部件相連，所以只要不出現(xiàn)Vi塊沖突和功能部件沖突，各個Vi塊之間和各個功能部件之間都能并行工作。（5）8個標(biāo)量寄存器組第三章 流水線技術(shù) 向量處理機V

54、i沖突：并行工作的各向量指令的源向量或結(jié)果向量的Vi有相同的。如V4=V1+V2V5=V1V3不能同時執(zhí)行。功能部件沖突：同一個功能部件被一條以上的并行工作向量指令所使用。如V4=V2*V3V5=V1*V6不能同時執(zhí)行。第三章 流水線技術(shù) 向量處理機CRAY-1的四種向量指令：（圖3.49）（1）向量向量操作。從Vi和Vj取一對元素送入功能部件，結(jié)果存入Vk中。（2）標(biāo)量向量操作。結(jié)果為向量。（3）取向量操作。（4）存向量操作。 上述操作需要向量長度寄存器VL和向量屏蔽寄存器VM的支持。第三章 流水線技術(shù) 向量處理機向量處理機的鏈接技術(shù)：實質(zhì)上是把流水線的“定向”思想引入到向量執(zhí)行中。例如：向

55、量運算D=A*（B+C），設(shè)A在存儲器中，B在V0中，C在V1中，D存放在V4。實現(xiàn)方式為1. V3存儲器（訪存，取A）2. V2V0+V1（浮點加）3. V4V2*V3（浮點乘，存D）第三章 流水線技術(shù) 向量處理機存儲器訪存浮點加浮點乘V0V1V2V3V4向量處理機的鏈接技術(shù)第三章 流水線技術(shù) 向量處理機假設(shè)浮點加流水線為6拍，浮點乘流水線為7拍，訪問存儲器流水線為6拍。假設(shè)由于同步的原因，數(shù)據(jù)流入和流出每個功能部件，都需要1拍時間。前面的三條指令全部串行執(zhí)行，則執(zhí)行時間為：(1+6+1)+N-1+ (1+6+1)+N-1+ (1+7+1)+N-1=3N+22若前兩條指令并行執(zhí)行，然后執(zhí)行第三條指令，則執(zhí)行時間為：(1+6+1)+N-1+ (1+7+1)+N-1=2N+15若采用鏈接技術(shù)，則執(zhí)行時間為：(1+6+1)+(1+7+1)+(N-1)=N+16第三章 流水線技術(shù) 向量處理機向量指令的格式