計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)05標(biāo)量處理機(jī)121105

1、1 第第5 5章章 標(biāo)量處理機(jī)標(biāo)量處理機(jī) 5.1 5.1 流水線技術(shù)流水線技術(shù) 5.2 5.2 相關(guān)性分析相關(guān)性分析 5.3 5.3 動(dòng)態(tài)調(diào)度技術(shù)動(dòng)態(tài)調(diào)度技術(shù) 5.4 5.4 超標(biāo)量處理機(jī)超標(biāo)量處理機(jī) 5.5 5.5 超流水處理機(jī)超流水處理機(jī) 5.6 5.6 超標(biāo)量超流水處理機(jī)超標(biāo)量超流水處理機(jī) 習(xí)題習(xí)題: :3 3、5 5、6 6、7 7、8 8、1515、1616 2 5.1 流水線技術(shù)流水線技術(shù) 空間并行性：空間并行性：設(shè)置多個(gè)獨(dú)立的操作部件設(shè)置多個(gè)獨(dú)立的操作部件 時(shí)間并行性：時(shí)間并行性：分時(shí)使用同一個(gè)部件的不同部分分時(shí)使用同一個(gè)部件的不同部分 5.1.1 指令的重疊執(zhí)行指令的重疊執(zhí)行

2、5.1.2 流水線工作原理流水線工作原理 5.1.3 流水線的性能分析流水線的性能分析 5.1.4 非線性流水線調(diào)度非線性流水線調(diào)度 3 5.1.1 指令的重疊執(zhí)行指令的重疊執(zhí)行 1、順序執(zhí)行方式。、順序執(zhí)行方式。 執(zhí)行執(zhí)行n條指令所用的時(shí)間為：條指令所用的時(shí)間為： 如果每段的時(shí)間都為如果每段的時(shí)間都為t，則執(zhí)行，則執(zhí)行n條指令所用的時(shí)間為：條指令所用的時(shí)間為： T=3 n t 主要優(yōu)點(diǎn)主要優(yōu)點(diǎn):控制簡單，節(jié)省設(shè)備?？刂坪唵危?jié)省設(shè)備。 主要缺點(diǎn)主要缺點(diǎn):速度慢速度慢,功能部件的利用率很低。功能部件的利用率很低。 取取 指指 令令k k 分分 析析k k 執(zhí)執(zhí) 行行k k 取取 指指 令令k

3、k+ +1 1 分分 析析k k+ +1 1 執(zhí)執(zhí) 行行k k+ +1 1 Ttttiii i n ( 取指令分析執(zhí)行） 1 4 2、一次重疊執(zhí)行方式、一次重疊執(zhí)行方式。 如果兩個(gè)過程的時(shí)間均相等，則執(zhí)行如果兩個(gè)過程的時(shí)間均相等，則執(zhí)行n條指令所條指令所 用的時(shí)間為：用的時(shí)間為： T(12n）t 主要優(yōu)點(diǎn)：主要優(yōu)點(diǎn)： 一是指令的執(zhí)行時(shí)間縮短，二是功能部件的一是指令的執(zhí)行時(shí)間縮短，二是功能部件的 利用利用率率明顯提高。明顯提高。 主要缺點(diǎn)：主要缺點(diǎn)： 需要增加一些硬件，控制過程也要復(fù)雜一些需要增加一些硬件，控制過程也要復(fù)雜一些 取指令取指令 k k分析分析 k k執(zhí)行執(zhí)行 k k 取取指指令令

4、k k+ +1 1分析分析 k+1k+1執(zhí)行執(zhí)行 k+1k+1 取指令取指令 k+2k+2 分析分析 k+2k+2執(zhí)行執(zhí)行 k+2k+2 5 3、二次重疊執(zhí)行方式、二次重疊執(zhí)行方式 如果執(zhí)行三如果執(zhí)行三個(gè)個(gè)過程的時(shí)間相等，則執(zhí)行過程的時(shí)間相等，則執(zhí)行n條指令所用的時(shí)條指令所用的時(shí) 間為：間為： T(2n）t 在理想情況下，處理機(jī)中同時(shí)有三條指令在執(zhí)行。在理想情況下，處理機(jī)中同時(shí)有三條指令在執(zhí)行。 處理機(jī)的結(jié)構(gòu)要比較大的改變，需要采用流水線技術(shù)處理機(jī)的結(jié)構(gòu)要比較大的改變，需要采用流水線技術(shù) 和緩存技術(shù)。和緩存技術(shù)。 取指令取指令 k k分析分析 k k執(zhí)行執(zhí)行 k k 取指令取指令 k+1k+1

5、分析分析 k+1k+1執(zhí)行執(zhí)行 k+1k+1 取指令取指令 k+2k+2分析分析 k+2k+2執(zhí)行執(zhí)行 k+2k+2 二次重疊執(zhí)行方式二次重疊執(zhí)行方式 6 5.1.2 流水線工作原理流水線工作原理 1.流水線寄存器流水線寄存器 流水線的每一個(gè)階段稱為流水線的每一個(gè)階段稱為流水步流水步、流水、流水 步驟、流水段、流水線階段、流水功能、步驟、流水段、流水線階段、流水功能、功功 能段、流水級(jí)能段、流水級(jí)、流水節(jié)拍等。、流水節(jié)拍等。 在每一個(gè)流水段的末斷或開頭必須設(shè)置在每一個(gè)流水段的末斷或開頭必須設(shè)置 一個(gè)寄存器，稱為一個(gè)寄存器，稱為流水線寄存器、流水鎖存流水線寄存器、流水鎖存 存器、流水寄存器等。存

6、器、流水寄存器等。 加入流水線寄存器，會(huì)增加指令執(zhí)行時(shí)間。加入流水線寄存器，會(huì)增加指令執(zhí)行時(shí)間。 在一般流水線時(shí)空?qǐng)D中不畫出流水線寄存在一般流水線時(shí)空?qǐng)D中不畫出流水線寄存 器。器。 7 2.一種指令流水線一種指令流水線 一般一般4至至20個(gè)流水段，大于等于個(gè)流水段，大于等于8個(gè)流水段稱個(gè)流水段稱 為為超流水線超流水線。 3.流水線時(shí)空?qǐng)D流水線時(shí)空?qǐng)D 輸入輸入 輸出輸出 取指令取指令 i 分析分析 i 執(zhí)行執(zhí)行 i 流水線流水線 寄存器寄存器 流水線流水線 寄存器寄存器 t 空間空間 執(zhí)行部件執(zhí)行部件 執(zhí)行執(zhí)行 k k 執(zhí)行執(zhí)行 k+1k+1 執(zhí)行執(zhí)行 k+2k+2 執(zhí)行執(zhí)行 k+3k+3 分析

7、分析部件部件 分析分析 k k 分析分析 k+1k+1 分析分析 k+2k+2 分析分析 k+3k+3 取指令部件取指令部件 取指令取指令 k k 取指令取指令 k+1k+1 取指令取指令 k+2k+2 取指令取指令 k+3k+3 0 t1 t2 t3 t4 t5 時(shí)間時(shí)間 8 一個(gè)浮點(diǎn)加法器流水線的一個(gè)浮點(diǎn)加法器流水線的時(shí)空?qǐng)D例時(shí)空?qǐng)D例 空空間間 規(guī)規(guī)格格化化 規(guī)規(guī)格格化化1 1 規(guī)規(guī)格格化化2 2 規(guī)規(guī)格格化化3 3 規(guī)規(guī)格格化化4 4 規(guī)規(guī)格格化化5 5 尾尾數(shù)數(shù)加加 尾尾數(shù)數(shù)加加1 1 尾尾數(shù)數(shù)加加2 2 尾尾數(shù)數(shù)加加3 3 尾尾數(shù)數(shù)加加4 4 尾尾數(shù)數(shù)加加5 5 對(duì)對(duì) 階階 對(duì)對(duì)階階

