流水線技術(shù)-中國(guó)科學(xué)技術(shù)大學(xué)

1、中國(guó)科學(xué)技術(shù)大學(xué),1,計(jì)算機(jī)體系結(jié)構(gòu),周學(xué)海xhzhou@ustc.edu.cn0551-63601556, 63492149中國(guó)科學(xué)技術(shù)大學(xué),第三章 流水線技術(shù),3.1流水線的基本概念3.2 MIPS基本流水線3.3 DLX (MIPS)中多周期操作的處理3.4 MIPS R4000流水線,中國(guó)科學(xué)技術(shù)大學(xué),chapter03.2,流水線的基本概念,一個(gè)任務(wù)可以分解為k 個(gè)子任務(wù)K個(gè)子任務(wù)在 K 個(gè)不同階段（使用不同的資

2、源）運(yùn)行每個(gè)子任務(wù)執(zhí)行需要1個(gè)單位時(shí)間整個(gè)任務(wù)的執(zhí)行時(shí)間為 K倍單位時(shí)間流水線執(zhí)行模式是重疊執(zhí)行模式K個(gè)流水段并行執(zhí)行K個(gè)不同任務(wù)每個(gè)單位時(shí)間進(jìn)入/離開(kāi)流水線一個(gè)任務(wù),中國(guó)科學(xué)技術(shù)大學(xué),chapter03.3,同步流水線,流水段之間采用時(shí)鐘控制的寄存器文件（clocked registers)時(shí)鐘上升沿到達(dá)時(shí)…所有寄存器同時(shí)保存前一流水段的結(jié)果流水段是組合邏輯電路流水線設(shè)計(jì)中希望各段相對(duì)平衡即所有段的延遲時(shí)間大致相等

3、時(shí)鐘周期取決于延遲最長(zhǎng)的流水段,中國(guó)科學(xué)技術(shù)大學(xué),chapter03.4,流水線的性能,設(shè) = time delay in stage Si時(shí)鐘周期 = max( ) 為最長(zhǎng)的流水段延遲時(shí)鐘頻率 f = 1/ = 1/max( )流水線可以在k+n-1個(gè)時(shí)鐘周期內(nèi)完成n個(gè)任務(wù) 完成第一個(gè)任務(wù)需要 k個(gè)時(shí)鐘周期其他n-1個(gè)任務(wù)需要n-1個(gè)時(shí)鐘周期完成K-段流水線的理想加速比（相對(duì)于串行執(zhí)行）,中國(guó)科學(xué)技術(shù)

4、大學(xué),chapter03.5,簡(jiǎn)單的5段流水線,5個(gè)流水段，每段的延遲為1個(gè)cycleIF: 取值階段選擇地址：下一條指令地址、轉(zhuǎn)移地址ID: 譯碼階段確定控制信號(hào) 并從寄存器文件中讀取寄存器值EX: 執(zhí)行Load 、Store：計(jì)算有效地址Branch：計(jì)算轉(zhuǎn)移地址并確定轉(zhuǎn)移方向MEM: 存儲(chǔ)器訪問(wèn)（僅Load和Store)WB: 結(jié)果寫(xiě)回,中國(guó)科學(xué)技術(shù)大學(xué),chapter03.6,流水線的可視化表示,多條指令執(zhí)行多

5、個(gè)時(shí)鐘周期指令按程序序從上到下排列圖中展示了每一時(shí)鐘周期資源的使用情況不同指令相鄰階段之間沒(méi)有干擾,中國(guó)科學(xué)技術(shù)大學(xué),chapter03.7,指令流時(shí)序,時(shí)序圖展示：每個(gè)時(shí)鐘周期指令所使用的流水段情況指令流在采用5段流水線執(zhí)行模式的執(zhí)行情況,中國(guó)科學(xué)技術(shù)大學(xué),chapter03.8,單周期、多周期、流水線控制性能比較,假設(shè)5段指令執(zhí)行流水線某一程序段假設(shè)：20% load, 10% store, 40% ALU,

6、and 30% branch比較三種執(zhí)行模式的性能,中國(guó)科學(xué)技術(shù)大學(xué),chapter03.9,中國(guó)科學(xué)技術(shù)大學(xué),chapter3.10,03/03-review 流水線技術(shù)要點(diǎn),流水線技術(shù)并不能提高單個(gè)任務(wù)的執(zhí)行效率，它可以提高整個(gè)系統(tǒng)的吞吐率流水線中的瓶頸——最慢的那一段多個(gè)任務(wù)同時(shí)執(zhí)行，但使用不同的資源其潛在的加速比＝流水線的級(jí)數(shù)流水段所需時(shí)間不均衡將降低加速比流水線存在裝入時(shí)間和排空時(shí)間，使得加速比降低由于存在相關(guān)問(wèn)

7、題，會(huì)導(dǎo)致流水線停頓,吞吐率：在單位時(shí)間內(nèi)流水線所完成的任務(wù)數(shù)量或輸 出結(jié)果的數(shù)量。,基本度量參數(shù)：吞吐率，加速比，效率,n：任務(wù)數(shù)Tk：處理完成n個(gè)任務(wù)所用的時(shí)間,流水線的性能分析,中國(guó)科學(xué)技術(shù)大學(xué),chapter03.11,1. 各段時(shí)間均相等的流水線各段時(shí)間均相等的流水線時(shí)空?qǐng)D,流水線技術(shù)提高系統(tǒng)的任務(wù)吞吐率,中國(guó)科學(xué)技術(shù)大學(xué),chapter03.12,流水線完成n個(gè)連續(xù)任務(wù)所需要的總時(shí)間為

