DLX流水线技术数据相关与结构相关

1、3.3.2 流水线的数据相关1. 数据相关简介当指令在流水线中重叠执行时， 流水线有可能改变指令读 /写操作数的顺序， 使得读 /写操 作顺序不同于它们非流水实现的顺序， 这将导致数据相关。 首先让我们考虑下列指令在流水 线中的执行情况： ADD R1 ， R2， R3SUB R4， R5， R1AND R6， R1 ， R7OR R8， R1， R9XOR R10 ， R1 ， R11ADD 指令后的所有指令都要用到 ADD 指令的计算结果，如图 3.3.4 所示， ADD 指令在 WB 段才将计算结果写入寄存器 R1 中，但是 SUB 指令在其 ID 段就要从寄存器 R1 中 读取该计算结

2、果，这种情况就叫做数据相关。除非有措施防止这一情况出现，否则 SUB 指令读到的是错误的值。所以，为了保证上述指令序列的正确执行，流水线只好暂停 ADD 指令之后的所有指令，直到 ADD 指令将计算结果写入寄存器 R1 之后，再启动 ADD 指令之后的指令继续执行。数据相关举例希赛教育拧考学曲 http;/wv. e due ity.ADD R1,R2,R3亦4,R1,葢AM 叔,ITOfi R 池 R9m R1CLJO.KL1帝喬數肓软勇学陆Mtp:/7inrw*e（juuit尹.ca/1图3壬虫茴术线的数据相并从图334还可以看到，AND指令同样也将受到这种相关关系的影响。ADD指令只有到

3、第五个时钟周期末尾才能结束对寄存器R1的写操作，所以 AND指令在第四个时钟周期从寄存器 R1中读出的值也是错误的。而XOR指令则可以正常操作，因为它是在第六个时钟周期读寄存器R1的容。另外，利用DLX流水线的一种简单技术，可以使流水线顺利执行OR指令。这种技术就是：在DLX流水线中，约定在时钟周期的后半部分进行寄存器文件的读操作，而在时 钟周期的前半部分进行寄存器文件的写操作。在本章的图中，我们将寄存器文件的边框适当地画成虚线来表示这种技术。2.通过定向技术减少数据相关带来的暂停图中的数据相关问题可以采用一种称为定向（也称为旁路或短路）的简单技术来解 决（动画演示）。定向技术的主要思想是：在

4、某条指令（如图 中的ADD指令）产生一个计算结果之前，其它指令（如图 中的SUB和AND指令）并不真正需要该计 算结果，如果能够将该计算结果从其产生的地方（寄存器文件EX/MEM ）直接送到其它指令需要它的地方（ALU的输入寄存器），那么就可以避免暂停。基于这种考虑，定向技术 的要点可以归纳为：（1）寄存器文件 EX/MEM 中的ALU的运算结果总是回送到ALU的输入寄存器。(2) 当定向硬件检测到前一个ALU运算结果的写入寄存器就是当前ALU操作的源寄存器时，那么控制逻辑将前一个ALU运算结果定向到 ALU的输入端，后一个 ALU操作就不必从源寄存器中读取操作数。采用定向挂术消能数播相关希赛

5、報育软考学陕p : www. edueity* cry1CC1 CCS CC3 0C4 K5 CC6CF R& RlpR9m RIO,fibRL1IrtTpiZ/wv. *duci+y. rn/圏33.5图334还表明，流水线中的指令所需要的定向结果可能并不仅仅是前一条指令的计算结果，而且还有可能是前面与其不相邻指令的计算结果，图是采用了定向技术后上述例子的执行情况，其中寄存器文件和功能单元之间的箭头表示定向路径。上述指令序列可以在图3.3.5中顺利执行而无需暂停。采用定命技忒后騎工柞过程壽赛觀育软考学嵐1.11 pi /忏艸 + ecui； ity.萌令】ADO叩昭時SIT鸥血曲AM

6、J廉匚即0雀专4殊血】嗨师育劇学廉kt t p;e ducL"t y* czv1指邻Xffi HI耳的北11上述定向技术可以推广到更一般的情况，可以将一个结果直接传送到所有需要它的功能单元。也就是说，一个结果不仅可以从某一功能单元的输出定向到其自身的输入，而且还可以从某一功能单元的输出定向到其它功能单元的输入。(1)写后读相关(RAW : Read After Write)(命名规则)：j的执行要用到i的计算结果，当它们在流水线中重叠执行时，j可能在i写入其计算结果之前就先行对保存该结果的寄存器进行读操作，从而得到错误的值。这是最常见的一种数据相关，图336和图337中采用定向技术消

