計算機體系結(jié)構(gòu)

1、計算機體系結(jié)構(gòu)Topic III: Pipelining流水線的基本概念一個任務(wù)可以分解為k 個子任務(wù)K個子任務(wù)在 K 個不同階段（使用不同的資源）運行每個子任務(wù)執(zhí)行需要1個單位時間整個任務(wù)的執(zhí)行時間為 K倍單位時間流水線執(zhí)行模式是重疊執(zhí)行模式K個流水段并行執(zhí)行K個不同任務(wù)每個單位時間進(jìn)入/離開流水線一個任務(wù)chapter03.29/8/2022同步流水線流水段之間采用時鐘控制的寄存器文件（clocked registers)時鐘上升沿到達(dá)時所有寄存器同時保存前一流水段的結(jié)果流水段是組合邏輯電路流水線設(shè)計中希望各段相對平衡即所有段的延遲時間大致相等時鐘周期取決于延遲最長的流水段9/8/2022

2、chapter03.3流水線的性能設(shè) = time delay in stage Si時鐘周期 = max( ) 為最長的流水段延遲時鐘頻率 f = 1/ = 1/max( )流水線可以在k+n-1個時鐘周期內(nèi)完成n個任務(wù) 完成第一個任務(wù)需要 k個時鐘周期其他n-1個任務(wù)需要n-1個時鐘周期完成K-段流水線的理想加速比（相對于串行執(zhí)行）chapter03.49/8/2022典型的RISC5段流水線5個流水段，每段的延遲為1個cycleIF: 取值階段選擇地址：下一條指令地址、轉(zhuǎn)移地址ID: 譯碼階段確定控制信號 并從寄存器文件中讀取寄存器值EX: 執(zhí)行Load 、Store：計算有效地址Bra

3、nch：計算轉(zhuǎn)移地址并確定轉(zhuǎn)移方向MEM: 存儲器訪問（僅Load和Store)WB: 結(jié)果寫回chapter03.59/8/2022典型的 RISC 5段流水線6MemoryEXecuteDecodeFetchRegistersALUBAData CachePCInstruction CacheStoreImmInst. RegisterWritebackThis version designed for regfiles/memories with synchronous reads and writes.流水線的可視化表示多條指令執(zhí)行多個時鐘周期指令按程序序從上到下排列圖中展示了每一時鐘

4、周期資源的使用情況不同指令相鄰階段之間沒有干擾chapter03.79/8/2022Recap：流水線技術(shù)要點流水線技術(shù)要點多個任務(wù)重疊（并發(fā)/并行）執(zhí)行，但使用不同的資源流水線技術(shù)提高整個系統(tǒng)的吞吐率，不能縮短單個任務(wù)的執(zhí)行時間其潛在的加速比流水線的級數(shù)影響流水線性能的因素流水線中的瓶頸最慢的那一段流水段所需時間不均衡將降低加速比流水線存在裝入時間和排空時間，使得加速比降低由于存在相關(guān)(hazards)問題，會導(dǎo)致流水線停頓Hazards 問題：流水線的執(zhí)行可能會導(dǎo)致對資源的訪問沖突，或破壞對資源的訪問順序流水線正常工作的基本條件增加寄存器文件保存當(dāng)前段傳送到下一段的數(shù)據(jù)和控制信息需要更高的

5、存儲器帶寬9/8/2022chapter3.8指令流時序時序圖展示：每個時鐘周期指令所使用的流水段情況指令流在采用5段流水線執(zhí)行模式的執(zhí)行情況9/8/2022chapter03.9單周期、多周期、流水線控制性能比較9/8/2022chapter03.10假設(shè)5段指令執(zhí)行流水線某一程序段假設(shè)：20% load, 10% store, 40% ALU, and 30% branch比較三種執(zhí)行模式的性能流水線的相關(guān)（Hazards)結(jié)構(gòu)相關(guān)：流水線中一條指令可能需要另一條指令使用的硬件資源數(shù)據(jù)和控制相關(guān)：一條指令可能依賴于先前的指令生成的內(nèi)容數(shù)據(jù)相關(guān)：依賴先前指令產(chǎn)生的結(jié)果（數(shù)據(jù)）值控制相關(guān)：依賴

