第5章 流水处理机

第一章 计算机系统结构的基本概念第二章 数据表示与指令系统第三章 中断与输入输出系统第四章 存储体系第五章 重叠、流水和向量处理机第六章 并行处理机和相联处理机第七章 多处理机第八章 具有现代特色的计算机1、并行性的含义： 并行性是指问题中具有可同时运算或操作的特性。同时性：两个或多个事件在同一时刻发生；并发性：两个或多个事件在同一时间间隔内发生；引言：系统结构中的并行性发展2、开发并行性的途径：时间重叠：——让多个处理过程在时间上错开，轮流重叠地使用同一套硬件设备的各个部分，使之加快硬件使用的周转来赢得速度。（流水线处理机）资源重复：——通过重复设置硬件资源来提高性能或可靠性。（并行处理机、相联处理机）资源共享：——用软件的方法让多个用户共用同一套资源，通过提高系统资源的利用率来提高系统的效率和性能。（多处理机）3、计算机系统的分类：SISD——单指令流单数据流SingleInstructionStreamSingleDataStream流水线处理机CUPUMMISCSDSCUISCSDSDSDSSIMD——单指令流多数据流SingleInstructionStreamMultipleDataStream并行处理机MISD——多指令流单数据流MultipleInstructionStreamSingleDataStreamISCSDSMIMD——多指令流多数据流MultipleInstructionStreamMultipleDataStream多处理机ISCSDS一、重叠方式1、指令的顺序方式与重叠方式解释指令的顺序解释方式指的是指令与指令之间顺序串行，指令内的各个微操作之间也是顺序串行的。优点：每条指令转入下一条指令的时间关系是确定的，指令间相互的关联关系易于得到控制和处理。缺点：程序解释的速度低，系统内各部件的时间利用率低。指令的重叠解释方式是在相邻的指令之间，让取指令、分析指令、执行指令等操作在时间上错开重叠的进行，而指令内部的微操作仍然是顺序串行的。一次重叠：在任何时间都只有“执行K”与“分析K+1”在时间上重叠。1234n1234n时间空间分析指令执行指令采用“一次重叠”的好处是系统只需要一套指令分析部件和一套指令执行部件，节省了硬件，也简化了指令之间的相关控制。为了使“一次重叠”方式的系统能有较高的重叠效率，应使“分析”和“执行”的时间尽可能调整成一样的。重叠解释不能加快每条指令的解释速度，但在硬件增加不多的情形下，可以加快相邻两条指令以及整段程序的解释，使系统的性能价格比有显著提高。2、重叠方式对计算机组成的要求为解决“分析K+1”、“执行K”在重叠时的访主存冲突，可采用的办法：①、分别设置各自独立编址的数据存储器和指令存储器，让存、取操作数和取指令可同时访存。缺点：增加了总线控制和软件设计的负担。②、让主存用逻辑上统一编址的多分体交叉访问的并行组成方式。缺点：可能发生分体冲突，而使并行度受到限制③、在硬件上，增设有一定容量的指令缓冲器和数据缓冲器，让主存插空将预取的指令存入指令缓冲器，或将要写入的数据暂时存入数据缓冲器中。目前，多采用第二、三种办法的组合。3．“一次重叠”方式的相关控制指令相关：下一条指令的内容取决于上一条指令的执行结果。 条件转移指令与后继指令存在着相关性，会使重叠效率下降。因此，程序中应尽量减少条件转移指令的使用。在需要使用条件转移指令时，可采用“延迟转移”的技术，由编译程序生成目标程序时，将条件转移指令与其前面的指令交换位置，可使重叠效率不致下降。 另外因为指令在程序的执行过程中允许被修改（本条指令要等到之前的指令执行完后才能修改形成好）也可能造成指令相关。解决这种指令相关的根本办法是在机器中规定指令在执行过程中不允许修改。但是，为了满足用户编程的灵活性，需要修改指令时，可以设置类似IBM370的“执行”指令，将指令相关转成操作数相关，统一按操作数相关来处理。数相关：主存空间的数相关：它是在相邻指令之间出现了对主存同一单元要求在先的指令必须先完成写，在后的指令才能读的“先写后读”相关。由于发生主存空间数相关的概率很低，为此可以采取推后后继指令对相关单元的读操作的办法来解决。通用寄存器组的数相关：推后后继指令的分析；设置“相关专用通道”BC运算器通用寄存器组数据总线相关专用通路

