第三章第三章 流水线技术流水线技术13.1流水线的基本概念3.2流水线的时空图及性能分析3.3流水线的相关3.4MIPS R4000流水线计算机 FallacySay，multiprocessors are a silver bullet. 2 The switch to multiple processors per chip around 2005 did not come from some breakthrough that dramatically simplified parallel programming or made it easy to build multicore computers. The reason the change occurred is that there was no other option due to the ILP walls and power walls. Multiple processors per chip do not guarantee 3lower power, its certainly possible to design a multicore chip that uses more power. The potential is just that its possible to continue to improve performance by replacing a high-clock-rate, inefficient core with several lower-clock-rate, efficient cores. As technology improves to shrink transistors, this can shrink both capacitance and the supply voltage a bit so that we can get a modest increase in the number of cores per generation. For example, for the last few years, Intel has been adding two cores per generation. 4 In fact, in nowadays, performance is now a programmers burden. The La-Z-Boy programmer era of relying on hardware designers to make their programs go faster without lifting a finger is officially over. If programmers want their programs to go faster with each generation, they must make their programs more parallel. 3.1 流水线的基本概念一指令的执行方式1.一条指令执行的所需过程:1）取指令： 根据PC（指令计数器）从M（存储器）取出指令送到IR（指令寄存器）2）析指： 译出指令的操作性质、寻址方式，取操作数3）执行：对操作数进行处理，主要涉及ALU（算术逻辑运算部件），存结果53.1.1有关基本概念2. 对指令执行的几种方式 1）串行执行当前一条指令的各过程段全部完成后，才从存储器取出下一条指令 6 取指取指 析指析指 执行执行 i条条 i +1条条取指取指析指析指执行执行问题？PCPC译码器译码器ALUALU3) 指令重叠执行：第i条指令的执行与第i+1条的析指及第i+2条的取指重叠。7 i条取译执 i+1条取译执 i+2条取译执注意：重叠解释并不能加快一条指令的实现，但能加快一段程序的解释。8 3. 3. 重叠方式中所需时间表达式及所需时间计算重叠方式中所需时间表达式及所需时间计算 1）条件：设一条指令分为三个过程段，各过程段分别用t取、t析、t执表示。 执行n条指令，分别采用顺序执行、重叠执行。2）分别列出上述两种执行方式所需时间表达式串行执行 n*（t取+t析+t执）重叠执行 t取+ ( t析, t取)max+(n-2) *（t取,t析,t执）max+( t执, t析)max+ t执3) 3) 例子例子 当当n=200n=200，t t取取=3t=3t，t t析析=4t=4t，t t执执=5t=5t时，时，分别计算上述两种执行方式的时间。分别计算上述两种执行方式的时间。串行执行：串行执行： 200200(3+4+5)=2400t(3+4+5)=2400t重叠：重叠： 3+4+(200-2)3+4+(200-2)5+5+5=1007t5+5+5=1007t94重叠方式需要解决的问题问题1：为了实现取指、分析指令、执行指令同时进行，需要有对应的独立部件。问题2：尽量缩短各个功能部件的运行速度，使得大致相等，避免在重叠中相互等待。问题3：主存访问冲突。例如，取指令k+1时需访存，分析指令k时可能也需要取操作数访存。10解决访存冲突，主要有3种解决办法：1)将主存分为两个独立编址的存储器：指令存储器和数据存储器，CPU可分别独立访问。2)低位交叉存取方式：可并行访问不在同一个存储体中的指令或数据。113) 3) 指令预取：在重叠操作中，当前一条指令在执行过程中就需要提前取出后面的指令进行相应处理，这种提前取出后继指令进行相应处理，称为先行（预取）。PowerPC内核E200z3的结构如图所示。Instruction fetch unit 将32或16位指令从存储单元预取到指令缓存单元。每一时钟Instruction fetch unit 将读取64位（即2条32位指令或4条16位指令）指令进入缓存buffer中等待解码单元处理。而这些buffer一共有六个，最多可以保存六条指令。12可能的问题：如果将执行的指令k是跳转指令，则指令k+1无效，需重新取指。二、流水线定义二、流水线定义 指令流水线是由一系列串联的流水段（级）构成，每个流水段完成指令的一个操作步骤。各个流水段之间设置流水线寄存器以暂存上个流水段的处理结果。若某个子过程所需时间较长，还可以继续细分为更小的子过程。比如，浮点加法流水线把流水线技术应用于运算的执行过程，就形成了运算操作流水线，也称为部件级流水线。把浮点加法的全过程分解为求阶差、对阶、尾数相加、规格化4个子过程。 理想情况：速度提高4倍133.1.2 流水线的分类14 流水线可按不同的观点进行分类，一般来说流水线可以分为以下几个类型。1 1、按各过程段用时是否相等分类、按各过程段用时是否相等分类 流水线按各过程段用时是否相等可分为均匀流水线和非均匀流水线两种。1） 均匀流水线指的是各过程段用时全相等的流水线2） 非均匀流水线指的是各过程段用时不全相等的流水线 152 2、按处理的数据类型、按处理的数据类型1） 标量流水线：用于对标量数据进行流水处理。如：IBM 360/91，AmDahl 470V/62） 向量流水线：用于对向量数据进行流水处理。（向量很适合流水处理），如：STAR-100，CYBER-205，CRAY-1. 按处理的数据类型可分为标量流水处理机和向量流水处理机两种。163.3.按流水线的规模按流水线的规模 按流水线的规模可分为操作流水线、指令流水线和宏流水线。1） 操作流水线是把处理机的算术逻辑部件分段，使得各种数据类型的操作能够进行流水，规模最小。 2） 指令流水线则是把执行指令的过程按照流水方式处理。 3） 宏流水线它是指由两个以上的处理机串行地对同一数据流进行处理，每个处理机完成一项任务。 1） 单功能流水线：只能完成一种固定功能的流水线。例如，浮点加法器流水线专门完成浮点加法运算，浮点乘法器流水线专门完成浮点乘法运算。2） 多功能流水线：流水线的各段可以进行不同的连接，以实现不同的功能。例： ASC的多功能流水线174.4.按功能分类按功能分类 按流水线完成的功能是否单一，流水线可分为单功能流水线与多功能流水线两种。18195.5.按工作方式分类按工作方式分类 流水线按工作方式可分为静态流水线和动态流水线两种。1） 静态流水线：在同一时间内，多功能流水线中的各段只能按同一种功能的连接方式工作。 对于静态流水线来说，只有当输入的是一串相同的运算任务时，流水的效率才能得到充分的发挥。2） 动态流水线：在同一时间内，多功能流水线中的各段可以按照不同的方式连接，同时执行多种功能。 优点灵活，能够提高流水线各段的使用率，从而提高处理速度。 缺点控制复杂。20静、动态流水线时空图对比216.6.按连接方式分类按连接方式分类 按照流水线的各个功能段之间是否有反馈信号，可将流水线分为线性流水线和非线性流水线。1） 线性流水线：流水线的各段串行连接，没有反馈回路。数据通过流水线中的各段时，每一个段最多只流过一次。2） 非线性流水线：流水线中除了有串行的连接外，还有反馈回路22237.7.其他分类其他分类 除上述几种外，流水线分类还有下述几种。1）根据控制方式分成顺序流水线和乱序流水线。 2）在线性流水线中，根据控制方式还可以分成同步流水线和异步流水线。 3.1.3 流水线的特点241.流水线处理的最好是连续任务，只有连续不断的任务才能充分发挥流水线的效率。2.流水线依靠多个功能部件并行工作宋缩短程序的执行时间，实际上是把一个大的功能部件分解为多个子过程，如前述将浮点数加法器分解为4个子过程。3.流水线中的每一功能部件后面都要有一个缓冲寄存器，即所谓的锁存器，以便平滑各个功能段延时时间的不一致。4.流水线中各段时间应尽量相等，避免段延时过长引起的相互等待。5.流水线需要有“装入时间”和“排空时间”。3.2 流水线的时空图及性能分析一、时空图时空图从时间和空间两个方面描述了流水线的工作过程。时空图中，横坐标代表时间，纵坐标代表流水线的各个段。 4段指令流水线的时空图253.2.1 流水线的时空图吞吐率：在单位时间内流水线所完成的任务数量或输出结果的数量。263.2.2 流水线的性能分析一、 吞吐率n：任务数Tk：处理完成n个任务所用的时间1、各段时间均相等的流水线各段时间均相等的流水线时空图27流水线完成n个连续任务所需要的总时间为（假设一条k段线性流水线）TkTkk kt t( (n n-1)-1)t t( (k kn n-1)-1)t t 流水线的实际吞吐率28最大吞吐率最大吞吐率与实际吞吐率的关系 29l流水线的实际吞吐率小于最大吞吐率，它除了与每个段的时间有关外，还与流水线的段数k以及输入到流水线中的任务数n有关。l只有当nk 时，才有TPTPmax。 2、各段时间不完全相等的流水线 各段时间不等的流水线及其时空图一条4段的流水线S1，S3，S4各段的时间：tS2的时间：3t （瓶颈段）流水线中这种时间最长的段称为流水线的瓶颈段。 30各段时间不等的流水线的实际吞吐率：（ ti为第i段的时间，共有k个段 ）31流水线的最大吞吐率为3、解决流水线瓶颈问题的常用方法 1）细分瓶颈段： 例如：对前面的4段流水线把瓶颈段S3细分为3个子流水线段：S3a，S3b，S3c32改进后的流水线的吞吐率 ：2)重复设置瓶颈段缺点：控制逻辑比较复杂，所需的硬件增加了。例如：对前面的4段流水线重复设置瓶颈段S3：S3a，S3b，S3c3334重复设置瓶颈段后的时空图重复设置瓶颈段后的时空图35二、 加速比 流水线的加速比（Speedup,S）完成某个任务顺序执行所用时间与流水线执行所用时间之比。 假设：不使用流水线（即顺序执行）所用的时间为Ts，使用流水线后所用的时间为Tk，则该流水线的加速比为1、流水线各段时间相等（都是t）一条k段流水线完成n个连续任务所需要的时间：Tk = (kn-1)t顺序执行n个任务所需要的时间： Ts = nkt流水线的实际加速比为最大加速比362、流水线的各段时间不完全相等时一条k段流水线完成n个连续任务的实际加速比为37三、 效率 流水线效率（Efficiency，E）是指流水线的设备利用率。在时空图上，流水线的效率定义为n个任务占用的时空区与k个功能段总的时空区之比，因此流水线的效率包含时间和空间两个方面的因素。 实际上，n个任务占用的时空区就是顺序执行n个任务的总的时间T0；而用一条k段流水线完成n个任务的总的时空区为K Tk ，其中Tk 是流水线完成n个任务所使用的总时间，则一条k段流水线的效率为：各段时间均相等的流水线时空图3839如果每个流水段时间是如果每个流水段时间是t，且任务是连续的实际效率：，且任务是连续的实际效率：最大效率：最大效率：举例举例计算：计算：S=a0+a1+a2+a3+a4+a5+a6+a7S=a0+a1+a2+a3+a4+a5+a6+a7对相关算式要合理分解算式对相关算式要合理分解算式尽量分解为少相关算式：尽量分解为少相关算式： S0=a0+a1 S4=S0+S1S0=a0+a1 S4=S0+S1 S1=a2+a3 S5=S2+S3 S1=a2+a3 S5=S2+S3 S2=a4+a5 S6=S4+S5 S2=a4+a5 S6=S4+S5 S3=a6+a7 S3=a6+a74041吞吐率：吞吐率：TP=7/(18tTP=7/(18t）效率：效率：E=E=（作用区域面积）（作用区域面积）/ /（完成运算所需时间矩形面积）（完成运算所需时间矩形面积） = =（7*5t7*5t）/ /（18t*518t*5）=7/18=7/18 例：假设是静态多功能流水线计算 A*B=4212345aibiA.BA+B123-5 做加法做加法145 做乘法做乘法解：分解算式解：分解算式 S1=a1.b1S1=a1.b1 s2=a2.b2 s2=a2.b2 s3=a3.b3 s3=a3.b3 s4=a4.b4 s4=a4.b4s5=s1+s2s5=s1+s2s6=s3+s4s6=s3+s4s7=s5+s6s7=s5+s643 44543210 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16时间时间吞吐率7(15)效率(3*4+4*3)/(5*15)3.3 流水线中的相关453.3.1 什么是流水线相关如果要执行算式S=a/b+c，要通过下列四条指令来执行。 LD R , A DIV R , B ADD R , C；要等DIV结果 ST R , S；存结果 第2条指令需要第1条指令的结果才能执行；第3条指令需要第2条指令的结果才能执行。这就出现了指令因等待前面结果，使后面没指令无法继续执行下去的现象，即相关。46流水线中的相关主要分为以下3种类型 1.结构相关 2.数据相关 3.控制相关 473.3.2 3.3.2 流水线中的结构相关（资源相关）流水线中的结构相关（资源相关） 如果某些指令组合在流水线中重叠执行时产生了资源冲突，那么我们称该流水线有结构相关。 由于访问同一个存储器而引起的结构冲突 48对于这种冲突，通常有以下两种解决方法 解决办法(1)： 插入暂停周期，即让流水线在完成前一条指令对数据的存储器访问时，暂停取后一条指令的操作 为消除结构冲突而插入的流水线气泡为消除结构冲突而插入的流水线气泡 MM49解决方法(2)： 设置相互独立的指令存储器和数据存储器或设置相互独立的指令Cache和数据Cache 50513.3.3 3.3.3 流水线中的数据相关流水线中的数据相关如果下面的条件之一成立，则指令j与指令i数据相关：（1）指令j使用指令i产生的结果（2）指令j与指令k数据相关，指令k与指令i数据相关，则指令j与指令i数据相关。 第2个条件指出，如果两条指令之间存在类似上述的传递关系，则它们之间也是相关的。这条相关链甚至可以贯穿整个程序。 例如：下面这一段代码存在数据相关。例如：下面这一段代码存在数据相关。52LoopLoop： L.DL.D F0F0，0 0（R1R1）/ F0/ F0为数组元素为数组元素 ADD.D ADD.D F4F4，F0F0，F2F2/ / 加上加上F2F2中的值中的值 S.D S.D F4F4，0 0（R1R1）/ / 保存结果保存结果 DADDIUDADDIU R1R1，R1R1，8 8/ / 数组指针递减数组指针递减8 8个字节个字节 BNE BNE R1R1，R2R2，LoopLoop/ / 如果如果R1R2R1R2，则分支，则分支 解决数据相关的一般方式：解决数据相关的一般方式：* * 暂停流水线；暂停流水线；* * 使用相关专用数据通路；使用相关专用数据通路；* * 编译优化调度（静态调度）；编译优化调度（静态调度）；* * 动态调度。动态调度。53543.3.4 3.3.4 流水线的控制相关流水线的控制相关 控制相关是指因为程序的执行方向可能被改变而引起的相关。可能改变程序执行方向的指令通常有无条件转移、条件转移、子程序调用、中断、异常等。无条件转移指令在程序中的使用情况一般如下无条件转移指令在程序中的使用情况一般如下 k： k1： JMP L k2： ADD R1, R2, R3 L： SUB 例如，有条件转移指令的程序：55 MOV R1，NUM LOOP： DEC R1 JGE LOOP ；=0转移转移 SUB 从相关的角度看，转移指令或断点指令与后续指令之存在着一种相关，使后续指令不能同时进入流水线执行，意味着前者控制了后者，故称为控制相关或全局相关。 数据相关也称为局部相关。56* 延迟转移技术延迟转移技术 例如：例如： PUSH BX MOV DX ，8 ADD AX ，CX JG L L： MOV 将前面将前面1条指令调到转移指令的后面执行，同时条指令调到转移指令的后面执行，同时也计算转移地址。也计算转移地址。无论成功与否，上面的无论成功与否，上面的1条指令都不需取消。条指令都不需取消。解决控制相关的一般方式：解决控制相关的一般方式：57 SUN 公司的公司的SPARC 使用上述技术，分支指令格使用上述技术，分支指令格式中有一位式中有一位a位。位。 a位用于延迟转移控制，当位用于延迟转移控制，当a0时，时，跟在转移指令下面的指令总是被执行；当跟在转移指令下面的指令总是被执行；当a=1时，只时，只在条件转移指令转移成功时，跟在转移指令下面的指在条件转移指令转移成功时，跟在转移指令下面的指令才被执行。令才被执行。 一般用于单流水线标量处理机中。据统计，一般用于单流水线标量处理机中。据统计，编译编译器调度一条指令成功的概率可达器调度一条指令成功的概率可达90%以上。以上。* 静态转移预测技术-处理器的硬件与软件设计好后，条件转移预测的方向已经确定了，或者预测为转移成功方向，或者预测为转移不成功方向。* 动态转移预测技术：根据近期转移是否成功的历史记录来预测下一次转移的方向。58* 提前形成条件码提前形成条件码 a在流水线中提前形成条件码（硬件）在流水线中提前形成条件码（硬件） 从上一节的分析可以看出，条件转移造成流从上一节的分析可以看出，条件转移造成流水线断流的一个原因是：条件码形成太晚。水线断流的一个原因是：条件码形成太晚。 实际上，在大多数情况下，可以在运算实际实际上，在大多数情况下，可以在运算实际开始以前或者在运算中间就能产生条件码，不必等开始以前或者在运算中间就能产生条件码，不必等到运算完成后。到运算完成后。59例如：例如： MUL AX ，BX JS L即只要比较两个操作数的符号就可形成即只要比较两个操作数的符号就可形成条件码，而不必等到指令完成条件码，而不必等到指令完成（积结果产生）。（积结果产生）。 方法是：方法是：在运算器的入口处设置一个比在运算器的入口处设置一个比较器，提前形成结果的符号较器，提前形成结果的符号，即是否为，即是否为“负负条件码。条件码。 Amdahl 470V/6计算机中采用该方法。计算机中采用该方法。60b将产生条件码的指令提前执行将产生条件码的指令提前执行 在某些情况下，通过编译器，再设置一在某些情况下，通过编译器，再设置一个专门的条件码寄存器，解决循环控制问题：个专门的条件码寄存器，解决循环控制问题：例如，有下面的程序：例如，有下面的程序： MOV R1，NUM LOOP： DEC R1 JGZ LOOP ；=0转移转移 HALT61 首先，编译器发现首先，编译器发现DEC R1 指令，并把它指令，并把它上移，同时用上移，同时用LDEC R1来替代它。来替代它。 其次，用其次，用LJGZ LOOP 代替代替 JGZ LOOP 指令：指令： MOV R1 ，NUMLOOP： LDEC R1 ；测试测试R1，产生的条件码保存在专用，产生的条件码保存在专用 的条件码寄存器的条件码寄存器 CCL 中中 LJGZ LOOP ；根据条件码根据条件码CCL决定是否转移决定是否转移 HALT623.4 MIPS R4000 3.4 MIPS R4000 流水线计算机流水线计算机 MIPS(Microprocessor without Interlocked Piped Stages)4000处理机属于超流水线处理机。 3.4.1 MIPS R4000流水线计算机基本结构和工作原理 R4000处理器是64位机，指令系统是32位长度的典型RISC指令集。63SGI公司生产的超流水线处理器公司生产的超流水线处理器MIPS R4000（RISC）：）： 两个两个Cache：指令：指令Cache 和数据和数据Cache，容量均为，容量均为64KB， 数据通路宽度为数据通路宽度为64位。每个主时钟周期可以位。每个主时钟周期可以 访问访问Cache两次。两次。 整数部件：整数部件：32个个64位通用寄存器，一个位通用寄存器，一个ALU，一个专用，一个专用 乘乘/除法部件。负责除法部件。负责取指令，整数操作译码和取指令，整数操作译码和 执行执行，LOAD和和STORE操作的执行。有相关专用操作的执行。有相关专用 数据通路。数据通路。 浮点部件：浮点部件：16个个64位或位或32个个32位的通用寄存器。位的通用寄存器。 乘法部件、除法部件、加法乘法部件、除法部件、加法/转换转换/求平方根部件，求平方根部件， 三个部件可并行操作三个部件可并行操作一、基本结构一、基本结构6465MIPS R4000的流水线有的流水线有8级，流水线操作如下图：级，流水线操作如下图：指令指令Cache：采用直接映像方式。从：采用直接映像方式。从Cache中读出的区号要与中读出的区号要与 存储器物理地址比较，相等即命中。对命中的存储器物理地址比较，相等即命中。对命中的 非存储器操作指令，结果在非存储器操作指令，结果在EX末尾得到。末尾得到。取指令后一取指令后一半半数据数据cache后一后一半半取指令前一取指令前一半半数据数据cache前一前一半半二、工作原理二、工作原理8个流水段的功能：取指令前一半取指令前一半IF：指令虚拟地址：指令虚拟地址IVA交指令交指令cache和和TLB取指令后一半取指令后一半IS：指令：指令cache送出指令和送出指令和TLB生成物理地址生成物理地址寄存器堆寄存器堆RF：指令译码、相关检查，指令：指令译码、相关检查，指令cache标志检查，标志检查，从寄存器取操作数从寄存器取操作数指令执行指令执行EX：如是：如是RR指令，指令，ALU完成操作；如是完成操作；如是load或或store指令，计算数虚拟地址；如是转移指令，计算转移目指令，计算数虚拟地址；如是转移指令，计算转移目标虚拟地址和检查转移条件标虚拟地址和检查转移条件数据数据cache前一半前一半DF：数据虚拟地址：数据虚拟地址DVA交数据交数据cache和和TLB数据数据cache后一半后一半DS：数据：数据cache输出数据和输出数据和TLB生成物理生成物理地址地址标志检查标志检查TC：为：为load/store指令完成标志检查指令完成标志检查写回写回WB：指令结果写回寄存器堆：指令结果写回寄存器堆666768MIPS R4000正常指令流水工作时序流水线充满时：有流水线充满时：有8条指令同时执行，且一个时钟周期分时发射条指令同时执行，且一个时钟周期分时发射2条指令，或完成两条指令，超流水线方式。条指令，或完成两条指令，超流水线方式。693.4.2 MIPS R40003.4.2 MIPS R4000流水线流水线指令序列在MIPS R4000流水线中重叠执行情况如图所示 ：70从上图可以看出，由于从存储器中读入的数据在DS段的末尾才会有效，所以其载人延迟是2个时钟周期，如下图所示：指令序列时钟周期1 12 23 34 45 56 67 78 89 9LW R1,10LW R1,10（R4R4）IFIFISISRFRFEXEXDFDFDSDSTCTCWBWBADD R2,R1,R3ADD R2,R1,R3IFIFISISRFRFstallstallstallstallEXEXDFDFDSDSSUB R3,R1,R5SUB R3,R1,R5IFIFISISstallstallstallstallRFRFEXEXDFDFOR R4,R1,R6OR R4,R1,R6IFIFstallstallstallstallISISRFRFEXEX71指令序列在R4000流水线中的执行时空图 72对对R4000R4000的流水线来说，定向（数据相关专用通路）是十分重要的。的流水线来说，定向（数据相关专用通路）是十分重要的。 在R4000的流水线中，ALU输入端的定向源有4个：EX/DF、DF/DS、DS/T和TC/WB，如图所示。73R4000流水线的基本分支延迟为3个时钟周期指令序列时钟周期123456789分支指令IFISRFEXDFDSTCWB延迟槽IFISRFEXDFDSTCWB暂停stallstallstallstallstallstallstall暂停stallstallstallstallStallstall分支目标IFISRFEXDF指令序列时钟周期123456789分支指令IFISRFEXDFDSTCWB延迟槽（分支指令+1）IFISRFEXDFDSTCWB分支指令+2IFISRFEXDFDSTC分支指令+3IFISRFEXDFDS74基于单周期延迟分支方法，R4000流水线处理分支指令的时空图