體系結(jié)構(gòu)第3章 第5講

1、國(guó)防科技大學(xué)計(jì)算機(jī)學(xué)院國(guó)防科技大學(xué)計(jì)算機(jī)學(xué)院主講人：主講人： 教授教授本章內(nèi)容本章內(nèi)容1. 1. 分支指令的實(shí)現(xiàn)分支指令的實(shí)現(xiàn)u一旦分支轉(zhuǎn)移成功，正確的地址要在一旦分支轉(zhuǎn)移成功，正確的地址要在MemMem段的末段的末尾尾才會(huì)被寫入才會(huì)被寫入PCPCu一旦一旦IDID段檢測(cè)到分支指令，就暫停執(zhí)行其后的指段檢測(cè)到分支指令，就暫停執(zhí)行其后的指令，直到分支指令達(dá)到令，直到分支指令達(dá)到MemMem段，確定新的段，確定新的PCPC為止為止u分支轉(zhuǎn)移成功分支轉(zhuǎn)移成功將導(dǎo)致將導(dǎo)致MIPSMIPS流水線流水線暫停暫停3 3個(gè)周期個(gè)周期2. 2. 減少分支開銷的途徑減少分支開銷的途徑u兩個(gè)基本途徑：同時(shí)采用，缺一

2、不可！兩個(gè)基本途徑：同時(shí)采用，缺一不可！- 在流水線中盡早判斷分支轉(zhuǎn)移是否成功在流水線中盡早判斷分支轉(zhuǎn)移是否成功- 轉(zhuǎn)移成功時(shí)，盡早計(jì)算出轉(zhuǎn)移目標(biāo)地址轉(zhuǎn)移成功時(shí)，盡早計(jì)算出轉(zhuǎn)移目標(biāo)地址u經(jīng)經(jīng)改進(jìn)改進(jìn)，MIPSMIPS流水線可以將分支開銷流水線可以將分支開銷減少減少1 1拍拍- 將將“=0?”=0?”測(cè)試提前到測(cè)試提前到IDID段段- 在在IDID段增加一個(gè)加法器，計(jì)算分支目標(biāo)地址段增加一個(gè)加法器，計(jì)算分支目標(biāo)地址表表3.63.6列出了改進(jìn)后流水線的分支操作列出了改進(jìn)后流水線的分支操作u再改進(jìn)再改進(jìn)，MIPSMIPS流水線可以將分支開銷流水線可以將分支開銷再減少再減少1 1拍拍-將分支判斷結(jié)果和

3、目標(biāo)地址提前到將分支判斷結(jié)果和目標(biāo)地址提前到ID/EXID/EX站前站前3. 3. 程序中分支指令的行為特點(diǎn)程序中分支指令的行為特點(diǎn)(1) (1) 各種能改變各種能改變PCPC值的指令的執(zhí)行頻度值的指令的執(zhí)行頻度u條件分支：條件分支：- 整數(shù)程序：整數(shù)程序：14-15%14-15%- 浮點(diǎn)程序：浮點(diǎn)程序：3-12%3-12%其中，向前分支與向后分支的比：其中，向前分支與向后分支的比：3:13:1u無條件分支：無條件分支：4%4%（絕大多數(shù)）（絕大多數(shù)）(2) (2) 條件分支轉(zhuǎn)移成功的概率條件分支轉(zhuǎn)移成功的概率u向前轉(zhuǎn)移成功：向前轉(zhuǎn)移成功：60%60%；向后轉(zhuǎn)移成功：；向后轉(zhuǎn)移成功：85%85

4、%4. 4. 減少流水線分支損失的方法減少流水線分支損失的方法(1) (1) 凍結(jié)或排空流水線凍結(jié)或排空流水線u思路：在流水線中停住或刪除分支后的指令，直思路：在流水線中停住或刪除分支后的指令，直到知道轉(zhuǎn)移目標(biāo)地址到知道轉(zhuǎn)移目標(biāo)地址u優(yōu)點(diǎn)：簡(jiǎn)單優(yōu)點(diǎn)：簡(jiǎn)單(2) (2) 預(yù)測(cè)分支轉(zhuǎn)移失敗預(yù)測(cè)分支轉(zhuǎn)移失敗u思路：流水線繼續(xù)照常流動(dòng)，如果分支轉(zhuǎn)移成功，思路：流水線繼續(xù)照常流動(dòng)，如果分支轉(zhuǎn)移成功，將分支指令后的指令轉(zhuǎn)換為空操作，并從分支目將分支指令后的指令轉(zhuǎn)換為空操作，并從分支目標(biāo)處開始取指令執(zhí)行；否則照常執(zhí)行標(biāo)處開始取指令執(zhí)行；否則照常執(zhí)行uMIPSMIPS流水線的處理過程流水線的處理過程4. 4.

