計算機體系結構第三章-2

1、n3.4 流水線的相關與沖突一、一個經典的5段流水線 (RISC(RISC流水線流水線) ) 一條指令的執(zhí)行過程分為5個周期：取指令周期（取指令周期（IF）、指令）、指令譯碼譯碼/讀寄存器周期（讀寄存器周期（ID）、執(zhí)行）、執(zhí)行/有效地址計算周期（有效地址計算周期（EX）、）、存儲器訪問分支完成周期（存儲器訪問分支完成周期（MEM）、）、寫回周期（寫回周期（WBWB）。）。3.4 流水線的相關與沖突流水線的相關與沖突n三類指令對三類指令對5 5級流水線的占用情況級流水線的占用情況: :ALU指令指令LOAD/STORE分支指令分支指令S1IF 取指取指取指取指取指取指S2ID 譯碼譯碼,讀通用

2、讀通用寄存器寄存器譯碼譯碼,讀通用寄存器讀通用寄存器譯碼譯碼,讀通用寄存讀通用寄存器器S3EX 運算（運算（R-R,R-立即數）立即數）計算有效地址計算有效地址計算轉移目標地計算轉移目標地址址,設置條件碼設置條件碼S4MEM-訪存訪存(讀或寫讀或寫)（store完成）完成）若條件成立若條件成立,將轉將轉移目標地址送移目標地址送PC（分支完成）（分支完成）S5WB 結果寫回通用結果寫回通用寄存器寄存器（ALU完成）完成）讀出數據寫入通用寄讀出數據寫入通用寄存器存器-3.4 流水線的相關與沖突流水線的相關與沖突3.4 流水線的相關與沖突流水線的相關與沖突n流水設計中流水設計中的一些的一些問題及解決

3、：問題及解決：IF(取指令取指令)，MEM(讀讀/寫寫數據數據)，訪存沖突。訪存沖突。通用寄存器訪存通用寄存器訪存沖突沖突-分分半拍。半拍。專門的加法器：專門的加法器：PCPC+4。n5段流水線的兩種描述方式n第一種描述（類似于時空圖）3.4 流水線的相關與沖突流水線的相關與沖突n第二種描述（按時間錯開的數據通路序列）3.4 流水線的相關與沖突流水線的相關與沖突二、相關二、相關n相關是指兩條指令之間存在某種依賴關系。n 如果兩條指令相關，則它們就有可能不能在流水線中重疊執(zhí)行或者只能部分重疊執(zhí)行。n主要是三種類型的相關: 數據數據相關相關 名名相關相關 控制控制相關相關3.4 流水線的相關與沖突

4、流水線的相關與沖突1、數據相關（真數據相關）、數據相關（真數據相關）n對于兩條指令i（在前）和j（在后），如果下述條件之一成立，則稱指令j與指令i數據相關。 u指令j使用指令i產生的結果；u指令j與指令k數據相關，而指令k又與指令i數據相關。n數據相關具有傳遞性。傳遞性。n數據相關反映了數據的流動關系，即如何從其產生者流動到其消費者。3.4 流水線的相關與沖突流水線的相關與沖突例如：下面這一段代碼存在數據相關 Loop： L. D F0，0(R1) / F0為數組元素 ADD.D F4，F(xiàn)0，F(xiàn)2 / 加上F2中的值 S. D F4 ，0(R1) / 保存結果 DADDIU R1，R1，8 /

5、 數組指針遞減8個字節(jié) BNE R1，R2，Loop / 如果R1R2，則分支3.4 流水線的相關與沖突流水線的相關與沖突當數據的流動是經過寄存器時，相關的檢測比較直觀當數據的流動是經過寄存器時，相關的檢測比較直觀和容易。和容易。當數據的流動是經過存儲器時，檢測比較復雜。當數據的流動是經過存儲器時，檢測比較復雜。 相同形式的地址其有效地址未必相同。相同形式的地址其有效地址未必相同。 形式不同的地址其有效地址卻可能相同。形式不同的地址其有效地址卻可能相同。3.4 流水線的相關與沖突流水線的相關與沖突2、名相關、名相關名：名：指令所訪問的寄存器或存儲器單元的名稱。如果兩條指令使用相同的名，但是它們

