第5章標(biāo)量處理機(jī)(5.4,5.5,5.6)流水線的沖突MIPS流水線

5.4流水線的相關(guān)與沖突5.4.1一條經(jīng)典的5段流水線5.4.2相關(guān)與流水線的沖突介紹一條經(jīng)典的5段RISC流水線

首先討論在非流水情況下是如何實(shí)現(xiàn)的一條指令的執(zhí)行過(guò)程分為以下5個(gè)周期：取指令周期（IF）以程序計(jì)數(shù)器PC中的內(nèi)容作為地址，從存儲(chǔ)器中取出指令并放入指令寄存器IR；同時(shí)PC值加4（假設(shè)每條指令占4個(gè)字節(jié)），指向順序的下一條指令。

5.4流水線的相關(guān)與沖突5.4.1一條經(jīng)典的5段流水線指令譯碼/讀寄存器周期（ID）對(duì)指令進(jìn)行譯碼，并讀出寄存器的內(nèi)容。用IR中的寄存器地址去訪問(wèn)通用寄存器組，讀出所需的操作數(shù)。由于指令的立即數(shù)部分也保存在相同的位置，需要擴(kuò)展立即數(shù)的操作也在本段完成。

執(zhí)行/有效地址計(jì)算周期（EX）不同指令所進(jìn)行的操作不同：load和store指令：ALU把指令中所指定的寄存器的內(nèi)容與偏移量相加，形成訪存有效地址。寄存器－寄存器ALU指令：ALU按照操作碼指定的操作對(duì)從通用寄存器組中讀出的數(shù)據(jù)進(jìn)行運(yùn)算。寄存器－立即數(shù)ALU指令：ALU按照操作碼指定的操作對(duì)從通用寄存器組中讀出的操作數(shù)和指令中給出的立即數(shù)進(jìn)行運(yùn)算。分支指令：ALU把指令中給出的偏移量與PC值相加，形成轉(zhuǎn)移目標(biāo)的地址。同時(shí)，對(duì)在前一個(gè)周期讀出的操作數(shù)進(jìn)行判斷，確定分支是否成功。存儲(chǔ)器訪問(wèn)／分支完成周期（MEM）該周期處理的指令只有l(wèi)oad、store和分支指令。其它類型的指令在此周期不做任何操作。load和store指令load指令：用上一個(gè)周期計(jì)算出的有效地址從存儲(chǔ)器中讀出相應(yīng)的數(shù)據(jù)；store指令：把指定的數(shù)據(jù)寫(xiě)入這個(gè)有效地址所指出的存儲(chǔ)器單元。分支指令分支“成功”，就把轉(zhuǎn)移目標(biāo)地址送入PC。分支指令執(zhí)行完成。寫(xiě)回周期（WB）

ALU運(yùn)算指令和load指令在這個(gè)周期把結(jié)果數(shù)據(jù)寫(xiě)入通用寄存器組。

ALU運(yùn)算指令：結(jié)果數(shù)據(jù)來(lái)自ALU。

load指令：結(jié)果數(shù)據(jù)來(lái)自存儲(chǔ)器。在這個(gè)實(shí)現(xiàn)方案中：分支指令需要4個(gè)時(shí)鐘周期（如果把分支指令的執(zhí)行提前到ID周期，則只需要2個(gè)周期）；store指令需要4個(gè)周期；其它指令需要5個(gè)周期才能完成。在更先進(jìn)的實(shí)現(xiàn)中，在ID段完成對(duì)寄存器的內(nèi)容進(jìn)行比較，判斷是否為轉(zhuǎn)移指令，若為真，將PC與帶符號(hào)的位移量相加，生成的轉(zhuǎn)移目標(biāo)地址寫(xiě)人PC，在ID段完成對(duì)轉(zhuǎn)移的處理。將上述實(shí)現(xiàn)方案修改為流水線實(shí)現(xiàn)一條經(jīng)典的5段流水線

每一個(gè)周期作為一個(gè)流水段；在各段之間加上鎖存器（流水寄存器）。流水寄存器保證了流水線中不同段的指令不會(huì)相互影響。每個(gè)時(shí)鐘周期結(jié)束之后，該段的所有執(zhí)行結(jié)果都保存在流水段寄存器中，在下一個(gè)時(shí)鐘周期開(kāi)始作為下一個(gè)段的輸入。

第一種描述（類似于時(shí)空?qǐng)D）

5段流水線的兩種描述方式流水線的實(shí)現(xiàn)必須關(guān)注：需要確定處理器在每一個(gè)時(shí)鐘周期都進(jìn)行什么樣的動(dòng)作。要保證在同一個(gè)周期沒(méi)有兩條指令使用相同的數(shù)據(jù)通路資源?？梢圆捎昧魉€方式下簡(jiǎn)化的RISC數(shù)據(jù)通路圖來(lái)表示：第二種描述（按時(shí)間錯(cuò)開(kāi)的數(shù)據(jù)通路序列）

采用流水線方式實(shí)現(xiàn)時(shí)，應(yīng)解決好以下幾個(gè)問(wèn)題：要保證不會(huì)在同一時(shí)鐘周期要求同一個(gè)功能段做兩件不同的工作。例如：不能要求ALU同時(shí)做有效地址計(jì)算和算術(shù)運(yùn)算。避免IF段的訪存（取指令）與MEM段的訪存（讀/寫(xiě)數(shù)據(jù)）發(fā)生沖突?？梢圆捎梅蛛x的指令存儲(chǔ)器和數(shù)據(jù)存儲(chǔ)器；一般采用分離的指令Cache和數(shù)據(jù)Cache。ID段和WB段都要訪問(wèn)同一寄存器文件。

