第05章標(biāo)量處理機(jī) eng2

1、central south university余臘生 版權(quán)所有，違者必究 空間并行性設(shè)置多個(gè)獨(dú)立的操作部件多操作部件處理機(jī)超標(biāo)量處理機(jī) 時(shí)間并行性采用流水線技術(shù)。不增加或只增加少量硬件就能使運(yùn)算速度提高幾倍流水線處理機(jī)超流水線處理機(jī)5.2 流水線技術(shù) Pipelining central south university2022-4-21余臘生 版權(quán)所有，違者必究5-2流水線的表示方法流水線的表示方法 流水線的表示法有三種：連接圖、時(shí)空?qǐng)D、預(yù)約表。主要考慮前二種。1、簡(jiǎn)單流水線的連接圖表示 流水線的每一個(gè)階段稱為流水步、流水步驟、流水段、流水線階段、流水功能段、功能段、流水級(jí)、流水節(jié)拍等。一

2、個(gè)流水階段與另一個(gè)流水階段相連形成流水線。指令從流水線一端進(jìn)入，經(jīng)過(guò)流水線的處理，從另一端流出。 有些復(fù)雜指令 在執(zhí)行階段也采用流水線方式工作，稱為操作流水線。取指令譯碼執(zhí)行保存結(jié)果t1t2t3t4central south university余臘生 版權(quán)所有，違者必究2、一種指令流水線 一般4至12個(gè)流水段，等于及大于8個(gè)流水段的稱為超流水線處理機(jī)取指形成操作數(shù)地址譯碼取操作數(shù)執(zhí)行保存結(jié)果central south university余臘生 版權(quán)所有，違者必究3、流水線的時(shí)空?qǐng)D采用“時(shí)空?qǐng)D”表示流水線的工作過(guò)程。在時(shí)空?qǐng)D中，橫坐標(biāo)表示時(shí)間，也就是輸入到流水線中的各個(gè)任務(wù)在流水線中所經(jīng)過(guò)的

3、時(shí)間。當(dāng)流水線中各個(gè)流水段的執(zhí)行時(shí)間都相等時(shí)，橫坐標(biāo)被分割成相等長(zhǎng)度的時(shí)間段?？v坐標(biāo)表示空間，即流水線的每一個(gè)流水段 一條簡(jiǎn)單流水線的時(shí)空?qǐng)D：分析k分析k+1 分析k+2 分析k+3執(zhí)行k執(zhí)行k+1 執(zhí)行k+2 執(zhí)行k+3時(shí)間空間0t1t2t3t4t5central south university余臘生 版權(quán)所有，違者必究 一個(gè)浮點(diǎn)加法器流水線的時(shí)空?qǐng)D(由求階差、對(duì)階、尾數(shù)加和規(guī)格化4個(gè)流水段組成)：ED1時(shí)間空間0t1t2t3t4t5ED2 ED3 ED4 ED5EA1 EA2 EA3 EA4 EA5MA1 MA2 MA3 MA4 MA5NL1 NL2 NL3 NL4 NL5t6t7t8N

4、L：規(guī)格化MA：尾數(shù)加EA：對(duì)階ED：求階差central south university2022-4-21余臘生 版權(quán)所有，違者必究5-6.12345.n-1 n.12345.n-1 n.12345.n-1 n.12345.n-1 n1234t t0 0 t t0 0 t t0 0 t t0 0T T0=m 0=m t t0 0n n t t0 0T T(m-1) (m-1) t t0 0(n-1) (n-1) t t0 0填入填入 正常正常 排空排空 流水時(shí)空?qǐng)D流水時(shí)空?qǐng)D空間空間時(shí)間時(shí)間central south university2022-4-21余臘生 版權(quán)所有，違者必究5-72、

5、流水線特點(diǎn)、流水線特點(diǎn)： 1）流水一定重疊，比重疊更苛刻。）流水一定重疊，比重疊更苛刻。 2）一條流水線通常有多個(gè)流水段組成。）一條流水線通常有多個(gè)流水段組成。 3）每段有專用功能部件，各部件順序連接，不斷流。）每段有專用功能部件，各部件順序連接，不斷流。 4）流水線有建立時(shí)間、滿載時(shí)間、排空時(shí)間，）流水線有建立時(shí)間、滿載時(shí)間、排空時(shí)間， 5）各段時(shí)間盡量短、一致；不一致時(shí)最慢子過(guò)程為瓶頸。）各段時(shí)間盡量短、一致；不一致時(shí)最慢子過(guò)程為瓶頸。 6）給出指標(biāo)如最大吞吐率，為滿負(fù)載最佳指標(biāo)。）給出指標(biāo)如最大吞吐率，為滿負(fù)載最佳指標(biāo)。建立時(shí)間：建立時(shí)間：在流水線開始時(shí)有一段流水線填入時(shí)間，使得流水線填

6、滿。在流水線開始時(shí)有一段流水線填入時(shí)間，使得流水線填滿。正常流動(dòng)時(shí)間：正常流動(dòng)時(shí)間：流水線正常工作，各功能段源源不斷滿載工作。流水線正常工作，各功能段源源不斷滿載工作。排空時(shí)間：排空時(shí)間：在流水線第一條指令結(jié)束時(shí)，其他指令還需要一段釋放時(shí)間。在流水線第一條指令結(jié)束時(shí)，其他指令還需要一段釋放時(shí)間。central south university2022-4-21余臘生 版權(quán)所有，違者必究5-81234出出入入非線性流水線非線性流水線流水的分級(jí)、分類流水的分級(jí)、分類分級(jí)分級(jí)：（處理的級(jí)別分類）：（處理的級(jí)別分類）v 部件級(jí)：將復(fù)雜的算邏運(yùn)算組成流水工作方式；部件級(jí)：將復(fù)雜的算邏運(yùn)算組成流水工作方式

