[研究生入学考试]四川大学计算机系统结构第三章.ppt

第三章 流水线技术,提高计算机性能（速度）的两个重要方法： 1. 缩短执行每条指令所需的平均周期数CPI，如：RISC技术。 2. 提高处理机在执行指令中的并行度，即同一时刻中处理机内同时运行多条指令。如：采用流水线技术。,3.1 重叠执行和先行控制,一.指令的重叠执行 一条指令的执行过程可以粗略地分为：取指令、分析和执行三个阶段，且这个次序是不能改变的。,用Ti表示执行一条指令所需的时间，可以写成： Ti = t取指令 + t分析 + t执行,3.1 重叠执行和先行控制,如果连续执行一段程序，计算机对前后相邻指令的执行过程可以有两种不同的选择: 1.顺序执行方式，即等前一条指令执行完毕，紧接着执行下一条指令.,2. 让前后连续的指令在处理机内以重叠的方式执行.,3.1 重叠执行和先行控制,一次重叠执行方式:,二次重叠执行方式:,如果三个阶段所需时间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相等的假设就可能不成立，所得到的节约三分之二时间的结论也被动摇了。下图形象地表示了这种情况所造成的影响。,这种情况可用先行控制技术来缓解。,3.1 重叠执行和先行控制,2采用先行控制技术的处理机,3.1 重叠执行和先行控制,缓冲栈实际上是一个以先进先出（FIFO）方式工作的移位寄存器组，上图表示了缓冲栈所处的地位。前置部件的输出不直接送入后置部件，而是通过缓冲栈暂存后才输出。,3.1 重叠执行和先行控制,3先行控制原理,通过先行指令计数器PC1预取指令序列,通过现行指令计数器PC取出现行指令,指令分析器,指令分析器:对取自先行指令栈的指令进行预处理. 1.对于程序控制类的指令，如转移指令，指今分析器可以直接完成指令的执行. 2.对于数据运算型指令，指令分析器要将它们变换成寄存器寄存器型(RR型)指令，即将操作数预先存到寄存器中，使指令能快速执行.,立即寻址 传数据,变址寻址或存储器型指令,传地址,RR*指令,3.1 重叠执行和先行控制,先行控制技术中采取了两个根本的措施：指令预处理技术和缓冲技术。由于指令和数据的缓冲，保证了指令分析和指令的执行都能全速地运行。,缓冲栈深度应满足以下关系： D取指栈D操作栈D读栈D写栈,3.2 流水线的基本概念,一.什么是流水线 1. 流水线技术（pipelining） 把一个重复的过程分解为若干个子过程，每个子过程由专门的功能部件来实现。 把多个处理过程在时间上错开，依次通过各功能段，这样，每个子过程就可以与其他的子过程并行进行。 流水线中的每个子过程及其功能部件称为流水线的级或段，段与段相互连接形成流水线。流水线的段数称为流水线的深度。,3.2 流水线的基本概念,2流水线结构 重叠执行是流水线结构的思想基础，只要在指令分析器与指令执行部件之后都加上一个锁存器，就成了一个简单的流水线结构。,在流水线的每一个功能部件的后面都要有一个缓冲寄存器，或称为锁存器、闸门寄存器等，它的作用是保存本流水段的执行结果。,3时空图 时空图可以直观地表现流水线的工作过程,横轴表示时间，即各条指令在处理机中经历各个操作时占用的时间段。如果各级执行所需的时间相等，在横轴上应表现为等距离的时间段。 纵轴表示空间，即流水线的各个子操作过程，通常也称为“功能段”。,3.2 流水线的基本概念,4流水线的工作特点 1）一条流水线通常由多个流水段组成，在每一个流水段有专门的功能部件来实现。 2）各流水段所需的时间应尽可能相等，否则将引起流水线堵塞、断流。 3）流水线每个功能部件后面都有一个缓冲寄存器，称为流水寄存器。 4）流水线的工作一般分为3个阶段，即建立（填入）、填满和排空。 5）流水线技术适合于大量重复的时序过程，只有在输入端不断地提供任务，才能充分发挥流水线的效率。,3.2 流水线的基本概念,二. 流水线的种类 1、 按处理机分类 操作部件级 为最低级别的流水线。是把处理机的算术逻辑运算部件分段。如果某一部件的处理过程比较复杂，如浮点运算,需要较长的时间。这时可以将该部件分为若干子部件，分别完成浮点运算中有关的子操作，这种在部件范围内形成的流水线称为操作部件级流水线。,3.2 流水线的基本概念,一个浮点加法部件的流水线：,部件级流水线通常是流水线处理机中的一部分，这时的处理机由于流水级数较多，又称为超流水线处理机。,3.2 流水线的基本概念,处理机级 又称为指令流水线，就是将一条指令的解释执行过程分解成若干个子过程，使每个子过程分别在一个部件中完成。 处理机间级 处理机间流水线通常是多处理机系统中对任务采取的一种处理策略。,3.2 流水线的基本概念,上图是处理机间流水线示意图，图中每个处理机是以任务为单位进行处理的，而处理机间的任务传递则是由公用存储器完成的。应当指出，图中给出的是一个处理的“流水”，并没有涉及更多的硬件结构。实际上这个过程更应该看作是一种任务的调度策略。,3.2 流水线的基本概念,2、 按流水线功能多少分类 单功能流水线 指一条流水线只能完成一种单一的任务。 多功能流水线 指能够在一个时间段内或不同时间段间改变部件之间的连接，从而达到改变其功能的流水线。,3.2 流水线的基本概念,在标量运算中，各种运算是混在一起的。,3、 按照工作方式分类 静态流水线 当执行某一规定功能的指令全部流出后，才允许改变部件间连接的流水线。,（可以是单功能流水线也可以是多功能流水线）,3.2 流水线的基本概念,动态流水线 没有这种时间上的限制，可以在任何时候根据需要改变其连接。,（只能是多功能流水线）,3.2 流水线的基本概念,4、 按连接方式分类 线性流水线 是指在部件上没有反馈连接的流水线。在这种流水线中，指令依次通过各个部件仅一次，完成指令执行的全过程。目前所使用的流水线绝大部分都是这类线性流水线。 非线性流水线 是指在各部件除了串行的连接外，还通过反馈线使某些部件得以重复使用。指令在通过这种流水线时，可能在反馈部件上重复运行若干次。,3.2 流水线的基本概念,非线性流水线工作特性示意图,3.2 流水线的基本概念,5、 按流入流出顺序分类 顺序流水线 其输出的结果与输入的次序相同，早期的流水线又称为顺序流水线。 乱序流水线 将原始的输入次序打乱，以最有利于处理机执行的方式运行，在输出结果时才恢复原次序。 在一些现代处理机中，如Pentium 4在流水线运行过程中采用了乱序方式。,3.2 流水线的基本概念,除了上述几种分类方法以外，还可以根据各种不同的观点对流水线进行区分。比如： 按照数据表示方式的不同，可以将流水线分为标量流水线和向量流水线两种。在标量处理机中使用的当然是标量流水线。 根据流水线在各级之间流动时的控制方法不同，又可以分成同步和异步两种流水线。,3.2 流水线的基本概念,处理机内的指令流水线都是同步流水线，即使用统一的时钟控制各级同时开始同时完成动作。 而处理机间的流水线通常都是异步流水线，需要在任务传送时进行应答，以确保传输的可靠性。,3.3 流水线的性能指标,吞吐率、加速比和效率是表明流水线性能的主要指标。 一.吞吐率 把流水线在单位时间内完成的任务量定义为吞吐率。,其中, n为完成任务的总数，在指令流水线中就是完成的指令总条数；Tk是完成n个任务所用的时间。,3.3 流水线的性能指标,各级执行时间相等的流水线 一条k级的流水线执行n条指令的时空图:,所需的总时间为：,3.3 流水线的性能指标,当n时，（k 1）可以忽略不计，得到的最大吞吐率为:,所以，吞吐率为:,3.3 流水线的性能指标,各级执行时间不等的流水线,执行时间不等的流水线时空图,3.3 流水线的性能指标,吞吐率的一般表示式为:,同样方法可以得到当n时的最大吞吐率为：,3.3 流水线的性能指标,如果流水线中各级的执行时间不相等，其中时间最长者就成了流水线中的“瓶颈”。瓶颈问题对流水线的吞吐率影响是明显的，所以消除“瓶颈”是设计流水线的一个重要原则。 “瓶颈”问题的消除 采用的方法主要有两种： 1）分割瓶颈部件的工作 2）重复设置瓶颈部件,3.3 流水线的性能指标,消除“瓶颈”影响的两种方法示意图：,两种方式在效果上是可以等效的，在输入n条指令的情况下，实际吞吐率都为：,3.3 流水线的性能指标,不消除“瓶颈”时的吞吐率：,两种方式在效果上是可以等效的，在输入n条指令的情况下，实际吞吐率都为：,3.3 流水线的性能指标,二.加速比 处理同一批任务，不用流水线与采用流水线时所花费的时间之比，称为流水线的加速比。 如果不用流水线所用的时间为T0，用了流水线所用时间为Tk，那么加速比就是： S = T0/Tk,3.3 流水线的性能指标,不用流水线时，每条指令执行时必须在时间上顺序地完成各处理步骤，那么n条指令所需时间就为T0 = nkt。而一个采用流水线的处理机所需时间为Tk = ( k + n 1 )t。 所以加速比就为,同样办法可以得到最大加速比,3.3 流水线的性能指标,如果考虑各级执行时间不等的情况时，一条指令的执行时间是各级运行时间之和。在没有流水线时，n条指令应是一条指令的n倍。于是，可得到加速比为,3.3 流水线的性能指标,三. 效率 效率被定义为：,各级执行时间相等的流水线效率等于：,3.3 流水线的性能指标,显然，n越大，空闲部件占据的比例就小，流水线表现的效率越高。最高效率为：,通过类似的分析方法，我们也可以得到在各 级执行时间不等的流水线中的效率计算方法。,3.3 流水线的性能指标,同样，,效率公式：,加速比公式：,两者相结合得出：E = S/k 或 S = k 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为：,这时流水线的加速比为:,而效率达到：,效率为何仍然不高？,3.3 流水线的性能指标,整个流水线的效率很低的原因： （1） 存在有数据相关，当发生数据相关时，必须等待前一个运算结果产生之后，下一个运算才能开始； （2） 流水线有填入与排空部分，当输入到流水线中的任务不多时，填入与排空部分所占的比例比较大。,练习：线性多功能静态流水线，输入任务是不连续的情况，计算流水线的吞吐率、加速比和效率。 用TIASC计算机的多功能静态流水线计算两个向量的点积： ZABCDEFGH,3.3 流水线的性能指标,解：为了尽量减少数据相关性，充分发挥流水线的作用。计算的顺序应该是先做4个乘法：AB、CD、EF和GH，然后做两个加法ABCD和EFGH，最后求总的结果Z。,Z(AB)(CD)(EF)(GH),1,2,3,4,5,7,6,3.3 流水线的性能指标,从流水线时空图中看到，用20个时钟周期完成了7个运算。当每一个功能段的延迟时间都为t时，,有：Tk20 t ，n7。流水线的吞吐率TP为,如果采用顺序执行方式，完成一次乘法要用4个t ，完成一次加法要用6个t ，则完成全部运算要用,则流水线的加速比S为：,整个流水线共有8段，流水线效率E为：,效率更低的原因？,原因：静态流水线造成加法运算必须在乘法运算所有指令流出流水线后才能进行。 解决：改为动态流水线 课后任务： 采用动态流水线对其性能进行分析,3.3 流水线的性能指标,四、流水线设计中的若干问题： 瓶颈问题 当流水线各段不均匀时，机器的时钟周期取决于瓶颈段的延迟时间。 在设计流水线时，要尽可能使各段时间相等。 流水线的额外开销 流水寄存器延迟 时钟偏移开销 冲突问题 流水线设计中要解决的重要问题之一。,3.4 流水线的相关与冲突,一、一个经典的5段流水线 一条指令的执行过程分为5个周期：取指令周期（IF）、指令译码/读寄存器周期（ID）、执行/有效地址计算周期（EX）、存储器访问分支完成周期（MEM）、写回周期（WB）。,3.4 流水线的相关与冲突,三类指令对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.D F2，F6，F4 ADD.D F6，F0，F12 SUB.D F8，F6，F14 DIV.D和ADD.D存在反相关。 进行寄存器换名（F6换成S）后，变成： DIV.D F2，F6，F4 ADD.D S，F0，F12 SUB.D F8，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 流水线的相关与冲突,（一）结构冲突 指多条指令进入流水线后，在同一时间争用同一功能部件，从而发生冲突。,访存冲突,3.4 流水线的相关与冲突,3.4 流水线的相关与冲突,解决方法：暂停一拍（也称为流水线气泡，简称气泡）。,3.4 流水线的相关与冲突,3.4 流水线的相关与冲突,（二）数据冲突 1、数据冲突 指由于流水线中各指令重叠执行，使得原来对操作数的访问顺序发生变化，从而引起的一种数据冲突。 如：DADD R1，R2，R3 DSUB R4，R1，R5,写R1,读R1,3.4 流水线的相关与冲突,2、解决办法 采用定向传送技术（旁路技术或相关专用通路技术）。,旁路传送,3.4 流水线的相关与冲突,3.4 流水线的相关与冲突,3、数据冲突类型 根据指令对同一寄存器读和写的先后顺序，数据冲突可分为三种类型： 1）RAW（读超前于写）,解决方法一：按序流动（顺序流动）的流水线中，用定向传送技术。,指流水线中流出的结果与流入指令的次序是一致的。,但是，定向技术并不能解决所有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,3.4 流水线的相关与冲突,由于允许非按序执行，使流水线的停顿时间大为减小，有利于提高流水线的吞吐率和效率。但同时还应该注意可能由此引起的另两种冲突: 2）WAR（写超前于读） 原程序要求对同一单元进行先读后写的操作，可能因为非按序执行成为先写后读，造成出错。 3）WAW（写后写） 原程序中如果两条指令都要对同一单元进行写数操作，可能因为非按序执行的原因，改变了两条指令写入的次序。,3.4 流水线的相关与冲突,（三）控制冲突 1、控制冲突 流水线遇到分支指令（转移指令）和其他会改变PC值的指令所引起的冲突。 分支指令的处理,末尾处更新PC值,3.4 流水线的相关与冲突,转移指令对流水线的影响 例:设在某一程序中， 条件转移指令在程序中所占的比例为25%，其中转移成功的概率为2/3。试计算执行一条指令的平均时钟周期数。 解：设执行一条指令的平均时钟周期数为Pi，则 Pi = (1- 25%) 1 + 25%(3+1) = 1.75,3.4 流水线的相关与冲突,2、有关措施 为了减小分支延迟造成的损失，可采用以下措施： 1）在流水线中尽早判断出分支转移是否成功。 2）尽早计算出分支目标地址。 两种措施同时采用，缺一不可。 假设该两步工作被提前到ID段完成，即分支指令是在ID段的末尾执行完成，所带来的分支延迟为一个时钟周期。,3.4 流水线的相关与冲突,为了减小分支延迟造成的损失，还可通过软件（编译器）来减少分支延迟，常见的有以下几种： （1）预测分支失败 允许分支指令后的指令继续在流水线中流动，就好象什么都没发生似的。 若确定分支失败，将分支指令看作是一条普通指令，流水线正常流动。 若确定分支成功，流水线就把在分支指令之后取出的所有指令转化为空操作，并按分支目地重新取指令执行。,3.4 流水线的相关与冲突,对于上例： 设在某一程序中， 条件转移指令在程序中所占的比例为25%，其中转移成功的概率为2/3。试计算执行一条指令的平均时钟周期数。 假设采用预测分支失败，则 执行一条指令的平均时钟周期数为Pi为： Pi = (1- 25%) 1 + 25%1/3 1+ 25%2/3(1+1) 1.17,3.4 流水线的相关与冲突,（2）预测分支成功 假设分支转移成功，并从分支目标地址处取指令执行。 起作用的前题：先知道分支目标地址，后知道分支是否成功。 前述5段流水线中，由于判断分支是否成功与分支目标地址计算是在同一流水段完成，这种方法没有任何好处。,3.4 流水线的相关与冲突,（3）采用延迟转移技术 方法一：从前调度,方法三：由失败处调度,方法二：从目标处调度,补充：非线性流水线的竞争与调度 1、非线性流水线中可能发生的冲突,非线性流水线中由于有些段需要在时间上复用，就不能像线性流水线那样逐时段连续地输入指令。把前一条指令输入开始到下一条指令输入为止的时间差，称为启动距离。 如果所采用的启动距离不合适，可能会在某些部件的使用上发生冲突。,流水线中任何一部件在同一时间段中只能为一条指令服务，出现争用现象是不允许的。 为此必须恰当地选择后一条指令输入的时间，既不使发生冲突，又不致使流水线的效率降低太多。那些会引起冲突的启动距离，被称为禁止启动距离。 将在任何时间都不会发生冲突的启动距离称为启动循环。,2、最优调度方法 为了避免冲突，就要对指令输入流水线的时间进行控制，这个任务就是流水线的无冲突调度。 1）根据预约表写出禁止向量 禁止向量F是一个流水线中所有禁止启动距离的集合。为了找出所有的禁止启动距离，必须考察各段的复用情况。S1在1，4，7三个时段中使用，从第1时段到第4时段的距离为3t（4t 1t = 3t），显然这是一个禁止启动距离。,同样理由，可以得到S1的另外两个禁止启动距离：7t 4t = 3t；7t 1t = 6t。 将这种计算所有打“”时段之间距离的方法施于其他三个部件，可以得到下面的结果: S2的禁止启动距离：3t S3的禁止启动距离：t，3t，4t 禁止向量F =（1, 3, 4, 6）,向量规定，如果某启动距离为禁止距离，则该位为“1”，反之则为“0”。于是，根据禁止向量，可以得到与之对应的初始冲突向量。 如上例中，禁止向量F =（1, 3, 4, 6），则对应的初始冲突向量C =（101101）。 由于第2、5位为“0”，因此，可以与当前指令间隔2拍（2t ）或5拍调入下一个指令。,2） 由禁止向量变换成初始冲突向量 用以表示非线性流水线工作时各启动距离特性的二进制序列，称为冲突向量。由预约表上第一条指令工作过程所求得的冲突向量称为初始冲突向量。 冲突向量用C =（CmCm-1C2C1 ）表示，其中m为禁止向量的最大值，如果执行一条指令需要k个时段，那末m k 1。于是，冲突向量的各位就可以理解为C1表示启动距离为1t时的冲突情况；C2是启动距离为2t时的冲突情况；,3）根据初始冲突向量推算出全部冲突向量 按照某一个无冲突启动距离输入后续指令后，由于在流水线中存在一条以上指令，使各部件的使用趋于复杂，也必然造成冲突情况发生改变。为了保证后续指令的正常输入，必须找出所有变化了的冲突向量。 根据例子，初始冲突向量C0 =（101101），由于第2、5位为“0”，因此，可以与当前指令间隔2拍（2t ）或5拍调入下一个指令。,若选择第2条指令在2拍后调入流水线：,第一条指令的当前禁止向量： F =（1-2, 3-2, 4-2, 6-2）=（1，2，4） 则此时初始冲突向量应该逻辑右移两位，形成第一条指令的当前冲突向量。如（ C0 =（101101），即：,为使第3条指令调入后不与前两条指令发生冲突，新的冲突向量应该是第1条指令的当前冲突向量与第2条指令的初始冲突向量按位进行“或”运算。,对C1继续推算新的冲突向量，因为其中只有一个0， 后续向量也只有一个。,在这个例子中，完成了全部推算后，只找到一个新的冲突向量C1。,4） 画出表示冲突向量迁移的有向图,3.5 流水线的实现,MIPS的一种简单实现 一. 实现MIPS指令子集的一种简单数据通路。（P87 图3.43） 该数据通路的操作分成5个时钟周期 取指令 指令译码/读寄存器 执行/有效地址计算 存储器访问/分支完成 写回 只讨论整数指令的实现（包括：load和store，等于0转移，整数ALU指令等。）,3.5 流水线的实现,二. 一条MIPS指令最多需要以下5个时钟周期： 1.取指令周期（IF） IRMemPC NPCPC+4 2.指令译码/读寄存器周期（ID） A Regsrs B Regsrt Imm （IR16）16#IR1631）,指令的译码操作和读寄存器操作是并行进行的。 原因：在MIPS指令格式中，操作码字段以及rs、rt字段都是在固定的位置。这种技术称为固定字段译码技术。,3.5 流水线的实现,3. 执行/有效地址计算周期（EX） 不同指令所进行的操作不同： 存储器访问指令 ALUoA + Imm 寄存器寄存器ALU指令 ALUoA func B 寄存器立即值ALU指令 ALUoA op Imm 分支指令 ALUoNPC+（Imm2）； cond（A = = 0）,将有效地址计算周期和执行周期合并为一个时钟周期，这是因为MIPS指令集采用loadstore结构，没有任何指令需要同时进行数据有效地址的计算、转移目标地址的计算和对数据进行运算。,3.5 流水线的实现,4. 存储器访问/分支完成周期（MEM） 所有指令都要在该周期对PC进行更新。除了分支指令，其他指令都是做PCNPC。 在该周期内处理的MIPS指令仅仅有load、store和分支三种指令。 （1）存储器访问指令 LMDMemALUo 或者 MemALUoB （2）分支指令 if （cond） PC ALUo else PCNPC,3.5 流水线的实现,5. 写回周期（WB） 不同的指令在写回周期完成的工作也不一样。 寄存器寄存器ALU指令 Regsrd ALUo 寄存器立即数ALU指令 Regsrt ALUo load指令 Regsrt LMD,3.5 流水线的实现,不采用单周期实现方案的主要原因 1.对于大多数CPU来说，单周期实现效率很低，因为不同的指令所需完成的操作差别相当大，因而所需要的时钟周期时间也大不一样。 2.单周期实现时，需要重复设置某些功能部件，而在多周期实现方案中，这些部件是可以共享的。,练习： 在一个如下图所示的线性流水线,各级运行所需的时间如下图中所标。,1）画出该流水线工作时空图。 2）如果输入的程序没有数据相关和转移指令，在连续执行10条指令后，计算该流水线的吞吐率和效率。 3）提出改进吞吐率、加速比和效率的方法，并计算改进后的性能（即改进后的吞吐率、加速比和效率）。,解： 在一个如下图所示的线性流水线,各级运行所需的时间如下图中所标。,1）画出该流水线工作时空图。,2）如果输入的程序没有数据相关和转移指令，在连续执行10条指令后，计算该流水线的吞吐率和效率。,= 5/（12 Dt）,= 0.625,3）提出改进吞吐率、加速比和效率的方法，并计算改进后的性能（即改进后的吞吐率、加速比和效率）。 解: 执行分为两级,分别为Dt，写回分为两级，分别为Dt。,= 0.67/Dt,E = TP t = 10/15 = 0.67,S = k E = 4,3.6 向量处理机,银河-I巨型计算机 银河-II巨型计算机,3.6 向量处理机,一.标量处理与向量处理 一个既有大小又有方向的量称为向量。 如果有下面的一个向量运算，其中A和B都是NN的矩阵：,3.6 向量处理机,要求计算: C=AB,3.6 向量处理机,在标量计算机中，我们可以很容易的编出一段循环程序，进行这个矩阵乘法运算，比如一段用FORTRAN语言编的程序段为： DO 100 I = 1, N DO 100 J = 1, N C(I,J) = 0.0 DO 100 K = 1, N C(I,J) = C(I,J) + A(I,K) * B(K,J) 100 CONTINUE,如果将这段程序编译成一个假想的汇编程序表示，就成了一个三重循环的汇编程序： INITIALIZE I=1, J=1, K=1 10 CLR C(I,J) 20 LOAD A(I,K) LOAD B(K,J) MUL A(I,K), B(K,J) ADD C(I,J), A(I,K) / C(I,J)C(I,J) + A(I,K)B(K,J) INC K / KK+1 IF KN GOTO 20 STORE C(I,J) INC J / JJ+1 IF JN GOTO 10 INC I / II+1 IF IN GOTO 10 HALT,上述操作如果由向量计算机来完成，其可能的程序如下所示： DO 100 I=1,N C(I,J) = 0.0 (J = 1:N) DO 100 K=1,N C(I,J) = C(I,J) + A(I,K) * B(K,J) (J=1:N) 100 CONTINUE 从形式上看，这两段程序差不多，但是在向量计算机上，不管是单元清零，还是做乘法和加法，一条语句处理的都是N个（或N对）数据，而不是一个或一对。,3.6 向量处理机,要求计算: C=AB,3.6 向量处理机,二.向量处理机的概念与特点 1向量处理机 把向量数据表示与流水线结合起来，就构成了向量流水处理机，简称为向量流水机或向量处理机。 向量处理机的处理对象是向量元素。,3.6 向量处理机,2向量流水处理的特点 1）在向量机中，一条向量指令往往针对的是一个向量，因此一条向量指令相当于一个标量循环。 2）在向量运算中，每一个结果元素仅与参加运算的元素有关，与上一次运算的值无关。 3）若向量指令所要访问的向量元素相邻，则可以将其存储到多体交叉存储器中。 4）一般向量机中，允许访问存储器与有效地址的计算流水化，在高档向量机中还允许多个向量操作同时进行，即多向量并行操作。,3.6 向量处理机,三向量处理的几种方式 向量处理的对象是一些数组，在实际处理时，可以由编译程序选择不同的处理方式。 假定有一个向量运算，其程序表示如下： DO 100 i = 1,N,1 100 Fi = Ai B + Di ( Ai - Ei ) 按照处理元素的排列次序，可以把处理方式分为三种。 横向处理方式 纵向处理方式 纵横处理方式,DO 100 i = 1,N,1 100 Fi = Ai B + Di ( Ai - Ei ) 横向处理方式 先取i=1的各数组元素,计算出F1的值,再依次算出Fi的值。 纵向处理方式,Fi = Ai * B + Di * ( Ai - Ei ),求出整个A的值，作为第一个运算单元,第二个运算单元,第三个运算单元, 纵横处理方式 将被处理的数组分割为比较小的数组，在这个较小的数组中进行纵向处理，然后在各小数组处理的基础上进行横向处理。,3.6 向量处理机,四.向量处理机的结构 1. 向量处理机的基本结构 包括： 标量流水部件：标量功能部件、若干标量寄存器 向量流水部件：向量功能部件、向量存取部件、向量寄存器、向量控制器等 2. 向量处理机的类型 存储器-存储器型 寄存器-寄存器型,3.6 向量处理机,存储器-存储器结构,3.6 向量处理机,在数据通道中加入可变长度的延迟电路方案框图,3.6 向量处理机,A B C,由8个存储器模块组成存储系统的向量处理机,假定A和B向量都只有8个元素，运算结果C向量也有8个元素。这个向量处理机的工作过程可以用下图表示。,3.6 向量处理机,由8个存储器模块组成存储系统的向量处理机,A B C,改变向量存储方法后可以得到如下的时空图：,3.6 向量处理机,寄存器-寄存器结构 以CRAY-1机为例 美国CRAY公司 1976年 每秒1亿次浮点运算 时钟周期：12.5 ns 1.CRAY-1的基本结构 1）功能部件 共有12条可并行工作的单功能流水线，可分别流水地进行地址、向量、标量的各种运算。,3.6 向量处理机,3.6 向量处理机,6个单功能流水部件：进行向量运算 整数加（3拍） 逻辑运算（2拍） 移位（4拍） 浮点加（6拍） 浮点乘（7拍） 浮点迭代求倒数（14拍） 括号中的数字为其流水经过的时间，每拍为一个时钟周期，即12.5 ns。,2）向量寄存组V 由512个64位的寄存器组成，分成8块。 编号：V0V7 每一个块称为一个向量寄存器，可存放一个长度（即元素个数）不超过64的向量。 每个向量寄存器可以每拍向功能部件提供一个数据元素，或者每拍接收一个从功能部件来的结果元素。,3.6 向量处理机,3）标量寄存器S和快速暂存器T 标量寄存器有8个：S0S7 64位 快速暂存器T用于在标量寄存器和存储器之间提供缓冲。 4）向量屏蔽寄存器VM 64位，每一位对应于向量寄存器的一个单元。 作用：用于向量的归并、压缩、还原和测试操作、对向量某些元素的单独运算等。,3.6 向量处理机,3.6 向量处理机,2.CRAY-1向量处理的显著特点 1）每个向量寄存器Vi都有连到6个向量功能部件的单独总线。 2）每个向量功能部件也都有把运算结果送回向量寄存器组的总线。 3）只要不出现Vi冲突和功能部件冲突，各Vi之间和各功能部件之间都能并行工作，大大加快了向量指令的处理。,3.6 向量处理机,Vi冲突：并行工作的各向量指令的源向量或结果向量使用了相同的Vi。 例如：源向量相同 V3V1V2 V5V4V1 功能部件冲突：并行工作的各向量指令要使用同一个功能部件。 例如：都需使用乘法功能部件 V3V1V2 V5V4V6,3.CRAY-1向量指令类型 1）Vk Vi op Vj 2）Vk Si op Vj 3）Vk 主存 4） 主存 Vi,3.6 向量处理机,五.提高向量处理机性能的方法 主要有： 设置多个功能部件，使它们并行工作。 采用链接技术，加快一串向量指令的执行。 采用循环开采技术，加快循环的处理。 采用多处理机系统，进一步提高性能。,3.6 向量处理机,1、设置多个功能部件 设置多个独立的功能部件。这些部件能并行工作，并各自按流水方式工作，从而形成了多条并行工作的运算操作流水线。 例如：CRAY-1向量处理机有4组12个单功能流水部件： 向量部件：向量加，移位，逻辑运算 浮点部件：浮点加，浮点乘，浮点求倒数 标量部件：标量加，移位，逻辑运算， 数“1”/计数 地址运算部件：整数加，整数乘,2. 向量链接技术 所谓“链接”就是将相关两条流水线对向量的处理进行前后衔接的技术。 比如，有下面的一段程序： ADDV V1，V2，V3 ； V1 V2 + V3 MULTV V4，V1，V5 ； V4 V1 V5 两条指令存在先写后读数据相关。若向量寄存器V1能在同一时钟周期内既能接收加法运算的结果，又能把这一结果作为下一条指令的源操作数传送给乘法运算功能部件，那么就能使两个功能部件链接起来工作。,3.6 向量处理机,假定，一个程序段有以下三个向量操作： V3 A V2 V0 + V1 V4 V2 * V3,假设：把向量数据元素送往向量功能部件以及把结果存入向量寄存器需要一拍时间，从存储器中把数据送入访存功能部件需要一拍时间。,1. 3条指令全部用串行方法执行，则执行时间为： （161）N1（161）N1 （171）N1 = 3N 22 （拍）,2. 前两条指令并行执行，然后再串行执行第3条指令，则执行时间为： （161）N1（171）N1 = 2N 15 （拍）,3. 第1、2条向量指令并行执行，并与第3条指令链接执行。从访存开始到把第一个结果元素存入V4所需的拍数（亦称为链接流水线的建立时间）为： （161） （171） = 17 （拍） 3条指令的执行时间为： （161） （171） （N1） = N16 （拍）,V3 A V2 V0 + V1 V4 V2 * V3,进行向量链接的要求 保证：无向量寄存器使用冲突和无功能部件使用冲突 1）前一条指令的结果是后一条指令的输入。 2）当一条向量指令的两个源操作数分别是两条先行指令的结果寄存器时，要求先行的两条指令产生运算结果的时间必须相等，即要求有关功能部件的通过时间相等。 3）要进行链接执行的向量指令的向量长度必须相等，否则无法进行链接。 4）只有在前一条指令的第一个结果元素送入结果向量寄存器的那一个时钟周期才可以进行链接。,例. 以下两条向量指令只能串行执行的是（ ） A. V1 存储器 B. V2 V0+V1 V3 V1+V2 V5 V3*V4 C. V2 V0+V1 D. V2 V0+V1 V5 V3+V4 V5 V2*V3 答案：C,3.6 向量处理机,3. 分段开采技术 如果向量的长度大于向量寄存器的长度，该如何处理呢？ 当向量的长度大于向量寄存器的长度时，必须把长向量分成长度固定的段，然后循环分段处理，每一次循环只处理一个向量段。这种技术称为分段开采技术。 例.设A和B是长度为N的向量，考虑在Cray-1向量处理器上实现以下的循环操作： DO 10 I = 1，N 10 A（I）= 5.0 * B（I） + C,3.6 向量处理机,5.0 * B（I） + C 当N 64时，可以用以下指令序列： S1 5.0 ；将常数5.0送入标量寄存器S1 S2 1.0 ；将常数1.0送入标量寄存器S2 VL N ；在向量长度寄存器VL中设置向量长度N V0 B ；从存储器中将向量B读入向量寄存器V0 V1 S1 V0 ；向量B中的每个元素分别和常数S1相乘 V2 S2 + V1 ；向量V1中的每个元素分别和常数S2相加 A V2 ；将计算结果从向量寄存器V2存入存储器的向量A 当N 64时，就需要进行分段开采。 循环次数K ：,余数L：,S1 5.0 ；将常数5.0送入标量寄存器S1 S2 1.0 ；将常数1.0送入标量寄存器S2 VL L ；在向量长度寄存器VL中设置向量长度L V0 B ；从存储器中将向量B0L-1读入向量 ； 寄存器V0 V1 S1 * V0 ；向量B中的每个元素分别和常数S1相乘 V2 S2 + V1 ；向量V1中的每个元素分别和常数S2相加 A V2 ；将计算结果从向量寄存器V2存入存储器 ；的向量A0L-1,处理余 数部分, 计算L 个元素,3.6 向量处理机,For (I=0 to K-1) V0 B ；从存储器中将向量BL+I*64L+I*64+63 ；读入向量寄存器V0 V1 S1 * V0 ；向量B中的每个元素分别和常数S1 ；相乘； V2 S2 + V1 ；向量V1中的每个元素分别和常数S2 ；相加 A V2 ；将计算结果V2存入存储器的向量 ； AL+I*64 L+I*64+63 ,循环 K次, 分段 处理,3.6 向量处理机,4. 采用多处理机系统 许多新型向量处理机系统采用了多处理机系统结构。例如： CRAY-2 包含了4个向量处理机 浮点运算速度最高可达1800MFLOPS CRAY Y-MP、C90 最多可包含16个向量处理机,3.6 向量处理机,3.6 向量处理机,六. 向量处理机的性能评价 在向量处理机中, 衡量向量处理机性能的指标主要有： 向量指令的处理时间Tvp 机器向量长度为无穷大时的向量处理机的峰值性能R 半性能向量长度n1/2 向量长度临界值nv,3.6 向量处理机,向量指令的处理时间Tvp （1）假定指令是预取的，那么一条向量指令的执行时间将由三部分组成，如下图所示:,其中， 建立段Ts是为向量指令的执行进行准备的阶段。 第二段Tvf是使被处理的向量中第一个（对）元素通过流水线所花费的时间。 第三段是所有后续元素通过流水线所花费的时间，Tc为流水线“瓶颈”段的执行时间。,得到向量指令执行时间:,通常，在数字计算机中，所有的操作时间都应是时钟周期的整数倍，而且也不会在流水线中存在“瓶颈”，假定基本时钟周期为TClk，上式可以写成:,式中的s和e表示前两段时间是时钟周期的多少倍，即需要多少个时钟周期。,上式也可以写成:,式中Tstart表示向量功能部件启动所需的时钟周期数，n为向量元素的个数。,（2） 一组向量指令及其编队运行 一组向量指令的执行时间并不是每条指令执行时间的简单相加，而必须根据具体处理机作具体分析。 影响一组向量指令运行时间要素是：向量中元素的个数；组织编队的情况。 将能够组合在一起并行运行的指令称为一个“编队”。,3.6 向量处理机,例1.下面是一组向量指令，假定每种指令都有一个功能流水线，它们可分成几个编队？ LV V1，RX ；从存储器取向量X到V1 MULTSV V2，S0，V1 ；标量S0乘向量V1，存入V2 LV V3，RY ；从存储器取向量Y到V3 ADDV V4，V2，V3 ；向量V2加上向量V3，存入V4 SV RY，V4 ；向量V4保存到RY中 解：按照原指令的排列次序对指令进行分析。由于第二条指令的执行依赖第一条指令的执行结果，这两条指令之间存在数据相关，不能成为一个编队。第一条指令与第三条指令之间没有数据相关，但是发生了功能部件冲突，不可能同时执行，所以也不允许乱序执行。后面的两条指令必须利用前几条指令的运行结果，都不可能与其他指令组成编队。,MULTSV V2，S0，V1,LV V3，RY,于是，这组指令的编队如下： LV V1，