第一講流水線數(shù)據(jù)通路和控制邏輯第二講流水線冒險處理第三講高級流水線技術

Ch7:InstructionPipeline指令流水線第一講流水線數(shù)據(jù)通路和控制日常生活中的流水線處理例子：洗衣服單周期處理器模型和流水線性能比較什么樣的指令集適合于流水線方式執(zhí)行如何設計流水線數(shù)據(jù)通路以MIPS指令子集來說明詳細設計取指令部件詳細設計執(zhí)行部件分析每條指令在流水線中的執(zhí)行過程，遇到各種問題：資源沖突寄存器和存儲器的信號競爭分支指令的延遲指令間數(shù)據(jù)相關如何設計流水線控制邏輯分析每條指令執(zhí)行過程中的控制信號給出控制器設計過程流水線冒險的概念主要內容復習：ASingleCycleProcessor32ALUctrClkbusWRegWr3232busA32busB555RwRaRb3232-bitRegistersRsRtRtRdRegDstExtenderMuxMux3216imm16ALUSrcExtOpMuxMemtoRegClkDataInWrEn32AdrDataMemory32MemWrALUZero010101InstructionFetch

UnitClkInstruction<31:0>JumpBranch<21:25><16:20><11:15><0:15>Imm16RdMainControlopALUControlfuncALUop3RegDstALUSrc:<5:0><31:26>Instr<15:0>Zero3復習：MultipleCycleProcessorMCP:一個功能部件在一個指令周期中可以被使用多次。IdealMemoryWrAdrDinRAdr323232DoutMemWr32ALU3232ALUOpALUControlInstructionReg32IRWr32Reg

FileRaRwbusWRb5532busA32busBRegWrRsRtMux01RtRdPCWrALUSelAMux01RegDstMux0132PCMemtoRegExtendExtOpMux01320123416Imm32<<2ALUSelBMux10Target32ZeroZeroPCWrCondPCSrcBrWr32IorD復習：單周期中l(wèi)w指令的定時ClkPCRs,Rt,Rd,Op,FuncClk-to-QALUctrInstructionMemoryAccessTimeOldValueNewValueRegWrOldValueNewValueDelaythroughControlLogicbusARegisterFileAccessTimeOldValueNewValuebusBALUDelayOldValueNewValueOldValueNewValueNewValueOldValueExtOpOldValueNewValueALUSrcOldValueNewValueAddressOldValueNewValuebusWOldValueNewDelaythroughExtender&MuxDataMemoryAccessTimeInstructionFetchInstrDecode/Reg.FetchAddressRegWrDataMemoryRegisterFileWriteTime132LaundryExampleA,B,C,D四個人，每人都有一批衣服需要

wash,dry,foldWash階段：30minutesDry階段：40minutesFold階段：

20minutesABCDPipelining:It’sNatural!一個日常生活中的例子—洗衣服如果讓你來管理洗衣店，你會如何安排？SequentialLaundry（串行方式）串行方式下，4批衣服需要花費6小時（4x(30+40+20)=360分鐘）N批衣服，需花費的時間為Nx(30+40+20)=90N如果用流水線方式洗衣服，則花多少時間呢?ABCD3040203040203040203040206PM7891011MidnightTaskOrderTimePipelinedLaundry:(StartworkASAP)串行為6小時，N批則為90N分鐘ABCD6PM7891011MidnightTaskOrderTime304040404020流水線方式下，需30+4x40+20=210分(3.5小時)如果有N批衣服呢？30+Nx40+20分鐘假定每一步時間均衡，則比串行方式提高約3倍！流水方式下，所用時間主要與最長階段的時間有關！復習：Load指令的5個階段Ifetch(取指):取指令并計算PC+4(用到哪些部件？)Reg/Dec(取數(shù)和譯碼):取數(shù)同時譯碼(用到哪些部件？)Exec(執(zhí)行):計算內存單元地址(用到哪些部件？)Mem(讀存儲器):從數(shù)據(jù)存儲器中讀(用到哪些部件？)Wr(寫寄存器):將數(shù)據(jù)寫到寄存器中(用到哪些部件？)階段1階段2階段

3階段4階段5IfetchReg/DecExecMemWr指令存儲器、Adder寄存器堆讀口、指令譯碼器擴展器、ALU數(shù)據(jù)存儲器寄存器堆寫口這里寄存器堆的讀口和寫口可看成兩個不同的部件。指令的執(zhí)行過程中，每個階段使用不同的部件。是否和“洗衣”過程類似？是否可以采用類似方式來執(zhí)行指令呢？單周期指令模型與流水線性能假定以下每步操作所花時間為：取指：2ns寄存器讀：1nsALU操作：2ns存儲器讀：2ns寄存器寫：1ns單周期模型每條指令在一個時鐘周期內完成時鐘周期等于最長的lw指令的執(zhí)行時間，即：8ns串行執(zhí)行時，N條指令的執(zhí)行時間為：8Nns流水線性能時鐘周期等于最長階段所花時間為：2ns每條lw指令的執(zhí)行時間為：2nsx5=10nsN條指令的執(zhí)行時間為：(5+(N-1))x2ns在N很大時約為2Nns，比串行方式提高約4倍若各階段操作均衡(例如，各階段都是2ns，則串行需10Nns，流水線仍為2Nns)，提高倍數(shù)為5倍。Load指令執(zhí)行時間總計為：8ns

