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

1、蘭州理工大學(xué)蘭州理工大學(xué)蘭州理工大學(xué) 包仲賢包仲賢包仲賢第第5章章 標(biāo)量處理機(jī)標(biāo)量處理機(jī)5.1 先行控制技術(shù)先行控制技術(shù)5.2 流水線技術(shù)流水線技術(shù)5.3 相關(guān)性分析技術(shù)相關(guān)性分析技術(shù)5.4 超標(biāo)量處理機(jī)超標(biāo)量處理機(jī)5.5 超流水線處理機(jī)超流水線處理機(jī)5.6 超標(biāo)量超流水線處理機(jī)超標(biāo)量超流水線處理機(jī)蘭州理工大學(xué)蘭州理工大學(xué)蘭州理工大學(xué) 包仲賢包仲賢包仲賢5.1 5.1 先行控制技術(shù)先行控制技術(shù)5.1.1 指令的重疊執(zhí)行方式指令的重疊執(zhí)行方式5.1.2 先行控制方式的原理先行控制方式的原理5.1.3 處理機(jī)結(jié)構(gòu)處理機(jī)結(jié)構(gòu)5.1.4 指令執(zhí)行序列指令執(zhí)行序列5.1.5 先行緩沖棧先行緩沖棧蘭州理工

2、大學(xué)蘭州理工大學(xué)蘭州理工大學(xué) 包仲賢包仲賢包仲賢5.1.1 5.1.1 指令的重疊執(zhí)行方式指令的重疊執(zhí)行方式1.1.順序執(zhí)行方式順序執(zhí)行方式執(zhí)行執(zhí)行n n條指令所用的時(shí)間為：條指令所用的時(shí)間為： 如果每段時(shí)間都為t，則執(zhí)行n條指令所用的時(shí)間為：T3 n t3 n t主要優(yōu)點(diǎn)：主要優(yōu)點(diǎn)：控制簡(jiǎn)單，節(jié)省設(shè)備控制簡(jiǎn)單，節(jié)省設(shè)備主要缺點(diǎn)：主要缺點(diǎn)：速度慢，功能部件的利用率低速度慢，功能部件的利用率低Ttttiiiin(取指令分析執(zhí)行）1 取取指指令令k k 分分析析k k 執(zhí)執(zhí)行行k k 取取指指令令k k+ +1 1 分分析析k k+ +1 1 執(zhí)執(zhí)行行k k+ +1 1 蘭州理工大學(xué)蘭州理工大學(xué)蘭

3、州理工大學(xué) 包仲賢包仲賢包仲賢2.2.一次重疊執(zhí)行方式一次重疊執(zhí)行方式如果兩個(gè)過(guò)程的時(shí)間相等，則執(zhí)行n條指令的時(shí)間為：T(1+2n)t1+2n)t主要優(yōu)點(diǎn)：主要優(yōu)點(diǎn)： 指令的執(zhí)行時(shí)間縮短，指令的執(zhí)行時(shí)間縮短， 功能部件的利用率明顯提高。功能部件的利用率明顯提高。主要缺點(diǎn)：主要缺點(diǎn)： 需要增加一些硬件，需要增加一些硬件， 控制過(guò)程稍復(fù)雜?？刂七^(guò)程稍復(fù)雜。取指令取指令 k k分析分析 k k執(zhí)行執(zhí)行 k k取取指指令令 k k+ +1 1分析分析 k+1k+1執(zhí)行執(zhí)行 k+1k+1取指令取指令k+2k+2分析分析 k+2k+2執(zhí)行執(zhí)行 k+2k+2蘭州理工大學(xué)蘭州理工大學(xué)蘭州理工大學(xué) 包仲賢包仲賢

4、包仲賢3.3.二次重疊執(zhí)行方式二次重疊執(zhí)行方式如果三個(gè)過(guò)程的時(shí)間相等，執(zhí)行n條指令的時(shí)間為：T(2 2n n）t t在理想情況下，處理機(jī)中同時(shí)有三條指令在執(zhí)行。處理機(jī)的結(jié)構(gòu)要作比較大的改變，需要采用先行處理機(jī)的結(jié)構(gòu)要作比較大的改變，需要采用先行控制技術(shù)?？刂萍夹g(shù)。 取取指指令令k k分分析析k k執(zhí)執(zhí)行行k k取取指指令令k k+ +1 1分分析析k k+ +1 1執(zhí)執(zhí)行行k k+ +1 1取取指指令令k k+ +2 2分分析析k k+ +2 2執(zhí)執(zhí)行行k k+ +2 2二二次次重重疊疊執(zhí)執(zhí)行行方方式式蘭州理工大學(xué)蘭州理工大學(xué)蘭州理工大學(xué) 包仲賢包仲賢包仲賢5.1.2 5.1.2 先行控制方式

5、的原理先行控制方式的原理1.1.采用二次重疊執(zhí)行方式必須解決兩個(gè)問(wèn)題：采用二次重疊執(zhí)行方式必須解決兩個(gè)問(wèn)題：(1)(1)有獨(dú)立的取指令部件、指令分析部件和指令執(zhí)有獨(dú)立的取指令部件、指令分析部件和指令執(zhí)行部件行部件 把一個(gè)集中的指令控制器，分解成三個(gè)獨(dú)立的控制器： 存儲(chǔ)控制器、指令控制器、運(yùn)算控制器存儲(chǔ)控制器、指令控制器、運(yùn)算控制器(2)(2)要解決訪問(wèn)主存儲(chǔ)器的沖突問(wèn)題要解決訪問(wèn)主存儲(chǔ)器的沖突問(wèn)題 取指令、分析指令、執(zhí)行指令都可能要訪問(wèn)存儲(chǔ)器蘭州理工大學(xué)蘭州理工大學(xué)蘭州理工大學(xué) 包仲賢包仲賢包仲賢2.2.解決訪存沖突的方法：解決訪存沖突的方法：(1)(1)采用低位交叉存取方式采用低位交叉存取方

6、式： 這種方法不能根本解決沖突問(wèn)題。指令、讀操作數(shù)、寫(xiě)結(jié)果。(2)(2)兩個(gè)獨(dú)立的存儲(chǔ)器兩個(gè)獨(dú)立的存儲(chǔ)器：獨(dú)立的指令存儲(chǔ)器和數(shù)據(jù)獨(dú)立的指令存儲(chǔ)器和數(shù)據(jù)存儲(chǔ)器。存儲(chǔ)器。如果再規(guī)定，執(zhí)行指令所需要的操作數(shù)和執(zhí)行結(jié)果只寫(xiě)到通用寄存器，則取指令、分析指令和執(zhí)行指令就可以同時(shí)進(jìn)行。在許多高性能處理機(jī)中，有獨(dú)立的指令Cache和數(shù)據(jù)Cache。這種結(jié)構(gòu)被稱為哈佛結(jié)構(gòu)。蘭州理工大學(xué)蘭州理工大學(xué)蘭州理工大學(xué) 包仲賢包仲賢包仲賢(3)(3)采用先行控制技術(shù)采用先行控制技術(shù) 采用先行控制技術(shù)的關(guān)鍵是緩沖技術(shù)和預(yù)處理采用先行控制技術(shù)的關(guān)鍵是緩沖技術(shù)和預(yù)處理技術(shù)。技術(shù)。緩沖技術(shù)通常用在工作速度不固定的兩個(gè)功能部件之間

7、。設(shè)置緩沖棧的目的是用來(lái)以平滑功能部件之間的工作速度。在采用了緩沖技術(shù)和預(yù)處理技術(shù)之后，運(yùn)算器能夠?qū)Ｐ挠跀?shù)據(jù)的運(yùn)算，從而大幅度提高程序的執(zhí)行速度。蘭州理工大學(xué)蘭州理工大學(xué)蘭州理工大學(xué) 包仲賢包仲賢包仲賢 空間并行性空間并行性：設(shè)置多個(gè)獨(dú)立的操作部件設(shè)置多個(gè)獨(dú)立的操作部件 時(shí)間并行性時(shí)間并行性：分時(shí)使用同一個(gè)部件的不同部分分時(shí)使用同一個(gè)部件的不同部分 5.2.1 流水線工作原理流水線工作原理 5.2.2 流水線的分類流水線的分類 5.2.3 線性流水線的性能分析線性流水線的性能分析 5.2.4 非線性流水線的調(diào)度非線性流水線的調(diào)度5.2 5.2 流水線技術(shù)流水線技術(shù)蘭州理工大學(xué)蘭州理工大學(xué)蘭州理