8、（假設(shè)一條k段線性流水線）　　　　Tk＝kΔt＋(n-1)Δt＝(k＋n-1)Δt 流水線的實(shí)際吞吐率,最大吞吐率:流水線在連續(xù)流動(dòng)達(dá)到穩(wěn)定狀態(tài)后所得到的吞吐率。,吞吐率,中國(guó)科學(xué)技術(shù)大學(xué),13,最大吞吐率與實(shí)際吞吐率的關(guān)系,流水線的實(shí)際吞吐率小于最大吞吐率，它除了與每個(gè)段的時(shí)間有關(guān)外，還與流水線的段數(shù)k以及輸入到流水線中的任務(wù)數(shù)n等有關(guān)。只有當(dāng)n>>k時(shí)，才有TP≈TPmax。,TP與Tpmax的關(guān)系,中國(guó)科學(xué)技術(shù)大

9、學(xué),chapter03.14,2. 各段時(shí)間不完全相等的流水線 各段時(shí)間不等的流水線及其時(shí)空?qǐng)D一條4段的流水線S1，S3，S4各段的時(shí)間：ΔtS2的時(shí)間：3Δt （瓶頸段）流水線中這種時(shí)間最長(zhǎng)的段稱為流水線的瓶頸段。,流水線中的瓶頸——最慢的段,中國(guó)科學(xué)技術(shù)大學(xué),chapter03.15,,中國(guó)科學(xué)技術(shù)大學(xué),chapter03.16,各段時(shí)間不等的流水線的實(shí)際吞吐率：（ Δti為第i段的時(shí)間，共有k個(gè)段 ）,流水線的最大吞吐

10、率為,,中國(guó)科學(xué)技術(shù)大學(xué),17,例如：一條4段的流水線中，S1，S2，S4各段的時(shí)間都是Δt，唯有S3的時(shí)間是3Δt。,最大吞吐率為,,中國(guó)科學(xué)技術(shù)大學(xué),18,解決流水線瓶頸問(wèn)題的常用方法 細(xì)分瓶頸段 例如：對(duì)前面的4段流水線把瓶頸段S3細(xì)分為3個(gè)子流水線段：S3a，S3b，S3c,改進(jìn)后的流水線的吞吐率 ：,,中國(guó)科學(xué)技術(shù)大學(xué),19,重復(fù)設(shè)置瓶頸段缺點(diǎn)：控制邏輯比較復(fù)雜，所需的硬件增加了。例如：對(duì)前面的4段流水

11、線 重復(fù)設(shè)置瓶頸段S3：S3a，S3b，S3c,,中國(guó)科學(xué)技術(shù)大學(xué),chapter03.20,重復(fù)設(shè)置瓶頸段后的時(shí)空?qǐng)D,,中國(guó)科學(xué)技術(shù)大學(xué),chapter03.21,加速比：完成同樣一批任務(wù)，不使用流水線所用的時(shí)間 與使用流水線所用的時(shí)間之比。假設(shè)：不使用流水線（即順序執(zhí)行）所用的間為T(mén)s，使用流水線后所用的時(shí)間為T(mén)k，則該流水線的加速比為,加速比,中國(guó)科學(xué)技術(shù)大學(xué),chapter03.22,1. 流水線各

12、段時(shí)間相等（都是△t）一條k段流水線完成n個(gè)連續(xù)任務(wù) 所需要的時(shí)間為 Tk = (k＋n-1)Δt順序執(zhí)行n個(gè)任務(wù) 所需要的時(shí)間： Ts= nk△t 流水線的實(shí)際加速比為,,中國(guó)科學(xué)技術(shù)大學(xué),chapter03.23,最大加速比,當(dāng)n>>k時(shí)，S ≈ k思考：流水線的段數(shù)愈多愈好？,,中國(guó)科學(xué)技術(shù)大學(xué),chapter03.24,流水線的各段時(shí)間不完全相等時(shí)一條k段流水線完成n個(gè)連續(xù)任務(wù)

13、的實(shí)際加速比為,,中國(guó)科學(xué)技術(shù)大學(xué),chapter03.25,效率,效率：流水線中的設(shè)備實(shí)際使用時(shí)間與整個(gè)運(yùn)行時(shí)間 的比值，即流水線設(shè)備的利用率。 由于流水線有通過(guò)時(shí)間和排空時(shí)間，所以在連續(xù)完成n個(gè)任務(wù)的時(shí)間內(nèi)，各段并不是滿負(fù)荷地工作。各段時(shí)間相等各段的效率ei相同,中國(guó)科學(xué)技術(shù)大學(xué),chapter03.26,整條流水線的效率為,,可以寫(xiě)成,最高效率為,當(dāng)n>>k時(shí)，E

14、≈1。,,中國(guó)科學(xué)技術(shù)大學(xué),27,當(dāng)流水線各段時(shí)間相等時(shí)，流水線的效率與吞吐率成正比。 E=TP△t 流水線的效率是流水線的實(shí)際加速比S與它的最大加速 比k的比值。,當(dāng)E=1時(shí)，S=k，實(shí)際加速比達(dá)到最大。,,中國(guó)科學(xué)技術(shù)大學(xué),chapter03.28,從時(shí)空?qǐng)D上看，效率就是n個(gè)任務(wù)占用的時(shí)空面積和 k個(gè)段總的時(shí)空面積之比。,當(dāng)各段時(shí)間不相等時(shí),,中國(guó)科學(xué)技術(shù)大學(xué),29,中國(guó)科學(xué)技術(shù)大