8、1 1 對(duì)對(duì)階階2 2 對(duì)對(duì)階階3 3 對(duì)對(duì)階階4 4 對(duì)對(duì)階階5 5 求求階階差差 求求階階差差1 1 求求階階差差2 2 求求階階差差3 3 求求階階差差4 4 求求階階差差5 5 0 t1 t2 t3 t4 t5 t6 t7 t8 時(shí)時(shí)間間 9 4.流水線的主要特點(diǎn)：流水線的主要特點(diǎn)： （1）只有連續(xù)提供同類任務(wù)才能發(fā)揮流水線效只有連續(xù)提供同類任務(wù)才能發(fā)揮流水線效 率率，盡量減少因條件分支造成的，盡量減少因條件分支造成的“斷流斷流”，通，通 過編譯技術(shù)提供連續(xù)的相同類型操作。過編譯技術(shù)提供連續(xù)的相同類型操作。 （2）每個(gè)流水段都要設(shè)置一個(gè)流水寄存器每個(gè)流水段都要設(shè)置一個(gè)流水寄存器，增，增

9、 加時(shí)間開銷：流水線的執(zhí)行時(shí)間加長；增加硬加時(shí)間開銷：流水線的執(zhí)行時(shí)間加長；增加硬 件開銷：每段需要增加一個(gè)寄存器。件開銷：每段需要增加一個(gè)寄存器。 （3）各流水段的時(shí)間應(yīng)盡量相等各流水段的時(shí)間應(yīng)盡量相等，流水線處理，流水線處理 機(jī)的基本時(shí)鐘周期等于時(shí)間最長的流水段的時(shí)機(jī)的基本時(shí)鐘周期等于時(shí)間最長的流水段的時(shí) 間長度。間長度。 （4）流水線需要有流水線需要有“裝入時(shí)間裝入時(shí)間”和和“排空時(shí)排空時(shí) 間間”。 10 5.1.3 流水線的性能分析流水線的性能分析 主要指標(biāo)：主要指標(biāo)：吞吐率、加速比和效率吞吐率、加速比和效率 1.吞吐率吞吐率(Thought put) 流水線吞吐率的最基本公式：流水線

10、吞吐率的最基本公式： 其中：其中：n為任務(wù)數(shù)，為任務(wù)數(shù)，Tk為完成為完成n個(gè)任務(wù)所個(gè)任務(wù)所 用時(shí)間。各段執(zhí)行時(shí)間相等，輸入連續(xù)任務(wù)用時(shí)間。各段執(zhí)行時(shí)間相等，輸入連續(xù)任務(wù) 情況下，完成情況下，完成n個(gè)任務(wù)需要的總的時(shí)間為：個(gè)任務(wù)需要的總的時(shí)間為： 其中：其中：k為流水線的段數(shù)，為流水線的段數(shù)， 為時(shí)鐘周期。為時(shí)鐘周期。 k T n Tp tnkT k )1( t 11 吞吐率為：吞吐率為： 最大吞吐率為最大吞吐率為： tnktntkTk) 1() 1( tnk n Tp )1( ttnk n Tp n 1 )1( lim max 空間空間 S4123n-1n S3123n-1n S2123n-1

11、n S11 12 23 3n-1n-1n n時(shí)間時(shí)間 kt(n1)t nt(k1)t T 12 各段時(shí)間不等，完成各段時(shí)間不等，完成n個(gè)連續(xù)任務(wù)：個(gè)連續(xù)任務(wù)： 吞吐率吞吐率： 最大吞吐率最大吞吐率： 流水線個(gè)段執(zhí)行時(shí)間不相等的解決辦法：流水線個(gè)段執(zhí)行時(shí)間不相等的解決辦法： ),max()1( 21 1 k k i i tttnt n Tp ),max( 1 21k ttt Tp s s1 1s s3 3s s4 4s s2 2 t t1 1= = t t t t2 2= 3= 3t t t t3 3= = t t t t4 4= = t t 輸出輸出輸入輸入 13 (1)將將“瓶頸瓶頸”部分再

12、細(xì)分部分再細(xì)分(如果可分的話）如果可分的話） 輸輸入入 S1S2-1S2-2S2-3S3S4 輸輸出出 t t t t t t “瓶瓶頸頸”流流水水段段再再次次細(xì)細(xì)分分 S2 (3 t) 空空間間 S4123n S3123n S2123n S1123n時(shí)時(shí)間間 k i it 1 （n1） t2 Tk 各段執(zhí)行時(shí)間不相等的流水線及其時(shí)空?qǐng)D 14 (2)“瓶頸瓶頸”流水段重復(fù)設(shè)置流水段重復(fù)設(shè)置：增加分配器和收集器：增加分配器和收集器 15 2.加速比加速比(Speedup) 計(jì)算加速比的基本公式：計(jì)算加速比的基本公式： 各段執(zhí)行時(shí)間相等，輸入連續(xù)任務(wù)情況下，各段執(zhí)行時(shí)間相等，輸入連續(xù)任務(wù)情況下，

13、加速比：加速比： 最大加速比：最大加速比： 各段時(shí)間不等，輸入連續(xù)任務(wù)情況下，實(shí)際加速各段時(shí)間不等，輸入連續(xù)任務(wù)情況下，實(shí)際加速 比為：比為： S T Tk 順序執(zhí)行時(shí)間 流水線執(zhí)行時(shí)間 0 S k nt knt k n kn () 11 SLim k n kn k n max 1 S nt tnttt i i k i i k k 1 1 121() m ax(,） 16 當(dāng)流水線段數(shù)增加時(shí)，需要連續(xù)輸入的任務(wù)也必當(dāng)流水線段數(shù)增加時(shí)，需要連續(xù)輸入的任務(wù)也必 須增加。須增加。 加速比加速比 S 10 加加 k=10 段段 8 速速 6 比比 k=6 段段 4 2 1 1 2 4 8 16 32

14、64 128 n 任任 務(wù)務(wù) 個(gè)個(gè) 數(shù)數(shù) 17 3.效率效率(Efficiency) 計(jì)算流水線效率的一般公式：計(jì)算流水線效率的一般公式： 各流水段時(shí)間相等，輸入各流水段時(shí)間相等，輸入n個(gè)連續(xù)任務(wù)，流水線個(gè)連續(xù)任務(wù)，流水線 的效率為：的效率為： 最高效率最高效率為：為： 各流水段時(shí)間不等，輸入各流水段時(shí)間不等，輸入n個(gè)連續(xù)任務(wù)，流水線個(gè)連續(xù)任務(wù)，流水線 效率為：效率為： E n k T k Tk 個(gè)任務(wù)占用的時(shí)空區(qū) 個(gè)流水段的總的時(shí)空區(qū) 0 E k nt kknt n kn () 11 ELim n kn n max 1 1 E nt ktnttt i i k i i k k 1 1 121)

15、m a x (,)（ 18 各段設(shè)備量或價(jià)格不等時(shí)，流水線的效率為：各段設(shè)備量或價(jià)格不等時(shí)，流水線的效率為： 即：即： 其中其中, ，aik，且k。 流水線的吞吐率、加速比與效率的關(guān)系：流水線的吞吐率、加速比與效率的關(guān)系： 因?yàn)橐驗(yàn)?因此：因此： tnk n Tp )1( 1 nk nk S 1 nk n E EkStTPE, 空區(qū)個(gè)流水段的總的加權(quán)時(shí) 區(qū)個(gè)任務(wù)占用的加權(quán)時(shí)空 k n E ), ,max()121 11 1 n k i ii ki I i k i ii tttntaa tan E （ 19 4.流水線性能分析舉例流水線性能分析舉例 對(duì)于輸入連續(xù)任務(wù)的情況，通過上面對(duì)于輸入連續(xù)任

16、務(wù)的情況，通過上面 給出的公式很容易計(jì)算出流水線的吞吐給出的公式很容易計(jì)算出流水線的吞吐 率、加速比和效率。率、加速比和效率。 對(duì)于輸入不連續(xù)任務(wù)等情況，通常采對(duì)于輸入不連續(xù)任務(wù)等情況，通常采 用基本公式計(jì)算。用基本公式計(jì)算。 例：例：用一條用一條4段浮點(diǎn)加法器流水線求段浮點(diǎn)加法器流水線求8個(gè)浮個(gè)浮 點(diǎn)數(shù)的和：點(diǎn)數(shù)的和：Z=A+B+C+D+E+F+G+H 20 解解：Z=(A+B)+(C+D)+(E+F)+(G+H) 空空 間間 周周 期期 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 1 10 0 1 11 1 1 12 2 1 13 3 1 14 4 1 15 5

