研究生入学考试四川大学计算机系统结构学习教案.pptx

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,11/7/2009,#,#,单击此处编辑母版标题样式,会计学,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,会计学,1,研究生入学考试四川大学(s chun d xu)计算机系统结构,第一页，共177页。,3.1 重叠执行(zhxng)和先行控制,如果连续执行一段程序(chngx)，计算机对前后相邻指令的执行过程可以有两种不同的选择:,1.顺序执行方式，即等前一条指令执行完毕，紧接着执行下一条指令.,2.让前后连续的指令(zhlng)在处理机内以重叠的方式执行.,取指,分析,执行,取指,分析,执行,k,+1,k,第1页/共177页,第二页，共177页。,3.1 重叠执行(zhxng)和先行控制,一次重叠(chngdi)执行方式:,二次重叠执行(zhxng)方式:,取指,分析,执行,取指,分析,执行,取指,分析,执行,第,k,条指令,第,k,+1,条指令,第,k,+2,条指令,取指,分析,执行,取指,分析,执行,取指,分析,执行,第,k,条指令,第,k,+1,条指令,第,k,+2,条指令,如果三个阶段所需时间,t,相等，,N,条指令顺序执行的时间为：,T=3Nt,。,一次重叠执行的时间：,T=(1+2N)t,。,二次重叠执行的时间为：,T=,（,2+N)t,。,第2页/共177页,第三页，共177页。,3.1 重叠(chngdi)执行和先行控制,二.先行控制技术,1实现重叠执行存在的问题,（1）问题一：,需要独立(dl)的取指部件，分析部件，执行部件。,解决方案:,设置对应存储控制器，指令控制器和运算控制器。,第3页/共177页,第四页，共177页。,3.1 重叠(chngdi)执行和先行控制,（2）问题二：,主存访问冲突(chngt),取指令时，处理机必须按指令计数器的指示访问存储器；,分析指令时，可能需要从存储器中获取操作数；,执行指令时，也可能要求将结果写回到存储器中。,处理机中三个独立的部件可能同时提出对存储器读写的请求，从而发生存储器访问冲突(chngt)。,第4页/共177页,第五页，共177页。,3.1 重叠执行(zhxng)和先行控制,解决方案：,1）分别设置两个独立的存储器：指令存储器和数据存储器，或一级Cache分为程序Cache和数据Cache，同时工作解决同时读指令和读数据引起的冲突。,程序空间和数据空间相互独立并具有独立的指令总线和数据总线的系统结构就称为哈佛结构,缺点：结构复杂，需要大量(dling)的数据线，对汇编程序员和机器程序员不透明,2）多体交叉存储器结构也可减少冲突的发生。,3）先行控制技术是最根本的办法。,第5页/共177页,第六页，共177页。,3.1 重叠(chngdi)执行和先行控制,在复杂的计算机指令系统中，各种指令在分析和执行阶段所需的时间可能(knng)有很大的差别。于是，前面对三个阶段所需时间t相等的假设就可能(knng)不成立，所得到的节约三分之二时间的结论也被动摇了。下图形象地表示了这种情况所造成的影响。,第,k,条指令,分析,执行,第,k,+2,条指令,执行,分析,第,k,+1,条指令,分析,执行,这种情况可用先行(xinxng)控制技术来缓解。,第6页/共177页,第七页，共177页。,3.1 重叠执行和先行(xinxng)控制,2采用(ciyng)先行控制技术的处理机,运算控制器,先 行 指 令 栈,后 行 写 数 栈,先 行 读 数 栈,存 储 控 制 器,去主存储器,地址线,指 令 分 析 器,先行操作栈,运 算 器,通 用 寄 存 器,第7页/共177页,第八页，共177页。,3.1 重叠执行(zhxng)和先行控制,缓冲栈实际上是一个以先进先出（FIFO）方式工作的移位寄存器组，上图表示了缓冲栈所处的地位。前置部件的输出(shch)不直接送入后置部件，而是通过缓冲栈暂存后才输出(shch)。,前置部件,后置部件,缓冲栈,第8页/共177页,第九页，共177页。,运算控制器,先 行 指 令 栈,后 行 写 数 栈,先 行 读 数 栈,存 储 控 制 器,去主存储器,地址线,指 令 分 析 器,先行操作栈,运 算 器,通 用 寄 存 器,3.1 重叠执行和先行(xinxng)控制,3先行(xinxng)控制原理,通过先行(xinxng)指令计数器PC1预取指令序列,通过现行指令计数器,PC,取出现行指令,指令分析器,指令分析器,:,对取自先行指令栈的指令进行预处理,.,1.,对于程序控制类的指令，如转移指令，指今分析器可以直接完成指令的执行,.,2.,对于数据运算型指令，指令分析器要将它们变换成寄存器寄存器型,(RR,型,),指令，即将操作数预先存到寄存器中，使指令能快速执行,.,立即寻址,传数据,变址寻址或存储器型指令,传地址,RR*,指令,第9页/共177页,第十页，共177页。,3.1 重叠执行(zhxng)和先行控制,先行控制技术中采取了两个根本的措施：指令预处理技术和缓冲(hunchng)技术。由于指令和数据的缓冲(hunchng)，保证了指令分析和指令的执行都能全速地运行。,第,k,条指令,分析,执行,第,k,+2,条指令,执行,分析,第,k,+1,条指令,分析,执行,缓冲栈深度应满足(mnz)以下关系：,D取指栈D操作栈D读栈D写栈,第,k,条指令,分析,执行,第,k,+2,条指令,执行,分析,第,k,+1,条指令,分析,执行,第10页/共177页,第十一页，共177页。,3.2,流水线的基本概念,一.什么是流水线,1.流水线技术（pipelining）,把一个重复的过程分解为若干个子过程，每个子过程由专门的功能部件(bjin)来实现。,把多个处理过程在时间上错开，依次通过各功能段，这样，每个子过程就可以与其他的子过程并行进行。,流水线中的每个子过程及其功能部件(bjin)称为流水线的级或段，段与段相互连接形成流水线。流水线的段数称为流水线的深度。,第11页/共177页,第十二页，共177页。,3.2,流水线的基本概念,2流水线结构,重叠(chngdi)执行是流水线结构的思想基础，只要在指令分析器与指令执行部件之后都加上一个锁存器，就成了一个简单的流水线结构。,指令执行部件,指令分析器,锁存器,锁存器,分析,k,+1,执行,k,t,2,t,1,结果出,指令入,在流水线的每一个功能部件的后面都要有一个缓冲寄存器，或称为锁存器、闸门寄存器等，它的作用是保存(bocn)本流水段的执行结果。,第12页/共177页,第十三页，共177页。,3时空图,时空图可以(ky)直观地表现流水线的工作过程,横轴表示时间(shjin)，即各条指令在处理机中经历各个操作时占用的时间(shjin)段。如果各级执行所需的时间(shjin)相等，在横轴上应表现为等距离的时间(shjin)段。,纵轴表示空间，即流水线的各个子操作过程，通常也称为“功能段”。,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,填入,填满,排空,第13页/共177页,第十四页，共177页。,3.2,流水线的基本概念,4流水线的工作特点,1）一条流水线通常由多个流水段组成，在每一个流水段有专门的功能部件来实现。,2）各流水段所需的时间应尽可能相等，否则将引起流水线堵塞、断流。,3）流水线每个功能部件后面都有一个缓冲寄存器，称为流水寄存器。,4）流水线的工作一般分为3个阶段，即建立（填入）、填满和排空。,5）流水线技术适合于大量重复的时序过程，只有在输入端不断地提供任务(rn wu)，才能充分发挥流水线的效率。,第14页/共177页,第十五页，共177页。,3.2,流水线的基本概念,二.流水线的种类,1、按处理机分类,操作部件级,为最低级别的流水线。是把处理机的算术逻辑运算部件分段。如果某一部件的处理过程比较复杂，如浮点运算,需要较长的时间。这时可以将该部件分为若干子部件，分别完成浮点运算中有关(yugun)的子操作，这种在部件范围内形成的流水线称为操作部件级流水线。,第15页/共177页,第十六页，共177页。,3.2,流水线的基本概念,一个(y)浮点加法部件的流水线：,求阶差,对阶,尾数加,规格化,入,出,部件(bjin)级流水线通常是流水线处理机中的一部分，这时的处理机由于流水级数较多，又称为超流水线处理机。,第16页/共177页,第十七页，共177页。,3.2,流水线的基本概念,处理机级,又称为(chn wi)指令流水线，就是将一条指令的解释执行过程分解成若干个子过程，使每个子过程分别在一个部件中完成。,处理机间级,处理机间流水线通常是多处理机系统中对任务采取的一种处理策略。,第17页/共177页,第十八页，共177页。,3.2,流水线的基本概念,上图是处理机间流水(lishu)线示意图，图中每个处理机是以任务为单位进行处理的，而处理机间的任务传递则是由公用存储器完成的。应当指出，图中给出的是一个处理的“流水(lishu)”，并没有涉及更多的硬件结构。实际上这个过程更应该看作是一种任务的调度策略。,处理机,2,M,处理机,n,M,输出,处理机,1,M,输入,任务,1,任务,2,任务,n,第18页/共177页,第十九页，共177页。,3.2,流水线的基本概念,2、按流水线功能多少分类,单功能流水线,指一条流水线只能完成一种单一的任务。,多功能流水线,指能够在一个时间段内或不同(b tn)时间段间改变部件之间的连接，从而达到改变其功能的流水线。,第19页/共177页,第二十页，共177页。,3.2,流水线的基本概念,在标量运算中，各种(zhn)运算是混在一起的。,第20页/共177页,第二十一页，共177页。,3、按照工作方式分类,静态流水线,当执行某一规定(gudng)功能的指令全部流出后，才允许改变部件间连接的流水线。,（可以(ky)是单功能流水线也可以(ky)是多功能流水线）,第21页/共177页,第二十二页，共177页。,3.2,流水线的基本概念,动态流水线,没有(mi yu)这种时间上的限制，可以在任何时候根据需要改变其连接。,（只能(zh nn)是多功能流水线）,第22页/共177页,第二十三页，共177页。,3.2,流水线的基本概念,4、按连接方式分类,线性流水线,是指在部件(bjin)上没有反馈连接的流水线。在这种流水线中，指令依次通过各个部件(bjin)仅一次，完成指令执行的全过程。目前所使用的流水线绝大部分都是这类线性流水线。,非线性流水线,是指在各部件(bjin)除了串行的连接外，还通过反馈线使某些部件(bjin)得以重复使用。指令在通过这种流水线时，可能在反馈部件(bjin)上重复运行若干次。,第23页/共177页,第二十四页，共177页。,3.2,流水线的基本概念,反馈回路,S1,S2,S3,入,出,S3,S1,S2,时间,非线性流水线工作(gngzu)特性示意图,第24页/共177页,第二十五页，共177页。,3.2,流水线的基本概念,5、按流入流出顺序分类,顺序流水线,其输出的结果(ji gu)与输入的次序相同，早期的流水线又称为顺序流水线。,乱序流水线,将原始的输入次序打乱，以最有利于处理机执行的方式运行，在输出结果(ji gu)时才恢复原次序。,在一些现代处理机中，如Pentium 4在流水线运行过程中采用了乱序方式。,第25页/共177页,第二十六页，共177页。,3.2,流水线的基本概念,除了上述几种分类方法以外，还可以根据各种不同的观点对流水线进行(jnxng)区分。比如：,按照数据表示方式的不同，可以将流水线分为标量流水线和向量流水线两种。在标量处理机中使用的当然是标量流水线。,根据流水线在各级之间流动时的控制方法不同，又可以分成同步和异步两种流水线。,第26页/共177页,第二十七页，共177页。,3.2,流水线的基本概念,处理机内的指令流水线都是同步流水线，即使用(shyng)统一的时钟控制各级同时开始同时完成动作。,而处理机间的流水线通常都是异步流水线，需要在任务传送时进行应答，以确保传输的可靠性。,第27页/共177页,第二十八页，共177页。,3.3,流水线的性能指标,吞吐率、加速比和效率是表明(biomng)流水线性能的主要指标。,一.吞吐率,把流水线在单位时间内完成的任务量定义为吞吐率。,k,T,n,TP,=,其中,n为完成任务的总数，在指令流水线中就是(jish)完成的指令总条数；Tk是完成n个任务所用的时间。,第28页/共177页,第二十九页，共177页。,3.3,流水线的性能指标,各级(j)执行时间相等的流水线,一条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,所需的总时间(shjin)为：,第29页/共177页,第三十页，共177页。,3.3,流水线的性能指标,当n时，（k 1）可以忽略不计，得到(d do)的最大吞吐率为:,t,t,n,k,n,TP,n,D,=,D,-,+,=,1,),1,(,lim,max,所以(suy)，吞吐率为:,t,n,k,n,TP,D,-,+,=,),1,(,第30页/共177页,第三十一页，共177页。,3.3,流水线的性能指标,各级(j)执行时间不等的流水线,执行(zhxng)时间不等的流水线时空图,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,第31页/共177页,第三十二页，共177页。,3.3,流水线的性能指标,吞吐(tnt)率的一般表示式为:,同样方法可以(ky)得到当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,=,第32页/共177页,第三十三页，共177页。,3.3,流水线的性能指标,如果流水线中各级的执行时间不相等，其中时间最长者就成了流水线中的“瓶颈”。瓶颈问题对流水线的吞吐率影响是明显的，所以消除“瓶颈”是设计流水线的一个重要原则。,“瓶颈”问题的消除,采用的方法主要有两种：,1）分割瓶颈部件的工作(gngzu),2）重复设置瓶颈部件,第33页/共177页,第三十四页，共177页。,3.3,流水线的性能指标,消除(xioch)“瓶颈”影响的两种方法示意图：,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,两种方式(fngsh)在效果上是可以等效的，在输入n条指令的情况下，实际吞吐率都为：,t,n,n,t,n,n,TP,D,+,=,D,-,+,=,),5,(,),1,6,(,第34页/共177页,第三十五页，共177页。,3.3,流水线的性能指标,不消除“瓶颈(pn jn)”时的吞吐率：,两种方式在效果上是可以(ky)等效的，在输入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,),(,第35页/共177页,第三十六页，共177页。,3.3,流水线的性能指标,二.加速比,处理同一批任务，不用流水线与采用(ciyng)流水线时所花费的时间之比，称为流水线的加速比。,如果不用流水线所用的时间为T0，用了流水线所用时间为Tk，那么加速比就是：,S=T0/Tk,第36页/共177页,第三十七页，共177页。,3.3,流水线的性能指标,不用流水线时，每条指令执行时必须(bx)在时间上顺序地完成各处理步骤，那么n条指令所需时间就为T0=nkt。而一个采用流水线的处理机所需时间为Tk=(k+n 1)t。,所以加速比就为,1,),1,(,0,-,+,=,D,-,+,D,=,=,n,k,n,k,t,n,k,t,k,n,T,T,S,k,同样(tngyng)办法可以得到最大加速比,k,n,k,n,k,S,n,=,-,+,=,1,lim,max,第37页/共177页,第三十八页，共177页。,3.3,流水线的性能指标,如果考虑各级执行时间不等的情况时，一条(y tio)指令的执行时间是各级运行时间之和。在没有流水线时，n条指令应是一条(y tio)指令的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,(,第38页/共177页,第三十九页，共177页。,3.3,流水线的性能指标,三.效率(xio l),效率(xio l)被定义为：,空区,个流水线级占用的总时,条指令占用的时空区,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,各级(j)执行时间相等的流水线效率等于：,1,),1,(,-,+,=,D,-,+,D,=,n,k,n,t,n,k,k,t,k,n,E,第39页/共177页,第四十页，共177页。,3.3,流水线的性能指标,显然，n越大，空闲部件(bjin)占据的比例就小，流水线表现的效率越高。最高效率为：,1,1,lim,max,=,-,+,=,n,k,n,E,n,通过(tnggu)类似的分析方法，我们也可以得到在各 级执行时间不等的流水线中的效率计算方法。,=,=,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,(,第40页/共177页,第四十一页，共177页。,3.3,流水线的性能指标,同样(tngyng)，,效率(xio l)公式：,加速(ji s)比公式：,两者相结合得出：,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,。,仅限于各级执行时,间相等的流水线,第41页/共177页,第四十二页，共177页。,3.3,流水线的性能指标,例：一个5级的线性流水线，可完成两个数相加运算。现要进行(jnxng)8个操作数连续相加运算，如何实现？性能如何？,分析：,若按M=A+B+C+D+E+F+G+H进行(jnxng)运算，效率很低。,可改为：,M=（A+B）+（C+D）+（E+F）+（G+H）,1,2,3,4,5,6,7,第42页/共177页,第四十三页，共177页。,工作(gngzu)时空图：,从时空图中看出，由于(yuy)输入任务的不连续，全部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,第43页/共177页,第四十四页，共177页。,这时流水线的加速(ji s)比为:,而效率(xio l)达到：,时间,空间,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,效率(xio l)为何仍然不高？,第44页/共177页,第四十五页，共177页。,3.3,流水线的性能指标,整个流水线的效率很低的原因：,（1）存在有数据相关，当发生数据相关时，必须等待前一个运算结果产生之后，下一个运算才能开始；,（2）流水线有填入与排空部分，当输入到流水线中的任务不多时，填入与排空部分所占的比例(bl)比较大。,第45页/共177页,第四十六页，共177页。,练习：线性多功能静态流水线，输入(shr)任务是不连续的情况，计算流水线的吞吐率、加速比和效率。用TIASC计算机的多功能静态流水线计算两个向量的点积：,ZABCDEFGH,第46页/共177页,第四十七页，共177页。,3.3,流水线的性能指标,解：为了尽量减少数据相关性，充分发挥流水线的作用。计算的顺序应该是先做4个乘法：AB、CD、EF和GH，然后做两个(lin)加法ABCD和EFGH，最后求总的结果Z。,Z,(AB),(CD),(EF),(GH),1,2,3,4,5,7,6,第47页/共177页,第四十八页，共177页。,3.3,流水线的性能指标,从流水线时空图中看到，用20个时钟(shzhng)周期完成了7个运算。当每一个功能段的延迟时间都为t时，,第48页/共177页,第四十九页，共177页。,有：Tk20 t，n7。流水线的吞吐(tnt)率TP为,如果采用(ciyng)顺序执行方式，完成一次乘法要用4个t，完成一次加法要用6个t，则完成全部运算要用,则流水线的加速(ji s)比S为：,整个流水线共有,8,段，流水线效率,E,为：,效率更低的原因？,第49页/共177页,第五十页，共177页。,原因：静态流水线造成加法运算必须在乘法运算所有指令流出流水线后才能进行(jnxng)。,解决：改为动态流水线,课后任务：采用动态流水线对其性能进行(jnxng)分析,第50页/共177页,第五十一页，共177页。,3.3,流水线的性能指标,四、流水线设计(shj)中的若干问题：,瓶颈问题,当流水线各段不均匀时，机器的时钟周期取决于瓶颈段的延迟时间。,在设计(shj)流水线时，要尽可能使各段时间相等。,流水线的额外开销,流水寄存器延迟,时钟偏移开销,冲突问题,流水线设计(shj)中要解决的重要问题之一。,第51页/共177页,第五十二页，共177页。,3.4 流水线的相关(xinggun)与冲突,一、一个经典的5段流水线,一条指令的执行过程分为5个周期：取指令周期（IF）、指令译码/读寄存器周期（ID）、执行/有效地址计算(j sun)周期（EX）、存储器访问分支完成周期（MEM）、写回周期（WB）。,第52页/共177页,第五十三页，共177页。,3.4 流水线的相关(xinggun)与冲突,三类指令对5级流水线的占用(zhn yn)情况:,ALU,指令,LOAD/STORE,BRANCH,IF(S1),取指,取指,取指,ID(S2),译码,读寄存器堆,译码,读寄存器堆,译码,读寄存器堆,EX(S3),执行,计算有效地址,计算转移目标地址,设置条件码,MEM(S4),-,访存,(,读或写,),若条件成立,将转移目标地址送,PC,WB(S5),结果写回寄存器堆,读出数据写入寄存器堆,-,第53页/共177页,第五十四页，共177页。,3.4 流水线的相关(xinggun)与冲突,5段流水线的两种描述方式(fngsh),第一种描述（类似于时空图）,第54页/共177页,第五十五页，共177页。,3.4 流水线的相关(xinggun)与冲突,第二种描述（按时间错开(cu ki)的数据通路序列）,第55页/共177页,第五十六页，共177页。,3.4 流水线的相关(xinggun)与冲突,二、相关,相关是指两条指令之间存在某种依赖关系。,从对流水线的分析中可以发现，如果流水线始终处于“充满”的状态，实际性能可以达到或接近理论值。如果流入流水线的指令出现断流，将极大地影响流水线的性能。,造成断流的原因主要(zhyo)是三大类:,1）名相关,2）数据相关,3）控制相关,第56页/共177页,第五十七页，共177页。,3.4 流水线的相关(xinggun)与冲突,1、名相关,名：指令所访问的寄存器或存储器单元的名称。,如果两条指令使用相同的名，但是它们(t men)之间并没有数据流动，则称这两条指令存在名相关。,第57页/共177页,第五十八页，共177页。,3.4 流水线的相关(xinggun)与冲突,指令(zhlng)j（在后）与指令(zhlng)i（在前）之间的名相关有两种：,反相关：如果指令(zhlng)j写的名与指令(zhlng)i读的名相同，则称指令(zhlng)i和j发生了反相关。,指令(zhlng)j写的名指令(zhlng)i读的名,如：DIV.D F2，F6，F4,ADD.D F6，F0，F12,第58页/共177页,第五十九页，共177页。,3.4 流水线的相关(xinggun)与冲突,输出相关：如果指令j和指令i写相同的名，则称指令i和j发生了输出相关。,指令j写的名指令i写的名,名相关的两条指令之间并没有数据的传送。,如果一条指令中的名改变(gibin)了，并不影响另外一条指令的执行。,但名相关的两条指令之间的执行顺序必须严格遵守。,第59页/共177页,第六十页，共177页。,解决方法:,换名技术：通过改变指令中操作数的名来消除名相关。,例如：考虑下述代码：,DIV.DF2，F6，F4,ADD.DF6，F0，F12,SUB.DF8，F6，F14,DIV.D和ADD.D存在(cnzi)反相关。,进行寄存器换名（F6换成S）后，变成：,DIV.DF2，F6，F4,ADD.DS，F0，F12,SUB.DF8，S，F14,第60页/共177页,第六十一页，共177页。,3.4 流水线的相关(xinggun)与冲突,2、数据相关,对于两条指令i（在前）和j（在后），如果下述条件之一成立，则称指令j与指令i数据相关。,指令j使用指令i产生的结果(ji gu)；,指令j与指令k数据相关，而指令k又与指令i数据相关。,数据相关具有传递性。,数据相关反映了数据的流动关系，即如何从其产生者流动到其消费者。,第61页/共177页,第六十二页，共177页。,例如：下面这一段代码存在数据相关,Loop：L.D F0，0（R1）/F0为数组元素,ADD.D F4，F0，F2/加上F2中的值,S.D 0（R1），F4/保存结果,DADDIU R1，R1，8 /数组指针递减(djin)8个字节,BNE R1，R2，Loop /如果R1R2，则分支,3.4 流水线的相关(xinggun)与冲突,第62页/共177页,第六十三页，共177页。,当数据的流动是经过寄存器时，相关的检测比较直观(zhgun)和容易。,当数据的流动是经过存储器时，检测比较复杂。,相同形式的地址其有效地址未必相同。,形式不同的地址其有效地址却可能相同。,3.4 流水线的相关(xinggun)与冲突,第63页/共177页,第六十四页，共177页。,3.4 流水线的相关(xinggun)与冲突,3、控制相关,控制相关是指由分支指令引起的相关。,典型的程序结构是“if-then”结构。,控制相关带来了以下两个限制：,与一条(y tio)分支指令控制相关的指令不能被移到该分支之前，否则这些指令就不受该分支控制了。,如果一条(y tio)指令与某分支指令不存在控制相关，就不能把该指令移到该分支之后。,第64页/共177页,第六十五页，共177页。,3.4 流水线的相关(xinggun)与冲突,三、流水线冲突,流水线冲突是指对于具体的流水线来说，由于相关的存在，使得指令流中的下一条指令不能在指定的时钟周期(zhuq)执行。,流水线冲突有3种类型：,结构冲突,数据冲突,控制冲突,第65页/共177页,第六十六页，共177页。,3.4 流水线的相关(xinggun)与冲突,（一）结构冲突,指多条指令进入(jnr)流水线后，在同一时间争用同一功能部件，从而发生冲突。,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,访存冲突(chngt),第66页/共177页,第六十七页，共177页。,3.4 流水线的相关(xinggun)与冲突,第67页/共177页,第六十八页，共177页。,3.4 流水线的相关(xinggun)与冲突,解决方法：暂停一拍（也称为流水线气泡(qpo)，简称气泡(qpo)）。,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,第68页/共177页,第六十九页，共177页。,3.4 流水线的相关(xinggun)与冲突,第69页/共177页,第七十页，共177页。,3.4 流水线的相关(xinggun)与冲突,（二）数据冲突,1、数据冲突,指由于流水线中各指令重叠执行，使得(sh de)原来对操作数的访问顺序发生变化，从而引起的一种数据冲突。,如：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,第70页/共177页,第七十一页，共177页。,3.4 流水线的相关(xinggun)与冲突,2、解决办法,采用定向传送(chun sn)技术（旁路技术或相关专用通路技术）。,IF,ID,EX MEM WB,DSUB,IF ID,EX,MEM,WB,DADD,1 2 3 4 5 6,写,R1,读,R1,ALU,运算结果,目标,R,ALU,操作数寄存器,旁路(pn l)传送,第71页/共177页,第七十二页，共177页。,3.4 流水线的相关(xinggun)与冲突,第72页/共177页,第七十三页，共177页。,3.4 流水线的相关(xinggun)与冲突,3、数据冲突类型,根据指令对同一寄存器读和写的先后顺序，数据冲突可分为(fn wi)三种类型：,1）RAW（读超前于写）,指令入,出,1,2,3,4,5,读数,写数,k,j,i,R,i,指令,:,写数,j,指令,:,读数,解决方法一：按序流动(lidng)（顺序流动(lidng)）的流水线中，用定向传送技术。,指流水线中流出的结果与流入指令的次序是一致的。,第73页/共177页,第七十四页，共177页。,但是，定向(dn xin)技术并不能解决所有RAW冲突。,如装入延迟：,LD R1，0（R2）,DADD R4，R1，R5,AND R6，R1，R7,XOR R8，R1，R9,第74页/共177页,第七十五页，共177页。,解决方法二：增加流水线互锁硬件，插入“暂停(zn tn)”。,作用：检测发现数据冲突，并使流水线停顿，直至冲突消失。,第75页/共177页,第七十六页，共177页。,解决方法三：指令调度（流水线调度）,前提：在非按序流动方式（乱步流动）的流水线中。,具体实现：通过(tnggu)编译使某些指令的运行结果可能先于j指令流出，情况如下:,指允许输出结果的次序与输入指令(zhlng)的次序不同。,l,k,i,k,j,i,l,指令入,出,1,2,3,4,5,读数,写数,R,i,指令,:,写数,j,指令,:,读数,第76页/共177页,第七十七页，共177页。,3.4 流水线的相关(xinggun)与冲突,由于允许非按序执行，使流水线的停顿时间大为减小，有利于提高流水线的吞吐率和效率。但同时还应该注意可能由此引起的另两种冲突:,2）WAR（写超前于读）,原程序要求对同一单元进行先读后写的操作，可能因为非按序执行成为先写后读，造成(zo chn)出错。,3）WAW（写后写）,原程序中如果两条指令都要对同一单元进行写数操作，可能因为非按序执行的原因，改变了两条指令写入的次序。,第77页/共177页,第七十八页，共177页。,3.4 流水线的相关(xinggun)与冲突,（三）控制(kngzh)冲突,1、控制(kngzh)冲突,流水线遇到分支指令（转移指令）和其他会改变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,末尾(mwi)处更新PC值,第78页/共177页,第七十九页，共177页。,3.4 流水线的相关(xinggun)与冲突,转移指令对流水线的影响,例:设在某一程序中，条件转移指令在程序中所占的比例为25%，其中转移成功的概率为2/3。试计算执行一条(y tio)指令的平均时钟周期数。,解：设执行一条(y tio)指令的平均时钟周期数为Pi，则,Pi=(1-25%)1+25%(3+1),=1.75,第79页/共177页,第八十页，共177页。,3.4 流水线的相关(xinggun)与冲突,2、有关措施,为了(wi le)减小分支延迟造成的损失，可采用以下措施：,1）在流水线中尽早判断出分支转移是否成功。,2）尽早计算出分支目标地址。,两种措施同时采用，缺一不可。,假设该两步工作被提前到ID段完成，即分支指令是在ID段的末尾执行完成，所带来的分支延迟为一个时钟周期。,第80页/共177页,第八十一页，共177页。,3.4 流水线的相关(xinggun)与冲突,为了减小分支延迟造成的损失，还可通过软件（编译器）来减少(jinsho)分支延迟，常见的有以下几种：,（1）预测分支失败,允许分支指令后的指令继续在流水线中流动，就好象什么都没发生似的。,若确定分支失败，将分支指令看作是一条普通指令，流水线正常流动。,若确定分支成功，流水线就把在分支指令之后取出的所有指令转化为空操作，并按分支目地重新取指令执行。,第81页/共177页,第八十二页，共177页。,3.4 流水线的相关(xinggun)与冲突,对于上例：,设在某一程序中，条件转移指令在程序中所占的比例为25%，其中转移成功的概率为2/3。试计算执行一条(y tio)指令的平均时钟周期数。,假设采用预测分支失败，则,执行一条(y tio)指令的平均时钟周期数为Pi为：,Pi=(1-25%)1+25%1/3 1+25%2/3(1+1),1.17,第82页/共177页,第八十三页，共177页。,3.4 流水线的相关(xinggun)与冲突,（2）预测分支成功,假设分支转移成功，并从分支目标地址(dzh)处取指令执行。,起作用的前题：先知道分支目标地址(dzh)，后知道分支是否成功。,前述5段流水线中，由于判断分支是否成功与分支目标地址(dzh)计算是在同一流水段完成，这种方法没有任何好处。,第83页/共177页,第八十四页，共177页。,3.4 流水线的相关