6、關(guān)系是如何確定下一條指令地址 (branches, exceptions)處理相關(guān)的一般方法是插入bubble，導(dǎo)致CPI1 (單發(fā)射理想CPI）11Pipeline CPI Examples12Time3 instructions finish in 3 cyclesCPI = 3/3 =1Inst 1Inst 2Inst 33 instructions finish in 4 cyclesCPI = 4/3 = 1.33Inst 1Inst 2Inst 3BubbleMeasure from when first instruction finishes to when last inst

7、ruction in sequence finishes.3 instructions finish in 5cyclesCPI = 5/3 = 1.67Inst 1Inst 2Inst 3Bubble 1Bubble 2Inst 3消減結(jié)構(gòu)相關(guān)當(dāng)兩條指令同時需要相同的硬件資源時，就會發(fā)生結(jié)構(gòu)相關(guān)（沖突）方法1：通過將新指令延遲到前一條指令執(zhí)行完（釋放資源后）執(zhí)行方法2：增加新的資源E.g., 如果兩條指令同時需要操作存儲器，可以通過增加到兩個存儲器操作端口來避免結(jié)構(gòu)沖突經(jīng)典的 RISC 5-段整型數(shù)流水線通過設(shè)計可以沒有結(jié)構(gòu)相關(guān)很多RISC實現(xiàn)在多周期操作時存在結(jié)構(gòu)相關(guān)例如多周期操作的mul

8、tipliers, dividers, floating-point units等，由于沒有多個寄存器文件寫端口 導(dǎo)致 結(jié)構(gòu)沖突13三種基本的數(shù)據(jù)相關(guān) 寫后讀相關(guān)(Read After Write (RAW) 由于實際的數(shù)據(jù)交換需求而引起的讀后寫相關(guān)（Write After Read (WAR) 編譯器編寫者稱之為“anti-dependence”（反相關(guān)），是由于重復(fù)使用寄存器名“x1”引起的.寫后寫相關(guān)（Write After Write (WAW)） 編譯器編寫者稱之為“output dependence” ，也是由于重復(fù)使用寄存器名 “x1”引起的.在后面的復(fù)雜的流水線中我們將會看到

9、WAR 和WAW 相關(guān)9/8/2022chapter3.14消減數(shù)據(jù)相關(guān)的三種策略連鎖機制（Interlock）在issue階段保持當(dāng)前相關(guān)指令，等待相關(guān)解除設(shè)置旁路定向路徑（Bypass or Forwarding)只要結(jié)果可用，通過旁路盡快傳遞數(shù)據(jù)投機（Speculate）猜測一個值繼續(xù)，如果猜測錯了再更正15Interlocking Versus Bypassing16add x1, x3, x5sub x2, x1, x4Fadd x1, x3, x5DFXDFsub x2, x1, x4WMXbubbleFDWXMWMWWMDXbubbleMXbubbleDFInstruction

10、interlocked in decode stageFDXMWadd x1, x3, x5FDXMWsub x2, x1, x4Bypass around ALU with no bubblesMemoryEXecuteDecodeFetchExample Bypass Path17RegistersALUBAData CachePCInstruction CacheStoreImmInst. RegisterWritebackMemoryEXecuteDecodeFetchFully Bypassed Data Path18RegistersALUBAData CachePCInstruc

11、tion CacheStoreImmInst. RegisterWritebackFDXMWFDXMWFDXMWFDXMW Assumes data written to registers in a W cycle is readable in parallel D cycle (dotted line). Extra write data register and bypass paths required if this is not possible. lw $t0, 4($t1)addi $t1, $t1addi $t0, $t0, 1針對數(shù)據(jù)相關(guān)的值猜測執(zhí)行不等待產(chǎn)生結(jié)果的指令產(chǎn)生

12、值，直接猜測一個值繼續(xù)這種技術(shù)，僅在某些情況下可以使用:分支預(yù)測堆棧指針更新存儲器地址消除歧義（Memory address disambiguation）19采用軟件方法避免數(shù)據(jù)相關(guān)9/8/2022chapter3.20Fast code:LW Rb,bLW Rc,cLW Re,e ADD Ra,Rb,RcLW Rf,fSW a,Ra SUB Rd,Re,RfSWd,RdTry producing fast code fora = b + c;d = e f;assuming a, b, c, d ,e, and f in memory. Slow code:LW Rb,bLW Rc,cAD

13、D Ra,Rb,RcSW a,Ra LW Re,e LW Rf,fSUB Rd,Re,RfSWd,Rd流水線的可視化表示多條指令執(zhí)行多個時鐘周期指令按程序序從上到下排列圖中展示了每一時鐘周期資源的使用情況不同指令相鄰階段之間沒有干擾chapter03.219/8/2022流水線的相關(guān)（Hazards)結(jié)構(gòu)相關(guān)：流水線中一條指令可能需要另一條指令使用的資源數(shù)據(jù)和控制相關(guān)：一條指令可能依賴于先前的指令生成的內(nèi)容數(shù)據(jù)相關(guān)：依賴先前指令產(chǎn)生的結(jié)果（數(shù)據(jù)）值控制相關(guān)：依賴關(guān)系是如何確定下一條指令地址 (branches, exceptions)處理相關(guān)的一般方法是插入bubble，導(dǎo)致CPI1 (單發(fā)射

14、理想CPI）22Control Hazards如何計算下一條指令地址（next PC）無條件直接轉(zhuǎn)移 Opcode, PC, and offset基于基址寄存器的無條件轉(zhuǎn)移Opcode, Register value, and offset條件轉(zhuǎn)移Opcode, Register (for condition), PC and offset其他指令Opcode and PC ( and have to know its not one of above )23MemoryEXecuteDecodeFetchControl flow information in pipeline24Regist

15、ersBAData CachePCInstruction CacheStoreImmInst. RegisterWritebackPC knownOpcode, offset knownBranch condition, Jump register value knownALUEXecuteDecodeFetchRISC-V Unconditional PC-Relative Jumps25RegistersBAInstruction CacheImmInst. RegisterALUPC_decodeAddJump?PCJumpSelPC_fetchKillFKill+4 Kill bit

16、turns instruction into a bubble Pipelining for Unconditional PC-Relative Jumps26MWXMWDXMWj target ;等同于 jal x0,offset ; pc +=sext(offset)FDFtarget: add x1, x2, x3XDFbubbleBranch Delay Slots早期的RISC機器的延遲槽技術(shù)改變ISA語義，在分支/跳轉(zhuǎn)后的延遲槽中指令總是在控制流發(fā)生變化之前執(zhí)行:0 x100 j target0 x104 add x1, x2, x3 / Executed before targe

17、t0 x205 target: xori x1, x1, 7軟件必須用有用的工作填充延遲槽（delay slots），或者用顯式的NOP指令填充延遲槽27MWXMWDXMWj targetFDFtarget: xori x1, x1, 7XDFadd x1, x2, x3Post-1990 RISC ISAs 取消了延遲槽性能問題當(dāng)延遲槽中填充了NOPs指令后，增加了I-cache的失效率即使延遲槽中只有一個NOP，I-cache失效導(dǎo)致機器等待使先進(jìn)的微體系架構(gòu)復(fù)雜化例如4發(fā)射30段流水線好的分支預(yù)測技術(shù)減少了采用延遲槽技術(shù)的動力28EXecuteDecodeFetchRISC-V Cond

18、itional Branches29RegistersBAInstruction CacheInst.Inst. RegisterALUPC_decodeAddBranch?PCSelPC_fetchKillFKill+4Cond?PC_executeAddKillDKillPipelining for Conditional Branches30MWXMWDXMWbeq x1, x2, targetFDFtarget: add x1, x2, x3XDFbubblebubbleFDXMWPipelining for Jump RegisterTarget address obtained i

19、n execute stage31MWXMWDXMWjr x1 (等同于 jalr x0,0(x1); pc=0(x1)FDFtarget: add x5, x6, x7XDFbubblebubbleFDXMW為什么在經(jīng)典的五段流水線中指令不能在每個周期都被分發(fā)(CPI1)采用全定向路徑可能代價太高而無法實現(xiàn)通常提供經(jīng)常使用的定向路徑一些不經(jīng)常使用的定向路徑可能會增加時鐘周期的長度，從而抵消降低CPI的好處 Load操作有兩個時鐘周期的延遲Load指令后的指令不能馬上使用Load的結(jié)果MIPS-I ISA 定義了延遲槽, 軟件可見的流水線沖突 (由編譯器調(diào)度無關(guān)的指令或插入NOP指令避免沖突）

20、，MIPS-II中取消了延遲槽語義（硬件上增加流水線interlocks機制)MIPS:“Microprocessor without Interlocked Pipeline Stages” Jumps/Conditional branches 可能會導(dǎo)致流水線斷流（bubbles)如果沒有延遲槽，則stall后續(xù)的指令32帶有軟件可見的延遲槽有可能需要執(zhí)行大量的由編譯器插入的NOP指令NOP指令降低了CPI，但是增加了程序中執(zhí)行的指令條數(shù)陷阱和中斷 術(shù)語說明異常（Exception）:由程序執(zhí)行過程中引起的異常內(nèi)部事件E.g., page fault, arithmetic underfl

21、ow陷阱（Trap）:因異常情況而被迫將控制權(quán)移交給監(jiān)控程序Not all exceptions cause traps (c.f. IEEE 754 floating-point standard)中斷（Interrupt）:運行程序之外的外部事件，導(dǎo)致控制權(quán)轉(zhuǎn)移到監(jiān)控程序陷阱和中斷通常由同樣的流水線機制處理33異常處理的發(fā)展歷史第一個帶有陷阱（traps）的系統(tǒng)是Univac-I （1951年）算術(shù)運算溢出有兩種選擇1.在地址0處觸發(fā)一個兩條指令的修復(fù)例程的執(zhí)行 或者2.根據(jù)程序員的選擇，使計算機停止 在后來的Univac 1103, 1955, 增加了外部中斷機制用于實時采集風(fēng)洞數(shù)據(jù)第一

22、個帶有I/O 中斷的系統(tǒng)是DYSEAC（1954）帶有兩個程序計數(shù)器，并且I/O信號引起這兩個PC間的切換它也是第一個帶有DMA (direct memory access by I/O device)的系統(tǒng)同時，也是第一臺移動計算機 (兩臺半掛牽引車, 12 tons + 8 tons)34DYSEAC, first mobile computer!35Carried in two tractor trailers, 12 tons + 8 tonsBuilt for US Army Signal CorpsCourtesy Mark Smotherman異步中斷I/O設(shè)備通過發(fā)出中斷請求信

23、號來請求處理當(dāng)處理器決定響應(yīng)該中斷時停止當(dāng)前指令(Ii)的執(zhí)行 , 執(zhí)行完當(dāng)前指令前面的指令（執(zhí)行完 Ii-1） (精確中斷）將li指令的PC值保存到專門寄存器(EPC)中關(guān)中斷并將控制轉(zhuǎn)移到以監(jiān)控模式運行的指定的中斷處理程序36Interrupts: 改變正常的控制流37Ii-1HI1HI2HInIiIi+1programinterrupt handler需要由另一個（系統(tǒng)）程序處理的外部或內(nèi)部事件。從程序的角度來看，事件通常是意外的或罕見的。Interrupt Handler允許嵌套中斷時，在開中斷之前需要保存EPC 需要執(zhí)行指令將EPC 存入 GPRs 至少在保存EPC之前，需要一種方法

24、來暫時屏蔽進(jìn)一步的中斷需要讀取記錄中斷原因的狀態(tài)寄存器使用專門的間接跳轉(zhuǎn)指令ERET (return-from-environment) 返回開中斷將處理器恢復(fù)到用戶模式恢復(fù)硬件狀態(tài)和控制狀態(tài)38Synchronous Trap同步陷阱是由特定指令執(zhí)行的異常引起的通常，該指令無法完成，需要在處理異常之后重新啟動需要撤消一個或多個部分執(zhí)行的指令的效果在系統(tǒng)調(diào)用(陷阱)的情況下，該指令被認(rèn)為已經(jīng)完成一種特殊的跳轉(zhuǎn)指令，涉及到切換到特權(quán)模式的操作39Exception Handling 5-Stage Pipeline40如何處理不同流水段的多個并發(fā)異常?如何以及在哪里處理外部異步中斷?PCInst

25、. MemDDecodeEMData MemW+Illegal OpcodeOverflowData address ExceptionsPC address ExceptionAsynchronous InterruptsException Handling 5-Stage Pipeline41PCInst. MemDDecodeEMData MemW+Illegal OpcodeOverflowData address ExceptionsPC address ExceptionAsynchronousInterruptsExcDPCDExcEPCEExcMPCMCauseEPCKill

26、D StageKill F StageKill E StageSelect Handler PCKill WritebackCommit PointException Handling 5-Stage Pipeline在流水線中將異常標(biāo)志保留到提交階段針對某一給定的指令，早期流水階段中的異常覆蓋該指令的后續(xù)異常在提交階段并入異步中斷請求 (覆蓋其他中斷)如果提交時檢測到異常: 更新異常原因及EPC寄存器 終止所有流水段,將異常處理程序的地址送入PC寄存器，以跳轉(zhuǎn)到處理程序中執(zhí)行42異常的推測預(yù)測機制異?？偸潜容^少的，所以簡單地預(yù)測為沒有異常 通常是大概率事件檢查預(yù)測機制在指令執(zhí)行的最后階段進(jìn)行

27、異常檢測采用專門的硬件用于檢測各種類型的異?；謴?fù)執(zhí)行機制僅在提交階段改變機器狀態(tài)，因此可以在發(fā)生異常后丟棄部分執(zhí)行的指令刷新流水線后啟動異常處理程序定向路徑機制允許后續(xù)的指令使用沒有提交的指令結(jié)果43流水線的性能分析基本度量參數(shù)：吞吐率，加速比，效率吞吐率：在單位時間內(nèi)流水線所完成的任務(wù)數(shù)量或輸出結(jié)果的數(shù)量。9/8/2022chapter03.44n：任務(wù)數(shù)Tk：處理完成n個任務(wù)所用的時間流水線技術(shù)提高系統(tǒng)的任務(wù)吞吐率1. 各段時間均相等的流水線各段時間均相等的流水線時空圖9/8/2022chapter03.45吞吐率流水線完成n個連續(xù)任務(wù)所需要的總時間（假設(shè)一條k段線性流水線） Tkkt(n

28、-1)t(kn-1)t 流水線的實際吞吐率最大吞吐率: 流水線在連續(xù)流動達(dá)到穩(wěn)定狀態(tài)后所得到的吞吐率。9/8/202246S412345.n-1nS312345.n-1nS212345.n-1nS112345.n-1nTP與TPmax的關(guān)系最大吞吐率與實際吞吐率的關(guān)系流水線的實際吞吐率小于最大吞吐率，它除了與每個段的時間有關(guān)外，還與流水線的段數(shù)k以及輸入到流水線中的任務(wù)數(shù)n有關(guān)。只有當(dāng)nk時，才有TPTPmax。 9/8/2022chapter03.47流水線中的瓶頸最慢的段2. 各段時間不完全相等的流水線 各段時間不等的流水線及其時空圖一條4段的流水線S1，S3，S4各段的時間：tS2的時間

29、：3t （瓶頸段）流水線中這種時間最長的段稱為流水線的瓶頸段9/8/2022chapter03.48各段時間不等的流水線的實際吞吐率：（ ti為第i段的時間，共有k個段 ）流水線的最大吞吐率為9/8/202249 例如：一條4段的流水線中，S1，S2，S4各段的時間都是t，唯有S3的時間是3t 9/8/202250最大吞吐率為解決流水線瓶頸問題的常用方法 細(xì)分瓶頸段 例如：對前面的4段流水線把瓶頸段S3細(xì)分為3個子流水線段：S3a，S3b，S3c改進(jìn)后的流水線的吞吐率 ：519/8/2022重復(fù)設(shè)置瓶頸段缺點：控制邏輯比較復(fù)雜，所需的硬件增加了。例如：對前面的4段流水線 重復(fù)設(shè)置瓶頸段S3：S

30、3a，S3b，S3c9/8/2022chapter03.52重復(fù)設(shè)置瓶頸段后的時空圖chapter03.539/8/2022加速比加速比：完成同樣一批任務(wù)，不使用流水線所用的時間與使用流水線所用的時間之比假設(shè)：不使用流水線（即順序執(zhí)行）所用的間為Ts，使用流水線后所用的時間為Tk，則該流水線的加速比為9/8/2022chapter03.541. 流水線各段時間相等（都是t）k段流水線完成n個連續(xù)任務(wù)所需要的時間為 Tk = (kn-1)t順序執(zhí)行n個任務(wù)所需要的時間 Ts= nkt 流水線的實際加速比為最大加速比當(dāng)nk時，S k9/8/2022chapter03.55思考：流水線的段數(shù)愈多愈好

31、？ 流水線的各段時間不完全相等時一條k段流水線完成n個連續(xù)任務(wù)的實際加速比為9/8/2022chapter03.56效率效率：流水線中的設(shè)備實際使用時間與整個運行時間的比值，即流水線設(shè)備的利用率 utilization。由于流水線有通過時間和排空時間，所以在連續(xù)完成n個任務(wù)的時間內(nèi)，各段并不是滿負(fù)荷地工作。各段時間相等各段的效率ei相同 9/8/2022chapter03.57整條流水線的效率為9/8/202258可以寫成 最高效率為 當(dāng)nk時，E1。 當(dāng)流水線各段時間相等時，流水線的效率與吞吐率成正比。 E=TPt 流水線的效率是流水線的實際加速比S與它的最大加速比k的比值。 9/8/202

32、2chapter03.59當(dāng)E=1時，S=k，實際加速比達(dá)到最大。從時空圖上看，效率就是n個任務(wù)占用的時空面積和k個段總的時空面積之比。9/8/202260當(dāng)各段時間不相等時Summary實際吞吐率：假設(shè)k段，完成n個任務(wù)，單位時間所實際完成的任務(wù)數(shù)。加速比: k段流水線的速度與等功能的非流水線的速度之比。效率：流水線的設(shè)備利用率。9/8/2022chapter3.61-Review: Pipelining指令流水線通過指令重疊減小 CPI充分利用數(shù)據(jù)通路當(dāng)前指令執(zhí)行時，啟動下一條指令其性能受限于花費時間最長的段檢測和消除相關(guān)如何有利于流水線技術(shù)的應(yīng)用所有的指令都等長只有很少的指令格式只用Lo

33、ad/Store來進(jìn)行存儲器訪問9/8/2022chapter3.62流水線的加速比計算 9/8/2022chapter3.63For simple RISC pipeline, CPI = 1:結(jié)構(gòu)相關(guān)對性能的影響例如: 如果每條指令平均訪存1.3 次，而每個時鐘周期只能訪存一次，那么在其他資源100利用的前提下，平均 CPI 1.39/8/2022chapter3.64例如： Dual-port vs. Single-port機器A: Dual ported memory (“Harvard Architecture”)機器B: Single ported memory存在結(jié)構(gòu)相關(guān)的機器B

34、的時鐘頻率是機器A的時鐘頻率的1.05倍Ideal CPI = 1 在機器B中l(wèi)oad指令會引起結(jié)構(gòu)相關(guān)，所執(zhí)行的指令中Loads指令占 40% Average instruction time = CPI * Clock cycle time 無結(jié)構(gòu)相關(guān)的機器A： Average Instruction time = Clock cycle time 存在結(jié)構(gòu)相關(guān)的機器B： Average Instruction time = (1+0.4*1) * clock cycle time /1.05 = 1.3 * clock cycle time9/8/2022chapter3.65解決控制相關(guān)的方法#1: Stall 直到分支方向確定#2: 預(yù)測分支失敗直接執(zhí)行后繼指令如果分支實際情況為分支成功