第3章-1流水線技術(shù)

1

課程內(nèi)容第1章計算機設(shè)計基礎(chǔ)第2章附錄B指令系統(tǒng)原理與實例第3章附錄A流水線：基礎(chǔ)和中級概念，

流水線模型機第4章指令級并行及其開發(fā)（教材第2章）第5章附錄C存儲層次結(jié)構(gòu)回顧存儲器層次結(jié)構(gòu)設(shè)計第6章多處理器和線程級并行（教材第4章）

附錄A流水線技術(shù)A.1

流水線的基本概念A.2

流水線的主要障礙---流水線冒險（相關(guān)）A.3

流水線處理機及其設(shè)計流水線的相關(guān)

（李亞民教材相關(guān)內(nèi)容）A.4

異常事件處理A.5擴展流水線到多周期操作23一、什么是流水線?二、RISC指令系統(tǒng)特點三、非流水線方式下RISC指令系統(tǒng)的實現(xiàn)四、經(jīng)典5段流水線RISC處理器五、流水線的基本性能A.1 流水線的基本概念4一、什么是流水線？

流水線是利用執(zhí)行指令操作之間的并行性，實現(xiàn)多條指令重疊執(zhí)行的技術(shù)?！霸谇耙粭l指令執(zhí)行完畢之前開始執(zhí)行本條指令。”

當今，流水線是實現(xiàn)更快CPU的基本和關(guān)鍵技術(shù)。不僅是實現(xiàn)CPU:12級流水線用于幾何變換的GPU中。目標5例：假定一條指令的執(zhí)行分為三個階段：取指令、分析、執(zhí)行。下圖表示了三種執(zhí)行方式相鄰指令間的時序關(guān)系。流水段（級）：完成一條指令的一部分操作并行

機器周期30ns90ns指令流入取指令部件分析部件執(zhí)行部件

指令流出二次重疊執(zhí)行方式的指令流水線：流水線鎖存器1913年福特密歇根工廠移動裝配線

（84個步驟）類似于工廠的自動裝配線：由工人、機器、裝配件構(gòu)成，通過工人不斷對產(chǎn)品進行裝配直至完成。6指令流入取指令部件分析部件執(zhí)行部件

指令流出二次重疊執(zhí)行方式的指令流水線：機器周期（流水線周期）：指令沿流水線移動一個流水段的時間。長度取決于最慢的流水段，一般是一個時鐘周期（有時是兩個時鐘周期）。每個流水線周期從指令流水線流出一條指令。吞吐量：單位時間從流水線流出的指令數(shù)。流水線寄存器（鎖存器）788流水段（級）：完成一條指令的一部分操作并行

機器周期30ns90ns流水線設(shè)計者：平衡每個流水段的時間，使之等長。因此，每條指令在流水線的平均時間在理想情況下為：非流水線機器平均指令執(zhí)行時間

流水線機器段數(shù)理想情況：流水線的加速比等于流水線機器的段數(shù)。流水線減少了指令執(zhí)行的平均時間（減少了CPI或時鐘周期）流水線技術(shù)（硬件實現(xiàn)）對編程者透明9非流水線機器平均指令執(zhí)行時間

流水線機器平均指令執(zhí)行時間10流水線特點一個流水線類似自動裝配線一個流水線有多個段（級），段間有流水線寄存器每個流水段執(zhí)行指令或操作的不同部分流水段之間采用同步時鐘控制一條指令或操作從流水線一端進入，經(jīng)過各段，從另一端流出流水線是開發(fā)串行指令流中并行性的一種實現(xiàn)技術(shù)11為什么采用流水線：結(jié)論制造快速CPU的關(guān)鍵技術(shù)：減少

CPUtime.改進吞吐量改進資源利用率12為什么不開發(fā)50段流水線?有些操作不能分為更細的邏輯實現(xiàn)5stagesOK50stagesNO.Sorry!流水線鎖存器不是免費的，要占據(jù)面積，且有延遲。機器周期>鎖存器延遲+時鐘偏移13流水線段數(shù)實例E.g.,IntelPentiumIII,Pentium4:20+stages正在執(zhí)行的指令超過20條時鐘頻率(>1GHz)高IPC

（每個時鐘周期執(zhí)行的指令數(shù)）太多的段數(shù):非常復雜處理正在執(zhí)行指令之間