17、 規(guī)規(guī) 格格 化化 1 1 2 2 3 3 4 4 5 5 6 6 7 7 尾尾 數(shù)數(shù) 加加 1 1 2 2 3 3 4 4 5 5 6 6 7 7 對(duì)對(duì) 階階 1 1 2 2 3 3 4 4 5 5 6 6 7 7 求求 階階 差差 1 1 2 2 3 3 4 4 5 5 6 6 7 7 時(shí)時(shí) 間間 加加 數(shù)數(shù) A A C C E E G G A A+ +B B E E+ +F F A A+ +B B+ +C C+ +D D 加加 數(shù)數(shù) B B D D F F H H C C+ +D D G G+ +H H E E+ +F F+ +G G+ +H H 結(jié)結(jié) 果果 A A+ +B B C C+

18、 +D D E E+ +F F g g+ +H H A A+ +B B+ +C C+ +D D Z Z E E+ +F F+ +G G+ +H H 用用 一一 條條4 4段段 浮浮 點(diǎn)點(diǎn) 加加 法法 器器 流流 水水 線線 求求8 8個(gè)個(gè) 數(shù)數(shù) 之之 和和 的的 流流 水水 線線 時(shí)時(shí) 空空 圖圖 21 解： 7個(gè)浮點(diǎn)加法共用了15個(gè)時(shí)鐘周期。 流水線的流水線的吞吐率吞吐率為：為： 流水線的流水線的加速比加速比為：為： 流水線的流水線的效率效率為為： ttT n Tp k 1 47.0 15 7 87.1 15 74 0 t t T T S k 47.0 154 74 0 t t Tk T E

19、 k 22 5.1.4 非線性流水線調(diào)度非線性流水線調(diào)度 1.線性流水線與非線性流水線線性流水線與非線性流水線 流水線的各個(gè)流水段之間是否有反反饋信號(hào)流水線的各個(gè)流水段之間是否有反反饋信號(hào) 線性流水線線性流水線(Linear Pipelining): 每個(gè)流水段都流過一次，而且僅流過一次線性每個(gè)流水段都流過一次，而且僅流過一次線性 流水線能夠用流水線連接圖唯一表示流水線能夠用流水線連接圖唯一表示 非線性流水線非線性流水線(Nonliner Pipelining): 某些流水段之間有反饋回路或前饋回路。非某些流水段之間有反饋回路或前饋回路。非 線性流水線必須用流水線連接圖和流水線預(yù)約表線性流水線

20、必須用流水線連接圖和流水線預(yù)約表 共同表示。共同表示。 23 非線性流水線調(diào)度的任務(wù)：非線性流水線調(diào)度的任務(wù)： 找出一個(gè)最小的啟動(dòng)循環(huán)周期，按照這周期流水找出一個(gè)最小的啟動(dòng)循環(huán)周期，按照這周期流水 線輸入新任務(wù)，流水線的各個(gè)功能段不會(huì)發(fā)生沖線輸入新任務(wù)，流水線的各個(gè)功能段不會(huì)發(fā)生沖 突，而且流水線的吞吐率和效率最高。突，而且流水線的吞吐率和效率最高。 前前饋饋回回路路 輸輸入入S S1 1S S2 2S S3 3 輸輸出出 反反饋饋回回路路 一一種種簡簡單單的的非非線線性性流流水水線線 24 非線性流水線的連接圖和預(yù)約表非線性流水線的連接圖和預(yù)約表 輸輸出出 輸輸入入 S1S2S3S4 前饋線

21、 反饋線 時(shí)時(shí)間間 功功能能段段 1234567 S1 S2 S3 S4 25 一張預(yù)約表可能與多個(gè)流水線連接土相對(duì)應(yīng)：一張預(yù)約表可能與多個(gè)流水線連接土相對(duì)應(yīng)： 時(shí)時(shí) 間間 功功 能能 段段 1 2 3 4 5 6 7 S1 S2 S3 S4 輸輸出出 S4 輸輸入入S1S2S3 前前饋饋線線 反反饋饋線線 26 一個(gè)流水線連接圖對(duì)應(yīng)與多張預(yù)約表：一個(gè)流水線連接圖對(duì)應(yīng)與多張預(yù)約表： 2.非線性流水線的沖突非線性流水線的沖突 啟動(dòng)距離：連續(xù)輸入兩個(gè)任務(wù)之間的時(shí)間間隔。啟動(dòng)距離：連續(xù)輸入兩個(gè)任務(wù)之間的時(shí)間間隔。 流水線沖突：幾個(gè)任務(wù)爭同一個(gè)流水段。流水線沖突：幾個(gè)任務(wù)爭同一個(gè)流水段。 時(shí)時(shí)間間 功

22、功能能段段 1 2 3 4 5 6 7 S1 S2 S3 S4 時(shí)時(shí)間間 功功能能段段 1 1 2 2 3 3 4 4 5 5 6 6 7 7 S1 S2 S3 S4 27 28 啟啟動(dòng)動(dòng)距距離離為為 5 5 時(shí)時(shí)的的流流水水線線不不沖沖突突 時(shí)時(shí)間間 功功能能段段 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 1 10 0 1 11 1 S S1 1 X X1 1 X X1 1 X X2 2 X X1 1 X X2 2 X X3 3 S S2 2 X X1 1 X X1 1 X X2 2 X X2 2 S S3 3 X X1 1 X X1 1 X X2 2 X X2

23、 2 S S4 4 X X1 1 X X2 2 啟啟動(dòng)動(dòng)周周期期 重重復(fù)復(fù)啟啟動(dòng)動(dòng)周周期期 啟啟動(dòng)動(dòng)距距離離為為( (1 1, ,7 7) )循循環(huán)環(huán)時(shí)時(shí)的的流流水水線線預(yù)預(yù)約約表表 時(shí)時(shí)間間 功功能能段段 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 1 10 0 1 11 1 1 12 2 1 13 3 1 14 4 1 15 5 1 16 6 S S1 1 X X1 1 X X2 2 X X1 1 X X2 2 X X1 1 X X2 2 X X3 3 X X4 4 X X3 3 X X4 4 X X3 3 X X4 4 S S2 2 X X1 1 X X2 2

24、 X X1 1 X X2 2 X X3 3 X X4 4 X X3 3 X X4 4 S S3 3 X X1 1 X X2 2 X X1 1 X X2 2 X X3 3 X X4 4 X X3 3 X X4 4 S S4 4 X X1 1 X X2 2 X X3 3 X X4 4 啟啟動(dòng)動(dòng)周周期期 重重復(fù)復(fù)啟啟動(dòng)動(dòng)周周期期 29 3.無沖突調(diào)度方法無沖突調(diào)度方法 由由E.S.Davidson及學(xué)生于及學(xué)生于1971年提出年提出 例：一條例：一條4功能段的非線性流水線，每個(gè)功能的延遲功能段的非線性流水線，每個(gè)功能的延遲 時(shí)間都相等，它的預(yù)約表如下：時(shí)間都相等，它的預(yù)約表如下： (1)寫出流水線的

25、禁止向量和初始沖突向量。寫出流水線的禁止向量和初始沖突向量。 (2)畫出調(diào)度流水線的狀態(tài)圖。畫出調(diào)度流水線的狀態(tài)圖。 (3)求最小啟動(dòng)循環(huán)和最小平均啟動(dòng)距離。求最小啟動(dòng)循環(huán)和最小平均啟動(dòng)距離。 (4)求平均啟動(dòng)距離最小的恒定循環(huán)。求平均啟動(dòng)距離最小的恒定循環(huán)。 時(shí) 間 功能段 1 2 3 4 5 6 7 S1 X X S2 X X S3 X X S4 X 30 解解: (1)禁止向量禁止向量：預(yù)約表中每一行任意兩個(gè)：預(yù)約表中每一行任意兩個(gè)“X”之之 間距離集合。本例中為間距離集合。本例中為(2,4,6). (2)沖突向量沖突向量：C=(CmCjC2C1) 其中：其中：m是禁止向量中的最大值。如

