計算機體系結(jié)構(gòu)第三章-2

3.4流水線的相關(guān)與沖突一、一個經(jīng)典的5段流水線(RISC流水線)

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

數(shù)據(jù)相關(guān)

名相關(guān)

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

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

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

ADD.DF4，F(xiàn)0，F(xiàn)2 //加上F2中的值

S.D F4

，0(R1)

//保存結(jié)果

DADDIUR1，R1，－8 //數(shù)組指針遞減8個字節(jié)

BNER1，R2，Loop //如果R1≠R2，則分支3.4流水線的相關(guān)與沖突當(dāng)數(shù)據(jù)的流動是經(jīng)過寄存器時，相關(guān)的檢測比較直觀和容易。當(dāng)數(shù)據(jù)的流動是經(jīng)過存儲器時，檢測比較復(fù)雜。相同形式的地址其有效地址未必相同。形式不同的地址其有效地址卻可能相同。3.4流水線的相關(guān)與沖突2、名相關(guān)名：指令所訪問的寄存器或存儲器單元的名稱。如果兩條指令使用相同的名，但是它們之間并沒有數(shù)據(jù)流動，則稱這兩條指令存在名相關(guān)。3.4流水線的相關(guān)與沖突指令j（在后）與指令i（在前）之間的名相關(guān)有兩種：（1）反相關(guān)：如果指令j寫的名與指令i讀的名相同，則稱指令i和j發(fā)生了反相關(guān)。指令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）輸出相關(guān)：如果指令j和指令i寫相同的名，則稱指令i和j發(fā)生了輸出相關(guān)。指令i寫的名＝指令j寫的名3.4流水線的相關(guān)與沖突名相關(guān)小結(jié)：名相關(guān)的兩條指令之間并沒有數(shù)據(jù)的傳送。但名相關(guān)的兩條指令之間的執(zhí)行順序必須嚴(yán)格遵守。如果一條指令中的名改變了，并不影響另外一條指令的執(zhí)行。針對名相關(guān)：可采用換名技術(shù)，消除名相關(guān)。3.4流水線的相關(guān)與沖突換名技術(shù)：通過改變指令中操作數(shù)的名來消除名相關(guān)。例如：考慮下述代碼：

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進(jìn)行寄存器換名（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)143.4流水線的相關(guān)與沖突反相關(guān)3、控制相關(guān)控制相關(guān)是指由分支指令引起的相關(guān)。典型的程序結(jié)構(gòu)是“if-then”結(jié)構(gòu)。3.4流水線的相關(guān)與沖突ifp1{ S1；

}；S；ifp2{ S2；

}；

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

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

停頓

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

設(shè)置相互獨立的指令存儲器和數(shù)據(jù)存儲器或設(shè)置相互獨立的指令Cache和數(shù)據(jù)Cache。3.4流水線的相關(guān)與沖突

說明：有時流水線設(shè)計者允許結(jié)構(gòu)沖突的存在主要原因：減少硬件成本（二）數(shù)據(jù)沖突

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

DSUBR4，R1，R5（讀R1）123456DADDIFIDEXMEM

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

i

寫入

j

讀出

如果在

i

寫入之前，j

先去讀，j

讀出的內(nèi)容是錯誤的。-對應(yīng)真數(shù)據(jù)相關(guān)。3.4流水線的相關(guān)與沖突（2）寫后寫沖突（WAW）

i

寫入

j

寫入如果在

i

寫入之前，j

先寫，最后寫入的結(jié)果是的錯誤！

-對應(yīng)輸出相關(guān)。

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

i

讀出

j

寫入如果在i

讀之前，j

先寫。i

讀出的內(nèi)容是錯誤的！-對應(yīng)反相關(guān)。

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

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

定向技術(shù)關(guān)鍵思想：在某條指令產(chǎn)生計算結(jié)果之前，其他指令并不真正立即需要該計算結(jié)果，如果能夠?qū)⒃撚嬎憬Y(jié)果從其產(chǎn)生的地方直接送到其他指令需要它的地方，那么就可以避免停頓。推廣一般的情況：

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

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

解決方法2：增加流水線互鎖硬件，插入“暫?！?。作用：檢測發(fā)現(xiàn)數(shù)據(jù)沖突，并使流水線停頓，直至沖突消失。

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

EXMEMWBSDRa，AIFstall

IDEXMEMWB3.4流水線的相關(guān)與沖突調(diào)度前的代碼調(diào)度后的代碼LDRb，BLDRc，CDADDRa，Rb，Rc

SDRa，ALDRe，ELDRf，F(xiàn)DSUBRd，Re，RfSDRd，DLDRb，BLDRc，CLDRe，EDADDRa，Rb，RcLDRf，F(xiàn)SDRa，ADSUBRd，Re，RfSDRd，D例：請為下列表達(dá)式生成沒有暫停的指令序列:

A＝B＋C；

D＝E－F；

假設(shè)載入延遲為1個時鐘周期。

（三）控制沖突1、控制沖突流水線遇到分支指令（條件轉(zhuǎn)移）和其他會改變PC值的指令所引起的沖突。分支指令的簡單處理：“凍結(jié)”，或“排空”流水線12345678分支指令I(lǐng)FIDEXMEMWB分支目標(biāo)指令i

IF

停頓停頓IFIDEXMEM分支目標(biāo)指令i+1

停頓停頓停頓IFIDEX分支目標(biāo)指令i+3

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

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

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