第三章流水線技術

第三章流水線技術第一頁，共一百三十四頁，編輯于2023年，星期四3.1 流水線的基本概念3.2 流水線的性能指標3.3 流水線的相關與沖突3.4 流水線的實現(xiàn)3.5小結(jié)第二頁，共一百三十四頁，編輯于2023年，星期四工業(yè)生產(chǎn)流水線

下面通過一個例子來說明流水線的好處:兩種方案兩種方案的工作過程對比流水線生產(chǎn)過程的抽象描述這種流水工作方式的主要特點3.1流水線的基本概念3.1.1什么是流水線第三頁，共一百三十四頁，編輯于2023年，星期四3.1流水線的基本概念流水線技術把一個重復的過程分解為若干個子過程，每個子過程由專門的功能部件來實現(xiàn)。把多個處理過程在時間上錯開，依次通過各功能段，這樣，每個子過程就可以與其他的子過程并行進行。流水線中的每個子過程及其功能部件稱為流水線的級或段，段與段相互連接形成流水線。流水線的段數(shù)稱為流水線的深度。第四頁，共一百三十四頁，編輯于2023年，星期四3.1流水線的基本概念指令流水線把指令的解釋過程分解為分析和執(zhí)行兩個子過程，并讓這兩個子過程分別用獨立的分析部件和執(zhí)行部件來實現(xiàn)。

理想情況：速度提高一倍4段指令流水線第五頁，共一百三十四頁，編輯于2023年，星期四3.1流水線的基本概念浮點加法流水線把流水線技術應用于運算的執(zhí)行過程，就形成了運算操作流水線，也稱為部件級流水線。把浮點加法的全過程分解為求階差、對階、尾數(shù)相加、規(guī)格化4個子過程。理想情況：速度提高3倍第六頁，共一百三十四頁，編輯于2023年，星期四時空圖時空圖從時間和空間兩個方面描述了流水線的工作過程。時空圖中，橫坐標代表時間，縱坐標代表流水線的各個段。4段指令流水線的時空圖第七頁，共一百三十四頁，編輯于2023年，星期四3.1流水線的基本概念流水技術的特點流水線把一個處理過程分解為若干個子過程（段），每個子過程由一個專門的功能部件來實現(xiàn)。流水線中各段的時間應盡可能相等，否則將引起流水線堵塞、斷流。時間長的段將成為流水線的瓶頸。流水線每一個功能部件的后面都要有一個緩沖寄存器（鎖存器），稱為流水寄存器。作用：在相鄰的兩段之間傳送數(shù)據(jù)，以保證提供后面要用到的數(shù)據(jù)，并把各段的處理工作相互隔離。第八頁，共一百三十四頁，編輯于2023年，星期四3.1流水線的基本概念流水技術適合于大量重復的時序過程，只有在輸入端不斷地提供任務，才能充分發(fā)揮流水線的效率。流水線需要有通過時間和排空時間。通過時間：第一個任務從進入流水線到流出結(jié)果所需的時間。排空時間：最后一個任務從進入流水線到流出結(jié)果所需的時間。第九頁，共一百三十四頁，編輯于2023年，星期四3.1流水線的基本概念從不同的角度和觀點，把流水線分成多種不同的種類。單功能流水線與多功能流水線

（按照流水線所完成的功能來分類）單功能流水線：只能完成一種固定功能的流水線。多功能流水線：流水線的各段可以進行不同的連接，以實現(xiàn)不同的功能。例：ASC的多功能流水線3.1.2流水線的分類第十頁，共一百三十四頁，編輯于2023年，星期四第十一頁，共一百三十四頁，編輯于2023年，星期四3.1流水線的基本概念靜態(tài)流水線與動態(tài)流水線（按照同一時間內(nèi)各段之間的連接方式對多功能流水線做進一步的分類）靜態(tài)流水線：在同一時間內(nèi)，多功能流水線中的各段只能按同一種功能的連接方式工作。對于靜態(tài)流水線來說，只有當輸入的是一串相同的運算任務時，流水的效率才能得到充分的發(fā)揮。例如：ASC的8段流水線第十二頁，共一百三十四頁，編輯于2023年，星期四3.1流水線的基本概念動態(tài)流水線：在同一時間內(nèi)，多功能流水線中的各段可以按照不同的方式連接，同時執(zhí)行多種功能。優(yōu)點靈活，能夠提高流水線各段的使用率，從而提高處理速度。缺點控制復雜。靜、動態(tài)流水線時空圖的對比第十三頁，共一百三十四頁，編輯于2023年，星期四第十四頁，共一百三十四頁，編輯于2023年，星期四3.1流水線的基本概念部件級、處理機級及處理機間流水線（按照流水的級別來進行分類）部件級流水線（運算操作流水線）：把處理機的算術邏輯運算部件分段，使得各種類型的運算操作能夠按流水方式進行。處理機級流水線（指令流水線）：把指令的解釋執(zhí)行過程按照流水方式處理。把一條指令的執(zhí)行過程分解為若干個子過程，每個子過程在獨立的功能部件中執(zhí)行。例如：前面的4段指令流水線第十五頁，共一百三十四頁，編輯于2023年，星期四3.1流水線的基本概念處理機間流水線（宏流水線）：它是由兩個或者兩個以上的處理機串行連接起來，對同一數(shù)據(jù)流進行處理，每個處理機完成整個任務中的一部分。第十六頁，共一百三十四頁，編輯于2023年，星期四3.1流水線的基本概念線性流水線與非線性流水線（按照流水線中是否有反饋回路來進行分類）線性流水線：流水線的各段串行連接，沒有反饋回路。數(shù)據(jù)通過流水線中的各段時，每一個段最多只流過一次。非線性流水線：流水線中除了有串行的連接外，還有反饋回路。非線性流水線的調(diào)度問題確定什么時候向流水線引進新的任務，才能使該任務不會與先前進入流水線的任務發(fā)生沖突——爭用流水段。

