第四章(流水處理和ILP)

1、計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)1 / 263 w流水線基本概念流水線基本概念 w相關(guān)性分析技術(shù)相關(guān)性分析技術(shù) w多指令發(fā)射技術(shù)多指令發(fā)射技術(shù) 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)2 / 263 w 引入引入 w 流水線工作原理流水線工作原理 w 流水線的分類流水線的分類 w 流水線的性能分析流水線的性能分析 w 非線性流水線的調(diào)度技術(shù)非線性流水線的調(diào)度技術(shù) 本章內(nèi)容 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)3 / 263 本章內(nèi)容流水線基本概念 具有標(biāo)量數(shù)據(jù)表示和標(biāo)量指令系統(tǒng)的處理機(jī)稱具有標(biāo)量數(shù)據(jù)表示和標(biāo)量指令系統(tǒng)的處理機(jī)稱 為標(biāo)量處理機(jī)。為標(biāo)量處理機(jī)。 提高處理機(jī)的工作主頻；提高處理機(jī)的工作主頻； 采用更好的算法和設(shè)計(jì)更好的功能部件；采用更好的算法和設(shè)計(jì)

2、更好的功能部件； 采用指令級并行（采用指令級并行（ILP）技術(shù)（技術(shù)（）。）。 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)4 / 263 本章內(nèi)容流水線基本概念 w 基本思想基本思想 w 表示方法表示方法 w 主要特點(diǎn)主要特點(diǎn) 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)5 / 263 本章內(nèi)容流水線基本概念流水線工作原理 以以為例進(jìn)行介紹：為例進(jìn)行介紹： 取指取指分析分析執(zhí)行執(zhí)行 通過將一個(gè)重復(fù)的過程分解為若通過將一個(gè)重復(fù)的過程分解為若 干子過程，每個(gè)子過程可以與其干子過程，每個(gè)子過程可以與其 它子過程同時(shí)進(jìn)行。它子過程同時(shí)進(jìn)行。 ttt 4 之 1 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)6 / 263 本章內(nèi)容流水線基本概念流水線工作原理 取指取指k分析分析k執(zhí)行執(zhí)行k

3、取指取指k+1分析分析k+1執(zhí)行執(zhí)行k+1 控制簡單，節(jié)省設(shè)備。控制簡單，節(jié)省設(shè)備。 處理器執(zhí)行指令的速度慢處理器執(zhí)行指令的速度慢 功能部件的利用率很低功能部件的利用率很低 tn3 (T n 1i iiittt ）執(zhí)行分析取指 4 之 2 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)7 / 263 本章內(nèi)容流水線基本概念流水線工作原理 t)n21 (T 取指取指k分析分析k執(zhí)行執(zhí)行k 取指取指k+1分析分析k+1執(zhí)行執(zhí)行k+1 取指取指k+2分析分析k+2執(zhí)行執(zhí)行k+2 執(zhí)行指令的速度較快執(zhí)行指令的速度較快 功能部件的利用率較高功能部件的利用率較高 控制較復(fù)雜，需增加設(shè)備控制較復(fù)雜，需增加設(shè)備 4 之 3 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)8

4、 / 263 本章內(nèi)容流水線基本概念流水線工作原理 t)n2(T 執(zhí)行指令的速度更快執(zhí)行指令的速度更快 功能部件的利用率更高功能部件的利用率更高 控制更復(fù)雜，需增加設(shè)備控制更復(fù)雜，需增加設(shè)備 取指取指k+2分析分析k+2執(zhí)行執(zhí)行k+2 取指取指k+1分析分析k+1執(zhí)行執(zhí)行k+1 取指取指k分析分析k執(zhí)行執(zhí)行k 4 之 4 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)9 / 263 本章內(nèi)容流水線基本概念流水線工作原理 流水線的表示方法通常有三種：流水線的表示方法通常有三種： w 連接圖連接圖 w 時(shí)空圖時(shí)空圖 w 預(yù)約表預(yù)約表 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)10 / 263 本章內(nèi)容流水線基本概念流水線工作原理流水線表示方法 分析器分析器

5、 分析分析k+1 流水流水 鎖存器鎖存器 執(zhí)行部件執(zhí)行部件 執(zhí)行執(zhí)行k 流水流水 鎖存器鎖存器 輸輸 入入 輸輸 出出 t1 t2 Stage 1latch 輸輸 入入 輸輸 出出 t1 t2 Stage 2latchStage 3latch t3 2 之 1 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)11 / 263 流水線的每一個(gè)階段稱為流水步、流水步驟、流水線的每一個(gè)階段稱為流水步、流水步驟、 流水段、流水線階段、流水功能段、流水級、流流水段、流水線階段、流水功能段、流水級、流 水節(jié)拍等。水節(jié)拍等。 在每一個(gè)流水段的末尾或開頭必須設(shè)置一個(gè)寄在每一個(gè)流水段的末尾或開頭必須設(shè)置一個(gè)寄 存器，稱為流水寄存器、流水鎖存器、

6、流水閘門存器，稱為流水寄存器、流水鎖存器、流水閘門 寄存器等。加入流水寄存器，會增加指令的執(zhí)行寄存器等。加入流水寄存器，會增加指令的執(zhí)行 時(shí)間。在一般流水線中不畫出流水寄存器。時(shí)間。在一般流水線中不畫出流水寄存器。 本章內(nèi)容流水線基本概念流水線工作原理流水線表示方法 2 之 2 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)12 / 263 1時(shí)間時(shí)間 空間空間 0 t1t2t3t4t5 2345 12345 12345 12345 t6t7t8 求階差求階差對階對階尾數(shù)加尾數(shù)加規(guī)格化規(guī)格化 求階差求階差 對階對階 尾數(shù)加尾數(shù)加 規(guī)格化規(guī)格化 tttt 本章內(nèi)容流水線基本概念流水線工作原理流水線表示方法 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)13

7、/ 263 本章內(nèi)容流水線基本概念流水線工作原理 盡量減少因條件分支造成的盡量減少因條件分支造成的“斷流斷流”，可通過編譯技術(shù)，可通過編譯技術(shù) 提供連續(xù)的相同類型操作。提供連續(xù)的相同類型操作。 用于保存本流水線段的執(zhí)行結(jié)果，會使流水線的執(zhí)行時(shí)用于保存本流水線段的執(zhí)行結(jié)果，會使流水線的執(zhí)行時(shí) 間加長，是流水線中需要增加的主要硬件。間加長，是流水線中需要增加的主要硬件。 流水線處理機(jī)的基本時(shí)鐘周期等于時(shí)間最長的流水段的流水線處理機(jī)的基本時(shí)鐘周期等于時(shí)間最長的流水段的 時(shí)間長度。時(shí)間長度。 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)14 / 263 本章內(nèi)容流水線基本概念 從不同的角度，按照不同的觀點(diǎn)，可以從不同的角度，按照不