8、工大學(xué) 包仲賢包仲賢包仲賢5.2.1 5.2.1 流水線工作原理流水線工作原理1. 1. 流水寄存器流水寄存器流水線的每一個(gè)階段稱為流水步流水步、流水步驟、流流水段水段、流水線階段、流水功能段、功能段功能段、流流水級(jí)水級(jí)、流水節(jié)拍等。在每一個(gè)流水段的末尾或開(kāi)頭必須設(shè)置一個(gè)寄存器，稱為流水寄存器、流水鎖存器、流水閘門(mén)流水寄存器、流水鎖存器、流水閘門(mén)寄存器等寄存器等。加入流水寄存器，會(huì)增加指令的執(zhí)行時(shí)間。在一般流水線時(shí)空?qǐng)D中不畫(huà)出流水寄存器。蘭州理工大學(xué)蘭州理工大學(xué)蘭州理工大學(xué) 包仲賢包仲賢包仲賢2.2.一種指令流水線一種指令流水線一般4至12個(gè)流水段，8個(gè)流水段的稱為超流水線處理機(jī)3.3.流水線

9、時(shí)空?qǐng)D流水線時(shí)空?qǐng)D 空空間間 執(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 k+ +1 1 分分析析k k+ +2 2 分分析析k k+ +3 3 取取指指令令部部件件 取取指指令令k k 取取指指令令k k+ +1 1 取取指指令令k k+ +2 2 取取指指令令k k+ +3 3 0 t1 t2 t3 t4 t5 時(shí)時(shí)間間 輸輸入入 輸輸出出 取取指指令令 i 分分析析 i 執(zhí)執(zhí)行行 i 流流水水線線 寄寄存存器器 流流水水線線 寄寄存存器器 t 蘭州理工大學(xué)蘭州理工大學(xué)蘭

10、州理工大學(xué) 包仲賢包仲賢包仲賢 一個(gè)浮點(diǎn)加法器流水線的時(shí)空?qǐng)D一個(gè)浮點(diǎn)加法器流水線的時(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ì) 階階 1 1 對(duì)對(duì) 階階 2 2 對(duì)對(duì) 階階 3 3 對(duì)對(duì) 階階 4 4 對(duì)對(duì) 階階 5 5 求求 階階 差差 求求 階階 差差 1 1 求求 階階 差差 2 2 求求 階階 差差 3

11、 3 求求 階階 差差 4 4 求求 階階 差差 5 5 0 t1 t2 t3 t4 t5 t6 t7 t8 時(shí)時(shí) 間間 蘭州理工大學(xué)蘭州理工大學(xué)蘭州理工大學(xué) 包仲賢包仲賢包仲賢4.4.流水線的主要特點(diǎn)流水線的主要特點(diǎn)只有連續(xù)提供同類任務(wù)才能發(fā)揮流水線效率只有連續(xù)提供同類任務(wù)才能發(fā)揮流水線效率盡量減少因條件分支造成的“斷流”通過(guò)編譯技術(shù)提供連續(xù)的相同類型操作每個(gè)流水線段都要設(shè)置一個(gè)流水寄存器每個(gè)流水線段都要設(shè)置一個(gè)流水寄存器時(shí)間開(kāi)銷(xiāo)：流水線的執(zhí)行時(shí)間加長(zhǎng)是流水線中需要增加的主要硬件各流水段的時(shí)間應(yīng)盡量相等各流水段的時(shí)間應(yīng)盡量相等 流水線處理機(jī)的基本時(shí)鐘周期等于時(shí)間最長(zhǎng)的流水段的時(shí)間長(zhǎng)度。流水線

12、需要有流水線需要有“裝入時(shí)間裝入時(shí)間”和和“排空時(shí)間排空時(shí)間” 蘭州理工大學(xué)蘭州理工大學(xué)蘭州理工大學(xué) 包仲賢包仲賢包仲賢5.2.2 5.2.2 流水線的分類流水線的分類1.1.線性流水線與非線性流水線線性流水線與非線性流水線 流水線的各個(gè)流水段之間是否有反饋信號(hào)線性流水線線性流水線（Linear Pipelining）： 每一個(gè)流水段都流過(guò)一次，而且僅流過(guò)一次非線性流水線非線性流水線（Nonlinear Pipelining）： 某些流水段之間有反饋回路或前饋回路。線性流水線能夠用流水線連接圖唯一表示非線性流水線必須用流水線連接圖和流水線預(yù)約表共同表示蘭州理工大學(xué)蘭州理工大學(xué)蘭州理工大學(xué) 包仲