第十七頁，共一百三十四頁，編輯于2023年，星期四3.1流水線的基本概念第十八頁，共一百三十四頁，編輯于2023年，星期四3.1流水線的基本概念順序流水線與亂序流水線（根據(jù)任務流入和流出的順序是否相同來進行分類）順序流水線：流水線輸出端任務流出的順序與輸入端任務流入的順序完全相同。每一個任務在流水線的各段中是一個跟著一個順序流動的。亂序流水線：流水線輸出端任務流出的順序與輸入端任務流入的順序可以不同，允許后進入流水線的任務先完成（從輸出端流出）。也稱為無序流水線、錯序流水線、異步流水線第十九頁，共一百三十四頁，編輯于2023年，星期四3.1流水線的基本概念標量處理機與向量流水處理機把指令執(zhí)行部件中采用了流水線的處理機稱為流水線處理機。標量處理機：處理機不具有向量數(shù)據(jù)表示和向量指令，僅對標量數(shù)據(jù)進行流水處理。向量流水處理機：具有向量數(shù)據(jù)表示和向量指令的處理機。向量數(shù)據(jù)表示和流水技術的結(jié)合。第二十頁，共一百三十四頁，編輯于2023年，星期四

吞吐率：在單位時間內(nèi)流水線所完成的任務數(shù)量或輸出結(jié)果的數(shù)量。3.2流水線的性能指標3.2.1吞吐率n：任務數(shù)Tk：處理完成n個任務所用的時間第二十一頁，共一百三十四頁，編輯于2023年，星期四3.2流水線的性能指標各段時間均相等的流水線各段時間均相等的流水線時空圖第二十二頁，共一百三十四頁，編輯于2023年，星期四3.2流水線的性能指標流水線完成n個連續(xù)任務所需要的總時間為（假設一條k段線性流水線）

Tk＝kΔt＋(n-1)Δt＝(k＋n-1)Δt

流水線的實際吞吐率最大吞吐率第二十三頁，共一百三十四頁，編輯于2023年，星期四3.2流水線的性能指標最大吞吐率與實際吞吐率的關系流水線的實際吞吐率小于最大吞吐率，它除了與每個段的時間有關外，還與流水線的段數(shù)k以及輸入到流水線中的任務數(shù)n等有關。只有當n>>k時，才有TP≈TPmax。

第二十四頁，共一百三十四頁，編輯于2023年，星期四3.2流水線的性能指標各段時間不完全相等的流水線各段時間不等的流水線及其時空圖舉例一條4段的流水線S1，S3，S4各段的時間：ΔtS2的時間：3Δt

（瓶頸段）流水線中這種時間最長的段稱為流水線的瓶頸段。

第二十五頁，共一百三十四頁，編輯于2023年，星期四3.2流水線的性能指標第二十六頁，共一百三十四頁，編輯于2023年，星期四3.2流水線的性能指標各段時間不等的流水線的實際吞吐率：（Δti為第i段的時間，共有k個段）流水線的最大吞吐率為第二十七頁，共一百三十四頁，編輯于2023年，星期四3.2流水線的性能指標

例如：一條4段的流水線中，S1，S2，S4各段的時間都是Δt，唯有S3的時間是3Δt。最大吞吐率為第二十八頁，共一百三十四頁，編輯于2023年，星期四3.2流水線的性能指標解決流水線瓶頸問題的常用方法

3-2-32.avi細分瓶頸段

例如：對前面的4段流水線把瓶頸段S3細分為3個子流水線段：S3a，S3b，S3c改進后的流水線的吞吐率：第二十九頁，共一百三十四頁，編輯于2023年，星期四3.2流水線的性能指標重復設置瓶頸段舉例：時空圖缺點：控制邏輯比較復雜，所需的硬件增加了。例如：對前面的4段流水線重復設置瓶頸段S3：S3a，S3b，S3c第三十頁，共一百三十四頁，編輯于2023年，星期四3.2流水線的性能指標重復設置瓶頸段后的時空圖第三十一頁，共一百三十四頁，編輯于2023年，星期四3.2流水線的性能指標加速比：完成同樣一批任務，不使用流水線所用的時間與使用流水線所用的時間之比。假設：不使用流水線（即順序執(zhí)行）所用的間為Ts，使用流水線后所用的時間為Tk，則該流水線的加速比為3.2.2加速比第三十二頁，共一百三十四頁，編輯于2023年，星期四3.2流水線的性能指標流水線各段時間相等（都是△t）一條k段流水線完成n個連續(xù)任務所需要的時間為

Tk=(k＋n-1)Δt順序執(zhí)行n個任務所需要的時間：

Ts=nk△t流水線的實際加速比為第三十三頁，共一百三十四頁，編輯于2023年，星期四3.2流水線的性能指標最大加速比當n>>k時，S

≈

k

思考：流水線的段數(shù)愈多愈好？

第三十四頁，共一百三十四頁，編輯于2023年，星期四3.2流水線的性能指標流水線的各段時間不完全相等時一條k段流水線完成n個連續(xù)任務的實際加速比為第三十五頁，共一百三十四頁，編輯于2023年，星期四3.2流水線的性能指標效率：流水線中的設備實際使用時間與整個運行時間的比值，即流水線設備的利用率。

由于流水線有通過時間和排空時間，所以在連續(xù)完成n個任務的時間內(nèi)，各段并不是滿負荷地工作。各段時間相等各段的效率ei相同(解釋)3.2.3效率第三十六頁，共一百三十四頁，編輯于2023年，星期四3.2流水線的性能指標整條流水線的效率為可以寫成

最高效率為當n>>k時，E≈1。第三十七頁，共一百三十四頁，編輯于2023年，星期四3.2流水線的性能指標當流水線各段時間相等時，流水線的效率與吞吐率成正比。

E=TP△t

流水線的效率是流水線的實際加速比S與它的最大加速比k的比值。當E=1時，S=k，實際加速比達到最大。第三十八頁，共一百三十四頁，編輯于2023年，星期四3.2流水線的性能指標從時空圖上看，效率就是n個任務占用的時空面積和

k個段總的時空面積之比。當各段時間不相等時第三十九頁，共一百三十四頁，編輯于2023年，星期四3.2流水線的性能指標例3.1設在下圖所示的靜態(tài)流水線上計算：

流水線的輸出可以直接返回輸入端或暫存于相應的流水寄存器中，試計算其吞吐率、加速比和效率。3.2.4流水線的性能分析舉例(每段的時間都為△t)第四十頁，共一百三十四頁，編輯于2023年，星期四3.2流水線的性能指標解：（1）選擇適合于流水線工作的算法先計算A1+B1、A2+B2、A3+B3和A4+B4；再計算(A1+B1)×(A2+B2)和(A3+B3)×(A4+B4)；然后求總的乘積結(jié)果。（2）畫出時空圖第四十一頁，共一百三十四頁，編輯于2023年，星期四3.2流水線的性能指標第四十二頁，共一百三十四頁，編輯于2023年，星期四3.2流水線的性能指標在18個△t時間中，給出了7個結(jié)果。吞吐率為：

