精确断点与不精确断点.ppt

5.3.7 精确断点与不精确断点,对于输入输出设备的中断服务，实际上不需要有精确断点。比较简单的处理方法是：让已经进入流水线的所有指令都执行完成，断点就是最后进入流水线的那条指令的地址。对于程序性错误和机器故障等引起的中断，它们出现的概率很低，处理原则：不在于缩短时间，关键是要正确保存现场和正确恢复断点。,不精确断点(Imprecise)，流水线可以不断流需要的硬件比较少，控制逻辑比较简单中断响应时间加长 采用不精确断点法可能会发生如下两个问题：(1)程序的调试困难调试程序时要设置断点，程序员通过查看断点处的中间执行结果判断程序是否正确。但由于不精确断点，程序不能准确中断，因此，难于调试。早期的流水线处理机，多采用不精确断点法近期的流水线处理机一般都采用精确断点法,(2)程序执行的结果可能出错，例如：i：FADD R1,R2；(R1)(R2)R1 i+1：FMUL R3,R1；(R3)(R1)R3当第i条指令执行到S6段时发现浮点加法结果溢出，于是发出中断服务申请。由于采用不精确断点法，已经进入流水线的第i+1条指令将执行完成；因为第i+1条指令使用了不正确的R1，所以浮点乘法的执行结果是不正确的。采用精确断(Precise)点法，要设置一定数量的后援寄存器，把整个流水线中所有指令的执行结果和现场都保存下来。,5.4 动态调度技术,5.4.1 顺序流动与乱序流动5.4.2 乱序流动中的数据相关5.4.3 数据重定向方法5.4.4 Tomasulo动态调度算法,实现方法：由硬件动态调整指令执行顺序，以减少数据相关造成的影响。主要优点：能够处理在编译时无法确定的相关，并简化编译器设计在其他流水线机器上编译的目标代码也能够高效运行用静态调度法生成的代码也能在动态调度法的机器中运行主要缺点：指令级并行度低，因为只能在比较小的范围内寻找并行性,5.4.1 顺序流动与乱序流动,1.顺序流动方式：任务按顺序流入流水线,也按顺序流出流水线把如下一段程序输入到这条流水线中：k：R0（R1）k+1：k+2：R2（R0）（R3）k+3：k+4：k+5：,指令k+2无法继续执行，要在功能段S2中等待。后续的指令k+4、k+5、等也不能进入流水线。功能段S3、S4、S5将逐渐空闲。缺点：吞吐率和效率降低优点：流水线的控制逻辑比较简单,流水线“断流”，有些功能段“空闲”,2.乱序(Out of order)流动方式：指令流出流水线的顺序与流入流水线的顺序不同。又称为错序流动方式、无序流动方式、异步流动方式等。,5.4.2 乱序流动中的数据相关,在乱序流动方式中，可能发生三种数据相关 写写相关 k：LOAD F1,A;F1（A）写读相关 k+1：FADD F2,F1;F2（F2）+（F1）k+2：FMUL F1,F3;F1（F1）（F3）k+3：STORE F1,B;B（F1）读写相关(1)写读相关：指令k与指令k+1之间关于F1的相关，又称为数据相关、先写后读相关、流相关、WR相关、RAW相关等。,(2)读写相关：指令k+1与指令k+2之间关于F1的相关，变量名相关、先读后写相关、反相关、RW相关、WAR相关等。(3)写写相关：指令k与指令k+2左边的F1之间的相关关系称为：输出相关、写写相关、WW相关、WAW相关或写后再写相关等。有时把相关称为“冒险”(hazard)、“竟争”(competition)等。在程序执行过程中，只有避免相关，执行结果才是正确的。,三种数据相关可以用下列关系式来表示：对于写读相关 D(i)S(j)对于读写相关 S(i)D(j)对于写写相关 D(i)D(j),5.4.3 数据重定向方法,1.三种数据相关的重定向 重定向之前，j只能在i之后执行。重定向之后，可以做到：(1)写读相关，j与i可以同时执行 即专用数据通路(2)写写相关，先后顺序无关(3)读写相关，先后顺序无关 后两种情况又称为“变量换名技术”,2.变量换名技术用来自动消除读写数据相关和写写数据相关规则：一个变量只允许定值一次在三种数据相关中，实际上只有写读数据相关必须依靠硬件、或采用软硬件结合的方法来解决 解决方法：推后处理或专用数据通路在上面的数据重定向图中，把B换成了B，并在以后的都引用B读写数据相关和写写数据相关就不存在了。一个实际例子：,Loop:LD F0,0(R1)ADD F0,F2 SD 0(R1),F0 LD F0,-8(R1)ADD F0,F2 SD-8(R1),F0 LD F0,-16(R1)ADD F0,F2 SD-16(R1),F0 LD F0,-24(R1)ADD F0,F2 SD-24(R1),F0 SUBI R1,R1,#32 BNEZ R1,Loop,Loop:LD F0,0(R1)LD F4,-8(R1)LD F6,-16(R1)LD F8,-24(R1)ADD F0，F2 ADD F4，F2 ADD F6，F2 ADD F8，F2 SD 0(R1),F0 SD-8(R1),F4 SUBI R1,R1,#32 SD-16(R1),F6 BNEZ R1,Loop SD-24(R1),F8,3.一个简单的程序：k：LOAD F1,A k+1：FADD F1,F2 k+2：FMUL F1,F3 k+3：STORE F1,B,专门设置：AFADD、FMULB、FADDFMUL三条专用路径。撤消：F1FADD、F1FMUL、FADDF1、AF1的路径。,5.4.4 Tomasulo动态调度算法P310,实用的动态调度算法主要有两种:(1)集中控制：CDC计分牌(scorebord)算法，最先在CDC 6600大型机中采用。(2)分散控制：Tomasulo算法,公共数据总线法，令牌法等。最早在大型机IBM 360/91的浮点处理部件中被采用。以上面的一段程序为例说明Tomasulo算法k：LOAD F1,Ak+1：FADD F1,F2k+2：FMUL F1,F3k+3：STORE F1,B,5.5 超标量处理机,5.5.1 基本结构5.5.2 单发射与多发射5.5.3 多流水线调度5.5.4 资源冲突5.5.5 超标量处理机性能,三种主流处理机：超标量处理机 超流水线处理机 超标量超流水线处理机,5.5.1 基本结构,普通标量流水线处理机：一条指令流水线，一个多功能操作部件，每个时钟周期平均执行指令的条数小于1。多操作部件标量处理机：一条指令流水线，多个独立的操作部件，指令级并行度小于1。超标量处理机典型结构：多条并行工作的指令流水线，多个独立的操作部件，指令级并行度（ILP）大于1。,Motorola公司的MC88110有10个操作部件两个寄存器堆：整数部件通用寄存器堆，32个32位寄存器浮点部件扩展寄存器堆，32个80位寄存器缓冲深度为4的先行读数栈缓冲深度为3的后行写数栈两个独立的高速Cache中，各为8KB，采用两路组相联方式转移目标指令Cache，用于存放另一条分支上的指令,5.5.2 单发射与多发射,1.单发射处理机：每个周期只取一条指令、只译码一条指令，只执行一条指令，只写回一个运算结果。取指令部件和指令译码部件各设置一套；只设置一个多功能操作部件或设置多个独立的操作部件；操作部件中可以采用流水线结构，也可以不采用流水线结构。目标是每个时钟周期平均执行一条指令，ILP的期望值为1。,2.多发射处理机：每个周期同时取多条指令、同时译码多条指令，同时执行多条指令，同时写回多个运算结果。多个取指令部件，多个指令译码部件和多个写结果部件。设置多个指令执行部件，有些指令执行部件采用流水线结构。目标是每个时钟周期平均执行多条指令，ILP的期望值大于1。,3.超标量处理机：有两条或两条以上能同时工作的指令流水线先行指令窗口：能够从指令Cache中预取多条指令，能够对窗口内的指令进行数据相关性分析和功能部件冲突检测。例如：Intel公司的i860、i960、Pentium，Motolora公司的MC88110，IBM公司的Power 6000,TI公司生产SuperSPARC等操作部件的个数一般多于每个周期发射的指令条数。通常为4 个至16个操作部件。超标量处理机的指令级并行度：1ILPm,5.5.3 多流水线调度,顺序发射(in-order issue)与乱序发射(out-order issue)：指令发射顺序是按照程序中指令排列顺序进行的称为顺序发射顺序完成(in-order completion)与乱序完成(out-order completion)：指令完成顺序是按照程序中指令排列顺序进行的称为顺序完成多流水线的调度主要有三种方法：顺序发射顺序完成顺序发射乱序完成乱序发射乱序完成,以如下6条指令组成的程序为例，说明这三种调度方法 I1：LOAD R1,A；R1(A)I2：FADD R2,R1；R2(R2)(R1)I3：FMUL R3,R4；R3(R3)(R4)I4：FADD R4,R5；R4(R4)(R5)I5：DEC R6；R6(R6)1 I6：FMUL R6,R7；R6(R6)(R7)6条指令中有4个数据相关，包括2个写读相关，1个读写相关和1个写写相关。,1.顺序发射顺序完成 共用10个时钟周期完成 还有8个空闲的时钟周期,2.顺序发射乱序完成 总的执行时间为9个时钟周期，节省了一个时钟周期。少了5个空闲时钟周期。,3.乱序发射乱序完成没有空闲周期，功能部件得到充分利用。总的执行时间为8个周期，节省2个周期。,5.5.4 资源冲突,如果操作部件采用流水线结构，发生资源冲突的可能性很小；如果不采用流水线结构，发生资源冲突的可能性就比较大。下面是一个由4条指令的程序例子：I1：FADD R0,R1；R0(R0)(R1)I2：FMUL R2,R3；R2(R2)(R3)I3：FADD R4,R5；R4(R4)(R5)I4：FMUL R6,R7；R6(R6)(R7),操作部件不采用流水线：做完4条指令总共用了11个周期，有5个空闲周期。,操作部件采用流水线：做完4条指令共用8个周期，少用3个周期。,操作部件采用流水线结构的原因分析假每个周期发射m条指令，操作部件的延迟时间为k个周期，如果操作部件不采用流水线结构，则使用同一个操作部件的两条指令应该至少相差mk如果操作部件采用k段流水线结构，则使用同一个操作部件的两条指令只需相差m或m以上指令流水线的段数k一般在4至10之间，每个时钟周期发射的指令条数m在2至4之间。取中间值，k7，m3,为了不发生资源冲突，如果操作部件不采用流水线结构，两条使用同一个功能部件的指令序号必须相差21或21以上。如果操作部件采用流水线结构，两条使用同一个功能部件的指令序号只需要相差3或3以上。因此，在超标量处理机中，操作部件一般要采用流水线结构。如果由于某种原因，操作部件不能采用流水线结构，则必须设置多个相同种类的操作部件,普通标量处理机，希望相同操作连续出现。只有连续出现相同操作的指令序列时，流水线的效率才能得到充分发挥。超标量处理机则正好相反，希望相同操作不要连续出现。相同操作的指令序列连续出现时，会发生资源冲突；要求相同操作的指令能够相对均匀地分布在程序中。超标量处理机的这种要求正好符合一般标量程序的特点。,5.5.5 超标量处理机性能,单流水线普通标量处理机的指令级并行度记作(1,1)，超标量处理机的指令级并行度记作(m,1)，超流水线处理机的指令级并行度记作(1,n)，而超标量超流水线处理机的指令级并行度记作(m,n)。在理想情况下，N条指令在单流水线标量处理机上的执行时间为：T(1,1)(kN1)t,在每个周期发射m条指令的超标量处理机上执行的时间为：超标量处理机相对于单流水线标量处理机的加速比为：超标量处理机的加速比的最大值为：S(m,1)MAXm,5.6 超流水线处理机,5.6.1 指令执行时序5.6.2 典型处理机结构5.6.3 超流水线处理机性能,超流水线处理机的两种定义：在一个周期内分时发射多条指令的处理机指令流水线的段数大于等于8的流水线处理机提高处理机性能的两种方法：通过增加硬件资源来提高处理机性能通过各部分硬件的重叠工作来提高处理机性能两种不同并行性：超标量处理机采用的是空间并行性。超流水线处理机采用的是时间并行性。,5.6.1 指令执行时序,每隔1/n个时钟周期发射一条指令，即处理机的流水线周期为1/n个时钟周期。,5.6.2 典型处理机结构,MIPS R4000处理机：每个时钟周期包含两个流水段是一种很标准的超流水线处理机结构。指令流水线有8个流水段。指令Cache和数据Cache的容量各8KB，每个时钟周期可以访问Cache两次，在一个时钟周期内可以从指令Cache中读出两条指令，从数据Cache中读出或写入两个数据。主要运算部件有整数部件和浮点部件。,如果在LOAD指令之后的两条指令中，任何一条指令要在它的EX流水级使用这个数据，则指令流水线要暂停一个时钟周期。,5.6.3 超流水线处理机性能,指令级并行度为(1,n)的超流水线处理机，执行N条指令所的时间为：超流水线处理机相对于单流水线普通标量处理机的加速比为：加速比的最大值为：S(1,n)MAXn,5.7 超标量超流水线处理机,一个时钟周期发射m次，每次发射n条指令 5.7.1 指令执行时序5.7.2 典型处理机结构5.7.3 超标量超流水线处理机性能5.7.4 三种处理机的性能比较,5.7.1 指令执行时序,5.7.2 典型处理机结构,DEC公司的Alpha处理机为典型的超标量超流水线结构。主要由四个功能部件和两个Cache组成：整数部件EBOX 浮点部件FBOX 地址部件ABOX 中央控制部件IBOX 指令Cache和数据Cache在EBOX内还有多条专用数据通路，可以把运算结果直接送到执行部件。,中央控制部件IBOX能够同时完成：同时读出两条指令；同时对两条指令进行译码，并作相关性检测；如果资源和相关性允许，IBOX就把两条指令同时发射给EBOX、ABOX和FBOX三个执行部件中的两个。指令流水线的控制方式：采用顺序发射乱序完成。在指令Cache中有一个转移历史表，实现条件转移的动态预测。,Alpha 21064处理机共有三条指令流水线：(1)整数操作流水线为7个流水段，其中，取指令2个流水段、分析指令2个流水段、运算2个流水段、写结果1个流水段。(2)访问存储器流水线为7个流水段。(3)浮点操作流水线分为10个流水段，其中，浮点执行部件FBOX的延迟时间为6个流水段。三条指令流水线的平均段数为(7+7+10)/3=8，且每个时钟周期发射两条指令。因此，Alpha 21064处理机为超标量超流水线处理机。,5.7.3 超标量超流水线处理机的性能,指令级并行度为(m,n)的超标量超流水线处理机，连续执行N条指令所需要的时间为：超标量超流水线处理机相对于单流水线标量处理机的加速比为：在理想情况下，超标量超流水线处理机加速比的最大值为：S(m,n)MAXm n,5.7.4 三种标量处理机的性能比较,从三种标量处理机的性能曲线中，可以得出如下结论：1.三种处理机的性能关系超标量处理机的相对性能最高，其次是超标量超流水线处理机，超流水线处理机的相对性能最低，主要原因如下：(1)超标量处理机功能部件的冲突比超流水线处理机小。在指令执行过程中的许多功能段，超标量处理机都重复设置有多个相同的指令执行部件，而超流水线处理机只是把同一个指令执行部件分解为多个流水级。,(2)条件转移等操作造成的损失，超流水线处理机要比超标量处理机大。由于超流水线处理机采用深度流水线结构，对条件转移等操作比超标量处理机敏感。(3)超流水线处理机的启动延迟通常要比超标量处理机大。超标量处理机在每个时钟周期的一开始就同时发射多条指令，超流水线处理机把一个时钟周期平均分成多个流水线周期，每个流水线周期只发射一条指令。,2.实际指令级并行度与理论指令级并行度的关系 当横坐标给出的理论指令级并行度比较低时，处理机的实际指令级并行度的提高比较快。当理论指令级并行度进一步增加时，处理机实际指令级并行度提高的速度越来越慢。在实际设计超标量、超流水线、超标量超流水线处理机的指令级并行度时要适当，否则，有可能造成花费了大量的硬件，但实际上处理机所能达到的指令级并行度并不高。目前，一般认为，m 和 n 都不要超过 4。,3.最大指令级并行度 一个特定程序由于受到本身的数据相关和控制相关的限制，它的指令级并行度的最大值是有限的，是有个确定的值。最大指令级并行度由程序自身的语义决定，与这个程序运行在那一种处理机上及采用何种方法开发并行性无关。对于某一个特定的程序，图中的三条曲线最终都要收拢到同一个点上。对于各个不同程序，这个收拢点的位置也是不同的。,本章重点：1.线性流水线的性能分析及计算2.非线性流水线的调度方法3.数据相关的种类，发生的情况及解决的办法4.分支预测技术5.乱序流动方式中的数据相关及解决办法6.单发射、多发射与先行指令窗口7.超标量、超流水线处理机的结构及性能分析 练习题:5.5 5.6 5.8 5.15 5.17 5.18,