ID段：讀WB段：寫(xiě)寄存器堆在ID段被讀，在WE段被寫(xiě)，所以在數(shù)據(jù)通路中出現(xiàn)兩次對(duì)于在一個(gè)時(shí)鐘周期內(nèi)同一寄存器堆進(jìn)行操作，在時(shí)鐘的前半部分進(jìn)行寫(xiě)寄存器的操作，后半部分進(jìn)行讀寄存器的操作。如何解決對(duì)同一寄存器的訪問(wèn)沖突？把寫(xiě)操作安排在時(shí)鐘周期的前半拍完成，把讀操作安排在后半拍完成。邊框畫(huà)實(shí)線表示操作，畫(huà)虛線表示不做任何操作?？紤]PC的問(wèn)題流水線為了能夠每個(gè)時(shí)鐘周期啟動(dòng)一條新的指令，就必須在每個(gè)時(shí)鐘周期進(jìn)行PC值的加4操作，并保留新的PC值。這種操作必須在IF段完成，以便為取下一條指令做好準(zhǔn)備。

（需設(shè)置一個(gè)專門(mén)的加法器）但分支指令也可能改變PC的值，而且是在MEM段進(jìn)行，這會(huì)導(dǎo)致沖突。請(qǐng)考慮一下，如何處理分支指令？相關(guān)：兩條指令之間存在某種依賴關(guān)系。如果兩條指令相關(guān)，則它們就有可能不能在流水線中重疊執(zhí)行或者只能部分重疊執(zhí)行。5.4.2.1相關(guān)與流水線沖突5.4.2相關(guān)與流水線沖突

流水線沖突是指對(duì)于具體的流水線來(lái)說(shuō)，由于相關(guān)的存在，使得指令流中的下一條指令不能在指定的時(shí)鐘周期執(zhí)行。流水線沖突有3種類型：結(jié)構(gòu)沖突：因硬件資源滿足不了指令重疊執(zhí)行的要求而發(fā)生的沖突。數(shù)據(jù)沖突：當(dāng)指令在流水線中重疊執(zhí)行時(shí)，因需要用到前面指令的執(zhí)行結(jié)果而發(fā)生的沖突?？刂茮_突：流水線遇到分支指令和其它會(huì)改變PC值的指令所引起的沖突。流水線沖突導(dǎo)致錯(cuò)誤的執(zhí)行結(jié)果。流水線可能會(huì)出現(xiàn)停頓，從而降低流水線的效率和實(shí)際的加速比。我們約定當(dāng)一條指令被暫停時(shí)，在該暫停指令之后流出的所有指令都要被暫停，而在該暫停指令之前流出的指令則繼續(xù)進(jìn)行（否則就永遠(yuǎn)無(wú)法消除沖突）。帶來(lái)的幾個(gè)問(wèn)題：在流水線處理機(jī)中，為了能夠使各種組合的指令都能順利地重疊執(zhí)行，需要對(duì)功能部件進(jìn)行流水或重復(fù)設(shè)置資源。如果某種指令組合因?yàn)橘Y源沖突而不能正常執(zhí)行，則稱該處理機(jī)有結(jié)構(gòu)沖突。常見(jiàn)的導(dǎo)致結(jié)構(gòu)沖突的原因：功能部件不是完全流水資源份數(shù)不夠結(jié)構(gòu)沖突結(jié)構(gòu)沖突舉例：訪存沖突

有些流水線處理機(jī)只有一個(gè)存儲(chǔ)器，將數(shù)據(jù)和指令放在一起，訪存指令會(huì)導(dǎo)致訪存沖突。解決辦法Ⅰ：插入暫停周期（“流水線氣泡”或“氣泡”）引入暫停后的時(shí)空?qǐng)D解決方法Ⅱ：

設(shè)置相互獨(dú)立的指令存儲(chǔ)器和數(shù)據(jù)存儲(chǔ)器或設(shè)置相互獨(dú)立的指令Cache和數(shù)據(jù)Cache。由于訪問(wèn)同一個(gè)存儲(chǔ)器而引起的結(jié)構(gòu)沖突

訪存沖突返回為消除結(jié)構(gòu)沖突而插入的流水線氣泡引入暫停后的時(shí)空?qǐng)D指令編號(hào)時(shí)鐘周期12345678910指令iIFIDEXMEMWB指令i+1IFIDEXMEMWB指令i+2IFIDEXMEMWB指令i+3stall

IFIDEXMEMWB指令i+4IFIDEXMEMWB指令i+5IFIDEXMEM有時(shí)流水線設(shè)計(jì)者允許結(jié)構(gòu)沖突的存在主要原因：減少硬件成本如果把流水線中的所有功能單元完全流水化，或者重復(fù)設(shè)置足夠份數(shù)，那么所花費(fèi)的成本將相當(dāng)高。

數(shù)據(jù)沖突當(dāng)相關(guān)的指令靠得足夠近時(shí)，它們?cè)诹魉€中的重疊執(zhí)行或者重新排序會(huì)改變指令讀/寫(xiě)操作數(shù)的順序，使之不同于它們串行執(zhí)行時(shí)的順序，則發(fā)生了數(shù)據(jù)沖突。

舉例：

DADDR1，R2，R3DSUBR4，R1，R5XORR6，R1，R7ANDR8，R1，R9ORR10，R1，R11流水線的數(shù)據(jù)沖突舉例ADD在WB段寫(xiě)R1，SUB則在ID段讀R1，產(chǎn)生了數(shù)據(jù)相關(guān)。XOR也受到數(shù)據(jù)相關(guān)的影響AND操作由于前半個(gè)周期寫(xiě)寄存器對(duì)，后半個(gè)周期讀寄存器堆，可以正確執(zhí)行。OR操作也能正確執(zhí)行，此時(shí)R1的值已經(jīng)被正確寫(xiě)人根據(jù)指令讀訪問(wèn)和寫(xiě)訪問(wèn)的順序，可以將數(shù)據(jù)沖突分為3種類型?？紤]兩條指令i和j

，且i在j之前進(jìn)入流水線，可能發(fā)生的數(shù)據(jù)沖突有：寫(xiě)后讀沖突（RAW）在

i

寫(xiě)入之前，j

先去讀。