不用流水線，由于一次求和需6△t，一次求積需4△t，則產(chǎn)生上述7個結(jié)果共需（4×6+3×4）△t=36△t

加速比為（3）計算性能第四十三頁，共一百三十四頁，編輯于2023年，星期四3.2流水線的性能指標

流水線的效率可以看出，在求解此問題時，該流水線的效率不高。

第四十四頁，共一百三十四頁，編輯于2023年，星期四3.2流水線的性能指標主要原因多功能流水線在做某一種運算時，總有一些段是空閑的。靜態(tài)流水線在進行功能切換時，要等前一種運算全部流出流水線后才能進行后面的運算。運算之間存在關聯(lián)，后面有些運算要用到前面運算的結(jié)果。流水線的工作過程有建立與排空部分。第四十五頁，共一百三十四頁，編輯于2023年，星期四3.2流水線的性能指標例3.2有一條動態(tài)多功能流水線由5段組成，加法用1、3、4、5段，乘法用1、2、5段，第2段的時間為2△t，其余各段時間均為△t，而且流水線的輸出可以直接返回輸入端或暫存于相應的流水寄存器中。若在該流水線上計算:

試計算其吞吐率、加速比和效率。第四十六頁，共一百三十四頁，編輯于2023年，星期四3.2流水線的性能指標解:(1)選擇適合于流水線工作的算法應先計算A1×B1、A2×B2、A3×B3和A4×B4；再計算(A1×B1)＋(A2×B2)(A3×B3)＋(A4×B4)；然后求總的累加結(jié)果。(2)畫出時空圖(3)計算性能第四十七頁，共一百三十四頁，編輯于2023年，星期四3.2流水線的性能指標第四十八頁，共一百三十四頁，編輯于2023年，星期四3.2流水線的性能指標

下面我們再看一個例子：

例在靜態(tài)流水線上計算:

求：吞吐率，加速比，效率。解：(1)確定適合于流水處理的計算過程(2)畫時空圖(3)性能計算吞吐率TP＝7／(20△t)

加速比S＝(34△t)／(20△t)＝1.7效率E＝(4×4＋3×6)／(8×20)＝0.21第四十九頁，共一百三十四頁，編輯于2023年，星期四3.2流水線的性能指標第五十頁，共一百三十四頁，編輯于2023年，星期四3.2流水線的性能指標瓶頸問題理想情況下，流水線在工作時，其中的任務是同步地每一個時鐘周期往前流動一段。當流水線各段不均勻時，機器的時鐘周期取決于瓶頸段的延遲時間。在設計流水線時，要盡可能使各段時間相等。流水線的額外開銷流水寄存器延遲時鐘偏移開銷3.2.5流水線設計中的若干問題第五十一頁，共一百三十四頁，編輯于2023年，星期四3.2流水線的性能指標流水寄存器需要建立時間和傳輸延遲建立時間：在觸發(fā)寫操作的時鐘信號到達之前，寄存器輸入必須保持穩(wěn)定的時間。傳輸延遲：時鐘信號到達后到寄存器輸出可用的時間。時鐘偏移開銷流水線中，時鐘到達各流水寄存器的最大差值時間。（時鐘到達各流水寄存器的時間不是完全相同）第五十二頁，共一百三十四頁，編輯于2023年，星期四3.2流水線的性能指標幾個問題流水線并不能減少（而且一般是增加）單條指令的執(zhí)行時間，但卻能提高吞吐率。增加流水線的深度（段數(shù)）可以提高流水線的性能。流水線的深度受限于流水線的額外開銷。當時鐘周期小到與額外開銷相同時，流水已沒意義。因為這時在每一個時鐘周期中已沒有時間來做有用的工作。沖突問題流水線設計中要解決的重要問題之一。第五十三頁，共一百三十四頁，編輯于2023年，星期四介紹一個經(jīng)典的5段RISC流水線

首先討論在非流水情況下是如何實現(xiàn)的一條指令的執(zhí)行過程分為以下5個周期：取指令周期（IF）IR←Mem[PC]。PC值加4。（假設每條指令占4個字節(jié)）

3.3流水線的相關與沖突3.3.1一個經(jīng)典的5段流水線第五十四頁，共一百三十四頁，編輯于2023年，星期四3.3流水線的相關與沖突指令譯碼/讀寄存器周期（ID）譯碼。用IR中的寄存器編號去訪問通用寄存器組，讀出所需的操作數(shù)。執(zhí)行/有效地址計算周期（EX）不同指令所進行的操作不同：存儲器訪問指令：ALU把所指定的寄存器的內(nèi)容與偏移量相加，形成用于訪存的有效地址。寄存器－寄存器ALU指令：ALU按照操作碼指定的操作對從通用寄存器組中讀取的數(shù)據(jù)進行運算。第五十五頁，共一百三十四頁，編輯于2023年，星期四3.3流水線的相關與沖突寄存器－立即數(shù)ALU指令：ALU按照操作碼指定的操作對從通用寄存器組中讀取的第一操作數(shù)和立即數(shù)進行運算。分支指令：ALU把偏移量與PC值相加，形成轉(zhuǎn)移目標的地址。同時，對在前一個周期讀出的操作數(shù)進行判斷，確定分支是否成功。存儲器訪問／分支完成周期（MEM）該周期處理的指令只有l(wèi)oad、store和分支指令。其他類型的指令在此周期不做任何操作。第五十六頁，共一百三十四頁，編輯于2023年，星期四3.3流水線的相關與沖突load和store指令load指令：用上一個周期計算出的有效地址從存儲器中讀出相應的數(shù)據(jù)。store指令：把指定的數(shù)據(jù)寫入這個有效地址所指出的存儲器單元。分支指令分支“成功”，就把轉(zhuǎn)移目標地址送入PC。分支指令執(zhí)行完成。第五十七頁，共一百三十四頁，編輯于2023年，星期四3.3流水線的相關與沖突寫回周期（WB）

ALU運算指令和load指令在這個周期把結(jié)果數(shù)據(jù)寫入通用寄存器組。