26、果是禁止向量中的最大值。如果j在禁止在禁止 向量中，則向量中，則Cj=1,否則否則Cj =0. 本例中本例中 C=(101010) (3)構(gòu)造狀態(tài)圖構(gòu)造狀態(tài)圖 S邏輯右移邏輯右移2、4、6位時(shí)，不作任何處理，位時(shí)，不作任何處理， 邏輯右移邏輯右移1、3、5和大于等于時(shí)：和大于等于時(shí)： S右移右移1位之后：位之后：010101V101010=111111 S右移右移3位之后：位之后：000101V101010=101111 S右移右移5位之后：位之后：000001V101010=101011 31 S右移右移7位或大于位或大于7位后：還原到本身位后：還原到本身 101111右移右移5位之后：位之

27、后：000001V101010=101011 101011右移右移3位之后：位之后：000101V101010=101111 101011右移右移5位之后：位之后：000001V101010=101011 32 簡單循環(huán)：簡單循環(huán)：狀態(tài)圖中各種沖突向量只經(jīng)過一次啟動(dòng)循狀態(tài)圖中各種沖突向量只經(jīng)過一次啟動(dòng)循 環(huán)。環(huán)。 (2)最小的啟動(dòng)循環(huán)最小的啟動(dòng)循環(huán)為為(1,7)和（和（3，5）,平均距離為平均距離為4。 (5)啟動(dòng)距離最小的恒定循環(huán)為啟動(dòng)距離最小的恒定循環(huán)為(5) 簡簡 單單 循循 環(huán)環(huán)平平 均均 啟啟 動(dòng)動(dòng) 距距 離離 （ 1 1， 7 7）4 4 （ 3 3， 7 7）5 5 （ 5 5，

28、 7 7）6 6 （ 3 3， 5 5， 7 7）5 5 （ 5 5， 3 3， 7 7）5 5 （ 3 3， 5 5）4 4 （ 5 5）5 5 （ 7 7）7 7 33 最最小小啟啟動(dòng)動(dòng)循循環(huán)環(huán)( (3 3, ,5 5) )的的流流水水線線工工作作狀狀態(tài)態(tài) 時(shí)時(shí)間間 功功能能段段 1 12 23 34 45 56 67 78 89 91 10 0 1 11 1 1 12 2 1 13 3 1 14 4 1 15 5 S S1 1X X1 1X X2 2X X1 1X X3 3X X2 2X X4 4X X3 3 S S2 2X X1 1X X2 2X X1 1X X2 2X X3 3X X

29、4 4X X3 3 S S3 3X X1 1X X1 1X X2 2X X2 2X X3 3X X3 3X X4 4 S S4 4X X1 1X X2 2X X3 3X X4 4 啟啟動(dòng)動(dòng)周周期期重重復(fù)復(fù)啟啟動(dòng)動(dòng)周周期期 最最小小啟啟動(dòng)動(dòng)循循環(huán)環(huán)( (1 1, ,7 7) )的的流流水水線線工工作作狀狀態(tài)態(tài) 時(shí)時(shí)間間 功功能能段段 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 1 10 0 1 11 1 1 12 2 1 13 3 1 14 4 1 15 5 S S1 1 X X1 1 X X2 2 X X1 1 X X2 2 X X3 3 X X4 4 X X3 3

30、 S S2 2 X X1 1 X X2 2 X X1 1 X X2 2 X X3 3 X X4 4 X X3 3 X X4 4 S S3 3 X X1 1 X X2 2 X X1 1 X X2 2 X X3 3 X X4 4 X X3 3 X X4 4 S S4 4 X X1 1 X X2 2 X X3 3 X X4 4 啟啟動(dòng)動(dòng)周周期期 重重復(fù)復(fù)啟啟動(dòng)動(dòng)周周期期 34 恒恒定定啟啟動(dòng)動(dòng)循循環(huán)環(huán)( (5 5) )的的流流水水線線工工作作狀狀態(tài)態(tài) 時(shí)時(shí)間間 功功能能段段 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 1 10 0 1 11 1 1 12 2 1 13 3

31、 1 14 4 1 15 5 S S1 1 X X1 1 X X2 2 X X1 1 X X3 3 X X2 2 S S2 2 X X1 1 X X1 1 X X2 2 X X2 2 X X3 3 S S3 3 X X1 1 X X1 1 X X2 2 X X2 2 X X3 3 X X3 3 S S4 4 X X1 1 X X2 2 X X3 3 啟啟動(dòng)動(dòng)周周期期 重重復(fù)復(fù)啟啟動(dòng)動(dòng)周周期期 35 4.優(yōu)化調(diào)度方法優(yōu)化調(diào)度方法 L.E.Shar于于1972年提出流水線最小平均啟動(dòng)年提出流水線最小平均啟動(dòng) 距離的限制范圍：距離的限制范圍： (1)最小平均啟動(dòng)距離的下限是預(yù)約表中任意一行里最小平均

32、啟動(dòng)距離的下限是預(yù)約表中任意一行里 “X”的最多個(gè)數(shù)。的最多個(gè)數(shù)。 (2)最小平均距離小于等于狀態(tài)圖中任意一個(gè)簡單循最小平均距離小于等于狀態(tài)圖中任意一個(gè)簡單循 環(huán)的平均啟動(dòng)距離。環(huán)的平均啟動(dòng)距離。 (3)最小平均啟動(dòng)距離的上限是沖突向量中最小平均啟動(dòng)距離的上限是沖突向量中1的個(gè)數(shù)的個(gè)數(shù) 再加上再加上1。 注注:A、1992年，年， L.E.Shar又證明了上述限制范圍。又證明了上述限制范圍。 B、最有用的是第一條。預(yù)約表中、最有用的是第一條。預(yù)約表中“X”最多的行最多的行 一定是一定是瓶頸流水段。瓶頸流水段。 36 對(duì)于上例的預(yù)約表，在同一行中對(duì)于上例的預(yù)約表，在同一行中“X”最多的最多的 為

33、為2個(gè)，因此，個(gè)，因此，最小平均距離可以達(dá)到最小平均距離可以達(dá)到2。 最小啟動(dòng)循環(huán)可以是最小啟動(dòng)循環(huán)可以是(2)、(1,3)、(1,1,4)、 (1,2,3).?，F(xiàn)取恒定循環(huán)。現(xiàn)取恒定循環(huán)(2)。 每一行中與第每一行中與第1個(gè)個(gè)“X”的距離為的距離為2的倍數(shù)的位的倍數(shù)的位 置都要預(yù)留出來。置都要預(yù)留出來。 S3行的第行的第2個(gè)個(gè)“X”從周期延遲到周期從周期延遲到周期6。為此，。為此， S2行的第行的第2個(gè)個(gè)“X”從周期延遲到周期從周期延遲到周期7； S1行的第行的第2個(gè)個(gè)“X”從周期延遲到周期從周期延遲到周期8。 實(shí)際上，只要在流水線段實(shí)際上，只要在流水線段S4的輸出端到流水的輸出端到流水S3

34、 的輸入端中間插入一個(gè)的輸入端中間插入一個(gè)非計(jì)算延遲非計(jì)算延遲D1。 37 采采用用預(yù)預(yù)留留調(diào)調(diào)度度算算法法的的預(yù)預(yù)約約表表 時(shí)時(shí) 間間12345678 S1 S2 S3 功功 能能 段段 S4 延延遲遲 D1 注注：表表示示由由D D1 1延延遲遲一一個(gè)個(gè)時(shí)時(shí)鐘鐘周周期期 38 有有 非非 計(jì)計(jì) 算算 延延 遲遲 的的 流流 水水 線線 狀狀 態(tài)態(tài) 圖圖 8 8* * 0 0 0 0 8 8* * 8 8* *1 1 2 2 4 4 6 6 8 8* * 0 0 0 0 0 0 1 1 2 2 4 4 6 6 39 在非線性流水線中，在非線性流水線中，“X”最多的流水段一最多的流水段一 定是