二、流水方式1、流水是重叠的引申“一次重叠”是把指令的解释分成两个子过程，让相邻的指令在时间上错开重叠的解释，因此，“一次重叠”对速度的提高最多也只是顺序方式的两倍。流水则是把指令的解释分成更多个（m个）子过程，让相邻的m条指令的解释在时间上错开重叠。1234123412341234时间空间取指令指令译码取操作数指令执行2、

流水线的分类部件级流水——处理机级流水——系统级流水部件机流水是指部件内的各个子部件之间的流水，如分析部件内部的取址、译码、地址形成和取数之间的流水；浮点加/减法运算器内的求阶差、对阶、尾数加/减和尾数规格化之间的流水；Cache存储器内查地址映象表进行地址变换与访物理Cache之间的流水处理机级流水是指构成处理机的各个部件之间的流水，如取指、分析、执行部件间的流水系统级流水是指处理机之间的流水，如宏流水，在任务、作业一级上的流水单功能流水——多功能流水单功能流水是指流水线内各段固定连接，只能完成单一的一种功能多功能流水是指流水线中各个段可以有多种不同的连接，以实现多种不同的功能在多功能流水线的基础上，静态流水——动态流水静态流水是指在流水线内各个段于同一时间里只能按其中的一种功能流水，只有等各个段全部空闲后，才能切换成按另一种功能的连接来流水，把功能负担加到软件调整上。动态流水是指流水线的各个段可以同时为不同的功能服务，把功能负担加到硬件控制上。123AABAABAAB123123123123123AAB输入减阶对阶移位相加规格化相乘累加输出时间空间线性流水——非线性流水线性流水线中各个段之间串行的连接，无反馈也无跳跃，每个任务流经流水线中各个段均只有一次。非线性流水是指如果流水线中除有串行联接的通路外，还有某种反馈回路，使一个任务流经流水线时，需多次经过某个段或越过某些段。1234向量流水机——标量流水机标量流水机则只有流水线，没有向量数据表示，处理向量、数组时需要借用程序的循环和变址向量流水机是向量数据表示和流水线的结合3、流水线处理机的主要性能吞吐率和效率是反映流水机器性能的主要指标吞吐率指的是在单位时间内，流水线机器所能处理的数据、指令或任务的数目效率是指流水线中设备实际使用时间占整个运行时间之比，也称为流水线设备的时间利用率；从时—空图上看，效率实际上就是n个任务占用的时—空区面积和m个段总的时—空区面积之比。12341234123412341234空间时间1234提高吞吐率的两个措施：2123412341234123412341234空间时间1212223341、将瓶颈子过程再细化1342122231234123432141234空间时间12A2B2C342、重复设置多套瓶颈段并使之并联1342A2B2C实际吞吐率：设一m段流水线的各段经过时间均为△t0，则最大吞吐率TPmax是1/△t0；则完成n条指令共需要T=m*△t0+(n–1)*△t0

则实际吞吐率TP=n/(m*△t0+(n–1)*△t0)=Tpmax/(1+(m–1)/n)1234n1234n1234n1234n1234空间时间补充：用加速比表示流水线方式相对于非流水线顺序串行方式速度提高的比值。非流水线顺序串行方式：n*m*△t0

流水线方式：m*△t0+(n–1)*△t0