13、賢包仲賢包仲賢2.2.按照流水線的級(jí)別來(lái)分按照流水線的級(jí)別來(lái)分 處理機(jī)級(jí)流水線處理機(jī)級(jí)流水線，又稱為指令流水線指令流水線。 例如：在采用先行控制器的處理機(jī)中，各功能部件之間的流水線 輸入 先行指令 緩沖棧 先行指令 分析器 先行讀數(shù)棧 先行操作棧 指令 執(zhí)行部件 后行 寫(xiě)數(shù)棧 輸出 功能: 取指令 指令譯碼, 形成操作數(shù)地址 取操作數(shù) 形成RR*指令 執(zhí)行算術(shù) 邏輯運(yùn)算 向存儲(chǔ)器 寫(xiě)結(jié)果 先行控制方式中的指令流水線 前饋回路前饋回路 輸入輸入S S1 1S S2 2S S3 3 輸出輸出反饋回路反饋回路一種簡(jiǎn)單的非線性流水線一種簡(jiǎn)單的非線性流水線蘭州理工大學(xué)蘭州理工大學(xué)蘭州理工大學(xué) 包仲賢包仲

14、賢包仲賢 部件級(jí)流水線部件級(jí)流水線(操作流水線操作流水線) 如浮點(diǎn)加法器流水線 宏流水線宏流水線(Macro Pipelining) 處理機(jī)之間的流水線稱，每個(gè)處理機(jī)對(duì)同一個(gè)數(shù)據(jù)流的不同部分分別進(jìn)行處理。 輸輸 入入 求求 階階 差差 對(duì)對(duì) 階階 尾尾 數(shù)數(shù) 加加 規(guī)規(guī) 格格 化化 輸輸 出出 t t1 t t2 t t3 t t4 輸輸 入入 處處理理機(jī)機(jī) 1 1 處處理理機(jī)機(jī) 2 2 處處理理機(jī)機(jī) n n 輸輸 出出 功功能能: : 任任務(wù)務(wù)1 1 任任務(wù)務(wù)2 2 任任務(wù)務(wù)n n 存儲(chǔ)器 存儲(chǔ)器 存儲(chǔ)器 蘭州理工大學(xué)蘭州理工大學(xué)蘭州理工大學(xué) 包仲賢包仲賢包仲賢3. 3. 單功能流水線與多功

15、能流水線單功能流水線與多功能流水線 單功能流水線：?jiǎn)喂δ芰魉€： 只能完成一種固定功能的流水線。只能完成一種固定功能的流水線。 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)不同功能流水線的各段通過(guò)不同連接實(shí)現(xiàn)不同功能 Texas公司的ASC機(jī)，8段流水線，能夠?qū)崿F(xiàn)：定點(diǎn)加減法、定點(diǎn)乘法、浮點(diǎn)加法、浮點(diǎn)乘法、邏輯運(yùn)算、移位操作、數(shù)據(jù)轉(zhuǎn)換、向量運(yùn)算等。蘭州理工大學(xué)蘭州理工大學(xué)蘭州理工大學(xué) 包仲賢包仲賢包仲賢 A B A B A B

16、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) 積蘭州理工大學(xué)蘭州理工大學(xué)蘭州理工大學(xué) 包仲賢包仲賢包仲賢4.4.靜態(tài)流水線與動(dòng)態(tài)流水線靜態(tài)流水線與動(dòng)態(tài)流水線靜態(tài)流水線靜態(tài)流水線：同一段時(shí)間內(nèi)，各個(gè)功能段只能按：同一段時(shí)間內(nèi)，各個(gè)功能段只能

17、按照一種方式連接，實(shí)現(xiàn)一種固定的功能。照一種方式連接，實(shí)現(xiàn)一種固定的功能?？湛臻g間浮浮點(diǎn)點(diǎn)加加法法定定點(diǎn)點(diǎn)乘乘法法輸出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對(duì)階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 1 n n1 12 23 34 4時(shí)時(shí)間間靜靜態(tài)態(tài)流流水水線線時(shí)時(shí)空空?qǐng)D圖蘭州理工大學(xué)蘭州理工大學(xué)蘭州理工大學(xué) 包仲賢包仲賢包仲賢動(dòng)態(tài)流水線動(dòng)態(tài)

18、流水線：在同一段時(shí)間內(nèi)，各段可以按照不：在同一段時(shí)間內(nèi)，各段可以按照不同的方式連接，同時(shí)執(zhí)行多種功能。同的方式連接，同時(shí)執(zhí)行多種功能。 空空間間 浮浮點(diǎn)點(diǎn)加加法法 定定點(diǎn)點(diǎn)乘乘法法 輸輸入入 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 對(duì)對(duì)階階 1 1 2 2 3 3 4 4 5 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

19、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 時(shí)時(shí)間間 動(dòng)動(dòng)態(tài)態(tài)流流水水線線時(shí)時(shí)空空?qǐng)D圖 蘭州理工大學(xué)蘭州理工大學(xué)蘭州理工大學(xué) 包仲賢包仲賢包仲賢5.5.流水線的其他分類方法流水線的其他分類方法按照數(shù)據(jù)表示方式：標(biāo)量流水線和向量流水線標(biāo)量流水線和向量流水線按照控制方式：同步流水線和異步流水線同步流水線和異步流水線順序流水線與亂序流水線順序流水線與亂序流水線，亂序流水線又稱為無(wú)序流水線、錯(cuò)序流水線或異步流水線等。 輸輸入入 就就緒緒 回回答答 S1 就就緒緒 回回答答 S2 就就緒緒 回回答答 Sn 輸輸出出