35、定是“瓶頸瓶頸”流水段。流水段。 實(shí)現(xiàn)最優(yōu)調(diào)度的目標(biāo)是使實(shí)現(xiàn)最優(yōu)調(diào)度的目標(biāo)是使“瓶頸瓶頸”流水段流水段 處于忙碌狀態(tài)，沒有空閑周期處于忙碌狀態(tài)，沒有空閑周期。 最優(yōu)調(diào)度方法能夠使非線性流水的吞吐率，最優(yōu)調(diào)度方法能夠使非線性流水的吞吐率， 加速比和效率達(dá)到最優(yōu)。加速比和效率達(dá)到最優(yōu)。 按按照照最最小小啟啟動(dòng)動(dòng)循循環(huán)環(huán)（2 2）工工作作的的流流水水線線預(yù)預(yù)約約表表 時(shí)時(shí)間間 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 1 10 0 1 11 1 1 12 2 功功 S S1 1 X X1 1 X X2 2 X X3 3 X X4 4 X X1 1 X X5 5 X X2

36、 2 X X6 6 X X3 3 能能 S S2 2 X X1 1 X X2 2 X X3 3 X X1 1 X X4 4 X X2 2 X X5 5 X X3 3 X X6 6 段段 S S3 3 X X1 1 X X2 2 X X1 1 X X3 3 X X2 2 X X4 4 X X3 3 X X5 5 X X4 4 S S4 4 X X1 1 X X2 2 X X3 3 X X4 4 X X5 5 延延 D D1 1 X X1 1 X X2 2 X X3 3 X X4 4 40 5.2 相關(guān)性分析技術(shù)相關(guān)性分析技術(shù) 5.2.1 數(shù)據(jù)相關(guān)數(shù)據(jù)相關(guān) 5.2.2 控制相關(guān)控制相關(guān) 5.2.3

37、 條件分支對(duì)流水線的影響條件分支對(duì)流水線的影響 5.2.4 靜態(tài)分支預(yù)測(cè)技術(shù)靜態(tài)分支預(yù)測(cè)技術(shù) 5.2.5 動(dòng)態(tài)分支預(yù)測(cè)技術(shù)動(dòng)態(tài)分支預(yù)測(cè)技術(shù) 5.2.6 精確斷點(diǎn)與不精確斷點(diǎn)精確斷點(diǎn)與不精確斷點(diǎn) 41 5.2.1 數(shù)據(jù)相關(guān)數(shù)據(jù)相關(guān) 數(shù)據(jù)相關(guān)：數(shù)據(jù)相關(guān)： 在執(zhí)行本條指令的過程中，如果用到的指在執(zhí)行本條指令的過程中，如果用到的指 令、操作數(shù)、變址量等是前面指令的執(zhí)行結(jié)果，令、操作數(shù)、變址量等是前面指令的執(zhí)行結(jié)果， 這種相關(guān)稱為數(shù)據(jù)相關(guān)。這種相關(guān)稱為數(shù)據(jù)相關(guān)。 控制相關(guān)：控制相關(guān)： 由條件分支指令、轉(zhuǎn)子程序指令、中斷等由條件分支指令、轉(zhuǎn)子程序指令、中斷等 引起的相關(guān)。引起的相關(guān)。 解決數(shù)據(jù)相關(guān)的方法有

38、兩種：解決數(shù)據(jù)相關(guān)的方法有兩種： 推后處理推后處理 設(shè)置專用路徑設(shè)置專用路徑。 42 1.指令相關(guān)指令相關(guān) 發(fā)生指令相關(guān)的情況：發(fā)生指令相關(guān)的情況： n: STORE R1，n+1 n+1:. 滿足關(guān)系：滿足關(guān)系：結(jié)果地址結(jié)果地址(n)=指令地址指令地址(n+1) 當(dāng)?shù)诋?dāng)?shù)趎條指令還沒有把執(zhí)行結(jié)果寫到主條指令還沒有把執(zhí)行結(jié)果寫到主 存之前，取出的第存之前，取出的第n+1指令顯然是錯(cuò)誤的。指令顯然是錯(cuò)誤的。 在第在第k個(gè)流水段的流水線處理機(jī)中，第個(gè)流水段的流水線處理機(jī)中，第 n條指令要修改從條指令要修改從n+1 到第到第n+k指令中任意指令中任意 一條指令，都可能造成程序執(zhí)行結(jié)果發(fā)生一條指令，都

39、可能造成程序執(zhí)行結(jié)果發(fā)生 錯(cuò)誤。錯(cuò)誤。 43 解決指令相關(guān)的根本辦法是：解決指令相關(guān)的根本辦法是： 在程序執(zhí)行過程中不允許修改指令。在程序執(zhí)行過程中不允許修改指令。 現(xiàn)代程序設(shè)計(jì)方法要求程序具有載入性，可以現(xiàn)代程序設(shè)計(jì)方法要求程序具有載入性，可以 被遞歸調(diào)用等，也要求不修改指令。被遞歸調(diào)用等，也要求不修改指令。 在在IBM370系列機(jī)中，用系列機(jī)中，用“執(zhí)行指令執(zhí)行指令”來解決：來解決： 在程序執(zhí)行過程中既能修改指令，程序又具有載入在程序執(zhí)行過程中既能修改指令，程序又具有載入 性。性。 “執(zhí)行指令執(zhí)行指令”執(zhí)行由第二地址執(zhí)行由第二地址(X2)+(B2)+D2) 決定的主存數(shù)據(jù)區(qū)中的指令。決定的

40、主存數(shù)據(jù)區(qū)中的指令。 44 2.通用寄存器數(shù)據(jù)相關(guān)通用寄存器數(shù)據(jù)相關(guān) 發(fā)生寄存器數(shù)據(jù)相關(guān)的可能性很大，影發(fā)生寄存器數(shù)據(jù)相關(guān)的可能性很大，影 響面也很大。響面也很大。 例如：例如： n:OP R1,A2 ;R1=(R1)OP（A2） n+1:OP R1,R2 ;R1=(R1)OP（R2） 發(fā)生發(fā)生R1(n)=R1(n+1)稱為稱為R1數(shù)據(jù)相關(guān)數(shù)據(jù)相關(guān)。 發(fā)生發(fā)生R1(n)=R2(n+1)稱為稱為R2數(shù)據(jù)相關(guān)數(shù)據(jù)相關(guān)。 解決通用寄存器數(shù)據(jù)相關(guān)的辦法：解決通用寄存器數(shù)據(jù)相關(guān)的辦法： 45 方法一方法一：把讀操作數(shù)、寫運(yùn)算結(jié)果與指令執(zhí)行把讀操作數(shù)、寫運(yùn)算結(jié)果與指令執(zhí)行 合在一個(gè)節(jié)拍。合在一個(gè)節(jié)拍。 從

41、數(shù)據(jù)從通用寄存器讀出，在運(yùn)算器中從數(shù)據(jù)從通用寄存器讀出，在運(yùn)算器中 完成運(yùn)算，結(jié)果寫回通用寄存器的整個(gè)回路完成運(yùn)算，結(jié)果寫回通用寄存器的整個(gè)回路 中，只有通用寄存器是時(shí)序邏輯。中，只有通用寄存器是時(shí)序邏輯。 當(dāng)發(fā)生下述情況時(shí)，不能采用這種方法：當(dāng)發(fā)生下述情況時(shí)，不能采用這種方法： (1) 當(dāng)寄存器個(gè)數(shù)多時(shí)，讀寫寄存器的時(shí)間當(dāng)寄存器個(gè)數(shù)多時(shí)，讀寫寄存器的時(shí)間 長。長。 (2)當(dāng)功能部件數(shù)量多時(shí)，寄存器的讀寫端當(dāng)功能部件數(shù)量多時(shí)，寄存器的讀寫端 口多?？诙唷?(3)當(dāng)功能部件的執(zhí)行時(shí)間比較長，或要求當(dāng)功能部件的執(zhí)行時(shí)間比較長，或要求 指令的執(zhí)行時(shí)間短時(shí)。指令的執(zhí)行時(shí)間短時(shí)。 46 方法二方法二：建