15、學(xué),chapter3.30,Summary,實(shí)際吞吐率：假設(shè)k段，完成n個(gè)任務(wù)，單位時(shí)間所實(shí)際完成的任務(wù)數(shù)。加速比: k段流水線的速度與等功能的非流水線的速度之比。效率：流水線的設(shè)備利用率。,中國(guó)科學(xué)技術(shù)大學(xué),chapter3.31,,中國(guó)科學(xué)技術(shù)大學(xué),chapter3.32,-Review: Pipelining,指令流水線通過(guò)指令重疊減小 CPI充分利用數(shù)據(jù)通路當(dāng)前指令執(zhí)行時(shí)，啟動(dòng)下一條指令其性能受限于花費(fèi)時(shí)間最長(zhǎng)的段檢

16、測(cè)和消除相關(guān)如何有利于流水線技術(shù)的應(yīng)用所有的指令都等長(zhǎng)只有很少的指令格式只用Load/Store來(lái)進(jìn)行存儲(chǔ)器訪問(wèn),中國(guó)科學(xué)技術(shù)大學(xué),chapter3.33,-Review：流水線性能分析,流水線技術(shù)應(yīng)用的難度何在? ：相關(guān)問(wèn)題,吞吐率、加速比、效率之間的關(guān)系,中國(guó)科學(xué)技術(shù)大學(xué),chapter3.34,指令流水線：CPU執(zhí)行大量的指令，指令吞吐率非常重要MIPS 的指令格式,3.2 MIPS的基本流水線,所有指令相同長(zhǎng)度在

17、指令格式中寄存器位于同一位置只有Loads和Stores可以對(duì)存儲(chǔ)器操作,6,中國(guó)科學(xué)技術(shù)大學(xué),chapter3.35,MIPS數(shù)據(jù)通路,中國(guó)科學(xué)技術(shù)大學(xué),chapter3.36,,中國(guó)科學(xué)技術(shù)大學(xué),chapter3.37,MIPS數(shù)據(jù)通路,中國(guó)科學(xué)技術(shù)大學(xué),chapter3.38,改進(jìn)后流水線的分支操作,中國(guó)科學(xué)技術(shù)大學(xué),chapter3.39,3.2.1 流水線的相關(guān),相關(guān)的基本概念結(jié)構(gòu)相關(guān)數(shù)據(jù)相關(guān)控制相關(guān),中國(guó)科學(xué)技術(shù)大學(xué)

18、,chapter3.40,采用流水線技術(shù)帶來(lái)的新問(wèn)題,流水線相關(guān)結(jié)構(gòu)相關(guān)：同一時(shí)間兩種方式使用同一資源例如 washer/dryer 合在一起，IM和ID合在一起控制相關(guān): 試圖在條件未評(píng)估之前，就做決定例如 branch instructions數(shù)據(jù)相關(guān)：在數(shù)據(jù)未準(zhǔn)備好之前，就需要使用數(shù)據(jù)當(dāng)前指令的執(zhí)行需要上一條指令的結(jié)果使用等待策略總是可以解決相關(guān)流水線控制必須能檢測(cè)相關(guān)，否則由軟件設(shè)計(jì)來(lái)避免采用相應(yīng)操作解決相關(guān)

19、 (or 等待),中國(guó)科學(xué)技術(shù)大學(xué),chapter3.41,,,Mem,單個(gè)存儲(chǔ)器引起的結(jié)構(gòu)相關(guān),Instr.Order,,,Time (clock cycles),Load,Instr 1,Instr 2,Instr 3,Instr 4,,,,,,,,,Reg,,,,Mem,Reg,,,,,,Reg,,,,Mem,Reg,,,,,,Detection is easy in this case! (right hal

20、f highlight means read, left half write),中國(guó)科學(xué)技術(shù)大學(xué),chapter3.42,消除結(jié)構(gòu)相關(guān),中國(guó)科學(xué)技術(shù)大學(xué),chapter3.43,結(jié)構(gòu)相關(guān)對(duì)性能的影響,例如: 如果每條指令平均訪存1.3 次，而每個(gè)時(shí)鐘周期只能訪存一次，那么在其他資源100％利用的前提下，平均 CPI ? 1.3,中國(guó)科學(xué)技術(shù)大學(xué),chapter3.44,流水線的加速比計(jì)算,For simple RISC pipeli

21、ne, CPI = 1:,中國(guó)科學(xué)技術(shù)大學(xué),chapter3.45,例如： Dual-port vs. Single-port,機(jī)器A: Dual ported memory (“Harvard Architecture”)機(jī)器B: Single ported memory存在結(jié)構(gòu)相關(guān)的機(jī)器B的時(shí)鐘頻率是機(jī)器A的時(shí)鐘頻率的1.05倍Ideal CPI = 1 在機(jī)器B中l(wèi)oad指令會(huì)引起結(jié)構(gòu)相關(guān)，所執(zhí)行的指令中Loads指令占

22、40% Average instruction time = CPI * Clock cycle time 無(wú)結(jié)構(gòu)相關(guān)的機(jī)器A： Average Instruction time = Clock cycle time 存在結(jié)構(gòu)相關(guān)的機(jī)器B： Average Instruction time = (1+0.4*1) * clock cycle time /1.05

23、 = 1.3 * clock cycle time,中國(guó)科學(xué)技術(shù)大學(xué),chapter3.46,數(shù)據(jù)相關(guān)問(wèn)題,,Time (clock cycles),,,,,中國(guó)科學(xué)技術(shù)大學(xué),chapter3.47,寫(xiě)后讀相關(guān)(Read After Write (RAW)) InstrJ tries to read operand before InstrI writes it