6、之間并沒有數據流動，則稱這兩條指令存在名相關。3.4 流水線的相關與沖突流水線的相關與沖突指令j（在后）與指令i（在前）之間的名相關有兩種： （1）反相關：）反相關：如果指令如果指令j寫的名與指令寫的名與指令i讀的名相同，則讀的名相同，則稱指令稱指令i和和j發(fā)生了反相關。發(fā)生了反相關。 指令i讀的名 指令j寫的名 例如： DIV.D F2，F(xiàn)6，F(xiàn)4 （先讀）（先讀） ADD.D F6，F(xiàn)0，F(xiàn)12 （后寫（后寫）（2） 輸出相關：輸出相關：如果指令如果指令j和指令和指令i寫相同的名，則稱寫相同的名，則稱指令指令i和和j發(fā)生了輸出相關。發(fā)生了輸出相關。 指令i寫的名 指令j寫的名3.4 流水線

7、的相關與沖突流水線的相關與沖突名相關小結：l名相關的兩條指令之間并沒有數據的傳送。l但名相關的兩條指令之間的執(zhí)行順序必須嚴格遵守。l如果一條指令中的名改變了，并不影響另外一條指令的執(zhí)行。針對名相關：可采用換名技術，消除名相關。3.4 流水線的相關與沖突流水線的相關與沖突換名技術：換名技術：通過改變指令中操作數的名來消除名相關。 例如：考慮下述代碼： DIV.DF2，F(xiàn)6，F(xiàn)4 ADD.DF6，F(xiàn)0，F(xiàn)12 SUB.DF8，F(xiàn)6，F(xiàn)14w進行寄存器換名（進行寄存器換名（F6 F6 換成換成 S S）后，變成：）后，變成： DIV.DF2，F(xiàn)6，F(xiàn)4 ADD.DS S，F(xiàn)0，F(xiàn)12 SUB.DF8

8、，S S，F(xiàn)14 3.4 流水線的相關與沖突流水線的相關與沖突反相關反相關3、控制相關、控制相關n控制相關控制相關是指由分支指令引起的相關。n典型的程序結構是“if-then”結構。3.4 流水線的相關與沖突流水線的相關與沖突if p1 if p1 S1 S1； ；S S；if p2 if p2 S2 S2； ； 控制相關帶來了以下兩個限制：兩個限制：l 與一條分支指令控制相關的指令不能被移到該分支之前，否則這些指令就不受該分支控制了。l 如果一條指令與某分支指令不存在控制相關，就不能把該指令移到該分支之后。三、流水線沖突三、流水線沖突流水線沖突流水線沖突是指對于具體的流水線來說，由于相關的存

9、在，使得指令流中的下一條指令不能在指定的時鐘周期執(zhí)行。n 流水線沖突有3種類型：結構沖突結構沖突數據沖突數據沖突控制沖突控制沖突3.4 流水線的相關與沖突流水線的相關與沖突（一）（一）結構沖突結構沖突 指多條指令進入流水線后，在同一時間爭用同一功能部件，從而發(fā)生沖突。n例如：存儲器訪問沖突1 2 3 4 5 6 7 8指令指令LOADIF ID EX MEM WB指令指令i+1 IF ID EX MEM WB指令指令i+2 IF ID EX MEM WB指令指令i+3 IF ID EX MEM WB指令指令i+4 IF ID EX MEM訪存沖突訪存沖突3.4 流水線的相關與沖突流水線的相關與

10、沖突3.4 流水線的相關與沖突流水線的相關與沖突n解決辦法解決辦法：暫停一拍（也稱為流水線氣泡，簡稱氣泡）。暫停一拍（也稱為流水線氣泡，簡稱氣泡）。1 2 3 4 5 6 7 8 9指令指令LOADIF ID EX MEM WB指令指令i+1 IF ID EX MEM WB指令指令i+2 IF ID EX MEM WB指令指令i+3 停頓停頓 IF ID EX MEM WB指令指令i+4 IF ID EX MEM3.4 流水線的相關與沖突流水線的相關與沖突 時時間間（時時鐘鐘周周期期） 1 2 3 4 5 6 M Reg ALU M Reg M Reg ALU M Reg M Reg ALU

11、M Reg 7 8 load 指指令令i+1 指指令令i+2 暫暫 停停 M Reg ALU M 指指令令i+3 氣氣泡泡 氣氣泡泡 氣氣泡泡 氣氣泡泡 氣氣泡泡 3.4 流水線的相關與沖突流水線的相關與沖突n解決方法解決方法： 設置相互獨立的指令存儲器和數據存儲器或設置相互獨設置相互獨立的指令存儲器和數據存儲器或設置相互獨立的指令立的指令CacheCache和數據和數據CacheCache。3.4 流水線的相關與沖突流水線的相關與沖突u 說明：有時流水線設計者允許結構沖突的存在 主要原因：主要原因：減少硬件成本減少硬件成本（二）（二）數據沖突數據沖突 1、數據沖突、數據沖突指由于流水線中各指

