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

./流水线的数据相关

1.数据相关简介

当指令在流水线中重叠执行时,流水线有可能改变指令读/写操作数的顺序,使得读/写操作顺序不同于它们非流水实现的顺序,这将导致数据相关。首先让我们考虑下列指令在流水线中的执行情况：ADD

R1,R2,R3

SUBR4,R5,R1

AND

R6,R1,R7

ORR8,R1,R9

XORR10,R1,

R11ADD指令后的所有指令都要用到ADD指令的计算结果,如图所示,ADD指令在WB段才将计算结果写入寄存器R1中,但是SUB指令在其ID段就要从寄存器R1中读取该计算结果,这种情况就叫做数据相关。除非有措施防止这一情况出现,否则SUB指令读到的是错误的值。所以,为了保证上述指令序列的正确执行,流水线只好暂停ADD指令之后的所有指令,直到ADD指令将计算结果写入寄存器R1之后,再启动ADD指令之后的指令继续执行。

从图还可以看到,AND指令同样也将受到这种相关关系的影响。ADD指令只有到第五个时钟周期末尾才能结束对寄存器R1的写操作,所以AND指令在第四个时钟周期从寄存器R1中读出的值也是错误的。而XOR指令则可以正常操作,因为它是在第六个时钟周期读寄存器R1的容。

另外,利用DLX流水线的一种简单技术,可以使流水线顺利执行OR指令。这种技术就是：在DLX流水线中,约定在时钟周期的后半部分进行寄存器文件的读操作,而在时钟周期的前半部分进行寄存器文件的写操作。在本章的图中,我们将寄存器文件的边框适当地画成虚线来表示这种技术。2.通过定向技术减少数据相关带来的暂停

图中的数据相关问题可以采用一种称为定向〔也称为旁路或短路的简单技术来解决〔动画演示。定向技术的主要思想是：在某条指令〔如图3.3.4中的ADD指令产生一个计算结果之前,其它指令〔如图3.3.4中的SUB和AND指令并不真正需要该计算结果,如果能够将该计算结果从其产生的地方〔寄存器文件EX/MEM直接送到其它指令需要它的地方〔ALU的输入寄存器,那么就可以避免暂停。基于这种考虑,定向技术的要点可以归纳为：

<1>寄存器文件EX/MEM中的ALU的运算结果总是回送到ALU的输入寄存器。

<2>当定向硬件检测到前一个ALU运算结果的写入寄存器就是当前ALU操作的源寄存器时,那么控制逻辑将前一个ALU运算结果定向到ALU的输入端,后一个ALU操作就不必从源寄存器中读取操作数。图还表明,流水线中的指令所需要的定向结果可能并不仅仅是前一条指令的计算结果,而且还有可能是前面与其不相邻指令的计算结果,图3.3.5是采用了定向技术后上述例子的执行情况,其中寄存器文件和功能单元之间的箭头表示定向路径。上述指令序列可以在图3.3.5中顺利执行而无需暂停。上述定向技术可以推广到更一般的情况,可以将一个结果直接传送到所有需要它的功能单元。也就是说,一个结果不仅可以从某一功能单元的输出定向到其自身的输入,而且还可以从某一功能单元的输出定向到其它功能单元的输入。<1>写后读相关〔RAW：ReadAfterWrite〔命名规则：j的执行要用到i的计算结果,当它们在流水线中重叠执行时,j可能在i写入其计算结果之前就先行对保存该结果的寄存器进行读操作,从而得到错误的值。这是最常见的一种数据相关,图和图3.3.7中采用定向技术消除的数据相关就属于这种类型。

<2>写后写相关〔WAW：WriteAfterWrite：j和i的目的寄存器相同,当它们在流水线中重叠执行时,j可能在i写入其计算结果之前就先行对该结果寄存器进行写操作,从而导致写入顺序错误,在目的寄存器中留下的是i写入的值,而不是j写入的值。

如果在流水线中不只一个段可以进行写操作,或者当流水线暂停某条指令时,允许该指令之后的指令继续前进,就可能会产生这种类型的数据相关。由于DLX流水线只在WB段写寄存器,所以在DLX流水线中执行的指令不会发生这种类型的数据相关。如果我们对DLX流水线作如下改变,在DLX流水线中执行的指令就有可能发生WAW相关。首先,将ALU运算结果的写回操作移到MEM段进行,因为这时计算结果已经有效；其次,假设访问数据存储器占两个流水段。下面是两条指令在修改后的DLX流水线中执行的情况：

可以看出,在修改后的DLX流水线中执行上述指令序列后,寄存器R1中的容是第一条指令〔LW的写入结果,而不是ADD指令的写入结果。这就是由于WAW相关所带来的错误执行结果。

<3>读后写相关〔WAR：WriteAfterRead：j可能在i读取某个源寄存器的容之前就先对该寄存器进行写操作,导致i后来读取到的值是错误的。