的冒險（相關(guān)）控制邏輯很大14二、RISC指令系統(tǒng)特點RISC系統(tǒng)結(jié)構(gòu)有以下幾個關(guān)鍵特點：所有參加運算的數(shù)據(jù)來自寄存器，結(jié)果也寫入寄存器。寄存器為32/64位。訪存只有l(wèi)oad和store指令指令的數(shù)量較少，所有指令長度相同。這種結(jié)構(gòu)可以有效地簡化流水線的實現(xiàn)。MIPS系統(tǒng)是默認的RISC系統(tǒng)結(jié)構(gòu)。三、非流水線方式下RISC指令系統(tǒng)的實現(xiàn)假定指令系統(tǒng)是MIPS的一個定點子集：

load/store指令，ALU指令，轉(zhuǎn)移指令。一條指令的執(zhí)行過程（多周期）最多需要5個時鐘周期：LoadStoreR-typeClkCycle1Cycle2Cycle3Cycle4Cycle5Cycle6Cycle7Cycle8Cycle9Cycle10Multip-CycleImplementation:

CPI=5,

IFIDEXMEMWBIFIDEXMEMWB（非流水線單周期指令系統(tǒng)實現(xiàn)不介紹）15多周期實現(xiàn)

Multi-cycleimplementation例：Loadr1,10(r4)175個周期IF:Instructionfetchcycle按照

PC內(nèi)容訪問指令存儲器，取出指令PC+4→NPC，以獲取下一條指令地址ID:Instructiondecode/registerfetchcycle指令譯碼讀寄存器如果需要，符號擴展指令中的位移量18EX:Execution/effectiveaddresscycleLoad/Store:

計算數(shù)據(jù)存儲器有效地址R-R/R-IALU:

執(zhí)行運算操作Branch:

做“=0？”測試，如果條件滿足計算目標地址送PCMEM:MemoryaccessLoad:

送有效地址到數(shù)據(jù)存儲器，取數(shù)據(jù)Store:

寫ID讀出數(shù)據(jù)到有效地址單元中

WB:Write-backcycleLoadorALU:寫結(jié)果到寄存器堆

19多周期實現(xiàn)

Multi-cycleimplementation例：addr1,r2,r3；r2+r3->r1

例：Loadr1,10(r4)20多周期實現(xiàn)例：store20（r2），r321多周期實現(xiàn)例：BEQr1,24

；if

r1=r0，

（NPC）

+24-

>

PC

22Single-cycleimplementation（參考）seldomused!SingleCycleImplementation:

CPI=1,longclockcycle

ClkLoadStoreWasteCycle1Cycle2多周期實現(xiàn)24多周期實現(xiàn)的特點數(shù)據(jù)路徑中的暫存器易于實現(xiàn)流水線注意：branch和Store指令花費

4clockcycles.假定branch執(zhí)行頻率12%，store執(zhí)行頻率10%,CPI是

4.78.

這種實現(xiàn)是沒有優(yōu)化的.4×（12％＋10％）＋5×78%＝4.7825怎樣改進多周期實現(xiàn)的性能？對于branch,將“=0？”測試和計算可能的轉(zhuǎn)移目標地址提前到ID.完成

ALU指令在MEMcyclebranch指令占2

cycles,store和

ALU指令占

4

cycles,只有l(wèi)oad指令占

5cycles.CPI降到4.07

，假定ALU指令操作頻率47%

2×12％＋4×（10％＋47％）＋31%×5＝4.0726優(yōu)化的多周期實現(xiàn)Temporarystoragelocations27改進硬件冗余ALU可以共享

數(shù)據(jù)和指令存儲器可以合并，因為訪問發(fā)生在不同的時鐘周期28四、經(jīng)典5段流水線RISC處理器5個段構(gòu)成了一個指令流水線，一條指令經(jīng)過每個段。

CPI減少到1，因為平均每個時鐘周期發(fā)射或完成一條指令。在任意時鐘周期，在每個流水段正執(zhí)行一條指令的部分。

Ideally,performanceisincreasedfivefold!

29storeload5-段流水線

MIPS數(shù)據(jù)通路pipelineregistersorlatches

30流水線怎樣減少執(zhí)行時間？