j讀出的內(nèi)容是錯(cuò)誤的。這是最常見(jiàn)的一種數(shù)據(jù)沖突，它對(duì)應(yīng)于真數(shù)據(jù)相關(guān)。數(shù)據(jù)沖突的三種類型寫(xiě)后寫(xiě)沖突（WAW）在

i

寫(xiě)入之前，j

先寫(xiě)。最后寫(xiě)入的結(jié)果是

i

的。錯(cuò)誤！這種沖突對(duì)應(yīng)于輸出相關(guān)。寫(xiě)后寫(xiě)沖突僅發(fā)生在這樣的流水線中：流水線中不只一個(gè)段可以進(jìn)行寫(xiě)操作；指令被重新排序了。前面介紹的5段流水線不會(huì)發(fā)生寫(xiě)后寫(xiě)沖突。（只在WB段寫(xiě)寄存器）讀后寫(xiě)沖突（WAR）在i

讀之前，j

先寫(xiě)。

i

讀出的內(nèi)容是錯(cuò)誤的！由反相關(guān)引起。這種沖突僅發(fā)生在這樣的情況下：有些指令的寫(xiě)結(jié)果操作提前了，而且有些指令的讀操作滯后了；指令被重新排序了。

通過(guò)定向技術(shù)減少數(shù)據(jù)沖突引起的停頓（定向技術(shù)也稱為旁路或短路）關(guān)鍵思想：在計(jì)算結(jié)果尚未出來(lái)之前，后面等待使用該結(jié)果的指令并不真正立即需要該計(jì)算結(jié)果，如果能夠?qū)⒃撚?jì)算結(jié)果從其產(chǎn)生的地方直接送到其它指令需要它的地方，那么就可以避免停頓。采用定向技術(shù)消除上例中的相關(guān)

DSUB操作是在DADD操作產(chǎn)生了結(jié)果之后才使用該結(jié)果的，考慮將DADD的結(jié)果從EX/MEM寄存器移到DSUB需要的地方，也就是ALU的輸入鎖存器，則不需要引入停頓。采用定向技術(shù)后的流水線數(shù)據(jù)通路

工作過(guò)程演示定向的實(shí)現(xiàn)EX段和MEM段之間的流水寄存器中保存的ALU運(yùn)算結(jié)果總是回送到ALU的入口。當(dāng)定向硬件檢測(cè)到前一個(gè)ALU運(yùn)算結(jié)果寫(xiě)入的寄存器就是當(dāng)前ALU操作的源寄存器時(shí)，那么控制邏輯就選擇定向的數(shù)據(jù)作為ALU的輸入，而不采用從通用寄存器組讀出的數(shù)據(jù)。在使用直通時(shí)，如果DSUB操作被停頓，那么DADD操作將被完整執(zhí)行，沒(méi)有必要激活旁路。當(dāng)兩個(gè)操作之間有一個(gè)中斷也是如此。直通的實(shí)現(xiàn)直通思想可以一般化：可以將結(jié)果直接送到需要它的單元，并不限制在同一個(gè)單元的輸出到輸入。并不是所有的數(shù)據(jù)沖突都可以用定向技術(shù)來(lái)解決。

舉例:LDR1，0（R2）DADDR4，R1，R5ANDR6，R1，R7XORR8，R1，R9增加流水線互鎖機(jī)制，插入“暫?！薄Ｗ饔茫簷z測(cè)發(fā)現(xiàn)數(shù)據(jù)沖突，并使流水線停頓，直至沖突消失。

舉例：演示A（資源圖表示）

演示B（時(shí)空?qǐng)D表示）需要停頓的數(shù)據(jù)沖突無(wú)法將LD指令的結(jié)果定向到DADD指令

采用定向無(wú)法解決返回依靠編譯器解決數(shù)據(jù)沖突

讓編譯器重新組織指令順序來(lái)消除沖突，這種技術(shù)稱為指令調(diào)度或流水線調(diào)度。調(diào)度前的代碼調(diào)度后的代碼LDRb，BLDRc，CDADDRa，Rb，RcSDRa，ALDRe，ELDRf，F(xiàn)DSUBRd，Re，RfSDRd，DLDRb，BLDRc，CLDRe，EDADDRa，Rb，RcLDRf，F(xiàn)SDRa，ADSUBRd，Re，RfSDRd，D舉例：

請(qǐng)為下列表達(dá)式生成沒(méi)有暫停的指令序列:

A＝B＋C；

D＝E－F；

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

題解控制沖突執(zhí)行分支指令的結(jié)果有兩種分支成功：PC值改變?yōu)榉种мD(zhuǎn)移的目標(biāo)地址。在條件判定和轉(zhuǎn)移地址計(jì)算都完成后，才改變PC值。不成功或者失?。篜C的值保持正常遞增，指向順序的下一條指令。處理分支指令最簡(jiǎn)單的方法：“凍結(jié)”或者“排空”流水線

優(yōu)點(diǎn)：簡(jiǎn)單前述5段流水線中，改變PC值是在MEM段進(jìn)行的。給流水線帶來(lái)了3個(gè)時(shí)鐘周期的延遲控制沖突分支指令I(lǐng)FIDEXMEMWB

分支目標(biāo)指令I(lǐng)F

stall

stall

IF

IDEXMEMWB分支目標(biāo)指令+1IFIDEXMEM

WB分支目標(biāo)指令+2IFIDEXMEM

分支目標(biāo)指令+3IFIDEX簡(jiǎn)單處理分支指令：分支成功的情況

把由分支指令引起的延遲稱為分支延遲。分支指令在目標(biāo)代碼中出現(xiàn)的頻度每3～4條指令就有一條是分支指令。假設(shè)：分支指令出現(xiàn)的頻度是30％

流水線理想CPI＝1

那么：流水線的實(shí)際CPI＝1.9可采取兩種措施來(lái)減少分支延遲。在流水線中盡早判斷出分支轉(zhuǎn)移是否成功；盡早計(jì)算出分支目標(biāo)地址。下面的討論中，我們假設(shè)：

