計算機(jī)體系結(jié)構(gòu)之流水線工作原理與分類

1、Computer Architecture, Autumn 2010北京郵電大學(xué) 計算機(jī)系科學(xué)與技術(shù)系http:/ 流水線基礎(chǔ) (Pipelining Basic)王春露（Prof. Chunlu Wang） Computer Architecture, Autumn 2010流水線技術(shù)流水線技術(shù)相關(guān)性分析技術(shù)相關(guān)性分析技術(shù)超標(biāo)量處理機(jī)超標(biāo)量處理機(jī)超流水線處理機(jī)超流水線處理機(jī)超標(biāo)量超流水線處理機(jī)超標(biāo)量超流水線處理機(jī) 流水線技術(shù)流水線技術(shù)Computer Architecture, Autumn 2010流水線是很自然的流水線是很自然的!洗衣店的例子洗衣店的例子A, B, C, D均有一些衣務(wù)要

2、清洗，甩干，折疊均有一些衣務(wù)要清洗，甩干，折疊清洗要花清洗要花 30 分鐘分鐘甩干要用甩干要用 30 分鐘分鐘疊衣物也需要疊衣物也需要 30 分鐘分鐘還要花費(fèi)還要花費(fèi) 30 分鐘的時間分鐘的時間將衣物放在衣柜里將衣物放在衣柜里ABCDComputer Architecture, Autumn 2010順序操作順序操作洗洗4 個人的衣物，順序操作需要個人的衣物，順序操作需要 8 個小時個小時如果使用流水線作業(yè)如果使用流水線作業(yè), 將需要多少時間呢將需要多少時間呢?30任務(wù)順序BCDA時間30 30303030303030 30303030 3030306 下午下午78910111212 上午上午

3、Computer Architecture, Autumn 2010流水線作業(yè)流水線作業(yè)流水線作業(yè)洗流水線作業(yè)洗4個人的衣物只需要個人的衣物只需要 3.5 個小時個小時!任務(wù)順序122 上午上午6 下午下午78910111時間BCDA3030 3030303030Computer Architecture, Autumn 2010流水線流水線 流水線無法幫助解決單個任務(wù)流水線無法幫助解決單個任務(wù)的的延遲延遲, 有利于減少整個工作有利于減少整個工作全部時間全部時間 多個多個任務(wù)同時操作需要不同任務(wù)同時操作需要不同的資源的資源 可能的加速比可能的加速比 =流水線的段數(shù)流水線的段數(shù) 流水線的速率受流

4、水線的速率受速度最慢速度最慢的流水段的限制的流水段的限制流水線各段長度不均會降低流水線各段長度不均會降低加速比加速比充滿充滿流水線所需的時間和流水線所需的時間和排空排空流水線所需的時間影響流水線所需的時間影響加速比加速比 會由于依賴而造成阻塞會由于依賴而造成阻塞6 下午下午789時間BCDA3030 3030303030任務(wù)順序Computer Architecture, Autumn 2010傳統(tǒng)的流水線執(zhí)行表示傳統(tǒng)的流水線執(zhí)行表示IFetch DcdExecMemWBIFetch DcdExecMemWBIFetch DcdExecMemWBIFetch DcdExecMemWBIFetc

5、h DcdExecMemWBIFetch DcdExecMemWB程序流時間軸Computer Architecture, Autumn 2010為什么采用流水線呢為什么采用流水線呢? 因為有資源空閑因為有資源空閑!指令順序時間 (時鐘周期)Inst 0Inst 1Inst 2Inst 4Inst 3ALUImRegDmRegALUImRegDmRegALUImRegDmRegALUImRegDmRegALUImRegDmRegComputer Architecture, Autumn 2010單時鐘周期單時鐘周期, 多時鐘周期多時鐘周期,同流水線比較同流水線比較. ClkCycle 1多時鐘

6、周期的實現(xiàn)多時鐘周期的實現(xiàn):IfetchRegExecMemWrCycle 2 Cycle 3 Cycle 4 Cycle 5 Cycle 6 Cycle 7 Cycle 8Cycle 9 Cycle 10LoadIfetchRegExecMemWrIfetchRegExecMemLoadStore流水線的實現(xiàn)流水線的實現(xiàn):IfetchRegExecMemWrStoreClk單時鐘周期的實現(xiàn)單時鐘周期的實現(xiàn):LoadStoreWasteIfetchR-typeIfetchRegExecMemWrR-typeCycle 1Cycle 2Computer Architecture, Autumn

7、2010為什么使用流水線為什么使用流水線? 設(shè)想我們要執(zhí)行設(shè)想我們要執(zhí)行 100 條指令條指令 單周期的機(jī)器單周期的機(jī)器45 ns /cycle x 1 CPI x 100 inst = 4500 ns 多周期的機(jī)器多周期的機(jī)器10 ns/cycle x 4.2 CPI (due to inst mix) x 100 inst = 4200 ns 理想的流水線機(jī)器理想的流水線機(jī)器10 ns /cycle x (1 CPI x 100 inst + 4 cycle drain) = 1040 nsComputer Architecture, Autumn 2010Load指令的五個指令的五個階段

8、階段Ifetch: 獲取指令獲取指令 從指令存儲器中獲取指令從指令存儲器中獲取指令Reg /Dec: 獲取寄存器，指令譯碼獲取寄存器，指令譯碼Exec: 計算內(nèi)存地址計算內(nèi)存地址Mem : 從數(shù)據(jù)存儲器中讀數(shù)據(jù)從數(shù)據(jù)存儲器中讀數(shù)據(jù)Wr : 向寄存器文件寫回數(shù)據(jù)向寄存器文件寫回數(shù)據(jù)Cycle 1 Cycle 2 Cycle 3 Cycle 4 Cycle 5IfetchReg /DecExecMemWrLoadComputer Architecture, Autumn 2010Pipelining通過增加指令的執(zhí)行階段增強(qiáng)性能通過增加指令的執(zhí)行階段增強(qiáng)性能理想的加速比是流水線的段數(shù)理想的加速比是

