dl流水線技術(shù)數(shù)據(jù)相關(guān)與結(jié)構(gòu)相關(guān)

1、3.3.2 流水線的數(shù)據(jù)相關(guān)1 .數(shù)據(jù)相關(guān)簡介當(dāng)指令在流水線中重疊執(zhí)行時(shí)，流水線有可能改變指令讀/寫操作數(shù)的順序，使得讀/寫操作順序不同于它們非流水實(shí)現(xiàn)的順序，這將導(dǎo)致數(shù)據(jù)相關(guān)。首先讓我們考慮下列指令在流水線中的執(zhí)行情況：ADDR1,R2,R3SUBR4,R5,R1ANDR6,R1,R7ORR8,R1,R9XORR10,R1,R11ADD 指令后的所有指令都要用到 ADD 旨令的計(jì)算結(jié)果，如圖 3.3.4 所示，ADD 指令在 WB段才將計(jì)算結(jié)果寫入寄存器 R1 中，但是 SUB 指令在其 ID 段就要從寄存器 R1 中讀取該計(jì)算結(jié)果，這種情況就叫做數(shù)據(jù)相關(guān)。除非有措施防止這一情況出現(xiàn)，否則

2、SUB 指令讀到的是錯(cuò)誤的值。所以，為了保證上述指令序列的正確執(zhí)行，流水線只好暫停 ADD 指令之后的所有指令，直到 ADD 指令將計(jì)算結(jié)果寫入寄存器 R1 之后，再啟動 ADD 指令之后的指令繼續(xù)執(zhí)行。數(shù)據(jù)相關(guān)率例數(shù)據(jù)相關(guān)率例希賽教育就考學(xué)院http:,Yeity.enf時(shí)閭【時(shí)鐘里：CCiCC2CC3CC4CCSCC6CCiCC2CC3CC4CCSCC6希賽教有軟考學(xué)浣Mtp:/vw,educit7-eg瑁流水線的數(shù)據(jù)相關(guān)從圖 3.3.4 還可以看到，AND 指令同樣也將受到這種相關(guān)關(guān)系的影響。ADD 指令只有到第五個(gè)時(shí)鐘周期末尾才能結(jié)束對寄存器 R1 的寫操作，所以 AND

3、指令在第四個(gè)時(shí)鐘周期從寄存器 R1 中讀出的值也是錯(cuò)誤的。而 XOR 指令則可以正常操作，因?yàn)樗窃诘诹鶄€(gè)時(shí)鐘周期讀寄存器 R1 的內(nèi)容。另外，利用 DLX 流水線的一種簡單技術(shù)，可以使流水線順利執(zhí)行 OR 指令。這種技術(shù)就是：在 DLX 流水線中，約定在時(shí)鐘周期的后半部分進(jìn)行寄存器文件的讀操作，而在時(shí)鐘周期的前半部分進(jìn)行寄存器文件的寫操作。在本章的圖中，我們將寄存器文件的邊框適當(dāng)?shù)禺嫵商摼€來表示這種技術(shù)。2.通過定向技術(shù)減少數(shù)據(jù)相關(guān)帶來的暫停圖 3.3.4 中的數(shù)據(jù)相關(guān)問題可以采用一種稱為定向（也稱為旁路或短路）的簡單技術(shù)來解決（動畫演示）。定向技術(shù)的主要思想是：在某條指令（如圖中的 ADD