24、由于實(shí)際的數(shù)據(jù)交換需求而引起的,三種基本的數(shù)據(jù)相關(guān),I: add r1,r2,r3J: sub r4,r1,r3,,中國(guó)科學(xué)技術(shù)大學(xué),chapter3.48,讀后寫(xiě)相關(guān)Write After Read (WAR) InstrJ writes operand before InstrI reads it編譯器編寫(xiě)者稱之為“anti-dependence”（反相關(guān)），是由于重復(fù)使用寄存器名“r1”引起的.DLX(MIP

25、S) 5 段基本流水線不會(huì)有此類相關(guān)因?yàn)? 所有的指令都是5段, 并且 讀操作總是在第2段，而寫(xiě)操作在第5段,,中國(guó)科學(xué)技術(shù)大學(xué),chapter3.49,寫(xiě)后寫(xiě)相關(guān)（Write After Write (WAW)） InstrJ writes operand before InstrI writes it.編譯器編寫(xiě)者稱之為“output dependence” ，也是由于重復(fù)使用寄存器名 “r1”引起的.在DLX(

26、MIPS) 5段基本流水線中，也不會(huì)發(fā)生。因?yàn)?所有指令都是5段，并且寫(xiě)操作都在第5段在后面的復(fù)雜的流水線中我們將會(huì)看到 WAR 和WAW 相關(guān),,中國(guó)科學(xué)技術(shù)大學(xué),chapter3.50,采用定向技術(shù)避免數(shù)據(jù)相關(guān),中國(guó)科學(xué)技術(shù)大學(xué),chapter3.51,采用定向技術(shù)硬件所需做的修改,中國(guó)科學(xué)技術(shù)大學(xué),chapter3.52,定向源為R-R ALU操作的定向比較判斷,中國(guó)科學(xué)技術(shù)大學(xué),chapter3.53,定向源為ALU－imm

27、操作的定向比較判斷,中國(guó)科學(xué)技術(shù)大學(xué),chapter3.54,定向源為L(zhǎng)oad操作的比較判定,中國(guó)科學(xué)技術(shù)大學(xué),chapter3.55,采用定向技術(shù)仍然存在相關(guān),中國(guó)科學(xué)技術(shù)大學(xué),chapter3.56,DMem,,中國(guó)科學(xué)技術(shù)大學(xué),chapter3.57,Try producing fast code fora = b + c;d = e – f;assuming a, b, c, d ,e, and f in memo

28、ry. Slow code:LW Rb,bLW Rc,cADD Ra,Rb,RcSW a,Ra LW Re,e LW Rf,fSUB Rd,Re,RfSWd,Rd,采用軟件方法避免數(shù)據(jù)相關(guān),Fast code:LW Rb,bLW Rc,cLW Re,e ADD Ra,Rb,RcLW Rf,fSW a,Ra SUB

29、Rd,Re,RfSWd,Rd,控制沖突,執(zhí)行分支指令的結(jié)果有兩種分支成功：PC值改變?yōu)榉种мD(zhuǎn)移的目標(biāo)地址。 在條件判定和轉(zhuǎn)移地址計(jì)算都完成后，才改變PC值。不成功或者失?。篜C的值保持正常遞增，指向順序的下一條指令。分支需要解決兩個(gè)問(wèn)題分支目標(biāo)地址（轉(zhuǎn)移成功意謂著PC值不是 PC+4）CC是否有效，這兩點(diǎn)在DLX(MIPS)中都在流水線的靠后段中確定處理分支指令最簡(jiǎn)單的方法：“凍結(jié)”或者“排空”流水線

30、。 優(yōu)點(diǎn)：簡(jiǎn)單。,中國(guó)科學(xué)技術(shù)大學(xué),chapter03.58,中國(guó)科學(xué)技術(shù)大學(xué),chapter3.59,回顧DLX (MIPS)數(shù)據(jù)通路,簡(jiǎn)單處理分支指令：分支成功的情況,簡(jiǎn)單處理分支指令：分支失敗的情況,,中國(guó)科學(xué)技術(shù)大學(xué),chapter03.60,中國(guó)科學(xué)技術(shù)大學(xué),chapter3.61,減少分支延時(shí)的方法,硬件的方法修改數(shù)據(jù)通路：使得目標(biāo)地址和分支條件盡早確定，其中之一盡早確定是沒(méi)有用的判斷是否為0可以在ID段確定使用另一

31、個(gè)加法器計(jì)算可以在ID段計(jì)算BTA(分支目標(biāo)地址)，即在ID段形成下一條指令地址，兩種可能（BTA, PC+4)，選擇哪一個(gè)取決于ID段確定的CC必要時(shí)使用互鎖機(jī)制來(lái)插入Stall?設(shè)計(jì)合適的ISAe.g. BNEZ, BEQZ on DLX 使得CC可以在ID段確定軟件（通過(guò)編譯器）的方法：調(diào)度一些指令放入分支的延遲槽中預(yù)測(cè)的方法：統(tǒng)計(jì)分支成功和失敗的情況，提高預(yù)測(cè)精度,中國(guó)科學(xué)技術(shù)大學(xué),chapter3.62,新的DL

32、X (MIPS)數(shù)據(jù)通路,中國(guó)科學(xué)技術(shù)大學(xué),chapter3.63,改進(jìn)后流水線的分支操作,中國(guó)科學(xué)技術(shù)大學(xué),chapter3.64,四種可能的解決控制相關(guān)的方法,#1: Stall 直到分支方向確定#2: 預(yù)測(cè)分支失敗直接執(zhí)行后繼指令如果分支實(shí)際情況為分支成功，則撤銷流水線中的指令對(duì)流水線狀態(tài)的更新DLX（MIPS）分支指令平均47%為分支失敗要保證：分支結(jié)果出來(lái)之前不會(huì)改變處理機(jī)的狀態(tài)，以便一旦猜錯(cuò)時(shí)，處理機(jī)能夠回退到原先