8、同的觀點(diǎn)，可以 將流水線分成多種不同的種類。將流水線分成多種不同的種類。 w 分類一分類一 w 分類二分類二 w 分類三分類三 w 分類四分類四 w 其它其它 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)15 / 263 w 單功能流水線單功能流水線 只能完成一種固定功能的只能完成一種固定功能的 流水線。例如：流水線。例如：Cray-1計(jì)算計(jì)算 機(jī)中有機(jī)中有12條；條；YH-1計(jì)算機(jī)計(jì)算機(jī) 有有18條；條；Pentium有一條有一條5 段定點(diǎn)和一條段定點(diǎn)和一條8段浮點(diǎn)流水段浮點(diǎn)流水 線；線；Pentium有兩條定點(diǎn)有兩條定點(diǎn) 和一條浮點(diǎn)指令流水線。和一條浮點(diǎn)指令流水線。 w 多功能流水線多功能流水線 流水線的各段通過不同連

9、流水線的各段通過不同連 接實(shí)現(xiàn)不同功能。例如：接實(shí)現(xiàn)不同功能。例如： Texas公司的公司的ASC機(jī)，機(jī)，8段段 流水線，能夠?qū)崿F(xiàn)：定點(diǎn)加流水線，能夠?qū)崿F(xiàn)：定點(diǎn)加 減法、定點(diǎn)乘法、浮點(diǎn)加法、減法、定點(diǎn)乘法、浮點(diǎn)加法、 浮點(diǎn)乘法、邏輯運(yùn)算、移位浮點(diǎn)乘法、邏輯運(yùn)算、移位 操作、數(shù)據(jù)轉(zhuǎn)換、向量運(yùn)算操作、數(shù)據(jù)轉(zhuǎn)換、向量運(yùn)算 等。等。 本章內(nèi)容流水線基本概念流水線的分類 按流水線具有功能的多少來分，可分為：按流水線具有功能的多少來分，可分為： 2 之 1 Texas公司公司ASC機(jī)上的機(jī)上的8段多功能流水線段多功能流水線 2 之 2 A B A B A B A B 輸 入輸 入輸 入輸 入 求 階 差求

10、 階 差求 階 差求 階 差 對 階對 階對 階對 階 尾 數(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) 積 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)17 / 263 本章內(nèi)容流水線基本概念流水線的分類 在多功能流水線中，按照在同一時(shí)間內(nèi)在多功能流水線中，按照在同一時(shí)間內(nèi) 是否能夠連接成多種方式，同時(shí)執(zhí)行多種功是否能夠連接成多種方式，同時(shí)執(zhí)行多種功

11、 能，可以將多功能流水線分為：能，可以將多功能流水線分為： w 靜態(tài)流水線靜態(tài)流水線 w 動態(tài)流水線動態(tài)流水線 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)18 / 263 本章內(nèi)容流水線基本概念流水線的分類分類二 同一段同一段 時(shí)間內(nèi)，時(shí)間內(nèi)， 各個(gè)功能各個(gè)功能 段只能按段只能按 照一種方照一種方 式連接，式連接， 實(shí)現(xiàn)一種實(shí)現(xiàn)一種 固定的功固定的功 能。能。 1 時(shí)間時(shí)間 空間空間 0 2 3 n 1 2 3 n 1 2 3 n 1 2 3 n 1 2 3 n 1 2 3 n 1 2 3 4 1 2 3 1 2 1 輸入輸入 求階差求階差 對階對階 尾數(shù)加尾數(shù)加 規(guī)格化規(guī)格化 尾數(shù)乘尾數(shù)乘 累加累加 輸出輸出 浮點(diǎn)加法

12、浮點(diǎn)加法定點(diǎn)乘法定點(diǎn)乘法 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)19 / 263 在同一在同一 段時(shí)間內(nèi)，段時(shí)間內(nèi)， 各段可以各段可以 按照不同按照不同 的方式連的方式連 接，同時(shí)接，同時(shí) 執(zhí)行多種執(zhí)行多種 功能。功能。 1 時(shí)間時(shí)間 空間空間 0 2 3 n 1 2 3 n 1 2 3 n 1 2 3 n 1 2 3 n 1 2 3 n 輸入輸入 求階差求階差 對階對階 尾數(shù)加尾數(shù)加 規(guī)格化規(guī)格化 尾數(shù)乘尾數(shù)乘 累加累加 輸出輸出 1 2 3546 1 2 354 1 2 3 4 1 2 3 浮點(diǎn)加法浮點(diǎn)加法定點(diǎn)乘法定點(diǎn)乘法 本章內(nèi)容流水線基本概念流水線的分類分類二 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)20 / 263 本章內(nèi)容流水線基

13、本概念流水線的分類 按照流水線的各個(gè)功能段之間是否有反饋信號，可以按照流水線的各個(gè)功能段之間是否有反饋信號，可以 將流水線分為：將流水線分為： 是指流水線內(nèi)各功能段串是指流水線內(nèi)各功能段串 行連接，沒有反饋回路，各行連接，沒有反饋回路，各 個(gè)功能段只經(jīng)過一次。一條個(gè)功能段只經(jīng)過一次。一條 線性流水線通常只完成一種線性流水線通常只完成一種 固定的功能。例子：指令流固定的功能。例子：指令流 水線、浮點(diǎn)加法器流水線等。水線、浮點(diǎn)加法器流水線等。 是指流水線內(nèi)除有串行連是指流水線內(nèi)除有串行連 接的通路外，還有某種反饋接的通路外，還有某種反饋 回路，使得一次流水過程中，回路，使得一次流水過程中， 某些段

14、會多次通過。非線性某些段會多次通過。非線性 流水線經(jīng)常用于遞歸調(diào)用，流水線經(jīng)常用于遞歸調(diào)用， 或構(gòu)成多功能流水線等?；驑?gòu)成多功能流水線等。 3 之 1 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)21 / 263 S1 輸入輸入 S2S3 輸出輸出 前饋回路前饋回路 反饋回路反饋回路 一種簡單的非線性流水線一種簡單的非線性流水線 對應(yīng)的兩種預(yù)約表對應(yīng)的兩種預(yù)約表 S3 S2 S1 4321 S3 S2 S1 43215 3 之 2 本章內(nèi)容流水線基本概念流水線的分類 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)22 / 263 w 線性流水線能夠用線性流水線能夠用唯一表示，非線性流唯一表示，非線性流 水線必須用水線必須用和和共同表示。共同表示。 w 一