9、流水線的段數(shù). 我們能夠獲得這個加速比嗎我們能夠獲得這個加速比嗎?Instructionfe tchR egA LUD ataaccessR eg8 nsIns tructionfetchR egA LUD ataaccessR eg8 nsInstru ctionfe tch 8 nsTim elw $1, 100($0)lw $2, 200($0)lw $3, 300($0)246810121416182468101214.程序執(zhí)行順序InstructionfetchR egALUD ataaccessR egTim elw $1, 100($0)lw $2, 200($0)lw $3,

10、300($0)2 nsInstructionfetchR egALUD a taaccessR eg2 nsInstructionfetchR egALUD a taaccessR eg2 ns2 ns2 ns2 ns2 nsProgramexecutionorder(in instructions)Computer Architecture, Autumn 2010基本思想基本思想我們要將數(shù)據(jù)通路分割成不同的階段，需要增加些什么?Instructionm emoryAddress4320AddAddres ultSh iftleft 2In structio nMux01AddPC0Writ

11、edataMux1R eg iste rsRe addata 1Re addata 2R eadregis ter 1R eadregis ter 216SignextendW riteregis terW ritedataReaddataAddressDatamemory1ALUresultMuxA LUZeroIF : In s tru c tio n fe tchID : Ins tru c tio n d e co de /r e gis ter file re a dE X : E x e cu te /a d d re ss ca lcu la tionM E M : M e m

12、ory a cc e ssW B : W rite ba c kComputer Architecture, Autumn 2010流水線數(shù)據(jù)通路流水線數(shù)據(jù)通路In s tr uctio nm e m o ryA dd re s s43 20A d dA d dre s ultS hiftle ft 2I n s tru c tio nIF /I DE X /M E MM E M /W BMux01A d dP C0W riteda taMux1R e g iste rsR e a dd a ta 1R e a dd a ta 2R e a dre g is ter 1R e a dre g

13、is ter 21 6S ig ne xte n dW ritere g is terW rited a taR ea dd a ta1A L Ures u ltMuxA L UZ e roID /E XD a tam e m o ryA d d re s sComputer Architecture, Autumn 2010流水線技術(shù)流水線技術(shù) 流水線是一種實現(xiàn)技術(shù)流水線是一種實現(xiàn)技術(shù) 空間并行性空間并行性：設(shè)置多個獨立的操作部件：設(shè)置多個獨立的操作部件 如：如：多操作部件處理機(jī)、超標(biāo)量處理機(jī)多操作部件處理機(jī)、超標(biāo)量處理機(jī) 時間并行性時間并行性：采用流水線技術(shù)：采用流水線技術(shù) 不增加或只增加

14、少量硬件就能使運(yùn)算速度提高幾倍，不增加或只增加少量硬件就能使運(yùn)算速度提高幾倍， 如：如：流水線處理機(jī)、超流水線處理機(jī)流水線處理機(jī)、超流水線處理機(jī)流水線工作原理流水線工作原理流水線的分類流水線的分類線性流水線的性能分析線性流水線的性能分析非線性流水線的調(diào)度技術(shù)非線性流水線的調(diào)度技術(shù)Computer Architecture, Autumn 2010流水線工作原理流水線工作原理1、流水線鎖存器、流水線鎖存器 流水線的每一個階段稱為流水線的每一個階段稱為流水步流水步、流水步驟、流水步驟、流水段流水段、流水流水 線階段、流水功能段、線階段、流水功能段、功能段功能段、流水級流水級、流水節(jié)拍等。、流水節(jié)拍

15、等。 在每一個流水段的末尾或開頭必須設(shè)置一個在每一個流水段的末尾或開頭必須設(shè)置一個( (多個多個) )寄存器，寄存器，稱為稱為 流水寄存器、流水鎖存器、流水閘門寄存器等流水寄存器、流水鎖存器、流水閘門寄存器等。 流水鎖存器會增加每條指令的執(zhí)行時間，但采用流水線之流水鎖存器會增加每條指令的執(zhí)行時間，但采用流水線之 后整個程序的執(zhí)行時間會縮短。后整個程序的執(zhí)行時間會縮短。 為了簡化，在一般流水線中不畫出流水鎖存器。為了簡化，在一般流水線中不畫出流水鎖存器。輸輸入入指指令令分分析析器器分分析析 k k+ +1 1流流水水鎖鎖存存器器指指令令執(zhí)執(zhí)行行部部件件執(zhí)執(zhí)行行 k k流流水水鎖鎖存存器器輸輸出出

16、t t1t t2Computer Architecture, Autumn 20102、流水線的表示方法、流水線的表示方法 流水線的流水線的連接圖連接圖表示方法表示方法 表示流水線的邏輯關(guān)系表示流水線的邏輯關(guān)系 流水線的流水線的時空圖時空圖表示方法表示方法 表示流水線的時間關(guān)系表示流水線的時間關(guān)系 流水線的流水線的預(yù)約表預(yù)約表表示方法表示方法 將在非線性流水線中介紹將在非線性流水線中介紹 一般處理機(jī)的指令流水線為一般處理機(jī)的指令流水線為 4 4 至至 12 12 個級個級 指令流水線等于和大于指令流水線等于和大于8 8級的稱為超流水線處理級的稱為超流水線處理機(jī)機(jī) 輸輸入入取取指指令令譯譯碼碼形