對比不同串行實現(xiàn)的機器：每條指令執(zhí)行用一個時鐘周期的機器（單周期實現(xiàn)）流水線減少時鐘周期的長度（時間）

每條指令執(zhí)行用多個時鐘周期的機器（多周期實現(xiàn)）流水線減少CPI.31單周期實現(xiàn)比較流水線LoadIFIDEXMEMWBIFIDEXMEMWBStoreIFIDEXMEMWBR-typeSingleCycleImplementation:

CPI=1,longclockcycle

ClkLoadStoreWasteCycle1Cycle2PipelineImplementation:

CPI=1,clockcyclelongclockcycle/5ClkCycle1Cycle2Cycle3Cycle4Cycle5Cycle6Cycle7Cycle8Cycle9Cycle1032LoadStoreR-typeClkCycle1Cycle2Cycle3Cycle4Cycle5Cycle6Cycle7Cycle8Cycle9Cycle10ClkCycle1Cycle2Cycle3Cycle4Cycle5Cycle6Cycle7Cycle8Cycle9Cycle10Multip-CycleImplementation:

CPI=5,

PipelineImplementation:

CPI=1,LoadIFIDEXMEMWBIFIDEXMEMWBStoreIFIDEXMEMWBR-typeIFIDEXMEMWBIFIDEXMEMWB多周期實現(xiàn)比較流水線33storeload流水線真如此簡單嗎？pipelineregistersorlatches

Whyneedtoaddthisline?34引入流水線后出現(xiàn)的問題注意：在同一時鐘周期不同操作不能使用同一數(shù)據(jù)通路資源。(結(jié)構(gòu)冒險structurehazard)有訪問存儲器沖突！

MemInstr.OrderTime(clockcycles)Ld/StInstr1Instr2Instr3ALUMemRegMemRegALUMemRegMemRegALUMemRegMemRegALURegMemReg35分離的數(shù)據(jù)存儲器和指令存儲器使用分開的指令cache和數(shù)據(jù)cache如果時鐘周期不變，流水線存儲系統(tǒng)的帶寬必須是非流水線的5倍。IMInstr.OrderTime(clockcycles)Ld/StInstr1Instr2Instr3ALUIMRegDMRegALUIMRegDMRegALUIMRegDMRegALURegDMReg36寄存器沖突！37重新設(shè)計寄存器堆資源允許在一個時鐘周期WB段先寫，ID段后讀每個時鐘周期完成2個讀和一個寫需要提供2個讀端口和一個寫端口當寫和讀同一個寄存器會發(fā)生什么？

(數(shù)據(jù)冒險

Datahazard)38當更新PC時產(chǎn)生沖突每個時鐘周期必須增量PC并存儲到PC遇到轉(zhuǎn)移指令怎么辦？轉(zhuǎn)移可能會改變PC的值——但是條件要等到ID段才能得到！如果轉(zhuǎn)移發(fā)生，在IF段取到的轉(zhuǎn)移指令其后的指令是無效的！

這是一個需要處理的嚴重問題，稱為控制冒險(Controlhazard)。稍后會討論。39storeload流水線模型pipelineregistersorlatches

Whyneedtoaddthisline?40流水線寄存器必須引入嗎？保證處在不同段的指令不會相互干擾

通過流水線寄存器，不同段能夠一個接一個形成流水線流水線寄存器數(shù)目比多周期實現(xiàn)機器多得多IR:IF/ID.IR;ID/EX.IR;EX/DM.IR;DM/WB.IRB:ID/EX.B;EX/DM.BALUoutput:EX/DM.ALUoutput,DM/WB.ALUoutput任何后面段需要的值必須放在流水線寄存器中，而且會復制到其后的寄存器中直到不需要為止。41storeload流水線模型pipelineregistersorlatches

Whyneedtoaddthisline?42五、流水線的基本性能流水線增大了吞吐量（單位時間完成的指令條數(shù)）吞吐量大，程序運行更快，總的執(zhí)行時間變短，盡管每一條指令的執(zhí)行時間并沒有加快！43影響流水線性能的因素延遲：每條指令的執(zhí)行時間沒有減少，而且附加的一些控制會比非流水線實現(xiàn)增加開銷。不平衡：