ALU運算指令：結(jié)果數(shù)據(jù)來自ALU。

load指令：結(jié)果數(shù)據(jù)來自存儲器系統(tǒng)。在這個實現(xiàn)方案中：分支指令需要4個時鐘周期（如果把分支指令的執(zhí)行提前到ID周期，則只需要2個周期）。store指令需要4個周期。其他指令需要5個周期才能完成。第五十八頁，共一百三十四頁，編輯于2023年，星期四將上述實現(xiàn)方案修改為流水線實現(xiàn)一個經(jīng)典的5段流水線

每一個周期作為一個流水段。在各段之間加上鎖存器（流水寄存器）。3.3流水線的相關與沖突第五十九頁，共一百三十四頁，編輯于2023年，星期四3.3流水線的相關與沖突5段流水線的兩種描述方式第一種描述（類似于時空圖）第六十頁，共一百三十四頁，編輯于2023年，星期四第二種描述（按時間錯開的數(shù)據(jù)通路序列）3.3流水線的相關與沖突第六十一頁，共一百三十四頁，編輯于2023年，星期四

采用流水線方式實現(xiàn)時，應解決以下幾個問題：要保證不會在同一時鐘周期要求同一個功能段做兩件不同的工作。例如，不能要求ALU同時做有效地址計算和算術運算。避免IF段的訪存（取指令）與MEM段的訪存（讀/寫數(shù)據(jù)）發(fā)生沖突?？梢圆捎梅蛛x的指令存儲器和數(shù)據(jù)存儲器；一般采用分離的指令Cache和數(shù)據(jù)Cache。避免ID段和WB段都要訪問同一寄存器文件。ID段：讀WB段：寫3.3流水線的相關與沖突第六十二頁，共一百三十四頁，編輯于2023年，星期四3.3流水線的相關與沖突如何解決對同一寄存器的訪問沖突？把寫操作安排在時鐘周期的前半拍完成，把讀操作安排在后半拍完成?？紤]PC的問題流水線為了能夠每個時鐘周期啟動一條新的指令，就必須在每個時鐘周期進行PC值的加4操作，并保留新的PC值。這種操作必須在IF段完成，以便為取下一條指令做好準備。

（需設置一個專門的加法器）但分支指令也可能改變PC的值，而且是在MEM段進行，這會導致沖突。請考慮一下，如何處理分支指令？第六十三頁，共一百三十四頁，編輯于2023年，星期四3.3流水線的相關與沖突相關：兩條指令之間存在某種依賴關系。如果兩條指令相關，則它們就有可能不能在流水線中重疊執(zhí)行或者只能部分重疊執(zhí)行。相關有3種類型數(shù)據(jù)相關（也稱真數(shù)據(jù)相關）名相關控制相關3.3.2相關與流水線沖突3.3.2.1相關第六十四頁，共一百三十四頁，編輯于2023年，星期四3.3流水線的相關與沖突數(shù)據(jù)相關對于兩條指令i（在前，下同）和j（在后，下同），如果下述條件之一成立，則稱指令j與指令i數(shù)據(jù)相關。

指令j使用指令i產(chǎn)生的結(jié)果；指令j與指令k數(shù)據(jù)相關，而指令k又與指令i數(shù)據(jù)相關。數(shù)據(jù)相關具有傳遞性。數(shù)據(jù)相關反映了數(shù)據(jù)的流動關系，即如何從其產(chǎn)生者流動到其消費者。第六十五頁，共一百三十四頁，編輯于2023年，星期四3.3流水線的相關與沖突

例如：下面這一段代碼存在數(shù)據(jù)相關。Loop：L.DF0，0（R1） //F0為數(shù)組元素

ADD.DF4，F(xiàn)0，F(xiàn)2 //加上F2中的值S.DF4，0（R1） //保存結(jié)果DADDIUR1，R1，－8 //數(shù)組指針遞減8個字節(jié)BNER1，R2，Loop //如果R1≠R2，則分支

第六十六頁，共一百三十四頁，編輯于2023年，星期四3.3流水線的相關與沖突當數(shù)據(jù)的流動是經(jīng)過寄存器時，相關的檢測比較直觀和容易。當數(shù)據(jù)的流動是經(jīng)過存儲器時，檢測比較復雜。相同形式的地址其有效地址未必相同。形式不同的地址其有效地址卻可能相同。名相關名：指令所訪問的寄存器或存儲器單元的名稱。如果兩條指令使用相同的名，但是它們之間并沒有數(shù)據(jù)流動，則稱這兩條指令存在名相關。第六十七頁，共一百三十四頁，編輯于2023年，星期四3.3流水線的相關與沖突指令j與指令i之間的名相關有兩種：反相關：如果指令j寫的名與指令i讀的名相同，則稱指令i和j發(fā)生了反相關。

指令j寫的名＝指令i讀的名輸出相關：如果指令j和指令i寫相同的名，則稱指令i和j發(fā)生了輸出相關。

指令j寫的名＝指令i寫的名第六十八頁，共一百三十四頁，編輯于2023年，星期四3.3流水線的相關與沖突名相關的兩條指令之間并沒有數(shù)據(jù)的傳送。如果一條指令中的名改變了，并不影響另外一條指令的執(zhí)行。換名技術換名技術：通過改變指令中操作數(shù)的名來消除名相關。對于寄存器操作數(shù)進行換名稱為寄存器換名。既可以用編譯器靜態(tài)實現(xiàn)，也可以用硬件動態(tài)完成。第六十九頁，共一百三十四頁，編輯于2023年，星期四3.3流水線的相關與沖突例如：考慮下述代碼：

DIV.D F2，F(xiàn)6，F(xiàn)4ADD.D F6，F(xiàn)0，F(xiàn)12SUB.D F8，F(xiàn)6，F(xiàn)14

DIV.D和ADD.D存在反相關。進行寄存器換名（F6換成S）后，變成：DIV.D F2，F(xiàn)6，F(xiàn)4ADD.D S，F(xiàn)0，F(xiàn)12SUB.D F8，S，F(xiàn)14第七十頁，共一百三十四頁，編輯于2023年，星期四3.3流水線的相關與沖突控制相關控制相關是指由分支指令引起的相關。為了保證程序應有的執(zhí)行順序，必須嚴格按控制相關確定的順序執(zhí)行。典型的程序結(jié)構(gòu)是“if-then”結(jié)構(gòu)。請看一個示例：ifp1{ S1；}；S；ifp2{ S2；}；第七十一頁，共一百三十四頁，編輯于2023年，星期四3.3流水線的相關與沖突控制相關帶來了以下兩個限制：與一條分支指令控制相關的指令不能被移到該分支之前，否則這些指令就不受該分支控制了。