33、的狀態(tài)。#3: 預(yù)測(cè)分支成功 前提：先知道分支目標(biāo)地址，后知道分支是否 成功。平均53% DLX （MIPS）分支為分支成功DLX（MIPS）分支目標(biāo)地址在ID段才能計(jì)算出目標(biāo)地址DLX（MIPS） 還是有1個(gè) cycle 的分支延遲,中國(guó)科學(xué)技術(shù)大學(xué),chapter3.65,延遲轉(zhuǎn)移,#4: 延遲轉(zhuǎn)移主要思想： 從邏輯上“延長(zhǎng)”分支指令的執(zhí)行時(shí)間。把延遲分支看成是由原來(lái)的分支指令和若干個(gè)延遲槽構(gòu)成，不管分支

34、是否成功，都要按順序執(zhí)行延遲槽中的指令。定義分支發(fā)生在一系列指令之后branch instructionsequential successor1sequential successor2........sequential successornbranch target if taken5級(jí)流水只需要一個(gè)延遲槽就可以確定目標(biāo)地址和確定條件DLX 使用這種方式,,,,,分支延遲槽中的指令“掩蓋”了流水線原

35、來(lái)必須插入的暫停周期。,具有一個(gè)分支延遲槽的流水線的執(zhí)行過(guò)程,中國(guó)科學(xué)技術(shù)大學(xué),66,中國(guó)科學(xué)技術(shù)大學(xué),chapter3.67,延遲轉(zhuǎn)移,從何處選擇指令來(lái)填充延遲槽？分支指令之前的指令：最好從分支目標(biāo)地址處取: 在分支成功可能性大時(shí)，這種策略較好從分支失敗處調(diào)度：僅在分支失敗時(shí)編譯器可以有效的調(diào)度一個(gè)延遲槽如果提供取消分支時(shí)， 編譯器可以調(diào)度更多的指令填入延遲槽,,調(diào)度前和調(diào)度后的代碼,中國(guó)科學(xué)技術(shù)大學(xué),chapter03.6

36、8,,三種方法的要求及效果,調(diào) 度 策 略,對(duì)調(diào)度的要求,什么情況下起作用,從 前 調(diào) 度,從目標(biāo)處調(diào)度,從失敗處調(diào)度,必須保證在分支失敗時(shí)執(zhí)行被調(diào)度的指令不會(huì)導(dǎo)致錯(cuò)誤。有可能需要復(fù)制指令,被調(diào)度的指令必須與分支無(wú)關(guān),必須保證在分支成功時(shí)執(zhí)行被調(diào)度的指令不會(huì)導(dǎo)致錯(cuò)誤,任何情況,分支成功時(shí)(但由于復(fù)制指令，有可能會(huì)增大程序空間),分支失敗時(shí),,,,,,,中國(guó)科學(xué)技術(shù)大學(xué),chapter03.69,分支取消機(jī)制,分支延遲受到兩個(gè)方

37、面的限制：可以被放入延遲槽中的指令要滿足一定的條件。編譯器預(yù)測(cè)分支轉(zhuǎn)移方向的能力。進(jìn)一步改進(jìn)：分支取消機(jī)制當(dāng)分支的實(shí)際執(zhí)行方向和事先所預(yù)測(cè)的一樣時(shí)執(zhí)行分支延遲槽中的指令，否則就將分支延遲槽中的指令轉(zhuǎn)化成一個(gè)空操作。,中國(guó)科學(xué)技術(shù)大學(xué),chapter03.70,,,預(yù)測(cè)分支成功的情況下，分支取消機(jī)制的執(zhí)行情況,分支取消機(jī)制示意,中國(guó)科學(xué)技術(shù)大學(xué),chapter03.71,中國(guó)科學(xué)技術(shù)大學(xué),chapter3.72,評(píng)估減少分支策略的

38、效果,SchedulingBranchCPIspeedup v.speedup v. scheme penaltyunpipelinedstallStall pipeline31.423.51.0Predict taken11.144.41.26Predict not taken11.094.51.29Delayed branch0.51.074.61.31

39、 1.14 = 1 + 1*14%*100% 1.09 = 1+1*14%*65% 1.07 = 1+ 0.5*14%Conditional & Unconditional = 14%, 65% change PC,中國(guó)科學(xué)技術(shù)大學(xué),chapter3.73,03/08-Review：流水線性能分析,流水線技術(shù)應(yīng)用的難度何在? ：相關(guān)問(wèn)題相關(guān)的類型：

40、結(jié)構(gòu)相關(guān)，控制相關(guān)，以及數(shù)據(jù)相關(guān)（RAW, WAR, WAW）,吞吐率、加速比、效率之間的關(guān)系,中國(guó)科學(xué)技術(shù)大學(xué),chapter3.74,指令流水線：CPU執(zhí)行大量的指令，指令吞吐率非常重要MIPS 的ISA：RISC,03/08-Review: MIPS的基本流水線,中國(guó)科學(xué)技術(shù)大學(xué),chapter3.75,03/08-Review,相關(guān)會(huì)影響流水線性能結(jié)構(gòu)相關(guān): 由于爭(zhēng)用資源而引起的解決辦法: 等待 增加（或拆分）資源

41、數(shù)據(jù)相關(guān)：兩條指令訪問(wèn)相同的數(shù)據(jù)而引起的解決辦法：硬件：定向技術(shù)（forwarding)軟件：指令級(jí)調(diào)度控制相關(guān)：由于控制類指令引起的減少性能損失的基本方法凍結(jié)或排空流水線預(yù)測(cè)分支成功預(yù)測(cè)分支失敗延遲轉(zhuǎn)移,中國(guó)科學(xué)技術(shù)大學(xué),chapter3.76,3.2.2 異常處理,流水線使得系統(tǒng)的吞吐率提高問(wèn)題:由于相關(guān)會(huì)影響系統(tǒng)性能的發(fā)揮另一問(wèn)題：異常 Why？多級(jí)流水－》多周期指令異常可以發(fā)生在任何地方指令序與異