各段時間以最慢的為基準，會降低性能附加開銷：流水線寄存器延遲和時鐘偏移，限制了時鐘周期頻率。流水線冒險（相關(guān)）：串行機器是不產(chǎn)生冒險的，冒險是達到理想性能的主要障礙“填充”流水線和“排空”流水線也會減少加速比A.2流水線的主要障礙—流水線冒險（相關(guān)）

一、冒險分類與有停頓流水線性能二、結(jié)構(gòu)冒險三、數(shù)據(jù)冒險四、控制冒險44一、冒險分類與有停頓流水線性能回顧：流水線以重疊方式執(zhí)行指令，制造快速CPU的實現(xiàn)技術(shù)(減少

CPUtime,改進吞吐量)流水線理想加速比：流水線的段數(shù)從執(zhí)行每條指令用多周期的機器角度：流水線減少了CPI.

45冒險分類冒險出現(xiàn)時：避免流水線上有冒險的指令執(zhí)行下一個流水段冒險分類結(jié)構(gòu)冒險

指令重疊執(zhí)行時，發(fā)生硬件資源沖突

數(shù)據(jù)冒險幾條指令重疊執(zhí)行時，一條指令依賴前面指令的結(jié)果卻沒有準備好（還沒有計算或存儲）控制冒險

：（流水線執(zhí)行轉(zhuǎn)移指令時）進入下一個時鐘周期時，轉(zhuǎn)移條件和轉(zhuǎn)移目標PC不能按時提供給IF段取指令。46數(shù)據(jù)冒險：例子47冒險總是可以用停頓解決解決冒險最簡單的方式就是停頓流水線停頓意味著為某些指令暫停流水線一個或多個時鐘周期。

一條指令被停頓后，其后的所有指令被停頓；該指令之前的指令必須繼續(xù)執(zhí)行。一個流水線停頓也稱為流水線氣泡或氣泡。

停頓時，沒有任何新的指令被取到流水線。48BubbleBubbleBubbleBubbleBubbleBubbleBubbleBubbleBubble怎樣停頓？

由編譯器插入

nop

指令（軟件）49有停頓的流水線性能停頓會降低流水線的性能，使其性能比理想的差回憶加速比公式：50非流水線是多周期實現(xiàn)的情況流水線處理器的理想CPI差不多總是1。

(maylessthanorgreaterthat)

因此：忽略流水線時鐘周期的額外開銷。流水段是理想平衡的。

51

因此：Clockcycleunpipelined=Clockcyclepipelining有：

Clockcycleunpipelined=ClockcyclepipeliningCPlunpipelined=pipelinedepth非流水線是多周期實現(xiàn)的情況52二、結(jié)構(gòu)冒險：流水段競爭Structuralhazards發(fā)生在同一個時鐘周期，2條或多條指令想要使用同一個硬件資源引起流水線機器停頓常見引起結(jié)構(gòu)冒險的情況：多重訪問寄存器堆多重訪問存儲器沒有或沒有充分流水功能部件53寄存器堆的多重訪問簡單插入停頓，將降低加速比在一個時鐘周期WB段先寫，ID段后讀54在一個時鐘周期WB段先寫，ID段后讀55多重訪問單端口存儲器插入停頓提供另一個存儲器端口分開的指令存儲器和數(shù)據(jù)存儲器使用指令緩沖器MemInstr.OrderTime(clockcycles)Ld/StInstr1Instr2Instr3ALUMemRegMemRegALUMemRegMemRegALUMemRegMemRegALURegMemReg56插入停頓

StallInstr.OrderTime(clockcycles)Ld/StInstr1Instr2Instr3ALUMemRegMemRegALUMemRegMemRegALUMemRegMemRegALUMemRegBubbleBubbleBubbleBubbleBubbleStall57無結(jié)構(gòu)冒險機器的CPI更低例子：load結(jié)構(gòu)冒險的影響

數(shù)據(jù)引用占程序的40%忽略結(jié)構(gòu)冒險的理想

CPI是1有結(jié)構(gòu)冒險的處理器時鐘頻率是無結(jié)構(gòu)冒險處理器時鐘頻率的1.05倍答案有結(jié)構(gòu)冒險平均指令執(zhí)行時間=CPIClockcycletime=(1+0.41)CCideal/1.05=1.3Ccideal顯然，無結(jié)構(gòu)冒險的處理器更快58IMInstr.OrderTime(clockcycles)Ld/StInstr1Instr2Instr3ALUIMRegDMRegALUIMRegDMRegALUIMRegDMRegALURegDMReg分開的指令與數(shù)據(jù)存儲器分開的指令和數(shù)據(jù)存儲器/多個存儲器端口/指令緩沖器