對于上述的例子，then部分中的指令不能移到if語句之前。

如果一條指令與某分支指令不存在控制相關，就不能把該指令移到該分支之后。對于上述的例子，不能把S移到if語句的then部分中。第七十二頁，共一百三十四頁，編輯于2023年，星期四3.3流水線的相關與沖突

流水線沖突是指對于具體的流水線來說，由于相關的存在，使得指令流中的下一條指令不能在指定的時鐘周期執(zhí)行。流水線沖突有3種類型：結(jié)構(gòu)沖突：因硬件資源滿足不了指令重疊執(zhí)行的要求而發(fā)生的沖突。數(shù)據(jù)沖突：當指令在流水線中重疊執(zhí)行時，因需要用到前面指令的執(zhí)行結(jié)果而發(fā)生的沖突。控制沖突：流水線遇到分支指令和其他會改變PC值的指令所引起的沖突。3.3.2.2流水線沖突第七十三頁，共一百三十四頁，編輯于2023年，星期四3.3流水線的相關與沖突帶來的幾個問題：導致錯誤的執(zhí)行結(jié)果。流水線可能會出現(xiàn)停頓，從而降低流水線的效率和實際的加速比。我們約定當一條指令被暫停時，在該暫停指令之后流出的所有指令都要被暫停，而在該暫停指令之前流出的指令則繼續(xù)進行（否則就永遠無法消除沖突）。第七十四頁，共一百三十四頁，編輯于2023年，星期四3.3流水線的相關與沖突結(jié)構(gòu)沖突在流水線處理機中，為了能夠使各種組合的指令都能順利地重疊執(zhí)行，需要對功能部件進行流水或重復設置資源。如果某種指令組合因為資源沖突而不能正常執(zhí)行，則稱該處理機有結(jié)構(gòu)沖突。常見的導致結(jié)構(gòu)相關的原因：功能部件不是完全流水資源份數(shù)不夠第七十五頁，共一百三十四頁，編輯于2023年，星期四3.3流水線的相關與沖突結(jié)構(gòu)沖突舉例：訪存沖突

有些流水線處理機只有一個存儲器，將數(shù)據(jù)和指令放在一起，訪存指令會導致訪存沖突。解決辦法Ⅰ：插入暫停周期（“流水線氣泡”或“氣泡”）

引入暫停后的時空圖解決方法Ⅱ：

設置相互獨立的指令存儲器和數(shù)據(jù)存儲器或設置相互獨立的指令Cache和數(shù)據(jù)Cache。第七十六頁，共一百三十四頁，編輯于2023年，星期四3.3流水線的相關與沖突由于訪問同一個存儲器而引起的結(jié)構(gòu)沖突

第七十七頁，共一百三十四頁，編輯于2023年，星期四3.3流水線的相關與沖突為消除結(jié)構(gòu)沖突而插入的流水線氣泡第七十八頁，共一百三十四頁，編輯于2023年，星期四3.3流水線的相關與沖突引入暫停后的時空圖指令編號時鐘周期12345678910指令iIFIDEXMEMWB指令i+1IFIDEXMEMWB指令i+2IFIDEXMEMWBWB指令i+3stall

IFIDEXMEMWB指令i+4IFIDEXMEMWB指令i+5IFIDEXMEM第七十九頁，共一百三十四頁，編輯于2023年，星期四3.3流水線的相關與沖突有時流水線設計者允許結(jié)構(gòu)沖突的存在主要原因：減少硬件成本如果把流水線中的所有功能單元完全流水化，或者重復設置足夠份數(shù)，那么所花費的成本將相當高。數(shù)據(jù)沖突當相關的指令靠得足夠近時，它們在流水線中的重疊執(zhí)行或者重新排序會改變指令讀/寫操作數(shù)的順序，使之不同于它們非流水實現(xiàn)時的順序，則發(fā)生了數(shù)據(jù)沖突。第八十頁，共一百三十四頁，編輯于2023年，星期四3.3流水線的相關與沖突舉例：DADDR1，R2，R3DSUBR4，R1，R5XORR6，R1，R7ANDR8，R1，R9ORR10，R1，R11第八十一頁，共一百三十四頁，編輯于2023年，星期四3.3流水線的相關與沖突流水線的數(shù)據(jù)沖突舉例第八十二頁，共一百三十四頁，編輯于2023年，星期四3.3流水線的相關與沖突根據(jù)指令讀訪問和寫訪問的順序，可以將數(shù)據(jù)沖突分為3種類型。考慮兩條指令i和j

，且i在j之前進入流水線，可能發(fā)生的數(shù)據(jù)沖突有：寫后讀沖突（RAW）在

i

寫入之前，j

先去讀。

j

讀出的內(nèi)容是錯誤的。這是最常見的一種數(shù)據(jù)沖突，它對應于真數(shù)據(jù)相關。第八十三頁，共一百三十四頁，編輯于2023年，星期四3.3流水線的相關與沖突寫后寫沖突（WAW）在

i

寫入之前，j

先寫。最后寫入的結(jié)果是

i

的。錯誤！這種沖突對應于輸出相關。寫后寫沖突僅發(fā)生在這樣的流水線中：流水線中不只一個段可以進行寫操作。當先前某條指令停頓時，允許其后續(xù)指令繼續(xù)前進。前面介紹的5段流水線不會發(fā)生寫后寫沖突。（只在WB段寫寄存器）第八十四頁，共一百三十四頁，編輯于2023年，星期四3.3流水線的相關與沖突讀后寫沖突（WAR）在i

讀之前，j

先寫。

i

讀出的內(nèi)容是錯誤的！由反相關引起。這種沖突僅發(fā)生在這樣的情況下：有些指令的寫結(jié)果操作提前了，而且有些指令的讀操作滯后了。指令被重新排序了。