15、條非線性流水線可以對應(yīng)有很多張預(yù)約表，一條非線性流水線可以對應(yīng)有很多張預(yù)約表， 同樣，一張預(yù)約表實(shí)際上僅表示了一條非線性同樣，一張預(yù)約表實(shí)際上僅表示了一條非線性 流水線的一種工作方式流水線的一種工作方式 w 線性流水線實(shí)際上也有預(yù)約表，只不過它的預(yù)線性流水線實(shí)際上也有預(yù)約表，只不過它的預(yù) 約表是固定的（一張對角線為的正方形的表約表是固定的（一張對角線為的正方形的表 格）格） 3 之 3 本章內(nèi)容流水線基本概念流水線的分類 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)23 / 263 按照流水線使用的不同級別，可以將流按照流水線使用的不同級別，可以將流 水線分為：水線分為： w 部件級流水線部件級流水線 w 處理機(jī)級流水線處

16、理機(jī)級流水線 w 系統(tǒng)級流水線系統(tǒng)級流水線 本章內(nèi)容流水線基本概念流水線的分類 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)24 / 263 本章內(nèi)容流水線基本概念流水線的分類分類四 是指構(gòu)成部件內(nèi)的各子部件之間的流水。例是指構(gòu)成部件內(nèi)的各子部件之間的流水。例 如：浮點(diǎn)加法器流水線。如：浮點(diǎn)加法器流水線。 求階差求階差 輸入輸入輸出輸出 t1 對階對階尾數(shù)加尾數(shù)加規(guī)格化規(guī)格化 t2 t3 t4 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)25 / 263 又稱為指令流水線又稱為指令流水線 ，例如：在采用先行控制，例如：在采用先行控制 器的處理機(jī)中，各功能部件之間的流水線。器的處理機(jī)中，各功能部件之間的流水線。 先行指令先行指令 緩沖棧緩沖棧 輸入輸入

17、先行控制方式先行控制方式 中的指令流水線中的指令流水線 先行指令先行指令 分析器分析器 先行讀數(shù)棧先行讀數(shù)棧 先行操作棧先行操作棧 取指取指譯碼譯碼取操作數(shù)取操作數(shù) 指令執(zhí)指令執(zhí) 行部件行部件 后行后行 寫數(shù)棧寫數(shù)棧 輸出輸出 執(zhí)行執(zhí)行寫結(jié)果寫結(jié)果 本章內(nèi)容流水線基本概念流水線的分類分類四 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)26 / 263 也稱為宏流水線，是處理機(jī)之間的流水線也稱為宏流水線，是處理機(jī)之間的流水線 。 例如：每個(gè)處理機(jī)對同一個(gè)數(shù)據(jù)流的不同部分分例如：每個(gè)處理機(jī)對同一個(gè)數(shù)據(jù)流的不同部分分 別進(jìn)行處理。別進(jìn)行處理。 P1 輸輸 入入 任務(wù)任務(wù)1 MM P2 任務(wù)任務(wù)2 MP3 任務(wù)任務(wù)3 輸輸 出出

18、本章內(nèi)容流水線基本概念流水線的分類分類四 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)27 / 263 按照不同的數(shù)據(jù)表示方式按照不同的數(shù)據(jù)表示方式 分：分： 對標(biāo)量數(shù)據(jù)進(jìn)行處理。對標(biāo)量數(shù)據(jù)進(jìn)行處理。 對向量數(shù)據(jù)進(jìn)行處理。對向量數(shù)據(jù)進(jìn)行處理。 按照流水線中信息流動順按照流水線中信息流動順 序的控制方式分：序的控制方式分： 流水線輸出端的任務(wù)流出流水線輸出端的任務(wù)流出 順序與輸入端的任務(wù)流入順順序與輸入端的任務(wù)流入順 序完全相同。序完全相同。 流水線輸出端的任務(wù)流出流水線輸出端的任務(wù)流出 順序與輸入端的任務(wù)流入順順序與輸入端的任務(wù)流入順 序可以不一樣。序可以不一樣。 本章內(nèi)容流水線基本概念流水線的分類 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)28 /

19、 263 本章內(nèi)容流水線基本概念 w 吞吐率吞吐率 w 加速比加速比 w 效效 率率 w 流水線最佳段數(shù)的選擇流水線最佳段數(shù)的選擇 w 性能分析舉例性能分析舉例 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)29 / 263 單位時(shí)間內(nèi)能流出的任務(wù)數(shù)或能流出的單位時(shí)間內(nèi)能流出的任務(wù)數(shù)或能流出的 結(jié)果數(shù)。結(jié)果數(shù)。 任務(wù)數(shù)；任務(wù)數(shù)； 處理完成處理完成n個(gè)任務(wù)所用的時(shí)間。個(gè)任務(wù)所用的時(shí)間。 本章內(nèi)容流水線基本概念流水線的性能分析 8 之 1 m T n TP 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)30 / 263 假設(shè)在流水線各段的執(zhí)行時(shí)間均相等，輸入到流水線假設(shè)在流水線各段的執(zhí)行時(shí)間均相等，輸入到流水線 中的任務(wù)是連續(xù)的理想情況下，一條單功能中的任務(wù)是

20、連續(xù)的理想情況下，一條單功能m段線性流水段線性流水 線能夠在線能夠在m+n-1個(gè)時(shí)鐘周期內(nèi)完成個(gè)時(shí)鐘周期內(nèi)完成n個(gè)任務(wù)。個(gè)任務(wù)。 本章內(nèi)容流水線基本概念流水線的性能分析 8 之 2 1 時(shí)間時(shí)間 空間空間 S123 n-1n S2 Sm 123 n-1n 123 n-1n m t(n-1) t n t(m-1) t Tm 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)31 / 263 本章內(nèi)容流水線基本概念流水線的性能分析 8 之 3 t) 1nm( n TP t 1 t) 1nm( n LimTPmax n max TP 1nm n TP 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)32 / 263 假設(shè)在流水線各段的執(zhí)行時(shí)間不相等，輸入假設(shè)在流水線各

21、段的執(zhí)行時(shí)間不相等，輸入 到流水線中的任務(wù)是連續(xù)的理想情況下。到流水線中的任務(wù)是連續(xù)的理想情況下。 w 本章內(nèi)容流水線基本概念流水線的性能分析 8 之 4 )t,t,tmax() 1n(t n TP m21 m 1i i )t,t,tmax( 1 TP m21 max 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)33 / 263 本章內(nèi)容流水線基本概念流水線的性能分析 8 之 5 流水線的流水線的TP和和TPmax主要由流水線中執(zhí)行時(shí)間主要由流水線中執(zhí)行時(shí)間 最長的那個(gè)功能段來決定，這個(gè)功能段就成了整最長的那個(gè)功能段來決定，這個(gè)功能段就成了整 個(gè)流水線的個(gè)流水線的“瓶頸瓶頸”。 將流水線中的將流水線中的“瓶頸瓶頸”再細(xì)分；

