【正文】 (WAW)） InstrJ writes operand before InstrI writes it. ? 編譯器編寫者稱之為 ―output dependence‖ ， 也是由于重復(fù)使用寄存器名 ―r1‖引起的 . ? 在 DLX(MIPS) 5段基本流水線中，也不會發(fā)生。 中國科學(xué)技術(shù)大學(xué) ktTPEtntktnEtnttnStntnTPtTPkiikijikijkijikiikijii?????????????????????????????????????111111ma x])1([)1()1(}m a x {1中國科學(xué)技術(shù)大學(xué) Review: Pipelining ? 指令流水線通過指令重疊減小 CPI ? 充分利用數(shù)據(jù)通路 –當前指令執(zhí)行時，啟動下一條指令 –其性能受限于花費時間最長的段 –檢測和消除相關(guān) ? 如何有利于流水線技術(shù)的應(yīng)用 –所有的指令都等長 –只有很少的指令格式 –只用 Load/Store來進行存儲器訪問 中國科學(xué)技術(shù)大學(xué) Review：流水線性能分析 流水線技術(shù)應(yīng)用的難度何在 ? ：相關(guān)問題 吞吐率、加速比、效率之間的關(guān)系 ktTPEtntktnEtnttnStntnTPtTPkiikijikijkijikiikijii?????????????????????????????????????111111ma x])1([)1()1(}m a x {1中國科學(xué)技術(shù)大學(xué) ? 指令流水線： CPU執(zhí)行大量的指令，指令吞吐率非常重要 ? MIPS 的指令格式 MIPS的基本流水線 Op 0 5 31 16 15 11 10 6 rs rt immediate Op 0 5 31 Op 0 5 31 16 15 11 10 6 rs rtoffset added to PC rd RegisterRegister (Rtype) ADD R1, R2, R3 26 25 21 20 RegisterImmediate (Itype) SUB R1, R2, 3 Jump / Call (Jtype) JUMP end func (jump, jump and link, trap and return from exception) ?所有指令相同長度 ?在指令格式中寄存器位于同一位置 ?只有 Loads和 Stores可以對存儲器操作 6 中國科學(xué)技術(shù)大學(xué) MIPS數(shù)據(jù)通路 中國科學(xué)技術(shù)大學(xué) 中國科學(xué)技術(shù)大學(xué) MIPS數(shù)據(jù)通路 中國科學(xué)技術(shù)大學(xué) 改進后流水線的分支操作 中國科學(xué)技術(shù)大學(xué) 流水線的相關(guān) ?相關(guān)的基本概念 ?結(jié)構(gòu)相關(guān) ?數(shù)據(jù)相關(guān) ?控制相關(guān) 中國科學(xué)技術(shù)大學(xué) 采用流水線技術(shù)帶來的新問題 ? 流水線相關(guān) – 結(jié)構(gòu)相關(guān)：同一時間兩種方式使用同一資源 187。 中國科學(xué)技術(shù)大學(xué) 從時空圖上看，效率就是 n個任務(wù)占用的時空面積和 k個段總的時空面積之比。 ? 各段時間相等 – 各段的效率 ei相同 121 ????????nknTtneeekk?中國科學(xué)技術(shù)大學(xué) – 整條流水線的效率為 kkkTtknkkekeeeE ??????? 121 ?1??? nknE11l i mm a x ???? ?? nk nE n? 可以寫成 ? 最高效率為 當 nk時， E≈1 。缺點： 控制邏輯比較復(fù)雜，所需的硬件增加了。S1， S3， S4各段的時間： Δ t 187。 吞吐率 S4 1 2 3 4 5 .. .. .. n1 n S3 1 2 3 4 5 .. .. .. n1 n S2 1 2 3 4 5 .. .. .. n1 n S1 1 2 3 4 5 .. .. .. n1 n 中國科學(xué)技術(shù)大學(xué) 13 – 最大吞吐率與實際吞吐率的關(guān)系 m a x1 TPnknTP???? 流水線的實際吞吐率小于最大吞吐率，它除了與每個段的時間有關(guān)外，還與流水線的段數(shù) k以及輸入到流水線中的任務(wù)數(shù) n等有關(guān)。中國科學(xué)技術(shù)大學(xué) 1 計算機體系結(jié)構(gòu) 周學(xué)海 055163601556, 63492149 中國科學(xué)技術(shù)大學(xué) 第三章 流水線技術(shù) MIPS基本流水線 DLX (MIPS)中多周期操作的處理 MIPS R4000流水線 中國科學(xué)技術(shù)大學(xué) 流水線的基本概念 ? 一個任務(wù)可以分解為 k 個子任務(wù) – K個子任務(wù)在 K 個不同階段（使用不同的資源）運行 – 每個子任務(wù)執(zhí)行需要 1個單位時間 – 整個任務(wù)的執(zhí)行時間為 K倍單位時間 ? 流水線執(zhí)行模式是重疊執(zhí)行模式 – K個流水段并行執(zhí)行 K個不同任務(wù) – 每個單位時間進入 /離開流水線一個任務(wù) 中國科學(xué)技術(shù)大學(xué) 同步流水線 ? 流水段之間采用時鐘控制的寄存器文件（ clocked registers) ? 時鐘上升沿到達時 … – 所有寄存器同時保存前一流水段的結(jié)果 ? 流水段是組合邏輯電路 ? 流水線設(shè)計中希望各段相對平衡 – 即所有段的延遲時間大致相等 ? 時鐘周期取決于延遲最長的流水段 中國科學(xué)技術(shù)大學(xué) 流水線的性能 ? 設(shè) = time delay in stage Si ? 時鐘周期 = max( ) 為最長的流水段延遲 ? 時鐘頻率 f = 1/ = 1/max( ) ? 流水線可以在 k+n1個時鐘周期內(nèi)完成 n個任務(wù) – 完成第一個任務(wù)需要 k個時鐘周期 – 其他 n1個任務(wù)需要 n1個時鐘周期完成 ? K段流水線的理想加速比（相對于串行執(zhí)行） 中國科學(xué)技術(shù)大學(xué) 簡單的 5段流水線 ? 5個流水段，每段的延遲為 1個 cycle ? IF: 取值階段 – 選擇地址：下一條指令地址、轉(zhuǎn)移地址 ? ID: 譯碼階段 – 確定控制信號 并從寄存器文件中讀取寄存器值 ? EX: 執(zhí)行 – Load 、 Store：計算有效地址 – Branch：計算轉(zhuǎn)移地址并確定轉(zhuǎn)移方向 ? MEM: 存儲器訪問（僅 Load和 Store) ? WB: 結(jié)果寫回 中國科學(xué)技術(shù)大學(xué) 流水線的可視化表示 ? 多條指令執(zhí)行多個時鐘周期 – 指令按程序序從上到下排列 – 圖中展示了每一時鐘周期資源的使用情況 – 不同指令相鄰階段之間沒有干擾 中國科學(xué)技術(shù)大學(xué) 指令流時序 ? 時序圖展示： – 每個時鐘周期指令所使用的流水段情況 ? 指令流在采用 5段流水線執(zhí)行模式的執(zhí)行情況 中國科學(xué)技術(shù)大學(xué) 單周期、多周期、流水線控制性能比較 ? 假設(shè) 5段指令執(zhí)行流水線 ? 某一程序段假設(shè)： – 20% load, 10% store, 40% ALU, and 30% branch ? 比較三種執(zhí)行模式的性能 中國科學(xué)技術(shù)大學(xué) 中國科學(xué)技術(shù)大學(xué) 03/03review 流水線技術(shù)要點 ? 流水線技術(shù)并不能提高單個任務(wù)的執(zhí)行效率，它可以提高整個系統(tǒng)的吞吐率 ? 流水線中的瓶頸 ——最慢的那一段 ? 多個任務(wù)同時執(zhí)行，但使用不同的資源 ? 其潛在的加速比＝流水線的級數(shù) ? 流水段所需時間不均衡將降低加速比 ? 流水線存在裝入時間和排空時間，使得加速比降低 ? 由于存在相關(guān)問題，會導(dǎo)致流水線停頓 吞吐率： 在單位時間內(nèi)流水線所完成的任務(wù)數(shù)量或輸 出結(jié)果的數(shù)量?！?t Tk 流水線技術(shù)提高系統(tǒng)的任務(wù)吞吐率 中國科學(xué)技術(shù)大學(xué) – 流水線完成 n個連續(xù)任務(wù)所需要的總時間為 （假設(shè)一條 k段 線性流水線） Tk＝ kΔ t＋ (n1)Δ t＝ (k＋ n1)Δ t – 流水線的 實際吞吐率 tnknTP???? )1(? ? ttnknTPn ????????11l i mm a x? 最大吞吐率 :流水線在連續(xù)流動達到穩(wěn)定狀態(tài)后所得到的吞吐率。一條 4段 的流水線 187。 S 1 S 3 S 2 S 4 入 出 △ t △ t 3 △ t △ t 最大吞吐率為 tTP ?? 31m a x中國科學(xué)技術(shù)大學(xué) 18 3. 解決流水線瓶頸問題的常用方法 – 細分瓶頸段 例如： 對前面的 4段 流水線 把瓶頸段 S3細分為 3個子流水線段： S3a， S3b， S3c S 1 S 2 入 出 S 4 △ t △ t △ t △ t △ t △ t S 3a S 3c S 3b 改進后的流水線的吞吐率 ： tTP ??1m a x中國科學(xué)技術(shù)大學(xué) 19 – 重復(fù)設(shè)置瓶頸段 187。 由于流水線有通過時間和排空時間，所以在連續(xù) 完成 n個 任務(wù)的時間內(nèi)，各段并不是滿負荷地工作。 kSE?當 E=1時， S=k，實際加速比達到最大。 ? 效率：流水線的設(shè)備利用率。 例如 branch instructions – 數(shù)據(jù)相關(guān)：在數(shù)據(jù)未準備好之前，就需要使用數(shù)據(jù) 187。 assuming a, b, c, d ,e, and f in memory. Slow 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 采用軟件方法避免數(shù)據(jù)相關(guān) Fast 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,Rd 控制沖突 ? 執(zhí)行分支指令的結(jié)果有兩種 – 分支成功： PC值改變?yōu)榉种мD(zhuǎn)移的目標地址。 優(yōu)點： 簡單。 必要時使用互鎖機制來插入 Stall? – 設(shè)計合適的 ISA 187。 DLX（ MIPS） 還是有 1個 cycle 的分支延遲 中國科學(xué)技術(shù)大學(xué) 延遲轉(zhuǎn)移 4: 延遲轉(zhuǎn)移 主要思想： 從邏輯上 “ 延長 ” 分支指令的執(zhí)行時間。有可能需要 復(fù)制指令 被調(diào)度的指令必須與分支無關(guān) 必須保證在分支成功時執(zhí)行被調(diào)度 的指令不會導(dǎo)致錯誤 任何情況 分支成功時 (但由于復(fù)制指令，有 可能會增大程序空間 ) 分支失敗時 中國科學(xué)技術(shù)大學(xué) 分支取消機制 ? 分支延遲受到兩個方面的限制： –可以被放入延遲槽中的指令要滿足一定的條件。 Unconditional = 14%, 65% change PC P i p e l i n e s p e ed u p = P i p e l i n e d ep t h1 + B r a n c h f r e q u en cy ? B r a n c h