：

取指令和存取數(shù)據(jù)使用不同的硬件資源59沒有完全流水化的功能部件：

可能引起結(jié)構(gòu)冒險

60為什么允許結(jié)構(gòu)冒險？減少成本

如，增加分開的caches需要兩倍的存儲器帶寬完全流水浮點部件需要很多邏輯門如果結(jié)構(gòu)冒險不經(jīng)常發(fā)生，則消除冒險的成本就太高

減少部件延遲

制造流水的功能部件增加延遲

(流水線附加開銷->流水線寄存器)非流水線部件的每個操作需要更少的時鐘周期

減少延遲有其他的性能好處61結(jié)構(gòu)冒險總結(jié)TaxonomyofHazards

結(jié)構(gòu)冒險

硬件資源沖突解決：可以增加硬件資源；

或者功能部件完全流水

；

否則，只有停頓流水線DatahazardsInstructiondependsonresultofpriorcomputationwhichisnotready(computedorstored)yetControlhazards

branchconditionandthebranchPCarenotavailableintimetofetchaninstructiononthenextclock62三、數(shù)據(jù)冒險數(shù)據(jù)冒險：由于流水線上指令重疊執(zhí)行，改變了原來串行執(zhí)行的讀/寫操作數(shù)順序，使得后面依賴前面指令結(jié)果的指令得不到準備好的數(shù)據(jù)。例子：DADDR1,R1,R3DSUBR4,R1,R5ANDR6,R1,R7ORR8,R1,R9XORR10,R1,R1163數(shù)據(jù)冒險基本結(jié)構(gòu)一條指令想要使用還沒有“完成”的數(shù)據(jù)值“完成”表示“數(shù)據(jù)值已經(jīng)被計算了”和“值已經(jīng)被放好，正常情況可以在流水線硬件中找到它”原因習慣上總是假定采用純串行指令執(zhí)行模型對于k>=1，指令N在指令N+1之前完成在相鄰指令之間有依賴存在結(jié)論數(shù)據(jù)冒險---指令想要的數(shù)據(jù)值還沒有完成，或者值沒有在正確的地方64數(shù)據(jù)冒險：例子65寄存器堆WB段先寫，ID段后讀66提出的解決方法提出的解決方法不要讓指令在數(shù)據(jù)冒險時重疊執(zhí)行實施技術(shù)不要讓有冒險的指令流過流水線尤其是，不要在冒險時寫有CPU狀態(tài)的流水線硬件（如，寄存器堆、存儲器）讓指令等待直到冒險消除

操作名稱：流水線停頓67BubbleBubbleBubbleBubbleBubbleBubbleBubbleBubbleBubble怎樣停頓？

由編譯器插入

nop

指令（軟件）68怎樣停頓？

增加硬件互鎖（Interlock）

!增加額外硬件檢測需要停頓的情況觀察指令字段位（如，寄存器字段）在流水線特定段檢測是否有“先讀后寫”沖突增加額外硬件放“氣泡”（暫停）到流水線實際操作：讓有冒險的指令通過流水線，但是禁止允許任何結(jié)果寫入機器狀態(tài)的位因此,有冒險的指令“執(zhí)行”，但是不能“存入”69互鎖：

插入

stallsBubbleBubbleEmptyslotsinthepipecalledbubbles;meansnorealinstructionworkgettingsavedhere70Forwarding

（前推、直通、轉(zhuǎn)發(fā)、相關(guān)數(shù)據(jù)通路）Genericname:forwarding(bypass,short-circuiting)仔細觀察，發(fā)現(xiàn)有冒險指令需要的結(jié)果可能已經(jīng)計算出來，存放在流水線寄存器中可以在數(shù)據(jù)通路上增加數(shù)據(jù)線（buses）傳送這些結(jié)果這些

buses在數(shù)據(jù)通路中總是“pointbackwards”，從后面的流水段連接到前面的流水段71直通技術(shù)：減少數(shù)據(jù)冒險停頓數(shù)據(jù)可能已經(jīng)計算好—只是不在寄存器堆中EX/MEM.ALUoutputALUinputportMEM/WB.ALUoutputALUinputport