這兩步工作被提前到ID段完成，即分支指令是在ID段的末尾執(zhí)行完成，所帶來(lái)的分支延遲為一個(gè)時(shí)鐘周期。3種通過(guò)軟件（編譯器）來(lái)減少分支延遲的方法

共同點(diǎn)：對(duì)分支的處理方法在程序的執(zhí)行過(guò)程中始終是不變的，是靜態(tài)的。（在整個(gè)程序的執(zhí)行過(guò)程中對(duì)每個(gè)轉(zhuǎn)移的處理都是一樣的）要么總是預(yù)測(cè)分支成功，要么總是預(yù)測(cè)分支失敗。預(yù)測(cè)分支失敗

允許分支指令后的指令繼續(xù)在流水線中流動(dòng)，就好象什么都沒(méi)發(fā)生似的；若確定分支失敗，將分支指令看作是一條普通指令，流水線正常流動(dòng)；若確定分支成功，流水線就把在分支指令之后取出的所有指令轉(zhuǎn)化為空操作，并按分支目地重新取指令執(zhí)行。要保證：分支結(jié)果出來(lái)之前不能改變處理機(jī)的狀態(tài)，以便一旦猜錯(cuò)時(shí)，處理機(jī)能夠回退到原先的狀態(tài)。流水線的處理過(guò)程轉(zhuǎn)移不成功和轉(zhuǎn)移成功兩種情況下的流水線序列預(yù)測(cè)分支成功：假設(shè)分支轉(zhuǎn)移成功，并從分支目標(biāo)地址處取指令執(zhí)行。起作用的前題：先知道分支目標(biāo)地址，后知道分支是否成功。前述5段流水線中，這種方法沒(méi)有任何好處。無(wú)論采用預(yù)測(cè)不成功還是預(yù)測(cè)成功，編譯器都能通過(guò)組織代碼來(lái)實(shí)現(xiàn)與硬件的最佳匹配。不論采用剛才說(shuō)的哪種策略，編譯器都能通過(guò)組織代碼來(lái)實(shí)現(xiàn)與硬件的最佳匹配。延遲分支主要思想：從邏輯上“延長(zhǎng)”分支指令的執(zhí)行時(shí)間。把延遲分支看成是由原來(lái)的分支指令和若干個(gè)延遲槽構(gòu)成，不管分支是否成功，都要按順序執(zhí)行延遲槽中的指令。有些處理器中也稱為延遲轉(zhuǎn)移，在早期的RISC處理器中被廣泛使用。在被延遲的轉(zhuǎn)移中，轉(zhuǎn)移延遲為1的執(zhí)行周期如下：轉(zhuǎn)移指令后續(xù)指令1（放在延遲槽內(nèi)）目標(biāo)地址的指令（如果轉(zhuǎn)移被選中）執(zhí)行過(guò)程雖然延遲槽的長(zhǎng)度可以大于1，實(shí)際上，所有帶轉(zhuǎn)移延遲的處理器一般只延遲一條指令，并使用其它技術(shù)來(lái)處理更多有關(guān)延遲的開(kāi)銷任務(wù)：在延遲槽中放入有用的指令由編譯器完成。能否帶來(lái)好處取決于編譯器能否把有用的指令調(diào)度到延遲槽中。三種調(diào)度方法：解決究竟將什么指令裝入延遲槽？從前調(diào)度（將轉(zhuǎn)移指令之前的指令裝入延遲槽）從目標(biāo)處調(diào)度（將轉(zhuǎn)移目標(biāo)地址處的指令裝入延遲槽）從失敗處調(diào)度（將延遲槽后的指令裝入延遲槽）分支延遲指令的調(diào)度從前面調(diào)度來(lái)自前面：將分支指令之前的一條獨(dú)立指令調(diào)度到延遲槽具有一個(gè)分支延遲槽的流水線的執(zhí)行過(guò)程分支失敗分支指令iIFIDEXMEMWB延遲槽指令I(lǐng)FIDEXMEMWB指令i+1IFIDEXMEMWB指令i+2IFIDEXMEMWB指令i+3IFIDEXMEMWB分支延遲槽中的指令“掩蓋”了流水線原來(lái)必需插入的暫停周期。分支成功

分支指令iIFIDEXMEMWB

延遲槽指令I(lǐng)FIDEXMEMWB分支目標(biāo)指令jIFIDEXMEMWB分支目標(biāo)指令j+1IFIDEXMEMWB分支目標(biāo)指令j+2IFIDEXMEMWB從目標(biāo)處調(diào)度來(lái)自目標(biāo)地址：將目標(biāo)處的指令拷貝到延遲槽同時(shí)修改分支指令的目標(biāo)地址。由于從別的路徑可能也要執(zhí)行到該指令，所以不能簡(jiǎn)單的移指令，而是復(fù)制。采用這種方法實(shí)際上是猜測(cè)分支成功，所以對(duì)于循環(huán)等分支轉(zhuǎn)移成功概率較高的采用此方法較好分支不跳轉(zhuǎn)分支指令iIFIDEXMEMWB延遲槽指令I(lǐng)Fidle

idleidleidle指令i+1IFIDEXMEMWB指令i+2IFIDEXMEMWB指令i+3IFIDEXMEMWB分支跳轉(zhuǎn)分支指令iIFIDEXMEMWB

延遲槽指令

IFIDEXMEMWB分支目標(biāo)指令j+1IFIDEXMEMWB分支目標(biāo)指令jj+2IFIDEXMEMWB分支目標(biāo)指令j+3IFIDEXMEMWB預(yù)測(cè)分支成功的情況下，分支取消機(jī)制的執(zhí)行情況從失敗處調(diào)度將延遲槽后的指令裝入延遲槽。分支不跳轉(zhuǎn)分支指令iIFIDEXMEMWB延遲槽指令i+1

IFIDEXMEMWB指令i+2IFIDEXMEMWB指令i+3IFIDEXMEMWB指令i+4IFIDEXMEMWB分支跳轉(zhuǎn)分支指令iIFIDEXMEMWB