17、形成成操操作作數(shù)數(shù)地地址址取取操操作作數(shù)數(shù)執(zhí)執(zhí)行行保保存存結(jié)結(jié)果果輸輸出出1 12 23 34 45 56 6Computer Architecture, Autumn 20103 3、流水線時空圖、流水線時空圖 一條一條簡單流水線的時空圖簡單流水線的時空圖 一個浮點加法器流水線的時空圖一個浮點加法器流水線的時空圖 由由求階差、對階、尾數(shù)加和規(guī)格化求階差、對階、尾數(shù)加和規(guī)格化4 4個流水段組成個流水段組成 空空間間 指指令令執(zhí)執(zhí)行行部部件件 執(zhí)執(zhí)行行k k 執(zhí)執(zhí)行行k k+ +1 1 執(zhí)執(zhí)行行k k+ +2 2 執(zhí)執(zhí)行行k k+ +3 3 指指令令分分析析部部件件 分分析析k k 分分析析k

18、k+ +1 1 分分析析k k+ +2 2 分分析析k k+ +3 3 0 t1 t2 t3 t4 t5 時時間間 空空間間 規(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 對對 階階 對對階階1 1 對對階階2 2 對對階階3 3 對對階階4 4 對對階階5 5 求求階階差差 求求階階差差1 1 求求階階差差2 2 求求階階差差3 3 求求階階差差4 4 求求階階差差5 5 0 t1 t2 t3 t4 t5 t6

19、t7 t8 時時間間 Computer Architecture, Autumn 20104 4、流水線的主要特點、流水線的主要特點 只有連續(xù)提供同類任務(wù)才能充分發(fā)揮流水線的效率。只有連續(xù)提供同類任務(wù)才能充分發(fā)揮流水線的效率。 對于指令流水線：要盡量減少因條件分支造成的對于指令流水線：要盡量減少因條件分支造成的“斷斷流流” 對于操作部件：主要通過編譯技術(shù)，盡量提供連續(xù)的對于操作部件：主要通過編譯技術(shù)，盡量提供連續(xù)的相同類型的操作。相同類型的操作。 在流水線的每一個流水線段中都要設(shè)置一個流水鎖存器。在流水線的每一個流水線段中都要設(shè)置一個流水鎖存器。 時間開銷：流水線的執(zhí)行時間加長，時間開銷：流水

20、線的執(zhí)行時間加長， 是流水線中需要增加的主要硬件之一。是流水線中需要增加的主要硬件之一。 各各流水段的時間應(yīng)盡量相等流水段的時間應(yīng)盡量相等。 流水線處理機(jī)的基本時鐘周期等于時間最長的流水段流水線處理機(jī)的基本時鐘周期等于時間最長的流水段的時間長度。的時間長度。 流水線需要有流水線需要有“裝入時間裝入時間”和和“排空時間排空時間”。 Latency & throughput? Computer Architecture, Autumn 2010流水線技術(shù)流水線技術(shù)n流水線技術(shù)在流水線技術(shù)在50年代后期被應(yīng)用于處理器設(shè)計年代后期被應(yīng)用于處理器設(shè)計nIBM Stretch-first gene

21、ral-purpose pipelined computernCDC 6600 use load/store design to achieve efficient pipelining.Computer Architecture, Autumn 2010流水線工作原理流水線工作原理流水線的分類流水線的分類線性流水線的性能分析線性流水線的性能分析非線性流水線的調(diào)度技術(shù)非線性流水線的調(diào)度技術(shù)流水線技術(shù)流水線技術(shù)Computer Architecture, Autumn 2010流水線的分類流水線的分類1 1、線性流水線與非線性流水線、線性流水線與非線性流水線 流水線的各個流水段之間是否有反饋信號

22、流水線的各個流水段之間是否有反饋信號 線性流水線線性流水線（Linear PipeliningLinear Pipelining）：）： 每一個流水段都流過一次，而且僅流過一次。每一個流水段都流過一次，而且僅流過一次。 非線性流水線非線性流水線（Nonlinear PipeliningNonlinear Pipelining）：）： 在流水線的某些流水段之間有反饋回路或前饋回路。在流水線的某些流水段之間有反饋回路或前饋回路。 線性流水線能夠用流水線連接圖線性流水線能夠用流水線連接圖唯一唯一表示表示 非線性流水線必須用流水線連接圖流水線預(yù)約表等共同表示非線性流水線必須用流水線連接圖流水線預(yù)約表等

23、共同表示前饋回路前饋回路 輸入輸入S S1 1S S2 2S S3 3 輸出輸出反饋回路反饋回路一種簡單的非線性流水線一種簡單的非線性流水線Computer Architecture, Autumn 20102 2、按照流水線的級別來分、按照流水線的級別來分 處理機(jī)級流水線，又稱為處理機(jī)級流水線，又稱為指令流水線指令流水線。 例如：在采用先行控制器的處理機(jī)中，各功能部件例如：在采用先行控制器的處理機(jī)中，各功能部件之間的流水線之間的流水線 部件級流水線（部件級流水線（操作流水線操作流水線），如浮點加法器流水線。），如浮點加法器流水線。 輸入 先行指令 緩沖棧 先行指令 分析器 先行讀數(shù)棧 先行操

24、作棧 指令 執(zhí)行部件 后行 寫數(shù)棧 輸出 功能: 取指令 指令譯碼, 形成操作數(shù)地址 取操作數(shù) 形成 RR*指令 執(zhí)行算術(shù) 邏輯運(yùn)算 向存儲器 寫結(jié)果 先行控制方式中的指令流水線 輸輸入入 求求階階差差 對對階階 尾尾數(shù)數(shù)加加 規(guī)規(guī)格格化化 輸輸出出 t t1 t t2 t t3 t t4 Computer Architecture, Autumn 2010 處理機(jī)之間的流水線稱為宏流水線（處理機(jī)之間的流水線稱為宏流水線（Macro PipeliningMacro Pipelining） 每個處理機(jī)對同一個數(shù)據(jù)流的不同部分分別進(jìn)行處理。每個處理機(jī)對同一個數(shù)據(jù)流的不同部分分別進(jìn)行處理。 輸輸 入

25、入 處處理理機(jī)機(jī) 1 1 處處理理機(jī)機(jī) 2 2 處處理理機(jī)機(jī) n n 輸輸 出出 功功能能: : 任任務(wù)務(wù)1 1 任任務(wù)務(wù)2 2 任任務(wù)務(wù)n n 存儲器 存儲器 存儲器 Computer Architecture, Autumn 20103 3、單功能流水線與多功能流水線、單功能流水線與多功能流水線 單功能流水線：單功能流水線：只能完成一種固定功能的流水線。只能完成一種固定功能的流水線。 Cray-1Cray-1計算機(jī)種有計算機(jī)種有1212條條 YH-1YH-1計算機(jī)有計算機(jī)有1818條條 PentiumPentium有一條有一條5 5段的定點和一條段的定點和一條8 8段的浮點流水線。段的浮點

26、流水線。 PentiumPentium有兩條定點指令流水線，一條浮點指令流有兩條定點指令流水線，一條浮點指令流水線。水線。 多功能流水線：多功能流水線： 流水線的各段通過不同的連接實現(xiàn)不同的功能。流水線的各段通過不同的連接實現(xiàn)不同的功能。 TexasTexas公司的公司的ASCASC計算機(jī)中的計算機(jī)中的8 8段流水線，能夠?qū)崿F(xiàn)：段流水線，能夠?qū)崿F(xiàn)： 定點加減法、定點乘法、定點加減法、定點乘法、 浮點加法、浮點乘法，浮點加法、浮點乘法， 邏輯運(yùn)算、移位操作、邏輯運(yùn)算、移位操作、 數(shù)據(jù)轉(zhuǎn)換、向量運(yùn)算等。數(shù)據(jù)轉(zhuǎn)換、向量運(yùn)算等。Computer Architecture, Autumn 2010 A