22、再細(xì)分； 通過重復(fù)設(shè)置多套瓶頸功能段，讓多個(gè)瓶頸通過重復(fù)設(shè)置多套瓶頸功能段，讓多個(gè)瓶頸 功能段并行工作。功能段并行工作。 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)34 / 263 本章內(nèi)容流水線基本概念流水線的性能分析 8 之 6 S1 t1= t S2 t2=3 t S3 t3= t S4 t4= t 輸輸 出出 1 時(shí)間時(shí)間 空間空間 S1 S2 S3 S4 ti(n-1) t2 Tm 23n 123n 123n 123n 輸輸 入入 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)35 / 263 本章內(nèi)容流水線基本概念流水線的性能分析 8 之 7 S1 輸入輸入 輸出輸出 t S2-1 t S2-2 t S2-3 t S3 t S4 t S2(

23、3 t) S1 輸入輸入輸出輸出 t1= t S2-3 S2-2 S2-1 S3S4 t3= t t4= t t2=3 t 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)36 / 263 本章內(nèi)容流水線基本概念流水線的性能分析 8 之 8 1 時(shí)間時(shí)間 空間空間 23nS1 S2-1 456 14 n-2n-1 n-2 25n-1 36n 123n456n-2n-1 123n456n-2n-1 S2-2 S2-3 S3 S4 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)37 / 263 本章內(nèi)容流水線基本概念流水線的性能分析 完成同樣一批任務(wù)，不使用流水線所用完成同樣一批任務(wù)，不使用流水線所用 的時(shí)間與使用流水線所用的時(shí)間之比。的時(shí)間與使用流水線所用的時(shí)

24、間之比。 m 0 T T S 順序執(zhí)行所用的時(shí)間；順序執(zhí)行所用的時(shí)間； 使用流水線所用的時(shí)間。使用流水線所用的時(shí)間。 3 之 1 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)38 / 263 假設(shè)在流水線各段的執(zhí)行時(shí)間都相等，輸入到假設(shè)在流水線各段的執(zhí)行時(shí)間都相等，輸入到 流水線中的任務(wù)是連續(xù)的理想情況下。流水線中的任務(wù)是連續(xù)的理想情況下。 w 本章內(nèi)容流水線基本概念流水線的性能分析 1nm nm t) 1nm( tnm S m 1nm nm limS n max 3 之 2 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)39 / 263 假設(shè)在流水線各段的執(zhí)行時(shí)間不相等，輸入到假設(shè)在流水線各段的執(zhí)行時(shí)間不相等，輸入到 流水線中的任務(wù)是連續(xù)的理想情況下。

25、流水線中的任務(wù)是連續(xù)的理想情況下。 w 本章內(nèi)容流水線基本概念流水線的性能分析 3 之 3 ） m21 m 1i i m 1i i t,t,tmax() 1n(t tn S 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)40 / 263 本章內(nèi)容流水線基本概念流水線的性能分析 是指流水線的設(shè)備利用率。在時(shí)空圖上，流水是指流水線的設(shè)備利用率。在時(shí)空圖上，流水 線的效率定義為線的效率定義為n個(gè)任務(wù)占用的時(shí)空區(qū)與個(gè)任務(wù)占用的時(shí)空區(qū)與m個(gè)功能個(gè)功能 段總的時(shí)空區(qū)之比。段總的時(shí)空區(qū)之比。 個(gè)功能段的總的時(shí)空區(qū) 個(gè)任務(wù)占用的時(shí)空區(qū) m n E 1 時(shí)間時(shí)間 空間空間 S1n S2 Sm 1n 1n 4 之 1 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)41 / 2

26、63 假設(shè)在流水線各段的執(zhí)行時(shí)間都相等，輸入到假設(shè)在流水線各段的執(zhí)行時(shí)間都相等，輸入到 流水線中的任務(wù)是連續(xù)的理想情況下。流水線中的任務(wù)是連續(xù)的理想情況下。 w 本章內(nèi)容流水線基本概念流水線的性能分析 4 之 2 1nm n t) 1nm(m tnm E 1 1nm n limE n max 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)42 / 263 假設(shè)在流水線各段的執(zhí)行時(shí)間不相等，輸入到假設(shè)在流水線各段的執(zhí)行時(shí)間不相等，輸入到 流水線中的任務(wù)是連續(xù)的理想情況下。流水線中的任務(wù)是連續(xù)的理想情況下。 w 本章內(nèi)容流水線基本概念流水線的性能分析 4 之 3 )t,t,tmax() 1ntm tn E m21 m 1i i

27、m 1i i （ 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)43 / 263 其中，其中， i為為i段的權(quán)值，段的權(quán)值， i 流水線基本概念流水線的性能分析 4 之 4 m 1i m 1i m21ii m 1i ii )t,t,tmax() 1n(t tn m n E 個(gè)功能段的總的時(shí)空區(qū) 個(gè)任務(wù)占用的時(shí)空區(qū) m m 1i i 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)44 / 263 本章內(nèi)容流水線基本概念流水線的性能分析 功能段數(shù)量的增加能提高流水線的吞吐率和加功能段數(shù)量的增加能提高流水線的吞吐率和加 速比，但使流水線價(jià)格增加（鎖存器數(shù)量的增速比，但使流水線價(jià)格增加（鎖存器數(shù)量的增 加），一條指令執(zhí)行的總時(shí)間增加（鎖存器的總加），一條指令執(zhí)行的

28、總時(shí)間增加（鎖存器的總 延遲時(shí)間增加）。所以從性價(jià)比角度出發(fā)流水線延遲時(shí)間增加）。所以從性價(jià)比角度出發(fā)流水線 存在著最佳段數(shù)。存在著最佳段數(shù)。 2 之 1 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)45 / 263 對自變量對自變量m求導(dǎo)，求求導(dǎo)，求PCR 的最大值，得到最佳段數(shù)為：的最大值，得到最佳段數(shù)為： 本章內(nèi)容流水線基本概念流水線的性能分析 bma )dm/ t/(1 PCR 流水線價(jià)格 最大吞吐量 ）性價(jià)比（ 任務(wù)總時(shí)間任務(wù)總時(shí)間 鎖存器時(shí)間鎖存器時(shí)間 功能段數(shù)功能段數(shù) 所有功能段價(jià)格所有功能段價(jià)格 鎖存器價(jià)格鎖存器價(jià)格bd at m 0 2 之 2 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)46 / 263 本章內(nèi)容流水線基本概念流水線