7、除的数据相关就属于这种类型。(2)写后写相关(WAW : Write After Write)： j和i的目的寄存器相同，当它们在流 水线中重叠执行时，j可能在i写入其计算结果之前就先行对该结果寄存器进行写操作， 从而导致写入顺序错误，在目的寄存器中留下的是i写入的值，而不是 j写入的值。如果在流水线中不只一个段可以进行写操作，或者当流水线暂停某条指令时，允许该指令之后的指令继续前进，就可能会产生这种类型的数据相关。由于DLX流水线只在WB段写寄存器，所以在 DLX流水线中执行的指令不会发生这种类型的数据相关。如果我们 对DLX流水线作如下改变，在 DLX流水线中执行的指令就有可能发生WAW相

8、关。首先,将ALU运算结果的写回操作移到MEM段进行，因为这时计算结果已经有效；其次，假设访问数据存储器占两个流水段。下面是两条指令在修改后的DLX流水线中执行的情况：希繇戟影后的DLX流水线会发生W册相关Http i / /wi. ediicity. cri/LW RE 0, (R2)IF IDEXMBM1MEM2WBADD Rl, R2, R3IFIDEXWB需赛載芦软考学院httpi/Zww* educity* cn/可以看出，在修改后的 DLX流水线中执行上述指令序列后，寄存器 R1中的容是第一 条指令(LW)的写入结果，而不是 ADD指令的写入结果。这就是由于 WAW 相关所带 来的

9、错误执行结果。(3) 读后写相关(WAR : Write After Read)： j可能在i读取某个源寄存器的容之前 就先对该寄存器进行写操作，导致i后来读取到的值是错误的。由于DLX流水线在ID段完成所有的读操作，在WB段完成所有的写操作。 所以，在DLX流水线中不会产生这种类型的数据相关。基于上面修改后的DLX流水线，考察下面两条指令的执行情况：SW R2, 0 (RS)IFIDEXJIEM111E1A2WBADDRS.刑IFIDEX如果SW指令在MEM2段的后半部分读取寄存器 R2的值，ADD指令在WB段的 前半部分将计算结果写回寄存器 R2，则SW将读取错误的值，将 ADD指令的计算

10、结果 写入存储器中。值得注意的是，在读后读( RAR : Read After Read)的情况下，不存在数 据相关问题。4. 需要暂停的数据相关前面我们讨论了如何利用定向技术消除由于数据相关带来的暂停。但是，并不是所有数 据相关带来的暂停都可以通过定向技术消除。定向技术不能解决的数毎相捷. educity, cm/師时钟周期)CC1 CC2 CCS CC4兀 E埠赛簌育軟肴学院 ht t p: /ww* e due it yt er/因3A1Q L隨&令不能将结杲定B3SU3ffi令为了保证流水线正确执行上述指令序列，可以设置一个称为流水线互锁(pipeline interlock)

11、的功能部件。一旦流水线互锁检测到上述数据相关， 流水线暂停执行LW指令之后的所 有指令，直到能够通过定向解决该数据相关为止。相关时曹停流水线图3312为流水线互锁插入暂停后流水线数据通路;图3313是 加入暂停前后的流水线时空图。在插入0暂碎撷药情况丁瀛水线妁工作过程荒间狞样風畀-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面讨论如何利用编译器技术来减少这种必须的暂停，然后论述如何在流水线中实现数据相关检测和定向。5. 对数据相关的编译器调度方法流水线常常会遇到许多种类型的暂停。比如，采用典型的代码生成方法对A = B + C这种常用的表达式进行处理，可以得到如图所示的指令序列。从图可以看出，在ADD指令的流水过程中必须插入一个暂停时钟周期，以保证变量C的读入值有效。既然定向无法消除指令序列中所包含的这种暂停，那么能否让编译器在进行代码生成时就消除这些潜在的暂停呢？表达式A-B+Ct代箱及其流术执柠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代询序及其流水銭实现时空图表示实际上，编译器的确可以通过重新组织代码顺序来消除这种暂停。通常称这种重新组织代码顺序消除暂停的技术为流水线调度(pipeline schedulin

14、g)或指令调度(instruction scheduling)。例3.6请为下列表达式生成没有暂停的DLX代码序列。假设载入延迟为1个时钟周期。a = b - c;解：调度前后的指令序列如表 3.2所示。可以看出，两条 ALU指令(ADD Ra, Rb，R c和SUB Rd，Re，Rf)分别和两条 Load指令(LW Rc，c和LW Rf，f)之间存在数据 相关。为了保证流水线正确执行调度前的指令序列，必须在指令执行过程中插入两个时钟周期的暂停。但是考察调度后的指令序列不难发现，由于流水线允许定向， 就不必在指令执行过程中插入任何暂停周期。3.2调度前后的代码序列希赛教肓软畫学院+ educi