12、令重疊執(zhí)行，使得原來對操作數的訪問順序發(fā)生變化，從而引起的一種數據沖突。 例如：DADD R1，R2，R3 （寫R1） DSUB R4，R1，R5 （讀R1）1 2 3 4 5 6DADDIF ID EX MEM WBDSUB IF ID EX MEM WB寫寫R1讀讀R13.4 流水線的相關與沖突流水線的相關與沖突n根據指令讀訪問和寫訪問的順序，根據指令讀訪問和寫訪問的順序，假設兩條指令假設兩條指令i i和和j j，且且i i在在j j之前進入流水線，可能發(fā)生的數據沖突有之前進入流水線，可能發(fā)生的數據沖突有3 3種類種類型型：（1 1）寫后讀沖突（）寫后讀沖突（RAWRAW） i i 寫入寫

13、入 j j 讀出讀出如果在如果在 i i 寫入之前，寫入之前，j j 先去讀，先去讀，j j 讀出的內容是錯誤的。讀出的內容是錯誤的。n- -對應對應真數據相關真數據相關。 3.4 流水線的相關與沖突流水線的相關與沖突（2 2）寫后寫沖突（）寫后寫沖突（WAWWAW） i i 寫入寫入 j j 寫入寫入 如果在如果在 i i 寫入之前，寫入之前，j j 先寫，最后寫入的結果是的錯誤！先寫，最后寫入的結果是的錯誤！n - -對應對應輸出相關輸出相關。n 寫后寫沖突發(fā)生的情況：寫后寫沖突發(fā)生的情況：n流水線中不只一個段可以進行寫操作。（流水線中不只一個段可以進行寫操作。（介紹的介紹的5 5段流水線

14、段流水線不會發(fā)生不會發(fā)生）n當先前某條指令停頓時，允許其后續(xù)指令繼續(xù)前進。當先前某條指令停頓時，允許其后續(xù)指令繼續(xù)前進。3.4 流水線的相關與沖突流水線的相關與沖突（3 3）讀后寫沖突（）讀后寫沖突（WARWAR） i i 讀出讀出j j 寫入寫入 如果在如果在 i i 讀之前，讀之前，j j 先寫。先寫。i i 讀出的內容是錯誤的！讀出的內容是錯誤的！n-對應對應反相關反相關。 n讀后寫沖突發(fā)生的情況：讀后寫沖突發(fā)生的情況：n有些指令的寫結果操作提前了，而且有些指令的讀操作滯后了。有些指令的寫結果操作提前了，而且有些指令的讀操作滯后了。n指令被重新排序了。指令被重新排序了。 讀后寫沖突在前述

15、讀后寫沖突在前述5 5段流水線中不會發(fā)生。段流水線中不會發(fā)生。（讀操作（在（讀操作（在IDID段）在寫結果操作（在段）在寫結果操作（在WBWB段）之前）段）之前）3.4 流水線的相關與沖突流水線的相關與沖突2、解決辦法：、解決辦法：- 針對針對“寫后讀沖突寫后讀沖突” 解決辦法1：采用定向傳送技術定向傳送技術（旁路技術或相關專用通路技術）。3.4 流水線的相關與沖突流水線的相關與沖突例： DADD R1，R2，R3 DSUB R4，R1，R5 XOR R6，R1，R7 AND R8，R1，R9 OR R10，R1，R11 時間（時鐘周期） 1 2 3 4 5 6 IM Reg ALU DM R

16、eg IM Reg ALU DM Reg IM Reg ALU DM IM Reg ALU DADD R1， R2， R3 DSUB R4，R1，R5 XOR R6，R1，R7 AND R8，R1，R9 IM Reg OR R10，R1，R11 寫寫R1讀讀R1流水線的數據沖突舉例 產生數產生數據據ALU目標目標R旁路傳送旁路傳送寄存器寄存器 時間（時鐘周期） 1 2 3 4 5 6 IM Reg ALU DM Reg IM Reg ALU DM Reg IM Reg ALU DM IM Reg ALU DADD R1，R2，R3 DSUB R4，R1，R5 XOR R6，R1，R7 AND

17、R8，R1，R9 IM Reg OR R10，R1，R11 3.4 流水線的相關與沖突流水線的相關與沖突采用定向技術后的流水線數據通路 n定向技術定向技術關鍵思想：關鍵思想： 在某條指令產生計算結果之前，其他指令并不真正立在某條指令產生計算結果之前，其他指令并不真正立即需要該計算結果，如果能夠將該計算結果即需要該計算結果，如果能夠將該計算結果從其產生的地從其產生的地方方直接送到其他指令直接送到其他指令需要它的地方需要它的地方，那么就可以避免停頓。，那么就可以避免停頓。n推廣一般的情況：推廣一般的情況： 結果數據不僅可以從某一功能部件的輸出定向到其自身的輸入，而且還可以定向到其他功能部件的輸入。