20、 就就緒緒 回回答答 一種異步流水線 蘭州理工大學(xué)蘭州理工大學(xué)蘭州理工大學(xué) 包仲賢包仲賢包仲賢5.2.3 5.2.3 線性流水線的性能分析線性流水線的性能分析 主要指標(biāo)：吞吐率、加速比和效率吞吐率、加速比和效率1.1.吞吐率（吞吐率（Though PutThough Put）流水線吞吐率的最基本公式：流水線吞吐率的最基本公式： 其中：n為任務(wù)數(shù)， k為完成n個(gè)任務(wù)所用的時(shí)間。各段執(zhí)行時(shí)間相等，輸入連續(xù)任務(wù)情況下，完成n個(gè)任務(wù)需要的總時(shí)間為： Tk(kn1) t 其中：k 為流水線的段數(shù)，t為時(shí)鐘周期。T PnTk蘭州理工大學(xué)蘭州理工大學(xué)蘭州理工大學(xué) 包仲賢包仲賢包仲賢 Tk= k t + (n

21、-1) t = (k+n-1) t 空空間間S4123n-1nS3123n-1nS2123n-1nS11 12 23 3n n- -1 1n n時(shí)時(shí)間間kt(n1)tnt(k1)tT 吞吐率為：吞吐率為： 最大吞吐率為：最大吞吐率為：TPnknt()1 nTPLimnknttmax() 11蘭州理工大學(xué)蘭州理工大學(xué)蘭州理工大學(xué) 包仲賢包仲賢包仲賢 各段時(shí)間不等，完成各段時(shí)間不等，完成n n個(gè)連續(xù)任務(wù)：個(gè)連續(xù)任務(wù)： 吞吐率：吞吐率： 最大吞吐率：最大吞吐率： 流水線各段執(zhí)行時(shí)間不相等的解決辦法流水線各段執(zhí)行時(shí)間不相等的解決辦法TPntntttiikk1121() max(,),max(121kt

22、ttTP 輸輸入入S1S2S3S4輸輸出出 t1 t t23 t t3 t t4 t蘭州理工大學(xué)蘭州理工大學(xué)蘭州理工大學(xué) 包仲賢包仲賢包仲賢(1)(1)將將“瓶頸瓶頸”部分再細(xì)分部分再細(xì)分（如果可分的話）（如果可分的話）空空間間S4123nS3123nS2123nS1123n時(shí)時(shí)間間 kiit1（n1） t2Tk各段執(zhí)行時(shí)間不相等的流水線及其時(shí)空?qǐng)D輸輸入入S1S2-1S2-2S2-3S3S4輸輸出出 t t t t t t“瓶瓶頸頸”流流水水段段再再次次細(xì)細(xì)分分 S2 (3 t)蘭州理工大學(xué)蘭州理工大學(xué)蘭州理工大學(xué) 包仲賢包仲賢包仲賢 空空間間 S4 1 2 3 4 5 6 n-2 n-1 n

23、 S3 1 2 3 4 5 6 n-2 n-1 n S2-3 3 6 n S2-2 2 5 n-1 S2-1 1 4 n-2 S1 1 2 3 4 5 6 n-2 n-1 n 時(shí)時(shí)間間 流流水水段段重重復(fù)復(fù)設(shè)設(shè)置置的的流流水水線線 ( (2 2) )“瓶瓶頸頸“流流水水段段重重復(fù)復(fù)設(shè)設(shè)置置：增加分配器和收集器 S2-3 輸輸入入 S1 S2-2 S3 S4 輸輸出出 t1 t t3 t t4 t S2-1 t23 t 蘭州理工大學(xué)蘭州理工大學(xué)蘭州理工大學(xué) 包仲賢包仲賢包仲賢2.2.加速比（加速比（SpeedupSpeedup） 計(jì)算加速比的基本公式：計(jì)算加速比的基本公式： 各段執(zhí)行時(shí)間相等，輸

24、入連續(xù)任務(wù)情況下, 加速比： 最大加速比： 各段時(shí)間不等，輸入連續(xù)任務(wù)情況下, 實(shí)際加 速比為：STTk順序執(zhí)行時(shí)間流水線執(zhí)行時(shí)間0Sk ntkntk nkn () 11SLimk nknknmax1Snttntttiikiikk 11121() m ax(,）蘭州理工大學(xué)蘭州理工大學(xué)蘭州理工大學(xué) 包仲賢包仲賢包仲賢 當(dāng)流水線段數(shù)增加時(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ù) 個(gè)個(gè) 數(shù)數(shù)蘭州理工大學(xué)蘭州理工大學(xué)蘭州理工大學(xué) 包仲賢包仲賢包仲賢3.3.效

25、率（效率（EfficiencyEfficiency）計(jì)算流水線效率的一般公式：計(jì)算流水線效率的一般公式：各流水段時(shí)間相等，輸入n個(gè)連續(xù)任務(wù)，流水線的效率為：最高效率為：各流水段時(shí)間不等，輸入n個(gè)連續(xù)任務(wù)，流水 線效率為： EnkTk Tk個(gè)任務(wù)占用的時(shí)空區(qū)個(gè)流水段的總的時(shí)空區(qū)0Ek ntkkntnkn () 11ELimnknnmax11Entktntttiikiikk 11121)m ax(,)（蘭州理工大學(xué)蘭州理工大學(xué)蘭州理工大學(xué) 包仲賢包仲賢包仲賢各段設(shè)備量或價(jià)格不等時(shí)，流水線的效率為：流水線的效率為： 即： 其中，aik，且k。流水線的吞吐率、流水線的吞吐率、加速比與效率的關(guān)系：加速比

26、與效率的關(guān)系：因?yàn)椋阂虼耍篍TPt，SkE空區(qū)個(gè)流水段的總的加權(quán)時(shí)區(qū)個(gè)任務(wù)占用的加權(quán)時(shí)空knE EnataatntttiiikiIikiiikn111121) max(,)（TPnknt() 1 Sknkn 1Enkn1蘭州理工大學(xué)蘭州理工大學(xué)蘭州理工大學(xué) 包仲賢包仲賢包仲賢4. 4. 流水線最佳段數(shù)的選擇流水線最佳段數(shù)的選擇采用順序執(zhí)行方式完成一個(gè)任務(wù)的時(shí)間為t在同等速度的 k 段流水線上執(zhí)行一個(gè)任務(wù)的時(shí)間為：tkd (d為流水鎖存器的延遲時(shí)間)流水線的最大吞吐率為：P=1(tkd)流水線的總價(jià)格估計(jì)為：Cab k， 其中：a為功能段身的總價(jià)格， b為每個(gè)鎖存器的價(jià)格 A.G.Larson把

27、流水線的性能價(jià)格比PCR定義為：PCRPCt kd abk11/蘭州理工大學(xué)蘭州理工大學(xué)蘭州理工大學(xué) 包仲賢包仲賢包仲賢 求PCR的最大值為：ktadb000)()()(0)(1)(0)1/1(2kbdatdktbkbkadkbkadktbkadktkbkadkt 性能價(jià)格比PCR 峰值 最佳值(k0) 流水線段數(shù)k蘭州理工大學(xué)蘭州理工大學(xué)蘭州理工大學(xué) 包仲賢包仲賢包仲賢5. 5. 流水線性能分析舉例流水線性能分析舉例對(duì)于單功能線性流水線，輸入連續(xù)任務(wù)的情況，通過(guò)上面給出的公式很容易計(jì)算出流水線的吞吐率、加速比和效率。對(duì)于輸入不連續(xù)任務(wù)，或多功能流水線，通常采用基本公式計(jì)算。例例5.2： 用一

28、條4段浮點(diǎn)加法器流水線求8個(gè)浮點(diǎn)數(shù)的和：ZABCDEFGH蘭州理工大學(xué)蘭州理工大學(xué)蘭州理工大學(xué) 包仲賢包仲賢包仲賢解：解： Z(AB)(CD)(EF)(GH) 空空間間 周周期期 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 規(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

29、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+ +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í)空空?qǐng)D圖 蘭州理工大學(xué)蘭州理工大學(xué)蘭州理

