3.4流水線的相關與沖突一、一個經典的5段流水線(RISC流水線)

一條指令的執行過程分為5個周期：取指令周期（IF）、指令譯碼/讀寄存器周期（ID）、執行/有效地址計算周期（EX）、存儲器訪問／分支完成周期（MEM）、寫回周期（WB）。3.4流水線的相關與沖突三類指令對5級流水線的占用情況:ALU指令LOAD/STORE分支指令S1IF取指取指取指S2ID譯碼,讀通用寄存器譯碼,讀通用寄存器譯碼,讀通用寄存器S3EX運算（R-R,R-立即數）計算有效地址計算轉移目標地址,設置條件碼S4MEM--訪存(讀或寫)（store完成）若條件成立,將轉移目標地址送PC（分支完成）S5WB結果寫回通用寄存器（ALU完成）讀出數據寫入通用寄存器--3.4流水線的相關與沖突3.4流水線的相關與沖突流水設計中的一些問題及解決：IF(取指令)，MEM(讀/寫數據)，訪存沖突。通用寄存器訪存沖突---分半拍。專門的加法器：PCPC+4。5段流水線的兩種描述方式第一種描述（類似于時空圖）3.4流水線的相關與沖突第二種描述（按時間錯開的數據通路序列）3.4流水線的相關與沖突二、相關相關是指兩條指令之間存在某種依賴關系。如果兩條指令相關，則它們就有可能不能在流水線中重疊執行或者只能部分重疊執行。主要是三種類型的相關:

數據相關

名相關

控制相關3.4流水線的相關與沖突1、數據相關（真數據相關）對于兩條指令i（在前）和j（在后），如果下述條件之一成立，則稱指令j與指令i數據相關。

指令j使用指令i產生的結果；指令j與指令k數據相關，而指令k又與指令i數據相關。數據相關具有傳遞性。數據相關反映了數據的流動關系，即如何從其產生者流動到其消費者。3.4流水線的相關與沖突例如：下面這一段代碼存在數據相關

Loop：L.DF0，0(R1) //F0為數組元素

ADD.DF4，F0，F2 //加上F2中的值

S.D F4

，0(R1)

//保存結果

DADDIUR1，R1，－8 //數組指針遞減8個字節

BNER1，R2，Loop //如果R1≠R2，則分支3.4流水線的相關與沖突當數據的流動是經過寄存器時，相關的檢測比較直觀和容易。當數據的流動是經過存儲器時，檢測比較復雜。相同形式的地址其有效地址未必相同。形式不同的地址其有效地址卻可能相同。3.4流水線的相關與沖突2、名相關名：指令所訪問的寄存器或存儲器單元的名稱。如果兩條指令使用相同的名，但是它們之間并沒有數據流動，則稱這兩條指令存在名相關。3.4流水線的相關與沖突指令j（在后）與指令i（在前）之間的名相關有兩種：（1）反相關：如果指令j寫的名與指令i讀的名相同，則稱指令i和j發生了反相關。指令i讀的名＝指令j寫的名例如：

DIV.D F2，F6，F4（先讀）

ADD.D

F6，F0，F12（后寫）（2）輸出相關：如果指令j和指令i寫相同的名，則稱指令i和j發生了輸出相關。指令i寫的名＝指令j寫的名3.4流水線的相關與沖突名相關小結：名相關的兩條指令之間并沒有數據的傳送。但名相關的兩條指令之間的執行順序必須嚴格遵守。如果一條指令中的名改變了，并不影響另外一條指令的執行。針對名相關：可采用換名技術，消除名相關。3.4流水線的相關與沖突換名技術：通過改變指令中操作數的名來消除名相關。例如：考慮下述代碼：

DIV.D F2，F6，F4ADD.D F6，F0，F12SUB.D F8，F6，F14進行寄存器換名（F6換成S）后，變成：