延遲槽指令i+1

IFidle

idleidleidle分支目標(biāo)指令jIFIDEXMEMWB分支目標(biāo)指令j+1IFIDEXMEMWB分支目標(biāo)指令j+2IFIDEXMEMWB預(yù)測(cè)分支不轉(zhuǎn)移的情況下，分支取消機(jī)制的執(zhí)行情況從失敗處調(diào)度調(diào)度前和調(diào)度后的代碼三種方法的要求及效果調(diào)度策略對(duì)調(diào)度的要求什么情況下起作用？從前調(diào)度從目標(biāo)處調(diào)度從失敗處調(diào)度必須保證在分支失敗時(shí)執(zhí)行被調(diào)度

的指令不會(huì)導(dǎo)致錯(cuò)誤。有可能需要

復(fù)制指令。被調(diào)度的指令必須與分支無(wú)關(guān)必須保證在分支成功時(shí)執(zhí)行被調(diào)度

的指令不會(huì)導(dǎo)致錯(cuò)誤。任何情況

分支成功時(shí)(但由于復(fù)制指令，有

可能會(huì)增大程序空間) 分支失敗時(shí)分支延遲受到兩個(gè)方面的限制：可以被放入延遲槽中的指令要滿足一定的條件；編譯器預(yù)測(cè)分支轉(zhuǎn)移方向的能力。進(jìn)一步改進(jìn)：分支取消機(jī)制（取消分支）當(dāng)分支的實(shí)際執(zhí)行方向和事先所預(yù)測(cè)的一樣時(shí)，執(zhí)行分支延遲槽中的指令，否則就將分支延遲槽中的指令轉(zhuǎn)化成一個(gè)空操作。此時(shí)，轉(zhuǎn)移指令帶有對(duì)轉(zhuǎn)移能否被選中的預(yù)測(cè)。預(yù)測(cè)準(zhǔn)確時(shí)，延遲槽中的指令像通常一樣執(zhí)行，否則就將延遲槽中的指令變成空操作。5.5流水線的實(shí)現(xiàn)5.5.1MIPS的一種簡(jiǎn)單實(shí)現(xiàn)5.5.2基本的MIPS流水線實(shí)現(xiàn)MIPS指令子集的一種簡(jiǎn)單數(shù)據(jù)通路。該數(shù)據(jù)通路的操作分成5個(gè)時(shí)鐘周期取指令指令譯碼/讀寄存器執(zhí)行/有效地址計(jì)算存儲(chǔ)器訪問(wèn)/分支完成寫(xiě)回只討論整數(shù)指令的實(shí)現(xiàn)（包括：load和store，等于0轉(zhuǎn)移，整數(shù)ALU指令等。）

5.5.1MIPS的一種簡(jiǎn)單實(shí)現(xiàn)5.5流水線的實(shí)現(xiàn)設(shè)置了一些臨時(shí)寄存器。其作用如下：PC：程序計(jì)數(shù)器，存放當(dāng)前指令的地址。NPC：下一條程序計(jì)數(shù)器，存放下一條指令的地址。IR：指令寄存器，存放當(dāng)前正在處理的指令。A：第一操作數(shù)寄存器，存放從通用寄存器組讀出來(lái)的操作數(shù)。B：第二操作數(shù)寄存器，存放從通用寄存器組讀出來(lái)的另一個(gè)操作數(shù)。Imm：存放符號(hào)擴(kuò)展后的立即數(shù)操作數(shù)。Cond：存放條件判定的結(jié)果。為“真”表示分支成功。ALUo：存放ALU的運(yùn)算結(jié)果。LMD：存放load指令從存儲(chǔ)器讀出的數(shù)據(jù)。臨時(shí)寄存器的作用MIPS指令系統(tǒng)結(jié)構(gòu)尋址方式編碼到操作碼中所有的指令都是32位的操作碼占6位3種指令格式

3種格式中，同名字段的位置固定不變。MIPS的指令格式MIPS指令系統(tǒng)結(jié)構(gòu)I類指令包括所有的load和store指令，立即數(shù)指令，分支指令，寄存器跳轉(zhuǎn)指令，寄存器鏈接跳轉(zhuǎn)指令。立即數(shù)字段為16位，用于提供立即數(shù)或偏移量。MIPS指令系統(tǒng)結(jié)構(gòu)load指令訪存有效地址：Regs[rs]＋immediate

從存儲(chǔ)器取來(lái)的數(shù)據(jù)放入寄存器rtstore指令訪存有效地址：Regs[rs]＋immediate

要存入存儲(chǔ)器的數(shù)據(jù)放在寄存器rt中立即數(shù)指令

Regs[rt]←Regs[rs]opimmediate分支指令轉(zhuǎn)移目標(biāo)地址(PC)＋immediate寄存器跳轉(zhuǎn)、寄存器跳轉(zhuǎn)并鏈接轉(zhuǎn)移目標(biāo)地址為Regs[rs]MIPS指令系統(tǒng)結(jié)構(gòu)R類指令包括ALU指令，專用寄存器讀/寫(xiě)指令，move指令等。ALU指令

Regs[rd]←Regs[rs]functRegs[rt]funct為具體的運(yùn)算操作編碼MIPS指令系統(tǒng)結(jié)構(gòu)J類指令包括跳轉(zhuǎn)指令，跳轉(zhuǎn)并鏈接指令，自陷指令，異常返回指令。在這類指令中，指令字的低26位是偏移量，它與PC值相加形成跳轉(zhuǎn)的地址。一條MIPS指令最多需要以下5個(gè)時(shí)鐘周期：取指令周期（IF）

操作IR←Mem[PC]NPC←PC+4指令譯碼/讀寄存器周期（ID）

操作A←

Regs[rs]B←

Regs[rt]Imm←

IR的立即數(shù)字段進(jìn)行符號(hào)擴(kuò)展

指令的譯碼操作和讀寄存器操作是并行進(jìn)行的。原因：在MIPS指令格式中，操作碼字段以及rs、rt