4、 指令）產(chǎn)生一個(gè)計(jì)算結(jié)果之前，其它指令（如圖中的 SUB 和 AND 指令）并不真正需要該計(jì)算結(jié)果，如果能夠?qū)⒃撚?jì)算結(jié)果從其產(chǎn)生的地方（寄存器文件 EX/MEM）直接送到其它指令需要它的地方（ALU 的輸入寄存器），那么就可以避免暫停。基于這種考慮，定向技術(shù)的要點(diǎn)可以歸納為：(1)寄存器文件 EX/MEM 中的 ALU 的運(yùn)算結(jié)果總是回送到 ALU 的輸入寄存器。程序勢仃順序(妻IKIKR R(2)當(dāng)定向硬件檢測到前一個(gè) ALU 運(yùn)算結(jié)果的寫入寄存器就是當(dāng)前 ALU 操作的源寄存器時(shí)，那么控制邏輯將前一個(gè) ALU 運(yùn)算結(jié)果定向到 ALU 的輸入端，后一個(gè) ALU 操作就不必從源寄存器中讀取操作

5、數(shù)。來用定向技術(shù)消除數(shù)據(jù)相關(guān)來用定向技術(shù)消除數(shù)據(jù)相關(guān)病賽教育軟考學(xué)院ktlp:，wnMaeduoity*cry1mrafttimraftti怖郡CClCCCClCC：0C3gX5CC60C3gX5CC6圖瓦3.5圖 3.3.4 還表明，流水線中的指令所需要的定向結(jié)果可能并不僅僅是前一條指令的計(jì)算結(jié)果，而且還有可能是前面與其不相鄰指令的計(jì)算結(jié)果，圖是采用了定向技術(shù)后上述例子的執(zhí)行情況，其中寄存器文件和功能單元之間的箭頭表示定向路徑。上述指令序列可以在圖中順利執(zhí)行而無需暫停。采用定向技術(shù)后的工作過程般般r.pr.p：,H3,H3zuzu鞏也需AMJAMJ城51,51,即耶踽叫跺察救育軟考學(xué)院ktt

6、p;ww,educLiy.kttp;ww,educLiy.皿皿ORiqRl/ORiqRl/門圖3,13,16上述定向技術(shù)可以推廣到更一般的情況，可以將一個(gè)結(jié)果直接傳送到所有需要它的功能單元。也就是說，一個(gè)結(jié)果不僅可以從某一功能單元的輸出定向到其自身的輸入，而且還可以從某一功能單元的輸出定向到其它功能單元的輸入。(1)寫后讀相關(guān)(RAWReadAfterWrite)(命名規(guī)則)：j 的執(zhí)行要用到 i 的計(jì)算結(jié)果，當(dāng)它們在流水線中重疊執(zhí)行時(shí)，j 可能在 i 寫入其計(jì)算結(jié)果之前就先行對保存該結(jié)果的寄存器進(jìn)行讀操作，從而得到錯(cuò)誤的值。這是最常見的一種數(shù)據(jù)相關(guān)，圖 3.3.6 和圖中采用定向技術(shù)消除的數(shù)

7、據(jù)相關(guān)就屬于這種類型。(2)寫后寫相關(guān)(WAWWriteAfterWrite):j 和 i 的目的寄存器相同，當(dāng)它們在流水線中重疊執(zhí)行時(shí)，j 可能在 i 寫入其計(jì)算結(jié)果之前就先行對該結(jié)果寄存器進(jìn)行寫操作，從而導(dǎo)致寫入順序錯(cuò)誤，在目的寄存器中留下的是 i 寫入的值，而不是 j 寫入的值。如果在流水線中不只一個(gè)段可以進(jìn)行寫操作，或者當(dāng)流水線暫停某條指令時(shí)，允許該指令之后的指令繼續(xù)前進(jìn)，就可能會產(chǎn)生這種類型的數(shù)據(jù)相關(guān)。由于 DLX 流水線只在 WB 段寫寄存器，所以在 DLX 流水線中執(zhí)行的指令不會發(fā)生這種類型的數(shù)據(jù)相關(guān)。如果我們對 DLX 流水線作如下改變，在DLX 流水線中執(zhí)行的指令就有可能發(fā)生

8、 WAWB 關(guān)。首先，將ALU 運(yùn)算結(jié)果的寫回操作移到 MEM 段進(jìn)行，因?yàn)檫@時(shí)計(jì)算結(jié)果已經(jīng)有效；其次，假設(shè)訪問密賽鞅音軟考學(xué)炭1.11p1.11p：/1*w*w+ +edutity.0Medutity.0M相令】指令3 30 指令4 4口指半案寨物骨軟考學(xué)院httpi.yrwvv.oducitffl./httpi.yrwvv.oducitffl./數(shù)據(jù)存儲器占兩個(gè)流水段。下面是兩條指令在修改后的 DLX 流水線中執(zhí)行的情況：系.“用1后的DLX流水線會發(fā)生WAW相關(guān)幫黃藜再栽芍子阮citycm/LWLWRLRL0,0,(R2)(R2)IFIFIDIDEXEXMBM1M