29、的性能分析 用一條用一條4段浮點(diǎn)加法器流水線求段浮點(diǎn)加法器流水線求8個(gè)浮點(diǎn)數(shù)的個(gè)浮點(diǎn)數(shù)的 和，要求所用時(shí)間最短，求流水線的吞吐率、和，要求所用時(shí)間最短，求流水線的吞吐率、 加速比和效率。加速比和效率。 ZABCDEFGH 由于存在著數(shù)據(jù)相關(guān)，如果直接交與流水線由于存在著數(shù)據(jù)相關(guān)，如果直接交與流水線 處理，效果與順序執(zhí)行完全一樣，因此先作處理，效果與順序執(zhí)行完全一樣，因此先作 一個(gè)簡單變換，然后交與流水線處理。一個(gè)簡單變換，然后交與流水線處理。 Z=(A+B)+(C+D)+(E+F)+(G+H) 3 之 1 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)47 / 263 本章內(nèi)容流水線基本概念流水線的性能分析 3 之 2 1

30、時(shí)間時(shí)間 空間空間 2 3求階差求階差4567 1 2 3 4567 1 2 3 4567 1 2 3 4567 對階對階 尾數(shù)加尾數(shù)加 規(guī)格化規(guī)格化 加數(shù)加數(shù)A C E GA+B E+F B D F HC+D G+H A+B+C+D E+F+G+H 結(jié)果結(jié)果A+B C+D E+F G+H A+B+C+D E+F+G+HZ 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)48 / 263 w 流水線的吞吐率為：流水線的吞吐率為： w 流水線的加速比為：流水線的加速比為： w 流水線的效率為：流水線的效率為： 本章內(nèi)容流水線基本概念流水線的性能分析 3 之 3 t 1 470 t15 7 T n TP m 871 t15 t74

31、 T T S m 0 470 t154 t74 E 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)49 / 263 本章內(nèi)容流水線基本概念 w 調(diào)度目的調(diào)度目的 w 非線性流水線的沖突非線性流水線的沖突 w 無沖突調(diào)度方法無沖突調(diào)度方法 w 優(yōu)化調(diào)度方法優(yōu)化調(diào)度方法 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)50 / 263 本章內(nèi)容流水線基本概念非線性流水線的調(diào)度技術(shù) 非線性流水線的調(diào)度目的是要找出一個(gè)非線性流水線的調(diào)度目的是要找出一個(gè) 最小的循環(huán)周期，按照這周期向流水線輸入最小的循環(huán)周期，按照這周期向流水線輸入 新任務(wù)，流水線的各個(gè)功能段都不會發(fā)生沖新任務(wù)，流水線的各個(gè)功能段都不會發(fā)生沖 突，而且流水線的吞吐率和效率最高。突，而且流水線的吞吐率和效

32、率最高。 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)51 / 263 本章內(nèi)容流水線基本概念非線性流水線的調(diào)度技術(shù) 向一條非線性流水線的輸入端順序輸入兩個(gè)任向一條非線性流水線的輸入端順序輸入兩個(gè)任 務(wù)之間的時(shí)間間隔稱為啟動距離務(wù)之間的時(shí)間間隔稱為啟動距離/等待時(shí)間等待時(shí)間。 幾個(gè)任務(wù)同時(shí)爭用同一個(gè)流水段的情況稱為非幾個(gè)任務(wù)同時(shí)爭用同一個(gè)流水段的情況稱為非 線性流水線的沖突線性流水線的沖突。 引起非線性流水線沖突的啟動距離成為禁止啟引起非線性流水線沖突的啟動距離成為禁止啟 動距離。動距離。 5 之 1 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)52 / 263 本章內(nèi)容流水線基本概念非線性流水線的調(diào)度技術(shù) 5 之 2 輸出輸出 S1S2S3S4 輸入

33、輸入 S4 S3 S2 S1 7654321 時(shí)間時(shí)間 流水段流水段 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)53 / 263 本章內(nèi)容流水線基本概念非線性流水線的調(diào)度技術(shù) 5 之 3 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)54 / 263 本章內(nèi)容流水線基本概念非線性流水線的調(diào)度技術(shù) 5 之 4 啟啟動動距距離離為為( (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

34、 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 啟啟動動周周期期 重重復(fù)復(fù)啟啟動動周周期期 不發(fā)生沖突的啟動距離一般是一個(gè)循環(huán)數(shù)列，稱為非線不發(fā)生沖突的啟動距離一般是一個(gè)循環(huán)數(shù)列，稱為非線 性流水線的啟動循環(huán)

35、，記作（性流水線的啟動循環(huán)，記作（1，7）。）。 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)55 / 263 啟動距離啟動距離5也可以認(rèn)為是一個(gè)循環(huán)數(shù)列，稱為非線性流也可以認(rèn)為是一個(gè)循環(huán)數(shù)列，稱為非線性流 水線的恒定循環(huán)，記作（水線的恒定循環(huán)，記作（5）。）。 本章內(nèi)容流水線基本概念非線性流水線的調(diào)度技術(shù) 5 之 5 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)56 / 263 本章內(nèi)容流水線基本概念非線性流水線的調(diào)度技術(shù) S4 S3 S2 S1 7654321 時(shí)間時(shí)間 流水段流水段 12 之 1 S1S2S3S4 輸入輸入 輸出輸出 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)57 / 263 本章內(nèi)容流水線基本概念非線性流水線的調(diào)度技術(shù) w 由預(yù)約表得到禁止向量由預(yù)約表得到

36、禁止向量 w 由禁止向量得到?jīng)_突向量由禁止向量得到?jīng)_突向量 w 由沖突向量構(gòu)造調(diào)度流水線的狀態(tài)圖由沖突向量構(gòu)造調(diào)度流水線的狀態(tài)圖 w 在狀態(tài)圖中找出可用啟動距離，并計(jì)算平均啟在狀態(tài)圖中找出可用啟動距離，并計(jì)算平均啟 動距離動距離 w 找出平均啟動距離最小的啟動循環(huán)或恒定循環(huán)找出平均啟動距離最小的啟動循環(huán)或恒定循環(huán) 12 之 2 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)58 / 263 本章內(nèi)容流水線基本概念非線性流水線的調(diào)度技術(shù)無沖突調(diào)度方法 w 由預(yù)約表得到禁止向量由預(yù)約表得到禁止向量 將一條非線性流水線的所有各功能段禁止將一條非線性流水線的所有各功能段禁止 啟動距離組合在一起形成的數(shù)列。啟動距離組合在一起形成的數(shù)列