72Forwarding的硬件變化MEM/WRID/EXEX/MEMDataMemoryALUmuxmuxRegistersNextPCImmediatemuxEX/Mem.ALUoutputALUinputMEM/WB.ALUoutputALUinputMEM/WB.LMDALUinput73Forwarding的其他輸入路徑storeloadMEM/WB.LMDDMinput74Forwarding不能解決的問題75插入stall:

LoadstallTime(clockcycles)Instr.Orderlwr1,0(r2)subr4,r1,r6andr6,r1,r7RegALUDMemIfetchRegRegIfetchALUDMemRegBubbleIfetchALUDMemRegBubbleRegIfetchALUDMemBubbleRegorr8,r1,r976Forwarding的硬件變化MEM/WRID/EXEX/MEMDataMemoryALUmuxmuxRegistersNextPCImmediatemuxEX/Mem.ALUoutputALUinputMEM/WB.ALUoutputALUinputMEM/WB.LMDALUinput77Forwarding和

Load延遲例子Whyforwarding?ADDR4,R5,R2LWR15,0(R4)SWR15,4(R2)Whyloaddelay?ADDR4,R5,R2LWR15,0(R4)SWR15,4(R2)78解決方法：沒有forwarding79解決方法：forwarding80Forwarding的其他輸入路徑storeloadMEM/WB.LMDDMinput81loadstall的性能影響

例子假定程序中30%是load指令。有一半的時間，load指令其后的指令依賴load的結(jié)果。

如果冒險引起一個時鐘周期暫停，相比理想流水線有停頓的流水線性能會降低多少？

AnswerCPI=1+30%50%1=1.15由于load停頓，流水線性能降低

15%

。82不同測試程序中l(wèi)oad

產(chǎn)生stall的比例83編譯器重排序避免loadstall為以下表達式產(chǎn)生更快的代碼：

a=b+c; d=e–f;

假設(shè)

a,b,c,d,e,f存放在主存中。

慢的

code: LW Rb,b LW Rc,c ADD Ra,Rb,Rc SW a,Ra LW Re,e LW Rf,f SUB Rd,Re,Rf SW d,Rd快的

code: LW Rb,b LW Rc,c

LW Re,e ADD Ra,Rb,Rc LW Rf,f

SW a,Ra

SUB Rd,Re,Rf SW d,Rd84數(shù)據(jù)冒險總結(jié)TaxonomyofHazards

StructuralhazardsTheseareconflictsoverhardwareresources.

數(shù)據(jù)冒險幾條指令重疊執(zhí)行時，一條指令依賴前面指令的結(jié)果卻沒有準備好（還沒有計算或存儲）解決方法：寄存器堆WB先寫ID后讀，F(xiàn)orwarding通路，軟件調(diào)度，否則就必須停頓

Controlhazards

branchconditionandthebranchPCarenotavailableintimetofetchaninstructiononthenextclock8586A.2流水線的主要障礙—流水線冒險

一、冒險分類與有停頓流水線性能二、結(jié)構(gòu)冒險三、數(shù)據(jù)冒險四、控制冒險四、控制冒險控制冒險怎樣解決控制冒險87流水線冒險TaxonomyofHazards

Structuralhazards

Theseareconflictsoverhardwareresources.

OK,maybeaddextrahardwareresources;orfullpipelinedthefunctionalunits(splitdublebump);otherwisestillhavetostallDatahazardsInstructiondependsonresultofpriorcomputationwhichisnotready(computedorstored)yetOK,wedidthese,DoubleBump,Forwardingpath,softwarescheduling,otherwisehavetostall控制冒險Controlhazards

（流水線上執(zhí)行轉(zhuǎn)移指令時）進入下一個時鐘周期時，轉(zhuǎn)移條件和轉(zhuǎn)移目標PC不能按時提供給IF段取指令。88控制冒險原因進入下一個時鐘周期時，轉(zhuǎn)移條件和轉(zhuǎn)移目標PC不能按時提供給IF段取指令。計算目標PC要花時間對于條件轉(zhuǎn)移，轉(zhuǎn)移分析要花時間計算控制冒險（SPEC2000int條件轉(zhuǎn)移平均12%）引起MIPS流水線的性能損失

