1、 華北電力大學計算機系1130計算機組成與結構8.2流水線性能分析8.3流水線中的相關 結構相關結構相關 數據相關數據相關 控制相關控制相關8.4流水線的調度8.1流水線的基本概念第八章 流水線技術 華北電力大學計算機系2130計算機組成與結構8.1流水線原理8.1.1 流水線的基本概念 1. 產品生產流水線下面通過一個例子來說明流水線的好處下面通過一個例子來說明流水線的好處: : 兩種方案兩種方案 兩種方案的工作過程對比兩種方案的工作過程對比第八章 流水線技術 華北電力大學計算機系3211 華北電力大學計算機系4211 流水線生產過程的抽象描述流水線生產過程的抽象描述 這種流水工作方式的主要

2、特點這種流水工作方式的主要特點 華北電力大學計算機系5130計算機組成與結構8.1 流水線原理2. 2. 簡單的理想指令流水線簡單的理想指令流水線將處理機執行指令的過程分為三個功能段：將處理機執行指令的過程分為三個功能段：取指取指分析分析執行執行 指令經過各功能段時間分別為指令經過各功能段時間分別為t t取取、t t分分、t t執執 華北電力大學計算機系6130計算機組成與結構8.1 流水線原理(1)順序方式順序方式程序總執行時間為：程序總執行時間為：T順順ni=1(t取取+t分分+t執執)3nt取指取指i分析分析i執行執行i取指取指i+1分析分析i+1執行執行i+1 華北電力大學計算機系71

3、30計算機組成與結構8.1 流水線原理(2) 一次重疊方式一次重疊方式取指取指i-1分析分析i-1執行執行i-1取指取指i分析分析i執行執行i取指取指i+1分析分析i+1執行執行i+1程序總執行時間為：程序總執行時間為：T一次一次t取取t分分t執執ni=2(t分分+t執執)3 t (n-1)2 t(2n+1) t 華北電力大學計算機系8130計算機組成與結構8.1 流水線原理( (3) ) 二次重疊方式二次重疊方式 取指取指i-1i-1分析分析i-1i-1執行執行i-1i-1取指取指i i分析分析i i執行執行i i取指取指i+1i+1分析分析i+1i+1執行執行i+1i+1程序總執行時間為：

4、程序總執行時間為：T T二次二次i=2i=2t t取取t t分分t t執執n nt t執執3 3 t t (n-1) (n-1) t t(n+2) (n+2) t t 華北電力大學計算機系9130計算機組成與結構3. 先行控制技術先行控制技術( (1) ) 處理機結構的改變處理機結構的改變 傳統的處理機是傳統的處理機是控制器控制器分析指令，在控制器控制下，分析指令，在控制器控制下，由由運算器運算器完成指令的執行，它們是一個整體。完成指令的執行，它們是一個整體。 流水方式中，各功能段相互獨立沒有沖突，它們在流水方式中，各功能段相互獨立沒有沖突，它們在同一時刻可以并行工作，這就要求同一時刻可以并行

5、工作，這就要求取指取指、分析分析、執行執行三三個功能段相互獨立。個功能段相互獨立。8.1 流水線原理 華北電力大學計算機系10130計算機組成與結構 在處理機內部需要有獨立的在處理機內部需要有獨立的取指令取指令、分析指令分析指令和和執行指令執行指令的功能部件，將傳統處理機中的指令控制器分解成為三個獨立的功能部件，將傳統處理機中的指令控制器分解成為三個獨立的控制器：的控制器： 存儲控制器存儲控制器：負責流水線中各功能段對存儲器的訪問控制：負責流水線中各功能段對存儲器的訪問控制 包括取指令、取操作數、寫回運算結果包括取指令、取操作數、寫回運算結果 指令控制器指令控制器：完成取指令部件和分析指令部件

6、的控制：完成取指令部件和分析指令部件的控制 運算控制器運算控制器：對運算器的執行加以控制：對運算器的執行加以控制8.1 流水線原理 華北電力大學計算機系11130計算機組成與結構（2 2）解決多功能段訪存沖突問題）解決多功能段訪存沖突問題 當指令在流水線中執行時，在二次重疊方式下流水當指令在流水線中執行時，在二次重疊方式下流水線完全充滿時，三個功能段同時工作。線完全充滿時，三個功能段同時工作。u “ “取指取指i+1”i+1”要訪問存儲器取第要訪問存儲器取第i+1i+1條指令條指令u “ “分析分析i”i”要訪問存儲器取第要訪問存儲器取第i i條指令需要的操作數條指令需要的操作數u “ “執行

7、執行i-1”i-1”也要訪存將運算結果寫回存儲器也要訪存將運算結果寫回存儲器8.1 流水線原理 華北電力大學計算機系12130計算機組成與結構解決方法：解決方法： 1 1將程序地址空間和數據地址空間分開，兩個地址空將程序地址空間和數據地址空間分開，兩個地址空間提供獨立訪問的能力。間提供獨立訪問的能力。 2 2采用低位交叉并行訪問存儲器。采用低位交叉并行訪問存儲器。 3 3采用先行控制技術。采用先行控制技術。 8.1 流水線原理 華北電力大學計算機系13130計算機組成與結構采用先行控制技術的處理機結構采用先行控制技術的處理機結構主存主存儲器儲器存存儲儲器器控控制制器器先行取指令棧先行取指令棧先