7、； v 指令級(jí)：把一條指令解釋過(guò)程分成多個(gè)子過(guò)程指令級(jí)：把一條指令解釋過(guò)程分成多個(gè)子過(guò)程 ；v 處理機(jī)級(jí)：每個(gè)處理機(jī)完成某一專門任務(wù)，各個(gè)處理機(jī)所處理機(jī)級(jí)：每個(gè)處理機(jī)完成某一專門任務(wù)，各個(gè)處理機(jī)所得到的結(jié)果需存放在與下一個(gè)處理機(jī)所共享的存儲(chǔ)器中得到的結(jié)果需存放在與下一個(gè)處理機(jī)所共享的存儲(chǔ)器中 其他分類：其他分類： 功能：?jiǎn)喂δ芰魉€（如功能：?jiǎn)喂δ芰魉€（如CRAY-1）、多功能流水線）、多功能流水線 （如（如TI-ASC） 工作方式：靜態(tài)流水線、動(dòng)態(tài)流水線工作方式：靜態(tài)流水線、動(dòng)態(tài)流水線 連接方式：線性、非線性連接方式：線性、非線性 處理數(shù)據(jù)：標(biāo)量流水、向量流水處理數(shù)據(jù)：標(biāo)量流水、向量流水c

8、entral south university余臘生 版權(quán)所有，違者必究 1、線性流水線與非線性流水線 流水線的各個(gè)流水段之間是否有反饋信號(hào) 線性流水線(Linear Pipelining)每個(gè)流水段都流過(guò)一次，且僅流過(guò)一次 非線性流水線(Nonlinear Pipelining)在流水線的某些流水段之間有反饋回路或前饋回路 線性流水線能夠用流水線連接圖唯一表示非線性流水線必須用流水線連接圖流水線預(yù)約表等共同表示S1輸入S2S3輸出前饋回路反饋回路一種簡(jiǎn)單的非線性流水線5.2.2 流水線的分類central south university余臘生 版權(quán)所有，違者必究 2、按照流水線的級(jí)別來(lái)分

9、處理機(jī)級(jí)流水線, 又稱為指令流水線 (Instruction Pipelining)例如：在采用先行控制器的處理機(jī)中，各功能部件之間的流水線先行指令緩沖棧輸入先行控制方式中的指令流水線先行指令分析器先行讀數(shù)棧先行操作棧取指譯碼取操作數(shù)指令執(zhí)行部件后行寫數(shù)棧輸出執(zhí)行寫結(jié)果central south university余臘生 版權(quán)所有，違者必究求階差輸入輸出t1對(duì)階尾數(shù)加規(guī)格化t2t3t4P1輸入任務(wù)1MMP2任務(wù)2MP3任務(wù)3輸出處理機(jī)之間的流水線稱為宏流水線 (Macro Pipelining)每個(gè)處理機(jī)對(duì)同一個(gè)數(shù)據(jù)流的不同部分分別進(jìn)行處理部件級(jí)流水線（操作流水線），如浮點(diǎn)加法器流水線cen

10、tral south university余臘生 版權(quán)所有，違者必究 3、單功能流水線與多功能流水線 單功能流水線：只能完成一種固定功能的流水線Cray-1計(jì)算機(jī)中有12條；YH-1計(jì)算機(jī)有18條；Pentium有一條5段的定點(diǎn)和一條8段的浮點(diǎn)流水線；Pentium有三條指令流水線，其中兩條定點(diǎn)指令流水線，一條浮點(diǎn)指令流水線。 多功能流水線：流水線的各段通過(guò)不同連接實(shí)現(xiàn)不同功能 Texas公司的ASC計(jì)算機(jī)中的8段流水線，能夠?qū)崿F(xiàn)：定點(diǎn)加減法、定點(diǎn)乘法、浮點(diǎn)加法、浮點(diǎn)乘法、邏輯運(yùn)算、移位操作、數(shù)據(jù)轉(zhuǎn)換、向量運(yùn)算等。central south university余臘生 版權(quán)所有，違者必究 A

11、B A B A B A B 輸入 輸入 輸入 輸入 求階差 求階差 求階差 求階差 對(duì)階 對(duì)階 對(duì)階 對(duì)階 尾數(shù)加 尾數(shù)加 尾數(shù)加 尾數(shù)加 規(guī)格化 規(guī)格化 規(guī)格化 規(guī)格化 尾數(shù)乘 尾數(shù)乘 尾數(shù)乘 尾數(shù)乘 累加 累加 累加 累加 輸出 輸出 輸出 輸出 g=f(A,B) 定點(diǎn)乘 浮點(diǎn)加 浮點(diǎn)點(diǎn)積 (a)功能段間的互連 (b)定點(diǎn)乘法 (c)浮點(diǎn)加法 (d)浮點(diǎn)點(diǎn)積 central south university余臘生 版權(quán)所有，違者必究 4、靜態(tài)流水線與動(dòng)態(tài)流水線靜態(tài)流水線：同一段時(shí)間內(nèi)，多功能流水線中的各個(gè)功能段只能按照一種固定的方式連接，實(shí)現(xiàn)一種固定的功能。只有連續(xù)出現(xiàn)同一種運(yùn)算時(shí)，流水線

12、的效率才能得到充分的發(fā)揮。動(dòng)態(tài)流水線：在同一段時(shí)間內(nèi)，多功能流水線中的各段可以按照不同的方式連接，同時(shí)執(zhí)行多種功能。central south university2022-4-21余臘生 版權(quán)所有，違者必究5-15.1234.n-1 n.1234.n-1 n.1234.n-1n.1234.n-1 n12345867.1234.n-1 n.1234.n-1 n時(shí)間時(shí)間空間空間(段號(hào)段號(hào))浮加浮加一一 二二 三三 四四二二 三三一一二二一一一一定乘定乘.靜態(tài)多功能流水線時(shí)靜態(tài)多功能流水線時(shí)-空?qǐng)D空?qǐng)D靜態(tài)流水線：靜態(tài)流水線：只有當(dāng)進(jìn)入的是一串相同運(yùn)算的指令時(shí)，流水的只有當(dāng)進(jìn)入的是一串相同運(yùn)算的指令

13、時(shí)，流水的效能才得以發(fā)揮，才能使各個(gè)功能段并行地對(duì)多條指令的數(shù)據(jù)效能才得以發(fā)揮，才能使各個(gè)功能段并行地對(duì)多條指令的數(shù)據(jù)進(jìn)行流水處理。進(jìn)行流水處理。 central south university2022-4-21余臘生 版權(quán)所有，違者必究5-16.12345.n-1 n.12345.n-1 n.12345.n-1 n.12345.n-1 n12345867.12345.n-1 n.12345.n-1 n時(shí)間時(shí)間浮加浮加定乘定乘一一二二三三 四四 五五 六六一一二二三三 四四 五五 六六七七一一二二三三 四四 五五一一二二三三 四四動(dòng)態(tài)多功能流水線時(shí)動(dòng)態(tài)多功能流水線時(shí)-空?qǐng)D空?qǐng)D區(qū)別：區(qū)別：如果