42、立相關(guān)專用通路建立相關(guān)專用通路(ByPass) 由于發(fā)生寄存器數(shù)據(jù)相關(guān)的情況很普遍，一般計(jì)由于發(fā)生寄存器數(shù)據(jù)相關(guān)的情況很普遍，一般計(jì) 算機(jī)系統(tǒng)都采用專用數(shù)據(jù)通路。算機(jī)系統(tǒng)都采用專用數(shù)據(jù)通路。 把讀通用寄存器、執(zhí)行操作和寫結(jié)果分為把讀通用寄存器、執(zhí)行操作和寫結(jié)果分為3個(gè)周個(gè)周 期，或期，或2個(gè)周期。個(gè)周期。 采用專用數(shù)據(jù)通路能夠縮短采用專用數(shù)據(jù)通路能夠縮短1至至2個(gè)周期。個(gè)周期。 通通用用寄寄存存器器堆堆 多多路路選選擇擇器器多多路路選選擇擇器器 運(yùn)運(yùn)算算器器 一一種種典典型型的的運(yùn)運(yùn)算算器器結(jié)結(jié)構(gòu)構(gòu) 通通用用寄寄存存器器堆堆 相相關(guān)關(guān)專專用用通通路路 鎖鎖存存器器鎖鎖存存器器 運(yùn)運(yùn)算算器器 設(shè)

43、設(shè)置置專專用用數(shù)數(shù)據(jù)據(jù)通通路路解解決決通通用用寄寄存存器器數(shù)數(shù)據(jù)據(jù)相相關(guān)關(guān) 47 變址相關(guān)：變址相關(guān)： 在采用變址尋址方式的處理機(jī)中，由在采用變址尋址方式的處理機(jī)中，由 于變址量放在寄存器中，因此，可能發(fā)生與于變址量放在寄存器中，因此，可能發(fā)生與 通用寄存器數(shù)據(jù)相關(guān)類似變址相關(guān)。通用寄存器數(shù)據(jù)相關(guān)類似變址相關(guān)。 3.LOAD相關(guān)相關(guān) LOAD操作的執(zhí)行時(shí)間可能比較長操作的執(zhí)行時(shí)間可能比較長 n: LOAD R1, A ;R1=(A) n+1: ADD R1, R2 ;R1=(R1)OP(R2) 如果如果R1(n)=R2(n+1),或或R1(n)=R1(n+1)，則發(fā)，則發(fā) 生生LOAD數(shù)據(jù)相關(guān)

44、。數(shù)據(jù)相關(guān)。 解決方法：解決方法： 48 方法一：方法一：由編譯器在由編譯器在LOAD之后插入不發(fā)生數(shù)據(jù)相之后插入不發(fā)生數(shù)據(jù)相 關(guān)的指令，由于關(guān)的指令，由于LOAD的執(zhí)行時(shí)間不確定，不能的執(zhí)行時(shí)間不確定，不能 根本解決問題。根本解決問題。 方法二：方法二：由硬件自動(dòng)插入空操作，直到由硬件自動(dòng)插入空操作，直到LOAD操作操作 完成。完成。 在單條流水線處理機(jī)中，也可以停止節(jié)拍發(fā)在單條流水線處理機(jī)中，也可以停止節(jié)拍發(fā) 生器生器 ，直到數(shù)據(jù)從存儲(chǔ)器中讀出為止。，直到數(shù)據(jù)從存儲(chǔ)器中讀出為止。 49 5.2.2 控制相關(guān) 因程序的執(zhí)行方向可能被改變而引起的相因程序的執(zhí)行方向可能被改變而引起的相 關(guān)，也稱

45、為關(guān)，也稱為全局相關(guān)全局相關(guān)。 主要包括：無條件轉(zhuǎn)移、一般條件轉(zhuǎn)移、主要包括：無條件轉(zhuǎn)移、一般條件轉(zhuǎn)移、 復(fù)合條件轉(zhuǎn)移、中斷等。復(fù)合條件轉(zhuǎn)移、中斷等。 1.無條件轉(zhuǎn)移無條件轉(zhuǎn)移 在流水線處理機(jī)中，無條件轉(zhuǎn)移指令不進(jìn)在流水線處理機(jī)中，無條件轉(zhuǎn)移指令不進(jìn) 入流水段，一般在指令譯碼階段就實(shí)際完成。入流水段，一般在指令譯碼階段就實(shí)際完成。 如果在處理機(jī)中設(shè)置有指令先行緩沖棧，如果在處理機(jī)中設(shè)置有指令先行緩沖棧， 則要全部或部分作廢先行指令緩沖棧中指令。則要全部或部分作廢先行指令緩沖棧中指令。 50 如果轉(zhuǎn)移目標(biāo)指令如果轉(zhuǎn)移目標(biāo)指令L不在先行指令緩沖不在先行指令緩沖 站中，站中，則要將先行指令緩沖棧中所

46、有指令全則要將先行指令緩沖棧中所有指令全 部作廢，并等待取出轉(zhuǎn)移目標(biāo)指令部作廢，并等待取出轉(zhuǎn)移目標(biāo)指令L。 如果轉(zhuǎn)移目標(biāo)指令如果轉(zhuǎn)移目標(biāo)指令L在先行指令緩沖棧在先行指令緩沖棧 中，中，只要作廢先行指令緩沖棧中的部分指令。只要作廢先行指令緩沖棧中的部分指令。 無條件轉(zhuǎn)移指令一般對(duì)指令執(zhí)行部件的無條件轉(zhuǎn)移指令一般對(duì)指令執(zhí)行部件的 工作不會(huì)造成影響。工作不會(huì)造成影響。 為進(jìn)一步減少無條件轉(zhuǎn)移指令造成的影為進(jìn)一步減少無條件轉(zhuǎn)移指令造成的影 響，響，在先行指令緩沖棧的入口處增設(shè)一個(gè)專在先行指令緩沖棧的入口處增設(shè)一個(gè)專 門處理無條件轉(zhuǎn)移指令的指令分析器。門處理無條件轉(zhuǎn)移指令的指令分析器。 51 2.一般條

47、件轉(zhuǎn)移一般條件轉(zhuǎn)移 k: ;設(shè)置條件碼設(shè)置條件碼CC k+1: JMP(CC)L ;如果如果CC為真轉(zhuǎn)向?yàn)檎孓D(zhuǎn)向L L: . 當(dāng)條件碼是上一條指令產(chǎn)生時(shí)，相關(guān)最嚴(yán)重。當(dāng)條件碼是上一條指令產(chǎn)生時(shí)，相關(guān)最嚴(yán)重。 52 無論轉(zhuǎn)移是否成功，條件轉(zhuǎn)移指令都在無論轉(zhuǎn)移是否成功，條件轉(zhuǎn)移指令都在 指令分析階段就已經(jīng)執(zhí)行完成。指令分析階段就已經(jīng)執(zhí)行完成。 無論轉(zhuǎn)移不成功或成功，指令分析器要無論轉(zhuǎn)移不成功或成功，指令分析器要 停頓一段時(shí)間，等待條件碼產(chǎn)生。停頓一段時(shí)間，等待條件碼產(chǎn)生。 53 如果轉(zhuǎn)移成功：指令如果轉(zhuǎn)移成功：指令L已經(jīng)在先行指令已經(jīng)在先行指令 緩沖棧，指令分析器接著緩沖棧，指令分析器接著“分析分

48、析L”,如果指如果指 令令L不在先行指令緩沖棧，指令分析器要等不在先行指令緩沖棧，指令分析器要等 待一個(gè)周期。待一個(gè)周期。 轉(zhuǎn)移不成功，對(duì)程序執(zhí)行影響不大，轉(zhuǎn)移不成功，對(duì)程序執(zhí)行影響不大， 當(dāng)轉(zhuǎn)移成功時(shí)，不僅指令執(zhí)行過程變成當(dāng)轉(zhuǎn)移成功時(shí)，不僅指令執(zhí)行過程變成 完全串行，而且要作廢先行指令緩沖棧中大完全串行，而且要作廢先行指令緩沖棧中大 量指令。量指令。 在采用流水線方式的處理機(jī)中，要通過在采用流水線方式的處理機(jī)中，要通過 軟件與硬件的多種手段來盡可能地降低轉(zhuǎn)移軟件與硬件的多種手段來盡可能地降低轉(zhuǎn)移 成功的概率，減少轉(zhuǎn)移成功造成影響。成功的概率，減少轉(zhuǎn)移成功造成影響。 54 5.2.3 條件分支