8、行取數棧先行取數棧指令分析器指令分析器先行操作棧先行操作棧運算控制器運算控制器運算器運算器通通用用寄寄存存器器堆堆后行寫數棧后行寫數棧8.1 流水線原理 華北電力大學計算機系14130計算機組成與結構指令分析器現行程序計數器現行程序計數器PC采用先行取指令棧結構采用先行取指令棧結構存存儲儲器器控控制制器器先行程序計數器先行程序計數器PCI控制邏輯控制邏輯先行取指令棧先行取指令棧指令寄存器指令寄存器IR8.1 流水線原理 華北電力大學計算機系15130計算機組成與結構使用先行控制技術前使用先行控制技術前分析分析i-1執行執行i-1分析分析i執行執行i分析分析i+1執行執行i+1分析分析i+2執行

9、執行i+2分析分析i-1執行執行i-1分析分析i執行執行i分析分析i+1執行執行i+1分析分析i+2執行執行i+2流水線使用先行控制技術前后的不同：流水線使用先行控制技術前后的不同：使用先行控制技術后使用先行控制技術后8.1 流水線原理 華北電力大學計算機系16130計算機組成與結構4. 指令流水線指令流水線把指令的解釋過程分解為把指令的解釋過程分解為“分析分析”和和“執行執行”兩個子過程，并讓這兩個子過程分別用獨立的分兩個子過程，并讓這兩個子過程分別用獨立的分析部件和執行部件來實現。析部件和執行部件來實現。理想情況：理想情況：速度提高一倍速度提高一倍8.1 流水線原理 華北電力大學計算機系1

10、7211 華北電力大學計算機系18130計算機組成與結構5. 浮點加法流水線浮點加法流水線把浮點加法的全過程分解為把浮點加法的全過程分解為“求階差求階差”、“對對階階”、“尾數相加尾數相加”、“規格化規格化”四個子過程，四個子過程，并讓并讓它們分別用各自獨立的部件來實現。它們分別用各自獨立的部件來實現。理想情況：理想情況：速度提高速度提高3 3倍倍8.1 流水線原理 華北電力大學計算機系19130計算機組成與結構8.1 流水線原理 華北電力大學計算機系20130計算機組成與結構6. 時空圖時空圖時空圖時空圖從時間和空間兩個方面描述了流水從時間和空間兩個方面描述了流水線的工作過程。時空圖中，橫坐

11、標代表時間，線的工作過程。時空圖中，橫坐標代表時間，縱坐標代表流水線的各個段。縱坐標代表流水線的各個段。8.1 流水線原理 華北電力大學計算機系21211 華北電力大學計算機系22130計算機組成與結構7. 流水技術流水技術流水技術是指：將一個重復的時序過程分解是指：將一個重復的時序過程分解成為若干個子過程，而每個子過程都可有效地在成為若干個子過程，而每個子過程都可有效地在其專用功能段上與其他子過程同時執行。其專用功能段上與其他子過程同時執行。8流水技術的特點(1) (1) 流水過程由多個相聯系的子過程組成，每個流水過程由多個相聯系的子過程組成，每個子過程稱為流水線的子過程稱為流水線的“級級”

12、或或“段段”。“段段”的數的數目稱為流水線的目稱為流水線的“深度深度”。(2) (2) 每個子過程由專用的功能段實現；每個子過程由專用的功能段實現；8.1 流水線原理 華北電力大學計算機系23130計算機組成與結構(4) (4) 流水線需要有流水線需要有“通過時間通過時間”（第一個任務流出結果（第一個任務流出結果所所需的時間），在此之后流水過程才進入穩定工作狀需的時間），在此之后流水過程才進入穩定工作狀態，每一個時鐘周期（拍）流出一個結果；態，每一個時鐘周期（拍）流出一個結果；(3) (3) 各個功能段所需時間應盡量相等，否則，時間長各個功能段所需時間應盡量相等，否則，時間長的功能段將成為流水

13、線的瓶頸，會造成流水線的的功能段將成為流水線的瓶頸，會造成流水線的 “堵塞堵塞”和和“斷流斷流”。這個時間一般為一個時鐘。這個時間一般為一個時鐘周期周期（拍）；（拍）；(5) (5) 流水技術適合于大量重復的時序過程，只有輸入流水技術適合于大量重復的時序過程，只有輸入端能連續地提供任務，流水線的效率才能充分發端能連續地提供任務，流水線的效率才能充分發揮。揮。8.1 流水線原理 華北電力大學計算機系25130計算機組成與結構8.1.2 流水線的分類流水線可以按不同的觀點進行分類。流水線可以按不同的觀點進行分類。 單功能流水線：單功能流水線：只能完成一種固定功能的只能完成一種固定功能的 流水線。流

14、水線。 多功能流水線：多功能流水線：流水線的各段可以進行不同的流水線的各段可以進行不同的 連接，從而實現不同的功能。連接，從而實現不同的功能。 例如：例如： TI ASCTI ASC的多功能流水線的多功能流水線1按功能的多少來分8.1 流水線原理 華北電力大學計算機系27130計算機組成與結構在靜態流水線中，只有當輸入是一串相同在靜態流水線中，只有當輸入是一串相同的運算操作時，流水的效率才能得到發揮。的運算操作時，流水的效率才能得到發揮。動畫演示動畫演示2按同一時間內各段之間的連接方式來分 靜態流水線：靜態流水線：在同一時刻，流水線的各段只能在同一時刻，流水線的各段只能 按同一種功能的連接方式

15、工作。按同一種功能的連接方式工作。 8.1 流水線原理 華北電力大學計算機系28130計算機組成與結構 動態流水線：動態流水線：在同一時刻，流水線的各段可以在同一時刻，流水線的各段可以 按不同功能的連接方式工作。按不同功能的連接方式工作。 動畫演示動畫演示 這樣就不是非得相同運算的一串操作才能這樣就不是非得相同運算的一串操作才能 流水處理。流水處理。 優點：優點：能提高流水線的效率能提高流水線的效率 缺點：缺點：會使流水線的控制變得復雜會使流水線的控制變得復雜8.1 流水線原理 靜、動態流水線時空圖的對比靜、動態流水線時空圖的對比 華北電力大學計算機系30130計算機組成與結構3按照流水線的級