(假定控制單元、PC訪問、信號傳遞等沒有延遲)流水線方式下，單條指令執(zhí)行時間不能縮短，但能大大提高指令吞吐率！222222222222222流水線指令集的設計具有什么特征的指令集有利于流水線執(zhí)行呢？長度盡量一致，有利于簡化取指令和指令譯碼操作MIPS指令32位，下址計算方便:PC+4X86指令從1字節(jié)到17字節(jié)不等，使取指部件極其復雜格式少，且源寄存器位置相同，有利于在指令未知時就可取操作數(shù)MIPS指令的Rs和Rt位置一定，在指令譯碼時就可讀Rs和Rt的值（若位置隨指令不同而不同，則需先確定指令后才能取寄存器編號）load/Store指令才能訪問存儲器，有利于減少操作步驟，規(guī)整流水線lw/sw指令的地址計算和運算指令的執(zhí)行步驟規(guī)整在同一個周期X86運算類指令操作數(shù)可為內存數(shù)據(jù)，需計算地址、訪存、執(zhí)行內存中”對齊”存放，有利于減少訪存次數(shù)和流水線的規(guī)整總之，規(guī)整、簡單和一致等特性有利于指令的流水線執(zhí)行流水線執(zhí)行方式能大大提高指令吞吐率，現(xiàn)代計算機都采用流水線方式！Load指令的流水線ClockCycle1Cycle2Cycle3Cycle4Cycle5Cycle6Cycle7IfetchReg/DecExecMemWr1stlwIfetchReg/DecExecMemWr2ndlwIfetchReg/DecExecMemWr3rdlw每個周期最多有五個功能部件同時在工作后面指令在前面完成取指后馬上開始每個load指令仍然需要五個周期完成但是吞吐率(throughput)提高許多，理想情況下，有：每個周期有一條指令進入流水線每個周期都有一條指令完成每條指令的有效周期(CPI)為1IfetchReg/DecExecMemWr4thlwIfetchReg/DecExecMemWr5thlwIfetchReg/DecExec…R-type指令的4個階段Ifetch:

取指令并計算PC+4Reg/Dec:

從寄存器取數(shù)，同時指令在譯碼器進行譯碼Exec:

在ALU中對操作數(shù)進行計算Wr:ALU計算的結果寫到寄存器Cycle1Cycle2Cycle3Cycle4IfetchReg/DecExecWrR-type含R-type和Load指令的流水線上述流水線有個問題:兩條指令試圖同時寫寄存器，因為Load在第5階段用寄存器寫口R-type在第4階段用寄存器寫口把一個功能部件同時被多條指令使用的現(xiàn)象稱為結構冒險(StrutureHazard)為了流水線能順利工作，規(guī)定：每個功能部件每條指令只能用一次（如：寫口不能用兩次或以上）每個功能部件必須在相同的階段被使用（如：寫口總是在第五階段被使用）IfetchReg/DecExecWrR-typeIfetchReg/DecExecWrR-typeClockCycle1Cycle2Cycle3Cycle4Cycle5Cycle6Cycle7Cycle8Cycle9IfetchReg/DecExecWrR-typeIfetchReg/DecExecWrR-typeIfetchReg/DecExecMemWrLoadWehaveaproblem!或稱為資源沖突！解決方案:R-type的Wr操作延后一個周期執(zhí)行加一個NOP階段以延遲“寫”操作:把“寫”操作安排在第5階段,這樣使R-Type的Mem階段為空NOP這樣使流水線中的每條指令都有相同多個階段!IfetchReg/DecExecWrR-type12345MemClockCycle1Cycle2Cycle3Cycle4Cycle5Cycle6Cycle7Cycle8Cycle9IfetchReg/DecWrR-typeIfetchReg/DecWrR-typeIfetchReg/DecExecMemWrLoadIfetchReg/DecWrR-typeIfetchReg/DecWrR-typeMemExecExecExecExecMemMemMemNOOP!Store指令的四個階段Ifetch：取指令并計算PC+4Reg/Dec：從寄存器取數(shù)，同時指令在譯碼器進行譯碼Exec：16位立即數(shù)符號擴展后與寄存器值相加，計算主存地址Mem：將寄存器讀出的數(shù)據(jù)寫到主存Cycle1Cycle2Cycle3Cycle4IfetchReg/DecExecMemStoreWrWr:

加一個空的寫階段，使流水線更規(guī)整！NOOP!Beq的四個階段Ifetch:取指令并計算PC+4Reg/Dec:從寄存器取數(shù)，同時指令在譯碼器進行譯碼Exec:

執(zhí)行階段ALU中比較兩個寄存器的大?。ㄗ鰷p法）Adder中計算轉移地址Mem:

如果比較相等,則：轉移目標地址寫到PCCycle1Cycle2Cycle3Cycle4IfetchReg/DecExecMemBeqWrNOOP!Wr:

加一個空寫階段，使流水線更規(guī)整！與多周期通路有什么不同？多周期通路中，在Reg/Dec階段投機進行了轉移地址的計算！可以減少Branch指令的時鐘數(shù)為什么流水線中不進行“投機”計算？因為，流水線中所有指令的執(zhí)行階段一樣多，Branch指令無需節(jié)省時鐘，因為有比它更復雜的指令。按照上述方式，把所有指令都按照最復雜的“l(fā)oad”指令所需的五個階段來劃分，不需要的階段加一個“NOP”操作APipelinedDatapath（五階段流水線數(shù)據(jù)通路）IF/ID

RegisterID/ExRegisterEx/Mem

RegisterMem/Wr

RegisterPCDataMemWADiRADoIUnitAIRFileDiRaRbRwMemWrRegWrExtOpExecUnitbusAbusBImmALUOpALUSrcMux10MemtoReg10RegDstRtRdImmPC+4PC+4RsRtPC+4ZeroBranch10ClkIfetch(IF)Reg/Dec(ID)Exec(Ex)MemWrClock-to-Qdelay下面看每條指令在流水線通路中的執(zhí)行過程Wr階段沒有Data-Path嗎？有！寄存器寫口流水段寄存器的作用？保存每個周期執(zhí)行的結果!屬于內部寄存器，對程序員透明，不需作為現(xiàn)場保存取指令（Ifetch)階段——開始時IF/ID:？？？？？？？ID/ExRegisterEx/Mem

RegisterMem/Wr

RegisterPC=10DataMemWADiRADoIUnitAIRFileDiRaRbRwMemWrRegWrExtOpExecUnitbusAbusBImmALUOpALUSrcMux10MemtoReg10RegDstRtRdImmPC+4PC+4RsRtPC+4ZeroBranch10ClkIfetchReg/DecExecMemYouarehere!第10單元指令:lw$1,0x100($2)功能：$1<-Mem[($2)+0x100]有誰發(fā)現(xiàn)這里有一個假設有問題？MIPS指令的地址可能是10嗎？取指令（Ifetch)階段——結束后IF/ID:lw$1,100($2)ID/ExRegisterEx/Mem

RegisterMem/Wr