比數(shù)據(jù)冒險大得多。89例子：

Branches9024R0R0回憶：基本流水線通路91控制冒險2492處理控制冒險4種簡單解決方法（硬件）凍結(jié)或沖刷流水線預測轉(zhuǎn)移不發(fā)生Predict-not-taken(Predict-untaken)處理每條轉(zhuǎn)移指令都當作未發(fā)生轉(zhuǎn)移預測轉(zhuǎn)移發(fā)生Predict-taken處理每條轉(zhuǎn)移指令都當作轉(zhuǎn)移發(fā)生轉(zhuǎn)移延遲注意：以上任何一種方法都會使硬件固定編譯時會根據(jù)硬件機制和轉(zhuǎn)移行為對代碼順序進行調(diào)度，以獲取最佳性能93回憶：插入stalls解決冒險

48or72

2494流水線狀態(tài)BranchinstructionIFIDEXMEMWBBranchSuccessorIFstallstallidleidleBranchsuccessor+1IFIDEXBranchsuccessor+2IFIDBranchsuccessor+3IF95凍結(jié)或

沖刷流水線最簡單的硬件實現(xiàn):在轉(zhuǎn)移目標地址確定前，保持或者刪除轉(zhuǎn)移指令后進入流水線的指令。性能損失是固定的，不能通過軟件來減少。96轉(zhuǎn)移Stalls會造成大的性能損失Problem:程序中有30%的轉(zhuǎn)移頻率，理想CPI為1，插入stalls后的性能是多少？Answer:CPI=1+30%３＝1.9這種方法得到的性能大約只有理想性能的一半。97總是停頓——降低了轉(zhuǎn)移不發(fā)生的性能2498假設(shè)轉(zhuǎn)移不發(fā)生會怎樣？2499預測轉(zhuǎn)移未選中（Predict–not-taken）硬件實現(xiàn)：對每條轉(zhuǎn)移指令都當作轉(zhuǎn)移未選中處理

(orastheformalinstruction)當轉(zhuǎn)移未選中時，取到的指令正好是要繼續(xù)執(zhí)行的，沒有任何停頓。如果轉(zhuǎn)移選中，則重新取轉(zhuǎn)移目標指令，此時引起3個stall。(shouldturnthefetchedinstructionintoano-op)編譯器：編譯時，將使用頻率最高的代碼放在轉(zhuǎn)移未選中路徑上，改進性能。100如果轉(zhuǎn)移是發(fā)生的會怎樣？24101如果轉(zhuǎn)移是發(fā)生的會怎樣？24102另一種方法：假定轉(zhuǎn)移選中多數(shù)轉(zhuǎn)移（60%)是選中的，似乎本該用轉(zhuǎn)移選中更快。假定轉(zhuǎn)移總是選中會怎樣呢？103預測轉(zhuǎn)移選中（Predict–taken）硬件實現(xiàn)將所有轉(zhuǎn)移指令都當作轉(zhuǎn)移選中處理

(evidence:morethan60%brachesaretaken)只要轉(zhuǎn)移目標地址計算出來，就開始取目標指令。只有在目標地址計算比轉(zhuǎn)移條件更早產(chǎn)生才有用。對于經(jīng)典5段流水線（如前頁圖），是先得到轉(zhuǎn)移條件后得到轉(zhuǎn)移目標地址，因此轉(zhuǎn)移選中方法沒有任何益處。編譯器編譯時，將使用頻率最高的代碼放在轉(zhuǎn)移選中路徑上，改進性能。104轉(zhuǎn)移選中：轉(zhuǎn)移地址提前計算轉(zhuǎn)移時，目標地址提前到ID段計算，轉(zhuǎn)移條件判斷不變。105預測轉(zhuǎn)移選中的流水線狀態(tài)44BEQR1,24IFIDEXMEMWB48ANDR12,R2,R5IFidleidleidleidle72LWR4,50(R7)IFIDEXMEMWB76IFIDEXMEM80IFIDEXBranchisnot

