,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,3.1,重叠执行和先行控制,一,.,指令的重叠执行,一条指令的执行过程可以粗略地分为：取指令、分析和执行三个阶段，且这个次序是不能改变的。,取指令,执行,分析,t,T,i,用,T,i,表示执行一条指令所需的时间，可以写成：,T,i,=,t,取指令,+,t,分析,+,t,执行,3.1,重叠执行和先行控制,如果连续执行一段程序，计算机对前后相邻指令的执行过程可以有两种不同的选择,:,1.,顺序执行方式，即等前一条指令执行完毕，紧接着执行下一条指令,.,2.,让前后连续的指令在处理机内以重叠的方式执行,.,取指,分析,执行,取指,分析,执行,k,+ 1,k,3.1,重叠执行和先行控制,一次重叠执行方式,:,二次重叠执行方式,:,取指,分析,执行,取指,分析,执行,取指,分析,执行,第,k,条指令,第,k,+ 1,条指令,第,k,+ 2,条指令,取指,分析,执行,取指,分析,执行,取指,分析,执行,第,k,条指令,第,k,+ 1,条指令,第,k,+ 2,条指令,如果三个阶段所需时间,t,相等，,N,条指令顺序执行的时间为 ：,T=3Nt,。,一次重叠执行的时间：,T=(1+2N)t,。,二次重叠执行的时间为：,T=,（,2+N)t,。,3.1,重叠执行和先行控制,二,.,先行控制技术,1,实现重叠执行,存在的问题,（,1,）问题一：,需要独立的取指部件，分析部件，执行部件。,解决方案,:,设置对应存储控制器，指令控制器和运算控制器。,3.1,重叠执行和先行控制,（,2,）问题二：,主存访问冲突,取指令时,，处理机必须按指令计数器的指示访问存储器；,分析指令时,，可能需要从存储器中获取操作数；,执行指令时,，也可能要求将结果写回到存储器中。,处理机中三个独立的部件可能同时提出对存储器读写的请求，从而发生存储器访问冲突。,3.1,重叠执行和先行控制,解决方案：,1,）分别设置两个独立的存储器：指令存储器和数据存储器，或一级,Cache,分为程序,Cache,和数据,Cache,，同时工作解决同时读指令和读数据引起的冲突。,程序空间和数据空间相互独立并具有独立的指令总线和数据总线的系统结构就称为哈佛结构,缺点：结构复杂，需要大量的数据线，,对汇编程序员和机器程序员不透明,2,）多体交叉存储器结构也可减少冲突的发生。,3,）先行控制技术是最根本的办法。,3.1,重叠执行和先行控制,在复杂的计算机指令系统中，各种指令在分析和执行阶段所需的时间可能有很大的差别。于是，前面对三个阶段所需时间,t,相等的假设就可能不成立，所得到的节约三分之二时间的结论也被动摇了。下图形象地表示了这种情况所造成的影响。,第,k,条指令,分析,执行,第,k,+2,条指令,执行,分析,第,k,+1,条指令,分析,执行,这种情况可用先行控制技术来缓解。,3.1,重叠执行和先行控制,2,采用先行控制技术的处理机,运算控制器,先 行 指 令 栈,后 行 写 数 栈,先 行 读 数 栈,存 储 控 制 器,去主存储器,地址线,指 令 分 析 器,先行操作栈,运 算 器,通 用 寄 存 器,3.1,重叠执行和先行控制,缓冲栈实际上是一个以先进先出（,FIFO,）方式工作的移位寄存器组，上图表示了缓冲栈所处的地位。前置部件的输出不直接送入后置部件，而是通过缓冲栈暂存后才输出。,前置部件,后置部件,缓冲栈,运算控制器,先 行 指 令 栈,后 行 写 数 栈,先 行 读 数 栈,存 储 控 制 器,去主存储器,地址线,指 令 分 析 器,先行操作栈,运 算 器,通 用 寄 存 器,3.1,重叠执行和先行控制,3,先行控制原理,通过先行指令计数器,PC1,预取指令序列,通过现行指令计数器,PC,取出现行指令,指令分析器,指令分析器,:,对取自先行指令栈的指令进行预处理,.,1.,对于程序控制类的指令，如转移指令，指今分析器可以直接完成指令的执行,.,2.,对于数据运算型指令，指令分析器要将它们变换成寄存器寄存器型,(RR,型,),指令，即将操作数预先存到寄存器中，使指令能快速执行,.,立即寻址,传数据,变址寻址或存储器型指令,传地址,RR*,指令,3.1,重叠执行和先行控制,先行控制技术中采取了两个根本的措施：,指令预处理技术,和,缓冲技术,。由于指令和数据的缓冲，保证了指令分析和指令的执行都能全速地运行。,第,k,条指令,分析,执行,第,k,+2,条指令,执行,分析,第,k,+1,条指令,分析,执行,缓冲栈深度应满足以下关系：,D,取指栈,D,操作栈,D,读栈,D,写栈,第,k,条指令,分析,执行,第,k,+2,条指令,执行,分析,第,k,+1,条指令,分析,执行,3.2,流水线的基本概念,一,.,什么是流水线,1.,流水线技术（,pipelining,）,把一个重复的过程分解为若干个子过程，每个子过程由专门的功能部件来实现。,把多个处理过程在时间上错开，依次通过各功能段，这样，每个子过程就可以与其他的子过程并行进行。,流水线中的每个子过程及其功能部件称为,流水线的级或段,，段与段相互连接形成流水线。流水线的段数称为,流水线的深度。,3.2,流水线的基本概念,2,流水线结构,重叠执行是流水线结构的思想基础，只要在指令分析器与指令执行部件之后都加上一个锁存器，就成了一个简单的流水线结构。,指令执行部件,指令分析器,锁存器,锁存器,分析,k,+1,执行,k,t,2,t,1,结果出,指令入,在流水线的每一个功能部件的后面都要有一个缓冲寄存器，或称为锁存器、闸门寄存器等，它的作用是保存本流水段的执行结果。,3,时空图,时空图可以直观地表现流水线的工作过程,横轴表示时间，即各条指令在处理机中经历各个操作时占用的时间段。如果各级执行所需的时间相等，在横轴上应表现为等距离的时间段。,纵轴表示空间，即流水线的各个子操作过程，通常也称为“功能段”。,k,t,(n-1),t,n-1,1,2,3,n,n-1,1,2,3,n,n-1,1,2,3,n,n-1,1,2,3,n,时间,空间,S,1,S,2,S,3,S,4,n-1,1,2,3,n,S,5,填入,填满,排空,3.2,流水线的基本概念,4,流水线的工作特点,1,）一条流水线通常由多个流水段组成，在每一个流水段有专门的功能部件来实现。,2,）各流水段所需的时间应尽可能相等，否则将引起流水线堵塞、断流。,3,）流水线每个功能部件后面都有一个缓冲寄存器，称为流水寄存器。,4,）流水线的工作一般分为,3,个阶段，即建立（填入）、填满和排空。,5,）流水线技术适合于大量重复的时序过程，只有在输入端不断地提供任务，才能充分发挥流水线的效率。,3.2,流水线的基本概念,二,.,流水线的种类,1,、 按处理机分类,操作部件级,为最低级别的流水线。是把处理机的算术逻辑运算部件分段。如果某一部件的处理过程比较复杂，如浮点运算,需要较长的时间。这时可以将该部件分为若干子部件，分别完成浮点运算中有关的子操作，这种在部件范围内形成的流水线称为操作部件级流水线。,3.2,流水线的基本概念,一个浮点加法部件的流水线：,求阶差,对阶,尾数加,规格化,入,出,部件级流水线通常是流水线处理机中的一部分，这时的处理机由于流水级数较多，又称为超流水线处理机。,3.2,流水线的基本概念,处理机级,又称为指令流水线，就是将一条指令的解释执行过程分解,成若干个子过程，使每个子过程分别在一个部件中完成。,处理机间级,处理机间流水线通常是多处理机系统中对任务采取的一种处理策略。,3.2,流水线的基本概念,上图是处理机间流水线示意图，图中每个处理机是以任务为单位进行处理的，而处理机间的任务传递则是由公用存储器完成的。应当指出，图中给出的是一个处理的,“,流水,”,，并没有涉及更多的硬件结构。实际上这个过程更应该看作是一种任务的调度策略。,处理机,2,M,处理机,n,M,输出,处理机,1,M,输入,任务,1,任务,2,任务,n,3.2,流水线的基本概念,2,、,按流水线功能多少分类,单功能流水线,指一条流水线只能完成一种单一的任务。,多功能流水线,指能够在一个时间段内或不同时间段间改变部件之间的连接，从而达到改变其功能的流水线。,3.2,流水线的基本概念,在标量运算中，各种运算是混在一起的。,3,、 按照工作方式分类,静态流水线,当执行某一规定功能的指令全部流出后，才允许改变部件间连接的流水线。,（可以是单功能流水线也可以是多功能流水线）,3.2,流水线的基本概念,动态流水线,没有这种时间上的限制，可以在任何时候根据需要改变其连接。,（只能是多功能流水线）,3.2,流水线的基本概念,4,、 按连接方式分类,线性流水线,是指在部件上没有反馈连接的流水线。在这种流水线中，指令依次通过各个部件仅一次，完成指令执行的全过程。目前所使用的流水线绝大部分都是这类线性流水线。,非线性流水线,是指在各部件除了串行的连接外，还通过反馈线使某些部件得以重复使用。指令在通过这种流水线时，可能在反馈部件上重复运行若干次。,3.2,流水线的基本概念,反馈回路,S1,S2,S3,入,出,S3,S1,S2,时间,非线性流水线工作特性示意图,3.2,流水线的基本概念,5,、 按流入流出顺序分类,顺序流水线,其输出的结果与输入的次序相同，早期的流水线又称为,顺序流水线,。,乱序流水线,将原始的输入次序打乱，以最有利于处理机执行的方式运行，在输出结果时才恢复原次序。,在一些现代处理机中，如,Pentium 4,在流水线运行过程中采用了,乱序方式,。,3.2,流水线的基本概念,除了上述几种分类方法以外，还可以根据各种不同的观点对流水线进行区分。比如：,按照数据表示方式的不同，可以将流水线分为,标量流水线,和,向量流水线,两种。在标量处理机中使用的当然是标量流水线。,根据流水线在各级之间流动时的控制方法不同，又可以分成,同步,和,异步,两种流水线。,3.2,流水线的基本概念,处理机内的,指令流水线,都是,同步流水线,，即使用统一的时钟控制各级同时开始同时完成动作。,而,处理机间的流水线,通常都是,异步流水线,，需要在任务传送时进行应答，以确保传输的可靠性。,3.3,流水线的性能指标,吞吐率、加速比和效率是表明流水线性能的主要指标。,一,.,吞吐率,把流水线在单位时间内完成的任务量定义为吞吐率。,k,T,n,TP,=,其中,n,为完成任务的总数，在指令流水线中就是完成的指令总条数；,T,k,是完成,n,个任务所用的时间。,3.3,流水线的性能指标,各级执行时间相等的流水线,一条,k,级的流水线执行,n,条指令的时空图,:,t,n,k,T,k,D,-,+,=,),1,(,n-1,1,2,3,n,n-1,1,2,3,n,n-1,1,2,3,n,n-1,1,2,3,n,k,t,(n-1),t,n,t,(k-1),t,T,k,时间,空间,S,1,S,2,S,3,S,4,所需的总时间为：,3.3,流水线的性能指标,当,n,时，（,k,1,）可以忽略不计，得到的最大吞吐率为,:,t,t,n,k,n,TP,n,D,=,D,-,+,=,1,),1,(,lim,max,所以，吞吐率为,:,t,n,k,n,TP,D,-,+,=,),1,(,3.3,流水线的性能指标,各级执行时间不等的流水线,执行时间不等的流水线时空图,n,1,2,3,1,2,3,n,n,3,2,1,3,1,2,n,(n-1),t,2,T,k,时间,空间,S,4,S,3,S,2,S,1,3.3,流水线的性能指标,吞吐率的一般表示式为,:,同样方法可以得到当,n,时的最大吞吐率为：,=,D,D,D,-,+,D,=,k,i,k,i,t,t,t,n,t,n,TP,1,2,1,),(,max,),1,(,),(,max,1,2,1,max,k,t,t,t,TP,D,D,D,=,3.3,流水线的性能指标,如果流水线中各级的执行时间不相等，其中时间最长者就成了流水线中的,“,瓶颈,”,。瓶颈问题对流水线的吞吐率影响是明显的，所以消除,“,瓶颈,”,是设计流水线的一个重要原则。,“,瓶颈,”,问题的消除,采用的方法主要有两种：,1,）分割瓶颈部件的工作,2,）重复设置瓶颈部件,3.3,流水线的性能指标,消除,“,瓶颈,”,影响的两种方法示意图：,S,2-1,S,2-2,S,2-3,S,2,(3,t ),t,t,(a),(b),S,2-3,S,2-1,S,2-2,t,2,=3,t,3,t,S,1,S,2,S,3,S,4,t,t,t,两种方式在效果上是可以等效的，在输入,n,条指令的情况下，实际吞吐率都为：,t,n,n,t,n,n,TP,D,+,=,D,-,+,=,),5,(,),1,6,(,3.3,流水线的性能指标,不消除,“,瓶颈,”,时的吞吐率：,两种方式在效果上是可以等效的，在输入,n,条指令的情况下，实际吞吐率都为：,t,n,n,t,n,n,TP,D,+,=,D,-,+,=,),5,(,),1,6,(,=,D,D,D,-,+,D,=,k,i,k,i,t,t,t,n,t,n,TP,1,2,1,),(,max,),1,(,=,6,3D,-,+,D,t,n,t,n,),1,(,=,3,D,+,t,3n,n,),(,3.3,流水线的性能指标,二,.,加速比,处理同一批任务，不用流水线与采用流水线时所花费的时间之比，称为流水线的,加速比,。,如果不用流水线所用的时间为,T,0,，用了流水线所用时间为,T,k,，那么加速比就是：,S = T,0,/T,k,3.3,流水线的性能指标,不用流水线时，每条指令执行时必须在时间上顺序地完成各处理步骤，那么,n,条指令所需时间就为,T,0,= nkt,。而一个采用流水线的处理机所需时间为,T,k,=,(,k + n ,1 ),t,。,所以加速比就为,1,),1,(,0,-,+,=,D,-,+,D,=,=,n,k,n,k,t,n,k,t,k,n,T,T,S,k,同样办法可以得到最大加速比,k,n,k,n,k,S,n,=,-,+,=,1,lim,max,3.3,流水线的性能指标,如果考虑各级执行时间不等的情况时，一条指令的执行时间是各级运行时间之和。在没有流水线时，,n,条指令应是一条指令的,n,倍。于是，可得到加速比为,=,=,D,D,D,-,+,D,D,=,k,i,k,i,k,i,i,t,t,t,n,t,t,n,S,1,2,1,1,),(,max,),1,(,3.3,流水线的性能指标,三,.,效率,效率被定义为：,空区,个流水线级占用的总时,条指令占用的时空区,k,n,E,=,n-1,1,2,3,n,n-1,1,2,3,n,n-1,1,2,3,n,n-1,1,2,3,n,k,t,(n-1),t,n,t,(k-1),t,T,k,时间,空间,S,1,S,2,S,3,S,4,各级执行时间相等的流水线效率等于：,1,),1,(,-,+,=,D,-,+,D,=,n,k,n,t,n,k,k,t,k,n,E,3.3,流水线的性能指标,显然，,n,越大，空闲部件占据的比例就小，流水线表现的效率越高。最高效率为：,1,1,lim,max,=,-,+,=,n,k,n,E,n,通过类似的分析方法，我们也可以得到在各 级执行时间不等的流水线中的效率计算方法。,=,=,D,D,D,-,+,D,D,=,k,i,k,i,k,i,i,t,t,t,n,t,k,t,n,E,1,2,1,1,),(,max,),1,(,3.3,流水线的性能指标,同样，,效率公式：,加速比公式：,两者相结合得出：,E = S/k,或,S = k E,1,-,+,=,n,k,n,k,S,1,-,+,=,n,k,n,E,效率公式：,t,n,k,n,TP,D,-,+,=,),1,(,吞吐率公式：,1,-,+,=,n,k,n,E,两者相结合得出：,E,=,TP t,或,TP = E /t,。,仅限于各级执行时,间相等的流水线,3.3,流水线的性能指标,例：一个,5,级的线性流水线，可完成两个数相加运算。现要进行,8,个操作数连续相加运算，如何实现？性能如何？,分析：,若按,M=A+B+C+D+E+F+G+H,进行运算，效率很低。,可改为：,M=,（,A+B,）,+,（,C+D,）,+,（,E+F,）,+,（,G+H,）,1,2,3,4,5,6,7,工作时空图：,从时空图中看出，由于输入任务的不连续，全部,7,个任务（指令），经过,18,个时钟周期后完成。如每段执行时间均等于,t,，吞吐率,TP,为：,时间,空间,1,2,3,4,5,6,7,1,2,3,4,5,6,7,1,2,3,4,5,6,7,1,2,3,4,5,6,7,1,2,3,4,5,6,7,1,2,3,18,4,5,6,7,8,9,10,11,12,13,14,15,16,17,S,5,S,1,S,2,S,3,S,4,M=,（,A+B,）,+,（,C+D,）,+,（,E+F,）,+,（,G+H,）,1,2,3,4,5,6,7,这时流水线的加速比为,:,而效率达到：,时间,空间,1,2,3,4,5,6,7,1,2,3,4,5,6,7,1,2,3,4,5,6,7,1,2,3,4,5,6,7,1,2,3,4,5,6,7,1,2,3,18,4,5,6,7,8,9,10,11,12,13,14,15,16,17,S,5,S,1,S,2,S,3,S,4,效率为何仍然不高？,3.3,流水线的性能指标,整个流水线的效率很低的原因：,（,1,） 存在有数据相关，当发生数据相关时，必须等待前一个运算结果产生之后，下一个运算才能开始；,（,2,） 流水线有填入与排空部分，当输入到流水线中的任务不多时，填入与排空部分所占的比例比较大。,练习：线性多功能,静态流水线,，输入任务是不连续的情况，计算流水线的吞吐率、加速比和效率。用,TI,ASC,计算机的多功能静态流水线计算两个向量的点积：,Z,AB,CD,EF,GH,3.3,流水线的性能指标,解：为了尽量减少数据相关性，充分发挥流水线的作用。计算的顺序应该是先做,4,个乘法：,AB,、,CD,、,EF,和,GH,，然后做两个加法,AB,CD,和,EF,GH,，最后求总的结果,Z,。,Z,(AB),(CD),(EF),(GH),1,2,3,4,5,7,6,3.3,流水线的性能指标,从流水线时空图中看到，用,20,个时钟周期完成了,7,个运算。当每一个功能段的延迟时间都为,t,时，,有：,T,k,20,t,，,n,7,。流水线的吞吐率,TP,为,如果采用顺序执行方式，完成一次乘法要用,4,个,t,，完成一次加法要用,6,个,t,，则完成全部运算要用,则流水线的加速比,S,为：,整个流水线共有,8,段，流水线效率,E,为：,效率更低的原因？,原因：,静态流水线造成加法运算必须在乘法运算所有指令流出流水线后才能进行。,解决：,改为,动态流水线,课后任务：,采用动态流水线对其性能进行分析,3.3,流水线的性能指标,四、流水线设计中的若干问题：,瓶颈问题,当流水线各段不均匀时，,机器的时钟周期取决于瓶颈段的延迟时间。,在设计流水线时，要尽可能使各段时间相等。,流水线的额外开销,流水寄存器延迟,时钟偏移开销,冲突问题,流水线设计中要解决的,重要问题之一。,3.4,流水线的相关与冲突,一、一个经典的,5,段流水线,一条指令的执行过程分为,5,个周期：取指令周期（,IF,）、指令译码,/,读寄存器周期（,ID,）、执行,/,有效地址计算周期（,EX,）、存储器访问分支完成周期（,MEM,）、,写回周期（,WB,）。,3.4,流水线的相关与冲突,三类指令对,5,级流水线的占用情况,:,ALU,指令,LOAD/STORE,BRANCH,IF(S,1,),取指,取指,取指,ID(S,2,),译码,读寄存器堆,译码,读寄存器堆,译码,读寄存器堆,EX(S,3,),执行,计算有效地址,计算转移目标地址,设置条件码,MEM(S,4,),-,访存,(,读或写,),若条件成立,将转移目标地址送,PC,WB(S,5,),结果写回寄存器堆,读出数据写入寄存器堆,-,3.4,流水线的相关与冲突,5,段流水线的两种描述方式,第一种描述,（类似于时空图）,3.4,流水线的相关与冲突,第二种描述,（按时间错开的数据通路序列）,3.4,流水线的相关与冲突,二、相关,相关是指两条指令之间存在某种依赖关系。,从对流水线的分析中可以发现，如果流水线始终处于,“,充满,”,的状态，实际性能可以达到或接近理论值。如果流入流水线的指令出现断流，将极大地影响流水线的性能。,造成断流的原因主要是三大类,:,1,）名相关,2,）数据相关,3,）控制相关,3.4,流水线的相关与冲突,1,、名相关,名：,指令所访问的寄存器或存储器单元的名称。,如果两条指令使用相同的名，但是它们之间并没有数据流动，则称这两条指令存在,名相关。,3.4,流水线的相关与冲突,指令,j,（在后）与指令,i,（在前）之间的名相关有两种：,反相关：,如果指令,j,写的名与指令,i,读的名相同，则称指令,i,和,j,发生了反相关。,指令,j,写的名指令,i,读的名,如：,DIV.D F2,，,F6,，,F4,ADD.D,F6,，,F0,，,F12,3.4,流水线的相关与冲突,输出相关：,如果指令,j,和指令,i,写相同的名，则称指令,i,和,j,发生了输出相关。,指令,j,写的名指令,i,写的名,名相关的两条指令之间并没有数据的传送。,如果一条指令中的名改变了，并不影响另外一条指令的执行。,但名相关的两条指令之间的执行顺序必须严格遵守。,解决方法,:,换名技术：,通过改变指令中操作数的名来消除名相关。,例如：考虑下述代码：,DIV.DF2,，,F6,，,F4,ADD.D,F6,，,F0,，,F12,SUB.DF8,，,F6,，,F14,DIV.D,和,ADD.D,存在反相关。,进行寄存器换名（,F6,换成,S,）后，变成：,DIV.DF2,，,F6,，,F4,ADD.D,S,，,F0,，,F12,SUB.DF8,，,S,，,F14,3.4,流水线的相关与冲突,2,、数据相关,对于两条指令,i,（在前）和,j,（在后），如果下述条件之一成立，则称,指令,j,与,指令,i,数据相关。,指令,j,使用指令,i,产生的结果；,指令,j,与指令,k,数据相关，而指令,k,又与指令,i,数据相关。,数据相关具有,传递性。,数据相关反映了数据的流动关系，即如何从其产生者流动到其消费者。,例如：下面这一段代码存在数据相关,Loop,：,L.D,F0,，,0,（,R1,）,/ F0,为数组元素,ADD.D,F4,，,F0,，,F2,/,加上,F2,中的值,S.D 0,（,R1,），,F4,/,保存结果,DADDIU,R1,，,R1,，,8,/,数组指针递减,8,个字节,BNE,R1,，,R2,，,Loop,/,如果,R1R2,，则分支,3.4,流水线的相关与冲突,当数据的流动是经过寄存器时，相关的检测比较直观和容易。,当数据的流动是经过存储器时，检测比较复杂。,相同形式的地址其有效地址未必相同。,形式不同的地址其有效地址却可能相同。,3.4,流水线的相关与冲突,3.4,流水线的相关与冲突,3,、控制相关,控制相关,是指由分支指令引起的相关。,典型的程序结构是,“,if-then,”,结构,。,控制相关带来了以下,两个限制：,与一条分支指令控制相关的指令不能被移到该分支之前，否则这些指令就不受该分支控制了。,如果一条指令与某分支指令不存在控制相关，就不能把该指令移到该分支之后。,3.4,流水线的相关与冲突,三、流水线冲突,流水线冲突,是指对于具体的流水线来说，由于相关的存在，使得指令流中的下一条指令不能在指定的时钟周期执行。,流水线冲突有,3,种类型：,结构冲突,数据冲突,控制冲突,3.4,流水线的相关与冲突,（一）,结构冲突,指多条指令进入流水线后，在同一时间争用同一功能部件，从而发生冲突。,1 2 3 4 5 6 7 8,指令,LOAD,IF ID EX,MEM,WB,指令,i+1,IF ID EX MEM WB,指令,i+2,IF ID EX MEM WB,指令,i+3,IF,ID EX MEM WB,指令,i+4,IF ID EX MEM,访存冲突,3.4,流水线的相关与冲突,3.4,流水线的相关与冲突,解决方法：,暂停一拍（也称为流水线气泡，简称气泡）。,1 2 3 4 5 6 7 8 9,指令,LOAD,IF ID EX,MEM,WB,指令,i+1,IF ID EX MEM WB,指令,i+2,IF ID EX MEM WB,指令,i+3,停顿,IF,ID EX MEM WB,指令,i+4,IF ID EX MEM,3.4,流水线的相关与冲突,3.4,流水线的相关与冲突,（二）,数据冲突,1,、数据冲突,指由于流水线中各指令重叠执行，使得原来对操作数的访问顺序发生变化，从而引起的一种数据冲突。,如：,DADD R1,，,R2,，,R3,DSUB R4,，,R1,，,R5,1 2 3 4 5 6,DA,DD,IF ID EX MEM,WB,DSUB,IF,ID,EX MEM WB,写,R1,读,R1,3.4,流水线的相关与冲突,2,、解决办法,采用定向传送技术（旁路技术或相关专用通路技术）。,IF,ID,EX MEM WB,DSUB,IF ID,EX,MEM,WB,DADD,1 2 3 4 5 6,写,R1,读,R1,ALU,运算结果,目标,R,ALU,操作数寄存器,旁路传送,3.4,流水线的相关与冲突,3.4,流水线的相关与冲突,3,、数据冲突类型,根据指令对同一寄存器读和写的先后顺序，数据冲突可分为三种类型：,1,）,RAW,（读超前于写）,指令入,出,1,2,3,4,5,读数,写数,k,j,i,R,i,指令,:,写数,j,指令,:,读数,解决方法一,：按序流动（顺序流动）的流水线中，用定向传送技术。,指流水线中流出的结果与流入指令的次序是一致的。,但是，定向技术并不能解决所有,RAW,冲突。,如装入延迟,：,LD,R1,，,0,（,R2,）,DADD R4,，,R1,，,R5,AND R6,，,R1,，,R7,XOR R8,，,R1,，,R9,解决方法二,：增加流水线互锁硬件，插入,“,暂停,”,。,作用：,检测发现数据冲突，并使,流水线停顿,，直至冲突消失。,解决方法三,：指令调度（流水线调度）,前提,：在非按序流动方式（乱步流动）的流水线中。,具体实现,：通过编译使某些指令的运行结果可能先于,j,指令流出，情况如下,:,指允许输出结果的次序与输入指令的次序不同。,l,k,i,k,j,i,l,指令入,出,1,2,3,4,5,读数,写数,R,i,指令,:,写数,j,指令,:,读数,3.4,流水线的相关与冲突,由于允许非按序执行，使流水线的停顿时间大为减小，有利于提高流水线的吞吐率和效率。但同时还应该注意可能由此引起的另两种冲突,:,2,）,WAR,（写超前于读）,原程序要求对同一单元进行先读后写的操作，可能因为非按序执行成为先写后读，造成出错。,3,）,WAW,（写后写）,原程序中如果两条指令都要对同一单元进行写数操作，可能因为非按序执行的原因，改变了两条指令写入的次序。,3.4,流水线的相关与冲突,（三）控制,冲突,1,、控制冲突,流水线遇到分支指令（转移指令）和其他会改变,PC,值的指令所引起的冲突。,分,支指令的处理,1 2 3 4 5 6 7 8,BRANCH(,转移,),IF ID EX,MEM,WB,指令,i+1,停顿 停顿 停顿,IF ID EX MEM,指令,i+2,停顿 停顿 停顿,IF ID EX,指令,i+3,停顿 停顿 停顿,IF ID,末尾处更新,PC,值,3.4,流水线的相关与冲突,转移指令对流水线的影响,例,:,设在某一程序中， 条件转移指令在程序中所占的比例为,25%,，其中转移成功的概率为,2/3,。试计算执行一条指令的平均时钟周期数。,解：设执行一条指令的平均时钟周期数为,P,i,，则,P,i,=,(1- 25%) 1,+,25%(3+1),= 1.75,3.4,流水线的相关与冲突,2,、有关措施,为了减小分支延迟造成的损失，可采用以下措施：,1,）在流水线中尽早判断出分支转移是否成功。,2,）尽早计算出分支目标地址。,两种措施同时采用，缺一不可。,假设该两步工作被提前到,ID,段完成，即分支指令是在,ID,段的末尾执行完成，所带来的分支延迟为一个时钟周期。,3.4,流水线的相关与冲突,为了减小分支延迟造成的损失，还可通过软件（编译器）来减少分支延迟，常见的有以下几种：,（,1,）预测分支失败,允许分支指令后的指令继续在流水线中流动，就好象什么都没发生似的。,若确定分支失败，将分支指令看作是一条普通指令，流水线正常流动。,若确定分支成功，流水线就把在分支指令之后取出的所有指令转化为空操作，并按分支目地重新取指令执行。,3.4,流水线的相关与冲突,对于上例：,设在某一程序中， 条件转移指令在程序中所占的比例为,25%,，其中转移成功的概率为,2/3,。试计算执行一条指令的平均时钟周期数。,假设采用预测分支失败，则,执行一条指令的平均时钟周期数为,P,i,为：,P,i,=,(1- 25%) 1,+,25%1/3 1,+,25%2/3(1+1), 1.17,3.4,流水线的相关与冲突,（,2,）预测分支成功,假设分支转移成功，并从分支目标地址处取指令执行。,起作用的前题：,先知道分支目标地址，后知道分支是否成功。,前述,5,段流水线中，由于,判断分支是否成功,与,分支目标地址计算,是在同一流水段完成，这种方法没有任何好处,。,3.4,流水线的相关与冲突,（,3,）采用延迟转移技术,方法一：从前调度,DADD R1,，,R2,，,R3,IF R2=0 THEN,延迟槽,IF R2=0 THEN,DADD R1,，,R2,，,R3,方法三：由失败处调度,方法二：从目标处调度,DSUB R4, R5, R6,DADD R1, R2, R3,IF R1=0 THEN,延迟槽,DSUB R4, R5, R6,DADD R1, R2, R3,IF R1=0 THEN,DSUB R4, R5, R6,DADD R1, R2, R3,IF R1=0 THEN,DSUB R4, R5, R6,延迟槽,DADD R1, R2, R3,IF R1=0 THEN,DSUB R4, R5, R6,补充：非线性流水线的竞争与调度,1,、非线性流水线中可能发生的冲突,前馈,反馈,输出,S,4,输入,S,1,S,2,S,3,（,a,） 带前馈和反馈的非线性流水线连线图,（,b,） 一种假定的预约表,1,2,3,4,5,6,7,8,S,1,S,2,S,3,S,4,非线性流水线中由于有些段需要在时间上复用，就不能像线性流水线那样逐时段连续地输入指令。把前一条指令输入开始到下一条指令输入为止的时间差，称为,启动距离,。,如果所采用的启动距离不合适，可能会在某些部件的使用上发生冲突。,前馈,反馈,输出,S,4,输入,S,1,S,2,S,3,（,a,） 带前馈和反馈的非线性流水线连线图,前馈,反馈,输出,S,4,输入,S,1,S,2,S,3,（,a,） 带前馈和反馈的非线性流水线连线图,（,b,） 一种假定的预约表,1,2,3,4,5,6,7,8,S,1,S,2,S,3,S,4,流水线中任何一部件在同一时间段中只能为一条指令服务，出现争用现象是不允许的。,为此必须恰当地选择后一条指令输入的时间，既不使发生冲突，又不致使流水线的效率降低太多。那些会引起冲突的启动距离，被称为,禁止启动距离,。,将在任何时间都不会发生冲突的启动距离称为,启动循环,。,2,、最优调度方法,为了避免冲突，就要对指令输入流水线的时间进行控制，这个任务就是流水线的无冲突调度。,1,）根据预约表写出禁止向量,禁止向量,F,是一个流水线中所有禁止启动距离的集合。为了找出所有的禁止启动距离，必须考察各段的复用情况。,S1,在,1,，,4,，,7,三个时段中使用，从第,1,时段到第,4,时段的距离为,3,t,（,4,t,1,t,= 3,t,）,，显然这是一个禁止启动距离。,1,2,3,4,5,6,7,8,S,1,S,2,S,3,S,4,同样理由，可以得到,S1,的另外两个禁止启动距离：,7t,4t = 3t,；,7t,1t = 6t,。,将这种计算所有打,“,”,时段之间距离的方法施于其他三个部件，可以得到下面的结果,:,S2,的禁止启动距离：,3,t,S3,的禁止启动距离：,t,，,3t,，,4t,禁止向量,F =,（,1, 3, 4, 6,）,1,2,3,4,5,6,7,8,S,1,S,2,S,3,S,4,向量规定，如果某启动距离为禁止距离，则该位为,“,1,”,，反之则为,“,0,”,。于是，根据禁止向量，可以得到与之对应的初始冲突向量。,如上例中，,禁止向量,F =,（,1, 3, 4, 6,）,，则对应的,初始冲突向量,C,=,（,101101,）,。,由于第,2,、,5,位为,“,0,”,，因此，可以与当前指令间隔,2,拍（,2,t,）或,5,拍调入下一个指令。,2,） 由禁止向量变换成初始冲突向量,用以表示非线性流水线工作时各启动距离特性的二进制序列，称为,冲突向量,。由预约表上第一条指令工作过程所求得的冲突向量称为,初始冲突向量,。,冲突向量用,C,=,（,C,m,C,m,-1,C,2,C,1,）,表示，其中,m,为禁止向量的最大值，如果执行一条指令需要,k,个时段，那末,m,k,1,。于是，冲突向量的各位就可以理解为,C,1,表示启动距离为,1,t,时的冲突情况；,C,2,是启动距离为,2,t,时的冲突情况；,3,）根据初始冲突向量推算出全部冲突向量,按照某一个无冲突启动距离输入后续指令后，由于在流水线中存在一条以上指令，使各部件的使用趋于复杂，也必然造成冲突情况发生改变。为了保证后续指令的正常输入，必须找出所有变化了的冲突向量。,根据例子，初始冲突向量,C,0 =,（,101101,），由于第,2,、,5,位为,“,0,”,，因此，可以与当前指令间隔,2,拍（,2,t,）或,5,拍调入下一个指令。,若选择第,2,条指令在,2,拍后调入流水线：,1,2,3,4,5,6,7,8,S,1,S,2,S,3,S,4,第一条指令的当前禁止向量：,F =,（,1,-2,3,-2,4,-2,6,-2,）,=,（,1,，,2,，,4,）,则此时初始冲突向量应该逻辑右移两位，形成第一条指令的当前冲突向量。如（,C0 =,（,101101,），即：,为使第,3,条指令调入后不与前两条指令发生冲突，新的冲突向量应该是第,1,条指令的当前冲突向量与第,2,条指令的初始冲突向量按位进行,“,或,”,运算。,对,C,1,继续推算新的冲突向量，因为其中只有一个,0,，,后续向量也只有一个。,在这个例子中，完成了全部推算后，只找到一个新的冲突向量,C,1,。,4,）,画出表示冲突向量迁移的有向图,101101,101111,C,1,C,0,2,5,5,3.5,流水线的实现,MIPS,的一种简单实现,一,.,实现,MIPS,指令子集的,一种简单数据通路,。（,P87,图,3.43,）,该数据通路的操作分成,5,个时钟周期,取指令,指令译码,/,读寄存器,执行,/,有效地址计算,存储器访问,/,分支完成,写回,只讨论整数指令的实现,（包括：,load,和,store,，等于,0,转移，整数,ALU,指令等。）,3.5,流水线的实现,二,.,一条,MIPS,指令最多需要以下,5,个时钟周期：,1.,取指令周期,（,IF,）,IR,MemPC,NPC,PC+4,2.,指令译码,/,读寄存器周期,（,ID,）,A,Regsrs,B,Regsrt,Imm,（,IR,16,）,16,#,IR,16.31,）,指令的译码操作和读寄存器操作是并行进行的。,原因：在,MIPS,指令格式中，操作码字段以及,rs,、,rt,字段都是在固定的位置。这种技术称为,固定字段译码,技术。,3.5,流水线的实现,3.,执行,/,有效地址计算周期,（,EX,）,不同指令所进行的操作不同：,存储器访问指令,ALUo,A + Imm,寄存器寄存器,ALU,指令,ALUo,A func B,寄存器立即值,ALU,指令,ALUo,A op Imm,分支指令,ALUo,NPC+,（,Imm2,）；,cond,（,A =,= 0,）,将有效地址计算周期和执行周期合并为一个时钟周期，这是因为,MIPS,指令集采用,load,store,结构，没有任何指令需要同时进行数据有效地址的计算、转移目标地址的计算和对数据进行运算。,3.5,流水线的实现,4.,存储器访问,/,分支完成周期,（,MEM,）,所有指令都要在该周期对,PC,进行更新。除了分支指令，其他指令都是做,PC,NPC,。,在该周期内处理的,MIPS,指令仅仅有,load,、,store,和分支,三种指令。,（,1,）存储器访问指令,LMD,MemALUo,或者,MemALUo,B,（,2,）分支指令,if,（,cond,）,PC,ALUo else PC,NPC,3.5,流水线的实现,5.,写回周期,（,WB,）,不同的指令在写回周期完成的工作也不一样。,寄存器寄存器,ALU,指令,Regsrd,ALUo,寄存器立即数,ALU,指令,Regsrt,ALUo,load,指令,Regsrt,LMD,3.5,流水线的实现,不采用单周期实现方案的,主要原因,1.,对于大多数,CPU,来说，单周期实现效率很低，因为不同的指令所需完成的操作差别相当大，因而所需要的时钟周期时间也大不一样。,2.,单周期实现时，需要重复设置某些功能部件，而在多周期实现方案中，这些部件是可以共享的。,练习：,在一个如下图所示的线性流水线,各级运行所需的时间如下图中所标,。,1,）画出该流水线工作时空图。,2,）如果输入的程序没有数据相关和转移指令，在连续执行,10,条指令后，计算该流水线的吞吐率和效率。,3,）提出改进吞吐率、加速比和效率的方法，并计算改进后的性能（即改进后的吞吐率、加速比和效率）。,取指,D,t,译码,D,t,执行,2,D,t,写回,2,D,t,解：,在一个如下图所示的线性流水线,各级运行所需的时间如下图中所标。,取指,D,t,译码,D,t,执行,2,D,t,写回,2,D,t,1,）画出该流水线工作时空图。,时间,0,t,1,t,2,t,3,