37、。 將預(yù)約表中的每一行中任意兩個(gè)將預(yù)約表中的每一行中任意兩個(gè)“”之之 間的距離都計(jì)算出來，去掉重復(fù)的，由這間的距離都計(jì)算出來，去掉重復(fù)的，由這 些數(shù)形成禁止向量。些數(shù)形成禁止向量。 上例所示非線性流水線的禁止向量為（上例所示非線性流水線的禁止向量為（2， 4，6）。）。 12 之 3 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)59 / 263 本章內(nèi)容流水線基本概念非線性流水線的調(diào)度技術(shù)無沖突調(diào)度方法 w 由禁止向量得到?jīng)_突向量由禁止向量得到?jīng)_突向量 沖突向量用一個(gè)沖突向量用一個(gè)m位的二進(jìn)制數(shù)表示（其位的二進(jìn)制數(shù)表示（其 中中m是禁止向量中的最大值），一般格式是禁止向量中的最大值），一般格式 為為C=（CmCm-1CiC

38、2C1），），若若i在禁止在禁止 向量中，則向量中，則Ci =1，否則否則Ci =0，其中其中Cm一一 定為定為1。 上例所示非線性流水線的沖突向量為上例所示非線性流水線的沖突向量為C= （101010）。 12 之 4 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)60 / 263 本章內(nèi)容流水線基本概念非線性流水線的調(diào)度技術(shù)無沖突調(diào)度方法 w 由沖突向量構(gòu)造調(diào)度流水線的狀態(tài)圖由沖突向量構(gòu)造調(diào)度流水線的狀態(tài)圖 w將沖突向量將沖突向量C作為初始沖突向量送入一個(gè)作為初始沖突向量送入一個(gè)m位邏輯右移位邏輯右移 移位器，移位移位器，移位m次；次； w若移出的是若移出的是“0”，用移位器中的值與初始沖突向，用移位器中的值與初始沖突向

39、 量作量作“按位或按位或”運(yùn)算，得到一個(gè)新的沖突向量；運(yùn)算，得到一個(gè)新的沖突向量； w若移出的是若移出的是“1”，不作任何處理。，不作任何處理。 w將中間形成的每一個(gè)新的沖突向量同樣處理；將中間形成的每一個(gè)新的沖突向量同樣處理； w畫出狀態(tài)圖。畫出狀態(tài)圖。 在初始沖突向量和所有的新形成的沖突向量之間用在初始沖突向量和所有的新形成的沖突向量之間用 帶箭頭的線連接，表示各種狀態(tài)之間的轉(zhuǎn)換關(guān)系。帶箭頭的線連接，表示各種狀態(tài)之間的轉(zhuǎn)換關(guān)系。 12 之 5 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)61 / 263 本章內(nèi)容流水線基本概念非線性流水線的調(diào)度技術(shù)無沖突調(diào)度方法 12 之 6 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)62 / 263 本章內(nèi)容流

40、水線基本概念非線性流水線的調(diào)度技術(shù)無沖突調(diào)度方法 w 在狀態(tài)圖中找出可用啟動距離，并計(jì)算平在狀態(tài)圖中找出可用啟動距離，并計(jì)算平 均啟動距離均啟動距離 在狀態(tài)圖中從初始狀態(tài)出發(fā)，能構(gòu)成一種間在狀態(tài)圖中從初始狀態(tài)出發(fā)，能構(gòu)成一種間 隔拍數(shù)呈周期性重復(fù)的方案就是可用啟動距離。隔拍數(shù)呈周期性重復(fù)的方案就是可用啟動距離。 即：找出所有的簡單循環(huán)（是指在狀態(tài)圖中各種即：找出所有的簡單循環(huán)（是指在狀態(tài)圖中各種 沖突向量只經(jīng)過一次的啟動循環(huán)）。沖突向量只經(jīng)過一次的啟動循環(huán)）。 12 之 7 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)63 / 263 本章內(nèi)容流水線基本概念非線性流水線的調(diào)度技術(shù)無沖突調(diào)度方法 簡單循環(huán)簡單循環(huán)平均啟動距離

41、平均啟動距離 1，74 3，75 5，76 3，5，75 5，3，75 3，54 55 77 12 之 8 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)64 / 263 本章內(nèi)容流水線基本概念非線性流水線的調(diào)度技術(shù)無沖突調(diào)度方法 w 找出平均啟動距離最小的啟動循環(huán)或恒定找出平均啟動距離最小的啟動循環(huán)或恒定 循環(huán)循環(huán) （1，7）和（）和（3，5） （5） 12 之 9 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)65 / 263 本章內(nèi)容流水線基本概念非線性流水線的調(diào)度技術(shù)無沖突調(diào)度方法 最最小小啟啟動動循循環(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

42、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 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 啟啟動動周周期期 重重復(fù)復(fù)啟啟動動周周期期 12 之 10 S3

43、S2 S1 43215 S4 67 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)66 / 263 本章內(nèi)容流水線基本概念非線性流水線的調(diào)度技術(shù)無沖突調(diào)度方法 12 之 11 S3 S2 S1 43215 S4 67 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)67 / 263 本章內(nèi)容流水線基本概念非線性流水線的調(diào)度技術(shù)無沖突調(diào)度方法 恒恒定定啟啟動動循循環(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 X1 1 X X3

44、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 啟啟動動周周期期 重重復(fù)復(fù)啟啟動動周周期期 12 之 12 S3 S2 S1 43215 S4 67 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)68 / 263 本章內(nèi)容流水線基本概念非線性流水線的調(diào)度技術(shù) 當(dāng)采用最小啟動循環(huán)啟動非線性流水線時(shí)，沒當(dāng)采用最小啟動循環(huán)啟動非線性流水線時(shí)，沒 有充分發(fā)揮非線性流水線的效率，因?yàn)榱魉€中有充分發(fā)揮非線性流水線的效率，因?yàn)榱魉€

45、中 的許多流水段還有空閑，即使最繁忙的流水段也的許多流水段還有空閑，即使最繁忙的流水段也 有空閑。有空閑。 采用非線性流水線的優(yōu)化調(diào)度方法（預(yù)留算采用非線性流水線的優(yōu)化調(diào)度方法（預(yù)留算 法），可以使流水線的工作效率最高。法），可以使流水線的工作效率最高。 7 之 1 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)69 / 263 本章內(nèi)容流水線基本概念非線性流水線的調(diào)度技術(shù) L.E.Shar于于1972年提出流水線最小平均啟年提出流水線最小平均啟 動距離的限制范圍并于動距離的限制范圍并于1992年進(jìn)行了證明：年進(jìn)行了證明： w 最小平均啟動距離小于等于狀態(tài)圖中任意一個(gè)最小平均啟動距離小于等于狀態(tài)圖中任意一個(gè) 簡單循環(huán)的平均啟