taken:3stall44BEQR1,24IFIDEXMEMWB48ANDR12,R2,R5IFidleidleidleidle72LWR4,50(R7)IFIDidleidleidle76IFidleidleidle48ANDR12,R2,R5IFIDEXBranchistaken:1stall106轉(zhuǎn)移未選中/選中的問題流水線按照假定的轉(zhuǎn)移方向執(zhí)行通常，選擇方向是正確的，可以節(jié)省時鐘周期偶爾，選擇是錯誤的結(jié)論開始執(zhí)行選擇錯誤的指令要修復，則必須確認這些錯誤指令沒有真正執(zhí)行尤其是，必須保證錯誤指令沒有改變機器狀態(tài)107將轉(zhuǎn)移計算提前108將轉(zhuǎn)移計算提前更早storeload109提早后結(jié)果：MIPS改善后的數(shù)據(jù)通路在BEQ指令后，只需要1個額外周期就可以知道正確地址在MIPS，條件轉(zhuǎn)移指令其后的這個周期稱為轉(zhuǎn)移延遲槽

thebranchdelayslot48or72

24110沖刷

:只需插入onestall解決控制冒險

（硬件固定）48or72

40ADDR30,R30,R30IFIDEXMEMWB44BEQR1,24IFIDEXMEMWB48ANDR12,R2,R5IFidleidleidleidle48or72IFIDEXMEM111為什么“浪費”取到的指令？已經(jīng)取到48號地址指令，如果轉(zhuǎn)移最終沒有發(fā)生，有必要第2次取該指令嗎？48or72

112預測轉(zhuǎn)移未選中predict-not-taken（硬件固定）40ADDR30,R30,R30IFIDEXMEMWB44BEQR1,24IFIDEXMEMWB48ANDR12,R2,R5IFIDEXMEMWB52ORR13,R6,R2IFIDEXMEM轉(zhuǎn)移未選中：

Nostall轉(zhuǎn)移發(fā)生：

1stall40ADDR30,R30,R30IFIDEXMEMWB44BEQR1,24IFIDEXMEMWB48ANDR12,R2,R5IFidleidleidleidle72LWR4,50(R7)IFIDEXMEM76IFIDEX113轉(zhuǎn)移延遲（Delayedbranch）好的方面只需要1個周期計算出正確的轉(zhuǎn)移地址和條件因此，不需要2或3個周期的NOP或

NOPorstall不如意的方面總是有1cycle，總是要等待（如果沒有采用措施）在MIPS中，無論轉(zhuǎn)移是否發(fā)生，這個周期的指令總是要執(zhí)行

(hardwarescheme)114轉(zhuǎn)移延遲槽branchdelayslot轉(zhuǎn)移指令后的指令周期被用于轉(zhuǎn)移地址計算，MIPS中1個周期的延遲是必須的。因此，可以將延遲槽作為自由的指令周期加以利用。Consequence編譯器可以將合適的代碼調(diào)整到這個

“slot”中,如果只放入NOP

就浪費了。(compilerscheme)。115怎樣調(diào)度代碼？三種策略116例子：重寫代碼

(a)117例子：重寫代碼(b-1)Loop:LWR2,0(R1)ADDR3,R2,R4SWR3,0(R1)……SUBR1,R1,#4BNEZR1,Loop

LWR2,0(R1)Loop:ADDR3,R2,R4SWR3,0(R1)……

SUBR1,R1,#4

BNEZR1,Loop

LWR2,0(R1)118例子：重寫代碼(b-2)Loop:LWR2,0(R1)ADDR3,R2,R4

SWR3,0(R1)DIV…..……SUBR1,R1,#4BNEZR1,LoopLoop:LWR2,0(R1)ADDR3,R2,R4DIV…...…...SUBR1,R1,#4BNEZR1,Loop

SWR3,+4(R1)119調(diào)度策略對比性能改善轉(zhuǎn)移延遲的限制對于調(diào)度到延遲槽的指令有限制。編譯器能準確預測轉(zhuǎn)移是否發(fā)生，以決定實際做多少有用的工作。對于調(diào)度策略

b和c：如果預測是錯誤的，必須保證執(zhí)行SUB/OR指令是正確的?；蛘?，硬件必須提供一種方法能夠撤銷SUB/OR指令。121撤銷功能考慮轉(zhuǎn)移預測的方向。如果轉(zhuǎn)移預測是錯誤的，CPU能夠?qū)⑥D(zhuǎn)移延遲槽中的指令轉(zhuǎn)換為一條空操作指令。（硬件支持）能夠減少編譯器選擇有用指令進