16、別來分 部件級流水線部件級流水線（運算操作流水線）：把處理機的（運算操作流水線）：把處理機的 算術邏輯部件分段，使得各種數據類型的操作能算術邏輯部件分段，使得各種數據類型的操作能 夠進行流水。夠進行流水。 處理機級流水線處理機級流水線（指令流水線）：把指令的解釋（指令流水線）：把指令的解釋 執行過程按照流水方式進行處理。執行過程按照流水方式進行處理。 例如：例如：前面把指令解釋過程分解為：前面把指令解釋過程分解為： 分析分析和和執行執行 DLXDLX的基本流水線把指令解釋過程分解為：的基本流水線把指令解釋過程分解為： 取指令、指令譯碼、執行、訪存、寫回。取指令、指令譯碼、執行、訪存、寫回。 (

17、 (圖示圖示) )8.1 流水線原理 華北電力大學計算機系31130計算機組成與結構8.1 流水線原理 華北電力大學計算機系32130計算機組成與結構 處理機間流水線處理機間流水線（宏流水線）：它是指由兩個（宏流水線）：它是指由兩個 以上的處理機串行地對同一數據流進行處理，以上的處理機串行地對同一數據流進行處理， 每個處理機完成一項任務。每個處理機完成一項任務。 動畫解析動畫解析8.1 流水線原理 華北電力大學計算機系33130計算機組成與結構4按照數據表示來分 向量處理機：向量處理機：具有向量指令和向量數據表示的具有向量指令和向量數據表示的 處理機。處理機。 例如：例如：TI ASC, CR

18、AY-I TI ASC, CRAY-I 等等 標量處理機：標量處理機：不具有向量指令和向量數據表示，不具有向量指令和向量數據表示， 僅對標量進行流水處理的處理機。僅對標量進行流水處理的處理機。 例如：例如：IBM860/91, Amdahl 470V/6IBM860/91, Amdahl 470V/6 等等5. 5. 按照是否有反饋回路來分按照是否有反饋回路來分 線性流水線：線性流水線：流水線中的各段串行連接，沒流水線中的各段串行連接，沒 有反饋回路。有反饋回路。 非線性流水線：非線性流水線：流水線中的各段除有串行連接流水線中的各段除有串行連接 外，還有反饋回路。外，還有反饋回路。 ( (舉例

19、舉例) )8.1 流水線原理 華北電力大學計算機系34130計算機組成與結構8.1 流水線原理 流水線的調度問題流水線的調度問題 華北電力大學計算機系36130計算機組成與結構順序流動流水線：順序流動流水線：流水線輸出端任務流出的順流水線輸出端任務流出的順 序與輸入端任務流入的順序序與輸入端任務流入的順序相同相同。 異步流動流水線異步流動流水線（亂序流水線）：流水線輸出（亂序流水線）：流水線輸出 端任務流出的順序與輸入端任務流入的順序端任務流出的順序與輸入端任務流入的順序 不同不同。6. 按照流動是否可以亂序來分8.1 流水線原理 華北電力大學計算機系37130計算機組成與結構8.2 流水線性

20、能分析吞吐率吞吐率是指單位時間內流水線所完成的任是指單位時間內流水線所完成的任務數或輸出結果的數量。務數或輸出結果的數量。1. 吞吐率(1) (1) 最大吞吐率最大吞吐率TPTPmaxmax 最大吞吐率最大吞吐率是指流水線在連續流動達到是指流水線在連續流動達到穩定狀態后所得到的吞吐率。穩定狀態后所得到的吞吐率。 若流水線各段的時間相等，均為若流水線各段的時間相等，均為t t0 0 ， 則：則： TPmax 1 /t0第八章 流水線技術 華北電力大學計算機系38130計算機組成與結構 若流水線各段的時間不等，則：若流水線各段的時間不等，則： 最大吞吐率取決于流水線中最慢的一段所最大吞吐率取決于流

21、水線中最慢的一段所 需的時間，這段就成了流水線的瓶頸。需的時間，這段就成了流水線的瓶頸。 消除瓶頸的方法消除瓶頸的方法 ( (舉例舉例) )l 細分瓶頸段細分瓶頸段 l 重復設置瓶頸段重復設置瓶頸段 ( (時時- -空圖空圖) )1 1maxmaxt ti i TPmax 8.2 流水線的性能分析重復設置瓶頸段重復設置瓶頸段( (時時- -空圖舉例空圖舉例) ) 華北電力大學計算機系41130計算機組成與結構 第一種情況：各段時間第一種情況：各段時間相等相等（設為（設為t t0 0） 假設流水線由假設流水線由 m m 段組成，完成段組成，完成 n n 個任務。個任務。l 時空圖時空圖l 完成完

22、成 n n 個任務所需的時間個任務所需的時間 T T流水流水m mt t0 0( (n n1)1)t t0 0 ( (說明說明) )(2) (2) 實際吞吐率實際吞吐率TPTP 流水線的實際吞吐率小于最大吞吐率。流水線的實際吞吐率小于最大吞吐率。8.2 流水線的性能分析 華北電力大學計算機系42211 華北電力大學計算機系43211完成完成 n n 個任務所需的時間個任務所需的時間 華北電力大學計算機系44130計算機組成與結構l 實際吞吐率實際吞吐率TP TP T T流水流水n nm mt t0 0( (n n) )t t0 0n n(1(1 ) )t t0 0 m m1 11 1TPTPm

