第5章標量處理機

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

2、大學蘭州理工大學蘭州理工大學 包仲賢包仲賢包仲賢5.1.1 5.1.1 指令的重疊執(zhí)行方式指令的重疊執(zhí)行方式1.1.順序執(zhí)行方式順序執(zhí)行方式執(zhí)行執(zhí)行n n條指令所用的時間為：條指令所用的時間為： 如果每段時間都為t，則執(zhí)行n條指令所用的時間為：T3 n t3 n t主要優(yōu)點：主要優(yōu)點：控制簡單，節(jié)省設備控制簡單，節(jié)省設備主要缺點：主要缺點：速度慢，功能部件的利用率低速度慢，功能部件的利用率低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 蘭州理工大學蘭州理工大學蘭

3、州理工大學 包仲賢包仲賢包仲賢2.2.一次重疊執(zhí)行方式一次重疊執(zhí)行方式如果兩個過程的時間相等，則執(zhí)行n條指令的時間為：T(1+2n)t1+2n)t主要優(yōu)點：主要優(yōu)點： 指令的執(zhí)行時間縮短，指令的執(zhí)行時間縮短， 功能部件的利用率明顯提高。功能部件的利用率明顯提高。主要缺點：主要缺點： 需要增加一些硬件，需要增加一些硬件， 控制過程稍復雜。控制過程稍復雜。取指令取指令 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蘭州理工大學蘭州理工大學蘭州理工大學 包仲賢包仲賢

4、包仲賢3.3.二次重疊執(zhí)行方式二次重疊執(zhí)行方式如果三個過程的時間相等，執(zhí)行n條指令的時間為：T(2 2n n）t t在理想情況下，處理機中同時有三條指令在執(zhí)行。處理機的結(jié)構要作比較大的改變，需要采用先行處理機的結(jié)構要作比較大的改變，需要采用先行控制技術?？刂萍夹g。 取取指指令令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í)行行方方式式蘭州理工大學蘭州理工大學蘭州理工大學 包仲賢包仲賢包仲賢5.1.2 5.1.2 先行控制方式

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

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

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

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