30、工大學(xué) 包仲賢包仲賢包仲賢解：解： 7 個(gè)個(gè)浮浮點(diǎn)點(diǎn)加加法法共共用用了了 15 個(gè)個(gè)時(shí)時(shí)鐘鐘周周期期。 流流水水線線的的吞吞吐吐率率為為：TPnTttk7150 471 流流水水線線的的加加速速比比為為：STTttk 047151 87 流流水水線線的的效效率率為為：ETk Tttk 0474 150 47 3636/206/206Computer architectureComputer architecture 例例 設(shè)在下圖所示的靜態(tài)流水線上計(jì)算：設(shè)在下圖所示的靜態(tài)流水線上計(jì)算： 流水線的輸出可以直接返回輸入端或暫存于相應(yīng)的流水寄存器中，流水線的輸出可以直接返回輸入端或暫存于相應(yīng)的流水寄

31、存器中，試計(jì)算其吞吐率、加速比和效率。試計(jì)算其吞吐率、加速比和效率。)(41iiiBA 1 2 3 4 5 乘法乘法 加減法加減法 6 7 8 ( (每段的時(shí)間都為每段的時(shí)間都為t t) ) 時(shí)間 段 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 輸 入 A1 B1 A2 B2 A3 B3 A4 B4 A B C D A B C D AB CD AB CD ABCD A=A1+B1 B=A2+B2 C=A3+B3 D=A4+B4 tTP18721836ttS25. 01884364E3838/206/206Comp

32、uter architectureComputer architecturep在在1818個(gè)個(gè)t t時(shí)間中，給出了時(shí)間中，給出了7 7個(gè)個(gè)結(jié)果。吞吐率為：結(jié)果。吞吐率為： tTP187p 不用流水線，由于一次求和需不用流水線，由于一次求和需6 6t t，一次求積需一次求積需4 4t t， 則產(chǎn)生上述則產(chǎn)生上述7 7個(gè)結(jié)果共需個(gè)結(jié)果共需（4 46+36+34 4）t t = 36 = 36t t 加速比為加速比為（3 3）計(jì)算性能）計(jì)算性能21836ttS3939/206/206Computer architectureComputer architecturep 流水線的效率流水線的效率 25

33、. 01884364E可以看出，在求解此問(wèn)題時(shí)，該流水線的效率不高。 為什么？段時(shí)間4040/206/206Computer architectureComputer architecture主要原因q多功能流水線在做某一種運(yùn)算時(shí)，總有一些段是空多功能流水線在做某一種運(yùn)算時(shí)，總有一些段是空閑的。閑的。q靜態(tài)流水線在進(jìn)行功能切換時(shí)，要等前一種運(yùn)算全靜態(tài)流水線在進(jìn)行功能切換時(shí)，要等前一種運(yùn)算全部流出流水線后才能進(jìn)行后面的運(yùn)算。部流出流水線后才能進(jìn)行后面的運(yùn)算。q運(yùn)算之間存在關(guān)聯(lián)，后面有些運(yùn)算要用到前面運(yùn)算運(yùn)算之間存在關(guān)聯(lián)，后面有些運(yùn)算要用到前面運(yùn)算的結(jié)果。的結(jié)果。q流水線的工作過(guò)程有建立與排空部分

34、。流水線的工作過(guò)程有建立與排空部分。 4141/206/206Computer architectureComputer architecture 例例 有一條動(dòng)態(tài)多功能流水線由有一條動(dòng)態(tài)多功能流水線由5 5段組成，加法用段組成，加法用1 1、3 3、4 4、5 5段，乘法用段，乘法用1 1、2 2、5 5段，第段，第2 2段的時(shí)間為段的時(shí)間為2 2t t，其余各段時(shí)間均，其余各段時(shí)間均為為t t，而且流水線的輸出可以直接返回輸入端或暫存于相應(yīng)的，而且流水線的輸出可以直接返回輸入端或暫存于相應(yīng)的流水寄存器中。若在該流水線上計(jì)算流水寄存器中。若在該流水線上計(jì)算: : 試計(jì)算其吞吐率、加速比和效率

35、。試計(jì)算其吞吐率、加速比和效率。)(41iiiBA 1 2 3 4 5 乘法乘法 加法加法 t 2t t t t 4242/206/206Computer architectureComputer architecture解解: : (1) (1) 選擇適合于流水線工作的算法選擇適合于流水線工作的算法p應(yīng)先計(jì)算應(yīng)先計(jì)算A A1 1B B1 1、A A2 2B B2 2、A A3 3B B3 3和和A A4 4B B4 4；p再計(jì)算再計(jì)算( (A A1 1B B1)1)( (A A2 2B B2)2) ( (A A3 3B B3)3)( (A A4 4B B4)4)；p然后求總的累加結(jié)果。然后求

36、總的累加結(jié)果。(2) (2) 畫(huà)出時(shí)空?qǐng)D畫(huà)出時(shí)空?qǐng)D(3) (3) 計(jì)算性能計(jì)算性能4343/206/206Computer architectureComputer architecture3.3 流水線的性能指標(biāo) 時(shí)間 段 1 2 3 4 5 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 輸 入 A1 B1 A2 B2 A3 B3 A4 B4 A B C D A B C D AB CD AB CD ABCD A=A1B1 B=A2B2 C=A3B3 D=A4B4 18 56. 11828ttStTP18731. 01854344E蘭州理工大學(xué)蘭州理工

