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

2、果，這種情況就叫做數(shù)據(jù)相關(guān)。除非有措施防止這一情況出現(xiàn)，否則 SUB 指令讀到的是錯誤的值。所以，為了保證上述指令序列的正確執(zhí)行，流水線只好暫停 ADD 指令之后的所有指令，直到 ADD 指令將計算結(jié)果寫入寄存器 R1 之后，再啟動 ADD 指令之后的指令繼續(xù)執(zhí)行。數(shù)據(jù)相關(guān)舉例希賽教育擰考學(xué)曲 http;/wv. e due ity.ADD R1,R2,R3亦4,R1,葢AM 叔,ITOfi R 池 R9m R1CLJO.KL1帝喬數(shù)肓軟勇學(xué)陸Mtp:/7inrw*e（juuit尹.ca/1圖3壬蟲茴術(shù)線的數(shù)據(jù)相并從圖334還可以看到，AND指令同樣也將受到這種相關(guān)關(guān)系的影響。ADD指令只有到

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

4、某條指令（如圖 中的ADD指令）產(chǎn)生一個計算結(jié)果之前，其它指令（如圖 中的SUB和AND指令）并不真正需要該計 算結(jié)果，如果能夠?qū)⒃撚嬎憬Y(jié)果從其產(chǎn)生的地方（寄存器文件EX/MEM ）直接送到其它指令需要它的地方（ALU的輸入寄存器），那么就可以避免暫停。基于這種考慮，定向技術(shù) 的要點可以歸納為：（1）寄存器文件 EX/MEM 中的ALU的運算結(jié)果總是回送到ALU的輸入寄存器。(2) 當(dāng)定向硬件檢測到前一個ALU運算結(jié)果的寫入寄存器就是當(dāng)前ALU操作的源寄存器時，那么控制邏輯將前一個ALU運算結(jié)果定向到 ALU的輸入端，后一個 ALU操作就不必從源寄存器中讀取操作數(shù)。采用定向掛術(shù)消能數(shù)播相關(guān)希賽

5、報育軟考學(xué)陜p : www. edueity* cry1CC1 CCS CC3 0C4 K5 CC6CF R& RlpR9m RIO,fibRL1IrtTpiZ/wv. *duci+y. rn/圏33.5圖334還表明，流水線中的指令所需要的定向結(jié)果可能并不僅僅是前一條指令的計算結(jié)果，而且還有可能是前面與其不相鄰指令的計算結(jié)果，圖是采用了定向技術(shù)后上述例子的執(zhí)行情況，其中寄存器文件和功能單元之間的箭頭表示定向路徑。上述指令序列可以在圖3.3.5中順利執(zhí)行而無需暫停。采用定命技忒后騎工柞過程壽賽觀育軟考學(xué)嵐1.11 pi /懺艸 + ecui； ity.萌令】ADO叩昭時SIT鷗血曲AM

6、J廉匚即0雀專4殊血】嗨師育劇學(xué)廉kt t p;e ducL"t y* czv1指鄰Xffi HI耳的北11上述定向技術(shù)可以推廣到更一般的情況，可以將一個結(jié)果直接傳送到所有需要它的功能單元。也就是說，一個結(jié)果不僅可以從某一功能單元的輸出定向到其自身的輸入，而且還可以從某一功能單元的輸出定向到其它功能單元的輸入。(1)寫后讀相關(guān)(RAW : Read After Write)(命名規(guī)則)：j的執(zhí)行要用到i的計算結(jié)果，當(dāng)它們在流水線中重疊執(zhí)行時，j可能在i寫入其計算結(jié)果之前就先行對保存該結(jié)果的寄存器進(jìn)行讀操作，從而得到錯誤的值。這是最常見的一種數(shù)據(jù)相關(guān)，圖336和圖337中采用定向技術(shù)消

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

8、關(guān)。首先,將ALU運算結(jié)果的寫回操作移到MEM段進(jìn)行，因為這時計算結(jié)果已經(jīng)有效；其次，假設(shè)訪問數(shù)據(jù)存儲器占兩個流水段。下面是兩條指令在修改后的DLX流水線中執(zhí)行的情況：希繇戟影后的DLX流水線會發(fā)生W冊相關(guān)Http i / /wi. ediicity. cri/LW RE 0, (R2)IF IDEXMBM1MEM2WBADD Rl, R2, R3IFIDEXWB需賽載蘆軟考學(xué)院httpi/Zww* educity* cn/可以看出，在修改后的 DLX流水線中執(zhí)行上述指令序列后，寄存器 R1中的容是第一 條指令(LW)的寫入結(jié)果，而不是 ADD指令的寫入結(jié)果。這就是由于 WAW 相關(guān)所帶 來的