42、常序可能不同必須按指令序處理異常采用何種策略取決于異常的類型,中國(guó)科學(xué)技術(shù)大學(xué),chapter3.77,異常的類型,I/O 設(shè)備請(qǐng)求 用戶程序調(diào)用OS服務(wù)斷點(diǎn) 整數(shù)或浮點(diǎn)數(shù)運(yùn)算溢出 缺頁(yè) 非對(duì)齊存儲(chǔ)器訪問(wèn) 存儲(chǔ)器保護(hù)沖突 未定義的指令 硬件失效 – 例如： parity or ECC error 電源故障,中國(guó)科學(xué)技術(shù)大學(xué),chapter3.78,異常的分類,Synchronous vs. Asynchronous

43、synchronous caused by a particular instructionasynchronous - external devices and HW failuresUser requested vs. Coercedrequested is predictable and can happen after the instructionUser maskable vs. user non-maskable

44、e.g. arithmetic overflow on some machines is user maskableWithin vs. Between instructionswithin ==> synchronous, key is that completion is preventedsome asynchronous are also within Resume vs. Terminate programi

45、mplications for how much state must be preserved,中國(guó)科學(xué)技術(shù)大學(xué),chapter3.79,例如,中國(guó)科學(xué)技術(shù)大學(xué),chapter3.80,最困難的問(wèn)題,異常發(fā)生在指令中(within)，并且要求恢復(fù)執(zhí)行(resume) 要求==>流水線必須安全地 shut downPC必須保存如果重新開(kāi)始的是一條分支指令，它需要重新執(zhí)行，這意味著條件碼狀態(tài)必須沒(méi)有改變?cè)贒LX(MIPS)中

46、的處理步驟強(qiáng)制trap指令在下一個(gè)IF段進(jìn)入流水線封鎖引起故障的指令的所有寫(xiě)操作和流水線中后繼指令的寫(xiě)操作讓所有前序指令執(zhí)行完（如果能）保存重新執(zhí)行時(shí)的地址（PC）PC 或 PC + 1調(diào)用OS處理異常,中國(guó)科學(xué)技術(shù)大學(xué),chapter3.81,,考慮延遲轉(zhuǎn)移時(shí)，假設(shè)有兩個(gè)延遲槽的分支I Branch Instr1I+1 Delay instr1I+2Delay Instr2I+3instI+4

47、inst假設(shè)branch指令是好的第1個(gè)延遲指令引起缺頁(yè)中斷第2條指令封鎖異常處理后，缺省的恢復(fù)點(diǎn)是第一條延遲指令不會(huì)有Branch指令因此需要保存的PC值不止一個(gè)，根據(jù)具體情況進(jìn)行恢復(fù),中國(guó)科學(xué)技術(shù)大學(xué),chapter3.82,精確中斷與非精確中斷,精確中斷如果流水線可以控制使得引起異常的指令前序指令都執(zhí)行完，故障后的指令可以重新執(zhí)行，則稱該流水線支持精確中斷按照指令的邏輯序處理異常理想情況，引起故障的指令沒(méi)有改變

48、機(jī)器的狀態(tài)要正確的處理這類異常請(qǐng)求，必須保證故障指令不產(chǎn)生副作用在有些機(jī)器上，浮點(diǎn)數(shù)異常流水線段數(shù)多，在發(fā)現(xiàn)故障前，故障點(diǎn)后的指令就已經(jīng)寫(xiě)了結(jié)果，在這種情況下，必須有辦法處理。當(dāng)今很多高性能計(jì)算機(jī)，Alpha 21164，MIPS R10000等支持精確中斷，但精確模式要慢10+倍，一般用在代碼調(diào)試時(shí)，很多系統(tǒng)要求精確中斷模式，如IEEE FP標(biāo)準(zhǔn)處理程序，虛擬存儲(chǔ)器等。精確中斷對(duì)整數(shù)流水線而言，不是太難實(shí)現(xiàn)指令執(zhí)行的中途改

49、變機(jī)器的狀態(tài)例如IA-32 的自動(dòng)增量尋址模式,中國(guó)科學(xué)技術(shù)大學(xué),chapter3.83,DLX (MIPS)中的異常,IF page fault, misaligned address, memory protection violationID undefined or illegal opcodeEX arithmetic exceptionMEM page fault, misaligned address, m

50、emory protection violationWB none,中國(guó)科學(xué)技術(shù)大學(xué),chapter3.84,3.3 DLX (MIPS)中多周期操作的處理,問(wèn)題浮點(diǎn)操作在1～2個(gè)cycles完成是不現(xiàn)實(shí)的，一般要花費(fèi)較長(zhǎng)時(shí)間在DLX(MIPS)中如何處理在1到2個(gè)cycles時(shí)間內(nèi)完成的處理方法采用較慢的時(shí)鐘源，或在FP部件中延遲其EX段現(xiàn)假設(shè)FP指令與整數(shù)指令采用相同的流水線，那么EX 段需要循環(huán)多次來(lái)完成FP操作