5、 減少流水線分支損失的方法減少流水線分支損失的方法(3) (3) 預(yù)測(cè)分支轉(zhuǎn)移成功預(yù)測(cè)分支轉(zhuǎn)移成功u思路：始終假設(shè)分支成功，直接從分支目標(biāo)處取思路：始終假設(shè)分支成功，直接從分支目標(biāo)處取指令執(zhí)行指令執(zhí)行u對(duì)對(duì)MIPSMIPS流水線沒有任何好處！流水線沒有任何好處！(4) (4) 延遲分支（延遲分支（delayed branchdelayed branch）u思路：思路：分支開銷為分支開銷為n n的分支指令后緊跟有的分支指令后緊跟有n n個(gè)延個(gè)延遲槽，遲槽，流水線遇到分支指令時(shí)，按正常方式處理流水線遇到分支指令時(shí)，按正常方式處理，順帶執(zhí)行延遲槽中的指令，從而減少分支開銷。順帶執(zhí)行延遲槽中的指令，從

6、而減少分支開銷。延遲分支及指令的執(zhí)行順序延遲分支及指令的執(zhí)行順序4. 4. 減少流水線分支損失的方法減少流水線分支損失的方法u具有一個(gè)分支延遲槽的具有一個(gè)分支延遲槽的MIPSMIPS流水線的流水線的執(zhí)行過程執(zhí)行過程u什么樣的指令能否放入分支延遲槽？什么樣的指令能否放入分支延遲槽？-三種調(diào)度方法三種調(diào)度方法：從前調(diào)度；從目標(biāo)處調(diào)度；從失敗處調(diào)度：從前調(diào)度；從目標(biāo)處調(diào)度；從失敗處調(diào)度-三種方法的要求與效果三種方法的要求與效果，存在限制因素，存在限制因素 編譯器預(yù)測(cè)分支是否成功的能力編譯器預(yù)測(cè)分支是否成功的能力 放入延遲槽中的指令放入延遲槽中的指令-取消分支取消分支（舉例舉例）思路：分支指令中包含預(yù)

7、測(cè)方向，若預(yù)測(cè)正確，正常執(zhí)行思路：分支指令中包含預(yù)測(cè)方向，若預(yù)測(cè)正確，正常執(zhí)行延遲槽中的指令，否則將其轉(zhuǎn)換為空操作延遲槽中的指令，否則將其轉(zhuǎn)換為空操作5. 5. 各種分支處理方法的性能各種分支處理方法的性能(1) (1) 假設(shè)理想假設(shè)理想CPI=1CPI=1，則加速比，則加速比S=D/(1+C)=D/(1+fS=D/(1+C)=D/(1+fp p分支分支) )這里，這里，D D為流水線的深度，為流水線的深度，p p分支分支為分支開銷，為分支開銷，C C為分支引起的流水線暫停時(shí)鐘周期數(shù)為分支引起的流水線暫停時(shí)鐘周期數(shù)( (每條指令每條指令的平均值的平均值) )，f f為分支的出現(xiàn)頻度。為分支的出

8、現(xiàn)頻度。(2) (2) 表表3.73.7列出了流水線中各種處理方法的開銷列出了流水線中各種處理方法的開銷3.4 實(shí)例分析：實(shí)例分析：MIPS R40003.4.1 MIPS R4000的整型流水線的整型流水線3.4.2 MIPS R4000的浮點(diǎn)流水線的浮點(diǎn)流水線3.4.3 MIPS R4000流水線性能分析流水線性能分析1. 1. 指令集：指令集：6464位位MIPS-3MIPS-3指令集指令集2. MIPS R40002. MIPS R4000流水線結(jié)構(gòu)流水線結(jié)構(gòu)u超流水結(jié)構(gòu)（超流水結(jié)構(gòu)（superpipelingsuperpipeling）u訪存操作流水化訪存操作流水化3. 3. 流水線