字段都是在固定的位置。這種技術(shù)稱為固定字段譯碼技術(shù)。

由于指令的立即數(shù)部分在MIPS格式中都有相同的位置，所以要是下一個(gè)時(shí)鐘周期需要使用立即數(shù)，帶符號(hào)立即數(shù)的符號(hào)擴(kuò)展操作也在當(dāng)前時(shí)鐘周期完成。執(zhí)行/有效地址計(jì)算周期（EX）不同指令所進(jìn)行的操作不同：load指令和store指令操作

ALUo←A+Imm寄存器－寄存器ALU指令操作

ALUo←AfunctB寄存器－立即值A(chǔ)LU指令操作

ALUo←AopImm分支指令操作

ALUo←NPC+（Imm<<2）；

cond←（A==0）

將有效地址計(jì)算周期和執(zhí)行周期合并為一個(gè)時(shí)鐘周期，這是因?yàn)镸IPS指令集采用load／store結(jié)構(gòu)，沒(méi)有任何指令需要同時(shí)進(jìn)行數(shù)據(jù)有效地址的計(jì)算、轉(zhuǎn)移目標(biāo)地址的計(jì)算和對(duì)數(shù)據(jù)進(jìn)行運(yùn)算。存儲(chǔ)器訪問(wèn)/分支完成周期（MEM）所有指令都要在該周期對(duì)PC進(jìn)行更新。除了分支指令，其它指令都是做：PC←NPC在該周期內(nèi)處理的MIPS指令僅僅有l(wèi)oad、store和分支三種指令。load指令和store指令操作LMD←Mem[ALUo]或者M(jìn)em[ALUo]←B分支指令操作

if（cond）PC←ALUoelsePC←NPC寫(xiě)回周期（WB）不同的指令在寫(xiě)回周期完成的工作也不一樣。寄存器－寄存器ALU指令操作

Regs[rd]←ALUo寄存器－立即數(shù)ALU指令操作

Regs[rt]←ALUoload指令操作

Regs[rt]←LMDMIPS的數(shù)據(jù)通路的實(shí)現(xiàn)每一個(gè)時(shí)鐘周期完成的工作看作是流水線的一段，每個(gè)時(shí)鐘周期啟動(dòng)一條新的指令，就可以使前面的數(shù)據(jù)通路流水。流水實(shí)現(xiàn)的數(shù)據(jù)通路設(shè)置了流水寄存器

所有用于在同一條指令的各個(gè)時(shí)鐘周期之間保存臨時(shí)數(shù)據(jù)的寄存器都要?dú)w入流水寄存器這一類中段與段之間設(shè)置流水寄存器流水寄存器的名稱用其相鄰的兩個(gè)段的名稱拼合而成。例如：ID段與EX段之間的流水寄存器用ID/EX表示每個(gè)流水寄存器是由若干個(gè)寄存器構(gòu)成的5.5.2基本的MIPS流水線流水實(shí)現(xiàn)的數(shù)據(jù)通路寄存器的命名形式為：x.y所包含的字段的命名形式為：x.y[s]

其中：x：流水寄存器名稱

y：具體寄存器名稱

s：字段名稱例如：

ID/EX.IR：流水寄存器ID/EX中的子寄存器IRIRID/EX.IR[op]：該寄存器的op字段（即操作碼字段）流水寄存器的作用

將各段的工作隔開(kāi)，使得它們不會(huì)互相干擾。保存相應(yīng)段的處理結(jié)果。屬于IF/ID部分的指令寄存器IR的各個(gè)字段，在用于提供寄存器名時(shí)就將其標(biāo)記。IR[rs]＝IR6..10IR[rt]＝IR11..15IR[rd]＝IR16..20流水線寄存器在兩個(gè)相鄰的流水段之間既傳遞數(shù)據(jù)也傳遞控制信息。后面流水段需要的數(shù)據(jù)，必須能從一個(gè)流水寄存器復(fù)制到下一個(gè)流水寄存器，直到不再需要為止。所以流水寄存器與非流水通路中使用的臨時(shí)寄存器不一樣。例如：EX/MEM.ALUo：保存EX段ALU的運(yùn)算結(jié)果MEM/WB.LMD：保存MEM段從數(shù)據(jù)存儲(chǔ)器讀出的數(shù)據(jù)向后傳遞后面將要用到的數(shù)據(jù)或者控制信息所有有用的數(shù)據(jù)和控制信息每個(gè)時(shí)鐘周期會(huì)隨著指令在流水線中的流動(dòng)往后流動(dòng)一段。

增加了向后傳遞IR和從MEM/WB.IR回送到通用寄存器組的連接。將對(duì)PC的修改移到了IF段，以便PC能及時(shí)地加

4，為取下一條指令做好準(zhǔn)備。流水實(shí)現(xiàn)的數(shù)據(jù)通路流水線的控制主要是如何控制四個(gè)多路選擇器。MUX2(根據(jù)指令類型是否是轉(zhuǎn)移操作來(lái)設(shè)定)if（ID/EX.IR[op]==“分支指令”）{MUX2_output＝ID/EX.NPC}；elseMUX2_output＝ID/EX.A；

//MUX2_output表示MUX2的輸出MUX3（根據(jù)指令類型是R-R的ALU操作還是其他指令來(lái)設(shè)定）if（ID/EX.IR[op]==“寄存器－寄存器型ALU指令”）{MUX3_output＝ID/EX.B}；elseMUX3_output＝ID/EX.Imm；

//MUX3_output表示MUX3的輸出MUX1if（（ID/EX.IR[op]==“分支指令”）&EX/MEM.cond）{MUX1_output＝EX/MEM.ALUo}；elseMUX1_output＝PC+4；

//MUX1_output表示MUX1的輸出MUX4if（ID/EX.IR[op]==“l(fā)oad”）{MUX4_output＝MEM/WB.LMD}；elseMUX4_output＝MEM/WB.ALUo