51、，循環(huán)次數(shù)取決于操作類型有多個(gè)FP功能部件，如果發(fā)射出的指令導(dǎo)致結(jié)構(gòu)或數(shù)據(jù)相關(guān)，需暫停,中國(guó)科學(xué)技術(shù)大學(xué),chapter3.85,對(duì)DLX(MIPS)的擴(kuò)充,四個(gè)功能部件Integer 部件處理：Loads, Store, Integer ALU操作和BranchFP/Integer 乘法部件：處理浮點(diǎn)數(shù)和整數(shù)乘法FP加法器：處理FP加，減和類型轉(zhuǎn)換FP/Integer除法部件：處理浮點(diǎn)數(shù)和整數(shù)除法這些功能部件未流水化,中國(guó)

52、科學(xué)技術(shù)大學(xué),chapter3.86,擴(kuò)展的DLX(MIPS)流水線,,中國(guó)科學(xué)技術(shù)大學(xué),chapter3.87,Latency & Repeat Interval,延時(shí)(Latency) 定義為完成某一操作所需的cycle數(shù)定義為使用當(dāng)前指令所產(chǎn)生結(jié)果的指令與當(dāng)前指令間的最小間隔周期數(shù)循環(huán)間隔（Repeat/Initiation interval）發(fā)射相同類型的操作所需的間隔周期數(shù)對(duì)于EX部件流水化的新的DLX(MI

53、PS),中國(guó)科學(xué)技術(shù)大學(xué),chapter3.88,將部分執(zhí)行部件流水化后的DLX(MIPS)流水線,,中國(guó)科學(xué)技術(shù)大學(xué),chapter3.89,新的相關(guān)和定向問(wèn)題,結(jié)構(gòu)沖突增多非流水的Divide部件，使得EX段增長(zhǎng)24個(gè)cycles在一個(gè)周期內(nèi)可能有多個(gè)寄存器寫(xiě)操作可能指令亂序完成（亂序到達(dá)WB段）有可能存在WAW 由于在ID段讀，還不會(huì)有 WAR 相關(guān)亂序完成導(dǎo)致異常處理復(fù)雜由于指令的延遲加大導(dǎo)致RAW 相關(guān)的stall

54、數(shù)增多需要付出更多的代價(jià)來(lái)增加定向路徑,中國(guó)科學(xué)技術(shù)大學(xué),chapter3.90,新的結(jié)構(gòu)相關(guān),縱向檢查指令所使用的資源第10個(gè)cycle，三條指令同時(shí)進(jìn)入MEM，但由于MULTD和ADDD在MEM段沒(méi)有實(shí)際動(dòng)作，這種情況沒(méi)有關(guān)系第11個(gè)cycle，三條指令同時(shí)進(jìn)入WB段，存在結(jié)構(gòu)相關(guān),中國(guó)科學(xué)技術(shù)大學(xué),chapter3.91,解決方法,Option 1在ID段跟蹤寫(xiě)端口的使用情況，以便能暫停該指令的發(fā)射一旦發(fā)現(xiàn)沖突，暫停當(dāng)前

55、指令的發(fā)射Option 2在進(jìn)入MEM或WB段時(shí)，暫停沖突的指令，讓有較長(zhǎng)延時(shí)的指令先做，因?yàn)檩^長(zhǎng)延時(shí)的指令，會(huì)更容易引起其他RAW相關(guān)，從而導(dǎo)致更多的stalls,中國(guó)科學(xué)技術(shù)大學(xué),chapter3.92,關(guān)于數(shù)據(jù)相關(guān),S.D 多延遲一個(gè)cycle，以消解與ADD.D的沖突,中國(guó)科學(xué)技術(shù)大學(xué),chapter3.93,新的沖突源,GPR與FPR間的數(shù)據(jù)傳送造成的數(shù)據(jù)相關(guān)MOVI2FP and MOVFP2I instruction

56、s如果在ID段進(jìn)行相關(guān)檢測(cè)，指令發(fā)射前須做如下檢測(cè)：結(jié)構(gòu)相關(guān)循環(huán)間隔檢測(cè)確定寄存器寫(xiě)端口是否可用RAW相關(guān)列表所有待寫(xiě)的目的寄存器不發(fā)射以待寫(xiě)寄存器做為源寄存器的指令，插入latency個(gè)stallWAW相關(guān)仍然使用上述待寫(xiě)寄存器列表不發(fā)射那些目的寄存器與待寫(xiě)寄存器列表中的指令有WAW沖突的指令，延遲1個(gè)cycle發(fā)射。,中國(guó)科學(xué)技術(shù)大學(xué),chapter3.94,精確中斷與長(zhǎng)流水線,例如DIVF F0,F2,F4

57、ADDF F10,F10,F8SUBF F12,F12,F14ADDF 和SUBF都在DIVF前完成如果DIVF導(dǎo)致異常，會(huì)如何？非精確中斷Ideas???,中國(guó)科學(xué)技術(shù)大學(xué),chapter3.95,處理中斷4種可能的辦法,方法1：忽略這種問(wèn)題，當(dāng)非精確處理原來(lái)的supercomputer的方法但現(xiàn)代計(jì)算機(jī)對(duì)IEEE 浮點(diǎn)標(biāo)準(zhǔn)的異常處理，虛擬存儲(chǔ)的異常處理要求必須是精確中斷。方法2：緩存操作結(jié)果，直到早期發(fā)射的指令執(zhí)行完

58、。當(dāng)指令運(yùn)行時(shí)間較長(zhǎng)時(shí)，Buffer區(qū)較大Future file (Power PC620 MIPS R10000)緩存執(zhí)行結(jié)果，按指令序確認(rèn)history file (CYBER 180/990)盡快確認(rèn)緩存區(qū)存放原來(lái)的操作數(shù)，如果異常發(fā)生，回卷到合適的狀態(tài),中國(guó)科學(xué)技術(shù)大學(xué),chapter3.96,第3 & 4種方法,以非精確方式處理，用軟件來(lái)修正為軟件修正保存足夠的狀態(tài)讓軟件仿真尚未執(zhí)行完的指令的執(zhí)行

