计算机系统结构第3章(流水技术与流水处理机).pptx

【学习目标学习目标】1.理理解解指指令令交交叉叉方方式式的的工工作作原原理理,以以及及处处理理机机处处理理机机在在结结构构上上必须解决的问题必须解决的问题.2.掌掌握握流流水水方方式式的的工工作作原原理理,掌掌握握利利用用时时空空图图计计算算流流水水线线的的吞吞吐吐率率、加加速速比比和和效效率率的的方方法法;了了解解从从不不同同角角度度对对流流水水线线的的分类及其定义分类及其定义,了解消除流水线瓶颈的方法了解消除流水线瓶颈的方法.3.掌掌握握单单功功能能非非线线性性流流水水线线的的最最优优调调度度方方法法,求求解解最最优优调调度度及及其其流流水水线线的的吞吞吐吐率率、加加速速比比和和效效率率的的方方法法.了了解解双双功功能能非非线线性流水线的最优调度方法及无冲突调度的实现方法性流水线的最优调度方法及无冲突调度的实现方法.4.掌握流水线发生局部相关和全局相关的原因及其处理方法掌握流水线发生局部相关和全局相关的原因及其处理方法.5.理理解解超超标标量量处处理理机机、超超流流水水线线处处理理机机、超超标标量量超超流流水水线线处处理理机机三三种种处处理理机机在在指指令令级级上上并并行行的的工工作作原原理理,以以及及它它们们分分别别相对于标量流水处理机加速比的计算方法相对于标量流水处理机加速比的计算方法.6.了解超长指令字处理机的基本工作原理了解超长指令字处理机的基本工作原理.7.了了解解向向量量的的3种种处处理理方方式式,掌掌握握向向量量流流水水处处理理机机上上的的一一串串向向量量指指令令序序列列的的指指令令并并行行和和指指令令链链接接的的条条件件,以以及及计计算算指指令令序序列执行时间的方法列执行时间的方法.3.13.1指令重叠与先行控制指令重叠与先行控制提高处理机执行指令速度的途径提高处理机执行指令速度的途径,通常有三种途径:(1)提高处理机的工作频率提高处理机的工作频率(2)采用采用RISC技术减少指令执行的平均周期数技术减少指令执行的平均周期数(3)多条指令并行执行多条指令并行执行指令级并行技术指令级并行技术流水线处理机或超流水线处理机流水线处理机或超流水线处理机(super pipelining processor)多操作部件处理机或超标量处理机多操作部件处理机或超标量处理机(superscalar)3.1.1指令的顺序执行方式与重叠执行方式指令的顺序执行方式与重叠执行方式3.1.2.先行控制技术先行控制技术超长指令字超长指令字（Very Long Instruction Word,VLIW）技术技术取指令取指令:指令计指令计数器数器访问访问主存主存取出一取出一条指令条指令指令寄指令寄存器存器分析分析指令指令:操作码译码操作码译码形成操作数地址形成操作数地址读取操作数读取操作数(从主存或寄存器从主存或寄存器)指令指令执行执行:完成指令规定的功能完成指令规定的功能结果写入主存或寄存器结果写入主存或寄存器三个三个阶段阶段都可都可能访能访问主问主存存指令的顺序执行方式与重叠执行方式指令的顺序执行方式与重叠执行方式1.指令的顺序执行方式指令的顺序执行方式 一条指令执行过程指令执行过程:一条指令的执行分为三个阶段:取指令、分析与执行取指令、分析与执行.指令的顺序执行方式与重叠执行方式指令的顺序执行方式与重叠执行方式1.指令的顺序执行方式指令的顺序执行方式 指令之间顺序串行指令之间顺序串行,且指令内的各阶段之间也是且指令内的各阶段之间也是顺序串行的方式顺序串行的方式.如果取指、分析、执行如果取指、分析、执行3个阶段所需时间均为个阶段所需时间均为t,那么顺序执行那么顺序执行n条指令所用的时间为条指令所用的时间为:=3nt 顺序执行方式的优点指令之间相互关联关系易于顺序执行方式的优点指令之间相互关联关系易于控制和处理控制和处理,结构设计与组成实现简便易行结构设计与组成实现简便易行.缺点是执行的速度慢缺点是执行的速度慢,系统各部件的利用率低系统各部件的利用率低.取指令i分析i执行i取指令i+1分析i+1执行i+1 一次重叠方式是指第i条指令和第i+1条指令的执行有一段的执行是重叠的。例如第i条指令的执行指令阶段同时也是第i+1条指令的取指令阶段.p一次重叠执行方式一次重叠执行方式假设执行一条指令的三个过程的时间都为假设执行一条指令的三个过程的时间都为t，可以看出：，可以看出：除了第一条指令外，每经过两段就会完成一条指令。除了第一条指令外，每经过两段就会完成一条指令。指令的顺序执行方式与重叠执行方式指令的顺序执行方式与重叠执行方式2.2.指令的重叠执行方式指令的重叠执行方式优点优点:一是提高了功能部件的利用率一是提高了功能部件的利用率;二是明显提高了指令的执行速度。二是明显提高了指令的执行速度。缺点缺点:需要增加一些硬件需要增加一些硬件;控制过程比较复杂控制过程比较复杂.p一次重叠执行方式一次重叠执行方式2.2.指令的重叠执行方式指令的重叠执行方式 两次重叠方式和一次重叠方式的道理是一样的，不过重叠的是指令的两个阶段.p两次重叠执行方式两次重叠执行方式如果执行一条指令的三个过程所用的时间相等，则执行n条指令的时间为：执行执行n条指令所用的时间条指令所用的时间优缺点优缺点:执行时间缩短了将近三分之二。处理机的机构要作比较大的改变,要采用先行控制方式.T=(2+n)t2.指令的重叠执行方式指令的重叠执行方式3.1.2 先行控制技术先行控制技术 采用二次重叠执行方式，在处理机中同时有三条指令分别在取指令、分析和执行。要使指令能够正确地重叠执行，必须解决如下两个问题：第一，为了实现取指令，分析指令和执行指令同时进行，需要有独立的取指令部件、指令分析部件和指令执行部件。因此，要把顺序执行方式中的一个集中的指令控制器，分解成三个相对独立的控制器，它们是：存储控制器，简称存控；指令控制器，简称指控；运算控制器，简称运控。n需要解决的问题：需要解决的问题：第二，要解决访问主存储器的冲突问题。例如，取指令时要访问主存储器，分析指令时可能要取操作数，执行指令时可能要向主存储器写运算结果。常规的主存储器体系结构无法实现指令的重叠执行。先行控制技术先行控制技术n需要解决的问题：需要解决的问题：如何解决如何解决p把主存储器分成两个独立编址的存储器，一个专门存放指令，称为指令存储器，简称指存；另一个专门存放操作数，称为数据存储器，简称数存。两个存储器可以同时独立访问；这样，就解决了取指令和读操作数的冲突。p指令和数据仍然混合存放在同一个主存储器内，采用低位交叉存取方式，在一个存储器周期中可以访问多个存储单元。如果处理机同时执行的取指令和读操作数所访问的不是同一个存储体，则可以实现指令重叠执行。如果正好访问同一个存储体，则指令无法重叠执行。先行控制技术先行控制技术n解决访问存储器冲突的方法：解决访问存储器冲突的方法：先行控制技术先行控制技术p采用先行控制技术的处理机结构采用先行控制技术的处理机结构主存储器存储控制器先行指令缓冲栈先行读数栈后行写数栈指令分析器先行操作栈运算控制器运算器通用寄存器先行指令缓冲栈先行指令缓冲栈 作为主存与指令分析器之间之间的缓冲部件作为主存与指令分析器之间之间的缓冲部件,用以平滑主存和指令分析器的工作速度的差异用以平滑主存和指令分析器的工作速度的差异.先行操作栈先行操作栈 是指令分析器与运算控制器之间的一个缓冲存储是指令分析器与运算控制器之间的一个缓冲存储器器,由指令分析器对指令进行预处理后送入先行操作栈由指令分析器对指令进行预处理后送入先行操作栈.各种运算各种运算型指令、移位指令、数据传输指令等都要处理成型指令、移位指令、数据传输指令等都要处理成RR型指令型指令,为了为了与指令系统中原有的与指令系统中原有的RR型指令相区别型指令相区别,通常将送入先行操作栈的通常将送入先行操作栈的指令称为指令称为RR*型指令型指令.运算控制器从先行操作栈取出运算控制器从先行操作栈取出RR*型指令型指令,运算器需要的操作数来自先行读数栈或通用寄存器运算器需要的操作数来自先行读数栈或通用寄存器.先行控制技术先行控制技术p采用先行控制技术的处理机结构采用先行控制技术的处理机结构主存储器存储控制器先行指令缓冲栈先行读数栈后行写数栈指令分析器先行操作栈运算控制器运算器通用寄存器先行读数栈先行读数栈 是主存和运算器之间的一种缓冲存储器是主存和运算器之间的一种缓冲存储器,用来平滑运算器与主存的工作速度差异用来平滑运算器与主存的工作速度差异.对于先行的指令对于先行的指令而言而言,是把后续的指令要用到的操作数是把后续的指令要用到的操作数“先行先行”从主存读取从主存读取,所以称为先行读数栈所以称为先行读数栈,原来要访存取操作数变为访问先行原来要访存取操作数变为访问先行读数栈中的寄存器读数栈中的寄存器,大大加快了指令的执行速度大大加快了指令的执行速度.先行控制技术先行控制技术p采用先行控制技术的处理机结构采用先行控制技术的处理机结构主存储器存储控制器先行指令缓冲栈先行读数栈后行写数栈指令分析器先行操作栈运算控制器运算器通用寄存器后行写数栈后行写数栈 当指令分析器遇到向主存写数的指令当指令分析器遇到向主存写数的指令,则把形成的则把形成的主存有效地址送入后行写数栈的后行地址缓冲器中主存有效地址送入后行写数栈的后行地址缓冲器中,并把预处理好并把预处理好的的RR*型指令送入先行操作栈型指令送入先行操作栈,这条这条RR*型指令中的目标寄存器就型指令中的目标寄存器就是后行写数栈的缓冲寄存器编号是后行写数栈的缓冲寄存器编号.当运算器执行这条当运算器执行这条RR*型指令时型指令时,把原定写到主存中去的数据送入后行写数栈的相应后行数据缓冲把原定写到主存中去的数据送入后行写数栈的相应后行数据缓冲寄存器中即可寄存器中即可,而由后行写数栈负责把数据缓冲器中的数据按地址而由后行写数栈负责把数据缓冲器中的数据按地址缓冲器中的主存地址送入主存缓冲器中的主存地址送入主存.这样这样,运算器不必等待数据写回主存运算器不必等待数据写回主存,就可以继续执行后续指令就可以继续执行后续指令.因此因此,后行写数栈也是主存与运算器之后行写数栈也是主存与运算器之间的一种缓冲存储器间的一种缓冲存储器.先行控制技术先行控制技术p采用先行控制技术的处理机结构采用先行控制技术的处理机结构主存储器存储控制器先行指令缓冲栈先行读数栈后行写数栈指令分析器先行操作栈运算控制器运算器通用寄存器 可以看出可以看出,先行控制技术实质上是缓冲技术和预处理技术相结合先行控制技术实质上是缓冲技术和预处理技术相结合的技术的技术.通过对指令和数据的预处理和缓冲通过对指令和数据的预处理和缓冲,使指令分析器和指令使指令分析器和指令执行部件能够独立地工作执行部件能够独立地工作,并始终处于忙碌状态并始终处于忙碌状态,从而大大提高了从而大大提高了指令重叠执行的速度指令重叠执行的速度.通常把先行指令缓冲栈、先行读数栈、先行操作栈和后行写数通常把先行指令缓冲栈、先行读数栈、先行操作栈和后行写数栈统称为先行控制器栈统称为先行控制器.先行控制器与指令分析器一起构成先行控先行控制器与指令分析器一起构成先行控制方式中的指令控制部件制方式中的指令控制部件.而原来的运算器及运算控制器一起组而原来的运算器及运算控制器一起组成指令执行部件成指令执行部件.3.2 流水线的分类与性能3.2.1.流水线的分类与时空图流水线的分类与时空图3.2.2线性流水线的性能计算线性流水线的性能计算1.流水线的分类流水线的分类2.时空图时空图1.吞吐率吞吐率2.加速比加速比3.效率效率 流水线可按不同的观点进行分类，一般来说流水线可以分为如下几种类型：(1)线性流水线和非线性流水线线性流水线和非线性流水线按照流水线的各个功能段之间是否有反馈信号分类n线性流水线线性流水线(linear pipelining)是指流水线的各段串行连接,数据从流水线的一端进入,从另一端输出,在各个功能段流过时仅流过一次,没有反馈回路。流水线的分类流水线的分类(1)线性流水线和非线性流水线线性流水线和非线性流水线非线性流水线非线性流水线 流水线中除有串行连接的通路处，还有反馈回路或前馈回路。下面的非线性流水线带有反馈回线。流水线的分类流水线的分类(2)单功能流水线和多功能流水线 这是按照流水线所完成的功能来分类的。单功能流水线单功能流水线，是指只能完成一种固定功能的流水线。要完成多种功能，可采用多个单功能流水线。多功能流水线多功能流水线，是指同一流水线的各个段之间可以进行不同的连接，从而使流水线在不同的时间，或者在同一时间完成不同的功能。流水线的分类流水线的分类(3)部件级、处理机级及系统级流水线部件级、处理机级及系统级流水线 是按照流水线使用的级别来进行分类。部件级流水线部件级流水线，又叫运算操作流水线。它是指部件内部各子部件组成的流水线.如指令分析部件中各子部件组成的指令分析部件流水线。处理机级流水线处理机级流水线，又叫指令流水线。它是指处理机内各部件之间的流水线,把执行指令的过程按照流水方式处理,取指部件、指令分析部件和指令执行部件组成的指令流水线。处理机间级流水线处理机间级流水线，又叫宏流水线。它是由两个以上的处理机串行地对同一数据流进行处理，每个处理机对数据流的不同部分分别进行处理。流水线的分类流水线的分类(4)静态流水线和动态流水线静态流水线和动态流水线在多功能流水线中,按照同一时间内是否能够连接成多种方式,同时执行多种功能来分类:静态流水线静态流水线，是指在同一时间内，流水线的各段只能按同一种功能的连接方式工作。动态流水线动态流水线，是指在同一时间内，当某些段上在实现某种运算(如定乘)时，另一些段却在实现另一种运算(如浮加)，这样就不是非得相同运算的一串操作才能流水处理。流水线的分类流水线的分类(5)(5)标量流水处理机与向量处理机标量流水处理机与向量处理机 流水处理机按是否具有向量数据表示和相应的流水处理机按是否具有向量数据表示和相应的向量指令向量指令,可分为标量流水处理机和向量流水处理可分为标量流水处理机和向量流水处理机机.标量流水处理机标量流水处理机(Scalar Pipeline(Scalar Pipeline Processor),Processor),只有流水线只有流水线,没有向量数据表示和相应没有向量数据表示和相应的向量指令的向量指令.向量流水处理机是向量数据表示与向量指令流向量流水处理机是向量数据表示与向量指令流水线的结合水线的结合.流水线的分类流水线的分类 流水线的工作常用“时空图”来描述，用横轴代表时间，纵轴表示流水线的各功能部件。规格化规格化1规格化规格化2规格化规格化3规格化规格化4规格化规格化52.时空图时空图(Time-Space Diagram)流水线的分类与时空图流水线的分类与时空图n四段浮点加法器流水线时空图四段浮点加法器流水线时空图p加法器流水线加法器流水线:求阶差求阶差对阶对阶尾数加尾数加规格化规格化入入出出p时空图时空图求阶差求阶差1求阶差求阶差2求阶差求阶差3求阶差求阶差4求阶差求阶差5对阶对阶1对阶对阶2对阶对阶3对阶对阶4对阶对阶5尾数加尾数加1尾数加尾数加2尾数加尾数加3尾数加尾数加4尾数加尾数加5空间空间时间时间0n多功能流水线的时空图多功能流水线的时空图时空图时空图输入输入求阶差求阶差对阶对阶尾数加尾数加规格化规格化尾数乘尾数乘累加累加输出输出A B输入输入求阶差求阶差对阶对阶尾数加尾数加规格化规格化尾数乘尾数乘累加累加输出输出A B输入输入求阶差求阶差对阶对阶尾数加尾数加规格化规格化尾数乘尾数乘累加累加输出输出A B输入输入求阶差求阶差对阶对阶尾数加尾数加规格化规格化尾数乘尾数乘累加累加输出输出A Bp流水线流水线g=f(A,B)定点乘定点乘浮点加浮点加浮点点积浮点点积123n-1n123n-1nn多功能流水线的时空图多功能流水线的时空图p静态时空图静态时空图空间空间输出输出累加累加尾数乘尾数乘规格化规格化尾数加尾数加对阶对阶求阶差求阶差输入输入123n-1n123n-1n123n-1n123n-1n浮点加浮点加时间时间1234123121定点乘定点乘123n-1n123n-1nn多功能流水线的时空图多功能流水线的时空图p动态时空图动态时空图空间空间输出输出累加累加尾数乘尾数乘规格化规格化尾数加尾数加对阶对阶求阶差求阶差输入输入123n-1n123n-1n123n-1n123n-1n浮点加浮点加时间时间123456123451234123定点乘定点乘吞吐率吞吐率 流水线的吞吐率流水线的吞吐率（throughput rate,），是指单位，是指单位时间内流水线完成的任务数或输出的结果时间内流水线完成的任务数或输出的结果.分子表示n个任务，分母表示完成n个任务所用的时间。线性流水线的性能计算线性流水线的性能计算(1)各段执行时间相的吞吐率各段执行时间相的吞吐率.输入连续任务情况下完成n个连续任务需要的总时间为：Tk=(k+n-1)Dt k为流水线的段数，D t为时钟周期流水线的吞吐率流水线的吞吐率从流水线的输出端看从流水线的输出端看,用用k个周期输出第一个任务个周期输出第一个任务,以后是每个时以后是每个时钟周期输出一个任务钟周期输出一个任务,即用即用n-1个时钟完成其余的个时钟完成其余的 n-1个任务个任务.从输入端看从输入端看,因为是任务之间隔一个时钟周期因为是任务之间隔一个时钟周期,因此要用因此要用n个时个时钟周期向流水线输入钟周期向流水线输入n个任务，另外还要用个任务，另外还要用k-1个时钟周期为个时钟周期为流水线的排空时间（即最后一个任务出流水线）流水线的排空时间（即最后一个任务出流水线）输输出出端端输输入入端端各段执行时间相等，输入连续任务各段执行时间相等，输入连续任务 吞吐率：吞吐率：最大吞吐率与吞吐率之间的关系最大吞吐率与吞吐率之间的关系最大吞吐率为最大吞吐率为：结论结论:流水线的实际吞吐率与哪些因素有关流水线的实际吞吐率与哪些因素有关?吞吐率吞吐率(2)流水线各段执行时间不相等流水线各段执行时间不相等37吞吐率为：吞吐率为：最大吞吐率为：最大吞吐率为：(2)各段执行时间不相等、输入连续任务情况各段执行时间不相等、输入连续任务情况吞吐率吞吐率实际吞吐率和最大吞吐率主要由流水线中执行时间实际吞吐率和最大吞吐率主要由流水线中执行时间最长的那个功能块决定最长的那个功能块决定.这个功能块成了整个流水线这个功能块成了整个流水线的的“瓶颈瓶颈”.吞吐率吞吐率n解决流水线的解决流水线的“瓶颈瓶颈”问题的方法问题的方法p一是将一是将“瓶颈瓶颈”流水段细分流水段细分(如果可分的话如果可分的话)p二是将二是将“瓶颈瓶颈”流水段重复设置流水段重复设置流水段重复设置的流水线1时间空间2 3nS1S2-14 5 614-2-1n-225n-136n1 2 3n4 5 6-2-11 2 3n4 5 6-2-1S2-2S2-3S3S4时空图时空图最大吞吐率最大吞吐率:线性流水线的性能计算线性流水线的性能计算 分子是采用非流水线用的时间，分母是采用流水线所用的时间。(1)各段执行时间相等的加速比各段执行时间相等的加速比在等效的非流水线上所需时间为：T0=nkt 所以,对于各功能段执行时间均相等,有K段的流水线完成n个连续任务时的加速比S为：2.加速比加速比 流水线的加速比是指等功能的非流水线的速度与具有流水线的加速比是指等功能的非流水线的速度与具有m段流水线的速度之比。段流水线的速度之比。加速比的基本公式为：加速比的基本公式为：2.加速比加速比最大加速比最大加速比:从上式可以看出，当nk时，流水线的最大加速比等于流水线的段数。即：最小加速比最小加速比:当n=1时,加速比为为1,最小 与流水线的段数有关与流水线的段数有关:如n=64时,4段流水线的加速比为3.8,而有8段的流水线的加速比为7.2是否流水线的段数可以不受限制的增加呢是否流水线的段数可以不受限制的增加呢?加速比加速比(2)各段执行时间不等的加速比各段执行时间不等的加速比如果各段时间不等，则有：线性流水线的性能计算线性流水线的性能计算 3.效率效率(Efficiency)定义定义:效率是指流水线的设备利用率。时空图表示时空图表示:在时空图上,流水线的效率表示为n个任务占用的时空区与k个功能段总的时空区之比.流水线的效率与其包含的时间、空间两方面的因素有关.表达式表达式:n个任务占用的时空区就是顺序执行n个任务所使用的总的时间T0,而一条k段的流水线完成n个任务的总的时空区为KTk.其中Tk是流水线完成n个任务使用的总时间.则一条k段的流水线的效率可以表示为:3.效率效率(1)各段执行时间相等各段执行时间相等,n个任务连续,一条k段的流水线的效率为:上式的分母是时空图中完成n个任务所用的时间与k个功能所围成的总面积；而分子是时空图中n个任务实际占用的面积。当nk时，E1。这个结论和上面分析吞吐率及加速比的结论是一致的.线性流水线的性能计算线性流水线的性能计算 从以上的分析很容易可以得出关于流水线的三个性能标准的之间的关系。三个性能标准的之间的关系三个性能标准的之间的关系p效率和吞吐率之间的关系可以表示为:当时钟周期t不变时，流水线的效率与吞吐率成正比。这就是说，为了提高流水线的效率而采取的措施，同时也提高了流水线的吞吐率。p效率和加速比之间的关系可以表示为：3.效率效率(2)各段执行时间不等的效率各段执行时间不等的效率例例3.3非线性流水线的调度与性能计算非线性流水线的调度与性能计算3.3.1非线性流水线的最优调度方法与性能计算非线性流水线的最优调度方法与性能计算1.单功能非线性流水线的最优调度方法及其性能计算单功能非线性流水线的最优调度方法及其性能计算2.多功能非线性流水线的最优调度方法及其性能计算多功能非线性流水线的最优调度方法及其性能计算3.3.2非线性流水线的最优调度的时空图非线性流水线的最优调度的时空图3.3.3非线性流水线的动态调度的实现非线性流水线的动态调度的实现流水线的相关问题与相关处理流水线的相关问题与相关处理 所谓相关相关是指在一段程序的相近指令之间有某种关系,这种关系可能影响指令的重叠执行.通常把相关分为两大类:局部相关(Local Correlation),仅涉及到相关指令前后的一条或几条指令的执行.全局相关(Global Correlation)指影响整个程序执行方向的相关,主要是转移类指令和中断引起的相关.3.4.1局部相关及处理局部相关及处理3.4.2全局相关及处理全局相关及处理3.4.3相关对流水线性能的影响相关对流水线性能的影响3.4.1局部相关及处理局部相关及处理局部相关主要有局部相关主要有:“先写后读先写后读”相关相关“先读后写先读后写”相关相关“写写-写写”相关相关这些相关问题的出现同对象序列在流水这些相关问题的出现同对象序列在流水线中流动顺序有关线中流动顺序有关1.顺序流动的顺序流动的“先写后读先写后读”相关及处理相关及处理 顺序流动是指对象从流水线流出的次序与它们流入流水线的次序一样.读读取取写写段段nKkjjjm空空ik空空iil空空hhh18指令指令存储单元存储单元入入出出(异步流动异步流动)(顺序流动顺序流动)(判出判出j,h 相关相关)如果指令如果指令h写入结果的目的地址同指令写入结果的目的地址同指令j读操作数的源地址是同读操作数的源地址是同一个存储单元或寄存器一个存储单元或寄存器,称这两条指令有称这两条指令有“先写后读先写后读”要求要求.若指若指令令j到达读段时到达读段时,指令指令h还没有到达写段完成写操作还没有到达写段完成写操作,则指令则指令j读出读出的数据就是错误的的数据就是错误的,这就是这就是“先写后读先写后读”相关相关.解决的方法当指令解决的方法当指令j到达读段时到达读段时,若通过比较地址码发现与指令若通过比较地址码发现与指令h相关相关,则指令则指令j及其后面的指令停止流动直到指令及其后面的指令停止流动直到指令h流过写段再继流过写段再继续流动续流动.2.2.异步流动的局部相关异步流动的局部相关 异步流动是指对象从流水线流出的次序同它们流入流水异步流动是指对象从流水线流出的次序同它们流入流水线的次序不同线的次序不同.异步流动也称乱序异步流动也称乱序(Out of Order)(Out of Order)流动或错流动或错序流动序流动.对于解决顺序流动中的对于解决顺序流动中的“先写后读先写后读”相关相关,异步流动可提异步流动可提高流水线的吞吐率和效率高流水线的吞吐率和效率,但会出现两种新的相关但会出现两种新的相关:“写写-写写”相关和相关和“先读后写先读后写”相关相关.若指令若指令i i和指令和指令k k都有写操作都有写操作,且写入的目的地址是同一且写入的目的地址是同一存储单元或同一寄存器存储单元或同一寄存器,顺序执行时是顺序执行时是i i先写先写,而而k k后写后写.但是但是,采用异步流动时采用异步流动时,可能可能k k先于到达写段先于到达写段,那么该存储单元或那么该存储单元或寄存器的内容最后是由寄存器的内容最后是由i i写入写入,这就是这就是“写写-写写”相关相关.若指令若指令i i的读操作和指令的读操作和指令k k写操作是同一个存储单元或寄存写操作是同一个存储单元或寄存器器,则这两条指令有则这两条指令有“先读后写先读后写”要求要求.采用异步流动采用异步流动,可能可能出现指令出现指令k k的写操作先于的写操作先于i i的读操作的读操作,造成造成“先读后写先读后写”相关相关.解决的方法解决的方法,同样可采用延迟方法同样可采用延迟方法.3.3.相关专用通路相关专用通路 解决解决“先写后读先写后读”相关的另一种方法是建立相关专用通路相关的另一种方法是建立相关专用通路,即在流水线的读段和写段之间增加一条专用的数据通路即在流水线的读段和写段之间增加一条专用的数据通路.对于对于“先写后读先写后读”数据相关，先数据相关，先AB，然后，然后BC；等效于；等效于ABC.如果采用设置专用路径的方法如果采用设置专用路径的方法,新增加一条从新增加一条从A到到C的的专用路径，撤消原来从专用路径，撤消原来从B到到C的路径的路径.这样可避免这样可避免“先写后读先写后读”数据数据相关，或者缩短发生相关，或者缩短发生“先写后读先写后读”数据相关的时间。数据相关的时间。延迟的方法是以增加时间为代价延迟的方法是以增加时间为代价,降低速度来解决问题降低速度来解决问题;相关专用通路是以增加设备为代价相关专用通路是以增加设备为代价,提高成本来解决问题提高成本来解决问题全局相关及处理全局相关及处理 由于程序的执行方向改变而引起的相关,例如条件转移或程序中断引起的相关,叫全局相关全局相关，是对整个程序的大的改变。在目前的处理机当中程序的执行方向改变主要有转移子程转移子程序，转移和中断序，转移和中断三种情况。条件转移指令条件转移指令在一般的程序中占有比较大比例.中断中断所占的比例不大,但中断发生在程序的哪一条指令,发生在指令执行过程中的哪一个功能段都是不确定的,因此处理好条件转移和中断所引起的全局相关是很重要的.1.条件转移的处理条件转移的处理2.中断处理中断处理条件转移的处理条件转移的处理n无条件转移，就是在流水线里，碰到一条无条件转移指令（通常是JMP指令），无条件的转移到别的地方。n条件转移指令有两种，即一般条件转移指令和复合条件转移指令。其中，一般条件转移指令的转移条件来自上一条指令，或来自更前面的指令。而复合型条件转移指令直接根据本条指令的执行结果决定是否转移。无论哪种情况，一般都要在转移指令执行到流水线的最后功能段时，转移条件才能建立因此，因此，在条件转移指令进入流水线之后，到形成转移条在条件转移指令进入流水线之后，到形成转移条件之前，后续指令不能进入流水线件之前，后续指令不能进入流水线(1)转移的影响转移的影响猜测的分支固定在转移不成功方向猜测的分支固定在转移不成功方向n如果形成的条件码是对应于转移不成功如果形成的条件码是对应于转移不成功,猜测正确猜测正确,吞吐和效率吞吐和效率不受影响不受影响;n如果形成的条件码对应于转移成功如果形成的条件码对应于转移成功,则则猜测错误猜测错误,有有k-2个功能个功能段是浪费的段是浪费的.转移的影响转移的影响用用“猜测法猜测法”解决由于条件转移使流水线解决由于条件转移使流水线“断流断流”问题问题i-1ii+1i+2i+k-3i+k-2pP+1P+k-4P+k-3形成条件形成条件码的指令码的指令条件转条件转移指令移指令转移不成功转移不成功转移成功转移成功形成条件码形成条件码输入输入输出输出输出输出时间时间条件转移的处理条件转移的处理n更严重的情况更严重的情况:如果第如果第i+1指令是指令是 (R1)+(R2)R1 一旦这条指令执行完成一旦这条指令执行完成,寄存器寄存器R1的内容就被破坏的内容就被破坏,使程序的执行结果发生错误使程序的执行结果发生错误.为避免之为避免之,采取两种做法采取两种做法:p 只进行指令译码和准备好操作数只进行指令译码和准备好操作数,在转移条件没在转移条件没有形成之前不执行运算有形成之前不执行运算;p一直执行到运算完成一直执行到运算完成,但不送回运算结果但不送回运算结果.n在一些典型程序中在一些典型程序中,转移指令所占的比例为转移指令所占的比例为p=20%,转移成功率为转移成功率为q=60%,对于一个有对于一个有8个功能个功能段的流水线段的流水线,由于条件转移的影响由于条件转移的影响,流水线的最大吞流水线的最大吞吐率要下降吐率要下降46%.转移的影响转移的影响条件转移的处理条件转移的处理n减少条件转移指令对流水线影响的措施减少条件转移指令对流水线影响的措施p延迟转移技术延迟转移技术.是RISC的关键技术.它是依靠编译器把转移指令之前的一条或几条没有数据相关的指令调整到转移指令的后面.一般用于段数较少的流水线中.据统计,编译器只调整一条指令的成功概率在90%以上,调整两条指令的成功概率只有40%左右.当没有合适的指令可供调整时,编译器只能在转移指令后面插入空操作指令.p静态转移预测技术静态转移预测技术.在在两个方向都预取指令,增设一定数量的缓冲寄存器堆栈,以减少转移方向猜测错误是造成的影响.(2)减少转移影响的措施减少转移影响的措施条件转移的处理条件转移的处理n减少条件转移指令对流水线影响的措施减少条件转移指令对流水线影响的措施p动态转移预测技术动态转移预测技术.是根据近期转移是否成功的历史记录来预测下一次转移的方向.能够随程序的执行过程动态地改变转移的预测方向.其关键技术:一一是如何记录转移的历史记录是如何记录转移的历史记录;二是如何根据记录的二是如何根据记录的历史信息预测转移的方向历史信息预测转移的方向.一种方法是在指令Cache中专门设置一个字段,称为“历史转移表”,将转移成功或不成功的信息记录在表中.p提前形成条件码提前形成条件码.由编译器调整指令序列,把产生条件码的运算型指令与使用这个条件码的条件转移指令分离开来,提前执行这个运算形指令.条件转移的处理条件转移的处理(2)减少转移影响的措施减少转移影响的措施 中断不能预知,在流水线处理机中,同时有多条指令被执行,每一条指令在流水线中都不断地改变着现场.因此,当有一个中断源的中断请求被响应时,选择哪一条指令作为断点指令?需要保存的现场信息是哪一些指令的现场?有两种处理方法:n不精确断点方法不精确断点方法.进入流水线的指令都执行完,断点是该指令序列中最后进入流水线的那条指令.提出中断请求的指令可能并不是最后那条指令.这种方法保存现场和恢复现场的工作量较小;但是有两个问题:一是程序执行的结果可能出错;二是程序员无法看到自己设置的断点初的现场.n精确断点法精确断点法.对于在流水线中同时执行的多条指令,由哪一条指令的程序性错误或故障发出的中断请求,断点就是这条指令.其前尚在流水线中已完全执行或部分执行的指令的执行情况都作为现场保存起来.硬件代价高,控制复杂.2.中断处理中断处理全局相关及处理全局相关及处理3.4.3相关对流水线性能的影响相关对流水线性能的影响 流水线处理对象之间的相关将导致流水线的性能下降.对此应尽可能采取措施减少流水线性能下降的程度.下面通过几个例子,说明用时空图来表示流水处理过程和对流水线性能的影响.例例1:在一台流水处理机上执行下述的指令序列在一台流水处理机上执行下述的指令序列,每条指每条指令的取指令和指令译码各需令的取指令和指令译码各需1个时钟周期个时钟周期,MOVE、ADD和和MUL的执行分别需要的执行分别需要2个、个、3个和个和4个时钟周个时钟周期期,且都在第一个时钟周期从通用寄存器中读取操且都在第一个时钟周期从通用寄存器中读取操作数作数,在最后一个时钟周期把目的操作数写到通用在最后一个时钟周期把目的操作数写到通用寄存器中寄存器中.k:MOVE R1,R0 ;R1(R0)k+1:MUL R0,R2,R1 ;R0(R2)(R1)k+2 ADD R0,R2,R3 ;R0(R2)(R3)(1)就程序本身而言就程序本身而言,哪些指令之间发生何种数据相关哪些指令之间发生何种数据相关?(2)画出按指令序列的顺序流动的时空图画出按指令序列的顺序流动的时空图,共使用了多共使用了多少个时钟周期少个时钟周期?解解:(1)若若3条指令顺序流动条指令顺序流动,则指令则指令k与指令与指令k+1对寄存对寄存器器R1发生操作数的发生操作数的“先写后读先写后读”相关相关.若若3条指令异条指令异步流动步流动,则指令则指令k+1与指令与指令 k对寄存器对寄存器R1发生发生“先读先读后写后写”相关相关,指令指令k+2与指令与指令k+1对寄存器对寄存器R0发生发生“写写-写写”相关相关.(2)若若3条指令顺序流动条指令顺序流动,则流水线的时空图如下则流水线的时空图如下:k kk kK+1K+1K+1K+1K+1K+2K+2K+2k kK+1K+1K+2kK+1K+2执行执行译码译码取指取指T()由图可以看出由图可以看出,由于指令由于指令k与指令与指令k+1之间的之间的“先写先写后读后读”相关相关,指令指令k+1多延迟了多延迟了2个时钟周期个时钟周期.3条指条指令顺序流动共需要令顺序流动共需要13个时钟周期个时钟周期.例例2:2:一条线性静态多功能流水线由一条线性静态多功能流水线由6 6个功能段组成个功能段组成,加法操作使用其中的加法操作使用其中的1 1、2 2、3 3、6 6功能段功能段,乘法操作使乘法操作使用其中的用其中的1 1、4 4、5 5、6 6功能段功能段,每个功能段的执行时间每个功能段的执行时间均为均为 .流水线的输出与输入端之间有直接数据通流水线的输出与输入端之间有直接数据通路路,且设置有足够的缓冲寄存器且设置有足够的缓冲寄存器.试用尽可能短的时试用尽可能短的时间计算间计算 ,画流水线时空图画流水线时空图,并计算流水线并计算流水线的实际吞吐率、加速比和效率的实际吞吐率、加速比和效率.解解:为了减少流水线中发生先写后读相关的次数为了减少流水线中发生先写后读相关的次数,使流水线完使流水线完成计算的时间尽可能短成计算的时间尽可能短,采用下列算法计算采用下列算法计算F:F:F=(aF=(a1 1bb1 1a a2 2bb2 2)(a a3 3bb3 3a a4 4bb4 4)(a(a5 5bb5 5a a6 6bb6 6)先计算括号内的先计算括号内的6 6次乘法次乘法,再做括号内的再做括号内的3 3次加法次加法,然后再做括然后再做括号外的两次加法号外的两次加法.123456789101112 23456123456789101178910111234567891011S6S5S4S3S2S1t由时空图可得的实际吞吐率、加速比和效率分别为由时空图可得的实际吞吐率、加速比和效率分别为:3.5多发射处理机及其性能多发射处理机及其性能常规的流水处理机是单发射处理机，即处理机在一个常规的流水处理机是单发射处理机，即处理机在一个时钟周期只解释一条指令，通常将一个时钟周期平均时钟周期只解释一条指令，通常将一个时钟周期平均发射指令的条数称为处理机的指令级并行度发射指令的条数称为处理机的指令级并行度（Instruction l