23、axmaxn n 1 1n nm m1 1TP TP TPTPmaxmax當當n n m m 時，時，TP TP TPTPmaxmax 第二種情況：各段時間第二種情況：各段時間不等不等l 時空圖時空圖8.2 流水線的性能分析 華北電力大學計算機系45130計算機組成與結構8.2 流水線的性能分析 華北電力大學計算機系46130計算機組成與結構 l 完成完成 n n 個任務所需的時間個任務所需的時間 T T流水流水t ti i( (n n1)1)t tj j t tj jmaxmaxt ti i l 實際吞吐率實際吞吐率TP TP t ti i( (n n1)1)t tj jm mi=1i=1n

24、 ni=1i=1m m8.2 流水線的性能分析 華北電力大學計算機系47130計算機組成與結構加速比加速比是指流水線的速度與等功能非流水是指流水線的速度與等功能非流水線的速度之比。線的速度之比。2. 加速比S S ST T非流水非流水T T流水流水（其中（其中T T流水流水和和T T非流水非流水分別為按流水和按非流水分別為按流水和按非流水方式處理方式處理 n n 個任務所需的時間）個任務所需的時間） 若流水線為若流水線為 m m 段，且各段時間相等，均段，且各段時間相等，均為為t t0 0 ，則：，則： T T非流水非流水n mn mt t0 0 ( (解釋解釋) ) T T流水流水m mt

25、t0 0( (n n1)1)t t0 0 8.2 流水線的性能分析 華北電力大學計算機系48130計算機組成與結構8.2 流水線的性能分析 華北電力大學計算機系49130計算機組成與結構可以看出：可以看出：當當n n m m 時，時，S S m m想一想：想一想：n n 越大越好？越大越好？效率效率是指流水線的設備利用率。是指流水線的設備利用率。(1) (1) 由于流水線有由于流水線有通過時間和排空時間通過時間和排空時間，所以，所以 流水線的各段并不是一直滿負荷地工作。流水線的各段并不是一直滿負荷地工作。 故：故：E E 1 1S S T T非流水非流水T T流水流水nmnmt t0 0m m

26、t t0 0( (n n1 1) )t t0 0mnmnm mn n1 1m mn n1 1 m m1 1 8效率 E8.2 流水線的性能分析 華北電力大學計算機系50130計算機組成與結構8.2 流水線的性能分析 華北電力大學計算機系51130計算機組成與結構(2) (2) 若各段時間相等，則各段的效率若各段時間相等，則各段的效率e ei i相等，即相等，即 e e1 1e e2 2 e e8 8 e em mn nt t0 0T T流水流水 ( (解釋解釋) ) 整個流水線的效率為整個流水線的效率為: :當當 n n m m 時，時，E E 1 1E E n nt t0 0T T流水流水n

27、 nm mn n1 11n n1 m1(3) (3) 從時空圖上看，效率實際上就是從時空圖上看，效率實際上就是 n n 個任務所個任務所占的時空區與占的時空區與 m m 個段總的時空區個段總的時空區之比，即：之比，即： n n 個任務占用的時空區個任務占用的時空區E E ( (解釋解釋) ) m m 個段總的時空區個段總的時空區8.2 流水線的性能分析 華北電力大學計算機系52211 華北電力大學計算機系53130計算機組成與結構(4) (4) 提高流水線效率所采取的措施對于提高提高流水線效率所采取的措施對于提高 吞吐率也有好處。吞吐率也有好處。4流水線性能分析舉例例例8.18.1 在在靜態流

28、水線靜態流水線上計算上計算 A Ai iB Bi i ， 求：吞吐率，加速比，效率。求：吞吐率，加速比，效率。4 4i i=1=18.2 流水線的性能分析 華北電力大學計算機系54130計算機組成與結構8.2 流水線的性能分析 華北電力大學計算機系55130計算機組成與結構解解：( (1) 1) 確定適合于流水處理的確定適合于流水處理的計算過程計算過程(2) (2) 畫時空圖畫時空圖 (8) (8) 計算性能計算性能 吞吐率吞吐率 TPTP7 7(20(20t t) ) 加速比加速比 S S(34(34t t) )(20(20t t) )1.71.7 效率效率 E E(4(44 43 36)6

29、)(8(820)20)0.210.218.2 流水線的性能分析 華北電力大學計算機系56211 華北電力大學計算機系57211 華北電力大學計算機系58130計算機組成與結構8.2 流水線的性能分析 華北電力大學計算機系59130計算機組成與結構可以看出，在求解此問題時，該流水線的效率可以看出，在求解此問題時，該流水線的效率不高。不高。 ( (原因原因) )動態流水線的時空圖動態流水線的時空圖 舉例舉例 8.2 流水線的性能分析 華北電力大學計算機系60130計算機組成與結構舉例舉例 : : 這樣行不行？這樣行不行？ 正確答案正確答案8.2 流水線的性能分析 華北電力大學計算機系61130計算

30、機組成與結構5有關流水線性能的若干問題(1) (1) 流水線并不能減少流水線并不能減少( (而且一般是增加而且一般是增加) )單條指單條指 令的執行時間，但卻能提高吞吐率。令的執行時間，但卻能提高吞吐率。(2) (2) 增加流水線的深度增加流水線的深度( (段數段數) )可以提高流水線的可以提高流水線的 性能。性能。(3) (3) 流水線的深度受限于流水線的延遲和流水線流水線的深度受限于流水線的延遲和流水線 的額外開銷。的額外開銷。8.2 流水線的性能分析 華北電力大學計算機系62130計算機組成與結構8.3流水線中的相關1相關的概念 流水線中的相關流水線中的相關是指相鄰或相近的兩條指是指相鄰