//MUX4_output表示MUX4的輸出第5個(gè)多路器：從MEM/WB回傳至通用寄存器組的寫(xiě)入地址應(yīng)該是從MEM/WB.IR[rd]和MEM/WB.IR[rt]中選一個(gè)。寄存器－寄存器型ALU指令：選擇MEM/WB.IR[rd]；寄存器－立即數(shù)型ALU指令和load指令：選擇MEM/WB.IR[rt]。圖中沒(méi)有畫(huà)出，但實(shí)際存在流水段流水線的每個(gè)流水段的操作所有指令類型ALU指令load/store指令分支指令I(lǐng)FIDEXIF/ID.IR←Mem[PC]IF/ID.NPC,PC←（if（（EX/MEM.IR[op]==branch）&EX/MEM.cond）{EX/MEM.ALUo}else{PC+4}）；

ID/EX.A←Regs[IF/ID.IR[rs]]；ID/EX.B←Regs[IF/ID.IR[rt]]；ID/EX.NPC←IF/ID.NPC；ID/EX.IR←IF/ID.IR；ID/EX.Imm←（IF/ID.IR16)16##IF/ID.IR16..31；

EX/MEM.IR←ID/EX.IR；EX/MEM.ALUo←ID/EX.AfunctID/EX.B或EX/MEM.ALUo←ID/EX.AopID/EX.Imm；

EX/MEM.IR←ID/EX.IR；EX/MEM.ALUo←ID/EX.A+ID/EX.Imm；EX/MEM.B←ID/EX.B；

EX/MEM.IR←ID/EX.IR；EX/MEM.ALUo←

（ID/EX.NPC+ID/EX.Imm<<2）；EX/MEM.cond←

（ID/EX.A==0）；

(動(dòng)畫(huà)演示)(動(dòng)畫(huà)演示)(動(dòng)畫(huà)演示)(動(dòng)畫(huà)演示)(動(dòng)畫(huà)演示)流水段任何指令類型ALU指令load/store指令分支指令MEMWBMEM/WB.IR←EX/MEM.IR；MEM/WB.ALUo←EX/MEM.ALUo；

MEM/WB.IR←EX/MEM.IR；MEM/WB.LMD←Mem[EX/MEM.ALUo]；或Mem[EX/MEM.ALUo]←EX/MEM.B；

Regs[MEM/WB.IR[rd]]←MEM/WB.ALUo；或Regs[MEM/WB.IR[rt]]←MEM/WB.ALUo；

Regs[MEM/WB.IR[rt]]←MEM/WB.LMD；

流水線的每個(gè)流水段的操作(動(dòng)畫(huà)演示)(動(dòng)畫(huà)演示)(動(dòng)畫(huà)演示)(動(dòng)畫(huà)演示)解決數(shù)據(jù)沖突的問(wèn)題讓一條指令從ID段到EX段的操作稱為發(fā)射指令。對(duì)于MIPS定點(diǎn)流水線，所有的數(shù)據(jù)沖突均可以在ID段檢測(cè)到。如果存在數(shù)據(jù)沖突，就在相應(yīng)的指令流出ID段之前（也就是發(fā)射前）將之暫停。完成該工作的硬件稱為流水線的互鎖機(jī)制。

同樣也可以在ID段確定需要什么樣的定向，并設(shè)置相應(yīng)的控制。這樣可以降低流水線的硬件復(fù)雜度。（這樣硬件不需要停頓一條已經(jīng)更新了機(jī)器狀態(tài)的指令）也可以在使用操作數(shù)的那個(gè)時(shí)鐘周期的開(kāi)始檢測(cè)沖突和確定必需的定向。實(shí)現(xiàn)方法：檢測(cè)沖突是通過(guò)比較寄存器地址是否相等來(lái)實(shí)現(xiàn)的。舉例：load互鎖由于使用load的結(jié)果而引起的流水線互鎖稱為load互鎖。

ID/EX中的操作碼（ID/EX.IR[op]）IF/ID中的操作碼（IF/ID.IR[op]）比較的操作數(shù)字段loadRRALUID/EX.IR[rt]=IF/ID.IR[rs]loadRRALUID/EX.IR[rt]=IF/ID.IR[rt]loadload、storeALU立即數(shù)或分支ID/EX.IR[rt]=IF/ID.IR[rs]在ID段檢測(cè)是否存在RAW沖突

（這時(shí)load指令在EX段）

若檢測(cè)到RAW沖突，流水線互鎖機(jī)制必須在流水線中插入停頓，并使當(dāng)前正處于IF段和ID段的指令不再前進(jìn)。將ID/EX.IR中的操作碼改為全0

（全0表示空操作）IF/ID寄存器的內(nèi)容回送到自己的入口冒險(xiǎn)更加復(fù)雜流水線中也采用的是相同的方法要考慮的情況更多通過(guò)比較流水寄存器中的寄存器地址來(lái)確定例如：若：(ID/EX.IR.op==RRALU)&（EX/MEM.IR.op==RRALU）&（ID/EX.IR[rt]==EX/MEM.IR[rd]）

則：EX/MEM.ALUo定向到ALU的下面一個(gè)輸入若：（ID/EX.IR[op]==RRALU）&（MEM/WB.IR[op]==load）&（ID/EX.IR[rt]==MEM/WB.IR[rt]）

則：把MEM/WB.LMD定向到ALU的下面一個(gè)輸入舉例若：(ID/EX.IR.op==RRALU)&（EX/MEM.IR.op==RRALU）&（ID/EX.IR[rt]==EX/MEM.IR[rd]）

則：EX/MEM.ALUo定向到ALU的下面一個(gè)輸入若：（ID/EX.IR[op]==RRALU）&（MEM/WB.IR[op]==load）&（ID/EX.IR[rt]==MEM/WB.IR[rt]）