27、B A B A B A B輸 入輸 入輸 入輸 入求 階 差求 階 差求 階 差求 階 差對 階對 階對 階對 階尾 數(shù) 加尾 數(shù) 加尾 數(shù) 加尾 數(shù) 加規(guī) 格 化規(guī) 格 化規(guī) 格 化規(guī) 格 化尾 數(shù) 乘尾 數(shù) 乘尾 數(shù) 乘尾 數(shù) 乘累 加累 加累 加累 加輸 出輸 出輸 出輸 出g=f(A,B)定 點 乘浮 點 加浮 點 點 積(a)功 能 段 間 的 互 連 (b)定 點 乘 法 (c)浮 點 加 法 (d)浮 點 點 積Computer Architecture, Autumn 20104 4、靜態(tài)流水線與動態(tài)流水線、靜態(tài)流水線與動態(tài)流水線 靜態(tài)流水線靜態(tài)流水線：同一段時間內(nèi)，多功能流水

28、線中的各個同一段時間內(nèi)，多功能流水線中的各個功能段只能按照一種固定的方式連接，實現(xiàn)一種固定功能段只能按照一種固定的方式連接，實現(xiàn)一種固定的功能。的功能。 只有連續(xù)出現(xiàn)同一種運(yùn)算時，流水線的效率才能得到只有連續(xù)出現(xiàn)同一種運(yùn)算時，流水線的效率才能得到充分的發(fā)揮。充分的發(fā)揮。空空間間浮浮點點加加法法定定點點乘乘法法輸出1 12 23 3 n n- -1 1 n n1 1累加1 12 2尾數(shù)乘1 12 23 3規(guī)格化1 12 23 3 n n- -1 1 n n尾數(shù)加1 12 23 3 n n- -1 1 n n對階1 12 23 3 n n- -1 1 n n求階差1 12 23 3 n n- -1

29、 1 n n輸入1 12 23 3 n n- -1 1 n n1 12 23 34 4時時間間靜靜態(tài)態(tài)流流水水線線時時空空圖圖Computer Architecture, Autumn 2010 動態(tài)流水線動態(tài)流水線：在同一段時間內(nèi)，多功能流水線中的各在同一段時間內(nèi)，多功能流水線中的各段可以按照不同的方式連接，同時執(zhí)行多種功能。段可以按照不同的方式連接，同時執(zhí)行多種功能。 空空間間 浮浮點點加加法法 定定點點乘乘法法 輸輸入入 1 1 2 2 3 3 n n- -1 1 n n 1 1 2 2 3 3 求求階階差差 1 1 2 2 3 3 4 4 對對階階 1 1 2 2 3 3 4 4 5

30、5 尾尾數(shù)數(shù)加加 1 1 2 2 3 3 n n- -1 1 n n 規(guī)規(guī)格格化化 1 1 2 2 3 3 n n- -1 1 n n 尾尾數(shù)數(shù)乘乘 1 1 2 2 3 3 n n- -1 1 n n 累累加加 1 1 2 2 3 3 n n- -1 1 n n 輸輸入入 1 1 2 2 3 3 n n- -1 1 n n 1 1 2 2 3 3 4 4 5 5 6 6 時時間間 動動態(tài)態(tài)流流水水線線時時空空圖圖 Computer Architecture, Autumn 20105 5、流水線的其他分類方法、流水線的其他分類方法 按照數(shù)據(jù)表示方式：按照數(shù)據(jù)表示方式：標(biāo)量流水線和向量流水線標(biāo)量