9、各段的功能流水線各段的功能4. 4. 指令序列在流水線中的重疊執(zhí)行過程指令序列在流水線中的重疊執(zhí)行過程定向定向+ +插入暫停周期插入暫停周期5. 5. 載入延遲為兩個(gè)時(shí)鐘周期載入延遲為兩個(gè)時(shí)鐘周期6. 6. 指令序列在流水線中的執(zhí)行時(shí)空?qǐng)D指令序列在流水線中的執(zhí)行時(shí)空?qǐng)D7. R40007. R4000流水線的定向路徑遠(yuǎn)多于流水線的定向路徑遠(yuǎn)多于MIPSMIPS流水線流水線ALUALU輸入端的定向源有輸入端的定向源有4 4個(gè)：個(gè)：EX/DFEX/DF，DF/DSDF/DS，DS/TCDS/TC，TC/WBTC/WB8. 8. 分支處理分支處理u在在EXEX段完成分支條件的計(jì)算，基本分支延遲為段完成

10、分支條件的計(jì)算，基本分支延遲為3 3個(gè)時(shí)鐘周期個(gè)時(shí)鐘周期u分支處理策略分支處理策略- 單周期延遲分支單周期延遲分支- 從失敗處調(diào)度從失敗處調(diào)度 時(shí)時(shí)- -空?qǐng)D空?qǐng)Du包括浮點(diǎn)除法器、浮點(diǎn)乘法器和浮點(diǎn)加法器各包括浮點(diǎn)除法器、浮點(diǎn)乘法器和浮點(diǎn)加法器各1 1個(gè)個(gè)u分為分為8 8段（段（P121 P121 表表3.93.9）u多功能非線性流水線多功能非線性流水線u雙精度浮點(diǎn)操作指令延遲、初始化間隔和流水段的雙精度浮點(diǎn)操作指令延遲、初始化間隔和流水段的使用情況（使用情況（P121 P121 表表3.103.10）1. 1. 引起流水線暫停的四個(gè)主要原因引起流水線暫停的四個(gè)主要原因u載入暫停載入暫停u分支暫

11、停分支暫停u浮點(diǎn)結(jié)果暫停浮點(diǎn)結(jié)果暫停u浮點(diǎn)結(jié)構(gòu)性暫停浮點(diǎn)結(jié)構(gòu)性暫停2. 2. 暫停對(duì)暫停對(duì)MIPS R4000MIPS R4000流水線流水線CPICPI的影響的影響表表3.113.11從前調(diào)度從前調(diào)度從目標(biāo)處調(diào)度從目標(biāo)處調(diào)度從失敗處調(diào)度從失敗處調(diào)度Notake takeADD ADD If If ADD R1,R2,R3Notake TakeADD ADD SUB SUBADD ADDif if SUB ADDNotake TakeADD ADD If If SUB Notake takeIf If ADD ADD Notake TakeADD ADD SUB SUBADD ADDif if

12、SUB SUB ADDNotake TakeADD ADD If IfSUB SUB 流水段流水段分分 支支 指指 令令 操操 作作IFIDEXIF/ID.IR MemPC; IF/ID.NPC,PC (if ID/EX.condID/EX.NPC else PC+4);ID/EX.A RegsIF/ID.IR6.10; ID/EX.B RegsIF/ID.IR11.15;ID/EX.NPC IF/ID.NPC + (IR16)16 # IR16.31;ID/EX.IR IF/ID.IR; ID/EX.cond (RegsIF/ID.IR6.10 op 0;ID/EX.Imm (IR16)16

13、#IR16.31;MEMWB表表3.63.6三種方法的要求及效果三種方法的要求及效果調(diào)度策略調(diào)度策略對(duì)調(diào)度的要求對(duì)調(diào)度的要求其作用前提其作用前提從前調(diào)度從前調(diào)度被調(diào)度的指令必須與分支結(jié)果被調(diào)度的指令必須與分支結(jié)果無關(guān)無關(guān)任何情況任何情況從目標(biāo)從目標(biāo)處調(diào)度處調(diào)度必須保證在分支失敗時(shí)執(zhí)行被必須保證在分支失敗時(shí)執(zhí)行被調(diào)度的指令不會(huì)導(dǎo)致錯(cuò)誤，可調(diào)度的指令不會(huì)導(dǎo)致錯(cuò)誤，可能需要復(fù)制指令能需要復(fù)制指令分支成功時(shí)分支成功時(shí)從失敗從失敗處調(diào)度處調(diào)度必須保證在分支成功時(shí)執(zhí)行被必須保證在分支成功時(shí)執(zhí)行被調(diào)度的指令不會(huì)導(dǎo)致錯(cuò)誤調(diào)度的指令不會(huì)導(dǎo)致錯(cuò)誤分支失敗時(shí)分支失敗時(shí)表表3.7 3.7 各種減少分支損失方法的效果各