RegisterPC=14DataMemWADiRADoIUnitAIRFileDiRaRbRwMemWrRegWrExtOpExecUnitbusAbusBImmALUOpALUSrcMux10MemtoReg10RegDstRtRdImmPC+4PC+4RsRtPC+4ZeroBranch10ClkIfetchReg/DecExecMemYouarehere!第10單元指令:lw$1,0x100($2)功能：$1Mem[($2)+0x100]下一目標：設計IUnit（功能是啥？）指令部件IUnit的設計第10單元指令::lw$1,0x100($2)隨后的指令在14號單元中！IF/ID:lw$1,100($2)PC=1410AdderInstructionMemory“4”InstructionAddressClkIfetchYouarehere!Reg/Dec開始從14號單元取指！PC新值（14）≠舊輸出（10）流水段寄存器用來存放各階段的執(zhí)行結果總是在下個時鐘到來后的Clock-to-Q寫入取指階段有哪些控制信號？不需控制信號，因為每條指令執(zhí)行功能一樣，是確定的，無需根據(jù)指令的不同來控制執(zhí)行不同的操作！指令部件功能InstrMem[PC]PCPC+4這里MUX的控制信號由其他階段產(chǎn)生！應把哪些信息存到流水段寄存器IF/ID中？應保存后面階段用到的指令和PC+4的值！指令在隨后階段被送出譯碼！PC+4用來計算轉移目標地址譯碼/取數(shù)（Reg/Dec）階段IF/ID:ID/Ex:Reg.2&0x100Ex/MemRegisterMem/Wr

RegisterPC

DataMemWADiRADoIUnitAIRFileDiRaRbRwMemWrRegWrExtOpExecUnitbusAbusBImmALUOpALUSrcMux10MemtoReg10RegDstRtRdImmPC+4PC+4RsRtPC+4ZeroBranch10ClkIfetchReg/DecExecMemYouarehere!第10單元指令:lw$1,0x100($2)功能：$1Mem[($2)+0x100]Reg[Rs],Reg[Rt],Rt,Rd,Imm16,PC+4等被保存在ID/EXE中該階段有哪些控制信號？沒有！因是所有指令的公共操作，故無控制信號！RegWr是Wr段的信號！指令還要存ID/EX中嗎？不要，只要存相關信息Load指令的地址計算階段IF/ID:ID/Ex

RegisterEx/Mem:Load’sAddressMem/Wr

RegisterPCDataMemWADiRADoIUnitAIRFileDiRaRbRwMemWrRegWrExecUnitbusAbusBImmMux10MemtoReg10RtRdImmPC+4PC+4RsRtPC+4ZeroBranch10ClkIfetchReg/DecExecMemYouarehere!第10單元指令:lw$1,0x100($2)功能：$1Mem[($2)+0x100]ExtOp=？ALUOp=？ALUSrc=？RegDst=0指令已被譯碼，可確定執(zhí)行部件的控制信號！下一目標：設計執(zhí)行部件(ExecUnit)連接到錯誤的目的地址，指令執(zhí)行錯誤！目的寄存器Rt不傳遞下去會怎樣？執(zhí)行部件（ExecUnit）的設計ID/Ex

RegisterEx/Mem:Load’sMemoryAddressALUControlALUctr32busA32busBExtenderMux16immALUSrc=?ExtOp=?3ALUZero0132ALUout32Adder3ALUOp=?<<232PC+4Target32ClkExecYouarehere!MemAdder用于計算分支指令的轉移地址RegDes=0,ALUSrc=1ALUop=add,Extop=1Load指令的各控制信號取值？執(zhí)行部件功能？計算內存地址計算轉移目標地址一般ALU運算Branch指令呢？RegDes=x,ALUSrc=0ALUop=sub,Extop=1Store指令呢？RegDes=x,ALUSrc=1ALUop=add,Extop=1Ori指令呢？RegDes=0,ALUSrc=1ALUop=or,Extop=0R型指令呢？RegDes=1,ALUSrc=0ALUop=‘func’,Extop=xLoad指令的存儲器讀(Mem)周期IF/ID:ID/Ex

RegisterEx/Mem

RegisterMem/Wr:Load’sDataPCDataMemWADiRADoIUnitAIRFileDiRaRbRwMemWr=0RegWrExtOpExecUnitbusAbusBImmALUOpALUSrcMux10MemtoReg10RegDstRtRdImmPC+4PC+4RsRtPC+4ZeroBranch=010ClkIfetchReg/DecExecMemYouarehere!第10單元指令:lw$1,0x100($2)功能：

$1Mem[($2)+0x100]周期以最長操作為準設計Cycle>Tread比較洗衣流水線，指令流水有什么不同？洗衣流程不能反向進行，但該階段有反向數(shù)據(jù)流，可能會引起冒險！以后介紹。Load指令的回寫（WriteBack）階段IF/ID:ID/Ex

RegisterEx/Mem

RegisterMem/Wr