31、流水線和向量流水線 按照按照控制方式：控制方式：同步流水線和異步流水線同步流水線和異步流水線 順序流水線與亂序流水線順序流水線與亂序流水線，亂序流水線又稱為無序流水線、，亂序流水線又稱為無序流水線、 錯序流水線或異步流水線等。錯序流水線或異步流水線等。(out of order)(out of order) 輸入輸入 就緒就緒 回答回答 S1 就緒就緒 回答回答 S2 就緒就緒 回答回答 Sn 輸出輸出 就緒就緒 回答回答 一種異步流水線 Computer Architecture, Autumn 2010流水線工作原理流水線工作原理流水線的分類流水線的分類線性流水線的性能分析線性流水線的性能

32、分析非線性流水線的調(diào)度技術(shù)非線性流水線的調(diào)度技術(shù)標(biāo)量處理機(jī)標(biāo)量處理機(jī)流水線技術(shù)流水線技術(shù)Computer Architecture, Autumn 2010 線性流水線的性能分析線性流水線的性能分析 衡量流水線性能的主要指標(biāo)有：衡量流水線性能的主要指標(biāo)有：吞吐率、加速比和效率吞吐率、加速比和效率。1 1、吞吐率（、吞吐率（Though PutThough Put） 計算流水線吞吐率的最基本公式：計算流水線吞吐率的最基本公式： 其中：其中：n n為任務(wù)數(shù)，為任務(wù)數(shù)，k k為完成為完成n n個任務(wù)所用的時間。個任務(wù)所用的時間。 各段執(zhí)行時間相等，輸入各段執(zhí)行時間相等，輸入連續(xù)連續(xù)任務(wù)情況下：任務(wù)情

33、況下： 完成完成n n個連續(xù)任務(wù)需要的總時間為：個連續(xù)任務(wù)需要的總時間為：Tk（kn1） t 其中：其中：k 為流水線的段數(shù)，為流水線的段數(shù)， t t為時鐘周期。為時鐘周期。 空空間間S4123n-1nS3123n-1nS2123n-1nS11 12 23 3n n- -1 1n n時時間間kt(n1)tnt(k1)tTT PnTkComputer Architecture, Autumn 2010 吞吐率為：吞吐率為： 最大吞吐率為：最大吞吐率為： 各段執(zhí)行時間不相等，輸入連續(xù)任務(wù)情況下：各段執(zhí)行時間不相等，輸入連續(xù)任務(wù)情況下： 吞吐率為：吞吐率為： 最大吞吐率為：最大吞吐率為： 流水線各段