加速比：Sp=m/1+(m-1)/n结论：如果线性流水线的各段时间相同，仅当n>>m时，即连续流入的任务数n远远大于流水线子过程数m的时候，其加速比才能趋于最大值，为流水线的段数m。假设指令的解释分取指、分析和执行3步，每步的时间相应为t取指t分析t执行，分别计算下列情况下，执行完100条指令所需时间的一般关系式：①顺序方式；②仅执行k与取址k+1重叠；③取址k+2分析k+1和执行k流水；当t取指=t分析=2，t执行=1当t取指=t执行=5，t分析=2取分析E取分析E取分析E取分析Et取指+100t分析+99max｛t取指，t执行｝+t执行取分析E取分析E取分析E取分析E……取分析E取分析Et取指+max｛t取指，t分析｝+98max｛t取指，t分析，t执行｝+max｛t分析，t执行｝+t执行设有两个向量A和B，各有4个元素，要在如下图所示的静态双功能流水线上，计算向量点积A·B（a1*b1+a2*b2+a3*b3+a4*b4）。其中，1→2→3→5组成加法流水线，1→4→5组成乘法流水线。又设每个流水线所经过的时间均为△t0

，而且流水线的输出结果可以直接返回到输入或暂存于相应的缓冲寄存器中，其延迟时间和功能切换所需的时间都可以忽略不计。请求出流水线从开始流入到结果流出这段时间的实际吞吐率TP和效率η。123541234+++1234++++++1234+++空间时间12345实际吞吐率：7/15加速比：24△t0/15△t0=1.6效率：24△t0/75△t0=0.32空间时间123412345++++12345++++12345++++12345++++【｛(A1+A2)+(A3+A4)｝+(A9+A10)】+｛(A5+A6)+(A7+A8)｝空间时间1234123456789123456789123456789A*(B+C*(D+E*F))+G*H=A*B+A*C*D+A*C*E*F+G*HA*CE*F1*D1*2A*BG*H5+34+6吞吐率：3/8；效率：3/8；空间时间1234123456789123456778899123456789A*(B+C*(D+E*F))+G*H=A*B+A*C*D+A*C*E*F+G*HA*CE*F1*D1*2A*BG*H5+34+6吞吐率：3/8；效率：3/8；空间时间12341234576891234566778899123457689A*(B+C*(D+E*F))+G*H=A*B+A*C*D+A*C*E*F+G*HA*CE*F1*D1*2A*BG*H5+34+6吞吐率：3/8；效率：3/8；A1*B1+A2*B2+A3*B3+A4*B4+A5*B5+A6*B6+A7*B7+A8*B8空间时间+++++++12345678空间时间⑴、（8+7）*5=75；+++++++12345678乘法加法乘法加法⑵、（2+7）*5=45；乘法加法1456714567145671456714567181818181812空间时间空间时间+++++++++++++++++++++++++++++++++++12345678123456781234567812345678123456781+2;3+4;5+6;12+7;34+8;56+127;348+125674、流水线的任务调度——非线性流水线预约表：二维的预约表其实就是一个任务在流水时的时空图；延迟禁止表：将流水线中所有各段对一个任务流过时会争用同一段的节拍间隔数汇集在一起，就构成一个延迟禁止表；初始冲突向量：由延迟禁止表可转换得到初始冲突向量；冲突向量中第I位的状态用以表示与当时相隔I拍给流水线送入后继任务是否会发生功能段的使用冲突；如果不会发生冲突，令该位为0，表示允许送入，否则，让该位为1，表示禁止送入。如果每个任务通过流水线需要n拍，则冲突向量取n–1位。由初始冲突向量可以得到状态转移图。预约表打√最多的行是流水线的性能瓶颈，其√的个数实际上限定了流水线可达到的最短平均间隔拍数。t0t1t2t3t4t5t6t7t8s1**s2**s3***s4**s5**123456123456121234345656123456123142536456t1t2t3t4t5t6t7t8t9s1**s2**s3***s4**s5**100011011010111110001111调度方案平均延迟2，53.52，74.5556，55.5666，76.5775，23.5257657576由初始状态出发，构成一种间隔拍数呈周期性重复的方案1000110100100011100011010000010010001101000000011000110100000010单功能流水线状态图禁止向量：8，1，3，4，5、流水机器的相关——全局性相关和局部性相关全局性相关：转移指令与其后继指令之间的相关发生全局性相关时，不仅不能同时解释，还会使指令缓冲器所预取的指令全部作废，重新花较长的时间再去访问主存取出指令；它对流水线性能的下降有着至关重要的影响；局部性相关：指令相关、主存数相关、通用寄存器组的数相关、基（变）址值相关等；这些相关都只影响到使相关的指令在某些功能段上停留等待一段时间，不会影响到使流水线需要等待，去重新访问主存取指令。这样，它们对流水线的吞吐率和效率的下降的影响是局部的，所以称为局部性相关。⑴、流水线全局性相关的处理①猜测法——猜选I+1和p中的一个分支继续流入流水线；为了猜错时使猜测流入流水线的那些指令都作废其部分解释，恢复成解释之前的原始现场，我们使用后援寄存器—让流入流水线的指令，其所有可能被破坏的原始内容都保存在后援寄存器中，一旦猜错了，只需很少的时间，用后援寄存器的内容来恢复就可以了。为了猜错后能尽快转入p分支流水，可设置转移目标指令缓冲器，以便在猜测流水的同时就预取p、p+1等指令，并将它们存入转移目标指令缓冲器中。这样，一旦猜错时，就不必再去访问存储器，只需直接从转移目标指令缓冲器中取出指令即可，以减少此时流水线的空等时间。②加快条件转移时条件码的生成包括在单条指令内部条件码的提前形成和在程序段内所用分支条件码的提前形成。提前知道程序将流向哪个分支，就可以减少猜错时，流水线效率的过分下降。也可以采用“延迟转移”技术。依靠编译技术，将转移指令与其前面不相关的一条或多条指令对换一下位置，使成功转移总是延迟到这一条或多条指令之后进行，就可以使转移造成的流水线性能的损失降低到最小。③加快对短循环程序的处理如果发现是一个短循环程序，就可将整个循环程序中的各条指令一次性全部装入指令缓冲器中，并暂时停止指令的预取操作，以减少不必要的访存次数。同时，让流水线的循环出口恒猜选循环分支。空间时间123412345ABC12345ABC12345ABc12345ABC⑵、流水线局部性相关的处理由于局部性相关都是因为出现“先写后读”引起的，因此，与重叠方式类似，可以采用推后对相关单元的读操作和设置相关专用通路的办法来解决。为了使流水线发生局部相关的指令在某个功能段处于停止等待时，后续不相关的指令可以越过它继续向前流动，以保证流水线仍有较高的吞吐率和效率，可以采用异步流动控制方式——流入流水线的指令顺序可以与流入流水线之前的指令顺序不同流水线采用异步流动方式后，会产生“写—写”相关和“先读后写”相关。“写—写”相关：指令之间对同一寄存器或存储单元，要求在先的指令应先写好，在后的指令才能写入的关联。“先读后写”相关：指令之间要求对同一寄存器或存储单元在先的指令应先读出，在后的指令才能写入的关联。流水机器处理局部性相关的一种典型的基本结构是IBM360/91。空间时间读写123345123345123345123345空间时间1234351234351234351234356、流水机器的中断处理中断和转移一样，都会使流水线断流。由于发生中断的概率远比发生条件转移的概率低，所以流水机器处理中断的关键不在于如何缩短因中断引起流水线断流的时间，而是看如何保存好中断时的断点及中断现场，以便在中断返回后，能使程序从断点处恢复正常工作。“不精确断点”法——不管第I条指令在哪一段发出中断请求，让未流入流水线的指令不再流入，而已进入流水线的指令继续流完，然后再转去执行中断处理程序，这种不精确的断点对程序的设计和排错很不利。IBM360/91“精确断点”法——不论指令I是在流水线中的哪一段响应中断，给中断处理程序的现场全都是对应I的，I之后流入流水线的指令的原有现场都能恢复。“精确断点”法需要设置大量的后援寄存器，以保证流水线内各条指令的原有现场都能保存和恢复。Amdahl470/V6D=A*(B+C)三、向量的流水处理和向量处理机横向（水平）处理方式：逐个求结果向量的各个元素；纵向（垂直）处理方式：将两个向量先全部运算完，得到一个中间结果向量后，再用此中间结果向量与其他向量运算。7+N+7+N+8+N=22+3N访存取A送入V3寄存器组V0(B)+V1(C)送入V2