則：把MEM/WB.LMD定向到ALU的下面一個(gè)輸入控制沖突分支指令的條件測(cè)試和分支目標(biāo)地址計(jì)算是在EX段完成，對(duì)PC的修改是在MEM段完成。它所帶來(lái)的分支延遲是3個(gè)時(shí)鐘周期。減少分支延遲：作如下改進(jìn)（把上述工作提前到ID段進(jìn)行）在ID段增設(shè)一個(gè)加法器：計(jì)算分支目標(biāo)地址把條件測(cè)試“=0？”的邏輯電路移到ID段這些結(jié)果直接回送到IF段的MUX1改進(jìn)后的流水線對(duì)分支指令的處理流水段分支指令操作IFIDEXIF/ID.IR←Mem[PC]；IF/ID.NPC,PC←(if((IF/ID[op]==branch)&((Regs[IF/ID.IR[rs]]==0)){IF/ID.NPC+(IF/ID.IR16)16##（IF/ID.IR16..31<<2）}else{PC+4})；

ID/EX.A←Regs[IF/ID.IR[rs]]；ID/EX.B←Regs[IF/ID.IR[rt]]；ID/EX.IR←IF/ID.IR；ID/EX.Imm←（IF/ID.IR16

）16##IF/ID.IR16..31；MEMWB改進(jìn)后流水線的分支操作

5.6開(kāi)發(fā)指令級(jí)并行技術(shù)5.6.1開(kāi)發(fā)指令級(jí)并行的技術(shù)——硬件技術(shù)5.6.2開(kāi)發(fā)指令級(jí)并行的技術(shù)——軟件技術(shù)指令級(jí)并行的概念現(xiàn)在復(fù)雜指令也使用流水線技術(shù)，但是復(fù)雜指令系統(tǒng)的流水線在實(shí)現(xiàn)時(shí)都是先把復(fù)雜的指令指令轉(zhuǎn)化為簡(jiǎn)單的類RISC指令，然后才進(jìn)行流水線的調(diào)度和執(zhí)行。這樣才效率更高，實(shí)現(xiàn)更簡(jiǎn)單。自1985年以來(lái)，所有的處理器都采用流水線方式使指令的執(zhí)行可以重疊執(zhí)行。由于可以將指令間的關(guān)系看做是并行的，因此將指令間的這種潛在重疊稱為指令級(jí)并行（ILP，Instruction-levelparallelism）指令級(jí)并行的概念開(kāi)發(fā)指令級(jí)并行的方法大致分為兩類：一種是基于軟件技術(shù)，在編譯階段靜態(tài)的發(fā)現(xiàn)并行；一種方法是依賴硬件，動(dòng)態(tài)的發(fā)現(xiàn)和開(kāi)發(fā)指令級(jí)的并行。目的都是提高指令序列的并行度。使用基于硬件的動(dòng)態(tài)方法的處理器包括Intel的Pentium處理器，在市場(chǎng)上占主導(dǎo)地位；而采用靜態(tài)方法的處理器包括Intel的Itanium，使用范圍局限于科學(xué)領(lǐng)域或者特定應(yīng)用環(huán)境中。簡(jiǎn)單流水線負(fù)責(zé)取指令并且發(fā)射指令，除非在流水線中的指令與剛?cè)〉降闹噶畲嬖跀?shù)據(jù)相關(guān)并且不能通過(guò)旁路技術(shù)或者直通技術(shù)避免，此時(shí)檢測(cè)沖突的硬件將停止有關(guān)指令以及后面指令進(jìn)入流水線，相關(guān)被取消之前不再取出和發(fā)射新的指令。為了能減少性能損失，編譯器將試圖調(diào)度指令以避免沖突，也就是編譯器調(diào)度法，又叫靜態(tài)調(diào)度法。也可以由硬件動(dòng)態(tài)調(diào)整執(zhí)行指令順序以減少停頓的影響，也就是動(dòng)態(tài)調(diào)度法。靜態(tài)調(diào)度依靠編譯器對(duì)代碼進(jìn)行靜態(tài)調(diào)度，以減少相關(guān)和沖突。它不是在程序執(zhí)行的過(guò)程中、而是在編譯期間進(jìn)行代碼調(diào)度和優(yōu)化。通過(guò)把相關(guān)的指令拉開(kāi)距離來(lái)減少可能產(chǎn)生的停頓。動(dòng)態(tài)調(diào)度在程序的執(zhí)行過(guò)程中，依靠專門(mén)硬件對(duì)代碼進(jìn)行調(diào)度，減少數(shù)據(jù)相關(guān)導(dǎo)致的停頓。靜態(tài)調(diào)度和動(dòng)態(tài)調(diào)度的特點(diǎn)能夠處理一些在編譯時(shí)情況不明的相關(guān)（比如涉及到存儲(chǔ)器訪問(wèn)的相關(guān)），并簡(jiǎn)化了編譯器；能夠使本來(lái)是面向某一流水線優(yōu)化編譯的代碼在其它的流水線（動(dòng)態(tài)調(diào)度）上也能高效地執(zhí)行。以硬件復(fù)雜性的顯著增加為代價(jià)

優(yōu)點(diǎn)：到目前為止我們所使用流水線的最大的局限性:指令是按序流出和按序執(zhí)行的考慮下面一段代碼：DIV.D F4，F(xiàn)0，F(xiàn)2ADD.D F10，F(xiàn)4，F(xiàn)6SUB.D F12，F(xiàn)6，F(xiàn)14ADD.D指令與DIV.D指令關(guān)于F4相關(guān)，導(dǎo)致流水線停頓。SUB.D指令與流水線中的任何指令都沒(méi)有關(guān)系，但也因此受阻。1動(dòng)態(tài)調(diào)度的基本思想5.6.1開(kāi)發(fā)指令級(jí)并行的技術(shù)——硬件技術(shù)指令的動(dòng)態(tài)調(diào)度在前面的基本流水線中：ID檢測(cè)結(jié)構(gòu)沖突檢測(cè)數(shù)據(jù)沖突

一旦一條指令受阻，其后的指令都將停頓。

指令的動(dòng)態(tài)調(diào)度為了使上述指令序列中的