【正文】 1 1 0 1()0 0 1 0 1 1()( 00)2(1 =?=?= CCS H RC000)5(2 )1 0 1 1 0 1()1 0 1 1 0 1()0 0 0 0 0 1()( CCCS H RC ==?=?=對(duì) C1繼續(xù)推算新的沖突向量，因?yàn)槠渲兄挥幸粋€(gè) 0， 后續(xù)向量也只有一個(gè)。 ? 若選擇第 2條指令在 2拍后調(diào)入流水線： 0 0 1 0 1 1)( 0)2( =CS H R 1 2 3 4 5 6 7 8 S 1 S 2 S 3 S 4 ○ ○ ○ ○ ○ ○ ○ ○ ○?第一條指令的當(dāng)前禁止向量： F =（ 12, 32, 42, 62） =（ 1， 2， 4） ?則此時(shí)初始沖突向量應(yīng)該邏輯右移兩位，形成第一條指令的當(dāng)前沖突向量。為了保證后續(xù)指令的正常輸入，必須找出所有變化了的沖突向量。 ? 沖突向量用 C =（ CmCm1… C2C1 ） 表示，其中 m為禁止向量的最大值，如果執(zhí)行一條指令需要 k個(gè)時(shí)段，那末 m ≤ k – 1。 2） 由禁止向量變換成初始沖突向量 ? 用以表示非線性流水線工作時(shí)各啟動(dòng)距離特性的二進(jìn)制序列，稱為 沖突向量 。 ? 如上例中， 禁止向量 F =（ 1, 3, 4, 6） ，則對(duì)應(yīng)的 初始沖突向量 C =（ 101101） 。 ? 將這種計(jì)算所有打 “ ”時(shí)段之間距離的方法施于其他三個(gè)部件，可以得到下面的結(jié)果 : S2的禁止啟動(dòng)距離： 3Δt S3的禁止啟動(dòng)距離： Δt， 3Δt， 4Δt 禁止向量 F =（ 1, 3, 4, 6） ○ ○ ○ ○ ○ ○ 1 2 3 4 5 6 7 8 S 1 S 2 S 3 S 4 ? 向量規(guī)定，如果某啟動(dòng)距離為禁止距離，則該位為 “ 1”，反之則為 “ 0”。 S1在 1， 4， 7三個(gè)時(shí)段中使用，從第 1時(shí)段到第 4時(shí)段的距離為 3Δt（ 4Δt – 1Δt = 3Δt） ，顯然這是一個(gè)禁止啟動(dòng)距離。 1）根據(jù)預(yù)約表寫出禁止向量 ? 禁止向量 F是一個(gè)流水線中所有禁止啟動(dòng)距離的集合。 ? 將在任何時(shí)間都不會(huì)發(fā)生沖突的啟動(dòng)距離稱為 啟動(dòng)循環(huán) 。 ? 為此必須恰當(dāng)?shù)剡x擇后一條指令輸入的時(shí)間，既不使發(fā)生沖突，又不致使流水線的效率降低太多。 ? 如果所采用的啟動(dòng)距離不合適，可能會(huì)在某些部件的使用上發(fā)生沖突。 流水線的相關(guān)與沖突 （ 3）采用延遲轉(zhuǎn)移技術(shù) 方法一：從前調(diào)度 DADD R1， R2， R3 IF R2=0 THEN 延遲槽 …… IF R2=0 THEN DADD R1， R2， R3 …… 方法三：由失敗處調(diào)度 方法二：從目標(biāo)處調(diào)度 DSUB R4, R5, R6 DADD R1, R2, R3 IF R1=0 THEN 延遲槽 DSUB R4, R5, R6 DADD R1, R2, R3 IF R1=0 THEN DSUB R4, R5, R6 DADD R1, R2, R3 IF R1=0 THEN DSUB R4, R5, R6 延遲槽 DADD R1, R2, R3 IF R1=0 THEN …… DSUB R4, R5, R6 補(bǔ)充：非線性流水線的競(jìng)爭(zhēng)與調(diào)度 非線性流水線中可能發(fā)生的沖突 前饋 反饋 輸出 S4 輸入 S1 S2 S3 （ a） 帶前饋和反饋的非線性流水線連線圖 （ b） 一種假定的預(yù)約表 1 2 3 4 5 6 7 8 S 1 S 2 S 3 S 4 ? 非線性流水線中由于有些段需要在時(shí)間上復(fù)用，就不能像線性流水線那樣逐時(shí)段連續(xù)地輸入指令。 ? 起作用的前題： 先知道分支目標(biāo)地址，后知道分支是否成功。試計(jì)算執(zhí)行一條指令的平均時(shí)鐘周期數(shù)。 ? 若確定分支成功，流水線就把在分支指令之后取出的所有指令轉(zhuǎn)化為空操作，并按分支目地重新取指令執(zhí)行。 流水線的相關(guān)與沖突 為了減小分支延遲造成的損失，還可通過軟件（編譯器）來減少分支延遲，常見的有以下幾種： （ 1）預(yù)測(cè)分支失敗 ? 允許分支指令后的指令繼續(xù)在流水線中流動(dòng)，就好象什么都沒發(fā)生似的。 ? 兩種措施同時(shí)采用，缺一不可。 解：設(shè)執(zhí)行一條指令的平均時(shí)鐘周期數(shù)為 Pi，則 Pi = (1 25%) 1 + 25% (3+1) = 流水線的相關(guān)與沖突 有關(guān)措施 為了減小分支延遲造成的損失，可采用以下措施： 1）在流水線中盡早判斷出分支轉(zhuǎn)移是否成功。 ? 分 支指令的處理 1 2 3 4 5 6 7 8 BRANCH(轉(zhuǎn)移 ) IF ID EX MEM WB 指令 i+1 停頓 停頓 停頓 IF ID EX MEM 指令 i+2 停頓 停頓 停頓 IF ID EX 指令 i+3 停頓 停頓 停頓 IF ID 末尾處更新 PC值 流水線的相關(guān)與沖突 ? 轉(zhuǎn)移指令對(duì)流水線的影響 例 :設(shè)在某一程序中， 條件轉(zhuǎn)移指令在程序中所占的比例為 25%，其中轉(zhuǎn)移成功的概率為 2/3。 3） WAW（寫后寫） 原程序中如果兩條指令都要對(duì)同一單元進(jìn)行寫數(shù)操作，可能因?yàn)榉前葱驁?zhí)行的原因，改變了兩條指令寫入的次序。 l k i k j i l 指令入 出 1 2 3 4 5 讀數(shù) 寫數(shù) R i指令 :寫數(shù) j指令 :讀數(shù) 流水線的相關(guān)與沖突 ? 由于允許非按序執(zhí)行，使流水線的停頓時(shí)間大為減小，有利于提高流水線的吞吐率和效率。 時(shí)間（時(shí)鐘周期） 1 2 3 4 5 6 IM Re g ALU DM Re g IM Re g ALU DM IM Re g ALU IM Re g LD R1 ， 0 (R2 ) D A D D R4 ， R1 ， R5 A N D R6 ， R1 ， R7 X O R R8 ， R1 ， R9 氣泡 氣泡 氣泡 解決方法三 ：指令調(diào)度（流水線調(diào)度） ? 前提 ：在非按序流動(dòng)方式（亂步流動(dòng)）的流水線中。 如裝入延遲 ： LD R1， 0（ R2） DADD R4， R1， R5 AND R6， R1， R7 XOR R8， R1， R9 時(shí)間（時(shí)鐘 周期） 1 2 3 4 5 6 IM Re g ALU DM Re g IM Re g ALU DM Re g IM Re g ALU DM IM Re g ALU L D R1 ， 0 (R2 ) D A D D R4 ， R1 ， R5 A N D R6 ， R1 ， R7 X O R R8 ， R1 ， R9 解決方法二 ：增加流水線互鎖硬件，插入 “ 暫停 ” 。 指流水線中流出的結(jié)果與流入指令的次序是一致的。 如： DADD R1， R2， R3 DSUB R4， R1， R5 1 2 3 4 5 6 DADD IF ID EX MEM WB DSUB IF ID EX MEM WB 寫 R1 讀 R1 流水線的相關(guān)與沖突 解決辦法 采用定向傳送技術(shù)（旁路技術(shù)或相關(guān)專用通路技術(shù)）。 1 2 3 4 5 6 7 8 指令 LOAD IF 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 訪存沖突 流水線的相關(guān)與沖突 流水線的相關(guān)與沖突 解決方法： 暫停一拍（也稱為流水線氣泡，簡(jiǎn)稱氣泡）。 流水線的相關(guān)與沖突 三、流水線沖突 ? 流水線沖突 是指對(duì)于具體的流水線來說，由于相關(guān)的存在，使得指令流中的下一條指令不能在指定的時(shí)鐘周期執(zhí)行。 ?控制相關(guān)帶來了以下 兩個(gè)限制： ?與一條分支指令控制相關(guān)的指令不能被移到該分支之前，否則這些指令就不受該分支控制了。 流水線的相關(guān)與沖突 流水線的相關(guān)與沖突 控制相關(guān) ?控制相關(guān) 是指由分支指令引起的相關(guān)。 ? 相同形式的地址其有效地址未必相同。 例如：下面這一段代碼存在數(shù)據(jù)相關(guān) Loop： F0， 0（ R1） // F0為數(shù)組元素 F4， F0， F2 // 加上 F2中的值 0（ R1）， F4 // 保存結(jié)果 DADDIU R1， R1，－ 8 // 數(shù)組指針遞減 8個(gè)字節(jié) BNE R1， R2， Loop // 如果 R1≠R2，則分支 流水線的相關(guān)與沖突 ?當(dāng)數(shù)據(jù)的流動(dòng)是經(jīng)過寄存器時(shí)，相關(guān)的檢測(cè)比較直觀和容易。 ?數(shù)據(jù)相關(guān)具有 傳遞性。 進(jìn)行寄存器換名（ F6換成 S）后，變成： F2， F6， F4 S， F0， F12 F8， S， F14 流水線的相關(guān)與沖突 數(shù)據(jù)相關(guān) ?對(duì)于兩條指令 i（在前）和 j（在后），如果下述條件之一成立，則稱 指令 j與 指令 i數(shù)據(jù)相關(guān)。 ?解決方法 : 換名技術(shù)： 通過改變指令中操作數(shù)的名來消除名相關(guān)。 ?如果一條指令中的名改變了，并不影響另外一條指令的執(zhí)行。 指令 j寫的名＝指令 i讀的名 如： F2， F6， F4 F6， F0， F12 流水線的相關(guān)與沖突 ? 輸出相關(guān)： 如果指令 j和指令 i寫相同的名，則稱指令 i和 j發(fā)生了輸出相關(guān)。 ?如果兩條指令使用相同的名，但是它們之間并沒有數(shù)據(jù)流動(dòng)，則稱這兩條指令存在名相關(guān)。如果流入流水線的指令出現(xiàn)斷流，將極大地影響流水線的性能。 流水線的相關(guān)與沖突 ? 三類指令對(duì) 5級(jí)流水線的占用情況 : ALU指令 LOAD/STORE BRANCH IF(S1) 取指 取指 取指 ID(S2) 譯碼 ,讀寄存器堆 譯碼 ,讀寄存器堆 譯碼 ,讀寄存器堆 EX(S3) 執(zhí)行 計(jì)算有效地址 計(jì)算轉(zhuǎn)移目標(biāo)地址 ,設(shè)置條件碼 MEM(S4) 訪存 (讀或?qū)?) 若條件成立 ,將轉(zhuǎn)移目標(biāo)地址送PC WB(S