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

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

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

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

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

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

6、之間并沒有數(shù)據(jù)流動(dòng)，則稱這兩條指令存在名相關(guān)。3.4 流水線的相關(guān)與沖突流水線的相關(guān)與沖突指令j（在后）與指令i（在前）之間的名相關(guān)有兩種： （1）反相關(guān)：）反相關(guān)：如果指令如果指令j寫的名與指令寫的名與指令i讀的名相同，則讀的名相同，則稱指令稱指令i和和j發(fā)生了反相關(guān)。發(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)：輸出相關(guān)：如果指令如果指令j和指令和指令i寫相同的名，則稱寫相同的名，則稱指令指令i和和j發(fā)生了輸出相關(guān)。發(fā)生了輸出相關(guān)。 指令i寫的名 指令j寫的名3.4 流水線

7、的相關(guān)與沖突流水線的相關(guān)與沖突名相關(guān)小結(jié)：l名相關(guān)的兩條指令之間并沒有數(shù)據(jù)的傳送。l但名相關(guān)的兩條指令之間的執(zhí)行順序必須嚴(yán)格遵守。l如果一條指令中的名改變了，并不影響另外一條指令的執(zhí)行。針對名相關(guān)：可采用換名技術(shù)，消除名相關(guān)。3.4 流水線的相關(guān)與沖突流水線的相關(guān)與沖突換名技術(shù)：換名技術(shù)：通過改變指令中操作數(shù)的名來消除名相關(guān)。 例如：考慮下述代碼： 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進(jìn)行寄存器換名（進(jìn)行寄存器換名（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 流水線的相關(guān)與沖突流水線的相關(guān)與沖突反相關(guān)反相關(guān)3、控制相關(guān)、控制相關(guān)n控制相關(guān)控制相關(guān)是指由分支指令引起的相關(guān)。n典型的程序結(jié)構(gòu)是“if-then”結(jié)構(gòu)。3.4 流水線的相關(guān)與沖突流水線的相關(guān)與沖突if p1 if p1 S1 S1； ；S S；if p2 if p2 S2 S2； ； 控制相關(guān)帶來了以下兩個(gè)限制：兩個(gè)限制：l 與一條分支指令控制相關(guān)的指令不能被移到該分支之前，否則這些指令就不受該分支控制了。l 如果一條指令與某分支指令不存在控制相關(guān)，就不能把該指令移到該分支之后。三、流水線沖突三、流水線沖突流水線沖突流水線沖突是指對于具體的流水線來說，由于相關(guān)的存

9、在，使得指令流中的下一條指令不能在指定的時(shí)鐘周期執(zhí)行。n 流水線沖突有3種類型：結(jié)構(gòu)沖突結(jié)構(gòu)沖突數(shù)據(jù)沖突數(shù)據(jù)沖突控制沖突控制沖突3.4 流水線的相關(guān)與沖突流水線的相關(guān)與沖突（一）（一）結(jié)構(gòu)沖突結(jié)構(gòu)沖突 指多條指令進(jìn)入流水線后，在同一時(shí)間爭用同一功能部件，從而發(fā)生沖突。n例如：存儲(chǔ)器訪問沖突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 流水線的相關(guān)與沖突流水線的相關(guān)與

10、沖突3.4 流水線的相關(guān)與沖突流水線的相關(guān)與沖突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 流水線的相關(guān)與沖突流水線的相關(guān)與沖突 時(shí)時(shí)間間（時(shí)時(shí)鐘鐘周周期期） 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 流水線的相關(guān)與沖突流水線的相關(guān)與沖突n解決方法解決方法： 設(shè)置相互獨(dú)立的指令存儲(chǔ)器和數(shù)據(jù)存儲(chǔ)器或設(shè)置相互獨(dú)設(shè)置相互獨(dú)立的指令存儲(chǔ)器和數(shù)據(jù)存儲(chǔ)器或設(shè)置相互獨(dú)立的指令立的指令CacheCache和數(shù)據(jù)和數(shù)據(jù)CacheCache。3.4 流水線的相關(guān)與沖突流水線的相關(guān)與沖突u 說明：有時(shí)流水線設(shè)計(jì)者允許結(jié)構(gòu)沖突的存在 主要原因：主要原因：減少硬件成本減少硬件成本（二）（二）數(shù)據(jù)沖突數(shù)據(jù)沖突 1、數(shù)據(jù)沖突、數(shù)據(jù)沖突指由于流水線中各指

