1

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

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

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

流水線的基本概念A(yù).2

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

CPI=5,

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

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

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

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

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

做“=0？”測試，如果條件滿足計(jì)算目標(biāo)地址送PCMEM:MemoryaccessLoad:

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

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

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

19多周期實(shí)現(xiàn)

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

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

；if

r1=r0，

（NPC）

+24-

>

PC

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

CPI=1,longclockcycle

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

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

4.78.

這種實(shí)現(xiàn)是沒有優(yōu)化的.4×（12％＋10％）＋5×78%＝4.7825怎樣改進(jìn)多周期實(shí)現(xiàn)的性能？對(duì)于branch,將“=0？”測試和計(jì)算可能的轉(zhuǎn)移目標(biāo)地址提前到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)化的多周期實(shí)現(xiàn)Temporarystoragelocations27改進(jìn)硬件冗余ALU可以共享

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

CPI減少到1，因?yàn)槠骄總€(gè)時(shí)鐘周期發(fā)射或完成一條指令。在任意時(shí)鐘周期，在每個(gè)流水段正執(zhí)行一條指令的部分。

Ideally,performanceisincreasedfivefold!

29storeload5-段流水線

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

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

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

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

CPI=1,longclockcycle

ClkLoadStoreWasteCycle1Cycle2PipelineImplementation:

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

CPI=5,

PipelineImplementation:

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

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

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

(數(shù)據(jù)冒險(xiǎn)

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

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

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

通過流水線寄存器，不同段能夠一個(gè)接一個(gè)形成流水線流水線寄存器數(shù)目比多周期實(shí)現(xiàn)機(jī)器多得多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任何后面段需要的值必須放在流水線寄存器中，而且會(huì)復(fù)制到其后的寄存器中直到不需要為止。41storeload流水線模型pipelineregistersorlatches

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

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

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

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

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

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

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

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

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

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

由編譯器插入

nop

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

(maylessthanorgreaterthat)

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

51

因此：Clockcycleunpipelined=Clockcyclepipelining有：

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

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

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

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

：

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

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

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

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

減少部件延遲

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

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

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

結(jié)構(gòu)冒險(xiǎn)

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

或者功能部件完全流水

；

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

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

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

由編譯器插入

nop

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

增加硬件互鎖（Interlock）

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

插入

stallsBubbleBubbleEmptyslotsinthepipecalledbubbles;meansnorealinstructionworkgettingsavedhere70Forwarding

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

buses在數(shù)據(jù)通路中總是“pointbackwards”，從后面的流水段連接到前面的流水段71直通技術(shù)：減少數(shù)據(jù)冒險(xiǎn)停頓數(shù)據(jù)可能已經(jīng)計(jì)算好—只是不在寄存器堆中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指令。有一半的時(shí)間，load指令其后的指令依賴load的結(jié)果。

如果冒險(xiǎn)引起一個(gè)時(shí)鐘周期暫停，相比理想流水線有停頓的流水線性能會(huì)降低多少？

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

15%

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

產(chǎn)生stall的比例83編譯器重排序避免loadstall為以下表達(dá)式產(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ù)冒險(xiǎn)總結(jié)TaxonomyofHazards

StructuralhazardsTheseareconflictsoverhardwareresources.

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

Controlhazards

branchconditionandthebranchPCarenotavailableintimetofetchaninstructiononthenextclock8586A.2流水線的主要障礙—流水線冒險(xiǎn)

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

Structuralhazards

Theseareconflictsoverhardwareresources.

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

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

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

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

48or72

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

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

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

(evidence:morethan60%brachesaretaken)只要轉(zhuǎn)移目標(biāo)地址計(jì)算出來，就開始取目標(biāo)指令。只有在目標(biāo)地址計(jì)算比轉(zhuǎn)移條件更早產(chǎn)生才有用。對(duì)于經(jīng)典5段流水線（如前頁圖），是先得到轉(zhuǎn)移條件后得到轉(zhuǎn)移目標(biāo)地址，因此轉(zhuǎn)移選中方法沒有任何益處。編譯器編譯時(shí)，將使用頻率最高的代碼放在轉(zhuǎn)移選中路徑上，改進(jìn)性能。104轉(zhuǎn)移選中：轉(zhuǎn)移地址提前計(jì)算轉(zhuǎn)移時(shí)，目標(biāo)地址提前到ID段計(jì)算，轉(zhuǎn)移條件判斷不變。105預(yù)測轉(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é)省時(shí)鐘周期偶爾，選擇是錯(cuò)誤的結(jié)論開始執(zhí)行選擇錯(cuò)誤的指令要修復(fù)，則必須確認(rèn)這些錯(cuò)誤指令沒有真正執(zhí)行尤其是，必須保證錯(cuò)誤指令沒有改變機(jī)器狀態(tài)107將轉(zhuǎn)移計(jì)算提前108將轉(zhuǎn)移計(jì)算提前更早storeload109提早后結(jié)果：MIPS改善后的數(shù)據(jù)通路在BEQ指令后，只需要1個(gè)額外周期就可以知道正確地址在MIPS，條件轉(zhuǎn)移指令其后的這個(gè)周期稱為轉(zhuǎn)移延遲槽

thebranchdelayslot48or72

24110沖刷

:只需插入onestall解決控制冒險(xiǎn)

（硬件固定）48or72

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

112預(yù)測轉(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個(gè)周期計(jì)算出正確的轉(zhuǎn)移地址和條件因此，不需要2或3個(gè)周期的NOP或

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

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

“slot”中,如果只放入NOP

就浪費(fèi)了。(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)度策略對(duì)比性能改善轉(zhuǎn)移延遲的限制對(duì)于調(diào)度到延遲槽的指令有限制。編譯器能準(zhǔn)確預(yù)測轉(zhuǎn)移是否發(fā)生，以決定實(shí)際做多少有用的工作。對(duì)于調(diào)度策略

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