46、動距離。簡單循環(huán)的平均啟動距離。 w 最小平均啟動距離的上限是沖突向量中最小平均啟動距離的上限是沖突向量中1 1的個(gè)數(shù)的個(gè)數(shù) 再加上再加上1 1。 7 之 2 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)70 / 263 本章內(nèi)容流水線基本概念非線性流水線的調(diào)度技術(shù) 最小啟動距離等于預(yù)約表中任意一行中最小啟動距離等于預(yù)約表中任意一行中“”的最大個(gè)的最大個(gè) 數(shù)。數(shù)。 為簡化流水線的控制邏輯，一般采用恒定循環(huán)作為最小為簡化流水線的控制邏輯，一般采用恒定循環(huán)作為最小 啟動循環(huán)。啟動循環(huán)。 對預(yù)約表中任意一行中任意兩個(gè)對預(yù)約表中任意一行中任意兩個(gè)“”之間的距離是最之間的距離是最 小啟動距離整數(shù)倍的通過插入延遲進(jìn)行預(yù)留。小啟動距離整

47、數(shù)倍的通過插入延遲進(jìn)行預(yù)留。 7 之 3 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)71 / 263 本章內(nèi)容流水線基本概念非線性流水線的調(diào)度技術(shù) S4 S3 S2 S1 7654321 時(shí)間時(shí)間 流水段流水段 S1S2S3S4 輸入輸入 輸出輸出 7 之 4 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)72 / 263 本章內(nèi)容流水線基本概念非線性流水線的調(diào)度技術(shù) S1S2S3S4 輸入輸入 輸出輸出 D1 時(shí)間時(shí)間12345678 功功 能能 段段 S1 S2 S3 S4 延遲延遲D1 7 之 5 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)73 / 263 從狀態(tài)從狀態(tài) 圖中很容易圖中很容易 可以看出：可以看出： 流水線的最流水線的最 小啟動循環(huán)小啟動循環(huán) 是（是（2）。

48、本章內(nèi)容流水線基本概念非線性流水線的調(diào)度技術(shù) 7 之 6 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)74 / 263 在非線性流水線中，在非線性流水線中，“”最多的流水段一定是最多的流水段一定是“瓶瓶 頸頸”流水段。實(shí)現(xiàn)最優(yōu)調(diào)度的目標(biāo)流水段。實(shí)現(xiàn)最優(yōu)調(diào)度的目標(biāo)是使是使“瓶頸瓶頸”流水段處流水段處 于忙碌狀態(tài)，沒有空閑周期于忙碌狀態(tài)，沒有空閑周期。 本章內(nèi)容流水線基本概念非線性流水線的調(diào)度技術(shù) 按按照照最最小小啟啟動動循循環(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

49、 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 5 延延 D D1 1 X X1 1 X X2 2 X X3 3 X X4 4 7 之 7 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)75

50、 / 263 w 基本概念基本概念 w 資源相關(guān)資源相關(guān) w 數(shù)據(jù)相關(guān)數(shù)據(jù)相關(guān) w 控制相關(guān)控制相關(guān) w 綜合應(yīng)用綜合應(yīng)用 w 循環(huán)處理循環(huán)處理 本章內(nèi)容 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)76 / 263 本章內(nèi)容相關(guān)性分析技術(shù) 相關(guān)（相關(guān)（Correlation or Dependency）也稱為沖突也稱為沖突 （Hazard）是指鄰近指令之間存在著某種關(guān)系，影響指令是指鄰近指令之間存在著某種關(guān)系，影響指令 的重疊執(zhí)行或流水線的正常運(yùn)行。的重疊執(zhí)行或流水線的正常運(yùn)行。 有三種類型的相關(guān)：有三種類型的相關(guān)： ：爭用部件。：爭用部件。 ：改變操作數(shù)的讀寫順序，使得順序執(zhí)行與：改變操作數(shù)的讀寫順序，使得順序執(zhí)行與

51、流水執(zhí)行時(shí)結(jié)果不同。流水執(zhí)行時(shí)結(jié)果不同。 ：分支、轉(zhuǎn)子程序、中斷。：分支、轉(zhuǎn)子程序、中斷。 2 之 1 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)77 / 263 本章內(nèi)容相關(guān)性分析技術(shù) 在介紹相關(guān)性分析技術(shù)時(shí)，我們以一個(gè)在介紹相關(guān)性分析技術(shù)時(shí)，我們以一個(gè) 典型的典型的RISC指令流水線（指令流水線（MIPS64指令集）指令集） 為例進(jìn)行介紹：為例進(jìn)行介紹： w MIPS基本流水線基本流水線 w MIPS擴(kuò)展流水線擴(kuò)展流水線 2 之 2 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)78 / 263 本章內(nèi)容相關(guān)性分析技術(shù)示例環(huán)境說明 采用采用MIPS64（MIPS的的64位版本）的整數(shù)子集：位版本）的整數(shù)子集：ALU指指 令（令（）、）、 load（

52、）/store（ ）指令和分支指令（指令和分支指令（）。）。 每一條每一條RISC指令的執(zhí)行至多需要指令的執(zhí)行至多需要5個(gè)時(shí)鐘周期：個(gè)時(shí)鐘周期： 、 、和和 。 13 之 1 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)79 / 263 本章內(nèi)容相關(guān)性分析技術(shù)示例環(huán)境說明 根據(jù)根據(jù)PC指示的地址從存儲器中取指令并裝入指示的地址從存儲器中取指令并裝入 指令寄存器（指令寄存器（IR），），同時(shí)同時(shí)PC加加4以獲取下一條指以獲取下一條指 令的地址。令的地址。IR中保存下一個(gè)時(shí)鐘周期需要的指令，中保存下一個(gè)時(shí)鐘周期需要的指令， NPC中保存下一條指令的中保存下一條指令的PC。 13 之 2 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)80 / 263 MEM/

53、WB 指 令 數(shù)據(jù) 存儲器 通用寄存器組 符號 位 擴(kuò)展 PC =0? ADD 16 32 4 存儲器 M U X 1 M U X 3 IR A B Imm IRrs IRrt MEM/WB.IR NPC IR ALUo B IR LMD ALUo IR EX/MEM ID/EX IF/ID ADD M X 4 U ALU 本章內(nèi)容相關(guān)性分析技術(shù)示例環(huán)境說明 13 之 3 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)81 / 263 本章內(nèi)容相關(guān)性分析技術(shù)示例環(huán)境說明 ，并結(jié)束分支指，并結(jié)束分支指 令（為簡單只設(shè)置一條：令（為簡單只設(shè)置一條：BEQZ）的操作。的操作。 13 之 4 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)82 / 263 MEM/