讀后寫沖突在前述5段流水線中不會發(fā)生。（讀操作（在ID段）在寫結(jié)果操作（在WB段）之前）第八十五頁，共一百三十四頁，編輯于2023年，星期四3.3流水線的相關與沖突通過定向技術減少數(shù)據(jù)沖突引起的停頓（定向技術也稱為旁路或短路）關鍵思想：在某條指令產(chǎn)生計算結(jié)果之前，其他指令并不真正立即需要該計算結(jié)果，如果能夠?qū)⒃撚嬎憬Y(jié)果從其產(chǎn)生的地方直接送到其他指令需要它的地方，那么就可以避免停頓。采用定向技術消除上例中的相關

工作過程演示第八十六頁，共一百三十四頁，編輯于2023年，星期四3.3流水線的相關與沖突采用定向技術后的流水線數(shù)據(jù)通路

第八十七頁，共一百三十四頁，編輯于2023年，星期四3.3流水線的相關與沖突當定向硬件檢測到前面某條指令的結(jié)果寄存器就是當前指令的源寄存器時，控制邏輯會將前面那條指令的結(jié)果直接從其產(chǎn)生的地方定向到當前指令所需的位置。結(jié)果數(shù)據(jù)不僅可以從某一功能部件的輸出定向到其自身的輸入，而且還可以定向到其他功能部件的輸入。

舉例:DSUBR1，R2，R3LDR5，0（R1）SDR5，12（R1）第八十八頁，共一百三十四頁，編輯于2023年，星期四3.3流水線的相關與沖突更多的定向路徑

第八十九頁，共一百三十四頁，編輯于2023年，星期四3.3流水線的相關與沖突需要停頓的數(shù)據(jù)沖突并不是所有的數(shù)據(jù)沖突都可以用定向技術來解決。

舉例:LDR1，0（R2）DADDR4，R1，R5ANDR6，R1，R7XORR8，R1，R9增加流水線互鎖硬件，插入“暫?！薄Ｗ饔茫簷z測發(fā)現(xiàn)數(shù)據(jù)沖突，并使流水線停頓，直至沖突消失。

舉例：演示A演示B第九十頁，共一百三十四頁，編輯于2023年，星期四3.3流水線的相關與沖突無法將LD指令的結(jié)果定向到DADD指令

第九十一頁，共一百三十四頁，編輯于2023年，星期四3.3流水線的相關與沖突流水線互鎖機制插入氣泡后的執(zhí)行過程

第九十二頁，共一百三十四頁，編輯于2023年，星期四3.3流水線的相關與沖突LDR1，0（R2）IFIDEXMEMWBDADDR4，R1，R5IFIDEXMEMWBANDR6，R1，R7IFIDEXMEMWBXORR8，R1，R9IFIDEXMEMWBLDR1，0（R2）IFIDEXMEMWBDADDR4，R1，R5IFIDstallEXMEMWBANDR6，R1，R7IFstallIDEXMEMWBXORR8，R1，R9stallIFIDEXMEM插入停頓前后的流水線時空圖

第九十三頁，共一百三十四頁，編輯于2023年，星期四3.3流水線的相關與沖突LDRb，BIFIDEXMEMWBLDRc，CIFIDEXEXMEMWBWBDADDRa，Rb，RcIFIDstall

EXMEMWBSDRa，AIFstall

IDEXMEMWB依靠編譯器解決數(shù)據(jù)沖突讓編譯器重新組織指令順序來消除沖突，這種技術稱為指令調(diào)度或流水線調(diào)度。例如：采用典型的代碼生成方法，

表達式A＝B＋C的代碼會導致暫停第九十四頁，共一百三十四頁，編輯于2023年，星期四調(diào)度前的代碼調(diào)度后的代碼LDRb，BLDRc，CDADDRa，Rb，RcSDRa，ALDRe，ELDRf，F(xiàn)DSUBRd，Re，RfSDRd，DLDRb，BLDRc，CLDRe，EDADDRa，Rb，RcLDRf，F(xiàn)SDRa，ADSUBRd，Re，RfSDRd，D舉例：

請為下列表達式生成沒有暫停的指令序列:

A＝B＋C；D＝E－F；

假設載入延遲為1個時鐘周期。

題解3.3流水線的相關與沖突第九十五頁，共一百三十四頁，編輯于2023年，星期四3.3流水線的相關與沖突控制沖突執(zhí)行分支指令的結(jié)果有兩種分支成功：PC值改變?yōu)榉种мD(zhuǎn)移的目標地址。在條件判定和轉(zhuǎn)移地址計算都完成后，才改變PC值。不成功或者失敗：PC的值保持正常遞增，指向順序的下一條指令。處理分支指令最簡單的方法：“凍結(jié)”或者“排空”流水線。

優(yōu)點：簡單。前述5段流水線中，改變PC值是在MEM段進行的。給流水線帶來了3個時鐘周期的延遲。第九十六頁，共一百三十四頁，編輯于2023年，星期四分支指令IFIDEXMEMWB分支目標指令IF

stall

stall

IFIDEXMEMWB分支目標指令+1IFIDEXMEMWB分支目標指令+2IFIDEXMEM分支目標指令+3IFIDEX分支指令IFIDEXMEMWB分支后繼指令

IFstall

stall

IFIDEXMEMWB分支后繼指令+1

IFIDEXMEMWB分支后繼指令+2IFIDEXMEM分支后繼指令+3IFIDEX簡單處理分支指令：分支成功的情況

簡單處理分支指令：分支失敗的情況

3.3流水線的相關與沖突第九十七頁，共一百三十四頁，編輯于2023年，星期四3.3流水線的相關與沖突把由分支指令引起的延遲稱為分支延遲。分支指令在目標代碼中出現(xiàn)的頻度每3～4條指令就有一條是分支指令?？刹扇煞N措施來減少分支延遲。在流水線中盡早判斷出分支轉(zhuǎn)移是否成功；盡早計算出分支目標地址。下面的討論中，我們假設：

這兩步工作被提前到ID段完成，即分支指令是在ID段的末尾執(zhí)行完成，所帶來的分支延遲為一個時鐘周期。第九十八頁，共一百三十四頁，編輯于2023年，星期四3.3流水線的相關與沖突3種通過軟件（編譯器）來減少分支延遲的方法

共同點：對分支的處理方法在程序的執(zhí)行過程中始終是不變的，是靜態(tài)的。要么總是預測分支成功，要么總是預測分支失敗。預測分支失敗