RegisterPCDataMemWADiRADoIUnitAIRFileDiRaRbRwMemWrRegWr=1ExtOpExecUnitbusAbusBImmALUOpALUSrcMux1010RegDstRtRdImmPC+4PC+4RsRtPC+4ZeroBranch10ClkIfetchReg/DecExecMemLocation10:lw$1,0x100($2)功能：$1Mem[($2)+0x100]Wr各階段所經(jīng)DataPath已有，控制信號如何得到？該階段有反向數(shù)據(jù)流，可能會引起冒險！以后介紹。MemtoReg=1流水線中的ControlSignals如何獲得?主要考察:第N階段的控制信號，它取決于是某條指令的某個階段。N=Exec,Mem,orWr(只有這三個階段有控制信號）例:Load的Exec段的控制信號如圖中所示MemWrMemtoRegRegDst=0IF/ID:ID/Ex

RegisterEx/Mem:Load’sAddressMem/Wr

RegisterPCDataMemWADiRADoIUnitAIRFileDiRaRbRwRegWrExtOp=1ExecUnitbusAbusBImmALUOp=AddALUSrc=1Mux1010RtRdI16PC+4PC+4RsRtPC+4ZeroBranch10IfetchReg/DecExecMemWr流水線中的ControlSignals如何獲得?在取數(shù)/譯碼（Reg/Dec）階段產(chǎn)生本指令每個階段的所有控制信號Exec信號(ExtOp,ALUSrc,...)在1個周期后使用Mem信號(MemWr,

Branch)在2個周期后使用Wr信號(MemtoReg,RegWr)在3個周期后使用IF/IDRegisterID/ExRegisterEx/MemRegisterMem/WrRegister2Reg/Dec3Exec4MemExtOpALUOpRegDstALUSrcBranchMemWrMemtoRegRegWrMainControlExtOpALUOpRegDstALUSrcMemtoRegRegWrMemtoRegRegWrMemtoRegRegWrBranchMemWrBranchMemWr5Wr

各流水段部件在一個時鐘內完成某條指令的某個階段的工作！所以，控制信號也要保存在流水段寄存器中！在下個時鐘到達時，把執(zhí)行結果以及前面?zhèn)鬟f來的后面各階段要用到的所有數(shù)據(jù)（如：指令、立即數(shù)、目的寄存器等）和控制信號保存到流水線寄存器中！流水線中的ControlSignals通過對前面流水線數(shù)據(jù)通路的分析，得知：因為每個時鐘都會改變PC的值，所以PC不需要寫控制信號流水段寄存器每個時鐘都會寫入一次，也不需要寫控制信號Ifecth階段和Dec/Reg階段都沒有控制信號，因為功能都一樣Exec階段的控制信號有四個ExtOp(擴展器操作)：1-符號擴展；0-零擴展ALUSrc(ALU的B口來源)：1-來源于擴展器；0-來源于BusBALUOp(主控制器輸出，用于輔助局部ALU控制邏輯來決定ALUCtrl)RegDst(指定目的寄存器)：1-Rd；0-RtMem階段的控制信號有兩個MemWr(DM的寫信號)：Store指令時為1，其他指令為0Branch(是否為分支指令)：分支指令時為1，其他指令為0Wr階段的控制信號有兩個MemtoReg(寄存器的寫入源)：1-DM輸出；0-ALU輸出RegWr(寄存器堆寫信號)：結果寫寄存器的指令都為1，其他指令為0控制邏輯(Control)的設計流水線控制邏輯的設計每條指令的控制信號在指令執(zhí)行期間都不變與單周期控制邏輯設計類似設計過程控制邏輯分成兩部分主控制邏輯：生成ALUop和其他控制信號局部ALU控制邏輯：根據(jù)ALUop和func字段生成ALUCtrl用真值表建立指令和控制信號之間的關系寫出每個控制信號的邏輯表達式控制邏輯的輸出（控制信號）在ID階段生成，并存放在ID/EX流水段寄存器中，然后每來一個時鐘跟著其它數(shù)據(jù)和信息傳送到下一級流水段寄存器在同一時刻，不同階段同時執(zhí)行不同指令，不同的指令得到不同控制信號請復習單周期和多周期控制器設計。。。藍色部分是控制信號控制信號在流水線中的傳遞以及帶來的問題在取數(shù)/譯碼（Reg/Dec）階段產(chǎn)生本指令每個階段的所有控制信號Exec信號(ExtOp,ALUSrc,...)在1個周期后使用Mem信號(MemWr,

Branch)在2個周期后使用Wr信號(MemtoReg,RegWr)在3個周期后使用IF/IDRegisterID/ExRegisterEx/MemRegisterMem/WrRegisterReg/DecExecMemExtOpALUOpRegDstALUSrcBranchMemWrMemtoRegRegWrMainControlExtOpALUOpRegDstALUSrcMemtoRegRegWrMemtoRegRegWrMemtoRegRegWrBranchMemWrBranchMemWrWr保存在流水段寄存器中的信息（包括前面階段傳遞來或執(zhí)行的結果及控制信號）一起被傳遞到下一個流水段！所以，控制信號也要保存在流水段寄存器中！RtData(這里是否會有問題？)Rt和Data在RegWr后到達怎么辦？同樣，這里也有問題！流水線中的“競爭”問題多周期中解決Addr和WrEn之間競爭問題的方法:在第N周期結束時，讓Addr信號有效在第N+1周期讓WrEn有效上述方法在流水線設計中不能用，因為：每個周期必須能夠寫Register每個周期必須能夠寫MemoryClockIfetchReg/DecExecMemWrStoreIfetchReg/DecExecMemWrStoreIfetchReg/DecExecMemWrR-typeIfetchReg/DecExecMemWrR-type如何解決?保證Addr信號在WriteEnable信號之前到達寄存器組的同步和存儲器的同步解決方案:將WriteEnable和時鐘信號“與”1.Addr,Data,和WrEn必須在Clk邊沿到來后至少穩(wěn)定一個set-up時間2.Clk高電平時間大于寫入時間ClkAddressDataWrEnReg

FileorMemoryWrEnI_AddrI_DataReg

FileorMemoryClkI_AddrI_WrEnAddressDataI_WrEnC_WrEnC_WrEnActual

write等價于須由電路專家確保不會發(fā)生“定時錯誤”（即：能合理設計“Clock”!）相當于單周期通路中的理想寄存器和存儲器流水線舉例：考察流水線DataPath的數(shù)據(jù)流動情況End

ofCycle4EndofCycle5End

ofCycle

6End

ofCycle7ClockCycle1Cycle2Cycle3Cycle4Cycle5Cycle6Cycle7Cycle8IfetchReg/DecExecMemWr0:LoadIfetchReg/DecExecMemWr4:R-typeIfetchReg/DecExecMemWr8:StoreIfetchReg/DecExecMemWr12:Beq(targetis1000)EndofCycle4:Load’sMem,R-type’sExec,Store’sReg,Beq’sIfetchEndofCycle5:Load’sWr,R-type’sMem,Store’sExec,Beq’sRegEndofCycle6:R-type’sWr,Store’sMem,Beq’sExecEndofCycle7:Store’sWr,Beq’sMem考察以下幾個點的情況：說明：后面僅考察數(shù)據(jù)流動情況，控制信號隨數(shù)據(jù)同步流動因而不再說明。第四周期結束時的狀態(tài)：0:Load’sMem4:R-type’sExec8:Store’sReg12:Beq’sIfetchIF/ID:BeqInstructionID/Ex:Store’sbusA&BEx/Mem:R-type’sResultMem/Wr:Load’sDoutPC=16DataMemWADiRADoIUnitAIRFileDiRaRbRwRegWr=?ExtOp=xExecUnitbusAbusBImmALUOp=R-typeALUSrc=0Mux10MemtoReg=?10RegDst=1RtRdImmPC+4PC+4RsRtPC+4ZeroBranch=01012:Beq’sIfet8:Store’s

