计算机系统结构第4章指令级并行及限制.ppt

1,第四章 指令级并行及限制,4.1 指令级并行的概念 4.2 指令的动态调度 4.3 转移预测技术 4.4 多发射技术 4.5 向指令级并行的支持与限制 4.6 Intel Pentium 4 实例分析,2,4.1 指令级并行的概念,指令级并行的概念,几乎所有的处理机都利用流水线来使指令重叠并行执行，以达到提高性能的目的。这种指令之间存在的潜在并行性称为指令级并行。 （ILP：Instruction-Level Parallelism）,3,4.1.1 指令级并行,1、流水线处理机的实际CPI 理想流水线的CPI加上各类停顿的时钟周期数： CPI流水线 = CPI理想 + 停顿结构冲突 + 停顿数据冲突 + 停顿控制冲突 理想CPI是衡量流水线最高性能的一个指标。 IPC：Instructions Per Cycle （每个时钟周期完成的指令条数） 2、基本程序块 基本程序块：一段除了入口和出口以外不包含其他分支的线性代码段。 程序平均每57条指令就会有一个分支。,4,3、循环级并行：使一个循环中的不同循环体并行执行。 开发循环体中存在的并行性 最常见、最基本 是指令级并行研究的重点之一 例如，考虑下述语句： for （i=1； i=500； i=i1） ai=ais； 每一次循环都可以与其他的循环重叠并行执行； 在每一次循环的内部，却没有任何的并行性。,5,4、最基本的开发循环级并行的技术 循环展开（loop unrolling）技术 采用向量指令和向量数据表示,6,4.1.2 相关性对指令级并行的影响,本章使用的浮点流水线的延迟,7,例4-1 对于下面的源代码， for (i=1; i=1000; i+) xi = xi + s; （）转换成DLX汇编语言，在不进行指令调度和进行指令调度两种情况下，分析代码一次循环的执行时间。 （）编译过程进行分析，来仔细考察换名的过程。 备注：本章使用的浮点流水线的延迟如上表所示,8,解： （） (1) 变量分配寄存器 整数寄存器R1：循环计数器，初值为向量 中最高端地址元素的地址。 浮点寄存器F2：保存常数S。 假定最低端元素的地址为8。 (2) DLX汇编语言后的程序 Loop: LD F0,0(R1) ADDD F4,F0,F2 SD 0(R1),F4 SUBI R1,R1,#8 BNEZ R1,Loop,9,(3) 程序执行的实际时钟,根据上表中给出的的延迟，实际时钟如下： 指令流出时钟 Loop: LD F0 , 0(R1) 1 （空转） 2 ADDD F4 , F0 , F2 3 （空转） 4 （空转） 5 SD 0(R1) , F4 6 SUBI R1 , R1 , #8 7 （空转） 8 BNEZ R1 , Loop 9 （空转） 10 每个元素的操作需要10个时钟周期，其中5个是空转周期。,10,(4) 指令调度以后，程序的执行情况,SD放在分支指令的分支延迟槽中 对存储器地址偏移量进行调整 指令流出时钟 Loop: LD F0 , 0(R1) 1 SUBI R1 , R1 , #8 2 ADDD F4 , F0 , F2 3 （空转） 4 BNEZ R1 , Loop 5 SD 8(R1) , F4 6 一个元素的操作时间从10个时钟周期减少到6个 5个周期是有指令执行的，1个空转周期。,11,（）,(1) 首先，仅仅去除4遍循环体中的分支指令，得到以下由17条指令构成的指令序列，如下所示：,Loop: LD F0 , 0(R1) ADD.D F4 , F0 , F2 SD 0(R1) , F4 SUBI R1 , R1 , #8 LD F0 , 0(R1) ADD.D F4 , F0 , F2 SD 0(R1) , F4 SUBI R1 , R1 , #8 LD F0 , 0(R1) ADD.D F4 , F0 , F2 SD 0(R1) , F4 SUBI R1 , R1 , #8 LD F0 , 0(R1) ADD.D F4 , F0 , F2 SD 0(R1) , F4 SUBI R1 , R1 , #8 BNEZ R1 , Loop,12,(2) 编译器可以通过对相关链上存储器访问偏移量的直接调整，将前3条SUBI指令消除掉，从而得到下面一个14条指令构成的指令序列，如下所示： Loop: LD F0 , 0(R1) ADD.D F4 , F0 , F2 SD 0(R1) , F4 LD F0 , -8(R1) ADD.D F4 , F0 , F2 SD -8(R1) , F4 LD F0 , -16(R1) ADD.D F4 , F0 , F2 SD -16(R1) , F4 LD F0 , -24(R1) ADD.D F4 , F0 , F2 SD -24(R1) , F4 SUBI R1 , R1 , #32 BNEZ R1 , Loop,13,(3) 通过寄存器换名，消除名相关。得到下面的指令序列，如下所示： Loop: LD F0 , 0(R1) ADD.D F4 , F0 , F2 SD 0(R1) , F4 LD F6 , -8(R1) ADD.D F8 , F6 , F2 SD -8(R1) , F8 LD F10 , -16(R1) ADD.D F12 , F10 , F2 SD -16(R1) , F12 LD F14 , -24(R1) ADD.D F16 , F14 , F2 SD -24(R1) , F16 SUBI R1 , R1 , #32 BNEZ R1 , Loop,14,再来看一个控制相关的例子。,典型的程序结构是“if-then”结构。,if p1 S1; ; S; if p2 S2; ;,P1控制相关S1，P2控制相关S2，而不是S1。,15,控制相关会带来两方面的限制：,（1）控制相关于一个分支的指令不能被移到分支之前执行。例如ifelse程序中，then后面的语句不能移到if之前执行 （2）没有控制相关于一个分支的指令不能移到该分支指令之后，从而受这个分支控制，例如ifthen程序中，if前的指令不能移到then部分执行。,16,再考察例4-1，假设循环展开时，循环控制分支指令没有去除，则指令序列如下所示：,loop: LD F0 , 0(R1) ADD.D F4 , F0 , F2 SD 0(R1) , F4 SUBI R1 , R1 , #8 BEQZ R1 , Exit LD F0 , 0(R1) DD F4 , F0 , F2 SD 0(R1) , F4 SUBI R1 , R1 , #8 BEQZ R1 , Exit LD F0 , 0(R1),ADD.D F4 , F0 , F2 SD 0(R1) , F4 SUBI R1 , R1 , #8 BEQZ R1 , Exit LD F0 , 0(R1) ADD.D F4 , F0 , F2 SD 0(R1) , F4 SUBI R1 , R1 , #8 BNEZ R1 , Loop Exit:,17,由于上述指令段中BEQZ R1 , Exit，BEQZ R1 , Exit，BEQZ R1 , Exit三条分支指令的存在，引起控制相关，导致其后的4条指令不能跨越分支指令进行调度，即不同循环遍次里的指令不能够跨越循环遍次进行调度。,18,4.1.3支持指令级并行的基本编译技术,1.检测并提高循环级并行,2.循环展开技术,3.全局指令调度,19,1.检测并提高循环级并行,循环级并行是指在源代码或靠近源代码的层次进行并行分析，而指令级并行则是对经过编译技术产生的指令进行并行分析。,循环级并行分析集中分析某一个循环体中的数据存取是否涉及前一个循环体中的数据。这种相关叫做体间相关。,20,在这个循环程序中，用到了两次xi，它们之间即存在数据相关，但这是循环体内的相关而不是体间相关。在相邻的两次对i的引用上，存在体间相关，但这种相关包含规约变量，很容易识别和消除。,看下面的程序： for (i=1000;i0;i=i+1) xi=xi+s;,21,循环体间相关常常以重现的形式出现的： for (i=2;1=100;i=i+1) Yi=Yi-1+Yi;,重现是对一个变量赋予前面一个循环体中一个变量的值，而且往往是最近的一个循环体中的变量,22,检测这种循环依赖关系有两点很重要的原因：一是有些系统结构（如向量计算机）可以专门支持执行这种循环结构的程序；二是有些存在循环依赖关系的程序也可以获得很高的并行度。,for (i=6;1=100;i=i+1) Yi=Yi-5+Yi;,在第i次循环中，循环引用了第i-5个元素，因此称该循环的相关距离是5。许多有相邻体间相关的循环，它们的相关距离是1。相关距离越大，通过展开循环可以获得的并行度就越高。,23,循环展开技术是利用多次复制循环体并相应调整展开后的指令和循环结束条件，增加有效操作时间与控制操作时间的比率。 这种技术也给编译器进行指令调度带来了更大的空间,2.循环展开技术,例4-2：将例4-1中的循环展开成3次得到4个循环体，再对展开后的指令序列在不调度和调度两种情况下，分析代码的性能。,24,解：假定R1的初值为32的倍数，即循环次数为4的倍数。 寄存器分配如下： （展开后的循环体内不重复使用寄存器。） F0、F4：用于展开后的第1个循环体； F2：保存常数； F6和F8：用于展开后的第2个循环体； F10和F12：用于第3个循环体； F14和F16：用于第4个循环体。,25,(1) 展开后没有调度的代码,流出时钟 Loop: LD F0,0(R1) 1 （空转） 2 ADDD F4,F0,F2 3 （空转） 4 （空转） 5 SD 0(R1),F4 6 LD F6,-8(R1) 7 （空转） 8 ADDD F8,F6,F2 9 （空转） 10 （空转） 11 SD -8(R1),F8 12 LD F10,-16(R1) 13 （空转） 14,流出时钟 ADDD F12,F10,F2 15 （空转） 16 （空转） 17 SD -16(R1),F12 18 LD F14,-24(R1) 19 （空转） 20 ADDD F16,F14,F2 21 （空转） 22 （空转） 23 SD -24(R1),F16 24 SUBI R1,R1,#32 25 （空转） 26 BNEZ R1,Loop 27 （空转） 28,26,结果分析:,这个循环每遍共使用了28个时钟周期 有4个循环体，完成4个元素的操作 平均每个元素使用28/4=7个时钟周期 原始循环的每个元素需要10个时钟周期 节省的时间:从减少循环控制的开销中获得的 在整个展开后的循环中，实际指令只有14条，其它13个周期都是空转。 效率并不高,27,(2) 对指令序列进行优化调度,指令流出时钟 Loop: LD F0,0(R1) 1 LD F6,-8(R1) 2 LD F10,-16(R1) 3 LD F14,-24(R1) 4 ADDD F4,F0,F2 5 ADDD F8,F6,F2 6 ADDD F12,F10,F2 7 ADDD F16,F14,F2 8 SD 0(R1),F4 9 SD -8(R1),F8 10 SUBI R1,R1,#32 12 SD 16(R1),F12 11 BNEZ R1,Loop 13 SD 8(R1),F16 14,28,结果分析：,没有数据相关引起的空转等待 整个循环仅仅使用了14个时钟周期 平均每个元素的操作使用14/4=3.5个时钟周期 循环展开和指令调度可以有效地提高循环级并行性。 这种循环级并行性的提高实际是通过实现指令级并行来达到的。 可以使用编译器来完成，也可以通过硬件来完成。,29,循环展开和指令调度时要注意的问题,(1) 保证正确性 (2) 注意有效性 (3) 使用不同的寄存器 (4) 尽可能减少循环控制中的测试指令和分支指令 (5) 注意对存储器数据的相关性分析 (6) 注意新的相关性,30,3.全局指令调度,全局指令调度是在保证不违背数据相关和控制相关的情况下，把代码尽可能压缩成几条指令。,循环分支指令引起的控制相关可以通过展开解决。 全局指令调度可以解决另一类由条件分支引起的控制相关。 全局指令调度并不保证能提高执行速度，但如果预测信息准确，编译器就可以进一步决定上述移动会不会提高运行速度。,31,4.2 指令的动态调度,静态调度 依靠编译器对代码进行静态调度，以减少相关和冲突。 它不是在程序执行的过程中、而是在编译期间进行代码调度和优化。 通过把相关的指令拉开距离来减少可能产生的停顿。 动态调度 在程序的执行过程中，依靠专门硬件对代码进行调度，减少数据相关导致的停顿。,32,4.2.1动态调度的原理,到目前为止我们所使用流水线的最大的局限性: 指令必须顺序流出 看下面一段代码： DIVD F0 , F2 , F4 ; S1 ADDD F10 , F0 , F8 ; S2：S2对S1数据相关, S2被阻塞 SUBD F12 , F8 ,F14 ;S3：S3与S1、S2都没 有相关,但也被阻塞,33,为了允许乱序执行，我们将基本流水线的译码阶段 再分为两个阶段： (1)流出（Issue，IS）：指令译码，检查是否存 在结构阻塞。 (2)读操作数（Read Operands，RO）：当没有数 据相关引发的阻塞时就读操作数。 指令乱序结束带来的最大问题: 异常处理比较复杂 (精确异常处理、不精确异常处理),34,4.2.2计分牌动态调度算法,例4-3：数据先读后写（WAR）相关引起的阻塞 代码序列： DIVD F0 , F2 , F4 ADDD F10 , F0 , F8 SUBD F8 , F8 , F14 指令乱序执行时就会出现先读后写相关。,记分牌技术的目标： 在资源充足时，尽可能早地执行没有数据阻 塞的指令，达到每个时钟周期执行一条指令。,35,要发挥指令乱序执行的好处，必须有多条指令 同时处于执行阶段，这就要求有多个功能部件 或功能部件流水化或者两者兼有。 假设：处理器采用多个功能部件。 CDC 6600具有16个功能部件： 4个浮点部件， 5个存储器访问部件 7个整数操作部件 在DLX中，假设有2个乘法器、1个加法器、1 个除法部件和1个整数部件。,36,1.采用记分牌技术的DLX处理器的基本结构。,记分牌电路负责记录资源的使用，并负责相关检测，控制指令的流出和执行。,37,2.每条指令在流水线中的执行过程分为四段： (1) 流出（Issue，记为IS） 如果本指令所需的功能部件有空闲，并 且其它正在执行的指令使用的目的寄存器与 本指令的不同，记分牌就向功能部件流出本 指令，并修改记分牌内部的数据记录。 解决了指令间存在的结构相关和先写后写相关。,38,(2) 读操作数（Read Operand，记为RO）。 记分牌需要监测源操作数寄存器中数据的 有效性，如果前面已流出的还在运行的指令不 对本指令的源操作数寄存器进行写操作，或者 一个正在工作的功能部件已经完成了对这个寄 存器的写操作，那么此操作数有效。当操作数 有效后，记分牌将启动本指令的功能部件读操 作数并开始执行。 解决了数据的先写后读（RAW）相关。 通过以上步骤，记分牌动态解决了结构相 和数据相关引发的阻塞，指令可能乱序流出。,39,(3) 执行（Execution，记为EX）。 (4) 写结果（Write Result，记为WR）。 记分牌知道指令执行完毕后，如果目标 寄存器空闲，就将结果写入到目标寄存器中， 然后释放本指令使用的所有资源。 检测先读后写（WAR）相关 在出现以下的情况时，就不允许指令写结果:,前面的某条指令（按顺序流出）还没有读取操作数； 其中某个源操作数寄存器与本指令的目的寄存器相同。,40,3. 记分牌需要纪录的信息分为三部分： (1) 指令状态表 记录正在执行的各条指令已经进入记 分牌DLX流水线四段中的哪一段。,(2) 功能部件状态表 纪录各个功能部件的状态。每个功能部件 在状态表中都由以下九个域来纪录： Busy： 指示功能部件是否在工作 Op： 功能部件当前执行的操作 Fi： 目的寄存器编号 Fj，Fk：源寄存器编号 Qj，Qk：向Rj，Rk中写结果的功能部件 Rj，Rk：表示Fj，Fk是否就绪，是否已经被使用,41,（3）结果寄存器状态表 每个寄存器在表中有一个域，用于纪录写入本寄存器的功能部件（编号）。如果当前正在运行的功能部件没有需要写入本寄存器的，则相应域置为空。,例4-4给出一段代码如下所示，请写出其代码运行过程中记分牌保存的信息。 LD F6 , 34(R2) LD F2 , 45(R3) MULT.D F0 , F2 , F4 SUB.D F8 , F6 , F2 DIV.D F10 , F0 , F6 ADD.D F6 , F8 , F2,42,指 令,指令状态表 IS RO EX WR,LD F6 , 34(R2) LD F2 , 45(R3) MULTD F0 , F2 , F4 SUBD F8 , F6 , F2 DIVD F10 , F0 , F6 ADDD F6 , F8 , F2,DLX记分牌信息组成和记录的信息,43,部件名称,功能部件状态表 Busy Op Fi Fj Fk Qj Qk Rj Rk,整数 yes LD F2 R3 no 乘法1 yes MULTD F0 F2 F4 整数 no yes 乘法2 no 加法 yes SUBD F8 F6 F2 整数 yes no 除法 yes DIVD F10 F0 F6 乘法1 no yes,44,4.2.3 Tomasulo动态调度算法,1.基本思想,Tomasulo算法将记分牌的关键部分和寄存器换名 技术结合在一起。,只要操作数有效，就将其取到保留站，避免 指令流出时才到寄存器中取数据。 指令的执行结果直接送到等待数据的其它保 留站中去。 一条指令流出时，存放操作数的寄存器名被 换成为对应于该寄存器保留站的名称。,45,(1).采用Tomasulo算法的DLX浮点部件的基本结构,46,保留站中保存已流出并等待到本功能部件执行的 操作（指令）的数据；还保存指令执行所需的控制信息。,如果该操作的源操作数在寄存器中已经就绪， 刚将该操作数取来，保存到保留站中； 如果操作数还没有计算出来，则保留站中记 录这个操作数将由谁计算出来，即指明它由 哪个功能部件产生。,取缓冲和存缓冲保存的是读/写存储器的数据或 地址。,47,浮点寄存器通过一对操作数总线连到功能部件， 通过其中一条总线连到公共数据总线，再送到 存缓冲。 功能部件的计算结果和从存储器读取的数据都送 到公用数据总线上，除了取缓冲的输入和存缓冲 的输出以外，所有部分均与公用数据总线相连。 两个运算功能部件,浮点乘法器完成乘法和除法操作 浮点加法器完成加法和减法操作,48,（2）.指令流水线的分段情况 使用Tomasulo算法的流水线需三段： (1) 流出（Issue）：从浮点操作队列中取一条指令。 (2) 执行（Execute） (3) 写结果（Write Result）,49,4.3转移预测技术,4.3.1静态转移预测,静态分支预测有时用于分支行为在编译时就可以比较精确地预测的处理器中，也可以用来协助动态分支预测器进行分支预测。,一种支持静态分支预测的系统结构特性叫分支延迟，分支延迟会引起流水线冲突，而编译器可以在编译时减小由此冲突带来的损失。 分支预测的效率取决于是否能够正确地猜测出分支的方向。在编译时对分支准确预测也有助于对数据冲突的调度。循环展开和条件分支就是这样的例子。,50,例4-8:有下面的程序段： LD R1,O(R2) 相关需一个停顿 DSUBU R1,R1,R3 BEQZ R1,L 非0跳转 OR R4,R5,R6 DADDU R10,R4,R3 L: DADDU R7,R8,R9 总会执行，可移至第一条指令后,编译时静态地进行分支预测,51,静态预测有多种方法：,最简单的方法是预测分支总是被选中。,另一种稍好的方法是根据分支的方向来预测分支是否命中，向后转移的分支预测为选中，向前转移的分支预测为不选中。,一个更精确的技术是基于以前运行时得到的配置文件信息。,52,4.3.2动态转移预测,动态分支预测技术能够根据近期转移是否成功的历史记录来预测下一次转移的方向。它能够随程序的执行过程动态地改变转移的预测方向。,动态转移预测技术的关键是要解决好两个问题：,一是如何记录转移历史信息 另一个是根据历史信息进行预测,53,记录转移历史信息的方法通常有三种：,1.转移预测缓存 记录最近几次转移的结果,2.分支目标缓冲 缓存转移目标指令的地址,3.基于硬件的前瞻执行 用Cache缓存转移地址的后继指令,54,在指令Cache中专门设置一个字段，称为“转移历史表”。,1.转移预测缓存,在执行转移指令时，把转移成功或不成功的信息记录在这个“转移历史表”中。,带有箭头的线表示状态转换的方向，线旁边的T表示指令实际执行结果为转移成功，而N表示指令实际执行结果为转移不成功。,只记录一次历史转移信息状态转化图,55,记录两次历史转移信息状态转化图,TT：两次转移都成功；NT：最近一次转移成功，再前一次转移不成功；TN：最近一次转移不成功，再前一次转移成功；NN：最近两次转移都不成功；t：本次预测转移成功；n:本次预测转移不成功；T：本次实际转移成功；N：本次实际转移不成功,56,2.分支目标缓冲,转移成功的分支指令地址和它的分支目标地址都放到一个缓冲区中保存起来，缓冲区以分支指令的地址作为标示；取指令阶段，所有指令地址都与保存的标示作比较，一旦相同，我们就认为本指令是分支指令，且认为它转移成功，并且它的分支目标(下一条指令)地址就是保存在缓冲区中的分支目标地址。这个缓冲区就是分支目标缓冲区(Branch-TargetBuffer，BTB，或者Branch-TargetCache，BTC)。,57,BTB的结构如图所示,用专门的硬件实现的一张表格。表格中的每一项至少有两个字段： （1）执行过的成功分支指令； （2）预测的分支目标地址。,58,由于BTB中存储的是执行过的成功分支指令的地址，所以如果当前指令的地址与BTB中的第一个字段匹配，那么就将该匹配项中第二个字段中的地址送给PC寄存器，从分支目标处开始取指令。,如果预测正确，则不会有任何分支延迟。如果预测错误或者在BTB中没有匹配的项，则会有至少两个时钟周期的开销。这是因为这时需要更新BTB中的项，这要花费一个时钟周期。,59,采用BTB技术时指令在各种情况下的延迟,60,BTB的另一种形式是在分支目标缓冲器中存储一条或则多条分支目标地址处的指令。,有的实现方案还保留了分支目标地址，有的则将之去掉了,这种方案有3个潜在的优点：,（1）更快地获得分支目标处的指令；,（2）可以一次提供分支目标处的多条指令，这对于多流出处理器是很有必要的；,（3）便于进行分支折叠优化。该优化可以用来实现零延迟无条件分支，甚至有时还可以做到零延迟条件分支。,61,3.基于硬件的前瞻执行,基于硬件的前瞻执行结合了以下3种思想：,（1）采用动态的分支预测技术来选择后续执行语句 （2）在控制相关消除之前指令前瞻执行。 （3）对基本块采用动态调度。,实现前瞻的关键思想是：,允许指令乱序执行，但必须顺序确认。只有确认以后的结果才是最终的结果，从而避免不可恢复的行为，如更新机器状态或执行过程发生异常。,62,4.4 多发射技术,4.4.1超标量技术,标量是相对于向量而言的，一个只有大小的量称为标量，而将既有大小又有方向的量称为向量。当然，向量中的某一个分量也是标量。 如果处理机每条指令的处理对象是一个或一对（如两个标量相加）标量，这种处理机称为标量处理机。 如果标量处理机内部存在多条指令流水线，则称为超标量处理机。,63,1单发射与多发射,处理机从指令存储单元（或指令分配单元）取得指令的过程称为“发射”。 如果一个处理机在单个时钟周期中只能取出一条指令供执行，就称为单发射处理机。 如果在一个时钟周期内可以同时取得多条指令的处理机可以称为多发射处理机。,(a) 单发射,(b)多发射,单发射与多发射工作方式比较,返回,上一张,64,（a）单发射指令流水线,65,（b）多发射指令流水线,66,在超标量处理机中同样面临着预测分析和处理指令之间的功能部件冲突、数据相关和控制相关问题。主要采用的技术有一下几种：,（1）寄存器重命名技术。,（2）先行指令窗口技术。,（3）转移预测技术。,（4）通过Tomasulo算法实现动态存储器地址的二义性消除。,（5）设置多个交叉开关，通过控制开关通路，把几个指令译码器的输出分别送到多个操作部件中去执行。,（6）要是指令流水线在一个周期内同时发射更多的指令，存储器就需要在一个周期为指令流水线提供多条指令。,67,4.4.2多发射的动态调度,1.多流水线调度,2.资源冲突,在标量处理机中，有多条指令流水线在同时工作，设置有多个能独立工作的操作部件，因此，必须解决多流水线的调度问题和操作部件的资源冲突问题。,68,1.多流水线调度,在有多条流水线同时工作时，指令的发射顺序和完成顺序对提高超标量处理机的性能非常重要。,如果指令的发射顺序是按照程序中的指令排列顺序进行的，称为顺序发射(in-order issue)，否则，称为乱序发射(outorder issue)。,如果指令的完成顺序必须按照程序中的指令排列顺序进行，称为顺序完成(in-order completion)，否则，称为乱序完成(outorder completion)。,69,通过一个具体的程序例子来介绍这三种方法。,I1: LOAD R1, A; I2: FADD R2, R1; I3: FMUL R3, R4; I4: FADD R4, R5; I5: FDEC R6; I6: FMUL R6, R7;,70,（1）顺序发射顺序完成,输入指令严格遵照编译后的机器指令次序排列，而且执行的次序也一点不作变动。 由于每次取得两条指令，当前面的指令没有执行完毕前，后进入的两条指令必须等待，直到执行部件完成前面的执行，流入写回部件为止。所以，当有资源冲突或相关发生时，将以等待来保证按序完成。,71,顺序发射顺序完成的指令流水线时空图,超标量处理机三种发射策略,72,无序完成方式在指令执行时间长短不一时往往特别有效。 无序完成调度方法可以最大限度地利用各个执行功能部件，只有当按序输入的指令中存在数据相关、过程相关或资源冲突时才不得不加入延迟。,（2）顺序发射乱序完成,73,顺序发射乱序完成指令流水线时空图,超标量处理机三种发射策略,74,（3）乱序发射乱序完成,乱序发射乱序完成的指令流水时空图,超标量处理机三种发射策略,75,2.资源冲突,下面是一个由4条指令组成的程序： FAD.D R0; FMUL R2; FAD.D R4; FMUL R6;,如果在一台每个时钟周期发射两条指令的双流水线超标量处理机上执行，有一个独立的浮点加法部件FADD和一个独立的浮点乘法部件FMUL。,假设完成一次浮点加法需要3个时钟周期，完成一次浮点乘法需要4个时钟周期。,76,若浮点加法器和浮点乘法器这两个操作部件都不采用流水线结构，则要发生资源冲突。,流水线的时空图如图4-22所示。,图4-22双流水线超标量处理机，操作部件不采用流水线的时空图,77,如果浮点加法器和浮点乘法器都采用流水线结构，每一个功能段的时间长度都相等。浮点加法器采用3段流水线，浮点乘法器需要4段流水线。在一台双流水线超标量处理机上，4条指令执行的时空图如图4-23所示。,图4-23双流水线超标量处理机，操作部件采用流水线时空图,78,比较图4-22和图4-23可以发现，在一台每个时钟周期发射m条指令的超标量处理机中，对于一个延迟时间为k个时钟周期的操作部件，如果它不采用流水线结构，则使用同一个操作部件的两条指令的序号应该至少相差mk，否则可能发生资源冲突。,如果操作部件采用是个功能段的流水线结构，则使用同一个操作部件的两条指令的序号只需要相差m或m以上，就不会发生资源冲突。,79,4.4.3超长指令字技术,超字长指令字（以下简称VLIW）结构是由水平微码和超标量处理两种技术相结合而产生的，VLIW处理机的机器指令字长度高达数百位。,VLIW处理方式的基本工作原理如图4-25所示,80,VLIW方式具有下述主要特征：,（1）依靠编译组装超长指令。,（2）硬件结构简单。,（3）需要较大的指令带宽和较大的存储空间，这是超长指令字整体传输的要求。,（4）虽然经过编译处理，但由于程序在动态执行时不可避免的转移等操作，超长指令字指令仍可能在并行执行时出现相关，导致代码空间和执行速度上的双重损失。,（5）适合于细粒度的并行处理。,（6）指令系统的非兼容性。,81,4.5 指令级并行的支持与限制,要讨论这个问题，先来看看理想的指令级并行处理器应具备什么条件，现有的先进技术能使处理器达到理想状态吗？,理想处理器是指消除了所有指令级并行约束的处理器。这些指令级并行的约束主要是结构相关、数据相关和控制相关。,要消除这些约束，理想处理器应具备：,82,（1）可供寄存器重命名的虚拟寄存器数量没有限制，因此可以避免所有的WAW和WAR冒险，并且可以有无限的指令同时开始执行。 （2）准确预测所有的条件转移和跳转转移，为此应拥有无限容量的指令缓存。 （3）准确确定所有的存储器地址，因而完全消除了存储器二义性。 （4）有最优的Cache，保证所有的访存只需1个时钟周期。,要消除这些约束，理想处理器应具备：,显然，具备上述条件的处理器具有无限发射指令的能力。当然，这种处理器是不不能出现的，也是难以接近的。,83,首先，在转移预测、重命名和相关性分析上依靠静态的编译分析是不可能完美的，更多地需要动态分析，这就要求先行将被检测指令暂存起来进行分析。,其次，即使采用目前最先进的基于Tournament的转移预测器，使用总共8K个入口、采用两级预测、约150KB的容量（约为目前预测器的4倍），检测表明，仅在循环并行度较高的情况下较接近理想处理器，而在其他情况下则相差较大。,再次，寄存器的数目是有限的。,此外，每时钟周期发射指令数量、功能单元及单元延迟、寄存器文件端口、功能单元队列、对转移发色的限制、对存储器并行访问的限制及对指令提交的限制等都是影响指令级并行的因素。,84,4.5.1 窗口大小和最大发射数目对理想处理器的限制,把为了同时执行而被检测的指令集合称做窗口。,窗口大小直接限制了特定周期内开始执行的指令数目。,图4-26与图4-27说明了限制窗口大小所造成的影响，两幅图所用的数据是相同的，区别只在于表现形式不同。,85,图4-26 减少窗口大小的影响,图4-27每个基准测试程序窗口大小对指令发射的影响,86,在合适的窗口大小下，整数程序和浮点程序可达到的并行度很接近（比如在窗口较小的情况下，浮点程序和整数程序的并行度差距并不大）。,在窗口较小的情况下，处理器也无法判断下一个循环体中的指令可否与现在的循环体中的指令同时发射。,太大的窗口容量是不切实际的，从图4-26和图4-27所示的数据也可看出，在实际的窗口大小条件下发射速率将会明显降低,87,4.5.2实际分支和分支预测的影响对理想处理器的限制,在理想处理器中，假设分支总是可以正确地预测出来，即程序中的任何一个分支均可以在其执行前被预测出来。实际上，这种情况是不会出现的。,图4.28和图4.29所示是真实的预测方案的效果，两个图的差别只是表示形式不同而已。图中的测试数据包括使用不同的分支预测方案和不使用任何预测的几种情况，假设对于跳转指令有一个单独的预测器,88,图4-28 分支预测对指令发射速度的影响,如图4-28展示的从理想的预测模型（所有的分支都被正确的预测）到各种动态预测器，到编译时和基于静态文件的预测器，最后到没有使用预测器的效果。,89,图4-29 分支预测的影像图（按应用程序排序）,90,对图4-29中所示的5种分支预测方法，说明如下：,（1）.完美型所有分支和跳转指令均可以在执行开始前被正确预测。,（2）.锦标赛分支预测器预测方案使用一个相关的两位预测器和一个不相关的两位预测器及一个选择器，选择器负责为每个分支选择合适的预测器。,（3）.带有512个两位入口的标准两位预测器除此之外，还假设使用一个有16个入口的缓冲器负责对返回指令进行预测。,（4）.静态法静态预测器使用程序的历史来预测分支被执行或不被执行。,（5）.无预测对分支指令不作预测，这时，可利用的并行性几乎都被限制在一个基本块内。,91,如图4-30所示的说明了对于基准测试程序一个子集中的条件分支，3个真实预测器的精确度。,图4-30 采用SPEC92子集测试的条件分支的预测精度,92,4.5.3有限数目寄存器的影响,图4-31和图4-32以相同数据的不同形式说明了减少重命名寄存器数目对性能的影响。,图4-31 重命名寄存器数量对指令发射的影响,93,如图4-31所示，浮点寄存器和通用寄存器的数量都沿x轴递减。从图中可以清楚的看到，尽管32个附加通用寄存器和32个附加浮点寄存器对所有的程序都有重大的影响，但是寄存器数量对浮点程序的影响最显著。,94,图4-32 每个时钟周期发射的指令条数,95,从图4-32可以清楚的看到，当可用寄存器减少时，可达到的指令并行度会大大降低。由于要使用多于64个寄存器，则需要有更多的并行性，对于整数程序，多于64个寄存器的影响没有列出，而这在整数程序中需要非常理想的分支预测。,尽管寄存器重命名对于性能的影响是显著的，但使用无限多的寄存器显然也是不切实际的,96,4.5.4 非完美别名分析造成的影响,我们的优化模型假设可以准确地分析出所有的内存相关，并消除所有的寄存器名字相关。然而，完美的别名分析在实际中是不可能的，别名分析在编译阶段不可能做得很完美。,图4-33和图4-34所示，分别给出了三种内存别名分析模型对指令级并行度的影响情况。这三种模型是：,1.全局堆栈完美分析法,2.检测法,3.无分析,97,图4-33 不同的别名分析对指令级并行度的影响,如图4-33所示，显示了不同别名分析技术对整数程序并行性的开发有巨大影响，且全局/堆栈分析法对FORTRAN程序来说是完美的，但是难以实现。,98,图4-34 不同别名分析对各个程序的影响,99,4.6 Intel Pentium 4 实例分析,4.6.1 Pentium 和Pentium4结构的简单比较,Pentium4的微系统结构被称为NetBurst，它与Pentium的结构类似(Pentium的结构被称为P6微系统结构)：都是每周期最多可以取3条IA-32指令，并将这些指令译码成相应的微操作，然后发送这些微操作到一个乱序执行引擎上，这个执行引擎每个周期最多能够执行3条微操作。 Pentium与Pentium4微系统结构的区别也很多，主要的区别是NetBurst结构可以在更高的时钟频率上工作，并且能够以接近峰值的速度持续运行。,100,以下是它们最重要的不同之处：,1.NetBurst有更深的流水线,流