9、EM2MEM2槌ADDADDR1,R1,R2,R3R2,R3IFIFIDIDEXEXWBWB希賽教亨軟考學(xué)院educity,cn/educity,cn/可以看出， 在修改后的DLX流水線中執(zhí)行上述指令序列后， 寄存器R1中的內(nèi)容是第一條指令(LW的寫入結(jié)果，而不是 ADD 指令的寫入結(jié)果。這就是由于 WAM 目關(guān)所帶來的錯(cuò)誤執(zhí)行結(jié)果。(3)讀后寫相關(guān)(WARWriteAfterRead):j 可能在 i 讀取某個(gè)源寄存器的內(nèi)容之前就先對該寄存器進(jìn)行寫操作，導(dǎo)致 i 后來讀取到的值是錯(cuò)誤的。由于 DLX 流水線在 ID 段完成所有的讀操作，在 WB 段完成所有的寫操作。所以，在 DLX 流水線中

10、不會產(chǎn)生這種類型的數(shù)據(jù)相關(guān)?；谏厦嫘薷暮蟮?DLX 流水線，考察下面兩條指令的執(zhí)行情況：SWR2,SWR2,0(RE)0(RE)IFIFIDIDEXEXHEM1HEM1MFN12MFN12WBWBADDRZR3iADDRZR3i刈IFIFIDIDEXEXWBWB如果 SW 指令在 MEM2 段的后半部分讀取寄存器 R2 的值，ADD 指令在 WB 段的前半部分將計(jì)算結(jié)果寫回寄存器 R2,則 SW 將讀取錯(cuò)誤的值，將 ADD 指令的計(jì)算結(jié)果寫入存儲器中。值得注意的是，在讀后讀(RARReadAfterRead)的情況下，不存在數(shù)據(jù)相關(guān)問題。4 .需要暫停的數(shù)據(jù)相關(guān)前面我們討論了如何利用定向技術(shù)

11、消除由于數(shù)據(jù)相關(guān)帶來的暫停。但是，并不是所有數(shù)據(jù)相關(guān)帶來的暫停都可以通過定向技術(shù)消除。足白技術(shù)不能解決的數(shù)據(jù)相關(guān)桑褰勒青兼老季快htt?:/ 1。LWLW指令不能將結(jié)果定向曳SU3SU3指令為了保證流水線正確執(zhí)行上述指令序列，可以設(shè)置一個(gè)稱為流水線互鎖(pipelineinterlock)的功能部件。一旦流水線互鎖檢測到上述數(shù)據(jù)相關(guān)，流水線暫停執(zhí)行 LW 旨令之后的所有指令，直到能夠通過定向解決該數(shù)據(jù)相關(guān)為止。程序玩行胸序(指也希賽軟首就希學(xué)院ht17MM.educity-cr/ht17MM.educity-cr/相關(guān)時(shí)將停流水線希賽救肯蒙考學(xué)詈http:/imrhttp:/imr.tduzi

12、tyiay.tduzityiay圖 3.3.12 為流水線互鎖插入暫停后流水線數(shù)據(jù)通路;在垢入口暫件.妁情況下遍木城的工作過混圖 313.12在插入在插入“暫停暫停”情況下，流水線的時(shí)空圖情況下，流水線的時(shí)空圖L*RLO(R2)L*RLO(R2)IFIDEXMEMIFIDEXMEM聯(lián)聯(lián)SUBR4,RI,R5SUBR4,RI,R5IFIDIFIDstallstallEXMEMKBEXMEMKBANDR6,RI,R7ANDR6,RI,R7IFIFstalJstalJIDEXMIDEXM則MBMBUKUK昭jKI,jKI,四stallstallJFDEXMENIBJFDEXMENIB圖 3.3.13

13、卜面討論如何利用編譯器技術(shù)來減少這種必須的暫停，然后論述如何在流水線中實(shí)現(xiàn)數(shù)據(jù)相關(guān)檢測和定向。圖 3.3.13 是加入暫停前后的流水線時(shí)空圖。程序推行喊序指之時(shí)間(療褲離期 1-C C1 1LKR1LKR1, ,0303 巨 h hSBR4.El,SBR4.El,即ANUKANUK 機(jī) KLKL 艮 1 1ORX6.KJORX6.KJRR5 .對數(shù)據(jù)相關(guān)的編譯器調(diào)度方法流水線常常會遇到許多種類型的暫停。比如，采用典型的代碼生成方法對 A=B+C 這種常用的表達(dá)式進(jìn)行處理，可以得到如圖 3.3.14 所示的指令序列。從圖可以看出，在ADD 指令的流水過程中必須插入一個(gè)暫停時(shí)鐘周期，以保證變量 C

14、 的讀入值有效。既然定向無法消除指令序列中所包含的這種暫停，那么能否讓編譯器在進(jìn)行代碼生成時(shí)就消除這些潛在的暫停呢表達(dá)式h8h8批的代碼及其流水執(zhí)行口廣市塞教苜較卷至譙D DA-A-B B+ +C Chtiphtip；/wwrf/wwrf#c#cI IB BF F. .S SUIUI/ /* *，取c;c;寄存鑿暫存于放在放在相加.分配S3S3*泰*普疆學(xué)院保存結(jié)果,http;/wv,educity.cWhttp;/wv,educity.cWr 充賽,育裁“院LWRLBIFIDEXIOIBLWRLBIFIDEXIOIB皿田加舊山口5 5W WLWR2CIPiDEXMELWR2CIPiDEXME

15、邨IFIDIFIDstalMstalMMHKflBMHKflBIFIFstallstallIDEXHEMWBIDEXHEMWB圖3.3，A二B+。的LX代斛序列及其疣水線購時(shí)空圖表示實(shí)際上，編譯器的確可以通過重新組織代碼順序來消除這種暫停。通常稱這種重新組織代碼順序消除暫停的技術(shù)為流水線調(diào)度(pipelinescheduling)或指令調(diào)度(instructionscheduling)。例請為下列表達(dá)式生成沒有暫停的 DLX 代碼序列。假設(shè)載入延遲為 1 個(gè)時(shí)鐘周期。a=b-c;d=e-f;解：調(diào)度前后的指令序列如表所示?？梢钥闯?，兩條 ALU 指令(ADDRa,Rb,Rc 和 SUBRd,R

16、e,Rf)LWRLBLWRLBLWR2,CLWR2,CADDR3,RLR2ADDR3,RLR2SWA.R3SWA.R3ADDADD電，RLR2RLR2分別和兩條 Load 指令(LWRc,c 和 LWRf,f)之間存在數(shù)據(jù)相關(guān)。 為了保證流水線正確執(zhí)行調(diào)度前的指令序列，必須在指令執(zhí)行過程中插入兩個(gè)時(shí)鐘周期的暫停。但是考察調(diào)度后的指令序列不難發(fā)現(xiàn)，由于流水線允許定向，就不必在指令執(zhí)行過程中插入任何暫停周期。表3.2調(diào)度前后的代碼序列表達(dá)式d-ft-f的代碼的調(diào)度U一。一L希賽教育軟考學(xué)院http:/wvw* _http:/wvcity-cn/.educity-cn/Re，

17、eLWRfRfnfSWaRaRd,R*RfSUBRd,Re,Rf4RdSW&Rd6.對 DLX 流水線控制的實(shí)現(xiàn)讓一條指令從流水線的指令譯碼段（ID）移動到執(zhí)行段（EXX的過程通常稱為指令發(fā)射，而經(jīng)過了該過程的指令為已發(fā)射的指令。對于 DLX 標(biāo)量流水線而言，所有的數(shù)據(jù)相關(guān)均可以在流水線的 ID 段檢測到，如果存在數(shù)據(jù)相關(guān)，指令在其發(fā)射之前就會被暫停。這樣，我們可以在 ID 段決定需要什么樣的定向，然后設(shè)置相應(yīng)的控制。在流水線中較早地檢測到相關(guān)，可以降低實(shí)現(xiàn)流水線的硬LWLWADDADDSWLWLWSUBSW件復(fù)雜度，因?yàn)檫@樣不必在流水過程中被迫將一條已經(jīng)改變了機(jī)器狀態(tài)的指令掛起。另外

18、一種方法是在使用一個(gè)操作數(shù)的時(shí)鐘周期開始（DLX 流水線的 EX 和 MEM 段的開始）檢測相關(guān)，確定必需的定向。為了說明這兩種方法的不同，我們將以 Load 指令所引起的 RAW 相關(guān)為例，論述如何通過在 ID段的檢測來實(shí)現(xiàn)流水線控制，其中到 ALU 輸入的定向路徑可以在 EX 段。表列出了流水線相關(guān)檢測硬件可以檢測到的各種相關(guān)情況。菽3湖窗日鄭嫄件可噓蟠!帆梯美情祝流水線相關(guān)檢測域件可以檢測到的流水線相關(guān)檢測域件可以檢測到的希賽髓就考學(xué)腐各種相關(guān)情況http:/wvhttp:/wv.edicity.edicity.W相關(guān)情況指令赤列晶陽卻任這三條指令與R1R1二點(diǎn)故不可靛出懶,前毒載htt

19、p:/wvhttp:/wv,edacity,cn/,edacity,cn/比敢鋸穩(wěn)測到加例自令中使用R R酢方長:卡溫并在ADADD D指令蚣E EX X段之前將之哲舉同時(shí)也將抑時(shí)吟民相守皆停）牘交銀卷冽畀5C5CB B指令申使用R RI I作力歸寄存耦,料及時(shí)的荏SUSUB B相令進(jìn)入曲段 N 前畜LoadLoad省分的結(jié)果定向機(jī)北山LWLW指令在前半月期將菰吳寫入R1R1GEGE指令防粉阱窈1 1現(xiàn)在來看看如何實(shí)現(xiàn)流水線互鎖。如果某條指令和 Load 指令有一個(gè) RAW 相關(guān)時(shí)，該指令處于 ID 段，Load 指令處于 EX 段。我們可以用表來描述此時(shí)所有可能的相關(guān)情況。LILIm,m,蛤

20、（咫）停;g g相學(xué)ADADi i題RE,RE,演MEME皿陶啦燈OROR啊隰R7R7LflLflR1,4SR1,4S（R2R2）罵要音信ADADD D甌R1,R1,野的僦叱陶陶書OROR碼題咫LWLWRLRL駁（R2R2）通過定向ADADD D甌嫡的i i畿的S S美SUBR8,R1,R7SUBR8,R1,R7OROR網(wǎng)的R7R7LffLffRLRL第（爻）朧第ADDR5,ADDR5,陶田陶田用聯(lián)SJBSJB潞電引電引OROR咫,R1,R7R1,R7裹3.43.4指令衽二D D段為檢測是否需啟動流水端ifif而進(jìn)行兩三和匕較在在IDID段檢測段檢測LoadLoad互裝雷進(jìn)行三種比較互裝雷進(jìn)行

21、三種比較 LoadxStorLoadxStor序、AUJAUJ立M M載.分支等搔爭:產(chǎn)存耨rsrsL L島.坤碧果存春器rdrd； IRuIRu,眸IF/IDIF/IDIDEXIDEX的拂隼遒量（祖成1 1曲一IF0IF0由巖炸諳域LoadLoadS-RALJS-RALJI ID D 加工 I&I&口i i. . . .|5|5= =IF/ID,1R.S-IF/ID,1R.S-. .JJQLeadLeadK-RALJK-RALJWLIKii.ts=IFaD.IRu.WLIKii.ts=IFaD.IRu.t t.s.sLeadLeadLoad.Load.中 cnaALcnaAL

22、 應(yīng)相性或分支 TimIRiiTimIRiiii=IlADlIRt.ii=IlADlIRt.一旦硬件檢測到上述 RAW 相關(guān)，流水線互鎖必須在流水線中插入暫停周期，使正處于 IF 和 ID 段的指令不再前進(jìn)。另外，還必須暫停向前傳送 IF/ID 寄存器組的內(nèi)容，使得流水線能夠保持被暫停的指令。對定向而言，雖然可能要考慮許多情況，但是定向邏輯的實(shí)現(xiàn)方法是類似的。實(shí)現(xiàn)定向邏輯的關(guān)鍵是，流水線寄存器不僅包含了被定向的數(shù)據(jù)，而且包含了目標(biāo)和源寄存器域。從上面的討論可知，所有定向都是從 ALU 或數(shù)據(jù)存儲器的輸出到 ALU、數(shù)據(jù)存儲器或 0 檢測單元的輸入的定向， 我們可以分別將 EX/MEM 和 MEM/WB 段的寄存器 IR 同 ID/EX 和 EX/MEM 段中的寄存器 I