Reg4:R-type’sExec0:Load’sMemClkMemWr=0Clk如果Mem階段是Branch且Zero為1，會怎樣？

?’sWrLoad指令前某指令（1）（2）（3）（5）（4）第五周期結束時的狀態(tài)：0:Lw’sWr4:R’sMem8:Store’sExec12:Beq’sReg16:R’sIfetchIF/ID:Instruction@16ID/Ex:Beq’sbusA&BEx/Mem:Store’sAddressMem/Wr:R-type’sResultPC=20DataMemWADiRADoIUnitAIRFileDiRaRbRwRegWr=1ExtOp=1ExecUnitbusAbusBImmALUOp=AddALUSrc=1Mux10MemtoReg=110RegDst=xRtRdImmPC+4PC+4RsRtPC+4ZeroBranch=01016:R’sIfet12:Beq’s

Reg8:Store’sExec4:R-type’sMemClkMemWr=0Clk同一周期寄存器有讀和寫，可能嗎？利用時鐘上升和下降沿兩次觸發(fā)，能做到前半周期寫，后半周期讀寄存器的寫口和讀口可看成是獨立的兩個部件！0:Load’sWr20第六周期結束時的狀態(tài)：4:R’sWr8:Store’sMem12:Beq’sExec16:R’sReg20:R’sIfetIF/ID:Instruction@20ID/Ex:R-type’sbusA&BEx/Mem:Beq’sResultsMem/Wr:NothingforStPC=24DataMemWADiRADoIUnitAIRFileDiRaRbRwRegWr=1ExtOp=1ExecUnitbusAbusBImmALUOp=SubALUSrc=0Mux10MemtoReg=010RegDst=xRtRdImmPC+4PC+4RsRtPC+4ZeroBranch=01020:R-type’s

Ifet16:R-type’sReg12:Beq’sExec8:Store’sMem4:R-type’sWrClkMemWr=1ClkIfetch和Reg兩個周期每條指令執(zhí)行的都一樣！第七周期結束時的狀態(tài)：8:Store’sWr12:Beq’sMem16:R’sExec20:R’sReg24:R’sIfetIF/ID:Instruction@24ID/Ex:R-type’sbusA&BEx/Mem:Rtype’sResultsMem/Wr:NothingforBeqPC=1000DataMemWADiRADoIUnitAIRFileDiRaRbRwRegWr=0ExtOp=xExecUnitbusAbusBImmALUOp=R-typeALUSrc=0Mux10MemtoReg=x10RegDst=1RtRdImmPC+4PC+4RsRtPC+4ZeroBranch=11024:R-type’s

Ifet20:R-type’sReg16:R-type’sExec12:Beq’sMem8:Store’sWrClkMemWr=0Clk假定相等，則Zero=1轉移目標地址送PC!這里出現(xiàn)反向數(shù)據(jù)流!轉移目標地址反向送給PC可能會導致控制冒險！總結前面的流水線執(zhí)行過程（有關beq）Branch指令何時確定是否轉移？轉移目標地址在第幾周期計算出來？第六周期得到Zero和轉移地址、第七周期控制轉移地址送到PC輸入端、第八周期開始才能根據(jù)轉移地址取指令如果Branch指令執(zhí)行結果是需要轉移（稱為taken），則流水線會怎樣？ClockCycle1Cycle2Cycle3Cycle4Cycle5Cycle6Cycle7Cycle8IfetchReg/DecExecMemWr0:LoadIfetchReg/DecExecMemWr4:R-typeIfetchReg/DecExecMemWr8:StoreIfetchReg/DecExecMemWr12:Beq(targetis1000)IfetchReg/DecExecMemWr16:R-typeIfetchReg/DecExecMemWrIfetchReg/DecExecMem24:R-type20:R-typeIfetchReg/DecExec1000:TargetofBr轉移分支指令(Branch)引起的“延遲”現(xiàn)象雖然Beq指令在第四周期取出，但:目標地址在第七周期才被送到PC的輸入端第八周期才能取出目標地址處的指令執(zhí)行結果：在取目標指令之前，已有三條指令被取出，取錯了三條指令！這種現(xiàn)象稱為控制冒險（ControlHazard）（注：也稱為分支冒險或轉移冒險（BranchHazard）

）Cycle4Cycle5Cycle6Cycle7Cycle8Cycle9Cycle10Cycle11ClkIfetchReg/DecExecMemWrIfetchReg/DecExecMemWr16:R-typeIfetchReg/DecExecMemWrIfetchReg/DecExecMemWr24:R-type12:Beq(targetis1000)20:R-typeIfetchReg/DecExecMemWr1000:TargetofBr總結前面的流水線執(zhí)行過程（有關load）Load指令何時能把數(shù)據(jù)寫到寄存器？第幾周期開始寫數(shù)據(jù)？第五周期寫入、第六周期開始才能使用如果后面R-Type的操作數(shù)是load指令目標寄存器的內容，則流水線怎樣？ClockCycle1Cycle2Cycle3Cycle4Cycle5Cycle6Cycle7Cycle8IfetchReg/DecExecMemWr0:LoadIfetchReg/DecExecMemWr4:R-typeIfetchReg/DecExecMemWr8:Store12:Beq(targetis1000)16:R-type24:R-type20:R-type1000:TargetofBr裝入指令(Load)引起的“延遲”現(xiàn)象盡管Load指令在第一周期就被取出，但:數(shù)據(jù)在第五周期結束才被寫入寄存器在第六周期時，寫入的數(shù)據(jù)才能被用結果：在Load指令結果有效前，已經(jīng)有三條指令被取出(如果隨后的指令要用到Load的數(shù)據(jù)的話，就需要延遲三條指令才能用！)這種現(xiàn)象被稱為數(shù)據(jù)冒險(DataHazard)