37、大學(xué)蘭州理工大學(xué) 包仲賢包仲賢包仲賢5.2.4 5.2.4 非線性流水線的調(diào)度非線性流水線的調(diào)度非線性流水線調(diào)度的任務(wù)是要找出一個(gè)最小的循環(huán)周期，非線性流水線調(diào)度的任務(wù)是要找出一個(gè)最小的循環(huán)周期，按照這周期向流水線輸入新任務(wù)，流水線的各個(gè)功能段按照這周期向流水線輸入新任務(wù)，流水線的各個(gè)功能段都不會(huì)發(fā)生沖突，而且流水線的吞吐率和效率最高。都不會(huì)發(fā)生沖突，而且流水線的吞吐率和效率最高。1.1.非線性流水線的表示非線性流水線的表示線性流水線能夠用流水線連接圖唯一表示對(duì)于非線形流水線，連接圖不能唯一表示工作流程，因此，引入流水線預(yù)約表例如：蘭州理工大學(xué)蘭州理工大學(xué)蘭州理工大學(xué) 包仲賢包仲賢包仲賢 輸輸

38、出出輸輸入入S1S2S3S4前饋線反饋線 非線形流水線的連接圖和預(yù)約表非線形流水線的連接圖和預(yù)約表時(shí)時(shí)間間功功能能段段1234567S1S2S3S4蘭州理工大學(xué)蘭州理工大學(xué)蘭州理工大學(xué) 包仲賢包仲賢包仲賢 時(shí)時(shí) 間間 功功 能能 段段 1 2 3 4 5 6 7 S1 S2 S3 S4 輸輸出出S4輸輸入入S1S2S3前前饋饋線線反反饋饋線線 輸輸出出輸輸入入S1S2S3S4前饋線反饋線 一張預(yù)約表可能與多個(gè)流水線連接圖一張預(yù)約表可能與多個(gè)流水線連接圖相對(duì)應(yīng)相對(duì)應(yīng)蘭州理工大學(xué)蘭州理工大學(xué)蘭州理工大學(xué) 包仲賢包仲賢包仲賢 時(shí)時(shí) 間間 功功 能能 段段 1 2 3 4 5 6 7 S1 S2 S3

39、 S4 輸輸 出出輸輸 入入S1S2S3S4前 饋 線反 饋 線 一個(gè)流水線連接圖對(duì)應(yīng)與多張預(yù)約一個(gè)流水線連接圖對(duì)應(yīng)與多張預(yù)約表表 時(shí)時(shí) 間間 功功 能能 段段 1 1 2 2 3 3 4 4 5 5 6 6 7 7 S1 S2 S3 S4 蘭州理工大學(xué)蘭州理工大學(xué)蘭州理工大學(xué) 包仲賢包仲賢包仲賢2.2.非線性流水線的沖突非線性流水線的沖突 啟動(dòng)距離：?jiǎn)?dòng)距離：連續(xù)輸入兩個(gè)任務(wù)之間的時(shí)間間隔 流水線沖突：流水線沖突：幾個(gè)任務(wù)爭(zhēng)用同一個(gè)流水段啟啟動(dòng)動(dòng)距距離離為為 3 3 的的流流水水線線沖沖突突情情況況 時(shí)時(shí)間間 功功能能段段 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9

40、9 1 10 0 1 11 1 S1 X X1 1 X X1 1X X2 2 X X1 1X X2 2X X3 3 X X2 2X X3 3X X4 4 S2 X X1 1 X X1 1X X2 2 X X2 2X X3 3 X X3 3X X4 4 S3 X X1 1 X X2 2 X X1 1 X X3 3 X X2 2 X X4 4 S4 X X1 1 X X2 2 X X3 3 啟啟動(dòng)動(dòng)距距離離為為 2 2 的的流流水水線線沖沖突突情情況況 時(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

41、 1 X X2 2 X X1 1 X X3 3 X X2 2 X X1 1X X4 4 X X3 3 X X2 2X X5 5 X X4 4 X X3 3X X6 6 S S2 2 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 S3 3 X X1 1 X X2 2 X X1 1X X3 3 X X2 2X X4 4 X X3 3X X5 5 S S4 4 X X1 1 X X2 2 X X3 3 X X4 4 X X5 5 啟啟動(dòng)動(dòng)距距離離為為 5 5 時(shí)時(shí)的的流流水水線線不不沖沖突突 時(shí)時(shí)間間 功功能能段段

42、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 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,7)(1,7)循環(huán)時(shí)的流水線預(yù)約表循環(huán)時(shí)的流水線預(yù)約表 時(shí)間時(shí)間 功能段功能段 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9

43、 1010 1111 1212 1313 1414 1515 1616 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 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ù)啟

44、動(dòng)周期重復(fù)啟動(dòng)周期 蘭州理工大學(xué)蘭州理工大學(xué)蘭州理工大學(xué) 包仲賢包仲賢包仲賢3.3.無(wú)沖突調(diào)度方法無(wú)沖突調(diào)度方法由E.S.Davidson及其學(xué)生于1971年提出禁止向量禁止向量：預(yù)約表中每一行任意兩個(gè)“”之間距離的集合。上例中為（3 3，4 4，6 6）沖突向量沖突向量：C（CmCm-1C2C1） 其中：m是禁止向量中的最大值。 如果i在禁止向量中，則Ci1，否則Ci0。 上例中C C(101100)(101100)時(shí)時(shí) 間間 功功 能能 段段 1 2 3 4 5 6 7 S1 S2 S3 S4 蘭州理工大學(xué)蘭州理工大學(xué)蘭州理工大學(xué) 包仲賢包仲賢包仲賢例例5.35.3：一條4功能段的非線性流

45、水線，每個(gè)功能段的延遲時(shí)間都相等，它的預(yù)約表如下： (1)寫(xiě)出流水線的禁止向量和初始沖突向量。 (2)畫(huà)出調(diào)度流水線的狀態(tài)圖。 (3)求最小啟動(dòng)循環(huán)和最小平均啟動(dòng)距離。 (4)求平均啟動(dòng)距離最小的恒定循環(huán)。時(shí) 間 功能段 1 2 3 4 5 6 7 S1 X X S2 X X S3 X X S4 X 蘭州理工大學(xué)蘭州理工大學(xué)蘭州理工大學(xué) 包仲賢包仲賢包仲賢解解：(1)(1)禁止向量為：禁止向量為：(2，4，6) 初始沖突向量：初始沖突向量：S = 101010S = 101010(2)(2)構(gòu)造狀態(tài)圖構(gòu)造狀態(tài)圖 S S邏輯右移邏輯右移2 2、4 4、6 6位時(shí)，不作任何處理，位時(shí)，不作任何處理