49、對(duì)流水線的影響條件分支對(duì)流水線的影響 處理好條件轉(zhuǎn)移和中斷的關(guān)鍵問題有兩個(gè)：處理好條件轉(zhuǎn)移和中斷的關(guān)鍵問題有兩個(gè)： 要確保流水線能夠正常工作要確保流水線能夠正常工作,減少因減少因“斷流斷流” 引起的吞吐率和效率的下降。引起的吞吐率和效率的下降。 1.條件分支在流水線中執(zhí)行過程條件分支在流水線中執(zhí)行過程 55 因?yàn)榈谝驗(yàn)榈趇條指令所需要的條件碼由條指令所需要的條件碼由i-1 條指令給出：在一條由條指令給出：在一條由k個(gè)功能段的流水個(gè)功能段的流水 線中，第線中，第i-1條指令要等到第條指令要等到第I+k-2條指令條指令 進(jìn)入流水線時(shí)才能形成條件碼。進(jìn)入流水線時(shí)才能形成條件碼。 轉(zhuǎn)移不成功轉(zhuǎn)移不成功

50、，猜測(cè)正確，流水線的，猜測(cè)正確，流水線的 吞吐率和效率沒有降低。吞吐率和效率沒有降低。 轉(zhuǎn)移成功轉(zhuǎn)移成功，猜測(cè)錯(cuò)誤，要先作廢流，猜測(cè)錯(cuò)誤，要先作廢流 水線中已經(jīng)執(zhí)行的水線中已經(jīng)執(zhí)行的i+1、i+2、.、i+k-2 指令；然后再從分支點(diǎn)開始執(zhí)行第指令；然后再從分支點(diǎn)開始執(zhí)行第P、 P+1、指令。一條指令。一條k段流水線有段流水線有k-2個(gè)功個(gè)功 能段是浪費(fèi)的。能段是浪費(fèi)的。 56 2.條件分支對(duì)流水線性能的影響條件分支對(duì)流水線性能的影響 假設(shè)條件轉(zhuǎn)移指令在一般程序中所占的比例為假設(shè)條件轉(zhuǎn)移指令在一般程序中所占的比例為p,轉(zhuǎn)移轉(zhuǎn)移 成功的概率為成功的概率為q。 N條指令的總的執(zhí)行時(shí)間是：條指令的總

51、的執(zhí)行時(shí)間是： TK-IF(n+k-1)t + npq(k-1)t 有條件轉(zhuǎn)移影響的流水線吞吐率為：有條件轉(zhuǎn)移影響的流水線吞吐率為： 有條件轉(zhuǎn)移影響的流水線最大吞吐率為：有條件轉(zhuǎn)移影響的流水線最大吞吐率為： TP n nktnpq kt IF （11)() tkpq )1(1 1 TPIFMAX （ 57 流水線吞吐率下降的百分比為： 在典型程序中，轉(zhuǎn)移指令占的比例為p=20%， 轉(zhuǎn)移成功概率為q=60%。 對(duì)于一條8功能段的指令流水線，由于條件轉(zhuǎn) 移指令的影響，流水線的最大吞吐率要下降： 如果指令流水線的功能段數(shù)為10，由于條件 轉(zhuǎn)移指令的影響，流水線的最大吞吐率將要下降 一半以下： ) 1

52、(1 ) 1( kpq kpq TP TPTP D MAX IFMAXMAX %46 ) 18(60. 020. 01 ) 18(60. 020. 0 8 D %53 ) 110(60. 020. 01 ) 110(60. 020. 0 D10 58 5.2.4 靜態(tài)分支預(yù)測(cè)技術(shù)靜態(tài)分支預(yù)測(cè)技術(shù) 靜態(tài)分支預(yù)測(cè)：靜態(tài)分支預(yù)測(cè)： 在程序執(zhí)行過程中轉(zhuǎn)移預(yù)測(cè)方向不能改變?cè)诔绦驁?zhí)行過程中轉(zhuǎn)移預(yù)測(cè)方向不能改變 動(dòng)態(tài)分支預(yù)測(cè)：動(dòng)態(tài)分支預(yù)測(cè)： 在程序執(zhí)行過程中能夠改變轉(zhuǎn)移預(yù)測(cè)方向在程序執(zhí)行過程中能夠改變轉(zhuǎn)移預(yù)測(cè)方向 本節(jié)講述靜態(tài)預(yù)測(cè)技術(shù)，下節(jié)講述動(dòng)態(tài)預(yù)測(cè)。本節(jié)講述靜態(tài)預(yù)測(cè)技術(shù)，下節(jié)講述動(dòng)態(tài)預(yù)測(cè)。 1.軟件軟件

53、“猜測(cè)法猜測(cè)法” 目標(biāo)：目標(biāo)：通過編譯器盡量降低轉(zhuǎn)移成功概率。通過編譯器盡量降低轉(zhuǎn)移成功概率。 例如：對(duì)于循環(huán)程序，普通編譯器生成的目標(biāo)代碼，例如：對(duì)于循環(huán)程序，普通編譯器生成的目標(biāo)代碼， 轉(zhuǎn)換成功的概率很高，不成功的只有一次。這種轉(zhuǎn)換成功的概率很高，不成功的只有一次。這種 編譯結(jié)果對(duì)流水線極為不利。編譯結(jié)果對(duì)流水線極為不利。 59 軟件軟件“猜測(cè)法猜測(cè)法” 通過編譯器降低轉(zhuǎn)移成功概率通過編譯器降低轉(zhuǎn)移成功概率。 60 2.硬件硬件“猜測(cè)法猜測(cè)法” 方法：方法：通過改變硬件結(jié)構(gòu)來降低轉(zhuǎn)移指令對(duì)流通過改變硬件結(jié)構(gòu)來降低轉(zhuǎn)移指令對(duì)流 水線的影響。水線的影響。 在指令緩沖棧的入口處設(shè)置一個(gè)簡單的指在

54、指令緩沖棧的入口處設(shè)置一個(gè)簡單的指 令分析器，當(dāng)檢測(cè)到轉(zhuǎn)移指令時(shí)，就從轉(zhuǎn)移目令分析器，當(dāng)檢測(cè)到轉(zhuǎn)移指令時(shí)，就從轉(zhuǎn)移目 標(biāo)地址開始起占領(lǐng)，同時(shí)保留當(dāng)前標(biāo)地址開始起占領(lǐng)，同時(shí)保留當(dāng)前PC中內(nèi)容，中內(nèi)容， 以便猜測(cè)錯(cuò)誤時(shí)恢復(fù)。轉(zhuǎn)移成功，猜測(cè)正確以便猜測(cè)錯(cuò)誤時(shí)恢復(fù)。轉(zhuǎn)移成功，猜測(cè)正確,對(duì)對(duì) 轉(zhuǎn)移指令對(duì)流水線不造成影響。轉(zhuǎn)移不成功，轉(zhuǎn)移指令對(duì)流水線不造成影響。轉(zhuǎn)移不成功， 用保存下來的地址恢復(fù)用保存下來的地址恢復(fù)PC。 軟硬件共同配合，都往一個(gè)方向去猜測(cè)。軟硬件共同配合，都往一個(gè)方向去猜測(cè)。 61 3.兩個(gè)先行指令緩沖棧兩個(gè)先行指令緩沖棧 在先行指令緩沖棧中在先行指令緩沖棧中增加一個(gè)先行目標(biāo)增加一個(gè)先行