或數(shù)據(jù)相關(DataDependency

)ClockCycle1Cycle2Cycle3Cycle4Cycle5Cycle6Cycle7Cycle8IfetchReg/DecExecMemWrI0:LoadIfetchReg/DecExecMemWrPlus1IfetchReg/DecExecMemWrPlus2IfetchReg/DecExecMemWrPlus3IfetchReg/DecExecMemWrR-Type寄存器的使用方式對數(shù)據(jù)冒險有影響數(shù)據(jù)在第五周期的前半段寫入寄存器在第五周期的后半段，寫入的數(shù)據(jù)才能被用結果：在Load指令結果有效前，已經(jīng)有兩條指令被取出(如果隨后的指令要用到Load的數(shù)據(jù)的話，就需要延遲兩條指令才能用！)ClockCycle1Cycle2Cycle3Cycle4Cycle5Cycle6Cycle7Cycle8IfetchReg/DecExecMemWrI0:LoadIfetchReg/DecExecMemWrPlus1IfetchReg/DecExecMemWrPlus2IfetchReg/DecExecMemWrR-Type第一講內容小結指令的執(zhí)行可以像洗衣服一樣，分為N個步驟，并用流水線方式進行均衡時指令吞吐率提高N倍，但不能縮短一條指令的執(zhí)行時間流水段數(shù)以最復雜指令所需步驟數(shù)為準（有些指令的某些階段為空操作），每個階段的寬度以最復雜階段所需時間為準（盡量調整使各階段均衡）以Load指令為準，分為五個階段取指令段(IF)取指令、計算PC+4（IUnit：InstructionMemory、Adder）譯碼/讀寄存器(ID/Reg)段指令譯碼、讀Rs和Rt（寄存器讀口）執(zhí)行(EXE)段計算轉移目標地址、ALU運算（Extender、ALU、Adder）存儲器(MEM)段讀或寫存儲單元（DataMemory）寫寄存器(Wr)段ALU結果或從DM讀出數(shù)據(jù)寫到寄存器（寄存器寫口）流水線控制器的實現(xiàn)IF和ID/Reg段不需控制信號控制，只有EXE、MEM和Wr需要ID段生成所有控制信號，并隨指令的數(shù)據(jù)同步向后續(xù)階段流動寄存器和存儲器的競爭問題可利用時鐘信號來解決流水線冒險：結構冒險、控制冒險、數(shù)據(jù)冒險（下一講主要介紹解決流水線冒險的數(shù)據(jù)通路如何設計）第二講流水線冒險的處理流水線冒險的幾種類型數(shù)據(jù)冒險的現(xiàn)象和對策數(shù)據(jù)冒險的種類相關的數(shù)據(jù)是ALU結果：可以通過轉發(fā)解決相關的數(shù)據(jù)是DM讀出的內容：隨后的指令需被阻塞一個時鐘數(shù)據(jù)冒險和轉發(fā)轉發(fā)檢測/轉發(fā)控制數(shù)據(jù)冒險和阻塞阻塞檢測/阻塞控制控制冒險的現(xiàn)象和對策靜態(tài)分支預測技術動態(tài)分支預測技術縮短分支延遲技術流水線中對異常和中斷的處理訪問缺失對流水線的影響主要內容Hazards：指流水線遇到無法正確執(zhí)行后續(xù)指令或執(zhí)行了不該執(zhí)行的指令Structuralhazards

Datahazards:Control(Branch)

hazards總結：流水線的三種沖突/冒險（Hazard）情況MemStructuralHazard（結構冒險）現(xiàn)象Time(clockcycles)LoadInstr1Instr2Instr3Instr4ALUMemRegMemRegALUMemRegMemRegALUMemRegMemRegALURegMemRegALUMemRegMemReg如果只有一個存儲器，則在Load指令取數(shù)據(jù)同時又取指令的話，則發(fā)生沖突！如果不對寄存器堆的寫口和讀口獨立設置的話，則發(fā)生沖突！結構冒險也稱為硬件資源沖突：同一個執(zhí)行部件被多條指令使用。RegStructuralHazard的解決方法Instr.OrderTime(clockcycles)LoadInstr1Instr2Instr3Instr4ALUImRegDmALUImRegDmALUImRegDmRegALURegDmRegALUImRegDmReg將InstructionMemory(Im)

和DataMemory(Dm)分開將寄存器讀口和寫口獨立開來Im為了避免結構冒險，規(guī)定流水線數(shù)據(jù)通路中功能部件的設置原則為：每個部件在特定的階段被用?。ㄈ纾篈LU總在第三階段被用?。㏑egBACKDataHazard現(xiàn)象addr1

,r2,r3subr4,r1

,r3andr6,r1

,r7orr8,r1

,r9xorr10,r1

,r11想一下，哪條指令的r1是老的值？哪條是新的值？畫出流水線圖能很清楚理解！舉例說明：以下指令序列中，寄存器r1會發(fā)生數(shù)據(jù)冒險本講介紹基本流水線，僅考慮RAW冒險DataHazardonr1Instr.OrderTime(clockcycles)addr1,r2,r3subr4,r1,r3andr6,r1,r7orr8,r1,r9xorr10,r1,r11IFID/RFEXMEMWBALUImRegDmRegALUImRegDmRegALUImRegDmRegImALURegDmRegALUImRegDmReg最后一條指令的r1才是新的值！如何解決這個問題？方案1:在硬件上采取措施，使相關指令延遲執(zhí)行Instr.OrderTime(clockcycles)addr1,r2,r3subr4,r1,r3andr6,r1,r7IFID/RFEXMEMWBALUImRegDmRegALUImRegDmRegstallstallstallALUImRegDmbubblebubblebubblebubbleImbubblebubblebubblebubbleImbubblebubblebubblebubbleIm

硬件上通過阻塞(stall)方式阻止后續(xù)指令執(zhí)行，延遲到有新值以后！這種做法稱為流水線阻塞，也稱為“氣泡Bubble”缺點：控制相當復雜，需要改數(shù)據(jù)通路！方案2:軟件上插入無關指令Instr.OrderTime(clockcycles)addr1,r2,r3subr4,r1,r3andr6,r1,r7IFID/RFEXMEMWBALUImRegDmRegALUImRegDmReg

最差的做法：由編譯器插入三條NOP指令，浪費三條指令的空間和時間nopnopnopALUImRegDmALUImRegDmRegALUImRegDmRegImALURegDmReg方案3:利用DataPath中的中間數(shù)據(jù)Instr.OrderTime(clockcycles)addr1,r2,r3subr4,r1,r3andr6,r1,r7orr8,r1,r9xorr10,r1,r11IFID/RFEXMEMWBALUImRegDmRegALUImRegDmRegALUImRegDmRegImALURegDmRegALUImRegDmReg