V2*V3送入V4

访存取A送入V3寄存器组V0(B)+V1(C)送入V2

V2*V3送入V4

7+N+8+N=15+2N访存取A送入V3寄存器组V0(B)+V1(C)送入V2

V2*V3送入V4

8+8+N=16+N在向量处理机上，每条向量指令的内部都是流水的；邻近多条向量指令之间如果既无流水线功能部件的使用冲突，也无向量寄存器组Vi的使用冲突，则这些向量指令都可以同时并行流水。如果相邻的多条向量指令之间无功能部件使用冲突，只有向量寄存器组Vi的先写后读相关，可以通过链接，实现指令之间大部分时间并行流水；链接：将前面指令的结果向量直接链入后续指令所用的流水线，使多个流水线功能部件链接，构成一条大的流水线，从而使处理机有更高的性能。如果后续指令的两个源向量寄存器组恰好是先行两条指令的结果寄存器组，只要前面这两条指令能设法调整到同一时钟周期得到一对分量时，可以实现链接。如果两条向量指令的向量长度不等，则不能链接。四、指令级高度并行的超级处理机结构特性标量超标量超流水超长指令字指令发射每周期1条每周期m条每周期1条*每周期1条是否与标量机兼容/是是否是否要软件支持/是否是（编译系统）时钟周期是否与标量相同/是否（小于标量）是CPI>1<1>1*<1流水线结构一条多条一条一条1、超标量(Superscalar)处理机：采用设置m条指令流水线同时并行，来实现度为m的。它是靠编译时，由编译程序来优化编排指令的执行顺序，将可并行的指令搭配成组，硬件不调整所执行指令的顺序，以利于实现。2、超流水线(Superpipelining)处理机：采用多相的高频时钟。一台度为m的超流水线处理机的时钟只是基本机器周期的1/m。3、超长指令字(VLIW)处理机：将水平型微码和超标量处理相结合。在编译时，将多个能并行执行的不相关或无关的操作组合在一起，形成一条有多个操作码字段的超长指令字。运行时，直接控制机器中多个相互独立的功能部件并行操作，来实现同时执行多条指令。123456789101112123456789101112123456789101112取指分析执行常规标量流水处理机481237112610159481237112610159481237112610159取指分析执行超标量处理机（m=4）4812371126101594812371126101511481237112610159取指分析执行5.75超流水线处理机（m=4）123123123123123123取指分析执行超长指令字处理机（m=4）复习指导：第五章重叠、流水和向量处理机概述：本章着重讲述在计算机组成设计中，如何通过采用重叠和流水等控制方式来提高解释机器语言程序的速度。在此基础上，讲述向量的流水处理方式、向量流水机的结构。结合CRAY-1向量流水处理机，介绍通过让向量指令之间并行或链接执行来进一步提高流水机的性能。最后简要介绍在指令级上发展高度并行的超标量处理机、超长指令字处理机和超流水线处理机的工作原理。基本要求：1、领会重叠方式的工作原理——采用重叠工作方式时，对计算机在组成设计上的要求；