9、錯誤執(zhí)行結(jié)果。(3) 讀后寫相關(guān)(WAR : Write After Read)： j可能在i讀取某個源寄存器的容之前 就先對該寄存器進(jìn)行寫操作，導(dǎo)致i后來讀取到的值是錯誤的。由于DLX流水線在ID段完成所有的讀操作，在WB段完成所有的寫操作。 所以，在DLX流水線中不會產(chǎn)生這種類型的數(shù)據(jù)相關(guān)。基于上面修改后的DLX流水線，考察下面兩條指令的執(zhí)行情況：SW R2, 0 (RS)IFIDEXJIEM111E1A2WBADDRS.刑IFIDEX如果SW指令在MEM2段的后半部分讀取寄存器 R2的值，ADD指令在WB段的 前半部分將計算結(jié)果寫回寄存器 R2，則SW將讀取錯誤的值，將 ADD指令的計算

10、結(jié)果 寫入存儲器中。值得注意的是，在讀后讀( RAR : Read After Read)的情況下，不存在數(shù) 據(jù)相關(guān)問題。4. 需要暫停的數(shù)據(jù)相關(guān)前面我們討論了如何利用定向技術(shù)消除由于數(shù)據(jù)相關(guān)帶來的暫停。但是，并不是所有數(shù) 據(jù)相關(guān)帶來的暫停都可以通過定向技術(shù)消除。定向技術(shù)不能解決的數(shù)毎相捷. educity, cm/師時鐘周期)CC1 CC2 CCS CC4兀 E埠賽簌育軟肴學(xué)院 ht t p: /ww* e due it yt er/因3A1Q L隨&令不能將結(jié)杲定B3SU3ffi令為了保證流水線正確執(zhí)行上述指令序列，可以設(shè)置一個稱為流水線互鎖(pipeline interlock)

11、的功能部件。一旦流水線互鎖檢測到上述數(shù)據(jù)相關(guān)， 流水線暫停執(zhí)行LW指令之后的所 有指令，直到能夠通過定向解決該數(shù)據(jù)相關(guān)為止。相關(guān)時曹停流水線圖3312為流水線互鎖插入暫停后流水線數(shù)據(jù)通路;圖3313是 加入暫停前后的流水線時空圖。在插入0暫碎擷藥情況丁瀛水線妁工作過程荒間獰樣風(fēng)畀-CC1SU® 也 Hl. R5OR 釀 R1, SScc<.在插入皿暫停31情況下，流水線的吋空圖LM R1.0 冋£F ID El M£M 魅SUB R4, RL R5IF ID stall EX MEM 即AND R6> Rl, R7IF stall ID EX MEM

12、flbOR KB, Rl, R9stallID EX MEN WRF面討論如何利用編譯器技術(shù)來減少這種必須的暫停，然后論述如何在流水線中實現(xiàn)數(shù)據(jù)相關(guān)檢測和定向。5. 對數(shù)據(jù)相關(guān)的編譯器調(diào)度方法流水線常常會遇到許多種類型的暫停。比如，采用典型的代碼生成方法對A = B + C這種常用的表達(dá)式進(jìn)行處理，可以得到如圖所示的指令序列。從圖可以看出，在ADD指令的流水過程中必須插入一個暫停時鐘周期，以保證變量C的讀入值有效。既然定向無法消除指令序列中所包含的這種暫停，那么能否讓編譯器在進(jìn)行代碼生成時就消除這些潛在的暫停呢？表達(dá)式A-B+Ct代箱及其流術(shù)執(zhí)檸ht ip:fcn/取C :寄複器暫存于歆左故在

13、hrttpiZ/wv. eitjcity. ciV相Jto：保存拮果Lff RL BLH R2»CADD R3, Rb R2SW A,R3LW Rl, BIF ID EX MEK IBhttp:/m.eiiucit7-cr/LW R2, CIP ID EX 莊片 HADD R3, Rl, R2IF ID stallEX MHK WBIF stall ID EX NEM 睡圖乩3, K A = B + C的nx代詢序及其流水銭實現(xiàn)時空圖表示實際上，編譯器的確可以通過重新組織代碼順序來消除這種暫停。通常稱這種重新組織代碼順序消除暫停的技術(shù)為流水線調(diào)度(pipeline schedulin

14、g)或指令調(diào)度(instruction scheduling)。例3.6請為下列表達(dá)式生成沒有暫停的DLX代碼序列。假設(shè)載入延遲為1個時鐘周期。a = b - c;解：調(diào)度前后的指令序列如表 3.2所示。可以看出，兩條 ALU指令(ADD Ra, Rb，R c和SUB Rd，Re，Rf)分別和兩條 Load指令(LW Rc，c和LW Rf，f)之間存在數(shù)據(jù) 相關(guān)。為了保證流水線正確執(zhí)行調(diào)度前的指令序列，必須在指令執(zhí)行過程中插入兩個時鐘周期的暫停。但是考察調(diào)度后的指令序列不難發(fā)現(xiàn)，由于流水線允許定向， 就不必在指令執(zhí)行過程中插入任何暫停周期。3.2調(diào)度前后的代碼序列希賽教肓軟畫學(xué)院+ educi