仔細觀察后發(fā)現(xiàn)：流水段寄存器中已有需要的值r1！1.把數(shù)據(jù)從流水段寄存器中直接取到ALU的輸入端2.寄存器寫/讀口分別在前/后半周期，使寫入被直接讀出稱為轉發(fā)（Forwading）或旁路（Bypassing）在哪個流水段R中？硬件上的改動以支持“轉發(fā)”技術(自學)加MUX，使流水段寄存器值返送ALU輸入端假定流水段寄存器能讀出新寫入的值(否則，需要更多的轉發(fā)數(shù)據(jù))addr3,r2,r1Subr5,r3,r4addr3,r2,r1Orr6,r2,r1Subr5,r3,r4lwr3,100(r1)Orr6,r2,r1Subr5,r3,r4lwr3,100(r1)Orr6,r3,r1如果指令序列為：能用“轉發(fā)”技術解決這里的數(shù)據(jù)冒險嗎？ExMem復習:Load指令引起的延遲現(xiàn)象Load指令最早在哪個流水線寄存器中開始有后續(xù)指令需要的值？ClockCycle1Cycle2Cycle3Cycle4Cycle5Cycle6Cycle7Cycle8IfetchReg/DecExecMemWrI0:LoadIfetchReg/DecExecMemWrPlus1IfetchReg/DecExecMemWrPlus2IfetchReg/DecExecMemWrPlus3IfetchReg/DecExecMemWrPlus4實際上，在第四周期結束時，數(shù)據(jù)在流水段寄存器中已經(jīng)有值。采用數(shù)據(jù)轉發(fā)技術可以使load指令后面第二條指令得到所需的值但不能解決load指令和隨后的第一條指令間的數(shù)據(jù)冒險，要延遲執(zhí)行一條指令！這種load指令和隨后指令間的數(shù)據(jù)冒險，稱為“裝入-使用數(shù)據(jù)冒險(load-useDataHazard)”若不采用轉發(fā)，則在何時才能用使用Load指令的結果？延遲2或3條指令！“Forwarding”技術使Load-use冒險只需延遲一個周期Instr.OrderTime(clockcycles)lwr1,0(r2)subr7,r1,r3andr6,r1,r7orr8,r1,r9IFID/RFEXMEMWBALUImRegDmRegALUImRegDmRegALUImRegDmRegImALURegDmReg采用“轉發(fā)”后僅第二條指令SUBr7,r1,r3不能按時執(zhí)行！需要阻塞一個周期。（其它后續(xù)指令順延）發(fā)生“裝入-使用數(shù)據(jù)冒險”時，需要對load后的指令阻塞一個時鐘周期！方案1:硬件阻止指令執(zhí)行來解決load-useInstr.OrderTime(clockcycles)lwr1,0(r2)subr4,r1,r3IFID/RFEXMEMWBALUImRegDmRegstallbubblebubblebubblebubbleImandr6,r1,r7orr8,r1,r9ALUImRegDmRegALUImRegDmRegImALURegDmReg用硬件阻塞一個周期方案2:軟件上插入NOP指令來解決load-useInstr.OrderTime(clockcycles)lwr1,0(r2)subr4,r1,r3IFID/RFEXMEMWB用軟件插入一條NOP指令！（有些處理器不支持硬件阻塞處理）例如：MIPS1處理器沒有硬件阻塞處理，而由編譯器（或匯編程序員）來處理。nopandr6,r1,r7orr8,r1,r9ALUImRegDmRegALUImRegDmRegImALURegDmRegALUImRegDmRegALUImRegDmReg以下源程序可生成兩種不同的代碼，優(yōu)化的代碼可避免Load阻塞 a=b+c; d=e–f;假定a,b,c,d,e,f在內存方案3：編譯器進行指令順序調整來解決load-useFastcode:

lw $2,b lw $3,c

lw $5,e add $1,$2,$3 lw $6,f

sw a,$1 sub $4,$5,$6 sw d,$4

Slowcode:

lw $2,b lw $3,c add $1,$2,$3

sw a,$1 lw $5,e

lw $6,f sub $4,$5,$6 sw d,$4調整后編譯器的優(yōu)化很重要！真正執(zhí)行時需阻塞2次真正執(zhí)行時無需阻塞階段小結：數(shù)據(jù)冒險的解決方法方法1：硬件阻塞（stall）方法2：軟件插入“NOP”指令方法3：編譯優(yōu)化：調整指令順序，能解決所有數(shù)據(jù)冒險嗎？方法4：合理實現(xiàn)寄存器堆的讀/寫操作，能解決所有數(shù)據(jù)冒險嗎？前半時鐘周期寫，后半時鐘周期讀，若同一個時鐘內前面指令寫入的數(shù)據(jù)正好是后面指令所讀數(shù)據(jù)，則不會發(fā)生數(shù)據(jù)冒險方法5：轉發(fā)（Forwarding或Bypassing旁路）技術，能解決所有數(shù)據(jù)冒險嗎？若相關數(shù)據(jù)是ALU結果，則如何？

可通過轉發(fā)解決若相關數(shù)據(jù)是上條指令DM讀出內容，則如何？不能通過轉發(fā)解決，隨后指令需被阻塞一個時鐘或加NOP指令實現(xiàn)“轉發(fā)”和“阻塞”要修改數(shù)據(jù)通路：（1）檢測何時需要“轉發(fā)”，并控制實現(xiàn)“轉發(fā)”（2）檢測何時需要“阻塞”，并控制實現(xiàn)“阻塞”稱為Load-use數(shù)據(jù)冒險！帶轉發(fā)的流水線數(shù)據(jù)通路ForwardAForwardBLoad-useDataHazard（硬件阻塞方式）Instr.OrderTime(clockcycles)lwr1,0(r2)subr4,r1,r3IFID/RFEXMEMWBALUImRegDmRegImandr6,r1,r7orr8,r1,r9ALUImRegDmRegALUImRegDmRegImALURegDmReg檢測點需解決以下問題：(1)判斷什么條件下需要阻塞阻塞點RegID/EX.MemReadand(ID/EX.RegisterRt=IF/ID.RegisterRsorID/EX.RegisterRt=IF/ID.RegisterRt)前面指令為Load并且前面指令的目的寄存器等于當前剛取出指令的源寄存器(2)修改數(shù)據(jù)通路來實現(xiàn)阻塞:ID/EX控制信號清空,PC和IF/ID內容不變bubblebubblebubblesubr4,r1,r3帶“轉發(fā)”和“阻塞”檢測的流水線數(shù)據(jù)通路至此，數(shù)據(jù)冒險的處理全部完成！ID/EX.MemReadand(ID/EX.RegisterRt=IF/ID.RegisterRsorID/EX.RegisterRt=IF/ID.RegisterRt)“寫使能”信號為0，使PC和IF/ID不變使控制信號清0，阻塞隨后指令?、佗冖?ControlHazard的解決方法方法1：硬件上阻塞（stall）分支指令后三條指令的執(zhí)行使后面三條指令清0或其操作信號清0，以插入三條NOP指令方法2：軟件上插入三條“NOP”指令