15、ty cn/调度前购眞码调度后的代码LWRb, bLWRb, bLWRe, cLWRcGADDRa, Rb, RgL¥!SW& RaLWRd ehttpsducLty. cn/LWR£ fLWRf, fS¥!a? RaSUBRd, Re, RfSUBRd, Red, RfSW& RdSW& Rd6. 对DLX流水线控制的实现让一条指令从流水线的指令译码段（ID ）移动到执行段（EX）的过程通常称为指令发射，而经过了该过程的指令为已发射的指令。对于DLX标量流水线而言，所有的数据相关均可以在流水线的ID段检测到，如果存在数据相关，指令在其发射

16、之前就会被暂停。这样，我们可以在ID段 决定需要什么样的定向，然后设置相应的控制。在流水线中较早地检测到相关，可以降低实现流水线的硬件复杂度，因为这样不必在流水过程中被迫将一条已经改变了机器状态的指令挂起。另外一种方法是在使用一个操作数的时钟周期开始（DLX流水线的EX和MEM段的开始）检测相关，确定必需的定向。为了说明这两种方法的不同，我们将以Load指令所引起的 RAW 相关为例，论述如何通过在ID段 的检测来实现流水线控制，其中到 ALU输入的定向路径可以在EX段。表3.3列出了流水线相关检测硬件可以检测到的各种相关情况。和$洽蝴冃关愉順戸:以鬪忸旳各附试II抚沆水线扌目关检瀬史件可以檢

17、测到的 盈赛數軸考学曉各种相芙椿况httpj/wv. einity.骑相黄情况看令存列艳国鬲作毀有相关LI RL45(R2)ADD酝畑R7 SUB風底R?OR R9,RRR7址三第捋亨WIU无弋故不可能出 碾育软考学院 http：/iwv, Edirity* ch/mi*的俄Lfl Rlf45(R2)ADD R5> Rt IffSUB岡岡R7 OR陶甌超鼎端检澳圍AD瞳令电使解IfW恒 各代倂在灿腕迪EK段打将 N善恨同时也将SUB#C1OR弟纟替伴）通过顔LW R1,45(R2) ADD版魅R?SUB R8.UK7OS陽隔R7鼎端捡测那TB扌詮中便用肛作肯忖 裁存議幷反时附在SU薩专芒

18、入EX段 之赫L曲捲翔络绘冋瓠LU卿序前冃Lff Rl, 4S(K2)ADD R5, R6, R7 SJB RS,更苗OR RS何冊L瞄&令銅半片期将结是写入扎10腓令胡辆船班现在来看看如何实现流水线互锁。如果某条指令和Load指令有一个 RAW 相关时，该指令处于ID段，Load指令处于EX段。我们可以用表3.4来描述此时所有可能的相关情况。4拒令在n段为栓別是否需启MiU线锁而逬行的三科I：章在ID段检aiLoM生饕需进打三种比较 R-R ALUB：膜荊那“：I&旳*源寄存霍“2； IRn is-Loed» Sto® AbU立即数*分支络捋4r确肺器E:

19、 I陆.埠1甯杲奋克鄴rd； R| .isIF/ID希赛敦育筋考学希 . 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立閃数秦井支ID/KK IRii if =uADl IRfl.灼一旦硬件检测到上述RAW 相关，流水线互锁必须在流水线中插入暂停周期，使正处于IF和ID段 的指令不再前进。另外，还必须暂停向前传送IF/ID寄存器组的容，使得流水线能够保持被暂停的指令。对定向而言，虽然可能要考虑许多情况，但是定向逻辑的实现方法是类似的。实现定向逻辑的关键是，流水线寄存器不仅包含了被定向的数据，而且包含了目标和源寄存器域。从上面的讨论可知，所有定向都是从ALU或数据存储器的输出到ALU、数据存储器或0检测单元的输入的定向， 我们可以分别将 EX/MEM 和MEM/WB 段的寄存器IR同ID/EX 和EX/MEM 段中的寄存器IR相比