DIV.D F2，F6，F4ADD.D S，F0，F12SUB.D F8，S，F143.4流水線的相關與沖突反相關3、控制相關控制相關是指由分支指令引起的相關。典型的程序結構是“if-then”結構。3.4流水線的相關與沖突ifp1{ S1；

}；S；ifp2{ S2；

}；

控制相關帶來了以下兩個限制：與一條分支指令控制相關的指令不能被移到該分支之前，否則這些指令就不受該分支控制了。如果一條指令與某分支指令不存在控制相關，就不能把該指令移到該分支之后。三、流水線沖突流水線沖突是指對于具體的流水線來說，由于相關的存在，使得指令流中的下一條指令不能在指定的時鐘周期執行。流水線沖突有3種類型：結構沖突數據沖突控制沖突3.4流水線的相關與沖突（一）結構沖突指多條指令進入流水線后，在同一時間爭用同一功能部件，從而發生沖突。例如：存儲器訪問沖突12345678指令LOADIFIDEXMEMWB指令i+1IFIDEXMEMWB指令i+2IFIDEXMEMWB指令i+3

IFIDEXMEMWB指令i+4IFIDEXMEM訪存沖突3.4流水線的相關與沖突3.4流水線的相關與沖突解決辦法Ⅰ：暫停一拍（也稱為流水線氣泡，簡稱氣泡）。123456789指令LOADIFIDEXMEMWB指令i+1IFIDEXMEMWB指令i+2IFIDEXMEMWB指令i+3

停頓

IFIDEXMEMWB指令i+4IFIDEXMEM3.4流水線的相關與沖突3.4流水線的相關與沖突解決方法Ⅱ：

設置相互獨立的指令存儲器和數據存儲器或設置相互獨立的指令Cache和數據Cache。3.4流水線的相關與沖突

說明：有時流水線設計者允許結構沖突的存在主要原因：減少硬件成本（二）數據沖突

1、數據沖突指由于流水線中各指令重疊執行，使得原來對操作數的訪問順序發生變化，從而引起的一種數據沖突。例如：DADDR1，R2，R3（寫R1）

DSUBR4，R1，R5（讀R1）123456DADDIFIDEXMEM

WBDSUBIFIDEXMEMWB寫R1讀R13.4流水線的相關與沖突根據指令讀訪問和寫訪問的順序，假設兩條指令i和j，且i在j之前進入流水線，可能發生的數據沖突有3種類型：（1）寫后讀沖突（RAW）

i

寫入

j

讀出

如果在

i

寫入之前，j

先去讀，j

讀出的內容是錯誤的。-對應真數據相關。3.4流水線的相關與沖突（2）寫后寫沖突（WAW）

i

寫入

j

寫入如果在

i

寫入之前，j

先寫，最后寫入的結果是的錯誤！

-對應輸出相關。

寫后寫沖突發生的情況：流水線中不只一個段可以進行寫操作。（介紹的5段流水線不會發生）當先前某條指令停頓時，允許其后續指令繼續前進。3.4流水線的相關與沖突（3）讀后寫沖突（WAR）

i

讀出

j

寫入如果在i

讀之前，j

先寫。i

讀出的內容是錯誤的！-對應反相關。

讀后寫沖突發生的情況：有些指令的寫結果操作提前了，而且有些指令的讀操作滯后了。指令被重新排序了。讀后寫沖突在前述5段流水線中不會發生。（讀操作（在ID段）在寫結果操作（在WB段）之前）3.4流水線的相關與沖突2、解決辦法：-針對“寫后讀沖突”

解決辦法1：采用定向傳送技術（旁路技術或相關專用通路技術）。3.4流水線的相關與沖突例：DADDR1，R2，R3DSUBR4，R1，R5XORR6，R1，R7ANDR8，R1，R9ORR10，R1，R11寫R1讀R1流水線的數據沖突舉例產生數據ALU目標R旁路傳送寄存器3.4流水線的相關與沖突采用定向技術后的流水線數據通路