34、執(zhí)行時間不相等的解決辦法流水線各段執(zhí)行時間不相等的解決辦法TPnknt() 1 nTPLimnkntt max() 11),max()1(211kkiitttntnTP ),max(121ktttTP 輸入輸入S1S2S3S4輸出輸出 t1 t t23 t t3 t t4 tComputer Architecture, Autumn 2010 (1)(1)將流水線的將流水線的“瓶頸瓶頸”部分再細(xì)分部分再細(xì)分（如果可分的話）。（如果可分的話）?？湛臻g間S4123nS3123nS2123nS1123n時時間間 kiit1（n1） t2Tk各段執(zhí)行時間不相等的流水線及其時空圖輸輸入入S1S2-1S2

35、-2S2-3S3S4輸輸出出 t t t t t t“瓶瓶頸頸”流流水水段段再再次次細(xì)細(xì)分分 S2 (3 t)Computer Architecture, Autumn 2010Computer Architecture, Autumn 20102 2、加速比（、加速比（SpeedupSpeedup） 計算流水線加速比的基本公式：計算流水線加速比的基本公式： 各段執(zhí)行時間相等，輸入連續(xù)任務(wù)情況下：各段執(zhí)行時間相等，輸入連續(xù)任務(wù)情況下： 加速比為：加速比為： 最大加速比為：最大加速比為： 各段執(zhí)行時間不相等，輸入連續(xù)任務(wù)情況下各段執(zhí)行時間不相等，輸入連續(xù)任務(wù)情況下, , 實際加速實際加速比為：比

36、為：STTk順序執(zhí)行時間流水線執(zhí)行時間0Sk ntkntk nkn () 11SLimk nknknmax1Snttntttiikiikk 11121() max(, ,）Computer Architecture, Autumn 2010 當(dāng)流水線段數(shù)增加時，需要連續(xù)輸入的任務(wù)數(shù)也必須當(dāng)流水線段數(shù)增加時，需要連續(xù)輸入的任務(wù)數(shù)也必須增加增加 加加速速比比 S 10 加加 k=10 段段 8 速速 6 比比 k=6 段段 4 2 1 1 2 4 8 16 32 64 128 n 任任 務(wù)務(wù) 個個 數(shù)數(shù)Computer Architecture, Autumn 2010Computer Archi

37、tecture, Autumn 2010 流水線各段的設(shè)備量或者各段的價格不相等時：流流水水線線的的效效率率為為：E空區(qū)個流水段的總的加權(quán)時區(qū)個任務(wù)占用的加權(quán)時空kn即：), ,max() 121111nkiikiikiiitttntatanE（其中，aik，且aiik1k。 流流水水線線的的吞吞吐吐率率、加加速速比比與與效效率率的的關(guān)關(guān)系系：因為：TPnknt() 1 ，1nknkS，Enkn1 因此：ETPt，SkEComputer Architecture, Autumn 20104 4、流水線最佳段數(shù)的選擇、流水線最佳段數(shù)的選擇 采用順序執(zhí)行方式完成一個任務(wù)的時間為采用順序執(zhí)行方式完成

38、一個任務(wù)的時間為t t 在同等速度的在同等速度的k段流水線上執(zhí)行一個任務(wù)的時間為：段流水線上執(zhí)行一個任務(wù)的時間為：tkd 其中：其中：d為流水鎖存器的延遲時間為流水鎖存器的延遲時間 流水線的最大吞吐率為：流水線的最大吞吐率為： 流水線的總價格估計為：流水線的總價格估計為：Cab k， 其中：其中：a為所有功能段本身的總價格，為所有功能段本身的總價格，b為每個鎖存器的價格為每個鎖存器的價格 A.G.Larson把流水線的性把流水線的性 能價格比能價格比PCR定義為：定義為： 求得到求得到PCR的最大值為：的最大值為：Ptkd1/PCRPCt kd abk11/ktadb0 性能價格比PCR 峰值

39、 最佳值(k0) 流水線段數(shù)kComputer Architecture, Autumn 20105 5、流水線性能分析舉例、流水線性能分析舉例 對于單功能線性流水線，輸入連續(xù)任務(wù)的情況，通過對于單功能線性流水線，輸入連續(xù)任務(wù)的情況，通過上面給出的公式很容易計算出流水線的吞吐率、加速比上面給出的公式很容易計算出流水線的吞吐率、加速比和效率。和效率。例：用一條例：用一條4 4段浮點加法器流水線求段浮點加法器流水線求8 8個浮點數(shù)的和：個浮點數(shù)的和： Z ZA AB BC CD DE EF FG GH H解：解：Z Z （A AB B）（）（C CD D） （E EF F）（）（G GH H） 0

40、00)()()(0)(1)(0)1/1(2222kbdatkbdbtkkbdadkkbdbtkadkatdktbkbkadkbkadktbkadktkbkadktdbtakComputer Architecture, Autumn 2010 空間空間 周期周期 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 1010 1111 1212 1313 1414 1515 規(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 對階對階 1 1 2 2 3 3 4 4 5 5 6 6 7 7

41、求階差求階差 1 1 2 2 3 3 4 4 5 5 6 6 7 7 時間時間 加數(shù)加數(shù) A C E G A+B E+F A+B+C+DA C E G A+B E+F A+B+C+D 加數(shù)加數(shù) B D F H B D F H C+D G+H E+F+G+H C+D G+H E+F+G+H 結(jié)果結(jié)果 A+B C+D E+F g+H A+B+C+D Z A+B C+D E+F g+H A+B+C+D Z E+F+G+HE+F+G+H 用一條用一條 4 4 段浮點加法器流水線求段浮點加法器流水線求 8 8 個數(shù)之和的流水線時空圖個數(shù)之和的流水線時空圖 7 個個浮浮點點加加法法共共用用了了 15 個個

42、時時鐘鐘周周期期。 流流水水線線的的吞吞吐吐率率為為：TPnTttk7150 471 流流水水線線的的加加速速比比為為：STTttk047151 87 流流水水線線的的效效率率為為：ETk Tttk0474150 47 Computer Architecture, Autumn 2010流水線工作原理流水線工作原理流水線的分類流水線的分類線性流水線的性能分析線性流水線的性能分析非線性流水線的調(diào)度技術(shù)非線性流水線的調(diào)度技術(shù) 流水線技術(shù)流水線技術(shù)Computer Architecture, Autumn 2010非線性流水線的調(diào)度技術(shù)非線性流水線的調(diào)度技術(shù) 非線性流水線調(diào)度的任務(wù)是要找出一個最小的

43、循環(huán)周期，非線性流水線調(diào)度的任務(wù)是要找出一個最小的循環(huán)周期，按照這周期向流水線輸入新任務(wù)，流水線的各個功能段都按照這周期向流水線輸入新任務(wù)，流水線的各個功能段都不會發(fā)生沖突，而且流水線的吞吐率和效率最高。不會發(fā)生沖突，而且流水線的吞吐率和效率最高。1 1、非線性流水線的表示非線性流水線的表示 線性流水線能夠用流水線連接圖唯一表示線性流水線能夠用流水線連接圖唯一表示 連接圖不能用唯一表示非線性流水線的工作流程，因此，連接圖不能用唯一表示非線性流水線的工作流程，因此，引入流水線預(yù)約表引入流水線預(yù)約表時時間間功功能能段段1234567S1S2S3S4Computer Architecture, Au

44、tumn 2010 輸輸出出輸輸入入S1S2S3S4前饋線反饋線 與流水線預(yù)約表對應(yīng)的流水線連接圖與流水線預(yù)約表對應(yīng)的流水線連接圖Computer Architecture, Autumn 2010時時 間間功功 能能 段段1234567S1S2S3S4 輸輸出出S4輸輸入入S1S2S3前前饋饋線線反反饋饋線線 輸輸出出輸輸入入S1S2S3S4前饋線反饋線 一張預(yù)約表可能與多個流水線連接圖相對應(yīng)一張預(yù)約表可能與多個流水線連接圖相對應(yīng)Computer Architecture, Autumn 2010時時間間功功能能段段1234567S1S2S3S4 輸輸出出輸輸入入S1S2S3S4前饋線反饋線

45、 一個流水線連接圖對應(yīng)與多張預(yù)約表一個流水線連接圖對應(yīng)與多張預(yù)約表時時間間功功能能段段1 12 23 34 45 56 67 7S1S2S3S4Computer Architecture, Autumn 20102 2、非線性流水線的沖突、非線性流水線的沖突 流水線的啟動距離：流水線的啟動距離：連續(xù)輸入兩個任務(wù)之間的時間連續(xù)輸入兩個任務(wù)之間的時間間隔間隔 流水線的沖突：幾個任務(wù)爭用同一個流水段流水線的沖突：幾個任務(wù)爭用同一個流水段啟啟動動距距離離為為 3 3 的的流流水水線線沖沖突突情情況況時時間間功功能能段段1 12 23 34 45 56 67 78 89 91 10 01 11 1S1X

46、 X1 1X X1 1X X2 2X X1 1X X2 2X X3 3X X2 2X X3 3X X4 4S2X X1 1X X1 1X X2 2X X2 2X X3 3X X3 3X X4 4S3X X1 1X X2 2X X1 1X X3 3X X2 2X X4 4S4X X1 1X X2 2X X3 3啟啟動動距距離離為為 2 2 的的流流水水線線沖沖突突情情況況時時間間功功能能段段1 12 23 34 45 56 67 78 89 91 10 01 11 1S S1 1X X1 1X X2 2X X1 1X X3 3X X2 2X X1 1X X4 4X X3 3X X2 2X X5

47、5X X4 4X X3 3X X6 6S S2 2X X1 1X X2 2X X1 1X X3 3X X2 2X X4 4X X3 3X X5 5X X4 4S S3 3X X1 1X X2 2X X1 1X X3 3X X2 2X X4 4X X3 3X X5 5S S4 4X X1 1X X2 2X X3 3X X4 4X X5 5Computer Architecture, Autumn 2010啟啟動動距距離離為為 5 5 時時的的流流水水線線不不沖沖突突時時間間功功能能段段1 12 23 34 45 56 67 78 89 91 10 01 11 1S S1 1X X1 1X X1

48、1X X2 2X X1 1X X2 2X X3 3S S2 2X X1 1X X1 1X X2 2X X2 2S S3 3X X1 1X X1 1X X2 2X X2 2S S4 4X X1 1X X2 2啟啟動動周周期期重重復(fù)復(fù)啟啟動動周周期期啟啟動動距距離離為為( (1 1, ,7 7) )循循環(huán)環(huán)時時的的流流水水線線預(yù)預(yù)約約表表時時間間功功能能段段1 12 23 34 45 56 67 78 89 91 10 01 11 11 12 21 13 31 14 41 15 51 16 6S S1 1X X1 1X X2 2X X1 1X X2 2X X1 1X X2 2X X3 3X X4

49、4X X3 3X X4 4X X3 3X X4 4S S2 2X X1 1X X2 2X X1 1X X2 2X X3 3X X4 4X X3 3X X4 4S S3 3X X1 1X X2 2X X1 1X X2 2X X3 3X X4 4X X3 3X X4 4S S4 4X X1 1X X2 2X X3 3X X4 4啟啟動動周周期期重重復(fù)復(fù)啟啟動動周周期期Computer Architecture, Autumn 20103 3、無沖突調(diào)度方法、無沖突調(diào)度方法, ,由由E.S.DavidsonE.S.Davidson及其學(xué)生于及其學(xué)生于19711971年年提出提出 非線性流水線的非線性

50、流水線的禁止啟動集合禁止啟動集合：預(yù)約表中每一行任意：預(yù)約表中每一行任意兩個兩個“” 之間的距離都計算出來，去掉重復(fù)的。上例之間的距離都計算出來，去掉重復(fù)的。上例中為中為（3 3，4 4，6 6） 由由禁止啟動集合禁止啟動集合得到得到?jīng)_突向量沖突向量：C（CmCm-1C2C1） 其中：其中：m是是禁止向量中的最大值。如果禁止向量中的最大值。如果i在禁止向量中，在禁止向量中， 則則Ci1，否則，否則Ci0。上。上例中例中 C C（101100101100）。）。 由沖突向量構(gòu)造狀態(tài)圖：由沖突向量構(gòu)造狀態(tài)圖： 把沖突向量送入一個把沖突向量送入一個m位邏輯右移移位器；如果移位器移出位邏輯右移移位器；

51、如果移位器移出0 0，用移位器中的值與用移位器中的值與初始沖突向量初始沖突向量作作“按位或按位或”運(yùn)算，得到一個新的運(yùn)算，得到一個新的沖突向量；否則不作任何處理；如此重復(fù)沖突向量；否則不作任何處理；如此重復(fù)m次。次。 對于中間形成的每一個新的沖突向量，也要按照這一方法進(jìn)行處理。對于中間形成的每一個新的沖突向量，也要按照這一方法進(jìn)行處理。 在初始沖突向量和所有的新形成的沖突向量之間用帶箭頭的線連在初始沖突向量和所有的新形成的沖突向量之間用帶箭頭的線連接，當(dāng)新形成的沖突向量出現(xiàn)重復(fù)時可以合并到一起。接，當(dāng)新形成的沖突向量出現(xiàn)重復(fù)時可以合并到一起。Computer Architecture, Aut

52、umn 2010例：一條有例：一條有4 4個功能段的非線性流水線，每個功能段的延遲個功能段的非線性流水線，每個功能段的延遲 時間都相等，它的預(yù)約表如下：時間都相等，它的預(yù)約表如下： (1) (1) 寫出流水線的禁止集合和初始沖突向量。寫出流水線的禁止集合和初始沖突向量。 (2) (2) 畫出調(diào)度流水線的狀態(tài)圖。畫出調(diào)度流水線的狀態(tài)圖。 (3) (3) 求流水線的最小啟動循環(huán)和最小平均啟動距離。求流水線的最小啟動循環(huán)和最小平均啟動距離。 (4) (4) 求平均啟動距離最小的恒定循環(huán)。求平均啟動距離最小的恒定循環(huán)。解：解：(1)(1)禁止集合為：（禁止集合為：（2 2，4 4，6 6） 初始沖突向

53、量：初始沖突向量：101010101010 (2) (2)初始沖突向量邏輯右移初始沖突向量邏輯右移2 2、4 4、6 6位時，不作任何處理，位時，不作任何處理， 邏輯右移邏輯右移1 1、3 3、5 5和大于等于和大于等于7 7時，要進(jìn)行處理。時，要進(jìn)行處理。時 間 功能段 1 2 3 4 5 6 7 S1 X X S2 X X S3 X X S4 X Computer Architecture, Autumn 2010初始沖突向量右移初始沖突向量右移1 1位之后：位之后：010101010101101010101010111111111111，初始沖突向量右移初始沖突向量右移3 3位之后：位之

54、后：000101000101101010101010101111101111，初始沖突向量右移初始沖突向量右移5 5位之后：位之后：000001000001101010101010101011101011，初始沖突向量右移初始沖突向量右移7 7位或大于位或大于7 7位后：還原到它本身。位后：還原到它本身。中間沖突向量中間沖突向量101111101111右移右移5 5位之后：位之后：000001000001101010101010101011101011，中間沖突向量中間沖突向量101011101011右移右移3 3位之后：位之后：00010100010110101010101010111110

55、1111，中間沖突向量中間沖突向量101011101011右移右移5 5位之后：位之后：000001000001101010101010101011101011。7*07*153 7*7*15 305非非線線性性流流水水線線的的狀狀態(tài)態(tài)圖圖Computer Architecture, Autumn 2010 預(yù)約表與狀態(tài)圖是唯一對應(yīng)，預(yù)約表與狀態(tài)圖是唯一對應(yīng)， 但不同的預(yù)約表也可能有相同的狀態(tài)圖。但不同的預(yù)約表也可能有相同的狀態(tài)圖。 簡單循環(huán)：狀態(tài)圖中各種沖突向量只經(jīng)過一次的啟動循環(huán)。簡單循環(huán)：狀態(tài)圖中各種沖突向量只經(jīng)過一次的啟動循環(huán)。 簡單循環(huán)的個數(shù)是有限的簡單循環(huán)的個數(shù)是有限的, ,由簡單

56、循環(huán)計算平均啟動距離。由簡單循環(huán)計算平均啟動距離。(3)(3)最小的啟動循環(huán)為（最小的啟動循環(huán)為（1 1，7 7）和（）和（3 3，5 5）, ,平均啟動距離為平均啟動距離為 4 4。(4)(4)啟動距離最小的恒定循環(huán)是（啟動距離最小的恒定循環(huán)是（5 5）。）。簡簡單單循循環(huán)環(huán)平平均均啟啟動動距距離離（1 1，7 7）4 4（3 3，7 7）5 5（5 5，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 7Computer Architecture, Autumn 2010最小啟動循環(huán)最小啟動循環(huán)(3,5)(3

57、,5)的流水線工作狀態(tài)的流水線工作狀態(tài)時間時間功能段功能段1 12 23 34 45 56 67 78 89 91010 1111 1212 1313 1414 1515S S1 1X X1 1X X2 2X X1 1X X3 3X X2 2X X4 4X X3 3S S2 2X X1 1X X2 2X X1 1X X2 2X X3 3X X4 4X X3 3S S3 3X X1 1X X1 1X X2 2X X2 2X X3 3X X3 3X X4 4S S4 4X X1 1X X2 2X X3 3X X4 4啟動周期啟動周期重復(fù)啟動周期重復(fù)啟動周期最小啟動循環(huán)最小啟動循環(huán)(1,7)(1,7

58、)的流水線工作狀態(tài)的流水線工作狀態(tài)時間時間功能段功能段1 12 23 34 45 56 67 78 89 9101011111212131314141515S S1 1X X1 1X X2 2X X1 1X X2 2X X3 3X X4 4X X3 3S S2 2X X1 1X X2 2X X1 1X X2 2X X3 3X X4 4X X3 3X X4 4S S3 3X X1 1X X2 2X X1 1X X2 2X X3 3X X4 4X X3 3X X4 4S S4 4X X1 1X X2 2X X3 3X X4 4啟動周期啟動周期重復(fù)啟動周期重復(fù)啟動周期Computer Archite

59、cture, Autumn 2010恒恒定定啟啟動動循循環(huán)環(huán)( (5 5) )的的流流水水線線工工作作狀狀態(tài)態(tài)時時間間功功能能段段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 5S S1 1X X1 1X X2 2X X1 1X X3 3X X2 2S S2 2X X1 1X X1 1X X2 2X X2 2X X3 3S S3 3X X1 1X X1 1X X2 2X X2 2X X3 3X X3 3S S4 4X X1 1X X2 2X X3 3啟啟動動周周期期重重復(fù)復(fù)啟啟動動周周期期Computer

60、Architecture, Autumn 20104 4、優(yōu)化調(diào)度方法、優(yōu)化調(diào)度方法 L.E.SharL.E.Shar于于19721972年提出流水線最小平均啟動距離的限制范圍年提出流水線最小平均啟動距離的限制范圍 (1)(1)下限是預(yù)約表中任意一行里下限是預(yù)約表中任意一行里“”的最多個數(shù)的最多個數(shù)。 (2)(2)小于或等于狀態(tài)圖中任意一個簡單循環(huán)的平均啟動距離。小于或等于狀態(tài)圖中任意一個簡單循環(huán)的平均啟動距離。 (3)(3)最小平均啟動距離的上限是沖突向量中最小平均啟動距離的上限是沖突向量中1 1的個數(shù)再加上的個數(shù)再加上1 1。 19921992年，年，L.E.SharL.E.Shar又證明了上述限