1、 2022-4-301第第8 8章章流水線處理技術流水線處理技術 2022-4-302本章主要內容本章主要內容 流水線的基本概念流水線的基本概念 概念、表示方法、特點和分類概念、表示方法、特點和分類 流水線的性能指標流水線的性能指標 吞吐率、加速比和效率吞吐率、加速比和效率 流水線的實現原理流水線的實現原理 DLX流水線實例流水線實例 流水線的流水線的“相關相關”問題問題 結構相關、數據相關和控制相關結構相關、數據相關和控制相關 指令級并行技術簡介指令級并行技術簡介 2022-4-303流水線的基本概念流水線的基本概念 不是計算機設計和實現領域所特有的技術不是計算機設計和實現領域所特有的技術在

2、計算機還沒有出現以前，工業生產中早已經廣在計算機還沒有出現以前，工業生產中早已經廣泛使用流水線方式進行生產。泛使用流水線方式進行生產。 2022-4-304流水線的基本概念流水線的基本概念 計算機中的流水線是把一個重復的過程分解為若干個子過程，每個子計算機中的流水線是把一個重復的過程分解為若干個子過程，每個子過程與其他子過程并行進行。由于這種工作方式與工廠中的生產流水過程與其他子過程并行進行。由于這種工作方式與工廠中的生產流水線十分相似，因此稱為線十分相似，因此稱為流水線技術流水線技術。 通常，可以從兩個方面來提高處理機內部的并行性，一個是所謂的通常，可以從兩個方面來提高處理機內部的并行性，一

3、個是所謂的空空間并行性間并行性，即在一個處理機內設置多個獨立的操作部件，并且使這些，即在一個處理機內設置多個獨立的操作部件，并且使這些部件并行工作；另一個是所謂的部件并行工作；另一個是所謂的時間并行性時間并行性，就是采用流水線技術。，就是采用流水線技術。流水線技術是一種非常經濟、對提高計算機的運算速度非常有效的技流水線技術是一種非常經濟、對提高計算機的運算速度非常有效的技術。采用流水線技術只需增加少量硬件就能把計算機的運算速度提高術。采用流水線技術只需增加少量硬件就能把計算機的運算速度提高幾倍，成為計算機中普遍使用的一種并行處理技術。幾倍，成為計算機中普遍使用的一種并行處理技術。 計算機各個部

4、分幾乎都可以采用流水線技術，如果指令的執行過程可計算機各個部分幾乎都可以采用流水線技術，如果指令的執行過程可以采用流水線，那么稱為以采用流水線，那么稱為指令流水線指令流水線。運算器中的操作部件，如浮點。運算器中的操作部件，如浮點加法器、浮點乘法器等可以采用流水線，稱為加法器、浮點乘法器等可以采用流水線，稱為操作部件流水線操作部件流水線；多個；多個計算機之間，通過存儲器連接，也可以采用流水線，計算機之間，通過存儲器連接，也可以采用流水線，稱為宏流水線稱為宏流水線。 2022-4-305流水線的基本概念流水線的基本概念 一條指令的執行過程可以分為多個階段一條指令的執行過程可以分為多個階段取指令：按

5、照指令計數器的內容訪問主存儲器，取指令：按照指令計數器的內容訪問主存儲器， 取出一條指令送到指令寄存器。取出一條指令送到指令寄存器。指令分析：對指令操作碼進行譯碼，按照給定的指令分析：對指令操作碼進行譯碼，按照給定的尋址方式和地址字段中的內容形成操作數的地址，尋址方式和地址字段中的內容形成操作數的地址，并用這個地址讀取操作數。并用這個地址讀取操作數。指令執行：根據操作碼的要求，完成指令規定的指令執行：根據操作碼的要求，完成指令規定的功能，即把運算結果寫到通用寄存器或主存中。功能，即把運算結果寫到通用寄存器或主存中。 2022-4-306流水線的基本概念流水線的基本概念 指令的幾種執行方式指令的