55、目標(biāo) 緩沖棧。緩沖棧。 按照轉(zhuǎn)移成功的方向預(yù)取指令到先行目標(biāo)按照轉(zhuǎn)移成功的方向預(yù)取指令到先行目標(biāo) 緩沖棧中。緩沖棧中。 先行指令緩沖棧仍然按照轉(zhuǎn)移不成功的先行指令緩沖棧仍然按照轉(zhuǎn)移不成功的 方向繼續(xù)預(yù)取指令。方向繼續(xù)預(yù)取指令。 如果轉(zhuǎn)移不成功，則繼續(xù)分析原來先行如果轉(zhuǎn)移不成功，則繼續(xù)分析原來先行 指令緩沖中指令。指令緩沖中指令。 如果轉(zhuǎn)移成功，則分析新增設(shè)的先行目如果轉(zhuǎn)移成功，則分析新增設(shè)的先行目 標(biāo)緩沖棧中的指令。標(biāo)緩沖棧中的指令。 62 兩個(gè)先行指令緩沖棧兩個(gè)先行指令緩沖棧 63 5.2.5 動(dòng)態(tài)分支預(yù)測(cè)技術(shù)動(dòng)態(tài)分支預(yù)測(cè)技術(shù) 動(dòng)態(tài)轉(zhuǎn)移預(yù)測(cè)技術(shù)的兩個(gè)關(guān)鍵問題：動(dòng)態(tài)轉(zhuǎn)移預(yù)測(cè)技術(shù)的兩個(gè)關(guān)鍵問題：

56、 如何記錄轉(zhuǎn)移歷史信息，如何根據(jù)記錄如何記錄轉(zhuǎn)移歷史信息，如何根據(jù)記錄 的轉(zhuǎn)移歷史信息預(yù)測(cè)轉(zhuǎn)移方向。的轉(zhuǎn)移歷史信息預(yù)測(cè)轉(zhuǎn)移方向。 記錄轉(zhuǎn)移歷史信息的方法有三種：記錄轉(zhuǎn)移歷史信息的方法有三種： (1)最近一次或幾次轉(zhuǎn)移是否成功的信息記錄在最近一次或幾次轉(zhuǎn)移是否成功的信息記錄在 轉(zhuǎn)移指令中。轉(zhuǎn)移指令中。 (2)用一個(gè)高速緩沖棧保存條件轉(zhuǎn)移指令的轉(zhuǎn)移用一個(gè)高速緩沖棧保存條件轉(zhuǎn)移指令的轉(zhuǎn)移 目標(biāo)地址。目標(biāo)地址。 (3)用用Cache保存轉(zhuǎn)移目標(biāo)地址之后的保存轉(zhuǎn)移目標(biāo)地址之后的n條指令。條指令。 64 1.在指令在指令Cache中記錄轉(zhuǎn)移歷史信息中記錄轉(zhuǎn)移歷史信息 在指令在指令Cache中專門設(shè)置一個(gè)字

57、段，中專門設(shè)置一個(gè)字段， 稱為稱為“轉(zhuǎn)移歷史表轉(zhuǎn)移歷史表”。 在執(zhí)行轉(zhuǎn)移指令時(shí)，把轉(zhuǎn)移成功或不在執(zhí)行轉(zhuǎn)移指令時(shí)，把轉(zhuǎn)移成功或不 成功的信息記錄在這個(gè)表中。成功的信息記錄在這個(gè)表中。 當(dāng)下次再執(zhí)行到這條指令時(shí)，轉(zhuǎn)移預(yù)當(dāng)下次再執(zhí)行到這條指令時(shí)，轉(zhuǎn)移預(yù) 測(cè)邏輯根據(jù)測(cè)邏輯根據(jù)“轉(zhuǎn)移歷史表轉(zhuǎn)移歷史表”中記錄的信息中記錄的信息 預(yù)測(cè)轉(zhuǎn)移成功或不成功。預(yù)測(cè)轉(zhuǎn)移成功或不成功。 65 只記錄最近一次轉(zhuǎn)移是否成功的歷史信息只記錄最近一次轉(zhuǎn)移是否成功的歷史信息 如果如果“轉(zhuǎn)移歷史表轉(zhuǎn)移歷史表”中記錄的內(nèi)容是中記錄的內(nèi)容是“T”，則，則 預(yù)測(cè)轉(zhuǎn)移成功，如果記錄的是預(yù)測(cè)轉(zhuǎn)移成功，如果記錄的是“N”，則按照轉(zhuǎn)移，則按照轉(zhuǎn)

58、移 不成功的方向繼續(xù)取指令。不成功的方向繼續(xù)取指令。 并用實(shí)際轉(zhuǎn)移是否成功的信息來修改并用實(shí)際轉(zhuǎn)移是否成功的信息來修改“轉(zhuǎn)移歷轉(zhuǎn)移歷 史表史表”。 T T T：轉(zhuǎn)移成功，N：轉(zhuǎn)移不成功 N N T N 66 只記錄最近兩次轉(zhuǎn)移是否成功的歷史信息只記錄最近兩次轉(zhuǎn)移是否成功的歷史信息 圖中采用圖中采用偏向成功的預(yù)測(cè)策略偏向成功的預(yù)測(cè)策略：只有歷史上：只有歷史上 最近兩次執(zhí)行這條轉(zhuǎn)移指令時(shí)，轉(zhuǎn)移都沒有成功，最近兩次執(zhí)行這條轉(zhuǎn)移指令時(shí)，轉(zhuǎn)移都沒有成功， 本次才預(yù)測(cè)轉(zhuǎn)移不成功。本次才預(yù)測(cè)轉(zhuǎn)移不成功。 也可以采用其他預(yù)測(cè)策略。也可以采用其他預(yù)測(cè)策略。 TT：最最近近兩兩次次轉(zhuǎn)轉(zhuǎn)移移都都成成功功 NT：最最

59、近近一一次次轉(zhuǎn)轉(zhuǎn)移移成成功功，前前一一次次轉(zhuǎn)轉(zhuǎn)移移不不成成功功 TN：最最近近一一次次轉(zhuǎn)轉(zhuǎn)移移不不成成功功，前前一一次次轉(zhuǎn)轉(zhuǎn)移移成成功功 NN：最最近近兩兩次次轉(zhuǎn)轉(zhuǎn)移移都都不不成成功功 t：本本次次預(yù)預(yù)測(cè)測(cè)轉(zhuǎn)轉(zhuǎn)移移成成功功 n：本本次次預(yù)預(yù)測(cè)測(cè)轉(zhuǎn)轉(zhuǎn)移移不不成成功功 T：本本次次實(shí)實(shí)際際轉(zhuǎn)轉(zhuǎn)移移成成功功 N：本本次次實(shí)實(shí)際際轉(zhuǎn)轉(zhuǎn)移移不不成成功功 TT t TN t NT t NN n T N N T T TN N 67 當(dāng)當(dāng)“轉(zhuǎn)移歷史表轉(zhuǎn)移歷史表”是空白時(shí)，是空白時(shí)，可以有兩種方法：可以有兩種方法： (1)在在“轉(zhuǎn)移歷史表轉(zhuǎn)移歷史表”中預(yù)置轉(zhuǎn)移歷史信息。中預(yù)置轉(zhuǎn)移歷史信息。 (2)根據(jù)指令本身的

60、偏移字段的符號(hào)來預(yù)測(cè)轉(zhuǎn)根據(jù)指令本身的偏移字段的符號(hào)來預(yù)測(cè)轉(zhuǎn) 移的方向，如果偏移字段為負(fù)，則預(yù)測(cè)轉(zhuǎn)移移的方向，如果偏移字段為負(fù)，則預(yù)測(cè)轉(zhuǎn)移 成功，否則預(yù)測(cè)轉(zhuǎn)移不成功。成功，否則預(yù)測(cè)轉(zhuǎn)移不成功。 主要優(yōu)點(diǎn)：主要優(yōu)點(diǎn)： 不必專門設(shè)置轉(zhuǎn)移緩沖棧，所有記錄的轉(zhuǎn)移不必專門設(shè)置轉(zhuǎn)移緩沖棧，所有記錄的轉(zhuǎn)移 歷史信息比較少。歷史信息比較少。 例如例如:DEC公司的公司的Alpha 21064處理機(jī)就處理機(jī)就 采用了這種轉(zhuǎn)移預(yù)測(cè)方法，在它的一級(jí)指令采用了這種轉(zhuǎn)移預(yù)測(cè)方法，在它的一級(jí)指令 Cache中有一個(gè)專門的中有一個(gè)專門的“轉(zhuǎn)移歷史表轉(zhuǎn)移歷史表”字段。字段。 68 指指 令令 Cache（ 8KB） 轉(zhuǎn)轉(zhuǎn) 移移