计算机系统结构-第四章(流水处理和ILP) 264页

流水处理和指令级并行流水线基本概念相关性分析技术多指令发射技术\n流水线基本概念引入流水线工作原理流水线的分类流水线的性能分析非线性流水线的调度技术本章内容\n引入本章内容>>流水线基本概念标量处理机具有标量数据表示和标量指令系统的处理机称为标量处理机。提高指令执行速度的主要途径提高处理机的工作主频；采用更好的算法和设计更好的功能部件；采用指令级并行（ILP）技术（本章介绍）。\n流水线工作原理本章内容>>流水线基本概念基本思想表示方法主要特点\n流水线基本思想本章内容>>流水线基本概念>>流水线工作原理基本思想：以指令流水线为例进行介绍：取指分析执行通过将一个重复的过程分解为若干子过程，每个子过程可以与其它子过程同时进行。△t△t△t5之1\n流水线基本思想本章内容>>流水线基本概念>>流水线工作原理顺序执行取指k分析k执行k取指k+1分析k+1执行k+1……优点：控制简单，节省设备。缺点：处理器执行指令的速度慢功能部件的利用率很低n条指令的执行时间为：5之2\nn条指令的执行时间为：流水线基本思想本章内容>>流水线基本概念>>流水线工作原理一次重叠取指k分析k执行k取指k+1分析k+1执行k+1取指k+2分析k+2执行k+2优点：执行指令的速度较快功能部件的利用率较高缺点：控制较复杂，需增加设备5之3\nn条指令的执行时间为：流水线基本思想本章内容>>流水线基本概念>>流水线工作原理二次重叠优点：执行指令的速度更快功能部件的利用率更高缺点：控制更复杂，需增加设备取指k+2分析k+2执行k+2取指k+1分析k+1执行k+1取指k分析k执行k5之4\n流水线基本思想本章内容>>流水线基本概念>>流水线工作原理流水线利用并行性实现：空间并行性设置多个独立的操作部件。时间并行性分时使用同一个部件的不同部分。5之5\n流水线表示方法本章内容>>流水线基本概念>>流水线工作原理流水线的表示方法通常有三种：连接图时空图预约表\n连接图本章内容>>流水线基本概念>>流水线工作原理>>流水线表示方法分析器分析k+1流水锁存器执行部件执行k流水锁存器输入输出t1t2Stage1latch输入输出t1t2Stage2latchStage3latcht32之1\n连接图功能段流水线的每一个阶段称为流水步、流水步骤、流水段、流水线阶段、流水功能段、流水级、流水节拍等。流水寄存器在每一个流水段的末尾或开头必须设置一个寄存器，称为流水寄存器、流水锁存器、流水闸门寄存器等。加入流水寄存器，会增加指令的执行时间。在一般流水线中不画出流水寄存器。本章内容>>流水线基本概念>>流水线工作原理>>流水线表示方法2之2\n时空图1时间空间0t1t2t3t4t52345123451234512345t6t7t8求阶差对阶尾数加规格化求阶差对阶尾数加规格化△t△t△t△t本章内容>>流水线基本概念>>流水线工作原理>>流水线表示方法\n流水线主要特点本章内容>>流水线基本概念>>流水线工作原理只有连续提供同类任务才能发挥流水线效率尽量减少因条件分支造成的“断流”，可通过编译技术提供连续的相同类型操作。每个流水线段都要设置一个流水寄存器用于保存本流水线段的执行结果，会使流水线的执行时间加长，是流水线中需要增加的主要硬件。各流水段的时间应尽量相等流水线处理机的基本时钟周期等于时间最长的流水段的时间长度。流水线需要有“装入时间”和“排空时间”\n流水线的分类本章内容>>流水线基本概念从不同的角度，按照不同的观点，可以将流水线分成多种不同的种类。分类一分类二分类三分类四其它\n分类一单功能流水线只能完成一种固定功能的流水线。例如：Cray-1计算机中有12条；YH-1计算机有18条；Pentium有一条5段定点和一条8段浮点流水线；PentiumⅢ有两条定点和一条浮点指令流水线。多功能流水线流水线的各段通过不同连接实现不同功能。例如：Texas公司的ASC机，8段流水线，能够实现：定点加减法、定点乘法、浮点加法、浮点乘法、逻辑运算、移位操作、数据转换、向量运算等。本章内容>>流水线基本概念>>流水线的分类按流水线具有功能的多少来分，可分为：2之1\nTexas公司ASC机上的8段多功能流水线2之2\n分类二本章内容>>流水线基本概念>>流水线的分类在多功能流水线中，按照在同一时间内是否能够连接成多种方式，同时执行多种功能，可以将多功能流水线分为：静态流水线动态流水线\n静态流水线本章内容>>流水线基本概念>>流水线的分类>>分类二同一段时间内，各个功能段只能按照一种方式连接，实现一种固定的功能。1时间空间023…n123…n123…n123…n123…n123…n1234…123…12……1输入求阶差对阶尾数加规格化尾数乘累加输出浮点加法定点乘法\n动态流水线在同一段时间内，各段可以按照不同的方式连接，同时执行多种功能。1时间空间023…n123…n123…n123…n123…n123…n输入求阶差对阶尾数加规格化尾数乘累加输出………………123546123541234123…………浮点加法定点乘法本章内容>>流水线基本概念>>流水线的分类>>分类二\n分类三本章内容>>流水线基本概念>>流水线的分类按照流水线的各个功能段之间是否有反馈信号，可以将流水线分为：线性流水线是指流水线内各功能段串行连接，没有反馈回路，各个功能段只经过一次。一条线性流水线通常只完成一种固定的功能。例子：指令流水线、浮点加法器流水线等。非线性流水线是指流水线内除有串行连接的通路外，还有某种反馈回路，使得一次流水过程中，某些段会多次通过。非线性流水线经常用于递归调用，或构成多功能流水线等。3之1\n非线性流水线S1输入S2S3输出前馈回路反馈回路一种简单的非线性流水线对应的两种预约表××S3×S2×S14321S3×××S2×S143215×3之2本章内容>>流水线基本概念>>流水线的分类\n提示线性流水线能够用连接图唯一表示，非线性流水线必须用连接图和预约表共同表示。一条非线性流水线可以对应有很多张预约表，同样，一张预约表实际上仅表示了一条非线性流水线的一种工作方式线性流水线实际上也有预约表，只不过它的预约表是固定的（一张对角线为×的正方形的表格）3之3本章内容>>流水线基本概念>>流水线的分类\n分类四按照流水线使用的不同级别，可以将流水线分为：部件级流水线处理机级流水线系统级流水线本章内容>>流水线基本概念>>流水线的分类\n部件级流水线本章内容>>流水线基本概念>>流水线的分类>>分类四是指构成部件内的各子部件之间的流水。例如：浮点加法器流水线。求阶差输入输出t1对阶尾数加规格化t2t3t4\n处理机级流水线又称为指令流水线，例如：在采用先行控制器的处理机中，各功能部件之间的流水线。先行指令缓冲栈输入先行控制方式中的指令流水线先行指令分析器先行读数栈先行操作栈取指译码取操作数指令执行部件后行写数栈输出执行写结果本章内容>>流水线基本概念>>流水线的分类>>分类四\n系统级流水线也称为宏流水线，是处理机之间的流水线。例如：每个处理机对同一个数据流的不同部分分别进行处理。P1输入任务1MM…P2任务2MP3任务3输出本章内容>>流水线基本概念>>流水线的分类>>分类四\n其它按照不同的数据表示方式分：标量流水线对标量数据进行处理。向量流水线对向量数据进行处理。按照流水线中信息流动顺序的控制方式分：顺序流水线流水线输出端的任务流出顺序与输入端的任务流入顺序完全相同。异步流水线流水线输出端的任务流出顺序与输入端的任务流入顺序可以不一样。本章内容>>流水线基本概念>>流水线的分类\n流水线的性能分析本章内容>>流水线基本概念吞吐率加速比效率流水线最佳段数的选择性能分析举例\n吞吐率定义单位时间内能流出的任务数或能流出的结果数。公式n：任务数；Tm：处理完成n个任务所用的时间。本章内容>>流水线基本概念>>流水线的性能分析8之1\n案例1：理想情况(1)假设在流水线各段的执行时间均相等，输入到流水线中的任务是连续的理想情况下，一条单功能m段线性流水线能够在m+n-1个时钟周期内完成n个任务。本章内容>>流水线基本概念>>流水线的性能分析8之21时间空间S123……n-1nS2…Sm123……n-1n…………………123……n-1nmt(n-1)tnt(m-1)tTm\n案例1：理想情况(2)本章内容>>流水线基本概念>>流水线的性能分析8之3实际吞吐率最大吞吐率两者之间的关系\n案例2：实际情况假设在流水线各段的执行时间不相等，输入到流水线中的任务是连续的理想情况下。实际吞吐率最大吞吐率本章内容>>流水线基本概念>>流水线的性能分析8之4\n问题及解决本章内容>>流水线基本概念>>流水线的性能分析8之5问题流水线的TP和TPmax主要由流水线中执行时间最长的那个功能段来决定，这个功能段就成了整个流水线的“瓶颈”。解决将流水线中的“瓶颈”再细分；通过重复设置多套瓶颈功能段，让多个瓶颈功能段并行工作。\n举例-瓶颈本章内容>>流水线基本概念>>流水线的性能分析8之6S1t1=tS2t2=3tS3t3=tS4t4=t输出1时间空间S1S2S3S4ti(n-1)t2Tm23…n123…n123…n123…n输入\n举例-瓶颈解决本章内容>>流水线基本概念>>流水线的性能分析8之7S1输入输出tS2-1tS2-2tS2-3tS3tS4tS2(3t)S1输入输出t1=tS2-3S2-2S2-1S3S4t3=tt4=tt2=3t瓶颈细分多套瓶颈\n举例-多套瓶颈时空图本章内容>>流水线基本概念>>流水线的性能分析8之81时间空间23nS1S2-1456…14…n-2n-1n-225…n-136…n123n456…n-2n-1123n456…n-2n-1S2-2S2-3S3S4\n加速比本章内容>>流水线基本概念>>流水线的性能分析定义完成同样一批任务，不使用流水线所用的时间与使用流水线所用的时间之比。公式T0：顺序执行所用的时间；Tm：使用流水线所用的时间。3之1\n案例1：理想情况假设在流水线各段的执行时间都相等，输入到流水线中的任务是连续的理想情况下。实际加速比最大加速比本章内容>>流水线基本概念>>流水线的性能分析3之2\n案例2：实际情况假设在流水线各段的执行时间不相等，输入到流水线中的任务是连续的理想情况下。实际加速比本章内容>>流水线基本概念>>流水线的性能分析3之3\n效率本章内容>>流水线基本概念>>流水线的性能分析定义是指流水线的设备利用率。在时空图上，流水线的效率定义为n个任务占用的时空区与m个功能段总的时空区之比。公式1时间空间S1…nS2…Sm1…n………1…n4之1\n案例1：理想情况假设在流水线各段的执行时间都相等，输入到流水线中的任务是连续的理想情况下。实际效率最大效率本章内容>>流水线基本概念>>流水线的性能分析4之2\n案例2：实际情况(1)假设在流水线各段的执行时间不相等，输入到流水线中的任务是连续的理想情况下。实际效率（功能段等权值）本章内容>>流水线基本概念>>流水线的性能分析4之3\n案例2：实际情况(2)实际效率（功能段权值不同）其中，i为i段的权值，i>流水线基本概念>>流水线的性能分析4之4\n流水线最佳段数的选择本章内容>>流水线基本概念>>流水线的性能分析问题提出功能段数量的增加能提高流水线的吞吐率和加速比，但使流水线价格增加（锁存器数量的增加），一条指令执行的总时间增加（锁存器的总延迟时间增加）。所以从性价比角度出发流水线存在着最佳段数。2之1\n流水线最佳段数的选择问题解决对自变量m求导，求PCR的最大值，得到最佳段数为：本章内容>>流水线基本概念>>流水线的性能分析t：任务总时间d：锁存器时间m：功能段数a：所有功能段价格b：锁存器价格2之2\n性能分析举例本章内容>>流水线基本概念>>流水线的性能分析问：用一条4段浮点加法器流水线求8个浮点数的和，要求所用时间最短，求流水线的吞吐率、加速比和效率。Z＝A＋B＋C＋D＋E＋F＋G＋H答：由于存在着数据相关，如果直接交与流水线处理，效果与顺序执行完全一样，因此先作一个简单变换，然后交与流水线处理。Z=[(A+B)+(C+D)]+[(E+F)+(G+H)]3之1\n性能分析举例本章内容>>流水线基本概念>>流水线的性能分析3之21时间空间23求阶差4567123456712345671234567对阶尾数加规格化加数ACEGA+BE+FBDFHC+DG+HA+B+C+DE+F+G+H结果A+BC+DE+FG+HA+B+C+DE+F+G+HZ被加数\n性能分析举例流水线的吞吐率为：流水线的加速比为：流水线的效率为：本章内容>>流水线基本概念>>流水线的性能分析3之3\n非线性流水线的调度技术本章内容>>流水线基本概念调度目的非线性流水线的冲突无冲突调度方法优化调度方法\n调度目的本章内容>>流水线基本概念>>非线性流水线的调度技术非线性流水线的调度目的是要找出一个最小的循环周期，按照这周期向流水线输入新任务，流水线的各个功能段都不会发生冲突，而且流水线的吞吐率和效率最高。\n非线性流水线的冲突本章内容>>流水线基本概念>>非线性流水线的调度技术启动距离向一条非线性流水线的输入端顺序输入两个任务之间的时间间隔称为启动距离/等待时间。冲突几个任务同时争用同一个流水线功能段的情况称为非线性流水线的冲突。禁止启动距离引起非线性流水线冲突的启动距离称为禁止启动距离。5之1\n举例-非线性流水线本章内容>>流水线基本概念>>非线性流水线的调度技术5之2输出S1S2S3S4输入×S4××S3××S2×××S17654321时间流水段\n举例-流水线冲突本章内容>>流水线基本概念>>非线性流水线的调度技术5之3\n举例-流水线不冲突本章内容>>流水线基本概念>>非线性流水线的调度技术5之4不发生冲突的启动距离一般是一个循环数列，称为非线性流水线的启动循环，记作（1，7）。\n举例-流水线不冲突启动距离5也可以认为是一个循环数列，称为非线性流水线的恒定循环，记作（5）。本章内容>>流水线基本概念>>非线性流水线的调度技术5之5\n无冲突调度方法-例子本章内容>>流水线基本概念>>非线性流水线的调度技术×S4××S3××S2××S17654321时间流水段12之1S1S2S3S4输入输出\n无冲突调度方法-步骤本章内容>>流水线基本概念>>非线性流水线的调度技术由预约表得到禁止向量由禁止向量得到冲突向量由冲突向量构造调度流水线的状态图在状态图中找出可用启动距离，并计算平均启动距离找出平均启动距离最小的启动循环或恒定循环12之2\n步骤一本章内容>>流水线基本概念>>非线性流水线的调度技术>>无冲突调度方法由预约表得到禁止向量定义：将一条非线性流水线的所有各功能段禁止启动距离组合在一起形成的数列。计算：将预约表中的每一行中任意两个“×”之间的距离都计算出来，去掉重复的，由这些数形成禁止向量。例子：上例所示非线性流水线的禁止向量为（2，4，6）。12之3\n步骤二本章内容>>流水线基本概念>>非线性流水线的调度技术>>无冲突调度方法由禁止向量得到冲突向量概念：冲突向量用一个m位的二进制数表示（其中m是禁止向量中的最大值），一般格式为C=（CmCm-1…Ci…C2C1），若i在禁止向量中，则Ci=1，否则Ci=0，其中Cm一定为1。例子：上例所示非线性流水线的冲突向量为C=（101010）。12之4\n步骤三（1）本章内容>>流水线基本概念>>非线性流水线的调度技术>>无冲突调度方法由冲突向量构造调度流水线的状态图将冲突向量C作为初始冲突向量送入一个m位逻辑右移移位器，移位m次；若移出的是“0”，用移位器中的值与初始冲突向量作“按位或”运算，得到一个新的冲突向量；若移出的是“1”，不作任何处理。将中间形成的每一个新的冲突向量同样处理；画出状态图。在初始冲突向量和所有的新形成的冲突向量之间用带箭头的线连接，表示各种状态之间的转换关系。12之5\n步骤三（2）本章内容>>流水线基本概念>>非线性流水线的调度技术>>无冲突调度方法12之6\n步骤四（1）本章内容>>流水线基本概念>>非线性流水线的调度技术>>无冲突调度方法在状态图中找出可用启动距离，并计算平均启动距离在状态图中从初始状态出发，能构成一种间隔拍数呈周期性重复的方案就是可用启动距离。即：找出所有的简单循环（是指在状态图中各种冲突向量只经过一次的启动循环）。12之7\n步骤四（2）本章内容>>流水线基本概念>>非线性流水线的调度技术>>无冲突调度方法简单循环平均启动距离1，743，755，763，5，755，3，753，54557712之8\n步骤五（1）本章内容>>流水线基本概念>>非线性流水线的调度技术>>无冲突调度方法找出平均启动距离最小的启动循环或恒定循环启动循环（1，7）和（3，5）恒定循环（5）12之9\n步骤五（2）本章内容>>流水线基本概念>>非线性流水线的调度技术>>无冲突调度方法12之10××S3×S2×S143215×S467××1234567891011121314151617181920…S1X1X2X1X2X3X4X3X4X5X6S2X1X2X1X2X3X4X3X4X5X6S3X1X2X1X2X3X4X3X4X5X6S4X1X2X3X4X5最小启动循环（1，7）的流水线工作状态启动周期重复启动周期\n步骤五（3）本章内容>>流水线基本概念>>非线性流水线的调度技术>>无冲突调度方法12之11××S3×S2×S143215×S467××1234567891011121314151617181920…S1X1X2X1X3X2X4X3X5X4X6S2X1X2X1X2X3X4X3X4X5S3X1X1X2X2X3X3X4X4X5S4X1X2X3X4X5最小启动循环（3，5）的流水线工作状态启动周期重复启动周期\n步骤五（4）本章内容>>流水线基本概念>>非线性流水线的调度技术>>无冲突调度方法12之12××S3×S2×S143215×S467××1234567891011121314151617181920…S1X1X2X1X3X2X4X3S2X1X1X2X2X3X3X4S3X1X1X2X2X3X3X4X4S4X1X2X3X4最小恒定循环（5）的流水线工作状态启动周期重复启动周期\n优化调度方法本章内容>>流水线基本概念>>非线性流水线的调度技术问题当采用最小启动循环启动非线性流水线时，没有充分发挥非线性流水线的效率，因为流水线中的许多流水段还有空闲，即使最繁忙的流水段也有空闲。解决采用非线性流水线的优化调度方法（预留算法），可以使流水线的工作效率最高。7之1\n理论基础本章内容>>流水线基本概念>>非线性流水线的调度技术L.E.Shar于1972年提出流水线最小平均启动距离的限制范围并于1992年进行了证明：最小平均启动距离的下限是预约表中任意一行里“×”的最多个数。最小平均启动距离小于等于状态图中任意一个简单循环的平均启动距离。最小平均启动距离的上限是冲突向量中1的个数再加上1。7之2\n预留算法本章内容>>流水线基本概念>>非线性流水线的调度技术确定流水线的最小启动距离最小启动距离等于预约表中任意一行中“×”的最大个数。确定最小启动循环为简化流水线的控制逻辑，一般采用恒定循环作为最小启动循环。插入延迟进行预留对预约表中任意一行中任意两个“×”之间的距离是最小启动距离整数倍的通过插入延迟进行预留。7之3\n举例-优化前（前例）本章内容>>流水线基本概念>>非线性流水线的调度技术×S4××S3××S2××S17654321时间流水段S1S2S3S4输入输出7之4\n举例-优化后本章内容>>流水线基本概念>>非线性流水线的调度技术S1S2S3S4输入输出D1时间12345678功能段S1××S2××S3××S4×延迟D1×7之5\n举例-优化后从状态图中很容易可以看出：流水线的最小启动循环是（2）。本章内容>>流水线基本概念>>非线性流水线的调度技术7之6\n举例-优化后在非线性流水线中，“×”最多的流水段一定是“瓶颈”流水段。实现最优调度的目标是使“瓶颈”流水段处于忙碌状态，没有空闲周期。本章内容>>流水线基本概念>>非线性流水线的调度技术7之7\n相关性分析技术基本概念资源相关数据相关控制相关综合应用循环处理本章内容\n基本概念本章内容>>相关性分析技术概念相关（CorrelationorDependency）也称为冲突（Hazard）是指邻近指令之间存在着某种关系，影响指令的重叠执行或流水线的正常运行。内容有三种类型的相关：资源相关：争用部件。数据相关：改变操作数的读写顺序，使得顺序执行与流水执行时结果不同。控制相关：分支、转子程序、中断。2之1\n示例环境说明本章内容>>相关性分析技术在介绍相关性分析技术时，我们以一个典型的RISC指令流水线（MIPS64指令集）为例进行介绍：MIPS基本流水线MIPS扩展流水线2之2\nMIPS基本流水线本章内容>>相关性分析技术>>示例环境说明RISC指令集采用MIPS64（MIPS的64位版本）的整数子集：ALU指令（5个时钟周期）、load（5个时钟周期）/store（4个时钟周期）指令和分支指令（2个时钟周期）。RISC指令的实现每一条RISC指令的执行至多需要5个时钟周期：取指令周期（IF）、指令译码/读寄存器周期（ID）、执行/有效地址周期（EX）、访问存储器周期（MEM）和写回周期（WB）。13之1\n取指令周期（IF）本章内容>>相关性分析技术>>示例环境说明IR←Mem[PC]NPC←PC+4解释：根据PC指示的地址从存储器中取指令并装入指令寄存器（IR），同时PC加4以获取下一条指令的地址。IR中保存下一个时钟周期需要的指令，NPC中保存下一条指令的PC。13之2\n图示IF本章内容>>相关性分析技术>>示例环境说明13之3\n指令译码/读寄存器周期（ID）本章内容>>相关性分析技术>>示例环境说明A←Regs[rs]B←Regs[rt]Imm←IR的立即数字段进行符号扩展ALUOutput←NPC+(Imm<<2)Cond←(A==0)if(cond)PC←ALUOutput解释：分析指令并访问寄存器堆以读寄存器，并结束分支指令（为简单只设置一条：BEQZ）的操作。13之4\n图示ID本章内容>>相关性分析技术>>示例环境说明13之5\n执行/有效地址周期（EX）访问存储器ALUOutput←A+Imm寄存器-寄存器ALUALUOutput←AfuncB寄存器-立即数ALUALUOutput←AopImm解释：Load/Store指令在本周期形成有效地址。ALU指令完成相应的ALU操作。本章内容>>相关性分析技术>>示例环境说明13之6\n图示EX本章内容>>相关性分析技术>>示例环境说明13之7\n访问存储器周期（MEM）本章内容>>相关性分析技术>>示例环境说明LMD←Mem[ALUOutput]orMem[ALUOutput]←B解释：Load指令从存储器中读出数据并装入LMD（装入存储器数据）寄存器，Store指令将寄存器B中的数据写入存储器。13之8\n图示MEM本章内容>>相关性分析技术>>示例环境说明13之9\n写回周期（WB）Load指令Regs[rt]←LMD寄存器-寄存器ALURegs[rd]←ALUOutput寄存器-立即数ALURegs[rt]←ALUOutput解释：将结果写入寄存器堆。寄存器的写入端口在两个目标中选择一个（rtorrd），具体选择哪一个要由操作码决定。本章内容>>相关性分析技术>>示例环境说明13之10\n图示WB本章内容>>相关性分析技术>>示例环境说明13之11\n时空图本章内容>>相关性分析技术>>示例环境说明指令时钟123456789iIFIDEXMEMWBi+1IFIDEXMEMWBi+2IFIDEXMEMWBi+3IFIDEXMEMWBi+4IFIDEXMEMWB13之12\nMIPS基本流水线的数据通路13之13IM：指令存储器DM：数据存储器CC：时钟周期写操作（前半周期进行）读操作（后半周期进行）\nMIPS基本流水线的实现9之9\nMIPS扩展流水线本章内容>>相关性分析技术>>示例环境说明3之1在MIPS基本流水线中引入浮点操作功能。主定点操作部件负责load/store、定点ALU操作和分支操作（功能同MIPS基本流水线）。浮点/定点乘法部件负责浮点/定点乘法，采用流水设计。浮点加法部件负责处理浮点加、减法及定点数/浮点数之间的转换，采用流水设计。浮点/定点除法部件负责浮点/定点除法，不采用流水设计。\n连接图本章内容>>相关性分析技术>>示例环境说明3之2\n一组独立的浮点操作流水线时序蓝色斜体的流水段需要数据，红色的流水段已经得到结果。本章内容>>相关性分析技术>>示例环境说明3之3MUL.DIFIDM1M2M3M4M5M6M7MEMWBADD.DIFIDA1A2A3A4MEMWBL.DIFIDEXMEMWBS.DIFIDEXMEMWB\n资源相关本章内容>>相关性分析技术因为资源冲突而导致流水线断流。例1:指重叠指令或流水线中的指令同时要用同一个功能部件，实际上是一种冲突。非线性流水线的调度就是为了尽量避免资源使用上的冲突。例2:后面介绍的RISC指令流水线当指令和数据共享同一个存储器时，也会出现资源冲突（见后图）。4之1\nMIPS基本流水线当指令和数据共享同一个存储器时会出现资源冲突4之2IF段ID段EX段MEM段WB段\n资源相关本章内容>>相关性分析技术原因分析主要有：部分功能部件没有充分流水资源没有充分重复设置解决方法可以采用推后处理法来解决：暂停相关指令的执行，直到所需的功能单元能够使用为止。4之3\n例子本章内容>>相关性分析技术指令时钟123456789loadIFIDEXMEMWBi+1IFIDEXMEMWBi+2IFIDEXMEMWBi+3stallIFIDEXMEMWBi+4IFIDEXMEM4之4时空图的另一种画法\n数据相关本章内容>>相关性分析技术数据相关类型数据相关解决动态调度技术\n数据相关类型本章内容>>相关性分析技术>>数据相关“先写后读”相关“先读后写”相关“写写”相关\n“先写后读”相关（RAW）本章内容>>相关性分析技术>>数据相关>>数据相关类型概念有两条相邻指令i和j，i在j之前执行，指令i将结果写入某个存储单元，而指令j从相同存储单元中读取该数据。如果指令j想在指令i写之前去读数据，则会发生“先写后读”相关，也称为写读相关、数据相关、RAW相关、WR相关等。2之1\n“先写后读”相关（RAW）本章内容>>相关性分析技术>>数据相关>>数据相关类型例子i：DADDR1,R2,R3;(R2)＋(R3)→(R1)j：DSUBR4,R1,R5;(R1)－(R5)→(R4)2之2IF段ID段EX段MEM段WB段流水寄存器\n“先读后写”相关（WAR）本章内容>>相关性分析技术>>数据相关>>数据相关类型概念有两条相邻指令i和j，i在j之前执行，指令i从某个存储单元中读取数据，而指令j将结果写入相同存储单元。如果指令j想在指令i读之前去写数据，则会发生“先读后写”相关，也称为读写相关、反相关、WAR相关、RW相关等。2之1\n“先读后写”相关（WAR）本章内容>>相关性分析技术>>数据相关>>数据相关类型例子i：DSUBR4,R1,R5;(R1)－(R5)→(R4)j：DADDR1,R2,R3;(R2)＋(R3)→(R1)2之2\n“写写”相关（WAW）本章内容>>相关性分析技术>>数据相关>>数据相关类型概念有两条相邻指令i和j，i在j之前执行，指令i将结果写入某个存储单元，而指令j也将结果写入相同存储单元。如果指令j想在指令i写之前去写该数据，则会发生“写写”相关，也称为写写相关、输出相关、WAW相关、WW相关等。3之1\n“写写”相关（WAW）本章内容>>相关性分析技术>>数据相关>>数据相关类型3之2例子i：DSUBR1,R4,R5;(R4)－(R5)→(R1)j：DADDR1,R2,R3;(R2)＋(R3)→(R1)\n“先写后读”相关在流水线顺序执行和乱序执行时都可能发生，“先读后写”相关和“写写”相关只有在流水线乱序执行时才可能发生，而“读读”相关无需处理。提示本章内容>>相关性分析技术>>数据相关>>数据相关类型3之3\n数据相关解决本章内容>>相关性分析技术>>数据相关“先读后写”相关“写写”相关设置专用路径推后处理“先写后读”相关寄存器换名\n设置专用路径思想将结果直接送到需要它的功能部件，即：一个结果能够从一个部件的输出直接送到另一个部件的输入。程序段DADDR1,R2,R3DSUBR4,R1,R5ANDR6,R1,R7ORR8,R1,R9XORR10,R1,R11本章内容>>相关性分析技术>>数据相关>>数据相关解决3之1\n“先写后读”数据相关3之2\n通过设置专用路径解决“先写后读”数据相关3之3\n推后处理思想对于采用设置专用路径无法解决的数据相关只有推后处理相关指令，直至数据就绪。程序段LDR1,0(R2)DSUBR4,R1,R5ANDR6,R1,R7ORR8,R1,R9本章内容>>相关性分析技术>>数据相关>>数据相关解决3之1\n通过设置专用路径解决数据相关（失败）3之2失败\n通过推后处理解决数据相关3之3指令时钟123456789LDR1,0(R2)IFIDEXMEMWBDSUBR4,R1,R5IFIDEXMEMWBANDR6,R1,R7IFIDEXMEMWBORR8,R1,R9IFIDEXMEMWB指令时钟123456789LDR1,0(R2)IFIDEXMEMWBDSUBR4,R1,R5IFIDstallEXMEMWBANDR6,R1,R7IFstallIDEXMEMWBORR8,R1,R9stallIFIDEXMEMWB推后处理前的数据相关\n寄存器换名WAR相关WAW相关本章内容>>相关性分析技术>>数据相关>>数据相关解决2之1ACACBBB’ijijACACBB’Bijij\n寄存器换名举例换名前DIV.DF0,F2,F4ADD.DF6,F0,F8S.DF6,0(R1)SUB.DF8,F10,F14MUL.DF6,F10,F8换名后DIV.DF0,F2,F4ADD.DS,F0,F8S.DS,0(R1)SUB.DT,F10,F14MUL.DF6,F10,T本章内容>>相关性分析技术>>数据相关>>数据相关解决2之2\n动态调度技术本章内容>>相关性分析技术>>数据相关引入思想方法CDC计分牌法Tomasulo算法\n引入本章内容>>相关性分析技术>>数据相关>>动态调度技术DIV.DF0,F2,F4ADD.DF10,F0,F8SUB.DF12,F8,F14时间1234…2627282930DIV.DIFIDDIVMEMWBADD.DIFID暂停…暂停EXMEMWBSUB.DIFID暂停…暂停EXMEMWB2之1\n问题在MIPS扩展流水线中，指令按序发射、按序执行和按序完成，RAW相关使ADD.D及后续指令在流水线中被暂停，即使后续指令与DIV.D、ADD.D指令没有冲突，这限制流水线的性能。解决如果指令按序发射、乱序执行和乱序完成，则可以减少暂停所带来的影响。引入本章内容>>相关性分析技术>>数据相关>>动态调度技术2之2\n思想本章内容>>相关性分析技术>>数据相关>>动态调度技术记录和检测指令相关，当指令的操作数就绪时就执行该指令（即：指令按序发射、乱序执行和乱序完成）以降低RAW相关的影响，采用寄存器换名技术来避免WAR、WAW相关的影响。\nTomasulo算法本章内容>>相关性分析技术>>数据相关>>动态调度技术概述实现举例\n概述本章内容>>相关性分析技术>>数据相关>>动态调度技术>>Tomasulo算法Tomasulo算法是由R.M.Tomasulo于1967年首先提出，并最早在大型机IBM360/91处理机的浮点处理部件中使用。Tomasulo算法也称为公共数据总线（CDB）法、令牌法等，它采用乱序方式来提高流水线的性能，并通过分散控制的办法处理数据相关。\n基于Tomasulo算法的MIPS浮点部件的基本结构6之1FPaddersAdd1Add2Add3FPmultipliersMult1Mult2FromMemFPRegistersReservationStationsCommonDataBus(CDB)ToMemFPOpQueueLoadBuffersStoreBuffersLoad1Load2Load3Load4Load5Load6\n保留站Op操作类型。Vj和Vk存放两个源操作数的值。Qj和Qk存放产生相应源操作数的保留站。对每个源操作数，V字段或Q字段中只有一个是有效的。A用于保存load/store操作的存储器地址信息。最初指令中的立即数存放于此，在地址计算后有效地址也存放于此。Busy指示该保留站及相关的功能部件是否正在使用。本章内容>>相关性分析技术>>数据相关>>动态调度技术>>Tomasulo算法寄存器换名是通过保留站实现的，保留站的数据结构为：6之2\n存储设备读数/写数缓冲器每个缓冲器也都是保留站，字段同前。浮点寄存器堆每个寄存器都需设置Qi字段，用于保存保留站号。在该保留站中进行的操作，其结果将存入该寄存器。如果Qi为空，则表示当前不会有运算结果要存到该寄存器。本章内容>>相关性分析技术>>数据相关>>动态调度技术>>Tomasulo算法6之3\n指令执行过程本章内容>>相关性分析技术>>数据相关>>动态调度技术>>Tomasulo算法发射从浮点操作队列中取得一条指令。如果相应保留站空闲（即：没有结构冲突），则可以发射指令和发送数据。寄存器换名工作在本阶段进行。执行对操作数进行相应的操作。当指令所需要的源操作数都准备好，就可以执行该运算；否则监视CDB等待源操作数。写回结果当计算结果出来之后，送至CDB，进而写回到寄存器中，或被其它保留站读取。6之4\n指令格式浮点运算指令load和store指令MUL.DF4，F0，F2rsrdrtL.DF2，45（R3）rsrtimmS.DF3，40（R4）rsrtimm本章内容>>相关性分析技术>>数据相关>>动态调度技术>>Tomasulo算法6之5jkjjkAA\n指令执行的具体过程6之6\n举例程序L.DF6,34(R2)L.DF2,45(R3)MUL.DF0,F2,F4SUB.DF8,F2,F6DIV.DF10,F0,F6ADD.DF6,F8,F2假设各指令在“发射”和“写回结果”所花时钟周期数都为1，在“执行”阶段所花时钟周期数分别为：L.D为2，ADD.D和SUB.D为2，MUL.D为10，DIV.D为40。本章内容>>相关性分析技术>>数据相关>>动态调度技术>>Tomasulo算法21之1\n指令指令状态发射执行写回结果L.DF6,34(R2)L.DF2,45(R3)MUL.DF0,F2,F4SUB.DF8,F6,F2DIV.DF10,F0,F6ADD.DF6,F8,F2站名保留站BusyOpVjVkQjQkALoad1YLoadRegs[R2]34Load2Add1Add2Add3Mult1Mult2寄存器状态字段F0F2F4F6F8F10F12…F30QiLoad1CLOCK：121之2\n指令指令状态发射执行写回结果L.DF6,34(R2)1L.DF2,45(R3)MUL.DF0,F2,F4SUB.DF8,F6,F2DIV.DF10,F0,F6ADD.DF6,F8,F2站名保留站BusyOpVjVkQjQkALoad1YLoadRegs[R2]34Load2YLoadRegs[R3]45Add1Add2Add3Mult1Mult2寄存器状态字段F0F2F4F6F8F10F12…F30QiLoad2Load1CLOCK：221之3\n指令指令状态发射执行写回结果L.DF6,34(R2)2L.DF2,45(R3)1MUL.DF0,F2,F4SUB.DF8,F6,F2DIV.DF10,F0,F6ADD.DF6,F8,F2站名保留站BusyOpVjVkQjQkALoad1YLoad34+Regs[R2]Load2YLoadRegs[R3]45Add1Add2Add3Mult1YMULRegs[F4]Load2Mult2寄存器状态字段F0F2F4F6F8F10F12…F30QiMult1Load2Load1CLOCK：321之4\n指令指令状态发射执行写回结果L.DF6,34(R2)L.DF2,45(R3)2MUL.DF0,F2,F4SUB.DF8,F6,F2DIV.DF10,F0,F6ADD.DF6,F8,F2站名保留站BusyOpVjVkQjQkALoad1NLoad2YLoad45+Regs[R3]Add1YSUBMem[34+Regs[R2]]Load2Add2Add3Mult1YMULRegs[F4]Load2Mult2寄存器状态字段F0F2F4F6F8F10F12…F30QiMult1Load2Mem[34+Regs[R2]]Add1CLOCK：421之5\n指令指令状态发射执行写回结果L.DF6,34(R2)L.DF2,45(R3)MUL.DF0,F2,F4SUB.DF8,F6,F2DIV.DF10,F0,F6ADD.DF6,F8,F2站名保留站BusyOpVjVkQjQkALoad1NLoad2NAdd1YSUBMem[34+Regs[R2]]Mem[45+Regs[R3]]Add2Add3Mult1YMULMem[45+Regs[R3]]Regs[F4]Mult2YDIVMem[34+Regs[R2]]Mult1寄存器状态字段F0F2F4F6F8F10F12…F30QiMult1Mem[45+Regs[R3]]Mem[34+Regs[R2]]Add1Mult2CLOCK：521之6\n指令指令状态发射执行写回结果L.DF6,34(R2)L.DF2,45(R3)MUL.DF0,F2,F41SUB.DF8,F6,F21DIV.DF10,F0,F6ADD.DF6,F8,F2站名保留站BusyOpVjVkQjQkALoad1NLoad2NAdd1YSUBMem[34+Regs[R2]]Mem[45+Regs[R3]]Add2YADDMem[45+Regs[R3]]Add1Add3Mult1YMULMem[45+Regs[R3]]Regs[F4]Mult2YDIVMem[34+Regs[R2]]Mult1寄存器状态字段F0F2F4F6F8F10F12…F30QiMult1Mem[45+Regs[R3]]Add2Add1Mult2CLOCK：621之7\n指令指令状态发射执行写回结果L.DF6,34(R2)L.DF2,45(R3)MUL.DF0,F2,F42SUB.DF8,F6,F22DIV.DF10,F0,F6ADD.DF6,F8,F2站名保留站BusyOpVjVkQjQkALoad1NLoad2NAdd1YSUBMem[34+Regs[R2]]Mem[45+Regs[R3]]Add2YADDMem[45+Regs[R3]]Add1Add3Mult1YMULMem[45+Regs[R3]]Regs[F4]Mult2YDIVMem[34+Regs[R2]]Mult1寄存器状态字段F0F2F4F6F8F10F12…F30QiMult1Mem[45+Regs[R3]]Add2Add1Mult2CLOCK：721之8\n指令指令状态发射执行写回结果L.DF6,34(R2)L.DF2,45(R3)MUL.DF0,F2,F43SUB.DF8,F6,F2DIV.DF10,F0,F6ADD.DF6,F8,F2站名保留站BusyOpVjVkQjQkALoad1NLoad2NAdd1NAdd2YADDMem[34+Regs[R2]]-Mem[45+Regs[R3]Mem[45+Regs[R3]]Add3Mult1YMULMem[45+Regs[R3]]Regs[F4]Mult2YDIVMem[34+Regs[R2]]Mult1寄存器状态字段F0F2F4F6F8F10F12…F30QiMult1Mem[45+Regs[R3]]Add2Mem[34+Regs[R2]]-Mem[45+Regs[R3]]Mult2CLOCK：821之9\n指令指令状态发射执行写回结果L.DF6,34(R2)L.DF2,45(R3)MUL.DF0,F2,F44SUB.DF8,F6,F2DIV.DF10,F0,F6ADD.DF6,F8,F21站名保留站BusyOpVjVkQjQkALoad1NLoad2NAdd1NAdd2YADDMem[34+Regs[R2]]-Mem[45+Regs[R3]Mem[45+Regs[R3]]Add3Mult1YMULMem[45+Regs[R3]]Regs[F4]Mult2YDIVMem[34+Regs[R2]]Mult1寄存器状态字段F0F2F4F6F8F10F12…F30QiMult1Mem[45+Regs[R3]]Add2Mem[34+Regs[R2]]-Mem[45+Regs[R3]]Mult2CLOCK：921之10\n指令指令状态发射执行写回结果L.DF6,34(R2)L.DF2,45(R3)MUL.DF0,F2,F45SUB.DF8,F6,F2DIV.DF10,F0,F6ADD.DF6,F8,F22站名保留站BusyOpVjVkQjQkALoad1NLoad2NAdd1NAdd2YADDMem[34+Regs[R2]]-Mem[45+Regs[R3]Mem[45+Regs[R3]]Add3Mult1YMULMem[45+Regs[R3]]Regs[F4]Mult2YDIVMem[34+Regs[R2]]Mult1寄存器状态字段F0F2F4F6F8F10F12…F30QiMult1Mem[45+Regs[R3]]Add2Mem[34+Regs[R2]]-Mem[45+Regs[R3]]Mult2CLOCK：1021之11\n指令指令状态发射执行写回结果L.DF6,34(R2)L.DF2,45(R3)MUL.DF0,F2,F46SUB.DF8,F6,F2DIV.DF10,F0,F6ADD.DF6,F8,F2站名保留站BusyOpVjVkQjQkALoad1NLoad2NAdd1NAdd2NAdd3Mult1YMULMem[45+Regs[R3]]Regs[F4]Mult2YDIVMem[34+Regs[R2]]Mult1寄存器状态字段F0F2F4F6F8F10F12…F30QiMult1Mem[45+Regs[R3]]…Mem[34+Regs[R2]]-Mem[45+Regs[R3]]Mult2CLOCK：1121之12\n指令指令状态发射执行写回结果L.DF6,34(R2)L.DF2,45(R3)MUL.DF0,F2,F47SUB.DF8,F6,F2DIV.DF10,F0,F6ADD.DF6,F8,F2站名保留站BusyOpVjVkQjQkALoad1NLoad2NAdd1NAdd2NAdd3Mult1YMULMem[45+Regs[R3]]Regs[F4]Mult2YDIVMem[34+Regs[R2]]Mult1寄存器状态字段F0F2F4F6F8F10F12…F30QiMult1………Mult2CLOCK：1221之13\n指令指令状态发射执行写回结果L.DF6,34(R2)L.DF2,45(R3)MUL.DF0,F2,F48SUB.DF8,F6,F2DIV.DF10,F0,F6ADD.DF6,F8,F2站名保留站BusyOpVjVkQjQkALoad1NLoad2NAdd1NAdd2NAdd3Mult1YMULMem[45+Regs[R3]]Regs[F4]Mult2YDIVMem[34+Regs[R2]]Mult1寄存器状态字段F0F2F4F6F8F10F12…F30QiMult1………Mult2CLOCK：1321之14\n指令指令状态发射执行写回结果L.DF6,34(R2)L.DF2,45(R3)MUL.DF0,F2,F49SUB.DF8,F6,F2DIV.DF10,F0,F6ADD.DF6,F8,F2站名保留站BusyOpVjVkQjQkALoad1NLoad2NAdd1NAdd2NAdd3Mult1YMULMem[45+Regs[R3]]Regs[F4]Mult2YDIVMem[34+Regs[R2]]Mult1寄存器状态字段F0F2F4F6F8F10F12…F30QiMult1………Mult2CLOCK：1421之15\n指令指令状态发射执行写回结果L.DF6,34(R2)L.DF2,45(R3)MUL.DF0,F2,F410SUB.DF8,F6,F2DIV.DF10,F0,F6ADD.DF6,F8,F2站名保留站BusyOpVjVkQjQkALoad1NLoad2NAdd1NAdd2NAdd3Mult1YMULMem[45+Regs[R3]]Regs[F4]Mult2YDIVMem[34+Regs[R2]]Mult1寄存器状态字段F0F2F4F6F8F10F12…F30QiMult1………Mult2CLOCK：1521之16\n指令指令状态发射执行写回结果L.DF6,34(R2)L.DF2,45(R3)MUL.DF0,F2,F4SUB.DF8,F6,F2DIV.DF10,F0,F6ADD.DF6,F8,F2站名保留站BusyOpVjVkQjQkALoad1NLoad2NAdd1NAdd2NAdd3Mult1NMult2YDIVMem[45+Regs[R3]*Regs[F4]Mem[34+Regs[R2]]寄存器状态字段F0F2F4F6F8F10F12…F30QiMem[45+Regs[R3]*Regs[F4]………Mult2CLOCK：1621之17\n指令指令状态发射执行写回结果L.DF6,34(R2)L.DF2,45(R3)MUL.DF0,F2,F4SUB.DF8,F6,F2DIV.DF10,F0,F61ADD.DF6,F8,F2站名保留站BusyOpVjVkQjQkALoad1NLoad2NAdd1NAdd2NAdd3Mult1NMult2YDIVMem[45+Regs[R3]*Regs[F4]Mem[34+Regs[R2]]寄存器状态字段F0F2F4F6F8F10F12…F30QiMem[45+Regs[R3]*Regs[F4]………Mult2CLOCK：1721之18\n……21之19\n指令指令状态发射执行写回结果L.DF6,34(R2)L.DF2,45(R3)MUL.DF0,F2,F4SUB.DF8,F6,F2DIV.DF10,F0,F640ADD.DF6,F8,F2站名保留站BusyOpVjVkQjQkALoad1NLoad2NAdd1NAdd2NAdd3Mult1NMult2YDIVMem[45+Regs[R3]*Regs[F4]Mem[34+Regs[R2]]寄存器状态字段F0F2F4F6F8F10F12…F30QiMem[45+Regs[R3]*Regs[F4]………Mult2CLOCK：5621之20\n指令指令状态发射执行写回结果L.DF6,34(R2)L.DF2,45(R3)MUL.DF0,F2,F4SUB.DF8,F6,F2DIV.DF10,F0,F6ADD.DF6,F8,F2站名保留站BusyOpVjVkQjQkALoad1NLoad2NAdd1NAdd2NAdd3Mult1NMult2N寄存器状态字段F0F2F4F6F8F10F12…F30Qi………Mem[45+Regs[R3]*Regs[F4]/Mem[34+Regs[R2]]CLOCK：5721之21\n控制相关本章内容>>相关性分析技术基本概念条件转移的影响条件转移的处理中断的处理\n基本概念本章内容>>相关性分析技术>>控制相关因程序的执行方向可能被改变而引起的相关，也称为全局相关（而将前面介绍的其他相关称为局部相关）。可能改变程序执行方向的指令主要包括：无条件转移、条件转移、子程序调用、中断等。2之1\n举例本章内容>>相关性分析技术>>控制相关指令时钟123456789分支指令IFIDEXMEMWB分支后继IFIFIDEXMEMWB分支后继+1IFIDEXMEMWB分支后继+2IFIDEXMEMWB2之2\n条件转移的影响本章内容>>相关性分析技术>>控制相关对于一条有k个流水段的流水线，在最坏情况下每一次条件转移（条件分支）指令将造成k-1个时钟的“停顿”；假设条件转移指令在一般程序中所占的比例为p，转移成功的概率为q。则n条指令的总执行时间是：3之1\n有条件转移影响的流水线吞吐率有条件转移影响的最大流水线吞吐率条件转移的影响本章内容>>相关性分析技术>>控制相关3之2\n流水线吞吐率下降的比例例子据统计：在一些典型程序中p=20%、q=60%，对于有8个流水段的流水线，最大吞吐率会下降46%；对于有10个流水段的流水线，最大吞吐率会下降52%。条件转移指令对流水线的影响很大，必须采取措施降低影响。条件转移的影响本章内容>>相关性分析技术>>控制相关3之3\n条件转移的处理本章内容>>相关性分析技术>>控制相关条件出来前提前形成条件码预测条件出来后停顿\n提前形成条件码本章内容>>相关性分析技术>>控制相关>>条件转移的处理可在运算开始或中间产生条件码在绝大多数情况下，只要在运算部件的入口处设置一个比较器，通过比较两个操作数的符号或者阶码就能够提前形成结果的正负号、是否为0、是否溢出等条件码。如果在一个时钟周期之内产生条件码，则正好可以提供给下一条条件转移指令使用，这样流水线就不会“断流”。3之1\n提前形成条件码本章内容>>相关性分析技术>>控制相关>>条件转移的处理加快循环内条件码形成编译前：LOADR1,NUM;循环次数初值装入R1LOOP：……;循环体开始……DECR1;循环次数减“1”BNELOOP;测试循环是否则结束HALT;程序结束NUM：n3之2\n提前形成条件码本章内容>>相关性分析技术>>控制相关>>条件转移的处理加快循环内条件码形成编译后：LOADR1,NUM;循环次数装入R1中LOOP:LDECR1;一条专用的循环次数减1指令……;循环体开始……LBNELOOP;一条专用的测试循环是否结束的指令HALT;程序结束NUM:n;循环次数【提示】指令LDEC和LBNE使用专用的条件码寄存器。3之3\n预测本章内容>>相关性分析技术>>控制相关>>条件转移的处理思想预测的后续处理分支现场的保护及恢复预防预测不中时的加速处理提高预测命中率静态预测动态预测\n思想本章内容>>相关性分析技术>>控制相关>>条件转移的处理>>预测选取发生概率较高的分支为预测方向，运行但不写回结果。若猜对，继续执行；否则,作废预测方向的执行，返回实际转移处。时间ti+1i+2…i+k-3i+k-2输出输入i-1ipp+1…p+k-4p+k-3输出形成条件码的指令条件转移指令形成转移条件转移不成功转移成功\n分支现场的保护及恢复本章内容>>相关性分析技术>>控制相关>>条件转移的处理>>预测问题当分支方向预测错误，不仅要浪费时间，更严重的是可能造成程序执行结果发生错误，因此要能恢复分支点处的原有现场。解决只进行指令译码和准备好运算所需的操作数，在转移条件没有形成之前不执行运算；一直执行到运算完成，但不送回运算结果；把可能被破坏的原始状态都用后援寄存器保存起来（此方法实现效率较高）。\n预防预测不中时的加速处理本章内容>>相关性分析技术>>控制相关>>条件转移的处理>>预测可以设置两个指令目标缓冲栈。当指令分析器分析到条件转移指令时，一个指令目标缓冲栈按照转移成功方向预取指令，另一个指令目标缓冲栈按照转移不成功方向预取指令。不管转移是否成功都可以继续分析指令目标缓冲栈中的指令。\n静态预测本章内容>>相关性分析技术>>控制相关>>条件转移的处理>>预测在程序实际执行过程中，转移猜测的方向不能改变。猜测不成功方向，由程序员和编译程序把发生概率高的分支安排在猜测方向。i←n循环体i←i-1i>0YNi←n循环体i←i-1i<=0YN①编译前②编译后\n动态预测本章内容>>相关性分析技术>>控制相关>>条件转移的处理>>预测转移预测缓冲器相关转移预测器自适应预测器转移目标缓冲器\n转移预测缓冲器本章内容>>相关性分析技术>>控制相关>>条件转移的处理>>预测>>动态预测思想实现1bit转移预测缓冲器2bit转移预测缓冲器性能\n思想本章内容>>相关性分析技术>>控制相关>>条件转移的处理>>预测>>动态预测>>转移预测缓冲器转移预测缓冲器也称为转移历史表（BHT：BranchHistoryTable），预测只依赖本条件转移指令的历史信息（局部信息）。具体实现为：设置一个较小的、按照条件转移指令的低位地址部分进行访问的存储器（每个表项对应一条条件转移指令）；在执行条件转移指令时，将转移成功或不成功的信息记录在该存储器中相应表项中；当下次再执行到该条件转移指令时，转移预测逻辑就根据记录的信息来预测是否转移。2之1\n示意图本章内容>>相关性分析技术>>控制相关>>条件转移的处理>>预测>>动态预测>>转移预测缓冲器2之2\n1bit转移预测缓冲器—方法本章内容>>相关性分析技术>>控制相关>>条件转移的处理>>预测>>动态预测>>转移预测缓冲器在转移预测缓冲器中每个表项中只设置1bit，用以说明该条件转移指令是否曾经成功转移过。该方法的有限状态机（状态转换图）为：2之1\n1bit转移预测缓冲器—缺点本章内容>>相关性分析技术>>控制相关>>条件转移的处理>>预测>>动态预测>>转移预测缓冲器2之2在1bit转移预测缓冲器中，即使条件转移指令大多数情况下总是转移成功（例如：循环），但也有可能错误地预测两次。例如：考察一个9次成功转移、1次不成功转移的循环程序。为克服1bit转移预测缓冲器的缺点，引入了2bit转移预测缓冲器。\n2bit转移预测缓冲器—方法本章内容>>相关性分析技术>>控制相关>>条件转移的处理>>预测>>动态预测>>转移预测缓冲器在转移预测缓冲器中每个表项中设置2bit，用以记录条件转移指令最近2次转移是否成功的信息。当预测不成功达到2次时才改变其预测方向。可以通过一个2bit饱和计数器来实现：当转移成功计数器加1，当转移不成功计数器减1。当计数器的值大于等于2（22-1），则预测转移成功，否则预测转移不成功。3之1\n2bit转移预测缓冲器—有限状态机本章内容>>相关性分析技术>>控制相关>>条件转移的处理>>预测>>动态预测>>转移预测缓冲器3之2\nnbit转移预测缓冲器—推而广之在转移预测缓冲器中每个表项中设置nbit预测位，用以记录最近多次转移是否成功的信息。这可以通过设置一个nbit饱和计数器来实现：当转移成功计数器加1，当转移不成功计数器减1。当计数器的值大于等于2n-1，则预测转移成功，否则预测转移不成功。在绝大多数系统中，往往采用2bit转移预测缓冲器，而不采用nbit转移预测缓冲器。本章内容>>相关性分析技术>>控制相关>>条件转移的处理>>预测>>动态预测>>转移预测缓冲器3之3\n转移预测缓冲器的性能\n相关转移预测器本章内容>>相关性分析技术>>控制相关>>条件转移的处理>>预测>>动态预测思想实现（1，1）预测器（m，n）预测器性能\n思想本章内容>>相关性分析技术>>控制相关>>条件转移的处理>>预测>>动态预测>>相关预测器依靠已经发生过的其他条件转移指令的历史信息（全局信息）来进行预测，可以提高预测的精确度。C语言程序if(d==0)d=1;if(d==1){…}MIPS代码BNEZR1,L1;分支b1(d!=0)DADDIUR1,R0,#1;d==0,sod=1L1:DADDIUR3,R1,#-1BNEZR3,L2;分支b2(d!=1)…L2:若b1不被执行，则b2也不会被执行\n（1，1）预测器—方法本章内容>>相关性分析技术>>控制相关>>条件转移的处理>>预测>>动态预测>>相关预测器根据前一次其它条件转移指令的行为去从一对1bit预测器中进行选择。即：每个条件转移指令需设置一对1bit预测器，其中1bit用于前一次其它条件转移指令未成功转移时的预测，另1bit用于前一次其它条件转移指令成功转移时的预测。预测位1bit/1bit未成功转移分支成功转移分支NT/NTNTNTNT/TNTTT/NTTNTT/TTT2之1\n（1，1）预测器—举例本章内容>>相关性分析技术>>控制相关>>条件转移的处理>>预测>>动态预测>>相关预测器2之2d=?对b1的预测b1的实际动作对b1的新预测对b2的预测b2的实际动作对b2的新预测1bit转移预测器（全部失败）2NTTTNTTT0TNTNTTNTNT2NTTTNTTT0TNTNTTNTNT(1,1)预测器（仅1次失败）2NT/NTTT/NTNT/NTTNT/T0T/NTNTT/NTNT/TNTNT/T2T/NTTT/NTNT/TTNT/T0T/NTNTT/NTNT/TNTNT/T\n（m，n）预测器—方法本章内容>>相关性分析技术>>控制相关>>条件转移的处理>>预测>>动态预测>>相关预测器根据前m次其它条件转移指令的行为去从2m个nbit预测器中进行选择。即：每个条件转移指令需设置2m个nbit预测器，分别用于前m次其它条件转移指令的2m个行为的预测。具体硬件实现为：最近m个条件转移指令的全局历史记录可以记录在一个mbit移位寄存器中，每1bit记录着该条件转移指令是否转移。对相关转移预测缓冲器的访问可由条件转移指令的低位拼接上mbit全局历史记录而得到。2之1\n（2，2）预测器—举例本章内容>>相关性分析技术>>控制相关>>条件转移的处理>>预测>>动态预测>>相关预测器2之2Branchaddress(low4bits)2-bitsperbranchlocalpredictorsPrediction2-bitglobalbranchhistory(01=nottakenthentaken)Numofbitsinan(m,n)predictor：2m×n×Numberofpredictionentriesselectedbythebranchaddress\n相关转移预测缓冲器的性能提示：2bit转移预测缓冲器也可称为（0，2）预测器。（0，2）预测器和（2，2）预测器最受欢迎。\n自适应预测器—思想本章内容>>相关性分析技术>>控制相关>>条件转移的处理>>预测>>动态预测转移预测缓冲器和相关转移预测器都是转移历史表（BHT），前者使用局部信息，而后者使用全局信息。本方法通过设置两个预测器，一个基于局部信息，另一个基于全局信息，并使用一个选择器来组合它们，希望为合适的条件转移指令选择合适的预测器。3之1\n自适应预测器—实现本章内容>>相关性分析技术>>控制相关>>条件转移的处理>>预测>>动态预测×／×：前一个×表示预测器1预测的情况；后一个×表示预测器2预测的情况；其中0表示预测错误，1表示预测正确。3之2\n自适应预测器—比较本章内容>>相关性分析技术>>控制相关>>条件转移的处理>>预测>>动态预测3之3\n转移目标缓冲器—思想本章内容>>相关性分析技术>>控制相关>>条件转移的处理>>预测>>动态预测转移目标缓冲器（BranchTargetBuffer）采用一个小容量的高速缓冲器保存最近成功转移的k条条件转移指令的“转移历史表”和“转移目标地址”，“条件转移指令地址”字段采用全相联方式进行访问。当程序执行到一条指令时，将当前指令地址与BTB中的所有“转移指令地址”进行比较，如相符，则根据同一行中的“转移历史表”预测本次转移方向，并用“转移目标地址”预取指令；如不符，直接取下一条指令。在实际转移条件形成之后，可以根据某一种规则修改BTB中相应内容。4之1\n转移目标缓冲器—举例本章内容>>相关性分析技术>>控制相关>>条件转移的处理>>预测>>动态预测PCofinstructiontoFETCH=?BranchpredictedtakenoruntakenYes:instructionisbranchandusepredictedPCasnextPCNo:branchnotpredicted,proceednormally(NextPC=PC+4)BranchPCPredictedPCPredictionstateBits(optional)4之2\nBTB的工作流程4之3\n转移目标缓冲器—变化本章内容>>相关性分析技术>>控制相关>>条件转移的处理>>预测>>动态预测在BTB中存储一条或多条目标指令，而不是预测的目标地址。4之4\n中断的处理本章内容>>相关性分析技术>>控制相关问题：当中断发生时，流水线中有多条指令在执行，那么断点究竟在哪一条指令呢？解决：不精确断点精确断点\n不精确断点本章内容>>相关性分析技术>>控制相关>>中断的处理让已经进入流水线的所有指令都执行完成，断点就是最后进入流水线的那条指令的地址。例如：下图中不精确断点地址是i+5。S1S2S3S4S5S6S7S8i+5i+4i+3i+2i+1ii-1i-2输入输出申请中断不精确断点2之1\n不精确断点本章内容>>相关性分析技术>>控制相关>>中断的处理特点所需硬件少，控制逻辑相对比较简单，主要缺点是中断响应时间稍长些。应用在早期生产的一批大型流水线处理机中，许多采用了不精确断点法。可用于处理I/O中断等类型中断。2之2\n精确断点本章内容>>相关性分析技术>>控制相关>>中断的处理由哪一条指令的程序性中断或故障发出的中断请求，断点就是这条指令的地址。例如：下图中精确断点地址是i。S1S2S3S4S5S6S7S8i+5i+4i+3i+2i+1ii-1i-2输入输出申请中断精确断点2之1\n精确断点本章内容>>相关性分析技术>>控制相关>>中断的处理特点所需硬件代价较高，控制逻辑相对比较复杂。应用近期生产的流水线处理机一般采用精确断点法。可用于处理程序性中断和机器故障等类型中断。2之2\n综合应用本章内容>>相关性分析技术综合前面的思想，我们介绍一个基于Tomasulo算法、预测执行和保持精确异常的硬件实现技术，此方法已经在一系列处理器（PowerPC603/604/G3/G4、MIPSR10000/R12000、IntelPentiumⅡ/Ⅲ/4、Alpha21264和AMDK5/K6/Athlon）上实现了。2之1\n综合应用本章内容>>相关性分析技术思想实现举例2之2\n思想本章内容>>相关性分析技术>>综合应用指令按序发射、乱序执行、乱序完成和按序提交。在指令提交之前应该避免任何无法恢复的行为发生（即：指令执行之后产生的结果可以直接被其它指令使用，但不必做任何不能恢复的更新操作，直到确定该指令不是预测指令之后，才再做完更新操作），这样才能实现预测错误后的恢复和实现精确异常。\nTomasulo+预测执行的MIPS浮点部件结构主要改变：增加了ROB，去掉了写数缓冲器（可由ROB代替）。6之1\n排序缓冲器(ROB)ROB用于在指令执行结束和指令提交之间保存指令的执行结果：按FIFO的次序存放指令，即指令发射的次序；当指令执行完成时，将结果放在ROB；当指令提交时，将ROB顶部的数值放到寄存器中，数据结构为：指令类型：用于指出指令是何种类型：分支（没有目的结果）/store（内存地址作为目的）/寄存器操作（ALU操作或load，寄存器作为目的）。目的字段：寄存器号(ALU/load)/内存地址(store)。数值字段：保存指令提交前的结果。就绪字段：表示指令是否已经执行结束/结果就绪？本章内容>>相关性分析技术>>综合应用6之2\n指令执行过程—之一本章内容>>相关性分析技术>>综合应用发射从浮点操作队列中取得一条指令。如果相应保留站和排序缓冲器空闲（即：没有结构冲突），则可以发射指令和发送数据。执行对操作数进行相应的操作。当指令所需要的源操作数都准备好，就可以执行该运算；否则监视CDB等待源操作数。6之3\n指令执行过程—之二本章内容>>相关性分析技术>>综合应用写回结果当计算结果出来之后，送至CDB，再从CDB写入排序缓冲器，从而可以送到任何等待该结果的保留站中。提交当一个指令到达ROB的头部时，如果是预测错误的分支指令，则从ROB中去除该指令并从分支的正确方向开始执行；否则用ROB中的值更新相应寄存器/内存单元，并从ROB中去除该指令。6之4\n指令执行的具体过程6之5\n指令执行的具体过程6之6\n举例本章内容>>相关性分析技术>>综合应用程序L.DF6,34(R2)L.DF2,45(R3)MUL.DF0,F2,F4SUB.DF8,F2,F6DIV.DF10,F0,F6ADD.DF6,F8,F2假设各指令在“发射”和“写回结果”所花时钟周期数都为1，在“执行”阶段所花时钟周期数分别为：L.D为2，ADD.D和SUB.D为2，MUL.D为10，DIV.D为40。2之1\n2之2当MUL.D准备提交时的状态\n循环处理本章内容>>相关性分析技术调度技术循环展开软件流水实验环境\n实验环境本章内容>>相关性分析技术>>循环的处理在MIPS扩展流水线中，为解决RAW冲突所需的延迟时间InstructionInstructionLatencyproducingresultusingresultincyclesFPALUopAnotherFPALUop3FPALUopStoredouble2LoaddoubleFPALUop1LoaddoubleStoredouble0IntegeropBranch1Branch12之1\n实验环境本章内容>>相关性分析技术>>循环的处理所用程序for(i=1000;i>0;i=i–1)x[i]=x[i]+s;2之2Loop:L.DF0,0(R1);F0=arrayelementADD.DF4,F0,F2;addscalarinF2S.DF4,0(R1);storeresultDADDUIR1,R1,#-8;decrementpointer(DW)BNER1,R2,Loop;branchR1!=R2\n调度技术—调度前本章内容>>相关性分析技术>>循环的处理ClockcycleissuedLoop:L.DF0,0(R1)1stall2ADD.DF4,F0,F23stall4stall5S.DF4,0(R1)6DADDUIR1,R1,#-87stall8BNER1,R2,Loop9stall102之1执行每个循环体需要10个时钟周期\n本章内容>>相关性分析技术>>循环的处理Loop:L.DF0,0(R1)DADDUIR1,R1,#-8ADD.DF4,F0,F2stallBNER1,R2,Loop;delayedbranchS.DF4,8(R1);altered&interchanged;withDADDUI2之2执行每个循环体只需6个时钟周期调度技术—调度后\n循环展开本章内容>>相关性分析技术>>循环的处理思想多次复制循环体代码，并调整循环出口代码。实现循环展开通常展开成一对循环：设循环次数为n，每次展开k次。第一个循环循环体与原来一样，循环次数为：nmodk。第二个循环循环体是原来循环体展开k次而得，循环次数为：n/k。6之1\n举例一—循环展开Loop:L.DF0,0(R1)ADD.DF4,F0,F2S.DF4,0(R1)L.DF6,-8(R1)ADD.DF8,F6,F2S.DF8,-8(R1)L.DF10,-16(R1)ADD.DF12,F10,F2S.DF12,-16(R1)L.DF14,-24(R1)ADD.DF16,F14,F2S.DF16,-24(R1)DADDUIR1,R1,#-32BNER1,R2,Loop本章内容>>相关性分析技术>>循环的处理6之2\n举例一—分析上述循环程序展开4次，新循环体需运行28个时钟周期，老循环体平均需运行28/4=7个时钟周期。本章内容>>相关性分析技术>>循环的处理6之3\n举例二—循环展开+调度Loop:L.DF0,0(R1)L.DF6,-8(R1)L.DF10,-16(R1)L.DF14,-24(R1)ADD.DF4,F0,F2ADD.DF8,F6,F2ADD.DF12,F10,F2ADD.DF16,F14,F2S.DF4,0(R1)S.DF8,-8(R1)DADDUIR1,R1,#-32S.DF12,16(R1)BNER1,R2,LoopS.DF16,8(R1)本章内容>>相关性分析技术>>循环的处理6之4\n举例二—分析上述循环程序展开4次并进行调度后，新循环体需运行14个时钟周期，老循环体平均需运行14/4=3.5个时钟周期。本章内容>>相关性分析技术>>循环的处理6之5\n小结本章内容>>相关性分析技术>>循环的处理6之6在进行循环展开和调度时，最重要的是：应该清楚指令间的相关关系，并懂得在上述相关关系下如何重组或改变（编译器或硬件实现）指令代码。循环展开和调度可用于解决数据相关(RAW、WAR、WAW)，但收益受制于：循环开销的减少程度、代码量的大小和寄存器的数量。\n软件流水—思想本章内容>>相关性分析技术>>循环的处理软件流水是一种重组循环的技术，如果循环体间是相互独立的，可以将来自不同循环体间的指令组成一个新循环体，在保证循环体中的相关关系的同时提高并行性。5之1\n软件流水—举例循环i:L.DF0,0(R1)ADD.DF4,F0,F2S.DF4,0(R1)循环i+1:L.DF0,0(R1)ADD.DF4,F0,F2S.DF4,0(R1)循环i+2:L.DF0,0(R1)ADD.DF4,F0,F2S.DF4,0(R1)L.DF0,16(R1)ADD.DF4,F0,F2L.DF0,8(R1)LOOP:S.DF4,16(R1)ADD.DF4,F0,F2L.DF0,0(R1)DADDUIR1,R1,#-8BNER1,R2,LOOPS.DF4,16(R1)ADD.DF4,F0,F2S.DF4,8(R1)本章内容>>相关性分析技术>>循环的处理装入代码排空代码5之2\n软件流水—分析一个软件流水循环程序从不同循环体中选取指令，因此仍然能够保证重复出现的原始循环体中的相关关系。装入和排空代码分别对应于软件流水循环体中的开始和结束部分。本例中的软件流水循环体需运行5个时钟周期（经调度后）。本章内容>>相关性分析技术>>循环的处理5之3\n软件流水—比较本章内容>>相关性分析技术>>循环的处理与循环展开相比，软件流水最主要的优点是：产生的代码少。软件流水和循环展开除了能够取得较好的内层循环调度外，还各自减少了不同类型的开销：循环展开减少的是循环开销（分支和计数器更新的代码），软件流水减少的是循环不能全速执行的次数：装入和排空各一次，而循环展开则是多次。故要获得最优性能理想的方法就是结合循环展开和软件流水。5之4\n软件流水—比较(图)本章内容>>相关性分析技术>>循环的处理5之5\n多指令发射技术超标量处理机超长指令字处理机本章内容\n超标量处理机工作原理调度方法资源冲突性能分析本章内容>>多指令发射技术\n工作原理标量处理机超标量处理机本章内容>>多指令发射技术>>超标量处理机\n标量处理机—连接图本章内容>>多指令发射技术>>超标量处理机>>工作原理IFIDFA1FA2FA3MD1MD2MD3ALLS浮点加法部件乘除法部件定点ALU部件取数存数部件WR来自指令Cache通用寄存器后行写数栈取指令指令译码指令执行写回结果3之1\n标量处理机—时空图本章内容>>多指令发射技术>>超标量处理机>>工作原理3之2IF时钟周期指令I1I2I3IDEXWRIFIDEXWRIFIDEXWR123456\n标量处理机—解释标量处理机只有一条指令流水线，采用单发射方式：每个周期只取一条指令、只译码一条指令、只执行一条指令、只写回一个运算结果。取指部件、译码部件和写结果部件各设置一套，可以只设置一个多功能操作部件，也可以设置多个独立的操作部件；操作部件中可以采用流水线结构，也可以不采用流水线结构。设计目标是每个时钟周期平均执行一条指令，ILP的期望值1。本章内容>>多指令发射技术>>超标量处理机>>工作原理3之3\n超标量处理机—连接图本章内容>>多指令发射技术>>超标量处理机>>工作原理取指令指令译码指令执行写回结果8之1IFIDFA1FA2FA3MD1MD2MD3ALLS浮点加法部件乘除法部件定点ALU部件取数存数部件WRIFIDWR来自指令Cache来自指令Cache通用寄存器后行写数栈通用寄存器后行写数栈\n超标量处理机—时空图本章内容>>多指令发射技术>>超标量处理机>>工作原理8之2IF时钟周期指令I1I2I3IDEXWR123456I4I5I6I7I8IFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWR\n超标量处理机—解释本章内容>>多指令发射技术>>超标量处理机>>工作原理8之3超标量处理机必须有两条或两条以上能够同时工作的指令流水线，采用多发射方式：每个周期同时取多条指令、同时译码多条指令、同时执行多条指令、同时写回多个运算结果。需要多个取指令部件、多个指令译码部件和多个写结果部件，设置多个指令执行部件，复杂的指令执行部件一般采用流水线结构。设计目标是每个时钟周期平均执行多条指令，ILP的期望值大于1。\n超标量处理机—定义本章内容>>多指令发射技术>>超标量处理机>>工作原理8之4一个时钟周期内能够同时发射多条指令的处理机称为超标量处理机。目前在多数超标量处理机中，每个时钟周期硬件可以发射1～8条不等数量的指令，可以通过编译器进行静态调度（按序执行），也可以使用诸如记分板或Tomasulo算法的动态调度（乱序执行）。\n超标量处理机—先行指令窗口(1)本章内容>>多指令发射技术>>超标量处理机>>工作原理8之5为进一步提高超标量处理机的性能，通常采用先行指令窗口：能够从指令Cache中预取多条指令，能够对窗口内的指令进行数据相关性分析和功能部件冲突的检测。另外还应该至少有一套取指令部件和一套指令译码部件。先行指令窗口的大小对超标量处理机的性能影响很大，目前窗口大小一般为2至8条指令。\n超标量处理机—先行指令窗口(2)本章内容>>多指令发射技术>>超标量处理机>>工作原理8之6IFIDFA1FA2FA3MD1MD2MD3ALLS浮点加法部件乘除法部件定点ALU部件取数存数部件WRIFIDWRIFID先行指令窗口\n超标量处理机—举例(1)本章内容>>多指令发射技术>>超标量处理机>>工作原理8之7整数部件整数部件位操作浮点加乘法部件除法部件图形部件图形部件内部总线读数/存数部件通用寄存器堆扩展寄存器堆目标指令Cache指令分配/转移部件数据Cache(8KB)指令Cache(8KB)系统总线32位地址总线32位数据总线超标量处理机MC88110的结构\n超标量处理机—举例(2)10个操作部件一般分为三类：定点处理部件、浮点处理部件和图形加速部件。两个寄存器堆整数部件使用通用寄存器堆，32个32位寄存器；浮点部件使用扩展寄存器堆，32个80位寄存器。两个独立的高速Cache哈佛结构，各为8KB，采用两路组相联方式工作。转移目标指令Cache在有两路分支时，存放其中一路分支上的指令。本章内容>>多指令发射技术>>超标量处理机>>工作原理8之8\n调度方法根据多流水线中指令发射顺序和完成顺序的不同组合，多流水线调度可分为：（下面通过一个例子进行介绍）顺序发射顺序完成顺序发射乱序完成乱序发射乱序完成本章内容>>多指令发射技术>>超标量处理机5之1\n顺序发射顺序完成I1:LOADR1,A;R1←主存（A）单元I2:FADDR2,R1;R2←(R2)+(R1)I3:FMULR3,R4;R3←(R3)×(R4)I4:FADDR4,R5;R4←(R4)+(R5)I5:DECR6;R6←(R6)-1I6:FMULR6,R7;R6←(R6)+(R7)IF1ID1LSWR1IF2ID2FA1FA2FA3WR2I3IF1ID1MD1MD2MD3WR1I4IF2ID2FA1FA2FA3WR2I5IF1ID1ALWR1I6IF2ID2MD1MD2MD3WR2I1I212345678910指令时钟周期流水线1流水线25之2\n顺序发射乱序完成I1:LOADR1,A;R1←主存（A）单元I2:FADDR2,R1;R2←(R2)+(R1)I3:FMULR3,R4;R3←(R3)×(R4)I4:FADDR4,R5;R4←(R4)+(R5)I5:DECR6;R6←(R6)-1I6:FMULR6,R7;R6←(R6)+(R7)IF1ID1LSWR1IF2ID2FA1FA2FA3WR2I3IF1ID1MD1MD2MD3WR1I4IF2ID2FA1FA2FA3WR2I5IF1ID1ALWR1I6IF2ID2MD1MD2MD3WR2I1I212345678910指令时钟周期流水线1流水线25之3\n乱序发射乱序完成（需采用先行指令窗口）I1:LOADR1,A;R1←主存（A）单元I2:FADDR2,R1;R2←(R2)+(R1)I3:FMULR3,R4;R3←(R3)×(R4)I4:FADDR4,R5;R4←(R4)+(R5)I5:DECR6;R6←(R6)-1I6:FMULR6,R7;R6←(R6)+(R7)IF1ID1LSWR1IF2ID2MD1MD2MD3WR2IF3ID3FA1FA2FA3WR3I2IF1ID1FA1FA2FA3WR2I5IF2ID2ALWR2I6IF1ID1MD1MD2MD3WR1I1I312345678910指令时钟周期I4流水线1流水线2先行窗口5之4\n举例本章内容>>多指令发射技术>>超标量处理机名称发射结构冲突检测调度主要特征实例超标量（静态）动态硬件静态顺序执行SunUltraSPARCⅡ/Ⅲ超标量（动态）动态硬件动态部分乱序执行IBMPower2超标量（猜测）动态硬件带猜测的动态执行带猜测的乱序执行PentiumⅢ/4,MIPSR10K5之5\n资源冲突如果操作部件采用流水线结构，发生资源冲突的可能性很小；如果不采用流水线结构，发生资源冲突的可能性就比较大。因此，在超标量处理机中，操作部件一般要采用流水线结构。如果由于某种原因，操作部件不能采用流水线结构，则必须设置多个相同种类的操作部件。本章内容>>多指令发射技术>>超标量处理机4之1\n操作部件不采用流水本章内容>>多指令发射技术>>超标量处理机I1:FADDR0,R1;R0←(R0)+(R1)I2:FMULR2,R3;R2←(R2)×(R3)I3:FADDR4,R5;R4←(R4)+(R5)I4:FMULR6,R7;R6←(R6)×(R7)IF1ID1FADDWR1IF2ID2FMULWR2IF1ID1FADDWR1IF2ID2FMULWR2流水线1流水线2I1I2指令时钟周期I3I412345678910114之2\n操作部件采用流水本章内容>>多指令发射技术>>超标量处理机I1:FADDR0,R1;R0←(R0)+(R1)I2:FMULR2,R3;R2←(R2)×(R3)I3:FADDR4,R5;R4←(R4)+(R5)I4:FMULR6,R7;R6←(R6)×(R7)IF1ID1FA1FA2FA3WR1IF2ID2MD1MD2MD3MD4WR2IF1ID1FA1FA2FA3WR1IF2ID2MD1MD2MD3MD4WR2流水线1流水线2I1I2指令时钟周期I3I412345678910114之3\n提示本章内容>>多指令发射技术>>超标量处理机普通标量处理机，希望相同操作连续出现。只有连续出现相同操作的指令序列时，流水线的效率才能得到充分发挥。超标量处理机则正好相反，希望相同操作不要连续出现。相同操作的指令序列连续出现时，会发生资源冲突；要求相同操作的指令能够相对均匀地分布在程序中。超标量处理机的这种要求正好符合一般标量程序的特点。4之4\n性能分析单流水线普通标量处理机的指令级并行度记作(1,1)，超标量处理机的指令级并行度记作(m,1)。理想情况下N条没有冲突和相关的指令在单流水线普通标量处理机上执行时间为：在每时钟周期发射m条指令的超标量处理机上执行时间：本章内容>>多指令发射技术>>超标量处理机2之1\n性能分析本章内容>>多指令发射技术>>超标量处理机超标量处理机相对于单流水线普通标量处理机的加速比为：当N→∞时，最大加速比为：2之2\n超长指令字处理机(VLIW)工作原理设计问题本章内容>>多指令发射技术\n工作原理本章内容>>多指令发射技术>>VLIW在编译时，编译程序找出指令间潜在的并行性，将多个能并行执行的不相关或无关的操作先行压缩组合在一起，形成一条有多个操作段的超长指令；运行时，不再用软件/硬件来检测其并行性，直接由这条超长指令控制机器中多个相互独立的功能部件并行操作。每个操作段控制其中的一个功能部件，相当于同时执行多条指令。5之1\n示意图本章内容>>多指令发射技术>>VLIW5之2\n传统指令和VLIW指令本章内容>>多指令发射技术>>VLIW5之3\n超标量处理机本章内容>>多指令发射技术>>VLIW5之4\n两者比较本章内容>>多指令发射技术>>VLIW5之5\n设计问题本章内容>>多指令发射技术>>VLIW编译技术代码膨胀二进制代码的兼容性\n编译技术本章内容>>多指令发射技术>>VLIW>>设计问题别名分析循环展开软件流水路径调度硬件支持的编译技术······4之1\n举例—说明程序Loop:L.DF0,0(R1)ADD.DF4,F0,F2S.DF4,0(R1)DADDUIR1,R1,#-8BNER1,R2,LoopVLIW处理机每个时钟周期能发射1个load/store或分支操作、1个定点操作和1个浮点操作。相关延迟Load/Store为1cycles、定点为1cycles、分支为1cycles和浮点为2cycles本章内容>>多指令发射技术>>VLIW>>设计问题4之2\n举例—VLIW调度本章内容>>多指令发射技术>>VLIW>>设计问题4之3Load/store或分支定点操作浮点操作时钟周期L.DF0,0(R1)nopnop1nopnopnop2nopnopADD.DF4,F0,F23nopnopnop4nopnopnop5S.DF4,0(R1)DADDUIR1,R1,#-8nop6nopnopnop7BNER1,R2,Loopnopnop8nopnopnop9\n举例—循环展开+VLIW调度本章内容>>多指令发射技术>>VLIW>>设计问题4之4Load/store或分支定点操作浮点操作时钟周期L.DF0,0(R1)nopnop1L.DF6,-8(R1)nopnop2L.DF10,-16(R1)nopADD.DF4,F0,F23L.DF14,-24(R1)nopADD.DF8,F6,F24L.DF18,-32(R1)nopADD.DF12,F10,F25S.DF4,0(R1)nopADD.DF16,F14,F26S.DF8,-8(R1)nopADD.DF20,F18,F27S.DF12,-16(R1)nopnop8S.DF16,-24(R1)nopnop9S.DF20,-32(R1)DADDUIR1,R1,#-40nop10nopnopnop11BNER1,R2,Loopnopnop12nopnopnop13\n代码膨胀本章内容>>多指令发射技术>>VLIW>>设计问题3之1主要原因有二：为了产生足够的操作填充一条长指令，必须展开多个循环体，这就增加了代码量。若指令未被填满，则空闲的功能部件在指令译码时仍会被翻译，并填以无用的指令，从而也增加了代码量。\n解决方法本章内容>>多指令发射技术>>VLIW>>设计问题3之2有二：智能译码例如：只有一个立即数字段供所有的功能部件使用。代码压缩将指令压缩存储到内存中，并在指令读出到Cache或进行译码时才扩展它们。\n代码压缩本章内容>>多指令发射技术>>VLIW>>设计问题3之3\n二进制代码的兼容性本章内容>>多指令发射技术>>VLIW>>设计问题2之1\n解决方法有二：机器代码翻译或仿真放宽VLIW的限制以保持二进制代码的兼容性本章内容>>多指令发射技术>>VLIW>>设计问题2之2\nILP总结本章内容\n作业本章内容参见“第四章（习题）.DOC”可要认真做哦！