定向技術關鍵思想：在某條指令產生計算結果之前，其他指令并不真正立即需要該計算結果，如果能夠將該計算結果從其產生的地方直接送到其他指令需要它的地方，那么就可以避免停頓。推廣一般的情況：

結果數據不僅可以從某一功能部件的輸出定向到其自身的輸入，而且還可以定向到其他功能部件的輸入。3.4流水線的相關與沖突3.4流水線的相關與沖突DSUBR1，R2，R3LDR5，0（R1）SDR5，12（R1）但是，定向技術并不能解決所有RAW沖突。例如： LDR1，0（R2）

DADDR4，R1，R5 ANDR6，R1，R7 XORR8，R1，R9無法將LD指令的結果定向到DADD指令

解決方法2：增加流水線互鎖硬件，插入“暫停”。作用：檢測發現數據沖突，并使流水線停頓，直至沖突消失。

解決方法3：指令調度技術（流水線調度）前提：在非按序流動方式（亂步流動）的流水線中。實現：通過編譯器重新組織指令順序來消除沖突。指允許輸出結果的次序與輸入指令的次序不同。例如：表達式A=B+C，采用典型的代碼生成方法：LDRb，BIFIDEXMEMWBLDRc，CIFIDEXMEMWBDADDRa，Rb，RcIFIDstall

EXMEMWBSDRa，AIFstall

IDEXMEMWB3.4流水線的相關與沖突調度前的代碼調度后的代碼LDRb，BLDRc，CDADDRa，Rb，Rc

SDRa，ALDRe，ELDRf，FDSUBRd，Re，RfSDRd，DLDRb，BLDRc，CLDRe，EDADDRa，Rb，RcLDRf，FSDRa，ADSUBRd，Re，RfSDRd，D例：請為下列表達式生成沒有暫停的指令序列:

A＝B＋C；

D＝E－F；

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

（三）控制沖突1、控制沖突流水線遇到分支指令（條件轉移）和其他會改變PC值的指令所引起的沖突。分支指令的簡單處理：“凍結”，或“排空”流水線12345678分支指令IFIDEXMEMWB分支目標指令i

IF

停頓停頓IFIDEXMEM分支目標指令i+1

停頓停頓停頓IFIDEX分支目標指令i+3

停頓停頓停頓IFID更新PC值3.4流水線的相關與沖突檢測到分支分支延遲:3個周期3.4流水線的相關與沖突轉移指令對流水線的影響假設：在某一程序中，分支指令在程序中所占的比例為25%，其中轉移成功的概率為2/3。按分支延遲為3個時鐘周期的情況，試計算該流水線指令的平均時鐘周期數。（流水線理想的CPI=1）2、有關措施為了減小分支延遲造成的損失，可采用以下措施：1）在流水線中盡早判斷出分支轉移是否成功。2）盡早計算出分支目標地址。兩種措施同時采用，缺一不可。假設該兩步工作被提前到ID段完成，即分支指令是在ID段的末尾執行完成，所帶來的分支延遲為一個時鐘周期。3.4流水線的相關與沖突減少分支延遲的方法有多種，下面介紹3種常見的方法。減少分支延遲的方法：通過軟件（編譯器）來減少分支延遲（靜態方法）（1）預測分支失敗允許分支指令后的指令繼續在流水線中流動，就好象什么都沒發生似的。若確定分支失敗，將分支指令看作是一條普通指令，流水線正常流動。若確定分支成功，流水線就把在分支指令之后取出的所有指令轉化為空操作，并按分支目地重新取指令執行。3.4流水線的相關與沖突預測分支失敗的情況：分支失敗分支成功3.4流水線的相關與沖突例如：在某一程序中，分支指令在程序中所占的比例為25%，其中轉移成功的概率為2/3。試計算該流水線指令的平均時鐘周期數。（流水線理想的CPI=1）

解：假設采用預測分支失敗的方法則，執行一條指令的平均時鐘周期數為CPI為：

CPI=(1-25%)×1+25%×1/3×1+25%×2/3×(1+1)≈1.173.4流水線的相