18、3.4 流水線的相關與沖突流水線的相關與沖突 時間（時鐘周期） 1 2 3 4 5 6 IM Reg ALU DM Reg IM Reg ALU DM Reg IM Reg ALU DM DSUB R1, R2, R3 LD R5，0(R1) SD R5，12(R1) 3.4 流水線的相關與沖突流水線的相關與沖突DSUB DSUB R1R1，R2R2，R3R3LD LD R5R5，0 0（R1R1）SD SD R5R5，1212（R1R1）但是，定向技術并不能解決所有但是，定向技術并不能解決所有RAW沖突。沖突。例如： LD R1，0（R2） DADD R4，R1，R5 AND R6，R1，R

19、7 XOR R8，R1，R9 時間（時鐘周期） 1 2 3 4 5 6 IM Reg ALU DM Reg IM Reg ALU DM Reg IM Reg ALU DM IM Reg ALU LD R1，0(R2) DADD R4，R1，R5 AND R6，R1，R7 XOR R8，R1，R9 無法將無法將LD指令的結果定指令的結果定向到向到DADD指令指令 解決方法解決方法2：增加流水線互鎖互鎖硬件，插入“暫停”。作用：檢測發(fā)現(xiàn)數據沖突，并使流水線停頓，直至沖突消失。 時間（時鐘周期） 1 2 3 4 5 6 IM Reg ALU DM Reg IM Reg ALU DM IM Reg A

20、LU IM Reg LD R1，0(R2) DADD R4，R1，R5 AND R6，R1，R7 XOR R8，R1，R9 氣泡 氣泡 氣泡 解決方法解決方法3：指令調度技術（流水線調度）n前提：在非按序流動方式（亂步流動）的流水線中。n實現(xiàn)：通過編譯器重新組織指令順序來消除沖突。指允許輸出結果的次序指允許輸出結果的次序與輸入指令的次序不同。與輸入指令的次序不同。例如：例如：表達式表達式 A=B+C，采用典型的代碼生成方法：，采用典型的代碼生成方法：LD RbLD Rb，B B IF ID EX MEM WB LD RcLD Rc，C C IF ID EX MEMWB DADD RaDADD

21、Ra，RbRb，Rc Rc IF ID stallstall EX MEM WB SD Ra SD Ra ，A A IF stallstall ID EX MEM WB 3.4 流水線的相關與沖突流水線的相關與沖突調度前的代碼 調度后的代碼 LD Rb，BLD Rc，CDADD Ra，Rb，Rc SD Ra，ALD Re，ELD Rf，F(xiàn)DSUB Rd，Re，RfSD Rd，D LD Rb，BLD Rc，CLD Re，E DADD Ra，Rb，RcLD Rf，F(xiàn)SD Ra，A DSUB Rd，Re，RfSD Rd，D 例：例：請為下列表達式生成沒有暫停的指令序列請為下列表達式生成沒有暫停的指令

22、序列: : A AB BC C ； D DE EF F ； 假設載入延遲為假設載入延遲為1 1個個時鐘周期。時鐘周期。 （三）控制（三）控制沖突沖突1 1、控制沖突、控制沖突流水線流水線遇到分支指令（條件轉移）和其他會改變遇到分支指令（條件轉移）和其他會改變PC值值的指令所引起的沖突。的指令所引起的沖突。n分支指令的簡單處理：“凍結”，或“排空”流水線1 2 3 4 5 6 7 8分支指令IF ID EX MEM WB分支目標指令i IF 停頓 停頓 IF ID EX MEM分支目標指令i+1 停頓 停頓 停頓 IF ID EX分支目標指令i+3 停頓 停頓 停頓 IF ID更新更新PC值值3

23、.4 流水線的相關與沖突流水線的相關與沖突檢測到分支檢測到分支分支延遲分支延遲:3個周期個周期3.4 流水線的相關與沖突流水線的相關與沖突n轉移指令對流水線的影響轉移指令對流水線的影響 假設：在某一程序中， 分支指令在程序中所占的比例為25%，其中轉移成功的概率為2/3。按分支延遲為3個時鐘周期的情況，試計算該流水線指令的平均時鐘周期數。（流水線理想的CPI=1）75. 1%751%25) 13()(1ICICCPICPIinii2 2、有關措施、有關措施 為了減小分支延遲造成的損失，可采用以下措施：1）在流水線中盡早判斷出分支轉移是否成功。）在流水線中盡早判斷出分支轉移是否成功。2）盡早計算

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