31、或相近的兩條指令因存在某種關聯，后一條指令不能在原指定令因存在某種關聯，后一條指令不能在原指定的時鐘周期開始執行的時鐘周期開始執行。 結構相關結構相關 當硬件資源滿足不了同時重疊執行的指當硬件資源滿足不了同時重疊執行的指 令的要求，而發生資源沖突時，就發生令的要求，而發生資源沖突時，就發生了結了結 構相關。構相關。2相關的分類第八章 流水線技術 華北電力大學計算機系63130計算機組成與結構 數據相關數據相關 當一條指令需要用到前面某條指令的結當一條指令需要用到前面某條指令的結 果，從而不能重疊執行時，就發生了果，從而不能重疊執行時，就發生了數據相數據相 關關。 控制相關控制相關 當流水線遇到

32、分支指令和其他能夠改變當流水線遇到分支指令和其他能夠改變 PCPC值的指令時，就會發生值的指令時，就會發生控制相關控制相關。3幾個問題 相關有可能會使流水線停頓。相關有可能會使流水線停頓。8.3 流水線中的相關 華北電力大學計算機系64130計算機組成與結構在本章中，我們在本章中，我們約定：約定： 當一條指令被暫停時，暫停在其后發射（流出）的指令，但繼續執行在其前發射的 指令。 消除相關的消除相關的基本方法：基本方法： 讓流水線中的某些指令暫停，而讓其它讓流水線中的某些指令暫停，而讓其它 指令繼續執行。指令繼續執行。8.3 流水線中的相關 華北電力大學計算機系65130計算機組成與結構8.3.

33、1 流水線中的結構相關2. 如果某種指令組合因資源沖突而不能順利重 疊執行，則稱該機器具有結構相關。1. 在流水線機器中，為了使各種指令組合能順 利地重疊執行，需要把功能部件流水化，并 把資源重復設置。3. 常見的導致結構相關的原因： 功能部件不是全流水功能部件不是全流水 重復設置的資源的份數不夠重復設置的資源的份數不夠8.3 流水線中的相關 華北電力大學計算機系66130計算機組成與結構4. 結構相關舉例：訪存沖突 當數據和指令存在同一存儲器中時，訪當數據和指令存在同一存儲器中時，訪存指令會存指令會導致訪存沖突導致訪存沖突。解決辦法解決辦法： 插入暫停周期插入暫停周期 （“流水線氣泡流水線氣

34、泡”或或“氣泡氣泡”）8.3 流水線中的相關 華北電力大學計算機系69130計算機組成與結構引入暫停后的時空圖引入暫停后的時空圖8.3 流水線中的相關 華北電力大學計算機系70130計算機組成與結構5. 避免結構相關：6. 有些設計方案允許有結構相關 所有功能單元完全流水化所有功能單元完全流水化 設置足夠的硬件資源設置足夠的硬件資源硬件代價很大。硬件代價很大。 降低成本降低成本 減少部件的延遲減少部件的延遲解決方法解決方法： 設置相互獨立的指令存儲器和設置相互獨立的指令存儲器和 數據存儲器或設置相互獨立的數據存儲器或設置相互獨立的 指令指令CacheCache和數據和數據CacheCache。

35、8.3 流水線中的相關 華北電力大學計算機系71130計算機組成與結構8.3.2 流水線的數據相關1. 數據相關簡介 當指令在流水線中重疊執行時，流水線有當指令在流水線中重疊執行時，流水線有 可能改變指令讀可能改變指令讀/ /寫操作數的順序，使之不同寫操作數的順序，使之不同 于它們在非流水實現時的順序，這將導致數據于它們在非流水實現時的順序，這將導致數據 相關。相關。 數據相關舉例數據相關舉例8.3 流水線中的相關 華北電力大學計算機系73130計算機組成與結構2. 利用定向技術減少數據相關引起的暫停 (1)(1) 定向技術的定向技術的主要思路：主要思路：在發生上述在發生上述 數據相關時，后面

36、的指令并不是馬數據相關時，后面的指令并不是馬 上就要用到前一條指令的計算結果。上就要用到前一條指令的計算結果。 如果能夠將計算結果從其產生的地如果能夠將計算結果從其產生的地 方直接送到需要它的地方，就可以方直接送到需要它的地方，就可以 避免暫停。避免暫停。 (2) (2) 采用定向技術消除上例中的相關采用定向技術消除上例中的相關 工作過程演示工作過程演示8.3 流水線中的相關 華北電力大學計算機系76130計算機組成與結構(3) (3) 當定向硬件檢測到前面某條指令的結果寄存當定向硬件檢測到前面某條指令的結果寄存 器就是當前指令的源寄存器時，控制邏輯會器就是當前指令的源寄存器時，控制邏輯會 將

37、前面那條指令的結果直接從其產生的地方將前面那條指令的結果直接從其產生的地方 定向到當前指令所需的位置。定向到當前指令所需的位置。(4) (4) 一個功能單元的輸出不僅可以定向到其自身一個功能單元的輸出不僅可以定向到其自身 的輸入，而且還可以定向到其它單元的輸入。的輸入，而且還可以定向到其它單元的輸入。 舉例舉例8.3 流水線中的相關 華北電力大學計算機系77130計算機組成與結構8.3 流水線中的相關 華北電力大學計算機系78130計算機組成與結構(5) (5) 在在DLXDLX中，任何流水寄存器到任何功能單元的中，任何流水寄存器到任何功能單元的 輸入都可能需要定向路徑。輸入都可能需要定向路徑

38、。(6) (6) 當兩條指令對存儲器同一單元進行讀寫時，當兩條指令對存儲器同一單元進行讀寫時， 也可能發生數據相關。但本章僅討論有關寄也可能發生數據相關。但本章僅討論有關寄 存器的數據相關。存器的數據相關。3. 數據相關的分類 按照指令對寄存器的讀寫順序，可以將數據按照指令對寄存器的讀寫順序，可以將數據相關分為以下三種類型：相關分為以下三種類型：（考慮（考慮兩條指令兩條指令i i和和j j ， 假設假設i i 先進入流水線）先進入流水線）8.3 流水線中的相關 華北電力大學計算機系80130計算機組成與結構(2) (2) 寫后寫相關寫后寫相關 (WAW)(WAW) 在在 i i 寫入之前，寫入