（以上兩種方法的效率太低，需結合分支預測進行）方法3：分支預測（Predict）簡單（靜態(tài)）預測：總是預測條件不滿足(nottaken)或滿足， 即：繼續(xù)執(zhí)行分支指令的后續(xù)指令動態(tài)預測：根據(jù)程序執(zhí)行的歷史情況，進行動態(tài)預測調整，能達90%的預測準確率注：采用分支預測方式時，流水線控制必須確保錯誤預測指令的執(zhí)行結果不能生效，而且要能從正確的分支地址處重新啟動流水線工作方法4：延遲分支（Delayedbranch）（通過編譯程序優(yōu)化指令順序?。┌逊种е噶钋懊媾c分支指令無關的指令調到分支指令后面執(zhí)行，也稱延遲轉移另一種控制冒險：異?；蛑袛嗫刂泼半U的處理簡單（靜態(tài)）分支預測方法基本做法總預測條件不滿足(nottaken)，即：繼續(xù)執(zhí)行分支指令的后續(xù)指令可加啟發(fā)式規(guī)則：在特定情況下總是預測滿足(taken)，其他情況總是預測不滿足如：循環(huán)頂（底）部分支總是預測為不滿足（滿足）。能達65%-85%的預測準確率預測失敗時，需把流水線中三條錯誤預測指令丟棄掉將三條丟棄指令的控制信號值設置為0，使其后續(xù)過程中執(zhí)行nop操作（注：涉及到當時在IF、ID和EX三個階段的指令）性能如果轉移概率是50%，則預測正確率僅有50%預測錯誤的代價預測錯誤的代價與何時能確定是否轉移有關。越早確定代價越少那最早可以提前到哪個階段呢？復習:

ControlHazard現(xiàn)象雖然Beq指令在第四周期取出，但:第七周期才確定“是否轉移”第八周期才轉移到正確指令執(zhí)行發(fā)生轉移時，要在流水線中清除Beq后面的三條指令延遲損失時間片C：發(fā)生轉移時，給流水線帶來的延遲損失Cycle4Cycle5Cycle6Cycle7Cycle8Cycle9Cycle10Cycle11IfetchReg/DecExecMemWrIfetchReg/DecExecMemWr16:R-typeIfetchReg/DecExecMemWrIfetchReg/DecExecMemWr24:R-type12:Beq(targetis1000)20:R-typeClkIfetchReg/DecExecMemWr1000:TargetofBr這里C=3簡單（靜態(tài)）分支預測方法縮短分支延遲，減少錯誤預測代價可以通過調整“轉移地址計算”和“分支條件判斷”操作到ID階段來縮短延遲缺點：增加處理部件和線路。優(yōu)點：C=1（原來C=3）預測錯誤的檢測和處理（稱為“沖刷、沖洗”--Flush）增加控制信號，為‘1’時代表預測失敗預測失敗時，完成以下兩件事：將轉移目標地址->PC清除IF(&EX&MEM)段中信息延遲C（1-3）個時鐘周期！動態(tài)分支預測方法簡單的靜態(tài)分支預測方法的預測成功率不高，所以應考慮動態(tài)預測動態(tài)預測基本思想：利用最近轉移發(fā)生的情況，來預測下一次可能發(fā)生的轉移實際執(zhí)行時：驗證并調整預測轉移發(fā)生的歷史情況記錄在BHT中現(xiàn)在幾乎所有的處理器都采用動態(tài)預測（dynamicpredictor）分支歷史記錄表BHT指令預取器分支指令地址轉移目標地址預測位分支指令地址控制邏輯指令執(zhí)行實際執(zhí)行情況命中與否加入新項順序取轉移取分支歷史記錄表BHT=？查找①選擇③②預測④修正查找時發(fā)現(xiàn)都不相等，則“未命中”未命中說明什么？說明以前沒有執(zhí)行過該分支指令

命中時：

根據(jù)預測位，選擇“轉移取”還是“順序取”未命中時：

加入新項，并填入指令地址和轉移目標地址、初始化預測位動態(tài)預測基本方法采用一位預測位：總是按上次實際發(fā)生的情況來預測下次用1位（0或1）表示預測和實際轉移情況可根據(jù)一個簡單的預測狀態(tài)圖進行預測和調整采用二位預測位用2位（00,01,10,11）來表示預測和實際轉移情況同樣可按預測狀態(tài)圖進行預測和調整采用比較多的是二位預測位，也有采用二位以上預測位。如：Pentium4的BTB2采用4位預測位一位預測狀態(tài)圖指令預取時，按照預測讀取相應分支的指令‘1’：選擇“轉移取”‘0’：選擇“順序取”指令執(zhí)行時，按實際執(zhí)行結果修改預測位對照狀態(tài)轉換圖來進行修改例如：對于一個循環(huán)分支若初始狀態(tài)為0(再次循環(huán)時為0)，則第一次和最后一次都錯若初始狀態(tài)為1，則只有最后一次會錯預測發(fā)生發(fā)生不發(fā)生預測不發(fā)生不發(fā)生發(fā)生10正確錯誤錯誤正確Loop:add$7,$3,$3;i*2 add$7,$7,$7 ;i*4 add$7,$7,$5 lw$6,0($7) ;$6=A[i] add$1,$1,$6 ;g=g+A[i] add$3,$3,$4 bne$3,$2,Loop

……Loop: g=g+A[i]; i=i+j; if(i!=h)gotoLoop:舉例：雙重循環(huán)的一位動態(tài)預測intosum(intN){inti,j,sum=0;for(i=0;i<N;i++)for(j=0;j<N;j++)sum=sum+1;returnsum;}……Loop-i:beq$t1,$a0,exit-i#若(i=N)則跳出外循環(huán)