46、， 邏輯右移邏輯右移1 1、3 3、5 5和大于等于和大于等于7 7時(shí)：時(shí)： S右移1位之后：010101101010111111111111， S右移3位之后：000101101010101111101111， S右移5位之后：000001101010101011101011， S右移7位或大于7位后：還原到它本身。蘭州理工大學(xué)蘭州理工大學(xué)蘭州理工大學(xué) 包仲賢包仲賢包仲賢101111右移5位之后：000001101010101011101011，101011右移3位之后：000101101010101111101111，101011右移5位之后：00000110101010101110101

47、1。7*07*153 7*7*15 305非非線線性性流流水水線線的的狀狀態(tài)態(tài)圖圖蘭州理工大學(xué)蘭州理工大學(xué)蘭州理工大學(xué) 包仲賢包仲賢包仲賢簡(jiǎn)單循環(huán)：簡(jiǎn)單循環(huán)：狀態(tài)圖中各種沖突向量只經(jīng)過(guò)一次的狀態(tài)圖中各種沖突向量只經(jīng)過(guò)一次的啟動(dòng)循環(huán)。啟動(dòng)循環(huán)。(3)(3)最小的啟動(dòng)循環(huán)最小的啟動(dòng)循環(huán)為為（1，7）和（3，5）, 平均啟動(dòng)距離為平均啟動(dòng)距離為 4 4。(4)(4)啟動(dòng)距離最小的恒定循環(huán)為（啟動(dòng)距離最小的恒定循環(huán)為（5 5）簡(jiǎn)簡(jiǎn) 單單 循循 環(huán)環(huán)平平 均均 啟啟 動(dòng)動(dòng) 距距 離離（ 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

48、（ 5 5， 3 3， 7 7）5 5（ 3 3， 5 5）4 4（ 5 5）5 5（ 7 7）7 7蘭州理工大學(xué)蘭州理工大學(xué)蘭州理工大學(xué) 包仲賢包仲賢包仲賢最小啟動(dòng)循環(huán)最小啟動(dòng)循環(huán)(3,5)(3,5)的流水線工作狀態(tài)的流水線工作狀態(tài)時(shí)間時(shí)間功能段功能段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 X

49、2 2X X2 2X X3 3X X3 3X X4 4S S4 4X X1 1X X2 2X X3 3X X4 4啟動(dòng)周期啟動(dòng)周期重復(fù)啟動(dòng)周期重復(fù)啟動(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 S S2 2 X X1 1 X X2 2 X X1 1 X X2

50、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)周周期期 恒恒定定啟啟動(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 1 14 4 1 15 5 S S1 1 X X1 1 X X2 2 X

51、 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)周周期期 蘭州理工大學(xué)蘭州理工大學(xué)蘭州理工大學(xué) 包仲賢包仲賢包仲賢4.4.優(yōu)化調(diào)度方法優(yōu)化調(diào)度方法L.E.Shar于1972年提出流水線最小平均啟動(dòng)距離的限制范圍： (1) (1)最小平均啟動(dòng)距離的下限是預(yù)約表中任意一最小平均啟動(dòng)距離的下限是預(yù)約表中任意一行里行里“”的最多個(gè)數(shù)。的最多個(gè)

52、數(shù)。 (2) (2)最小平均啟動(dòng)距離小于等于狀態(tài)圖中任意一最小平均啟動(dòng)距離小于等于狀態(tài)圖中任意一個(gè)簡(jiǎn)單循環(huán)的平均啟動(dòng)距離。個(gè)簡(jiǎn)單循環(huán)的平均啟動(dòng)距離。 (3) (3)最小平均啟動(dòng)距離的上限是沖突向量中最小平均啟動(dòng)距離的上限是沖突向量中1 1的的個(gè)數(shù)再加上個(gè)數(shù)再加上1 1。1992年，L.E.Shar又證明了上述限制范圍。最有用的是第1條。預(yù)約表中“”最多的行一定是瓶頸流水段瓶頸流水段蘭州理工大學(xué)蘭州理工大學(xué)蘭州理工大學(xué) 包仲賢包仲賢包仲賢對(duì)于例5.3的預(yù)約表，在同一行中“”最多的為2個(gè)，因此，最小平均距離可以達(dá)到最小平均距離可以達(dá)到2。最小啟動(dòng)循環(huán)可以是(2)、(1,3)、(1,1,4)、(1,

53、2,3)、。現(xiàn)取恒定循環(huán)恒定循環(huán)(2)(2)。每一行中與第每一行中與第1 1個(gè)個(gè)“”的距離為的距離為2 2的倍數(shù)的位置的倍數(shù)的位置都要預(yù)留出來(lái)。都要預(yù)留出來(lái)。 S3行的第2個(gè)“”從周期5延遲到周期6。為此， S2行的第2個(gè)“”從周期6延遲到周期7； S1行的第2個(gè)“”從周期7延遲到周期8。實(shí)際上，只要在流水段S4的輸出端到流水段S3的輸入端中間插入一個(gè)非計(jì)算延遲非計(jì)算延遲D1。蘭州理工大學(xué)蘭州理工大學(xué)蘭州理工大學(xué) 包仲賢包仲賢包仲賢采采用用預(yù)預(yù)留留調(diào)調(diào)度度算算法法的的預(yù)預(yù)約約表表時(shí)時(shí) 間間12345678S1S2S3功功能能段段S4延延遲遲 D1注注：表表示示由由D D1 1延延遲遲一一個(gè)個(gè)時(shí)

54、時(shí)鐘鐘周周期期蘭州理工大學(xué)蘭州理工大學(xué)蘭州理工大學(xué) 包仲賢包仲賢包仲賢有有 非非 計(jì)計(jì) 算算 延延 遲遲 的的 流流 水水 線線 狀狀 態(tài)態(tài) 圖圖8 8* * 0 0 0 08 8* * 8 8* *1 1 2 2 4 4 6 6 8 8* * 0 0 0 0 0 0 1 12 2 4 4 6 6 增增加加了了一一個(gè)個(gè)非非計(jì)計(jì)算算延延遲遲流流水水段段 D1的的流流水水線線連連接接圖圖 輸輸出出輸輸入入S1S2S3S4D1蘭州理工大學(xué)蘭州理工大學(xué)蘭州理工大學(xué) 包仲賢包仲賢包仲賢按按照照最最小小啟啟動(dòng)動(dòng)循循環(huán)環(huán)（2 2）工工作作的的流流水水線線預(yù)預(yù)約約表表 時(shí)時(shí)間間 1 1 2 2 3 3 4 4

55、 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 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