14、從軟硬功能分配的觀點(diǎn)上來(lái)看，靜態(tài)流水線其實(shí)如果從軟硬功能分配的觀點(diǎn)上來(lái)看，靜態(tài)流水線其實(shí)是把功能負(fù)擔(dān)較多地加到軟件上，以簡(jiǎn)化硬件，動(dòng)態(tài)流水線是把功能負(fù)擔(dān)較多地加到軟件上，以簡(jiǎn)化硬件，動(dòng)態(tài)流水線則是把功能負(fù)擔(dān)較多地加在硬件上，以提高流水的效能。則是把功能負(fù)擔(dān)較多地加在硬件上，以提高流水的效能。central south university余臘生 版權(quán)所有，違者必究 5、流水線的其他分類方法按照數(shù)據(jù)表示方式：標(biāo)量流水線和向量流水線按照控制方式：同步流水線和異步流水線順序流水線與亂序流水線：亂序流水線又稱為無(wú)序流水線、錯(cuò)序流水線或異步流水線等S1就緒回答S2就緒回答S3就緒回答輸出就緒回答輸入ce

15、ntral south university余臘生 版權(quán)所有，違者必究 Example 1central south university2022-4-21余臘生 版權(quán)所有，違者必究5-19Example 2 在靜態(tài)、加乘雙功能流水線上實(shí)現(xiàn)。在靜態(tài)、加乘雙功能流水線上實(shí)現(xiàn)。41)(iiiba143265xyz乘乘加加 in the pipeline ,stage 1 and 5 needs 3 time units： algorithmsalgorithms：消除相關(guān)性，可并行執(zhí)行的操作先執(zhí)行；消除相關(guān)性，可并行執(zhí)行的操作先執(zhí)行； 使流水線盡可能長(zhǎng)時(shí)間執(zhí)行同一種功能。使流水線盡可能長(zhǎng)時(shí)間執(zhí)行同

16、一種功能。 the best orderthe best order： x1=a1+b1x1=a1+b1，x2=a2+b2,x3=a3+b3,x4=a4+b4x2=a2+b2,x3=a3+b3,x4=a4+b4； y1=x1y1=x1* *x2,y2=x3x2,y2=x3* *x4x4； z=y1z=y1* *y2y2central south university余臘生 版權(quán)所有，違者必究 衡量流水線性能的主要指標(biāo)有：吞吐率、加速比和效率1 1、吞吐率（、吞吐率（ThoughPutThoughPut） 求流水線吞吐率的最基本公式： TP = n / Tkn為任務(wù)數(shù), Tk為完成n個(gè)任務(wù)所用時(shí)

17、間 各段執(zhí)行時(shí)間相等，輸入連續(xù)任務(wù)情況下完成n個(gè)連續(xù)任務(wù)需要的總時(shí)間為：Tk= (k+n-1) t k為流水線的段數(shù)， t為時(shí)鐘周期線性流水線的性能分析線性流水線的性能分析central south university余臘生 版權(quán)所有，違者必究1timespaceS123 n-1 nS2S3S4123 n-1 n123 n-1 n123 n-1 nkt(n-1) tnt(k-1)tTcentral south university余臘生 版權(quán)所有，違者必究 Throughput ：最大吞吐率為：各段執(zhí)行時(shí)間不相等、輸入連續(xù)任務(wù)情況下：吞吐率為：最大吞吐率為：tnknTP) 1(nTPLimn

18、knttmax() 11),max() 1(211kkiitttntnTP ),max(121maxktttTP central south university余臘生 版權(quán)所有，違者必究流水線各段執(zhí)行時(shí)間不相等的解決辦法S1輸入t1=tS2t2=3tS3t3=tS4t4=t輸出1時(shí)間空間S1S2S3S4Sti(n-1)t2Tk23n123n123n123ncentral south university余臘生 版權(quán)所有，違者必究 一是將“瓶頸”流水段細(xì)分(如果可分的話)：/合并？ 二是將 “瓶頸”流水段重復(fù)設(shè)置：S1輸入輸出tS2-1tS2-2tS2-3tS3tS4tS2(3t)S1輸入輸出

19、t1=tS2-1S2-1S2-1S3S4t3=tt4=tt2=3tcentral south university2022-4-21余臘生 版權(quán)所有，違者必究5-25 如何解決瓶頸問(wèn)題？如何解決瓶頸問(wèn)題？ a. a.將此段進(jìn)一步細(xì)化，保證細(xì)化后的段與其將此段進(jìn)一步細(xì)化，保證細(xì)化后的段與其它段處理時(shí)間相同或相近；它段處理時(shí)間相同或相近；123a3b43c1471014710S s3b s3a s2 s1t1t12t17T s3c s46811 1235911 122 3592681471035911 122681471035911 122681471035911 122681471035911

20、12268central south university2022-4-21余臘生 版權(quán)所有，違者必究5-26147101471014710S s3b s3a s2 s1t1t12t17T s3c s46811 1235911 122 35926825811369121471035911 12268 b. b.并聯(lián)設(shè)置多套功能部件，通過(guò)并聯(lián)設(shè)置多套功能部件，通過(guò)控制器控制器進(jìn)行調(diào)度。進(jìn)行調(diào)度。1243b3a3ct3t3ttt 此方法運(yùn)行效果與過(guò)程細(xì)化方法效果相同。此方法運(yùn)行效果與過(guò)程細(xì)化方法效果相同。central south university余臘生 版權(quán)所有，違者必究 2 2、加速比（、

21、加速比（SpeedupSpeedup） 計(jì)算流水線加速比的基本公式：S = 順序執(zhí)行時(shí)間T0 / 流水線執(zhí)行時(shí)間Tk 各段執(zhí)行時(shí)間相等，輸入連續(xù)任務(wù)情況下加速比為： 最大加速比為： 各段執(zhí)行時(shí)間不等，輸入連續(xù)任務(wù)情況下實(shí)際加速比為：1) 1(nknktnktnkSSLimk nknknmax1central south university余臘生 版權(quán)所有，違者必究K=6K=10任務(wù)個(gè)數(shù)加速比10246811 248 16 32 64 128Snttntttiikiikk 11121() max(, ,）central south university余臘生 版權(quán)所有，違者必究3 3、效率（、

22、效率（EfficiencyEfficiency）計(jì)算流水線效率的一般公式：各流水段執(zhí)行時(shí)間相等，輸入n個(gè)連續(xù)任務(wù)流水線的效率為： 流水線的最高效率為：各流水段執(zhí)行時(shí)間不等，輸入n個(gè)連續(xù)任務(wù)流水線的效率為：kTkTknE0個(gè)流水段的總的時(shí)空區(qū)個(gè)任務(wù)占用的時(shí)空區(qū)1) 1(nkntnkktnkE11maxnknLimEncentral south university余臘生 版權(quán)所有，違者必究 流水線各段的設(shè)備量或各段的價(jià)格不相等時(shí)：流水線的效率為：即： 其中，ai M流水性能才發(fā)揮得更好流水性能才發(fā)揮得更好central south university2022-4-21余臘生 版權(quán)所有，違者必究

23、5-39例例4 4 在靜態(tài)、加乘雙功能流水線上實(shí)現(xiàn)。在靜態(tài)、加乘雙功能流水線上實(shí)現(xiàn)。41)(iiiba143265xyz乘乘加加 流水線結(jié)構(gòu)如下：流水線結(jié)構(gòu)如下： 實(shí)現(xiàn)算法：實(shí)現(xiàn)算法：消除相關(guān)性，可并行執(zhí)行的操作先執(zhí)行；消除相關(guān)性，可并行執(zhí)行的操作先執(zhí)行； 使流水線盡可能長(zhǎng)時(shí)間執(zhí)行同一種功能。使流水線盡可能長(zhǎng)時(shí)間執(zhí)行同一種功能。 最佳最佳實(shí)現(xiàn)順序：實(shí)現(xiàn)順序： x1=a1+b1x1=a1+b1，x2=a2+b2,x3=a3+b3,x4=a4+b4x2=a2+b2,x3=a3+b3,x4=a4+b4； y1=x1y1=x1* *x2,y2=x3x2,y2=x3* *x4x4； z=y1z=y1*

24、*y2y2central south university2022-4-21余臘生 版權(quán)所有，違者必究5-40 T TP P= = S SP P= = E E = =7/(17t)7/(17t)(4(4* *3t+33t+3* *5t)/(17t)=27/17=1.885t)/(17t)=27/17=1.88(3(3* *4t+34t+3* *5t)/(65t)/(6* *17t)=9/34=26.4%17t)=9/34=26.4%134S s4 s3 s2 s1t6t12T221212121333313421342 s5 s6213(a1+b1)(a2+b2)(a3+b3)(a4+b4)(a

25、1+b1)(a2+b2)(a3+b3)(a4+b4)(a1+b1)(a2+b2)(a3+b3)(a4+b4)t17加法加法乘法乘法1乘法乘法2a1b1a2b2a3b3(a1+b1)(a2+b2)(a3+b3)(a4+b4)(a1+b1)(a2+b2)(a3+b3)(a4+b4)a4b4central south university2022-4-21余臘生 版權(quán)所有，違者必究5-41 結(jié)果分析：結(jié)果分析： 流水線適用范圍？流水線適用范圍？ 流水線適合于操作相同、操作數(shù)間無(wú)相關(guān)性的多流水線適合于操作相同、操作數(shù)間無(wú)相關(guān)性的多個(gè)指令的執(zhí)行。個(gè)指令的執(zhí)行。 功能切換必須等待排空后進(jìn)行。功能切換必須等

26、待排空后進(jìn)行。（靜態(tài)通?。o態(tài)通?。?如何提高流水線效率？如何提高流水線效率？ 盡量細(xì)化各功能段，盡量細(xì)化各功能段，盡量減少功能切換，盡量減盡量減少功能切換，盡量減少數(shù)據(jù)相關(guān)，盡量增加一次處理的指令數(shù)量。少數(shù)據(jù)相關(guān)，盡量增加一次處理的指令數(shù)量。 建立、排空時(shí)間過(guò)多；建立、排空時(shí)間過(guò)多； （流水線斷流（流水線斷流數(shù)據(jù)相關(guān)和操作變換數(shù)據(jù)相關(guān)和操作變換 ） 對(duì)此題動(dòng)態(tài)流水線結(jié)果如何？對(duì)此題動(dòng)態(tài)流水線結(jié)果如何？（減少（減少2 2個(gè)個(gè)tt）課堂作業(yè) stage 1 : 1 t ,Stage 2: 3 t , stage 3: 2 t, stage 4 :1 t, 每隔每隔3 t輸入一個(gè)任務(wù)輸入一個(gè)任務(wù)

27、,求求Tp,E,Spcentral south university2022-4-21余臘生 版權(quán)所有，違者必究5-42流水線的實(shí)現(xiàn)與控制流水線的實(shí)現(xiàn)與控制一、流水線的中斷處理一、流水線的中斷處理1.1.解決問(wèn)題解決問(wèn)題 中斷現(xiàn)場(chǎng)的保護(hù)與恢復(fù)。中斷現(xiàn)場(chǎng)的保護(hù)與恢復(fù)。 處理時(shí)不在乎斷流時(shí)間長(zhǎng)短。處理時(shí)不在乎斷流時(shí)間長(zhǎng)短。（概率低，不可預(yù)知）概率低，不可預(yù)知）2.2.解決方法解決方法（1 1）不精確斷點(diǎn)法）不精確斷點(diǎn)法 斷點(diǎn)精確到中斷請(qǐng)求時(shí)最后進(jìn)入流水線的那條指令。斷點(diǎn)精確到中斷請(qǐng)求時(shí)最后進(jìn)入流水線的那條指令。 特點(diǎn)：特點(diǎn)：硬件開銷小，控制簡(jiǎn)單，程序排錯(cuò)不方便。硬件開銷小，控制簡(jiǎn)單，程序排錯(cuò)不方便

28、。central south university2022-4-21余臘生 版權(quán)所有，違者必究5-43（2 2）精確斷點(diǎn)法）精確斷點(diǎn)法 斷點(diǎn)精確到中斷請(qǐng)求時(shí)已進(jìn)入流水線的各條斷點(diǎn)精確到中斷請(qǐng)求時(shí)已進(jìn)入流水線的各條指令。指令。 硬件要求：硬件要求：增設(shè)大量的后援寄存器。增設(shè)大量的后援寄存器。central south university2022-4-21余臘生 版權(quán)所有，違者必究5-44Nonlinear pipelining什么是非線性流水線？ 如果存在反饋回路，當(dāng)一個(gè)任務(wù)在流水線中流過(guò)時(shí)，在同一個(gè)流水段中可能要經(jīng)過(guò)多次。不能每一個(gè)時(shí)鐘周期向流水線輸入一個(gè)新任務(wù)。這樣的流水線就是非線性流水線

29、。 非線性流水線的調(diào)度問(wèn)題就是要解決要隔多少個(gè)時(shí)鐘周期向流水線輸入一個(gè)新任務(wù)才能使流水線 的各個(gè)流水段都不發(fā)生沖突。 表示一個(gè)非線性流水線需要用到連接圖和預(yù)約表。如圖：central south university2022-4-21余臘生 版權(quán)所有，違者必究5-45S1S2S3S4輸出輸入反饋線 時(shí)間流水段1234567S1XXXS2XXS3XXS4X非線性流水線的連接圖非線性流水線的預(yù)約表central south university2022-4-21余臘生 版權(quán)所有，違者必究5-46 預(yù)約表橫坐標(biāo)表示流水線的時(shí)鐘周期，縱坐標(biāo)表示流水線的各個(gè)流水段，中間有“X”表示該流水段在這一個(gè)時(shí)鐘周

30、期處于工作狀態(tài)，空白表示該流水段在這一個(gè)時(shí)鐘周期不工作。 一行中可以有多個(gè)“X”，表示一個(gè)任務(wù)在不同時(shí)鐘周期重復(fù)使用了同一流水段；一列中有多個(gè)“X”表示在同一個(gè)時(shí)鐘周期同時(shí)占用了多個(gè)流水段。預(yù)約表的行數(shù)是流水線的段數(shù)，預(yù)約表的列數(shù)是一個(gè)任務(wù)從進(jìn)入流水線到流水線中輸出所經(jīng)過(guò)的時(shí)鐘周期數(shù)。 向一條非線性流水線的輸入端連續(xù)輸入兩個(gè)任務(wù)之間的時(shí)間間隔稱為非線性流水線的啟動(dòng)距離，以時(shí)鐘周期數(shù)表示。 當(dāng)使用3為啟動(dòng)距離，則對(duì)上述的流水線，將在某些流水段發(fā)生沖突，即兩個(gè)以上任務(wù)同時(shí)爭(zhēng)用一個(gè)流水段。引起非線性流水線流水段沖突的啟動(dòng)距離稱為禁啟動(dòng)止距離。 不發(fā)生沖突的啟動(dòng)距離是一個(gè)循環(huán)數(shù)列。使非線性流水線的任何

31、一個(gè)流水段在任何一個(gè)時(shí)鐘周期都不發(fā)生沖突的循環(huán)數(shù)列稱為非線性流水線的啟動(dòng)循環(huán)。central south university2022-4-21余臘生 版權(quán)所有，違者必究5-47X3X2X1S4X4X2X3X1X2X1S3X3X4X2X3X1X2X1S2X2X3X4X1X2X3X1X2X1S11110987654321 時(shí)間流水段啟動(dòng)距離為3的流水線沖突情況兩個(gè)任務(wù)爭(zhēng)用一個(gè)流水段S1兩個(gè)任務(wù)爭(zhēng)用一個(gè)流水段S1central south university2022-4-21余臘生 版權(quán)所有，違者必究5-48X3X2X1X1S4X2X2X2X1S3X3X1X1S2X2X1X1X1S1111098

32、7654321 時(shí)間流水段啟動(dòng)距離為5的流水線預(yù)約表X2X3啟動(dòng)周期重復(fù)啟動(dòng)周期（5）是一個(gè)循環(huán)，稱為恒定循環(huán)。central south university2022-4-21余臘生 版權(quán)所有，違者必究5-49時(shí)間流水段12345678910111213141516S1X1X2X1X2X1X2X3X4X3X4X3X4S2X1X2X1X2X3X4X3X4S3X1X2X1X2X3X4X3X4S4X1X2X3X4啟動(dòng)距離為（1，7）循環(huán)時(shí)的流水線預(yù)約表要正確地調(diào)度一條非線性流水線，首先要找出流水線的所有禁止啟動(dòng)距離。所有禁止啟動(dòng)啟動(dòng)距離組合在一起成為一個(gè)數(shù)列，稱為禁止向量。central sout

33、h university2022-4-21余臘生 版權(quán)所有，違者必究5-50 由預(yù)約表得到禁止向量的方法： 將預(yù)約表的每一行中任意兩個(gè)“X”之間的距離都計(jì)算出來(lái)，去掉重復(fù)的，這種數(shù)組成的一個(gè)數(shù)列就是這條非線性流水線的禁止向量。 例如：前述的非線性流水線，其禁止向量為 （3，4，6）。 把一個(gè)啟動(dòng)循環(huán)內(nèi)的所有啟動(dòng)距離相加，然后再除以這個(gè)循環(huán)內(nèi)的啟動(dòng)距離個(gè)數(shù)，就得到這個(gè)啟動(dòng)循環(huán)的平均啟動(dòng)距離。 非線性流水線無(wú)沖突調(diào)度的主要目標(biāo)是要找出具有最小平均啟動(dòng)距離的啟動(dòng)循環(huán)，按照這樣的啟動(dòng)循環(huán)向非線性流水線的輸入端輸入任務(wù)，流水線的工作速度最快，而且所有流水段在任何時(shí)間都沒(méi)有沖突。central south

34、 university2022-4-21余臘生 版權(quán)所有，違者必究5-51 例子：一條有4個(gè)流水段的非線性流水線，每個(gè)流水段的延遲時(shí)間都相等，它的預(yù)約表如下圖： 時(shí)間流水段1234567S1XXS2XXS3XXS4X（1）寫出流水線的禁止向量和初始沖突向量（2）畫出調(diào)度流水線的狀態(tài)圖（3）求流水線的最小啟動(dòng)循環(huán)和最小啟動(dòng)距離（4）求平均啟動(dòng)距離最小的恒定循環(huán)。central south university2022-4-21余臘生 版權(quán)所有，違者必究5-52 解：（1）禁止向量為（2，4，6）沖突向量：用二進(jìn)制表示，長(zhǎng)度是禁止向量的最大距離。沖突向量C=（C1C2C3C4C5C6），由禁止向量

35、，C2=C4=C6=1，其余位為0，沖突向量為 C=（101010）。 （2）由沖突向量構(gòu)造一張圖：將C放到一個(gè)6位邏輯右移移位器，當(dāng)從移位器移出0，用移位器中的值與初始沖突向量做“按位或”，得到一個(gè)新的沖突向量。當(dāng)移位器移出1，不做任何處理。重復(fù)這個(gè)步驟。對(duì)產(chǎn)生的每一個(gè)新的沖突向量做同樣處理。在初始沖突向量和所有形成的沖突向量之間，箭頭連接。central south university2022-4-21余臘生 版權(quán)所有，違者必究5-531010101111111011111010117*157*3537*當(dāng)右移2、4、6位，時(shí)移出位為1，表示用這些啟動(dòng)距離輸入新任務(wù)要發(fā)生沖突，不做任何處

36、理。當(dāng)右移1、3、5和大于等于7位時(shí)，移出位是0，表示用這些啟動(dòng)距離輸入新任務(wù)不會(huì)發(fā)生沖突。7*表示大于等于75central south university2022-4-21余臘生 版權(quán)所有，違者必究5-54（3）從狀態(tài)圖中可以找到許多不發(fā)生流水段沖突的啟動(dòng)循環(huán)。，只要找到簡(jiǎn)單循環(huán)，進(jìn)而確定平均啟動(dòng)距離最小的啟動(dòng)循環(huán)。它們是： （1，7）、（3，5，7）、（5，7）等簡(jiǎn)單循環(huán)平均啟動(dòng)距離（1，7）4（3，5）4（5，7）6（3，5，7）5（5，3，7）5（3，5）4（5）5（7）7最小啟動(dòng)循環(huán)是具有最小平均最小啟動(dòng)距離的啟動(dòng)循環(huán)。central south university2022-4

37、-21余臘生 版權(quán)所有，違者必究5-55 最小循環(huán)為（1，7）、（3，5） 最小恒定循環(huán)為（5） 時(shí)間流水12345678910111213141516S1X1X2X1X3X2X4X3S2X1X2X1X2X3X4X3S3X1X1X2X2X3X3X4S4X1X2X3X4最小啟動(dòng)循環(huán)為（3，5）的流水線工作狀態(tài)central south university2022-4-21余臘生 版權(quán)所有，違者必究5-56 時(shí)間流水段123456789101112131415S1X1X2X1X2X3X4X3S2X1X2X1X2X3X4X3X4S3X1X2X1X2X3X4X3X4S4X1X2X3X4最小啟動(dòng)循環(huán)為

38、（1，7）的流水線工作狀態(tài)central south university2022-4-21余臘生 版權(quán)所有，違者必究5-57 時(shí)間流水段123456789101112131415S1X1 X2X1 X3X2 S2X1 X1X2X2X3 S3X1 X1 X2X2 X3 X3S4X1 X2 X3恒定啟動(dòng)循環(huán)（5）的流水線工作狀態(tài)啟動(dòng)周期重復(fù)啟動(dòng)周期central south university2022-4-21余臘生 版權(quán)所有，違者必究5-58例例2 非線性流水線調(diào)度非線性流水線調(diào)度某流水線結(jié)構(gòu)如下：某流水線結(jié)構(gòu)如下：S1S2S3S4S5入入出出 流水線調(diào)度方案如下：流水線調(diào)度方案如下：cen

39、tral south university2022-4-21余臘生 版權(quán)所有，違者必究5-59（1 1）形成預(yù)約表）形成預(yù)約表 指令總拍數(shù)為指令總拍數(shù)為n，流水線有，流水線有k個(gè)段，則形成個(gè)段，則形成nk的預(yù)約表，段的使用情況用的預(yù)約表，段的使用情況用“”表示。表示。 預(yù)約表如下：預(yù)約表如下：543 21987654382716tS轉(zhuǎn)上頁(yè)central south university2022-4-21余臘生 版權(quán)所有，違者必究5-60（2 2）由預(yù)約表形成禁止表）由預(yù)約表形成禁止表F F F= F=各段中沖突間隔拍數(shù)各段中沖突間隔拍數(shù) 本例：本例： F=1F=1，5 5，6 6，88543

40、21987654382716tS543 21987654382716tS5681central south university2022-4-21余臘生 版權(quán)所有，違者必究5-61（3 3）由禁止表）由禁止表F F形成初始沖突向量形成初始沖突向量C C0 0 C C0 0= =（c cN Nc c0 0），），c ci i=1=1沖突，沖突，=0=0不沖突。不沖突。 本例：本例：C C0 0 = =（1011000110110001）。）。（4 4）由初始沖突向量）由初始沖突向量C C0 0形成狀態(tài)轉(zhuǎn)換圖形成狀態(tài)轉(zhuǎn)換圖 a.a.C C0 0每過(guò)一拍邏輯右移一位，若移出每過(guò)一拍邏輯右移一位，若移

41、出0 0，則允許后續(xù)，則允許后續(xù)指令進(jìn)入流水線，再與指令進(jìn)入流水線，再與C C0 0按位按位“或或”，形成新的沖突，形成新的沖突向量向量C Ci i；10110001101101111011110110111011初始狀態(tài)初始狀態(tài)3427central south university2022-4-21余臘生 版權(quán)所有，違者必究5-62 2拍后，新指令拍后，新指令(-I2-I2 )進(jìn)入后：進(jìn)入后：54321987654321tS643I1I1與與I3I3的的F=3,4,6F=3,4,6，I2I2與與I3I3的的F=1,5,6,8, F=1,5,6,8, 新新F=1,3,4,5,6,8F=1,3

42、,4,5,6,8，C C2 2=(10111101)=(10111101)。 注意：注意：C Ci i為第為第i拍后流水線的沖突向量，此時(shí)流水線拍后流水線的沖突向量，此時(shí)流水線中已有兩條指令，中已有兩條指令，C Ci i用于判斷第三條指令的進(jìn)入。用于判斷第三條指令的進(jìn)入。central south university2022-4-21余臘生 版權(quán)所有，違者必究5-631011000110110111101111011011101110111111初始狀態(tài)初始狀態(tài)34422777 b.b.各各C Ci i再每過(guò)一拍邏輯右移一位，若移出再每過(guò)一拍邏輯右移一位，若移出0 0，允許后續(xù)指令進(jìn)入，再與

43、允許后續(xù)指令進(jìn)入，再與C C0 0按位按位“或或”，形成，形成新的沖突向量新的沖突向量C Cijij； 注意：注意：C Cijij為第為第i+j拍后流水線的沖突向量，此時(shí)流水拍后流水線的沖突向量，此時(shí)流水線中已有三條指令，線中已有三條指令， C Cijij用于判斷第四條指令的進(jìn)入。用于判斷第四條指令的進(jìn)入。central south university2022-4-21余臘生 版權(quán)所有，違者必究5-64 對(duì)對(duì)C C2 2，再，再2 2拍后，新指令拍后，新指令( (-I3-I3) )進(jìn)入后：進(jìn)入后： 42 154321987654321tS98I1I1與與I4I4的的F=1,2,4F=1,2,

44、4， I2I2與與I4I4的的F=3,4,6,F=3,4,6,I3I3與與I4I4的的F=1,5,6,8,F=1,5,6,8,新新F=1,2,3,4,5,6,8F=1,2,3,4,5,6,8，C C2222=(10111111)=(10111111)。643 注意：注意：C Cijij為第為第i+j拍后流水線的沖突向量，此時(shí)流水拍后流水線的沖突向量，此時(shí)流水線中已有三條指令，線中已有三條指令， C Cijij用于判斷第四條指令的進(jìn)入。用于判斷第四條指令的進(jìn)入。central south university2022-4-21余臘生 版權(quán)所有，違者必究5-65 c.c.重復(fù)上一步驟，直到不再生成

45、新的沖突向重復(fù)上一步驟，直到不再生成新的沖突向量為止。量為止。1011000110110111101111011011101110111111初始狀態(tài)初始狀態(tài)34342277777（5 5）找出最加調(diào)度方案）找出最加調(diào)度方案 從各個(gè)從各個(gè)閉合回路閉合回路中找出平均間隔最小的一個(gè)。中找出平均間隔最小的一個(gè)。central south university2022-4-21余臘生 版權(quán)所有，違者必究5-66 本例中調(diào)度方案如下：本例中調(diào)度方案如下：調(diào)度策略平均間隔拍數(shù)調(diào)度策略平均間隔拍數(shù)(2, 7)4.50(3, 4, 3, 7) 4.25(2, 2, 7)3.67(4, 3, 7)4.67(3,

46、 4)3.50(4, 7)5.00(3, 7)5.00(7)7.00(3, 4, 7)4.67 可見(jiàn)，調(diào)度方案為（可見(jiàn)，調(diào)度方案為（3，4）。）。 對(duì)非對(duì)非C0開始的調(diào)度方案由開始的調(diào)度方案由流水線控制器流水線控制器完成控制的完成控制的過(guò)渡。過(guò)渡。central south university2022-4-21余臘生 版權(quán)所有，違者必究5-672.2.多功能非線性流水線調(diào)度多功能非線性流水線調(diào)度 如：加（如：加（A）、乘（）、乘（B）雙功能流水線預(yù)約）雙功能流水線預(yù)約表如下：表如下：1234 5S1ABA BS2ABS3BABAV VAAAA =(0110)=(0110)， V VABAB

47、=(1011)=(1011)；V VBBBB =(0110)=(0110)， V VBABA =(1010)=(1010)。V VABAB表示先執(zhí)行表示先執(zhí)行B B后執(zhí)行后執(zhí)行A A；V VBABA表示先執(zhí)行表示先執(zhí)行A A后執(zhí)行后執(zhí)行B B。 M MA A為為A A的初始沖突矩陣的初始沖突矩陣( (從從A A開始開始) )，包含，包含V VAAAA和和V VBABA； M MB B為為B B的初始沖突矩陣的初始沖突矩陣( (從從B B開始開始) )，包含，包含V VBBBB和和V VABAB。central south university2022-4-21余臘生 版權(quán)所有，違者必究5-68

48、 a.a.同單功能調(diào)度方法，首先生成同單功能調(diào)度方法，首先生成n個(gè)個(gè)初始初始沖突矩陣沖突矩陣（按在先功能分類）。（按在先功能分類）。 調(diào)度方案：調(diào)度方案：0110101010110110MAMB b.b.再由初始沖突矩陣按后續(xù)功能再由初始沖突矩陣按后續(xù)功能分類按位右移分類按位右移，形成新的沖突矩陣，最終形成狀態(tài)轉(zhuǎn)換圖。形成新的沖突矩陣，最終形成狀態(tài)轉(zhuǎn)換圖。 新沖突矩陣形成規(guī)則：新沖突矩陣形成規(guī)則： V VB B= =（V Vxx）|M|MB B，V V后續(xù)操作為后續(xù)操作為B B； V VA A= =（V Vxx）|M|MA A，V V后續(xù)操作為后續(xù)操作為A A。central south un

49、iversity2022-4-21余臘生 版權(quán)所有，違者必究5-69011010101011011010110111011111111111011101111010B1,B3A4MAB4B4B1B4MBB5A5A3B1,B3A3A4A1A4 c.c.從閉合回路中找出調(diào)度方案（按功能順序分成從閉合回路中找出調(diào)度方案（按功能順序分成幾種）。幾種）。central south university2022-4-21余臘生 版權(quán)所有，違者必究5-703.3.利用延遲線改善性能利用延遲線改善性能 目的：目的：通過(guò)修改預(yù)約表，減少瓶頸段沖突通過(guò)修改預(yù)約表，減少瓶頸段沖突概率。概率。 分析：分析：設(shè)設(shè)num

50、=max各段使用的次數(shù)各段使用的次數(shù);拍啟動(dòng)一個(gè)任務(wù)每隔最大啟動(dòng)速度numnum1 結(jié)論：結(jié)論：若實(shí)際調(diào)度速度最大啟動(dòng)速度，則流水線若實(shí)際調(diào)度速度最大啟動(dòng)速度，則流水線性能可改善。性能可改善。 方法：方法：以以接近或等于最大啟動(dòng)速度接近或等于最大啟動(dòng)速度為目標(biāo)，重點(diǎn)分為目標(biāo)，重點(diǎn)分析析瓶頸段瓶頸段，在適當(dāng)位置，在適當(dāng)位置插入延遲線插入延遲線作為流水線的一個(gè)作為流水線的一個(gè)段，來(lái)調(diào)整預(yù)約表，以達(dá)到最大速度。段，來(lái)調(diào)整預(yù)約表，以達(dá)到最大速度。central south university2022-4-21余臘生 版權(quán)所有，違者必究5-71 舉例：舉例：流水線預(yù)約表如下圖：流水線預(yù)約表如下圖： 調(diào)

51、度方案：調(diào)度方案：間隔間隔5拍；拍； 最大啟動(dòng)速度：最大啟動(dòng)速度：間隔間隔3拍；拍； 結(jié)果：結(jié)果：性能性能可改善！可改善！ 實(shí)現(xiàn)步驟：實(shí)現(xiàn)步驟： (1)(1)預(yù)約表中設(shè)置第一個(gè)預(yù)約表中設(shè)置第一個(gè)，在目標(biāo)速度拍內(nèi)填，在目標(biāo)速度拍內(nèi)填F F，表示該位置（表示該位置（F F位置）不允許有實(shí)際的位置）不允許有實(shí)際的。central south university2022-4-21余臘生 版權(quán)所有，違者必究5-72F FF F (2)(2)從第二拍開始，有從第二拍開始，有時(shí)填時(shí)填，但不允許，但不允許填在填在F F位置，且在目標(biāo)速度拍內(nèi)填位置，且在目標(biāo)速度拍內(nèi)填F F。 (3)(3)若當(dāng)前若當(dāng)前位置為位

52、置為F F時(shí)，置此位置為時(shí)，置此位置為D D，且在其目，且在其目標(biāo)速度拍內(nèi)填標(biāo)速度拍內(nèi)填F F，重復(fù)，重復(fù)(3)(3)，直到遇到空位置為止。，直到遇到空位置為止。 D DF FF FF FF F F FF FF FF FF Fcentral south university2022-4-21余臘生 版權(quán)所有，違者必究5-73 (4)(4)將將填入空位置，所有相關(guān)填入空位置，所有相關(guān)均右移一均右移一個(gè)位置。個(gè)位置。 D D F FF FF FF FF F (5)(5)重復(fù)重復(fù)(2)(2)(4)(4)，得到新的預(yù)約表。，得到新的預(yù)約表。D D改善后改善后結(jié)果：結(jié)果： 間隔間隔3拍。拍。 D D F

53、 FF FF FF F F Fcentral south university2022-4-21余臘生 版權(quán)所有，違者必究5-74 可改善原因：可改善原因： (1)流水線實(shí)際速度最大啟動(dòng)速度；流水線實(shí)際速度最大啟動(dòng)速度； (2)流水線性能與指令處理過(guò)程流水線性能與指令處理過(guò)程(m)無(wú)關(guān)，無(wú)關(guān)，只與只與t有關(guān)；有關(guān)； (3)流水線中各段及各拍之間為相對(duì)關(guān)系。流水線中各段及各拍之間為相對(duì)關(guān)系。 總結(jié)：總結(jié)：非線性流水線調(diào)度方案；非線性流水線調(diào)度方案； 非線性流水線調(diào)度優(yōu)化。非線性流水線調(diào)度優(yōu)化。central south university余臘生 版權(quán)所有，違者必究Scheduling 靜態(tài)指令

54、調(diào)度靜態(tài)指令調(diào)度 靜態(tài)調(diào)度(static scheduling)是由優(yōu)化的編譯程序來(lái)完成，其基本思想是重排指令序列，拉開具有數(shù)據(jù)相關(guān)的有關(guān)指令間的距離。由于是用編譯程序判測(cè)潛在的數(shù)據(jù)相關(guān)，并在程序運(yùn)行之前完成調(diào)度，故稱為靜態(tài)調(diào)度靜態(tài)調(diào)度。 【例例4】 有A、B、C、D四個(gè)存儲(chǔ)器操作數(shù)，要求完成(AB)(C+D)的運(yùn)算。若原來(lái)程序如圖 (a)所示，為拉開I3與I1、I2的距離，I6與I4、I5的距離，重排后的指令序列如圖 (b)所示。central south university2022-4-21余臘生 版權(quán)所有，違者必究5-76Static SchedulingHave compiler r

55、e-order code to mitigate the effects of data and control dependencesConcepts A comparison of static and dynamic scheduling Each has advantages/disadvantages Bottom line: find good combination of the two Support for high-performance static scheduling Register pressure: large architectural register fi

56、le Branches: compile-time region formation Ambiguous memory dependences: speculative loads Basic scheduling techniques Basic block scheduling Loop unrolling Software pipelining (modulo scheduling) Trace scheduling Predicationcentral south university2022-4-21余臘生 版權(quán)所有，違者必究5-77Static / Dynamic Scheduli

57、ng Dynamic StaticModeratelyScheduled Codedynamicallyre-orderinstructionsFUFUFUFUModeratelyScheduled Codestaticallyre-orderinstructionsFUFUFUFUcompilerhardwarecompilerhardwareVLIWPROCESSORSUPERSCALARPROCESSORcentral south university2022-4-21余臘生 版權(quán)所有，違者必究5-78Hardware(+) Precise view of program at run-

58、time (+) Accurate and adaptable branch prediction (+) Can handle dependences unknown at compile time (e.g., Ambiguous Memory & Control dependences)(-) Limited view of program (-) Limited or no knowledge of program structure (-) Limited (but accurate) scheduling scope (-) Expend resources regeneratin

59、g information available in compiler but not conveyed in the binary(-) Hardware complexity (-) Complex: circuits may impact cycle time (-) Expensive: die area and hardware verificationcentral south university2022-4-21余臘生 版權(quán)所有，違者必究5-79Compiler (+) Global view of the program (+) Better understanding of

60、 program structure and coarse-grain parallelism (loops, functions, etc.) (+) Potentially much larger scheduling scope (+) Very sophisticated analysis possible Not constrained by die area or cycle time Although compile time + memory usage still importantcentral south university2022-4-21余臘生 版權(quán)所有，違者必究5