15、ty cn/調(diào)度前購眞碼調(diào)度后的代碼LWRb, bLWRb, bLWRe, cLWRcGADDRa, Rb, RgL¥!SW& RaLWRd ehttpsducLty. cn/LWR£ fLWRf, fS¥!a? RaSUBRd, Re, RfSUBRd, Red, RfSW& RdSW& Rd6. 對DLX流水線控制的實現(xiàn)讓一條指令從流水線的指令譯碼段（ID ）移動到執(zhí)行段（EX）的過程通常稱為指令發(fā)射，而經(jīng)過了該過程的指令為已發(fā)射的指令。對于DLX標(biāo)量流水線而言，所有的數(shù)據(jù)相關(guān)均可以在流水線的ID段檢測到，如果存在數(shù)據(jù)相關(guān)，指令在其發(fā)射

16、之前就會被暫停。這樣，我們可以在ID段 決定需要什么樣的定向，然后設(shè)置相應(yīng)的控制。在流水線中較早地檢測到相關(guān)，可以降低實現(xiàn)流水線的硬件復(fù)雜度，因為這樣不必在流水過程中被迫將一條已經(jīng)改變了機器狀態(tài)的指令掛起。另外一種方法是在使用一個操作數(shù)的時鐘周期開始（DLX流水線的EX和MEM段的開始）檢測相關(guān)，確定必需的定向。為了說明這兩種方法的不同，我們將以Load指令所引起的 RAW 相關(guān)為例，論述如何通過在ID段 的檢測來實現(xiàn)流水線控制，其中到 ALU輸入的定向路徑可以在EX段。表3.3列出了流水線相關(guān)檢測硬件可以檢測到的各種相關(guān)情況。和$洽蝴冃關(guān)愉順戸:以鬪忸旳各附試II撫沆水線扌目關(guān)檢瀬史件可以檢

17、測到的 盈賽數(shù)軸考學(xué)曉各種相芙椿況httpj/wv. einity.騎相黃情況看令存列艷國鬲作毀有相關(guān)LI RL45(R2)ADD醞畑R7 SUB風(fēng)底R?OR R9,RRR7址三第捋亨WIU無弋故不可能出 碾育軟考學(xué)院 http：/iwv, Edirity* ch/mi*的俄Lfl Rlf45(R2)ADD R5> Rt IffSUB岡岡R7 OR陶甌超鼎端檢澳圍AD瞳令電使解IfW恒 各代倂在燦腕迪EK段打?qū)?N善恨同時也將SUB#C1OR弟纟替伴）通過顔LW R1,45(R2) ADD版魅R?SUB R8.UK7OS陽隔R7鼎端撿測那TB扌詮中便用肛作肯忖 裁存議幷反時附在SU薩專芒

18、入EX段 之赫L曲捲翔絡(luò)繪冋瓠LU卿序前冃Lff Rl, 4S(K2)ADD R5, R6, R7 SJB RS,更苗OR RS何冊L瞄&令銅半片期將結(jié)是寫入扎10腓令胡輛船班現(xiàn)在來看看如何實現(xiàn)流水線互鎖。如果某條指令和Load指令有一個 RAW 相關(guān)時，該指令處于ID段，Load指令處于EX段。我們可以用表3.4來描述此時所有可能的相關(guān)情況。4拒令在n段為栓別是否需啟MiU線鎖而逬行的三科I：章在ID段檢aiLoM生饕需進(jìn)打三種比較 R-R ALUB：膜荊那“：I&旳*源寄存霍“2； IRn is-Loed» Sto® AbU立即數(shù)*分支絡(luò)捋4r確肺器E:

19、 I陸.埠1甯杲奮克鄴rd； R| .isIF/ID希賽敦育筋考學(xué)希 . edu:ity»civ，'IL/EX的按乍詢倉血龍亙1氐訂LeadS-R AL'JID /EL I 為 i. gs= IF/ID. I Rs，八 wLeadK-R AL JID/KL IRii.£=IF/IDl IE.jsLeadLoad，Stor曇3立閃數(shù)秦井支ID/KK IRii if =uADl IRfl.灼一旦硬件檢測到上述RAW 相關(guān)，流水線互鎖必須在流水線中插入暫停周期，使正處于IF和ID段 的指令不再前進(jìn)。另外，還必須暫停向前傳送IF/ID寄存器組的容，使得流水線能夠保持被暫停的指令。對定向而言，雖然可能要考慮許多情況，但是定向邏輯的實現(xiàn)方法是類似的。實現(xiàn)定向邏輯的關(guān)鍵是，流水線寄存器不僅包含了被定向的數(shù)據(jù)，而且包含了目標(biāo)和源寄存器域。從上面的討論可知，所有定向都是從ALU或數(shù)據(jù)存儲器的輸出到ALU、數(shù)據(jù)存儲器或0檢測單元的輸入的定向， 我們可以分別將 EX/MEM 和MEM/WB 段的寄存器IR同ID/EX 和EX/MEM 段中的寄存器IR相比