39、之前，j j 先寫。先寫。 最后寫入的結果是最后寫入的結果是 i i 的，錯誤！的，錯誤！(1) (1) 寫后讀相關寫后讀相關 (RAW) (RAW) ( (命名規則命名規則) ) 在在 i i 寫入之前，寫入之前，j j 先去讀。先去讀。 j j 讀出的內容是錯誤的。讀出的內容是錯誤的。 這是最常見的相關。這是最常見的相關。 這種相關僅出現在這樣的流水線中這種相關僅出現在這樣的流水線中： 流水線中有多個段可以進行寫操作流水線中有多個段可以進行寫操作 當某條指令在流水線中暫停時，允許其后當某條指令在流水線中暫停時，允許其后 的指令繼續向前流動。的指令繼續向前流動。8.3 流水線中的相關 DLX

40、 DLX整數流水線中不會發生這種相關整數流水線中不會發生這種相關 （僅在（僅在WBWB段進行寫操作）段進行寫操作） 若對若對DLXDLX作以下修改，則會發生作以下修改，則會發生WAWWAW相關相關： 把把ALUALU操作指令的操作指令的“寫回寫回”移到移到MEMMEM段段 假設訪問數據存儲器需占用兩拍假設訪問數據存儲器需占用兩拍 舉例舉例 華北電力大學計算機系82130計算機組成與結構(3) (3) 讀后寫相關讀后寫相關 (WAR)(WAR)在在 i i 讀之前，讀之前，j j 先寫。先寫。i i 讀出的內容是錯誤的！讀出的內容是錯誤的！ 這種相關僅出現在這樣的流水線中：這種相關僅出現在這樣的

41、流水線中： 有些指令是在流水線的后部讀源操作數，有些指令是在流水線的后部讀源操作數， 而有些指令則是在流水線的前部寫結果。而有些指令則是在流水線的前部寫結果。 DLX DLX流水線中不會發生這種相關；流水線中不會發生這種相關； （讀在先（讀在先(ID),(ID),寫在后寫在后(WB)(WB)） 這種相關很少發生；這種相關很少發生； （因為流水線一般是先讀操作數，后寫結果）（因為流水線一般是先讀操作數，后寫結果） 復雜指令可能導致這種相關。復雜指令可能導致這種相關。8.3 流水線中的相關 華北電力大學計算機系83130計算機組成與結構(1) (1) 并非所有的數據相關都可以用定向技術解決并非所有

42、的數據相關都可以用定向技術解決 舉例舉例4. 需要暫停的數據相關8.3 流水線中的相關 華北電力大學計算機系85130計算機組成與結構(2) (2) 增加流水線互鎖硬件，插入增加流水線互鎖硬件，插入“暫停暫停”。 當互鎖硬件發現這種相關時，就當互鎖硬件發現這種相關時，就 暫停流水線暫停流水線，直到相關消失。直到相關消失。 舉例：舉例：演示演示A A 演示演示B B 8.3 流水線中的相關 華北電力大學計算機系87130計算機組成與結構8.3 流水線中的相關 華北電力大學計算機系88130計算機組成與結構例例8.58.5 假設某指令序列中假設某指令序列中2020的指令是的指令是LoadLoad指

43、令，指令，并且緊跟在并且緊跟在LoadLoad指令之后的半數指令需要使用到載指令之后的半數指令需要使用到載入的結果，如果這種數據相關將產生一個時鐘周期入的結果，如果這種數據相關將產生一個時鐘周期的延遲。理想流水線（沒有任何延遲，的延遲。理想流水線（沒有任何延遲，CPICPI為為1 1）的）的指令執行速度要比這種真實流水線的快多少？指令執行速度要比這種真實流水線的快多少？解解：我們可以利用我們可以利用CPICPI作為衡量標準。對于真實的流作為衡量標準。對于真實的流水線而言，由于水線而言，由于LoadLoad指令之后的半數指令需要暫停，指令之后的半數指令需要暫停，所以這些被暫停指令的所以這些被暫停

44、指令的CPICPI是是2 2。又知。又知LoadLoad指令占全指令占全部指令的部指令的2020，所以真實流水線的實際，所以真實流水線的實際CPICPI為：為：(0.9(0.91+0.11+0.12)=1.12)=1.1，這表示理想流水線的指令執，這表示理想流水線的指令執行速度是其執行速度的行速度是其執行速度的1.11.1倍倍。 8.3 流水線中的相關 華北電力大學計算機系89130計算機組成與結構5對數據相關的編譯調度方法 (1) (1) 流水線中常常會遇到許多種類型的暫停流水線中常常會遇到許多種類型的暫停 例如，按通常的代碼生成模式，表達式例如，按通常的代碼生成模式，表達式 A AB BC

45、 C的代碼會導致暫停的代碼會導致暫停8.3 流水線中的相關A AB BC C的代碼會導致暫停的代碼會導致暫停 華北電力大學計算機系91130計算機組成與結構(3) (3) 舉例：舉例： 例例8.68.6 請為下列表達式生成沒有暫停的請為下列表達式生成沒有暫停的DLXDLX 指令序列：指令序列： a ab bc c ； d de ef f ； 假設載入延遲為假設載入延遲為1 1個時鐘周期。個時鐘周期。 題解題解(2) (2) 編譯器可以通過重新排列代碼的順序來消編譯器可以通過重新排列代碼的順序來消除這種暫停，這種技術稱為除這種暫停，這種技術稱為流水線調度或流水線調度或 指令調度。指令調度。8.3