14、種減少分支損失方法的效果 調(diào)度方法每條分支指令的平均分支損失暫停流水線預(yù)測(cè)分支成功每條條件分支指 令的分支損失預(yù)測(cè)分支失敗1.00延遲分支每條無條件分支指令的損失具有分支暫停 的有效 CPI浮 點(diǎn)平 均整 型平 均整 型平 均整 型平 均浮 點(diǎn)平 均浮 點(diǎn)平 均1.001.000.620.251.001.001.001.001.000.690.211.001.171.151.001.17 1.150.741.121.110.701.000.350.000.301.041.04EarleEarle鎖存器鎖存器u19651965年由年由J.G.EarleJ.G.Earle發(fā)明發(fā)明u優(yōu)點(diǎn)優(yōu)點(diǎn)- 對(duì)時(shí)

15、鐘扭曲不敏感（相對(duì)而言），一般是兩級(jí)門對(duì)時(shí)鐘扭曲不敏感（相對(duì)而言），一般是兩級(jí)門延遲，避免了數(shù)據(jù)通過鎖存器時(shí)可能產(chǎn)生的時(shí)鐘延遲，避免了數(shù)據(jù)通過鎖存器時(shí)可能產(chǎn)生的時(shí)鐘扭曲扭曲- 在鎖存器中可以執(zhí)行兩級(jí)邏輯運(yùn)算，而不會(huì)增加在鎖存器中可以執(zhí)行兩級(jí)邏輯運(yùn)算，而不會(huì)增加鎖存器的延遲時(shí)間，可以隱藏鎖存器產(chǎn)生的額外鎖存器的延遲時(shí)間，可以隱藏鎖存器產(chǎn)生的額外開銷開銷表表3.9 R40003.9 R4000浮點(diǎn)流水線中浮點(diǎn)流水線中8 8個(gè)流水段個(gè)流水段流水段流水段功能部件功能部件描述描述A A浮點(diǎn)加法器浮點(diǎn)加法器尾數(shù)加尾數(shù)加D D浮點(diǎn)除法器浮點(diǎn)除法器除法除法E E浮點(diǎn)乘法器浮點(diǎn)乘法器例外測(cè)試?yán)鉁y(cè)試MM浮點(diǎn)乘法

16、器浮點(diǎn)乘法器乘法第一階段乘法第一階段N N浮點(diǎn)乘法器浮點(diǎn)乘法器乘法第二階段乘法第二階段R R浮點(diǎn)加法器浮點(diǎn)加法器舍入舍入S S浮點(diǎn)加法器浮點(diǎn)加法器操作數(shù)移位操作數(shù)移位U U展開浮點(diǎn)數(shù)展開浮點(diǎn)數(shù)表表3.10 3.10 雙精度浮點(diǎn)操作指令延遲、初雙精度浮點(diǎn)操作指令延遲、初始化間隔和流水段的使用情況始化間隔和流水段的使用情況浮點(diǎn)指令浮點(diǎn)指令延遲延遲初始化間隔初始化間隔使用的流水段使用的流水段加、減加、減43U,S+A,A+R,R+S乘乘84U,E+M,M,M,M,N,N+A,R除除3635U,A,R,D28,D+A,D+R,D+A,D+R,A,R求平方根求平方根112111U,E,(A+R)108,A,R取反取反21U,S求絕對(duì)值求絕對(duì)值21U,S浮點(diǎn)比較浮點(diǎn)比較32U,A,R表表3.11 3.11 暫停對(duì)暫停對(duì)R4000R4000流水線流水線CPICPI的影響的影響整數(shù)平均：整數(shù)平均：流水線流水線CPICPI 1.54 1.54 載入暫停時(shí)鐘周期數(shù)