54、WB 指 令 數(shù)據(jù) 存儲器 通用寄存器組 符號 位 擴(kuò)展 PC =0? ADD 16 32 4 存儲器 M U X 1 M U X 3 IR A B Imm IRrs IRrt MEM/WB.IR NPC IR ALUo B IR LMD ALUo IR EX/MEM ID/EX IF/ID ADD M X 4 U ALU 本章內(nèi)容相關(guān)性分析技術(shù)示例環(huán)境說明 13 之 5 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)83 / 263 Load/Store指令指令 在本周期形成有效地在本周期形成有效地 址。址。ALU指令完成相指令完成相 應(yīng)的應(yīng)的ALU操作。操作。 本章內(nèi)容相關(guān)性分析技術(shù)示例環(huán)境說明 13 之 6 計(jì)算機(jī)系統(tǒng)

55、結(jié)構(gòu)84 / 263 MEM/WB 指 令 數(shù)據(jù) 存儲器 通用寄存器組 符號 位 擴(kuò)展 PC =0? ADD 16 32 4 存儲器 M U X 1 M U X 3 IR A B Imm IRrs IRrt MEM/WB.IR NPC IR ALUo B IR LMD ALUo IR EX/MEM ID/EX IF/ID ADD M X 4 U ALU 本章內(nèi)容相關(guān)性分析技術(shù)示例環(huán)境說明 13 之 7 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)85 / 263 本章內(nèi)容相關(guān)性分析技術(shù)示例環(huán)境說明 Load指令從存儲器中讀出數(shù)據(jù)并裝入指令從存儲器中讀出數(shù)據(jù)并裝入 LMD（裝入存儲器數(shù)據(jù)）寄存器，裝入存儲器數(shù)據(jù)）寄存器，St

56、ore指指 令將寄存器令將寄存器B中的數(shù)據(jù)寫入存儲器。中的數(shù)據(jù)寫入存儲器。 13 之 8 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)86 / 263 MEM/WB 指 令 數(shù)據(jù) 存儲器 通用寄存器組 符號 位 擴(kuò)展 PC =0? ADD 16 32 4 存儲器 M U X 1 M U X 3 IR A B Imm IRrs IRrt MEM/WB.IR NPC IR ALUo B IR LMD ALUo IR EX/MEM ID/EX IF/ID ADD M X 4 U ALU 本章內(nèi)容相關(guān)性分析技術(shù)示例環(huán)境說明 13 之 9 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)87 / 263 將結(jié)果寫入寄存將結(jié)果寫入寄存 器堆。寄存器的寫入器堆。寄存器的

57、寫入 端口在兩個(gè)目標(biāo)中選端口在兩個(gè)目標(biāo)中選 擇一個(gè)（擇一個(gè)（rt or rd），）， 具體選擇哪一個(gè)要由具體選擇哪一個(gè)要由 操作碼決定。操作碼決定。 本章內(nèi)容相關(guān)性分析技術(shù)示例環(huán)境說明 13 之 10 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)88 / 263 MEM/WB 指 令 數(shù)據(jù) 存儲器 通用寄存器組 符號 位 擴(kuò)展 PC =0? ADD 16 32 4 存儲器 M U X 1 M U X 3 IR A B Imm IRrs IRrt MEM/WB.IR NPC IR ALUo B IR LMD ALUo IR EX/MEM ID/EX IF/ID ADD M X 4 U ALU 本章內(nèi)容相關(guān)性分析技術(shù)示例環(huán)境說

58、明 13 之 11 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)89 / 263 本章內(nèi)容相關(guān)性分析技術(shù)示例環(huán)境說明 指指 令令 時(shí)鐘時(shí)鐘 123456789 iIFIDEX MEM WB i+1IFIDEX MEM WB i+2IFIDEX MEM WB i+3IFIDEX MEM WB i+4IFIDEX MEM WB 13 之 12 時(shí)空圖的另一種畫法時(shí)空圖的另一種畫法 指令存儲器指令存儲器 數(shù)據(jù)存儲器數(shù)據(jù)存儲器 時(shí)鐘周期時(shí)鐘周期 寫操作寫操作 （前半周期進(jìn)行）（前半周期進(jìn)行） 讀操作讀操作 （后半周期進(jìn)行）（后半周期進(jìn)行） 13 之 13 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)91 / 263 本章內(nèi)容相關(guān)性分析技術(shù)示例環(huán)境說明 3 之

59、1 在在MIPS基本流水線中引入浮點(diǎn)操作功能。基本流水線中引入浮點(diǎn)操作功能。 負(fù)責(zé)負(fù)責(zé)load/store、定點(diǎn)定點(diǎn)ALU操作和分支操作（功能同操作和分支操作（功能同 MIPS基本流水線）?；玖魉€）。 負(fù)責(zé)浮點(diǎn)負(fù)責(zé)浮點(diǎn)/定點(diǎn)乘法，采用流水設(shè)計(jì)。定點(diǎn)乘法，采用流水設(shè)計(jì)。 負(fù)責(zé)處理浮點(diǎn)加、減法及定點(diǎn)數(shù)負(fù)責(zé)處理浮點(diǎn)加、減法及定點(diǎn)數(shù)/浮點(diǎn)數(shù)之間的轉(zhuǎn)換，采浮點(diǎn)數(shù)之間的轉(zhuǎn)換，采 用流水設(shè)計(jì)。用流水設(shè)計(jì)。 負(fù)責(zé)浮點(diǎn)負(fù)責(zé)浮點(diǎn)/定點(diǎn)除法，不采用流水設(shè)計(jì)。定點(diǎn)除法，不采用流水設(shè)計(jì)。 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)92 / 263 本章內(nèi)容相關(guān)性分析技術(shù)示例環(huán)境說明 3 之 2 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)93 / 263 需要數(shù)據(jù)，需要數(shù)

60、據(jù)，已經(jīng)得到結(jié)果。已經(jīng)得到結(jié)果。 本章內(nèi)容相關(guān)性分析技術(shù)示例環(huán)境說明 3 之 3 MUL.DMUL.D IFIFIDIDM2M2M3M3M4M4M5M5M6M6MEMMEM WBWB ADD.DADD.DIFIFIDIDA2A2A3A3MEMMEM WBWB L.DL.DIFIFIDIDWBWB S.DS.DIFIFIDIDWBWB 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)94 / 263 本章內(nèi)容相關(guān)性分析技術(shù) 指重疊指令或流水線中的指令同時(shí)要用指重疊指令或流水線中的指令同時(shí)要用 同一個(gè)功能部件，實(shí)際上是一種沖突。同一個(gè)功能部件，實(shí)際上是一種沖突。 非線性流水線的調(diào)度就是為了盡量避免非線性流水線的調(diào)度就是為了盡量避免