允許分支指令后的指令繼續(xù)在流水線中流動，就好象什么都沒發(fā)生似的。若確定分支失敗，將分支指令看作是一條普通指令，流水線正常流動。第九十九頁，共一百三十四頁，編輯于2023年，星期四3.3流水線的相關與沖突若確定分支成功，流水線就把在分支指令之后取出的所有指令轉(zhuǎn)化為空操作，并按分支目地重新取指令執(zhí)行。要保證：分支結(jié)果出來之前不會改變處理機的狀態(tài)，以便一旦猜錯時，處理機能夠回退到原先的狀態(tài)。第一百頁，共一百三十四頁，編輯于2023年，星期四3.3流水線的相關與沖突第一百零一頁，共一百三十四頁，編輯于2023年，星期四3.3流水線的相關與沖突預測分支成功假設分支轉(zhuǎn)移成功，并從分支目標地址處取指令執(zhí)行。前述5段流水線中，這種方法沒有任何好處，由于判斷分支是否成功與分支目標地址計算是在同一流水段完成。延遲分支主要思想：從邏輯上“延長”分支指令的執(zhí)行時間。把延遲分支看成是由原來的分支指令和若干個延遲槽構(gòu)成，不管分支是否成功，都要按順序執(zhí)行延遲槽中的指令。延遲分支以及指令的執(zhí)行順序第一百零二頁，共一百三十四頁，編輯于2023年，星期四具有一個分支延遲槽的流水線的執(zhí)行過程分支失敗分支指令iIFIDEXMEMWB延遲槽指令i+1

IFIDEXMEMWB指令i+2IFIDEXMEMWB指令i+3IFIDEXMEMWB指令i+4IFIDEXMEMWB分支延遲槽中的指令“掩蓋”了流水線原來必須插入的暫停周期。分支成功

分支指令iIFIDEXMEMWB

延遲槽指令i+1

IFIDEXMEMWB分支目標指令jIFIDEXMEMWB分支目標指令j+1IFIDEXMEMWB分支目標指令j+2IFIDEXMEMWB3.3流水線的相關與沖突第一百零三頁，共一百三十四頁，編輯于2023年，星期四3.3流水線的相關與沖突分支延遲指令的調(diào)度任務：在延遲槽中放入有用的指令。由編譯器完成。能否帶來好處取決于編譯器能否把有用的指令調(diào)度到延遲槽中。三種調(diào)度方法：從前調(diào)度從目標處調(diào)度從失敗處調(diào)度第一百零四頁，共一百三十四頁，編輯于2023年，星期四調(diào)度前和調(diào)度后的代碼3.3流水線的相關與沖突第一百零五頁，共一百三十四頁，編輯于2023年，星期四3.3流水線的相關與沖突三種方法的要求及效果調(diào)度策略對調(diào)度的要求什么情況下起作用從前調(diào)度從目標處調(diào)度從失敗處調(diào)度必須保證在分支失敗時執(zhí)行被調(diào)度

的指令不會導致錯誤。有可能需要

復制指令被調(diào)度的指令必須與分支無關必須保證在分支成功時執(zhí)行被調(diào)度

的指令不會導致錯誤任何情況分支成功時(但由于復制指令，有

可能會增大程序空間) 分支失敗時第一百零六頁，共一百三十四頁，編輯于2023年，星期四3.3流水線的相關與沖突分支延遲受到兩個方面的限制：可以被放入延遲槽中的指令要滿足一定的條件。編譯器預測分支轉(zhuǎn)移方向的能力。進一步改進：分支取消機制當分支的實際執(zhí)行方向和事先所預測的一樣時，執(zhí)行分支延遲槽中的指令，否則就將分支延遲槽中的指令轉(zhuǎn)化成一個空操作。第一百零七頁，共一百三十四頁，編輯于2023年，星期四分支失敗分支指令iIFIDEXMEMWB延遲槽指令i+1

IFidle

idleidleidle指令i+2IFIDEXMEMWB指令i+3IFIDEXMEMWB指令i+4IFIDEXMEMWB分支成功

分支指令iIFIDEXMEMWB

延遲槽指令i+1

IFIDEXMEMWB分支目標指令jIFIDEXMEMWB分支目標指令j+1IFIDEXMEMWB分支目標指令j+2IFIDEXMEMWB預測分支成功的情況下，分支取消機制的執(zhí)行情況第一百零八頁，共一百三十四頁，編輯于2023年，星期四實現(xiàn)MIPS指令子集的一種簡單數(shù)據(jù)通路。該數(shù)據(jù)通路的操作分成5個時鐘周期取指令指令譯碼/讀寄存器執(zhí)行/有效地址計算存儲器訪問/分支完成寫回只討論整數(shù)指令的實現(xiàn)（包括：load和store，等于0轉(zhuǎn)移，整數(shù)ALU指令等。）

3.4流水線的實現(xiàn)3.4.1MIPS的一種簡單實現(xiàn)第一百零九頁，共一百三十四頁，編輯于2023年，星期四第一百一十頁，共一百三十四頁，編輯于2023年，星期四3.4流水線的實現(xiàn)一條MIPS指令最多需要以下5個時鐘周期：取指令周期（IF）

操作IR←Mem[PC]NPC←PC+4指令譯碼/讀寄存器周期（ID）

操作A←Regs[rs]B←

Regs[rt]Imm←

（（IR16）16##IR16..31）指令的譯碼操作和讀寄存器操作是并行進行的。原因：在MIPS指令格式中，操作碼字段以及rs、rt

字段都是在固定的位置。這種技術稱為固定字段譯碼技術。

第一百一十一頁，共一百三十四頁，編輯于2023年，星期四3.4流水線的實現(xiàn)執(zhí)行/有效地址計算周期（EX）不同指令所進行的操作不同：存儲器訪問指令操作ALUo←A+Imm寄存器－寄存器ALU指令操作ALUo←AfuncB寄存器－立即值ALU指令操作ALUo←AopImm分支指令操作ALUo←NPC+（Imm<<2）；cond←（A=