56、 5 延延 D D1 1 X X1 1 X X2 2 X X3 3 X X4 4 在非線性流水線中，“”最多的流水段一定是“瓶頸“流水段。實(shí)現(xiàn)最優(yōu)調(diào)度的目標(biāo)是使“瓶頸瓶頸”流水段處于忙碌流水段處于忙碌狀態(tài)，沒(méi)有空閑周期。狀態(tài)，沒(méi)有空閑周期。最優(yōu)調(diào)度方法能夠使非線性流水線的吞吐率、加速比和效率達(dá)到最優(yōu)。蘭州理工大學(xué)蘭州理工大學(xué)蘭州理工大學(xué) 包仲賢包仲賢包仲賢5.3 5.3 相關(guān)性分析技術(shù)相關(guān)性分析技術(shù)資源相關(guān)：資源相關(guān)：資源相關(guān)是指多條指令進(jìn)入流水線后在資源相關(guān)是指多條指令進(jìn)入流水線后在同一機(jī)器時(shí)鐘周期內(nèi)爭(zhēng)用同一個(gè)功能部件所發(fā)生的同一機(jī)器時(shí)鐘周期內(nèi)爭(zhēng)用同一個(gè)功能部件所發(fā)生的沖突。假定一條指令流水

57、線由沖突。假定一條指令流水線由五段組成五段組成。數(shù)據(jù)相關(guān)：數(shù)據(jù)相關(guān)：在一個(gè)程序中，如果必須等前一條指令在一個(gè)程序中，如果必須等前一條指令執(zhí)行完畢后，才能執(zhí)行后一條指令，那么這兩條指執(zhí)行完畢后，才能執(zhí)行后一條指令，那么這兩條指令就是數(shù)據(jù)相關(guān)的。令就是數(shù)據(jù)相關(guān)的。控制相關(guān)：控制相關(guān)：控制相關(guān)沖突是由轉(zhuǎn)移指令引起的。當(dāng)控制相關(guān)沖突是由轉(zhuǎn)移指令引起的。當(dāng)執(zhí)行轉(zhuǎn)移指令時(shí)，依據(jù)轉(zhuǎn)移條件的產(chǎn)生結(jié)果，可能執(zhí)行轉(zhuǎn)移指令時(shí)，依據(jù)轉(zhuǎn)移條件的產(chǎn)生結(jié)果，可能為順序取下條指令；也可能轉(zhuǎn)移到新的目標(biāo)地址取為順序取下條指令；也可能轉(zhuǎn)移到新的目標(biāo)地址取指令，從而使流水線發(fā)生斷流。指令，從而使流水線發(fā)生斷流。蘭州理工大學(xué)蘭州理工

58、大學(xué)蘭州理工大學(xué) 包仲賢包仲賢包仲賢解決資源相關(guān)沖突的辦法解決資源相關(guān)沖突的辦法：第第I4I4條指令停頓一拍后再啟動(dòng)；條指令停頓一拍后再啟動(dòng)；增設(shè)一個(gè)存儲(chǔ)器，將指令和數(shù)據(jù)分別放在兩個(gè)存儲(chǔ)器中。增設(shè)一個(gè)存儲(chǔ)器，將指令和數(shù)據(jù)分別放在兩個(gè)存儲(chǔ)器中。 如果數(shù)據(jù)和指令放在同一個(gè)如果數(shù)據(jù)和指令放在同一個(gè)存儲(chǔ)器中且只有一個(gè)訪問(wèn)口時(shí)，存儲(chǔ)器中且只有一個(gè)訪問(wèn)口時(shí)，便發(fā)生兩條指令爭(zhēng)用存儲(chǔ)資源的便發(fā)生兩條指令爭(zhēng)用存儲(chǔ)資源的相關(guān)沖突。相關(guān)沖突。5.3.1 資源相關(guān)資源相關(guān)n 先行指令緩沖棧作為主存儲(chǔ)器與指令分析器之間的一個(gè)緩沖部件，用它來(lái)平滑主存儲(chǔ)器和指令分析器的工作。當(dāng)指令分析器分析某一條指令所需要的時(shí)間比較長(zhǎng)，或

59、者主存儲(chǔ)器有空閑時(shí)，就從主存儲(chǔ)器中多取出幾條指令存放在先行指令緩沖棧中。而當(dāng)指令分析器分析指令很快，或者主存儲(chǔ)器比較忙時(shí)，指令分析器也能夠從先行指令緩沖棧中得到所需要的指令。蘭州理工大學(xué)蘭州理工大學(xué)蘭州理工大學(xué) 包仲賢包仲賢包仲賢2.2.解決訪存沖突的方法：解決訪存沖突的方法：(1)(1)采用低位交叉存取方式采用低位交叉存取方式： 這種方法不能根本解決沖突問(wèn)題。指令、讀操作數(shù)、寫(xiě)結(jié)果。(2)(2)兩個(gè)獨(dú)立的存儲(chǔ)器兩個(gè)獨(dú)立的存儲(chǔ)器：獨(dú)立的指令存儲(chǔ)器和數(shù)據(jù)獨(dú)立的指令存儲(chǔ)器和數(shù)據(jù)存儲(chǔ)器。存儲(chǔ)器。如果再規(guī)定，執(zhí)行指令所需要的操作數(shù)和執(zhí)行結(jié)果只寫(xiě)到通用寄存器，則取指令、分析指令和執(zhí)行指令就可以同時(shí)進(jìn)行。

60、在許多高性能處理機(jī)中，有獨(dú)立的指令Cache和數(shù)據(jù)Cache。這種結(jié)構(gòu)被稱為哈佛結(jié)構(gòu)。蘭州理工大學(xué)蘭州理工大學(xué)蘭州理工大學(xué) 包仲賢包仲賢包仲賢(3)(3)采用先行控制技術(shù)采用先行控制技術(shù) 采用先行控制技術(shù)的關(guān)鍵是緩沖技術(shù)和預(yù)處理采用先行控制技術(shù)的關(guān)鍵是緩沖技術(shù)和預(yù)處理技術(shù)。技術(shù)。緩沖技術(shù)通常用在工作速度不固定的兩個(gè)功能部件之間。設(shè)置緩沖棧的目的是用來(lái)以平滑功能部件之間的工作速度。在采用了緩沖技術(shù)和預(yù)處理技術(shù)之后，運(yùn)算器能夠?qū)Ｐ挠跀?shù)據(jù)的運(yùn)算，從而大幅度提高程序的執(zhí)行速度。蘭州理工大學(xué)蘭州理工大學(xué)蘭州理工大學(xué) 包仲賢包仲賢包仲賢先先行行指指令令緩緩沖沖棧棧指指令令分分析析器器主主存存存存儲(chǔ)儲(chǔ)先先行