59、例如Instruction 1 – A 執(zhí)行時(shí)間較長(zhǎng)，引起中斷的指令I(lǐng)nstruction 2, instruction 3, ….instruction n-1 未執(zhí)行完的指令I(lǐng)nstruction n 已執(zhí)行完的指令由于第n條指令已執(zhí)行完，希望中斷返回后從第n+1條指令開(kāi)始執(zhí)行，如果我們保存所有的流水線的PC值，那么軟件可以仿真Instruction1 到Instruction n-1 的執(zhí)行暫停發(fā)射，直到確定先前的

60、指令都可無(wú)異常的完成，再發(fā)射下面的指令。在EX段的前期確認(rèn)（MIPS流水線在前三個(gè)周期中）MIPS R2K to R4K 以及Pentium使用這種方法,中國(guó)科學(xué)技術(shù)大學(xué),chapter3.97,DLX(MIPS)流水線的性能,Stalls per FP operation for each major type of FP operation for the SPEC89 FP benchmarks,中國(guó)科學(xué)技術(shù)大學(xué),chapte

61、r3.98,平均每條指令的stall數(shù),The stalls occurring for the MIPS FP pipeline for five for the SPEC89 FP benchmarks.,中國(guó)科學(xué)技術(shù)大學(xué),chapter3.99,MIPS R4000,實(shí)際的 64-bit 機(jī)器主頻100MHz ~200MHz較深的流水線（級(jí)數(shù)較多）(有時(shí)也稱為 superpipelining)指令集與DLX非常類似,中國(guó)科學(xué)

62、技術(shù)大學(xué),chapter3.100,MIPS R4000的8 級(jí)整數(shù)流水線,IF–取指階段前半部分；選擇PC值，初始化指令cache的訪問(wèn)IS–取指階段后半部分，主要完成訪問(wèn)指令cache的操作RF–指令譯碼，寄存器讀取，相關(guān)檢測(cè)以及指令cache命中檢測(cè)EX–執(zhí)行，包括：計(jì)算有效地址，進(jìn)行ALU操作，計(jì)算分支目標(biāo)地址和檢測(cè)分支條件DF–取數(shù)據(jù)，訪問(wèn)數(shù)據(jù)cache的前半部分DS–訪問(wèn)數(shù)據(jù)cache的后半部分TC–tag 檢測(cè)

63、，確定數(shù)據(jù)cache是否命中WB–Load操作和R-R操作的結(jié)果寫(xiě)回,中國(guó)科學(xué)技術(shù)大學(xué),chapter3.101,需注意的問(wèn)題,在使用定向技術(shù)的情況下，Load 延遲為2個(gè)cyclesLoad和與其相關(guān)的指令間必須有2條指令或兩個(gè)bubbles原因：load的結(jié)果在DS結(jié)束時(shí)可用分支延遲3個(gè)cycles分支與目標(biāo)指令間需要3條指令或3個(gè)bubbles原因：目標(biāo)地址在EX段后才能知道R4000的流水線中，到ALU輸入端有四個(gè)

64、定向源EX/DF, DF/DS, DS/ TC, TC/WB,中國(guó)科學(xué)技術(shù)大學(xué),chapter3.102,圖示,03/10-review,影響流水線性能結(jié)構(gòu)相關(guān)、數(shù)據(jù)相關(guān)控制相關(guān)、異常異常處理種類與分類精確與非精確中斷支持浮點(diǎn)數(shù)操作的MIPS流水線Latency & Repeat Interval問(wèn)題：結(jié)構(gòu)相關(guān)（增多）；數(shù)據(jù)相關(guān)、控制相關(guān)引起的stall增多；有新的沖突源產(chǎn)生；定向路徑增多；異常處理復(fù)雜MIP

65、S R4000 8級(jí)流水線存儲(chǔ)器操作分階段 – load延遲為2個(gè)cyclesBranch操作在EX段確定分支方向- 3個(gè)cycles的延遲多個(gè)定向源 ：EX/DF，DF/DS，DS/TC，TC/WBMIPS R4000的浮點(diǎn)數(shù)操作,中國(guó)科學(xué)技術(shù)大學(xué),chapter03.103,ALU輸入端的定向源,,中國(guó)科學(xué)技術(shù)大學(xué),chapter03.104,中國(guó)科學(xué)技術(shù)大學(xué),chapter3.105,MIPS R4000 浮點(diǎn)數(shù)操作,3個(gè)

66、功能部件組成：FP Adder, FP Multiplier, FP Divider在乘/除操作的最后一步要 使用FP Adder FP操作需要2（negate）-112個(gè)（square root）cycles8 種類型的FP units:StageFunctional unitDescriptionAFP adderMantissa ADD stage DFP dividerDivide pipeline

67、 stageEFP multiplierException test stageMFP multiplierFirst stage of multiplierNFP multiplierSecond stage of multiplierRFP adderRounding stageSFP adderOperand shift stageUUnpack FP numbers,,中國(guó)科學(xué)技術(shù)

68、大學(xué),chapter03.106,雙精度浮點(diǎn)數(shù)操作延遲及初始化間隔,中國(guó)科學(xué)技術(shù)大學(xué),chapter03.107,中國(guó)科學(xué)技術(shù)大學(xué),chapter3.108,MIPS FP 流水段,FP Instr 1 2 3 4 5 6 7 8…Add, SubtractU S+A A+R R+SMultiplyU E+M M

69、 M M N N+A RDivideU A R D28… D+A，D+R, D+R, D+A, D+R, A, RSquare rootU E (A+R)108… ARNegateU SAbsolute valueU SFP compareU