6、幾種執行方式 指令多次重疊執行方式實際上就是指令流水線指令多次重疊執行方式實際上就是指令流水線 2022-4-307流水線的基本概念流水線的基本概念 如果取指令、分析指令、執行指令的時間都相等，如果取指令、分析指令、執行指令的時間都相等，每段的時間都為每段的時間都為t，則，則n條指令所用的時間為：條指令所用的時間為： 順序執行順序執行 一次重疊執行一次重疊執行 兩次重疊執行兩次重疊執行 ntT3tnT)21 ( tnT)2( 2022-4-308流水線的表示方法流水線的表示方法 流水線的每一個階段完成一條指令的一部分，不同階段并流水線的每一個階段完成一條指令的一部分，不同階段并行完成不同指令的

7、不同部分。行完成不同指令的不同部分。 流水線中的每一個階段稱為一個流水階段、流水節拍、流流水線中的每一個階段稱為一個流水階段、流水節拍、流水步、流水段、功能段、流水級等。一個流水階段與另一水步、流水段、功能段、流水級等。一個流水階段與另一個流水階段相連接形成流水線。個流水階段相連接形成流水線。 指令從流水線的一端進入，經過流水線的處理，從另一端指令從流水線的一端進入，經過流水線的處理，從另一端流出。目前大部分處理機的指令流水線在流出。目前大部分處理機的指令流水線在312段之間。段之間。 流水線常用的兩種表示方法流水線常用的兩種表示方法 流水線連接圖表示法，各個流水段順序連接在一起流水線連接圖表

8、示法，各個流水段順序連接在一起 流水線時空圖表示法，直觀描述流水線工作過程流水線時空圖表示法，直觀描述流水線工作過程 2022-4-309 流水線連接圖表示法流水線連接圖表示法流水線的表示方法流水線的表示方法 2022-4-3010流水線的表示方法流水線的表示方法 流水線時空圖表示法流水線時空圖表示法在時空圖中，橫坐標表示時間，也就是輸入到流水線中在時空圖中，橫坐標表示時間，也就是輸入到流水線中的各個任務在流水線中所經過的時間。當流水線中各個的各個任務在流水線中所經過的時間。當流水線中各個流水段的執行時間都相等時，橫坐標被分割成相等長度流水段的執行時間都相等時，橫坐標被分割成相等長度的時間段。

9、縱坐標表示空間，即流水線的每一個流水段。的時間段?？v坐標表示空間，即流水線的每一個流水段。 2022-4-3011流水線的特點流水線的特點 第一，把一個任務（一條指令或一個操作）分解為幾個第一，把一個任務（一條指令或一個操作）分解為幾個有聯系的子任務，每個子任務由一個專門的功能部件來有聯系的子任務，每個子任務由一個專門的功能部件來實現。實現。 第二，流水線每一個功能段部件后面都要有一個緩沖寄第二，流水線每一個功能段部件后面都要有一個緩沖寄存器，或稱為鎖存器，其作用是保存本流水段的結果。存器，或稱為鎖存器，其作用是保存本流水段的結果。 2022-4-3012流水線的特點流水線的特點 第三，流水線

10、中各功能段的時間應盡量相等，否第三，流水線中各功能段的時間應盡量相等，否則將引起堵塞、斷流。要求流水線的時鐘周期不則將引起堵塞、斷流。要求流水線的時鐘周期不能快于最慢的流水段。能快于最慢的流水段。 第四，只有第四，只有連續不斷連續不斷地提供同一種任務時才能發地提供同一種任務時才能發揮流水線的效率，所以在流水線中處理的必須是揮流水線的效率，所以在流水線中處理的必須是連續任務。連續任務。 第五，流水線需要有第五，流水線需要有裝入時間裝入時間和和排空時間排空時間。裝入。裝入時間是指第一個任務進入流水線到輸出流水線的時間是指第一個任務進入流水線到輸出流水線的時間。排空時間是指第時間。排空時間是指第n個

11、（最后一個）任務進入個（最后一個）任務進入流水線到輸出流水線的時間。流水線到輸出流水線的時間。 2022-4-3013流水線的分類流水線的分類 部件功能級流水線部件功能級流水線所謂功能部件級流水線也可以稱為運算操作流水線（所謂功能部件級流水線也可以稱為運算操作流水線（Arithmetic Pipelines）。前面的浮點加法器就是一種典型的功能部件級流水線。）。前面的浮點加法器就是一種典型的功能部件級流水線。 處理機級流水線處理機級流水線所謂處理機級流水線，又叫指令流水線（所謂處理機級流水線，又叫指令流水線（Instruction Pipelines），它），它是把解釋指令的過程按照流水方式處

12、理，使處理機能夠重疊地解釋多是把解釋指令的過程按照流水方式處理，使處理機能夠重疊地解釋多條指令。條指令。 處理機間級流水線處理機間級流水線所謂處理機間流水線，又被稱為宏流水線（所謂處理機間流水線，又被稱為宏流水線（Macro Pipelines）。這種）。這種流水線由兩個或者兩個以上的處理機通過存儲器串行連接起來，每個流水線由兩個或者兩個以上的處理機通過存儲器串行連接起來，每個處理機完成整個任務的一部分。處理機完成整個任務的一部分。 2022-4-3014流水線的分類流水線的分類 單功能流水線單功能流水線如果一條流水線只如果一條流水線只能完成一種固定的能完成一種固定的功能，這種流水線功能，這種

13、流水線稱為單功能流水線。稱為單功能流水線。 多功能流水線多功能流水線多功能流水線是指多功能流水線是指流水線各段可以進流水線各段可以進行不同的連接。在行不同的連接。在不同時間內，或者不同時間內，或者在同一時間內，通在同一時間內，通過不同的連接方式過不同的連接方式實現不同的功能。實現不同的功能。 2022-4-3015流水線的分類流水線的分類靜態流水線靜態流水線所謂靜態流水線是指所謂靜態流水線是指在同一段時間內，多在同一段時間內，多功能流水線中的各個功能流水線中的各個功能段只能夠按照一功能段只能夠按照一種固定的方式連接，種固定的方式連接，實現一種固定的功能。實現一種固定的功能。只有當按照這種連接只

14、有當按照這種連接方式工作的所有任務方式工作的所有任務都流出流水線之后，都流出流水線之后，多功能流水線才能重多功能流水線才能重新進行連接。新進行連接。動態流水線動態流水線而動態流水線是指在而動態流水線是指在同一段時間內，多功同一段時間內，多功能流水線中的各段可能流水線中的各段可以按照不同的方式連以按照不同的方式連接，同時執行多種功接，同時執行多種功能。這種同時實現多能。這種同時實現多種連接方式是有條件種連接方式是有條件的，即流水線中的各的，即流水線中的各個功能部件之間不能個功能部件之間不能發生沖突。發生沖突。 2022-4-3016流水線的分類流水線的分類 線性流水線線性流水線所謂線性流水線是將

15、流水線的各段串行連接起來，沒有反饋回路。所謂線性流水線是將流水線的各段串行連接起來，沒有反饋回路。輸入數據從流水線的一端進入，從另一端輸出。數據在流水線的各輸入數據從流水線的一端進入，從另一端輸出。數據在流水線的各個功能段流過時，每個功能段都流過且僅流過一次。個功能段流過時，每個功能段都流過且僅流過一次。 非線性流水線非線性流水線而非線性流水線則是在流水線的各個功能段之間除了有串行的連接而非線性流水線則是在流水線的各個功能段之間除了有串行的連接之外，還有反饋回路。之外，還有反饋回路。 2022-4-3017流水線的分類流水線的分類 其他的流水線分類方法其他的流水線分類方法按照數據表示方式的不同

16、，可以把流水線分為標量流水按照數據表示方式的不同，可以把流水線分為標量流水線（處理機無向量數據表示，僅對標量數據進行流水處線（處理機無向量數據表示，僅對標量數據進行流水處理）和向量流水線（處理機有向量數據表示，有向量指理）和向量流水線（處理機有向量數據表示，有向量指令）兩種。本章主要介紹的都是標量流水線。令）兩種。本章主要介紹的都是標量流水線。在線性流水線中，根據對流水線控制方式的不同，可以在線性流水線中，根據對流水線控制方式的不同，可以把流水線分為同步流水線和異步流水線兩類。本章中介把流水線分為同步流水線和異步流水線兩類。本章中介紹的都是同步流水線，一般的宏流水線采用異步流水線紹的都是同步流

17、水線，一般的宏流水線采用異步流水線方式。方式。按照流水線輸出端流出的任務與流水線輸入端流入的任按照流水線輸出端流出的任務與流水線輸入端流入的任務的順序是否相同，還可以把流水線分為順序流水線和務的順序是否相同，還可以把流水線分為順序流水線和亂序流水線（又可稱為錯序流水線或者無序流水線）兩亂序流水線（又可稱為錯序流水線或者無序流水線）兩種。種。 2022-4-3018流水線的性能指標流水線的性能指標 衡量流水線性能的主要指標有衡量流水線性能的主要指標有吞吐率吞吐率、加速比加速比和和效率效率。 流水線設計中，流水線的流水線設計中，流水線的最佳段數最佳段數選擇也是一個選擇也是一個重要問題。重要問題。

18、下面以線性流水線為例，分析流水線的主要性能下面以線性流水線為例，分析流水線的主要性能指標。其分析方法和有關公式也適用于非線性流指標。其分析方法和有關公式也適用于非線性流水線。水線。 2022-4-3019流水線的性能指標流水線的性能指標 流水線的吞吐率流水線的吞吐率吞吐率（吞吐率（Throughput Rate）是衡量流水線速度）是衡量流水線速度的重要指標。它是指在單位時間內流水線所完成的重要指標。它是指在單位時間內流水線所完成的任務數量，或是輸出結果的數量，計算流水線的任務數量，或是輸出結果的數量，計算流水線吞吐率的最基本的公式表示為：吞吐率的最基本的公式表示為：上面公式中，上面公式中，n為

19、任務數，為任務數，Tk為處理完成為處理完成n個任個任務所用的時間。務所用的時間。 kTnTP 2022-4-3020流水線的性能指標流水線的性能指標 流水線的吞吐率流水線的吞吐率各個流水段執行時間相等的情況，各個流水段執行時間相等的情況，k為流水線的段數，為流水線的段數， t為時鐘周期。為時鐘周期。從流水線輸出端看，用從流水線輸出端看，用k個時鐘周期輸出第一個任務，其余個時鐘周期輸出第一個任務，其余n1個個時鐘周期，每個時鐘周期輸出一個任務，即用時鐘周期，每個時鐘周期輸出一個任務，即用n1個時鐘周期輸出個時鐘周期輸出n1個任務。因此，流水線完成個任務。因此，流水線完成n個連續任務需要的總時間為

20、：個連續任務需要的總時間為： tnkTk) 1( 2022-4-3021流水線的性能指標流水線的性能指標 流水線的吞吐率流水線的吞吐率流水線的實際吞吐率為：流水線的實際吞吐率為：當連續輸入的任務當連續輸入的任務n時，得最大吞吐率為：時，得最大吞吐率為：最大吞吐率與實際吞吐率的關系是：最大吞吐率與實際吞吐率的關系是： tnknTP) 1(ttnknLimTPn1)1(maxmax) 1(TPnknTP 2022-4-3022流水線的性能指標流水線的性能指標 流水線的加速比流水線的加速比完成同樣一批任務，不使用流水線所用的時間與完成同樣一批任務，不使用流水線所用的時間與使用流水線所用的時間之比稱為

21、流水線的加速比使用流水線所用的時間之比稱為流水線的加速比（Speedup Ratio）。）。設設T0表示不使用流水線，即順序執行所用的時間，表示不使用流水線，即順序執行所用的時間，Tk表示使用流水線時的執行時間，則流水線加速表示使用流水線時的執行時間，則流水線加速比比S的基本公式為：的基本公式為： kTTS0 2022-4-3023流水線的性能指標流水線的性能指標 流水線的加速比流水線的加速比如果流水線各段執行時間都相等，則一條如果流水線各段執行時間都相等，則一條k段流段流水線完成水線完成n個連續任務實際加速比為：個連續任務實際加速比為：上述情況下的最大加速比為：上述情況下的最大加速比為： 1

22、) 1(nkkntnktknSknkknLimSn1max 2022-4-3024流水線的性能指標流水線的性能指標 流水線的效率流水線的效率流水線的設備利用率稱為流水線的效率（流水線的設備利用率稱為流水線的效率（Efficiency）。）。在時空圖上，流水線的效率定義為完成在時空圖上，流水線的效率定義為完成n個任務占用的時個任務占用的時空區有效面積與空區有效面積與n個任務所用的時間與個任務所用的時間與k個流水段所圍成個流水段所圍成的時空區總面積之比。因此，流水線的效率包含了時間的時空區總面積之比。因此，流水線的效率包含了時間和空間兩個因素。和空間兩個因素。n個任務占用的時空區有效面積就是順序執

23、行個任務占用的時空區有效面積就是順序執行n個任務所個任務所使用的總的時間使用的總的時間T0，而，而n個任務所用的時間與個任務所用的時間與k個流水段個流水段所圍成的時空區總面積為所圍成的時空區總面積為kTk，其中，其中Tk是流水線完成是流水線完成n個個任務所使用的總時間，計算流水線效率的一般公式可以任務所使用的總時間，計算流水線效率的一般公式可以表示為：表示為：kkTTknnE0總面積個流水段所圍的時空區效面積個任務占用的時空區有個任務所用的時間與 2022-4-3025流水線的性能指標流水線的性能指標 流水線的效率流水線的效率如果流水線的各段執行時間均相等，而且輸入的如果流水線的各段執行時間均

24、相等，而且輸入的n個任務是連續的，則一條個任務是連續的，則一條k段流水線的效率為：段流水線的效率為：在流水線的各段執行時間均相等，輸入到流水線在流水線的各段執行時間均相等，輸入到流水線的任務是連續的情況下，流水線的最高效率為：的任務是連續的情況下，流水線的最高效率為： 1) 1(nkntnkktknE11maxnknLimEn 2022-4-3026流水線的性能指標流水線的性能指標 流水線的最佳段數流水線的最佳段數增加流水線段數增加流水線段數k時，流水線的吞吐率和加速比時，流水線的吞吐率和加速比都能提高。但是每一流水段輸出端必須設置一個都能提高。但是每一流水段輸出端必須設置一個鎖存器，當流水段

25、數增多時，鎖存器的總延遲時鎖存器，當流水段數增多時，鎖存器的總延遲時間也將增加；并且流水線的價格也會增加。為此，間也將增加；并且流水線的價格也會增加。為此，要綜合考慮各方面的因素，根據總價性能價格比要綜合考慮各方面的因素，根據總價性能價格比來選擇流水線最佳段數。來選擇流水線最佳段數。目前，一般處理機中的流水線段數在目前，一般處理機中的流水線段數在3到到12之間，之間，極少有超過極少有超過15段的流水線。一般把段的流水線。一般把8段或超過段或超過8段段的流水線稱為超流水線，采用的流水線稱為超流水線，采用8段以上流水線的段以上流水線的處理機有時也稱為超流水線處理機。處理機有時也稱為超流水線處理機。

26、 2022-4-3027流水線的實現原理流水線的實現原理 DLX指令集結構指令集結構DLX（讀做（讀做Deluxe）是一種）是一種LoadStore型指令型指令集結構。所謂集結構。所謂LoadStore型又稱為寄存器寄型又稱為寄存器寄存器型，是指對通用寄存器型指令集而言，其所存器型，是指對通用寄存器型指令集而言，其所有的有的ALU指令都不包含存儲器操作數。指令都不包含存儲器操作數。DLX強調：簡單的強調：簡單的LoadStore指令集；設計上指令集；設計上重視流水線效率，包括固定長度指令編碼；使編重視流水線效率，包括固定長度指令編碼；使編譯器更容易產生高效的目標代碼。總之，譯器更容易產生高效的

27、目標代碼?？傊?，DLX是是一種適合于學習和研究的系統結構模型。一種適合于學習和研究的系統結構模型。 DLX指令格式指令格式 2022-4-3028流水線的實現原理流水線的實現原理 2022-4-3029流水線的實現原理流水線的實現原理 DLX的一種簡單實現的一種簡單實現每一條每一條DLX指令的實現至多需要指令的實現至多需要5個時鐘周期。這個時鐘周期。這5個時個時鐘周期如下：鐘周期如下：取指令周期（IF）指令譯碼讀寄存器周期（ID） 執行有效地址計算周期（EX） 存儲器訪問分支完成周期（MEM） 寫回周期（WB）不同類型的指令在以上不同類型的指令在以上5個時鐘周期中進行的操作各不相個時鐘周期中進

28、行的操作各不相同。同。在這種實現方案中，分支指令需要在這種實現方案中，分支指令需要4個時鐘周期，而其他個時鐘周期，而其他指令需要指令需要5個時鐘周期。個時鐘周期。 2022-4-3030流水線的實現原理流水線的實現原理 DLX的一種簡單實現的一種簡單實現 2022-4-3031流水線的實現原理流水線的實現原理 簡單的簡單的DLX基本流水線基本流水線 每一個時鐘周期啟動一條新的指令，就可以使每一個時鐘周期啟動一條新的指令，就可以使DLX數據通路成功流水，每一個時鐘周期就是流水線的一數據通路成功流水，每一個時鐘周期就是流水線的一個流水段。每一條指令經過個流水段。每一條指令經過5個時鐘周期執行完成，

29、個時鐘周期執行完成，而在每一個時鐘周期內，硬件將啟動一條新的指令并而在每一個時鐘周期內，硬件將啟動一條新的指令并執行執行5條不同指令的某個部分。條不同指令的某個部分。 2022-4-3032流水線的實現原理流水線的實現原理實際的流水線就這么簡單嗎？實際的流水線就這么簡單嗎？NO！ 必須保證在指令重疊執行時不會存在任何流水線資源沖突問題，必須保證在指令重疊執行時不會存在任何流水線資源沖突問題，即要保證流水線的各段在同一個時鐘周期內不會使用相同的數即要保證流水線的各段在同一個時鐘周期內不會使用相同的數據通路資源。據通路資源。簡化的簡化的DLX流水線數據通路流水線數據通路 下圖從使用流水線資源的角度

30、描述上述流水線的流水過程，這下圖從使用流水線資源的角度描述上述流水線的流水過程，這張圖顯示了不同數據通路的重疊，其中周期張圖顯示了不同數據通路的重疊，其中周期5表示穩定狀態。表示穩定狀態。 在包圍每個流水段的線框中，如果實線在右側，說明是讀操作；在包圍每個流水段的線框中，如果實線在右側，說明是讀操作；如果實線在左側，說明是寫操作；其他部分用虛線。如果實線在左側，說明是寫操作；其他部分用虛線。 主要的功能部件都在不同的時鐘周期內使用，因而多條指令重主要的功能部件都在不同的時鐘周期內使用，因而多條指令重疊執行時引入的沖突疊執行時引入的沖突很少 。 分開的指令存儲器（分開的指令存儲器（IM）和數據存

31、儲器（）和數據存儲器（DM）。）。對存儲器對存儲器性能要求？性能要求？ 在兩個流水線段都使用了寄存器：在兩個流水線段都使用了寄存器：ID段讀，段讀，WB段寫。這兩段寫。這兩個流水段使用的寄存器一般是不同的。個流水段使用的寄存器一般是不同的。如果讀寫相同的寄存如果讀寫相同的寄存器呢？器呢？ 沒有考慮沒有考慮PC的問題，流水要求的問題，流水要求IF段要形成新的段要形成新的PC值。值。如何如何處理分支指令呢？處理分支指令呢？ 2022-4-3033流水線的實現原理流水線的實現原理 簡化的簡化的DLX流水線數據通路流水線數據通路 2022-4-3034流水線的實現原理流水線的實現原理 DLX流水線數據

32、通路流水線數據通路 2022-4-3035流水線的實現原理流水線的實現原理 DLX流水線數據通路流水線數據通路在流水線的各個流水段之間加入了被稱為流水線寄存器（流水線鎖在流水線的各個流水段之間加入了被稱為流水線寄存器（流水線鎖存器）的寄存器堆，并在這些寄存器堆上標明所連接的流水段。存器）的寄存器堆，并在這些寄存器堆上標明所連接的流水段。所有用于在同一條指令的各個時鐘周期之間保存臨時數據的寄所有用于在同一條指令的各個時鐘周期之間保存臨時數據的寄存器，都歸入流水線寄存器這一類中。存器，都歸入流水線寄存器這一類中。流水線寄存器保存著從一個流水段傳送到下一個流水段的所有流水線寄存器保存著從一個流水段傳

33、送到下一個流水段的所有數據和控制信息。數據和控制信息。PC值多路選擇器被移到值多路選擇器被移到IF段，這樣做的目的是保證對段，這樣做的目的是保證對PC值的寫操值的寫操作只出現在一個流水段內，否則當分支轉移成功的時候，流水線中作只出現在一個流水段內，否則當分支轉移成功的時候，流水線中兩條指令都試圖在不同的流水段修改兩條指令都試圖在不同的流水段修改PC值，從而發生寫沖突。值，從而發生寫沖突。每個時刻，每條指令都只在一個流水段上是活動的，因此，任何指每個時刻，每條指令都只在一個流水段上是活動的，因此，任何指令所作的任何動作都發生在一對流水線寄存器之間，具體操作由指令所作的任何動作都發生在一對流水線寄

34、存器之間，具體操作由指令類型決定。令類型決定。 2022-4-3036流水線的相關問題流水線的相關問題 什么是流水線中的什么是流水線中的“相關相關”？在流水線中經常有一些被稱為在流水線中經常有一些被稱為“相關相關”的情況發生，它使得指令序的情況發生，它使得指令序列中下一條指令無法按照設計的時鐘周期執行，這些列中下一條指令無法按照設計的時鐘周期執行，這些“相關相關”可能可能會降低流水線可以獲得的理想性能。會降低流水線可以獲得的理想性能。 流水線中的相關可以分為以下三種類型流水線中的相關可以分為以下三種類型第一種是第一種是結構相關結構相關，是指令在重疊執行的過程中，硬件資源滿足不，是指令在重疊執行

35、的過程中，硬件資源滿足不了指令重疊執行的要求，發生硬件資源沖突而產生的相關。了指令重疊執行的要求，發生硬件資源沖突而產生的相關。第二種是第二種是數據相關數據相關，是指在同時重疊執行的幾條指令中，一條指令，是指在同時重疊執行的幾條指令中，一條指令依賴于前面指令執行結果數據，但是又得不到時發生的相關。依賴于前面指令執行結果數據，但是又得不到時發生的相關。第三種是第三種是控制相關控制相關，它是指流水線中的分支指令或者其他需要改寫，它是指流水線中的分支指令或者其他需要改寫PC的指令造成的相關。的指令造成的相關。 解決流水線中解決流水線中“相關相關”問題的重要性問題的重要性流水線相關問題是流水線執行過程

36、中的主要障礙，會給流水線中指流水線相關問題是流水線執行過程中的主要障礙，會給流水線中指令序列的順利執行帶來許多不利的影響。如果不能較好的處理流水令序列的順利執行帶來許多不利的影響。如果不能較好的處理流水線相關問題，就可能影響流水線的性能，甚至使程序運行產生錯誤線相關問題，就可能影響流水線的性能，甚至使程序運行產生錯誤的結果。的結果。 2022-4-3037結構相關和相應解決方法結構相關和相應解決方法如果因資源沖突而無法使用某種指令組合，那么就稱該流水線產生了如果因資源沖突而無法使用某種指令組合，那么就稱該流水線產生了結構相結構相關關。例如：指令和數據都共享一個存儲器，在某個時鐘周期內，流水線既

37、要。例如：指令和數據都共享一個存儲器，在某個時鐘周期內，流水線既要完成某條指令對數據的存儲器訪問操作，又要完成后續的另一條指令的取指完成某條指令對數據的存儲器訪問操作，又要完成后續的另一條指令的取指令操作，這樣就會發生存儲器訪問沖突問題，產生結構相關。令操作，這樣就會發生存儲器訪問沖突問題，產生結構相關。 2022-4-3038結構相關和相應解決方法結構相關和相應解決方法 消除結構相關的最簡單方法就是引入暫停周期，如下圖所示，這必然消除結構相關的最簡單方法就是引入暫停周期，如下圖所示，這必然要降低流水線的性能。要降低流水線的性能。 2022-4-3039結構相關和相應解決方法結構相關和相應解決

38、方法 解決結構相關的基本方法解決結構相關的基本方法結構相關的起因是資源爭用，那么可以考慮采用資源充結構相關的起因是資源爭用，那么可以考慮采用資源充分重復設置的方法來避免結構相關。分重復設置的方法來避免結構相關。 解決存儲器爭用沖突的辦法解決存儲器爭用沖突的辦法(1)如果指令和數據放在同一個存儲器，可使用雙端口存如果指令和數據放在同一個存儲器，可使用雙端口存儲器，其中一個端口存取數據，另一個端口取指令。儲器，其中一個端口存取數據，另一個端口取指令。(2)設置兩個存儲器，其中一個作為數據存儲器，另一個設置兩個存儲器，其中一個作為數據存儲器，另一個作為指令存儲器。作為指令存儲器。上述兩種方案中，取指

39、令和訪問數據可以并行進行，不上述兩種方案中，取指令和訪問數據可以并行進行，不會發生結構相關。會發生結構相關。 2022-4-3040數據相關和相應解決方法數據相關和相應解決方法 流水線技術可以通過指令的流水線技術可以通過指令的重疊執行重疊執行來改變指令的來改變指令的相對執行時間相對執行時間，這，這就可能導致流水線中的指令序列就可能導致流水線中的指令序列讀寫操作數的順序讀寫操作數的順序發生改變，而不同發生改變，而不同于非流水線時的指令序列讀寫操作數的順序。示例如下：于非流水線時的指令序列讀寫操作數的順序。示例如下： 2022-4-3041數據相關和相應解決方法數據相關和相應解決方法定向定向(旁路

40、旁路)技術技術解決數據相關，主要思想是：在某條指令產生一個計算結果之解決數據相關，主要思想是：在某條指令產生一個計算結果之前，其他指令并不真正需要使用這個計算結果，如果能夠從這個計算結果產前，其他指令并不真正需要使用這個計算結果，如果能夠從這個計算結果產生的地方直接將它送到后續指令需要使用它的地方，那么就可以避免暫停生的地方直接將它送到后續指令需要使用它的地方，那么就可以避免暫停 2022-4-3042數據相關和相應解決方法數據相關和相應解決方法 定向技術對定向技術對DLX相應數據通路的修改相應數據通路的修改 2022-4-3043數據相關和相應解決方法數據相關和相應解決方法 按照指令讀寫寄存

41、器順序對數據相關分類按照指令讀寫寄存器順序對數據相關分類對于兩條指令對于兩條指令i和和j，假設指令，假設指令i在在j之前進入流水線，下面之前進入流水線，下面討論幾種不同的數據相關。討論幾種不同的數據相關。 寫后讀相關（寫后讀相關（RAW：Read After Write）指令指令j的執行需要使用指令的執行需要使用指令i的計算結果，但是當它們在流的計算結果，但是當它們在流水線中重疊執行時，指令水線中重疊執行時，指令j可能在指令可能在指令i將其計算結果寫入將其計算結果寫入之前就先行對保存該計算結果的寄存器進行了讀操作，之前就先行對保存該計算結果的寄存器進行了讀操作，這樣指令這樣指令j讀出的寄存器值

42、就是錯誤的。讀出的寄存器值就是錯誤的。這是最常見的一種數據相關，采用定向技術消除的數據這是最常見的一種數據相關，采用定向技術消除的數據相關就屬于這種類型。相關就屬于這種類型。 2022-4-3044數據相關和相應解決方法數據相關和相應解決方法寫后寫相關（寫后寫相關（WAW：Write After Write） 指令指令j和指令和指令i的目的操作數相同，但是當它們在流水線中重疊執行時，的目的操作數相同，但是當它們在流水線中重疊執行時，指令指令j可能在指令可能在指令i將其計算結果寫入之前就先行對保存該計算結果的將其計算結果寫入之前就先行對保存該計算結果的寄存器進行了寫操作，這樣就導致了寄存器寫入順

43、序的錯誤，此時，寄存器進行了寫操作，這樣就導致了寄存器寫入順序的錯誤，此時，目的寄存器的內容是指令目的寄存器的內容是指令i寫入的值，而不是指令寫入的值，而不是指令j寫入的值。寫入的值。DLX中不會發生中不會發生WAW相關相關 如果在流水線中不只一個流水段可以進行寫操作，或者當流水線暫如果在流水線中不只一個流水段可以進行寫操作，或者當流水線暫停某條指令的執行時，允許該指令之后的其他指令繼續執行，就可停某條指令的執行時，允許該指令之后的其他指令繼續執行，就可能發生這種數據相關。但是能發生這種數據相關。但是DLX流水線中的指令是不會發生這種數流水線中的指令是不會發生這種數據相關的，因為據相關的，因為

44、DLX流水中只有流水中只有WB段才會寫寄存器。段才會寫寄存器。 如果對如果對DLX流水線進行改變，將流水線進行改變，將ALU運算結果的寫回操作移到運算結果的寫回操作移到MEM段進行，因為這時計算結果已經有效，同時再假定訪問數據存段進行，因為這時計算結果已經有效，同時再假定訪問數據存儲器需要兩個流水段，那么儲器需要兩個流水段，那么DLX流水線中執行的指令就可能發生流水線中執行的指令就可能發生WAW相關。相關。LW R1，0（R2）IFIDEXMEM1MEM2WBADD R1，R2，R3IFIDEXWB 2022-4-3045數據相關和相應解決方法數據相關和相應解決方法讀后寫相關（讀后寫相關（WA

45、R：Write After Read） 指令指令j可能在指令可能在指令i讀取某個源寄存器的內容之前就對該寄存器進讀取某個源寄存器的內容之前就對該寄存器進行了寫操作，結果就是導致了指令行了寫操作，結果就是導致了指令i后來讀取的值是錯誤的。后來讀取的值是錯誤的。DLX中不會發生中不會發生WAR相關相關 因為因為DLX流水線在流水線在ID段完成所有的讀操作，而在段完成所有的讀操作，而在WB段完成所有段完成所有的寫操作。的寫操作。 但是在上面修改后的但是在上面修改后的DLX流水線中，是有可能發生這種數據相流水線中，是有可能發生這種數據相關的，觀察下面的兩條指令的執行情況，如果關的，觀察下面的兩條指令的

46、執行情況，如果SW指令在指令在MEM2的后半部分讀取寄存器的后半部分讀取寄存器R2的值，的值，ADD指令在指令在WB段的前半部分段的前半部分將計算結果寫回到寄存器將計算結果寫回到寄存器R2，那么，那么SW讀取的寄存器值就是錯誤讀取的寄存器值就是錯誤的，這個值是的，這個值是ADD指令的計算結果，并不是預期的結果。指令的計算結果，并不是預期的結果。SW 0（R5），），R2IFIDEXMEM1MEM2WBADD R2，R3，R4IFIDEXWB 2022-4-3046數據相關和相應解決方法數據相關和相應解決方法 必須進行暫停的數據相關必須進行暫停的數據相關 2022-4-3047數據相關和相應解決

47、方法數據相關和相應解決方法 為了保證流水線能夠正確執行上述的指令序列，需要加入一種稱為為了保證流水線能夠正確執行上述的指令序列，需要加入一種稱為“流水線互鎖流水線互鎖” 的新功能部件。通常，流水線互鎖檢測到上述的數據的新功能部件。通常，流水線互鎖檢測到上述的數據相關后就暫停流水線，直到能夠通過定向技術解決數據相關為止。相關后就暫停流水線，直到能夠通過定向技術解決數據相關為止。 2022-4-3048數據相關和相應解決方法數據相關和相應解決方法編譯器調度方法處理數據相關編譯器調度方法處理數據相關 例如對于最常見的例如對于最常見的ABC這樣的操作形式，采用比較典型的代碼生成這樣的操作形式，采用比較

48、典型的代碼生成方法可以得到如下的指令序列：方法可以得到如下的指令序列：LWR1, BLWR2, CADDR3, R1, R2SWA, R3 這個指令序列的流水線時空圖這個指令序列的流水線時空圖 2022-4-3049數據相關和相應解決方法數據相關和相應解決方法 編譯器調度方法處理數據相關編譯器調度方法處理數據相關編譯器是如何通過指令調度來消除流水線暫停的呢？例如有下面連編譯器是如何通過指令調度來消除流水線暫停的呢？例如有下面連續的兩個操作：續的兩個操作：abc；def；指令調度前后代碼對比（左：調度前，右：調度后）指令調度前后代碼對比（左：調度前，右：調度后）LW LW RbRb，b bLW

49、LW RcRc，c cADD RaADD Ra，RbRb，RcRcSW aSW a，RaRaLW ReLW Re，e eLW LW RfRf，f fSUB RdSUB Rd，ReRe，RfRfSW dSW d，RdRdLW LW RbRb，b bLW LW RcRc，c cLW ReLW Re，e e ；交換指令，消除；交換指令，消除ADDADD指令暫停指令暫停ADD RaADD Ra，RbRb，RcRcLW LW RfRf，f fSW aSW a，Ra Ra ；Store/LoadStore/Load交換，消除交換，消除SUBSUB指令暫停指令暫停SUB RdSUB Rd，ReRe，RfRf

50、SW dSW d，RdRd 2022-4-3050數據相關和相應解決方法數據相關和相應解決方法 數據相關的動態調度數據相關的動態調度這種方法是由硬件動態調整指令這種方法是由硬件動態調整指令執行順序執行順序以減少暫停的以減少暫停的影響，能夠簡化編譯器設計。影響，能夠簡化編譯器設計。動態調度并不能真正消除數據相關，但它能在出現數據動態調度并不能真正消除數據相關，但它能在出現數據相關時盡量避免出現處理器暫停。而靜態調度方法則是相關時盡量避免出現處理器暫停。而靜態調度方法則是盡量通過分離有相關問題的指令使它們不會導致沖突，盡量通過分離有相關問題的指令使它們不會導致沖突，從而減少暫停的影響。從而減少暫停

51、的影響。 動態調度的主要思想：動態調度的主要思想：指令順序發射指令順序發射亂序執行亂序執行指令亂序流出指令亂序流出動態調度的問題：異常處理的不精確性。在采用動態調動態調度的問題：異常處理的不精確性。在采用動態調度方法的處理機中，在某條指令產生異常情況時，有可度方法的處理機中，在某條指令產生異常情況時，有可能出現其后面的指令已經執行完成的情況，這樣異常處能出現其后面的指令已經執行完成的情況，這樣異常處理是不精確的。理是不精確的。 2022-4-3051控制相關和相應解決方法控制相關和相應解決方法 流水線的流水線的控制相關控制相關是因為程序執行是因為程序執行轉移類指令轉移類指令而引起的相關。轉移類

52、而引起的相關。轉移類指令如無條件轉移、條件轉移、子程序調用、中斷等，它們屬于分支指令如無條件轉移、條件轉移、子程序調用、中斷等，它們屬于分支指令，執行中可能改變程序的方向，從而造成流水線斷流。指令，執行中可能改變程序的方向，從而造成流水線斷流。 數據相關影響到的僅僅是本條指令附近少數幾條指令，所以稱為數據相關影響到的僅僅是本條指令附近少數幾條指令，所以稱為局部局部相關相關。而控制相關影響的范圍要大得多，它會引起程序執行方向的改。而控制相關影響的范圍要大得多，它會引起程序執行方向的改變，使流水線損失更多的性能，所以稱為變，使流水線損失更多的性能，所以稱為全局相關全局相關。 控制相關會使流水線的連

53、續流動受到破壞。當執行條件轉移指令時，控制相關會使流水線的連續流動受到破壞。當執行條件轉移指令時，有兩種可能結果：有兩種可能結果：如發生轉移，將程序計數器如發生轉移，將程序計數器PC的內容改變成轉移目標地址；的內容改變成轉移目標地址；如不發生轉移，只將如不發生轉移，只將PC加上一個增量，指向下一條指令的地址。加上一個增量，指向下一條指令的地址。 2022-4-3052控制相關和相應解決方法控制相關和相應解決方法 控制相關簡單解決方法控制相關簡單解決方法一旦發現分支指令就暫停流水線，即暫停一旦發現分支指令就暫停流水線，即暫停該指令之后的所有指令，直到分支指令達該指令之后的所有指令，直到分支指令達

54、到到MEM段確定了新的段確定了新的PC值為止。值為止。在發現它是分支指令之前是不愿意暫停流在發現它是分支指令之前是不愿意暫停流水線的，因此暫停在水線的，因此暫停在ID段之后才會發生，段之后才會發生，下圖所示的流水線時空圖就描述了這種出下圖所示的流水線時空圖就描述了這種出來方法。來方法。 2022-4-3053控制相關和相應解決方法控制相關和相應解決方法 簡單方法處理時空圖簡單方法處理時空圖 減少流水線處理分支指令時暫停周期數的兩個步驟減少流水線處理分支指令時暫停周期數的兩個步驟 在流水線中盡早判斷出分支轉移是否成功；在流水線中盡早判斷出分支轉移是否成功； 盡早計算出分支成功轉移時的盡早計算出分

55、支成功轉移時的PC直（如分支的目標直（如分支的目標地址）。地址）。 2022-4-3054控制相關和相應解決方法控制相關和相應解決方法 2022-4-3055控制相關和相應解決方法控制相關和相應解決方法 減少流水線分支開銷的方法減少流水線分支開銷的方法凍結或者排空流水線的方法 預測分支轉移失敗的方法 譯碼到一條分支指令指令時，就像分支指令就是一條譯碼到一條分支指令指令時，就像分支指令就是一條普通的指令那樣，流水線繼續取后續的指令，并且允普通的指令那樣，流水線繼續取后續的指令，并且允許分支指令后續指令在流水線中正常流動。（兩種情許分支指令后續指令在流水線中正常流動。（兩種情況下的時空圖見下頁）況

56、下的時空圖見下頁）預測分支轉移成功的方法 一旦完成分支指令的譯碼并且計算出了分支的目標地一旦完成分支指令的譯碼并且計算出了分支的目標地址，就假設分支轉移成功，并且開始在分支目標地址址，就假設分支轉移成功，并且開始在分支目標地址處取指令執行。處取指令執行。分支延遲（延遲轉移）的方法 2022-4-3056控制相關和相應解決方法控制相關和相應解決方法 預測分支轉移失敗的方法預測分支轉移失敗的方法 2022-4-3057控制相關和相應解決方法控制相關和相應解決方法分支延遲的方法分支延遲的方法 延遲長度為延遲長度為n的分支指令的執行順序如下：的分支指令的執行順序如下：分支指令分支指令后續指令后續指令1

57、后續指令后續指令2后續指令后續指令n分支目標地址指令（分支目標地址指令（如果分支轉移成功如果分支轉移成功） 后續指令放在分支延遲槽中，不管分支轉移是否成功，這些指令后續指令放在分支延遲槽中，不管分支轉移是否成功，這些指令都要被流水執行。延遲槽一般只放置一條指令。都要被流水執行。延遲槽一般只放置一條指令。分支延遲槽分支延遲槽 2022-4-3058控制相關和相應解決方法控制相關和相應解決方法 分支延遲的方法分支延遲的方法 無論分支轉移成功與否，延遲槽內的指令都要執行。如果分支轉無論分支轉移成功與否，延遲槽內的指令都要執行。如果分支轉移失敗，只需要按取來的指令執行；否則，按照分支目標地址的移失敗，

58、只需要按取來的指令執行；否則，按照分支目標地址的指令執行。指令執行。 2022-4-3059控制相關和相應解決方法控制相關和相應解決方法分支延遲的方法分支延遲的方法 選擇放到分支延遲槽中的指令必須按照一定的原則經過編譯器的選擇放到分支延遲槽中的指令必須按照一定的原則經過編譯器的調度。對分支延遲的三種調度方法：調度。對分支延遲的三種調度方法： 2022-4-3060控制相關和相應解決方法控制相關和相應解決方法分支延遲的方法分支延遲的方法 三種調度方法的所受的限制，以及他們各自的應用場合。三種調度方法的所受的限制，以及他們各自的應用場合。 2022-4-3061控制相關和相應解決方法控制相關和相應

59、解決方法 控制相關的動態調度控制相關的動態調度分支預測緩沖技術（Branch Prediction Buffer）緩沖區的每一項內容被用來預測分支轉移是否成功，并且根據緩沖區的每一項內容被用來預測分支轉移是否成功，并且根據實際的分支情況對內容進行修改。這種方法是基于如下的考慮：實際的分支情況對內容進行修改。這種方法是基于如下的考慮：如果本次分支轉移成功了，那么預測下一次分支轉移也成功，如果本次分支轉移成功了，那么預測下一次分支轉移也成功，例如一個循環體就是這種情況。例如一個循環體就是這種情況。 分支目標緩沖技術（Branch Target Buffer）將分支轉移成功的分支指令的地址和它的分支

60、目標地址都放到將分支轉移成功的分支指令的地址和它的分支目標地址都放到一個緩沖區中保存起來，緩沖區以分支指令的地址作為標志；一個緩沖區中保存起來，緩沖區以分支指令的地址作為標志；在取指令階段，所有的指令地址都與保存的標志作比較，如果在取指令階段，所有的指令地址都與保存的標志作比較，如果相同，就認為本條指令是分支指令，而且認為它分支轉移成功，相同，就認為本條指令是分支指令，而且認為它分支轉移成功，同時它的分支目標（下一條指令）地址就是保存在緩沖區中的同時它的分支目標（下一條指令）地址就是保存在緩沖區中的分支目標地址。分支目標地址。 2022-4-3062指令級并行技術簡介指令級并行技術簡介 當指令