9、時空圖流水線時空圖 空空間間 執(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 時時間間 輸輸入入 輸輸出出 取取指指令令 i 分分析析 i 執(zhí)執(zhí)行行 i 流流水水線線 寄寄存存器器 流流水水線線 寄寄存存器器 t 蘭州理工大學蘭州理工大學蘭

10、州理工大學 包仲賢包仲賢包仲賢 一個浮點加法器流水線的時空圖一個浮點加法器流水線的時空圖 空空 間間 規(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

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

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

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

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

15、能流水線單功能流水線與多功能流水線 單功能流水線：單功能流水線： 只能完成一種固定功能的流水線。只能完成一種固定功能的流水線。 Cray-1計算機種有12條，YH-1計算機有18條 Pentium有一條5段定點和一條8段浮點流水線。 Pentium有兩條定點和一條浮點指令流水線。 多功能流水線：多功能流水線： 流水線的各段通過不同連接實現(xiàn)不同功能流水線的各段通過不同連接實現(xiàn)不同功能 Texas公司的ASC機，8段流水線，能夠?qū)崿F(xiàn)：定點加減法、定點乘法、浮點加法、浮點乘法、邏輯運算、移位操作、數(shù)據(jù)轉(zhuǎn)換、向量運算等。蘭州理工大學蘭州理工大學蘭州理工大學 包仲賢包仲賢包仲賢 A B A B A B

16、A B輸 入輸 入輸 入輸 入求 階 差求 階 差求 階 差求 階 差對 階對 階對 階對 階尾 數(shù) 加尾 數(shù) 加尾 數(shù) 加尾 數(shù) 加規(guī) 格 化規(guī) 格 化規(guī) 格 化規(guī) 格 化尾 數(shù) 乘尾 數(shù) 乘尾 數(shù) 乘尾 數(shù) 乘累 加累 加累 加累 加輸 出輸 出輸 出輸 出g=f(A,B)定 點 乘浮 點 加浮 點 點 積(a)功 能 段 間 的 互 連 (b)定 點 乘 法 (c)浮 點 加 法 (d)浮 點 點 積蘭州理工大學蘭州理工大學蘭州理工大學 包仲賢包仲賢包仲賢4.4.靜態(tài)流水線與動態(tài)流水線靜態(tài)流水線與動態(tài)流水線靜態(tài)流水線靜態(tài)流水線：同一段時間內(nèi)，各個功能段只能按：同一段時間內(nèi)，各個功能段只能

17、按照一種方式連接，實現(xiàn)一種固定的功能。照一種方式連接，實現(xiàn)一種固定的功能?？湛臻g間浮浮點點加加法法定定點點乘乘法法輸出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 1 n n輸入1 12 23 3 n n- -1 1 n n1 12 23 34 4時時間間靜靜態(tài)態(tài)流流水水線線時時空空圖圖蘭州理工大學蘭州理工大學蘭州理工大學 包仲賢包仲賢包仲賢動態(tài)流水線動態(tài)

18、流水線：在同一段時間內(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 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 時時間間 動動態(tài)態(tài)流流水水線線時時空空圖圖 蘭州理工大學蘭州理工大學蘭州理工大學 包仲賢包仲賢包仲賢5.5.流水線的其他分類方法流水線的其他分類方法按照數(shù)據(jù)表示方式：標量流水線和向量流水線標量流水線和向量流水線按照控制方式：同步流水線和異步流水線同步流水線和異步流水線順序流水線與亂序流水線順序流水線與亂序流水線，亂序流水線又稱為無序流水線、錯序流水線或異步流水線等。 輸輸入入 就就緒緒 回回答答 S1 就就緒緒 回回答答 S2 就就緒緒 回回答答 Sn 輸輸出出

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

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

22、ttTP 輸輸入入S1S2S3S4輸輸出出 t1 t t23 t t3 t t4 t蘭州理工大學蘭州理工大學蘭州理工大學 包仲賢包仲賢包仲賢(1)(1)將將“瓶頸瓶頸”部分再細分部分再細分（如果可分的話）（如果可分的話）空空間間S4123nS3123nS2123nS1123n時時間間 kiit1（n1） t2Tk各段執(zhí)行時間不相等的流水線及其時空圖輸輸入入S1S2-1S2-2S2-3S3S4輸輸出出 t t t t t t“瓶瓶頸頸”流流水水段段再再次次細細分分 S2 (3 t)蘭州理工大學蘭州理工大學蘭州理工大學 包仲賢包仲賢包仲賢 空空間間 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 時時間間 流流水水段段重重復復設設置置的的流流水水線線 ( (2 2) )“瓶瓶頸頸“流流水水段段重重復復設設置置：增加分配器和收集器 S2-3 輸輸入入 S1 S2-2 S3 S4 輸輸出出 t1 t t3 t t4 t S2-1 t23 t 蘭州理工大學蘭州理工大學蘭州理工大學 包仲賢包仲賢包仲賢2.2.加速比（加速比（SpeedupSpeedup） 計算加速比的基本公式：計算加速比的基本公式： 各段執(zhí)行時間相等，輸

24、入連續(xù)任務情況下, 加速比： 最大加速比： 各段時間不等，輸入連續(xù)任務情況下, 實際加 速比為：STTk順序執(zhí)行時間流水線執(zhí)行時間0Sk ntkntk nkn () 11SLimk nknknmax1Snttntttiikiikk 11121() m ax(,）蘭州理工大學蘭州理工大學蘭州理工大學 包仲賢包仲賢包仲賢 當流水線段數(shù)增加時，需要連續(xù)輸入的任務 數(shù)也必須增加 加加速速比比 S 10 加加 k=10 段段 8 速速 6 比比 k=6 段段 4 2 1 1 2 4 8 16 32 64 128 n 任任 務務 個個 數(shù)數(shù)蘭州理工大學蘭州理工大學蘭州理工大學 包仲賢包仲賢包仲賢3.3.效

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

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

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

28、條4段浮點加法器流水線求8個浮點數(shù)的和：ZABCDEFGH蘭州理工大學蘭州理工大學蘭州理工大學 包仲賢包仲賢包仲賢解：解： 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 對對階階 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ù) 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段段浮浮點點加加法法器器流流水水線線求求8 8個個數(shù)數(shù)之之和和的的流流水水線線時時空空圖圖 蘭州理工大學蘭州理工大學蘭州理

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

31、存器中，試計算其吞吐率、加速比和效率。試計算其吞吐率、加速比和效率。)(41iiiBA 1 2 3 4 5 乘法乘法 加減法加減法 6 7 8 ( (每段的時間都為每段的時間都為t t) ) 時間 段 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個個t t時間中，給出了時間中，給出了7 7個個結(jié)果。吞吐率為：結(jié)果。吞吐率為： tTP187p 不用流水線，由于一次求和需不用流水線，由于一次求和需6 6t t，一次求積需一次求積需4 4t t， 則產(chǎn)生上述則產(chǎn)生上述7 7個結(jié)果共需個結(jié)果共需（4 46+36+34 4）t t = 36 = 36t t 加速比為加速比為（3 3）計算性能）計算性能21836ttS3939/206/206Computer architectureComputer architecturep 流水線的效率流水線的效率 25

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

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

35、。試計算其吞吐率、加速比和效率。)(41iiiBA 1 2 3 4 5 乘法乘法 加法加法 t 2t t t t 4242/206/206Computer architectureComputer architecture解解: : (1) (1) 選擇適合于流水線工作的算法選擇適合于流水線工作的算法p應先計算應先計算A A1 1B B1 1、A A2 2B B2 2、A A3 3B B3 3和和A A4 4B B4 4；p再計算再計算( (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) 畫出時空圖畫出時空圖(3) (3) 計算性能計算性能4343/206/206Computer architectureComputer architecture3.3 流水線的性能指標 時間 段 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蘭州理工大學蘭州理工

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

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

39、 S4 輸輸 出出輸輸 入入S1S2S3S4前 饋 線反 饋 線 一個流水線連接圖對應與多張預約一個流水線連接圖對應與多張預約表表 時時 間間 功功 能能 段段 1 1 2 2 3 3 4 4 5 5 6 6 7 7 S1 S2 S3 S4 蘭州理工大學蘭州理工大學蘭州理工大學 包仲賢包仲賢包仲賢2.2.非線性流水線的沖突非線性流水線的沖突 啟動距離：啟動距離：連續(xù)輸入兩個任務之間的時間間隔 流水線沖突：流水線沖突：幾個任務爭用同一個流水段啟啟動動距距離離為為 3 3 的的流流水水線線沖沖突突情情況況 時時間間 功功能能段段 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 啟啟動動距距離離為為 2 2 的的流流水水線線沖沖突突情情況況 時時間間 功功能能段段 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 啟啟動動距距離離為為 5 5 時時的的流流水水線線不不沖沖突突 時時間間 功功能能段段

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 啟啟動動周周期期 重重復復啟啟動動周周期期 啟動距離為啟動距離為(1,7)(1,7)循環(huán)時的流水線預約表循環(huán)時的流水線預約表 時間時間 功能段功能段 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 啟動周期啟動周期 重復啟

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

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

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

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

48、（ 5 5， 3 3， 7 7）5 5（ 3 3， 5 5）4 4（ 5 5）5 5（ 7 7）7 7蘭州理工大學蘭州理工大學蘭州理工大學 包仲賢包仲賢包仲賢最小啟動循環(huán)最小啟動循環(huán)(3,5)(3,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 X

49、2 2X X2 2X X3 3X X3 3X X4 4S S4 4X X1 1X X2 2X X3 3X X4 4啟動周期啟動周期重復啟動周期重復啟動周期最最小小啟啟動動循循環(huán)環(huán)( (1 1, ,7 7) )的的流流水水線線工工作作狀狀態(tài)態(tài) 時時間間 功功能能段段 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 啟啟動動周周期期 重重復復啟啟動動周周期期 恒恒定定啟啟動動循循環(huán)環(huán)( (5 5) )的的流流水水線線工工作作狀狀態(tài)態(tài) 時時間間 功功能能段段 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 啟啟動動周周期期 重重復復啟啟動動周周期期 蘭州理工大學蘭州理工大學蘭州理工大學 包仲賢包仲賢包仲賢4.4.優(yōu)化調(diào)度方法優(yōu)化調(diào)度方法L.E.Shar于1972年提出流水線最小平均啟動距離的限制范圍： (1) (1)最小平均啟動距離的下限是預約表中任意一最小平均啟動距離的下限是預約表中任意一行里行里“”的最多個數(shù)。的最多個

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

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

54、時鐘鐘周周期期蘭州理工大學蘭州理工大學蘭州理工大學 包仲賢包仲賢包仲賢有有 非非 計計 算算 延延 遲遲 的的 流流 水水 線線 狀狀 態(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 增增加加了了一一個個非非計計算算延延遲遲流流水水段段 D1的的流流水水線線連連接接圖圖 輸輸出出輸輸入入S1S2S3S4D1蘭州理工大學蘭州理工大學蘭州理工大學 包仲賢包仲賢包仲賢按按照照最最小小啟啟動動循循環(huán)環(huán)（2 2）工工作作的的流流水水線線預預約約表表 時時間間 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 在非線性流水線中，“”最多的流水段一定是“瓶頸“流水段。實現(xiàn)最優(yōu)調(diào)度的目標是使“瓶頸瓶頸”流水段處于忙碌流水段處于忙碌狀態(tài)，沒有空閑周期。狀態(tài)，沒有空閑周期。最優(yōu)調(diào)度方法能夠使非線性流水線的吞吐率、加速比和效率達到最優(yōu)。蘭州理工大學蘭州理工大學蘭州理工大學 包仲賢包仲賢包仲賢5.3 5.3 相關性分析技術相關性分析技術資源相關：資源相關：資源相關是指多條指令進入流水線后在資源相關是指多條指令進入流水線后在同一機器時鐘周期內(nèi)爭用同一個功能部件所發(fā)生的同一機器時鐘周期內(nèi)爭用同一個功能部件所發(fā)生的沖突。假定一條指令流水

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

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

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

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