12、令重疊執(zhí)行，使得原來對操作數(shù)的訪問順序發(fā)生變化，從而引起的一種數(shù)據(jù)沖突。 例如：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 流水線的相關(guān)與沖突流水線的相關(guān)與沖突n根據(jù)指令讀訪問和寫訪問的順序，根據(jù)指令讀訪問和寫訪問的順序，假設(shè)兩條指令假設(shè)兩條指令i i和和j j，且且i i在在j j之前進(jìn)入流水線，可能發(fā)生的數(shù)據(jù)沖突有之前進(jìn)入流水線，可能發(fā)生的數(shù)據(jù)沖突有3 3種類種類型型：（1 1）寫后讀沖突（）寫后讀沖突（RAWRAW） i i 寫入寫

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

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

15、讀后寫沖突在前述5 5段流水線中不會(huì)發(fā)生。段流水線中不會(huì)發(fā)生。（讀操作（在（讀操作（在IDID段）在寫結(jié)果操作（在段）在寫結(jié)果操作（在WBWB段）之前）段）之前）3.4 流水線的相關(guān)與沖突流水線的相關(guān)與沖突2、解決辦法：、解決辦法：- 針對針對“寫后讀沖突寫后讀沖突” 解決辦法1：采用定向傳送技術(shù)定向傳送技術(shù)（旁路技術(shù)或相關(guān)專用通路技術(shù)）。3.4 流水線的相關(guān)與沖突流水線的相關(guān)與沖突例： DADD R1，R2，R3 DSUB R4，R1，R5 XOR R6，R1，R7 AND R8，R1，R9 OR R10，R1，R11 時(shí)間（時(shí)鐘周期） 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流水線的數(shù)據(jù)沖突舉例 產(chǎn)生數(shù)產(chǎn)生數(shù)據(jù)據(jù)ALU目標(biāo)目標(biāo)R旁路傳送旁路傳送寄存器寄存器 時(shí)間（時(shí)鐘周期） 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 流水線的相關(guān)與沖突流水線的相關(guān)與沖突采用定向技術(shù)后的流水線數(shù)據(jù)通路 n定向技術(shù)定向技術(shù)關(guān)鍵思想：關(guān)鍵思想： 在某條指令產(chǎn)生計(jì)算結(jié)果之前，其他指令并不真正立在某條指令產(chǎn)生計(jì)算結(jié)果之前，其他指令并不真正立即需要該計(jì)算結(jié)果，如果能夠?qū)⒃撚?jì)算結(jié)果即需要該計(jì)算結(jié)果，如果能夠?qū)⒃撚?jì)算結(jié)果從其產(chǎn)生的地從其產(chǎn)生的地方方直接送到其他指令直接送到其他指令需要它的地方需要它的地方，那么就可以避免停頓。，那么就可以避免停頓。n推廣一般的情況：推廣一般的情況： 結(jié)果數(shù)據(jù)不僅可以從某一功能部件的輸出定向到其自身的輸入，而且還可以定向到其他功能部件的輸入。

18、3.4 流水線的相關(guān)與沖突流水線的相關(guān)與沖突 時(shí)間（時(shí)鐘周期） 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 流水線的相關(guān)與沖突流水線的相關(guān)與沖突DSUB DSUB R1R1，R2R2，R3R3LD LD R5R5，0 0（R1R1）SD SD R5R5，1212（R1R1）但是，定向技術(shù)并不能解決所有但是，定向技術(shù)并不能解決所有RAW沖突。沖突。例如： LD R1，0（R2） DADD R4，R1，R5 AND R6，R1，R

19、7 XOR R8，R1，R9 時(shí)間（時(shí)鐘周期） 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指令的結(jié)果定指令的結(jié)果定向到向到DADD指令指令 解決方法解決方法2：增加流水線互鎖互鎖硬件，插入“暫?！?。作用：檢測發(fā)現(xiàn)數(shù)據(jù)沖突，并使流水線停頓，直至沖突消失。 時(shí)間（時(shí)鐘周期） 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：指令調(diào)度技術(shù)（流水線調(diào)度）n前提：在非按序流動(dòng)方式（亂步流動(dòng)）的流水線中。n實(shí)現(xiàn)：通過編譯器重新組織指令順序來消除沖突。指允許輸出結(jié)果的次序指允許輸出結(jié)果的次序與輸入指令的次序不同。與輸入指令的次序不同。例如：例如：表達(dá)式表達(dá)式 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 流水線的相關(guān)與沖突流水線的相關(guān)與沖突調(diào)度前的代碼 調(diào)度后的代碼 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 例：例：請為下列表達(dá)式生成沒有暫停的指令序列請為下列表達(dá)式生成沒有暫停的指令

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

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

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