=0）第一百一十二頁，共一百三十四頁，編輯于2023年，星期四3.4流水線的實現(xiàn)將有效地址計算周期和執(zhí)行周期合并為一個時鐘周期，這是因為MIPS指令集采用load／store結(jié)構(gòu)，沒有任何指令需要同時進行數(shù)據(jù)有效地址的計算、轉(zhuǎn)移目標地址的計算和對數(shù)據(jù)進行運算。存儲器訪問/分支完成周期（MEM）所有指令都要在該周期對PC進行更新。除了分支指令，其他指令都是做PC←NPC在該周期內(nèi)處理的MIPS指令僅僅有l(wèi)oad、store和分支三種指令。第一百一十三頁，共一百三十四頁，編輯于2023年，星期四3.4流水線的實現(xiàn)存儲器訪問指令操作LMD←Mem[ALUo]或者Mem[ALUo]←B分支指令操作if（cond）PC←ALUoelsePC←NPC寫回周期（WB）不同的指令在寫回周期完成的工作也不一樣。寄存器－寄存器ALU指令操作Regs[rd]←ALUo寄存器－立即數(shù)ALU指令操作Regs[rt]←ALUoload指令操作Regs[rt]←LMD第一百一十四頁，共一百三十四頁，編輯于2023年，星期四3.4流水線的實現(xiàn)不采用單周期實現(xiàn)方案的主要原因?qū)τ诖蠖鄶?shù)CPU來說，單周期實現(xiàn)效率很低，因為不同的指令所需完成的操作差別相當大，因而所需要的時鐘周期時間也大不一樣。單周期實現(xiàn)時，需要重復設置某些功能部件，而在多周期實現(xiàn)方案中，這些部件是可以共享的。第一百一十五頁，共一百三十四頁，編輯于2023年，星期四3.4流水線的實現(xiàn)每一個時鐘周期完成的工作看作是流水線的一段，每個時鐘周期啟動一條新的指令。流水實現(xiàn)的數(shù)據(jù)通路設置了流水寄存器段與段之間設置流水寄存器流水寄存器的命名用其相鄰的兩個段的名稱拼合而成。例如：ID段與EX段之間的流水寄存器用ID/EX表示每個流水寄存器是由若干個寄存器構(gòu)成的3.4.2基本的MIPS流水線第一百一十六頁，共一百三十四頁，編輯于2023年，星期四3.4流水線的實現(xiàn)流水實現(xiàn)的數(shù)據(jù)通路第一百一十七頁，共一百三十四頁，編輯于2023年，星期四3.4流水線的實現(xiàn)寄存器的命名形式為：x.y所包含的字段的命名形式為：x.y[s]其中：x：流水寄存器名稱

y：具體寄存器名稱

s：字段名稱例如：ID/EX.IR：流水寄存器ID/EX中的子寄存器IRIRID/EX.IR[op]：該寄存器的op字段（即操作碼字段）流水寄存器的作用將各段的工作隔開，使得它們不會互相干擾。保存相應段的處理結(jié)果。第一百一十八頁，共一百三十四頁，編輯于2023年，星期四3.4流水線的實現(xiàn)例如：EX/MEM.ALUo：保存EX段ALU的運算結(jié)果MEM/WB.LMD：保存MEM段從數(shù)據(jù)存儲器讀出的數(shù)據(jù)向后傳遞后面將要用到的數(shù)據(jù)或者控制信息所有有用的數(shù)據(jù)和控制信息每個時鐘周期會隨著指令在流水線中的流動往后流動一段。

增加了向后傳遞IR和從MEM/WB.IR回送到通用寄存器組的連接。將對PC的修改移到了IF段，以便PC能及時地加

4，為取下一條指令做好準備。第一百一十九頁，共一百三十四頁，編輯于2023年，星期四3.4流水線的實現(xiàn)每一個流水段進行的操作IR[rs]＝IR6..10IR[rt]＝IR11..15IR[rd]＝IR16..20

第一百二十頁，共一百三十四頁，編輯于2023年，星期四流水段流水線的每個流水段的操作所有指令類型ALU指令load/store指令分支指令IFIDEXIF/ID.IR←Mem[PC]IF/ID.NPC,PC←（if（（EX/MEM.IR[op]==branch）&EX/MEM.cond）{EX/MEM.ALUo}else{PC+4}）；

ID/EX.A←Regs[IF/ID.IR[rs]]；ID/EX.B←Regs[IF/ID.IR[rt]]；ID/EX.NPC←IF/ID.NPC；ID/EX.IR←IF/ID.IR；ID/EX.Imm←（IF/ID.IR16)16##IF/ID.IR16..31；

EX/MEM.IR←ID/EX.IR；EX/MEM.ALUo←ID/EX.AfuncID/EX.B或EX/MEM.ALUo←ID/EX.AopID/EX.Imm；

EX/MEM.IR←ID/EX.IR；EX/MEM.ALUo←ID/EX.A+ID/EX.Imm；EX/MEM.B←ID/EX.B；

EX/MEM.IR←ID/EX.IR；EX/MEM.ALUo←ID/EX.NPC+ID/EX.Imm<<2；EX/MEM.cond←（ID/EX.A==0）；

(動畫演示)(動畫演示)(動畫演示)(動畫演示)(動畫演示)第一百二十一頁，共一百三十四頁，編輯于2023年，星期四流水段任何指令類型ALU指令load/store指令分支指令MEMWBMEM/WB.IR←EX/MEM.IR；MEM/WB.ALUo←EX/MEM.ALUo；

MEM/WB.IR←EX/MEM.IR；MEM/WB.LMD←Mem[EX/MEM.ALUo]；或Mem[EX/MEM.ALUo]←EX/MEM.B；

Regs[MEM/WB.IR[rd]]←MEM/WB.ALUo；或Regs[MEM/WB.IR[rt]]←MEM/WB.ALUo；

Regs[MEM/WB.IR[rt]]←MEM/WB.LMD；

流水線的每個流水段的操作(動畫演示)(動畫演示)(動畫演示)(動畫演示)第一百二十二頁，共一百三十四頁，編輯于2023年，星期四3.4流水線的實現(xiàn)流水線的控制主要是如何控制4個多路選擇器。MUX2：若ID/EX.IR中的指令是分支指令，則選擇ID/EX.NPC，否則選ID/EX.A。MUX3：若ID/EX.IR中的指令是寄存器－寄存器型ALU指令，則選ID/EX.B，否則選ID/EX.Imm。MUX1：若EX/MEM.IR中的指令是分支指令，而且EX/MEM.cond為真，則選EX/MEM.ALUo，即分支目標地址，否則選PC+4。MUX