46、 流水線中的相關 華北電力大學計算機系93130計算機組成與結構(1) (1) 指令發射指令發射(issue)(issue)：指令從譯碼段：指令從譯碼段(ID)(ID)進入進入 執行段執行段(EX)(EX)。 相應的指令稱為相應的指令稱為已發射的指令已發射的指令。 (2) DLX(2) DLX整數流水線中，可以在整數流水線中，可以在IDID段檢測所有的段檢測所有的 數據相關；數據相關； 若數據相關，則在指令流出前，讓其暫停。若數據相關，則在指令流出前，讓其暫停。 (3) (3) 可以在可以在IDID段確定需要什么樣的定向，并設置段確定需要什么樣的定向，并設置 相應的控制；相應的控制； 這樣能減

47、少硬件復雜度這樣能減少硬件復雜度( (因為不必掛起已因為不必掛起已 改變了機器狀態的指令）。改變了機器狀態的指令）。6. 對DLX流水線控制的實現8.3 流水線中的相關 華北電力大學計算機系94130計算機組成與結構(4) (4) 也可以在需要用到操作數的那個時鐘周期檢測也可以在需要用到操作數的那個時鐘周期檢測 相關或定向；相關或定向；(5) (5) 舉例說明：舉例說明： 由由LoadLoad指令引起的指令引起的RAWRAW相關的互鎖相關的互鎖( (簡稱簡稱Load Load 互鎖互鎖) )可以通過可以通過IDID段的檢測來實現；段的檢測來實現； 到到ALUALU輸入的定向可以在輸入的定向可以

48、在EXEX段實現。段實現。LoadLoad互鎖互鎖 流水線相關硬件可以檢測到的各種相關情況流水線相關硬件可以檢測到的各種相關情況 可以看出，僅需把可以看出，僅需把LoadLoad指令的目的寄存指令的目的寄存 器地址與器地址與LoadLoad指令后的兩條指令的源寄存器指令后的兩條指令的源寄存器 地址進行比較。地址進行比較。8.3 流水線中的相關 在在IDID段檢測是否需要啟動段檢測是否需要啟動LoadLoad互鎖需要進行互鎖需要進行 三種比較三種比較 華北電力大學計算機系97130計算機組成與結構 當檢測到相關后，控制部件必須在流水線中當檢測到相關后，控制部件必須在流水線中 插入暫停周期，并使插

49、入暫停周期，并使IFIF和和IDID段中的指令停止段中的指令停止 前進。前進。l 將將ID/EXID/EX中的控制部分清中的控制部分清“O”O”。l IF/IDIF/ID內容回送到其自身入口。內容回送到其自身入口。定向邏輯定向邏輯 有更多的情況要考慮有更多的情況要考慮 關鍵思路：關鍵思路：流水線寄存器不僅包含數據，而且流水線寄存器不僅包含數據，而且 包含源寄存器和目的寄存器地址（字段）包含源寄存器和目的寄存器地址（字段）8.3 流水線中的相關 華北電力大學計算機系98130計算機組成與結構 所有的定向發生在：所有的定向發生在： ALUALU或或DMDM輸出輸出 ALU ALU輸入，輸入，DMD

50、M輸入，輸入， “ “O”O”檢測部件檢測部件 ( (圖示圖示) ) 華北電力大學計算機系99211 華北電力大學計算機系100130計算機組成與結構8.3.8 流水線的控制相關1. 分支指令的執行結果一、分支引起的暫停及減少分支開銷的方法 轉移失敗：轉移失敗：PCPC值加值加4 4 轉移成功：轉移成功：將將PCPC值改變為轉移目標地址值改變為轉移目標地址 到到MEMMEM段的末尾才改變段的末尾才改變 一旦檢測到分支指令一旦檢測到分支指令( (在在IDID段段) )，就暫停，就暫停執行其后的指令，直到分支指令到達執行其后的指令，直到分支指令到達MEMMEM段，段，確定出新的確定出新的PCPC值

51、為止。值為止。2. 處理分支指令最簡單的方法8.3 流水線中的相關 在在DLXDLX流水線中，分支轉移成功導致流水線中，分支轉移成功導致暫停暫停3 3個個時鐘周期時鐘周期。 若分支指令的頻度為若分支指令的頻度為8080，理想理想CPICPI1 1， 則則 實際實際CPICPI1 180803232 華北電力大學計算機系102130計算機組成與結構3. 減少分支開銷的兩種途徑 在流水線中盡早判斷分支轉移是否成功；在流水線中盡早判斷分支轉移是否成功； 轉移成功時，盡早計算出轉移目標地址。轉移成功時，盡早計算出轉移目標地址。兩者應同時采用，缺一不可。兩者應同時采用，缺一不可。對于對于DLXDLX作如

52、下改進作如下改進: :(1) (1) 把把“0 0？”測試移至測試移至IDID段；段；8.3 流水線中的相關 華北電力大學計算機系104130計算機組成與結構(2) (2) 在在IDID段增設一個加法器，這樣可以把分支段增設一個加法器，這樣可以把分支 開銷減少一拍。開銷減少一拍。 改進后流水線的分支操作改進后流水線的分支操作 （表（表8.58.5）8.3 流水線中的相關流流 水水 段段分分 支支 指指 令令 操操 作作IFIFIDIDEXEXIF/ID.IR IF/ID.IR MemPC MemPC; IF/ID.NPC,PC ; IF/ID.NPC,PC (if ID/EX.cond (if

53、 ID/EX.cond ID/EX.NPC else PC+4); ID/EX.NPC else PC+4);ID/EX.A ID/EX.A RegsIF/ID.IR RegsIF/ID.IR6.106.10; ID/EX.B ; ID/EX.B RegsIF/ID.IR RegsIF/ID.IR11.1511.15;ID/EX.NPC ID/EX.NPC IF/ID.NPC + (IR IF/ID.NPC + (IR1616) )1616#IR#IR16.8116.81; ;ID/EX.IR ID/EX.IR IF/ID.IR; ID/EX.cond IF/ID.IR; ID/EX.cond

54、 (RegsIF/ID.IR (RegsIF/ID.IR6.106.10 op 0; op 0;ID/EX.ImmID/EX.Imm (IR (IR1616) )1616#IR#IR16.8116.81; ;MEMMEMWBWB表 8.5 改進后流水線的分支操作( (動畫演示動畫演示) )( (動畫演示動畫演示) ) 華北電力大學計算機系106130計算機組成與結構二、程序中分支的行為特點1. 各種能改變各種能改變PCPC值的指令的執行頻度值的指令的執行頻度 （SPECSPEC基準程序，基準程序，DLXDLX上執行）上執行） 條件分支條件分支 整數程序：整數程序：14141515 浮點程序：浮

55、點程序：8 81212 向前分支與向后分支的比：向前分支與向后分支的比： 8181 無條件分支無條件分支 絕大多數：絕大多數：448.3 流水線中的相關 華北電力大學計算機系108130計算機組成與結構2條件分支轉移成功的概率條件分支轉移成功的概率 平均值平均值 整數程序整數程序 向前：向前：1818無條件：無條件：4 4 向后：向后：8 8 浮點程序浮點程序 向前：向前：7 7 無條件：無條件：1 1 向右：向右：8 8所有條件分支：所有條件分支：6767向前：向前：6060向后：向后：8585（向后分支一般形成循環）（向后分支一般形成循環）8.3 流水線中的相關 華北電力大學計算機系109

56、130計算機組成與結構8.3 流水線中的相關 華北電力大學計算機系110130計算機組成與結構三、減少流水線分支損失的方法（種簡單的靜態方法，編譯時預測）（種簡單的靜態方法，編譯時預測）1. “凍結”或“排空”流水線 在流水線中停住或刪除分支后的指令，在流水線中停住或刪除分支后的指令，直到知道轉移目標地址。直到知道轉移目標地址。 優點：優點：簡單。簡單。2預測分支失敗 流水線繼續照常流動，就像沒發生什么似的。流水線繼續照常流動，就像沒發生什么似的。8.3 流水線中的相關 華北電力大學計算機系111130計算機組成與結構 在知道分支結果之前，分支指令后的指令不在知道分支結果之前，分支指令后的指令

57、不 能改變機器狀態，或者改變了之后能夠回退。能改變機器狀態，或者改變了之后能夠回退。 若分支失敗，則照常執行；否則，從轉移目若分支失敗，則照常執行；否則，從轉移目 標處開始取指令執行。標處開始取指令執行。 DLXDLX流水線的處理過程流水線的處理過程8.3 流水線中的相關 華北電力大學計算機系113130計算機組成與結構3. 3. 預測分支成功預測分支成功 假設分支轉移成功，并開始從分支目標地址假設分支轉移成功，并開始從分支目標地址 處取指令執行。處取指令執行。 起作用的前題：先知道分支目標地址，后知起作用的前題：先知道分支目標地址，后知 道分支是否成功。道分支是否成功。 對對DLXDLX流水

58、線沒有任何好處。流水線沒有任何好處。8.3 流水線中的相關 華北電力大學計算機系114130計算機組成與結構4. 延遲分支 (delayed branch)(delayed branch) (1)(1) 基本概念基本概念 把分支開銷為把分支開銷為n n 的分支指令看成是延遲長的分支指令看成是延遲長 度為度為n n 的分支指令，其后緊跟有的分支指令，其后緊跟有n n 個延遲槽。個延遲槽。 流水線遇到分支指令時，按正常方式處理，順流水線遇到分支指令時，按正常方式處理，順 帶執行延遲槽中的指令，從而減少分支開銷。帶執行延遲槽中的指令，從而減少分支開銷。 延遲分支以及指令的執行順序延遲分支以及指令的執

59、行順序 8.3 流水線中的相關 華北電力大學計算機系116130計算機組成與結構(2)(2) 具有一個分支延遲槽的具有一個分支延遲槽的DLXDLX流水線的流水線的執行過程執行過程分支延遲槽中的指令分支延遲槽中的指令“掩蓋掩蓋”了流水線原來了流水線原來 必需插入的暫停周期。必需插入的暫停周期。8.3 流水線中的相關 華北電力大學計算機系117211延遲分支指令延遲分支指令(i+1) 指令指令(i+2) 指令指令(i+3) 指令指令(i+4)延遲分支指令延遲分支指令(i+1) 華北電力大學計算機系118130計算機組成與結構8.4 流水線的調度8.4.1 線性流水線的調度1. 靜態調度 在指令執行

60、之前，利用軟件的手段生成適在指令執行之前，利用軟件的手段生成適合流水線工作特點、盡可能減少指令執行過程合流水線工作特點、盡可能減少指令執行過程相關性的機器代碼，并對代碼優化的調度方法。相關性的機器代碼，并對代碼優化的調度方法。 優化延遲轉移技術優化延遲轉移技術 展開循環體后調度方法展開循環體后調度方法第三章 流水線技術 華北電力大學計算機系119130計算機組成與結構2. 動態調度 在程序執行過程中，由硬件重新安排指令的執行順在程序執行過程中，由硬件重新安排指令的執行順序，以減少流水線停頓的方法。序，以減少流水線停頓的方法。 CDC記分牌法記分牌法 Tomasulo動態指令調度算法動態指令調度