由于DLX流水线在ID段完成所有的读操作,在WB段完成所有的写操作。所以,在DLX流水线中不会产生这种类型的数据相关。基于上面修改后的DLX流水线,考察下面两条指令的执行情况：

如果SW指令在MEM2段的后半部分读取寄存器R2的值,ADD指令在WB段的前半部分将计算结果写回寄存器R2,则SW将读取错误的值,将ADD指令的计算结果写入存储器中。值得注意的是,在读后读〔RAR：ReadAfterRead的情况下,不存在数据相关问题。4.需要暂停的数据相关

前面我们讨论了如何利用定向技术消除由于数据相关带来的暂停。但是,并不是所有数据相关带来的暂停都可以通过定向技术消除。

为了保证流水线正确执行上述指令序列,可以设置一个称为流水线互锁〔pipelineinterlock的功能部件。一旦流水线互锁检测到上述数据相关,流水线暂停执行LW指令之后的所有指令,直到能够通过定向解决该数据相关为止。图为流水线互锁插入暂停后流水线数据通路；

图是加入暂停前后的流水线时空图。下面讨论如何利用编译器技术来减少这种必须的暂停,然后论述如何在流水线中实现数据相关检测和定向。

5.对数据相关的编译器调度方法

流水线常常会遇到许多种类型的暂停。比如,采用典型的代码生成方法对A=B+C这种常用的表达式进行处理,可以得到如图所示的指令序列。从图3.3.14可以看出,在ADD指令的流水过程中必须插入一个暂停时钟周期,以保证变量C的读入值有效。既然定向无法消除指令序列中所包含的这种暂停,那么能否让编译器在进行代码生成时就消除这些潜在的暂停呢？实际上,编译器的确可以通过重新组织代码顺序来消除这种暂停。通常称这种重新组织代码顺序消除暂停的技术为流水线调度〔pipelinescheduling或指令调度〔instructionscheduling。

例3.6请为下列表达式生成没有暂停的DLX代码序列。假设载入延迟为1个时钟周期。

a=b-c；

d=e-f；

解：调度前后的指令序列如表3.2所示。可以看出,两条ALU指令〔ADDRa,Rb,Rc和SUBRd,Re,Rf分别和两条Load指令〔LWRc,c和LWRf,f之间存在数据相关。为了保证流水线正确执行调度前的指令序列,必须在指令执行过程中插入两个时钟周期的暂停。但是考察调度后的指令序列不难发现,由于流水线允许定向,就不必在指令执行过程中插入任何暂停周期。6.对DLX流水线控制的实现

让一条指令从流水线的指令译码段〔ID移动到执行段〔EX的过程通常称为指令发射,而经过了该过程的指令为已发射的指令。

对于DLX标量流水线而言,所有的数据相关均可以在流水线的ID段检测到,如果存在数据相关,指令在其发射之前就会被暂停。这样,我们可以在ID段决定需要什么样的定向,然后设置相应的控制。在流水线中较早地检测到相关,可以降低实现流水线的硬件复杂度,因为这样不必在流水过程中被迫将一条已经改变了机器状态的指令挂起。另外一种方法是在使用一个操作数的时钟周期开始〔DLX流水线的EX和MEM段的开始检测相关,确定必需的定向。

为了说明这两种方法的不同,我们将以Load指令所引起的RAW相关为例,论述如何通过在ID段的检测来实现流水线控制,其中到ALU输入的定向路径可以在EX段。表3.3列出了流水线相关检测硬件可以检测到的各种相关情况。

现在来看看如何实现流水线互锁。如果某条指令和Load指令有一个RAW相关时,该指令处于ID段,Load指令处于EX段。我们可以用表3.4来描述此时所有可能的相关情况。

一旦硬件检测到上述RAW相关,流水线互锁必须在流水线中插入暂停周期,使正处于IF和ID段的指令不再前进。另外,还必须暂停向前传送IF/ID寄存器组的容,使得流水线能够保持被暂停的指令。

对定向而言,虽然可能要考虑许多情况,但是定向逻辑的实现方法是类似的。实现定向逻辑的关键是,流水线寄存器不仅包含了被定向的数据,而且包含了目标和源寄存器域。从上面的讨论可知,所有定向都是从ALU或数据存储器的输出到ALU、数据存储器或0检测单元的输入的定向,我们可以分别将EX/MEM和MEM/WB段的寄存器IR同ID/EX和EX/MEM段中的寄存器IR相比较,决定是否需要定向,从而实现必需的定向控制。定向的控制硬件除了需要用比较器和组合逻辑来确定什么时候打开哪一条定向路径之外,还需要在ALU输入端采用具有多个输入的多路器,并增加相应的定向路径连接通路。改进图中的相关硬件,可以得到图3.3.15,图中画出了所增设的定向路径。

在DLX中,任何流水线