我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:2019跑狗图高清彩图 > 指令级并行 >

《计算机系统结构课件》1第4章指令级并行徐洁2013计算机系统结构

归档日期:07-27       文本归类:指令级并行      文章编辑:爱尚语录

  计量、质量管理体系、质量手册、程序文件、医药、食品安全,法律法规、生活常识、销售管理、国学、论文等专业文档。知识改变世界,知识让你我成长。部分文档为本人收集整理,如有(疑似)侵权,请联系我或道客客服删除。

  内容提示:指 第四章 指令级并行及限制4.1 指令级并行的概念4.2 指令的动态调度4.3 转移预测技术1转移预测技术4.4 多发射技术4.5 指令级并行的支持与限制4.6 Intel Pentium 4 实例分析 4.1 指令级并行的概念指令级并行的概念几乎所有的处理机都利用流水线来使指令重叠并行执行,以达到提高性能的目的。这种指令之间存在的潜在并行性称为指令级并行。 (ILP:Instruction-Level Parallelism)在流水线模型机中 如果指令间无相关或者相关可以通22在流水线模型机中,如果指令间无相关或者相关可以通过专用数据通路消除,则流水线没有停顿,指令级并行得以充分发挥。但是,不能消...

  指 第四章 指令级并行及限制4.1 指令级并行的概念4.2 指令的动态调度4.3 转移预测技术1转移预测技术4.4 多发射技术4.5 指令级并行的支持与限制4.6 Intel Pentium 4 实例分析 4.1 指令级并行的概念指令级并行的概念几乎所有的处理机都利用流水线来使指令重叠并行执行,以达到提高性能的目的。这种指令之间存在的潜在并行性称为指令级并行。 (ILP:Instruction-Level Parallelism)在流水线模型机中 如果指令间无相关或者相关可以通22在流水线模型机中,如果指令间无相关或者相关可以通过专用数据通路消除,则流水线没有停顿,指令级并行得以充分发挥。但是,不能消除的相关必然会导致流水线的停顿,使流水线的利用率下降。例如,第3章介绍涉及load指令的内部前推技术时只能强制暂停流水线的执行。那是不是对此情况就只能暂停流水线的执行呢? 答案是还有其他解决方法。注意第三章所讲到的有load指令时的暂停流水线有个很重要的前提是所有指令都是顺序执行。Load的后一条指令如果跟load数据相关,必须要暂停流水线以获取正确的数据。例如: load r1, 100(r2);add r3, r1, r43add r3, r1, r4在第三章后面延迟转移的一个例子里,编译器调度一条与load无关的指令到以上两条指令之间,就可以避免暂停流水线。 本章要讨论的主要技术,就是基于第三章的技术基础上,允许打乱指令的顺序执行,尽量开发指令级并行,减少或消除由指令相关引起的流水线停顿。那么内容上与第三章的区别在哪里呢?与第三章内容的区别:第三章也是介绍指令级并行,但其主要讨论的范围是:44,但其主要讨论的范围是:1. 主要是基于一个简化的5级流水线. 模型机的所有指令顺序执行,尽管第三章最后一点内容讨论了打乱指令顺序,但只是编译器对指令次序进行了优化调度,硬件仍然是顺序执行调度后的指令序列。 第四章的内容范围:1. 并不局限于第三章给出的模型机;2. 将分别以硬件和软件实现的方式讨论如何打乱指令之间的顺序,在保证执行结果正确性基础上,提高性能。打乱指令顺序主要有两种方法:一种是在编译阶段静态的发现指令级并行,再重新排序和优化指令(静态调度);一种是在硬件执行指令时动态的发现指令级的55调度);一种是在硬件执行指令时动态的发现指令级的并行,允许指令乱序执行(动态调度)。如Intel的Pentium系列采用动态调度;Intel的Itanium(用于科学领域和特殊应用)采用静态调度。在RISC机器中,指令系统支持编译优化,其编译器一般采用静态调度方式,有的也同时采用动态调度。 4.1.1 基本概念1、流水线处理机的实际CPI 理想流水线的CPI加上各类相关停顿的时钟周期数:流水线CPI =理想CPI + 结构相关停顿+ 数据相关停顿+ 控制相关停顿 理想流水线CPI是指在程序执行过程中可达到的最大性能。 减少相关停顿也就减少了CPI,即提高了IPC(Instructions Per Cycle)。 (每个时钟周期完成的指令条数)62、基本程序块 基本程序块:一段除了入口和出口以外不包含其他分支的线性代码段。 程序平均每5~7条指令就会有一个分支。仅仅开发基本程序块内的指令级并行,其并行度是有限的。因此,更有效的方法是开发多个基本块之间的并行性。 3、循环级并行:提高指令并行最常用和简单的方法是将一个循环中的各次迭代并行执行。 例如,考虑下述语句:for (i=1; i=500; i=i+1)a[i]=a[i]+s; 由于各次循环迭代无关,因此每一次循环的迭代都 与其他任何 次循 迭代重叠执行7代都可以与其他任何一次循环迭代重叠执行。4、 最基本的开发循环级并行的技术 指令调度技术 循环展开(loop unrolling)技术 换名技术 4.1.2 循环展开调度的基本方法指令调度:通过改变指令在程序中的位置,将相关指令间的距离加大到不小于指令执行延迟的时钟周期数,这样就可以将相关指令转化为无关指令。8指令的相关距离:两条相关指令之间的指令条数。编译器在完成指令调度时,受限于两个特性:* 一是程序固有的指令级并行性;* 二是流水线功能部件的执行延迟。 设使用的浮点流水线的延迟如下表产生结果指令 使用结果指令 延迟时钟周期数浮点计算 另外的浮点计算 3浮点计算 浮点数据存操作(SD) 2浮点数据取操作(LD) 浮点计算 1浮点计算 另外的浮点计算 3浮点计算 浮点数据存操作(SD) 2浮点数据取操作(LD) 浮点计算 19浮点数据取操作(LD) 浮点数据存操作(SD) 0条件转移(分支)指令如果使用上一条指令的结果作为判断条件,需要等待(分支)指令如果使用上一条指令的结果作为判断条件,需要等待 一个 时钟周期,同时分支指令有一个时钟周期的分支延迟槽。分支指令有一个时钟周期的分支延迟槽。 例子:指令流入时钟Loop: LD F0 , 0(R1) 1(空转) 2ADDD F4 , F0 , F2 3(空转) 4(空转) 510(空转) 5SD 0(R1) , F4 6SUB R1 , R1 , #8 7(空转) 8BNEZ R1 , Loop 9(空转) 10 例4-1:下面通过一个实例对循环展开技术进行研究与分析对于下面的源代码,转换成DLX汇编语言,在不进行指令调度和进行指令调度两种情况下,分析代码一次循环的执行时间。for (i=1; i=1000; i++)11x[i] = x[i] + s;备注:本章使用的浮点流水线的延迟如前表所示 解:浮点数长度8个字节,64位双精度浮点数。(1) 变量分配寄存器整数寄存器R1: 循环计数器,初值为向量中最高端地址元素的地址。浮点寄存器F2: 保存常数S S.。假定最低端元素的地址为8。(2) 转换为DLX汇编语言后的程序12(2) 转换为DLX汇编语言后的程序Loop: LD F0,0(R1) ADDD F4,F0,F2SD 0(R1),F4SUBI R1,R1,#8BNEZ R1,Loop (3) 不进行指令调度时,根据前表给出的浮点流水线指令执行的延迟,以上程序执行的情况如下:指令流入时钟Loop: LD F0 , 0(R1) 1(空转) 2ADDD F4 , F0 , F2 3(空转) 4(空转) 513(空转) 5SD 0(R1) , F4 6SUB R1 , R1 , #8 7(空转) 8BNEZ R1 , Loop 9(空转) 10 每完成一个元素的操作需要10个时钟周期,其中5个是空转周期。 (4) 指令调度以后,程序的执行情况: SD指令放在分支指令的分支延迟槽中 对存储器地址指针计算指令进行调整指令流入时钟Loop: LD F0 , 0(R1) 1SUBI R1 , R1 , #8 2ADDD F4 , F0 , F2 3(空转) 414(空转) 4BNEZ R1 , Loop 5SD 8(R1) , F4 6 一个元素的操作时间从 10 个时钟周期减少到6 6 个5 5 个周期是有指令执行的,1个空转周期。仔细分析以上指令发现,其中的有效指令LD、ADDD和SD占用了3个时钟周期,而其余指令是为了控制循环和解决数据相关。因此,要减少循环控制开销的一种有效方法就是运用循环展开技术。 循环展开技术是利用多次复制循环体,并相应调整展开后的指令和循环结束条件,增加有效操作时间、减少控制操作时间。这种技术也给编译器进行指令调度带来了更大的空间15Loop: LD F0,0(R1) ADDD F4,F0,F2SD 0(R1),F4SUBI R1,R1,#8BNEZ R1,Loop 解:假定R1的初值为32的倍数。寄存器分配如下:(展开后的循环体内不重复使用寄存器,后面会讲到寄存器换名以优例4-2:将例4-1中的循环展开3次得到4个循环体,再对展开后的指令序列在不调度和调度两种情况下,分析代码的性能。16化调度)F0、F4:用于展开后的第1个循环体;F2:保存常数;F6和F8:用于展开后的第2个循环体;F10和F12:用于第3个循环体;F14和F16:用于第4个循环体。 (1) 展开后没有调度的代码: 展开后的循环体中去掉了SUB、BNEZ指令,因此需要调整相应指令的偏移量。流入时钟Loop: LD F0,0(R1) 1(空转) 2ADDD F4,F0,F2 3(空转) 4(空转) 5SD 0(R1),F4 6LD F6,-8(R1) 7流入时钟ADDD F12,F10,F2 15(空转) 16 (空转) 17SD -16(R1),F12 18LD F14,-24(R1) 19(空转) 20ADDD F16,F14,F2 2117(空转) 8ADDD F8,F6,F2 9(空转) 10(空转) 11SD -8(R1),F8 12LD F10,-16(R1) 13(空转) 14, ,(空转) 22(空转) 23SD -24(R1),F16 24SUBI R1,R1,#32 25(空转) 26BNEZ R1,Loop 27(空转) 28 结果分析: 这个循环每遍共使用了28个时钟周期 有4个循环体,完成4个元素的操作平均每个元素使用28/4=7个时钟周期每18 原始循环的每个元素需要10个时钟周期节省的时间:从减少循环控制的开销中获得的 在整个展开后的循环中,实际指令只有14条,其它13个周期都是空转。效率并不高 (2) 对指令序列进行优化调度指令流入时钟Loop: LD F0,0(R1) 1LD F6,-8(R1) 2LD F10,-16(R1) 3LD F14,-24(R1) 4ADDD F4,F0,F2 5ADDD F8 F6 F2 619ADDD F8,F6,F2 6ADDD F12,F10,F2 7ADDD F16,F14,F2 8SD 0(R1),F4 9SD -8(R1),F8 10SUBI R1,R1,#32 12SD 16(R1),F12 11BNEZ R1,Loop 13SD 8(R1),F16 14 结果分析: 没有数据相关引起的空转等待 整个循环仅仅使用了14个时钟周期 平均每个元素的操作使用14/4=3.5个时钟周期 循环展开和指令调度可以有效地提高循环级并20 循环展开和指令调度可以有效地提高循环级并行性。 这种循环级并行性的提高实际是通过实现指令级并行来达到的。 循环展开和指令调度时要注意的问题(1) 保证正确性(2) 注意有效性(3) 采用(1) 保证正确性(2) 注意有效性(3) 采用 寄存器换名(4) 尽可能 减少循环控制 中的 测试指令 和 分支指令21(5) 注意对存储器数据的 相关性分析(6) 注意 新的相关性 虚拟的处理器:DLX处理器(读作Deluxe) 。该处理器是Patterson和Anderson在其Computer Architectrue:A Quantitive Approach”一书中提出的。该处理器反映了新一代处理器的特点。DLX是一组在设计思想上与它相似的实验和商用处理器22DLX是 组在设计思想上与它相似的实验和商用处理器的代表。这些机器包括AMD29K,DECstation 3100,HP 850,IBM 801,Intel i860,MIPS M/120A,MIPS M/1000,Motorala 88K,RISC I,SGI 4D/60,SPARCstation-1,Sun-4/110,Sun-4/260等。 DLX的指令集结构具有下面的特征:(1)使用load/store结构。(2)运算指令只能访问寄存器。(3)支持寻址方式:变址、立即(8~16位)、寄存器寻址。(4)支持简单的指令系统,包括:load,store,加,减,寄存器到寄存器,转移,与,移位,测试相等,测试不等,分支,跳转,调用,返回。(5)支持的数据类型:8位、16位和32位整型,64位IEEE75423(5)支持的数据类型:8位、16位和32位整型,64位IEEE754浮点数。(6)侧重处理器性能时使用固定指令编码;侧重代码大小时使用可变长指令编码。(7)提供至少16个通用寄存器和单独的浮点寄存器,确保所有的寻址模式都可应用于所有的数据转移指令,并形成最简指令集。 DLX有32个32位的通用寄存器(GPR),名称为R0,R1,,R31。还有一套浮点寄存器(FPR),它既可用作32个32位单精度寄存器也可用作16个双精度64位寄存器。这些64位的双精度浮点寄存器被命名为F0 F2 F28 F30 指令系统提供了24浮点寄存器被命名为F0,F2,,F28,F30。指令系统提供了单精度和双精度的浮点操作。 4.1.3 相关性分析研究指令代码的相关性,可以明确代码固有的并行性和可以获得的并行性,有助于指令的调度。但是相关是否导致流水线的空转,还与流水线的组织与结构有关。怎样处理相关与流水线之间的关系,是开发指令级并行的关键25关键。程序中的相关主要有3种:数据相关、名相关、控制相关 1 、数据相关分析如果下面的条件之一成立,则指令j 与指令i 数据相关: (1 )指令j 使用指令i 产生的结果 (2 )指令j 与指令k 数据相关,指令k 与指令i数据相关,则指令数据相关,则指令j 与指令i 数据相关。数据相关(先写后读相关)是导致流水线要保证数据相关指令之间的执行顺序关系,在硬件上如果检测到指令与前面指令间有数据相关,就暂停本指令的执行,插入空操作周期,一直到前面执行指令的结果可以使用为止。这个过程也称为互锁机制。 这个功能也可以使用编译器通过指令调度完成:编译器在相关处插入足够数量的空操作指令(如果有其他非相关指令则可用来替代空操作指令),保证当前指令不会错误地使用一个尚未产生的结果。此时,编译器必须精确了解处理器的结构与这个功能也可以使用编译器通过指令调度完成:编译器在相关处插入足够数量的空操作指令(如果有其他非相关指令则可用来替代空操作指令),保证当前指令不会错误地使用一个尚未产生的结果。此时,编译器必须精确了解处理器的结构与指令执行的过程 否则编译结果是不能正确工作的27指令执行的过程 , 否则编译结果是不能正确工作的 。 指令的相关距离:两条相关指令之间的指令条数。分析数据相关的主要工作包括:(1)确定指令的相关性,找到所有可能产生停顿的地方。(2)确定必须严格遵守的数据的计算顺序。(3)确定指令的最大相关距离,确定程序中可能的最大并行性28。以上因素决定了程序中到底有多少指令级并行性,是否可以获得这些并行性。想要消除一个确实的数据相关引起的停顿,需要对程序的结构进行分析,通常由编译器完成这个分析过程,也可以在程序执行时由硬件分析。 需要注意的一个问题是判断数据相关时面对的对象:寄存器和存储器。当数据相关发生在寄存器之间时,编译器较容易判断,因为寄存器是按统一规则被唯一命名的,不存在二义性。而对于存储器中的数据相关性判断要困难得多,如10(R1)与20(R2)表示相同地址。又如程序执行时的有效地址会随着执行变化 20(R4)与20(R4)可能是不同的 因此 存储器29执行变化,20(R4)与20(R4)可能是不同的。因此,存储器数据相关性检测会更复杂,通常用硬件判断。解决数据相关的一般方式:* 暂停流水线(互锁机制);* 使用相关专用数据通路;* 编译优化调度(静态调度);* 动态调度。 2 、名相关指令使用的寄存器或存储器称为名。如果两条指令使用相同的名,但它们之间没有数据流,则称之为指令使用的寄存器或存储器称为名。如果两条指令使用相同的名,但它们之间没有数据流,则称之为 名相关 。指令j 与指令i之间名相关有以下两种:(之间名相关有以下两种:(1 ) 反相关 :指令i 先执行,指令j 写的名是指令i读的名。反相关指令间的顺序是必须保证的。反相关就是读的名。反相关指令间的顺序是必须保证的。反相关就是 先读后写相关。(相关。(2 ) 输出相关 :指令j 和指令i 写相同的名。输出相关指令的执行30j顺序是不能颠倒的。输出相关就是 写后写相关 。例如:反相关 ( 先读后写)ADD R1, R2, R3LD R2, 10 ( R4)例如:输出相关( 写后写相关)SUB R1, R2, R3OR R1, R4, 100 与数据相关比较, 名相关 的指令间 没有数据传送,在不需要调度指令顺序时,程序执行的正确性可以保证。但是,如果要通过调度改变指令顺序时,就必须消除名相关。由于一条指令中的名改变了,并不影响名相关的另外一条在不需要调度指令顺序时,程序执行的正确性可以保证。但是,如果要通过调度改变指令顺序时,就必须消除名相关。由于一条指令中的名改变了,并不影响名相关的另外一条指令的执行 ,因此, 可 以通过 改变指令中操作数的名字来消除31指令的执行 可 改变指令中操作数的名字来消除名相关,这就是 换名技术。对寄存器操作数进行换名称为寄存器换名。这个过程可以用编译器静态完成,也可以用硬件动态完成。。对寄存器操作数进行换名称为寄存器换名。这个过程可以用编译器静态完成,也可以用硬件动态完成。 (1) 首先,仅仅去除4遍循环体中的分支指令,得到以下由17条指令构成的指令序列,如下所示:Loop: LD F0 , 0(R1)ADDD F4 , F0 , F2SD 0(R1) , F4SUBI R1 , R1 , #8LD F0 , 0(R1)ADDD F4 F0 F2借助例4-2 ,对其编译过程进行分析,仔细考察换名过程。32ADDD F4 , F0 , F2SD 0(R1) , F4SUBI R1 , R1 , #8LD F0 , 0(R1)ADDD F4 , F0 , F2 SD 0(R1) , F4SUBI R1 , R1 , #8LD F0 , 0(R1)ADDD F4 , F0 , F2SD 0(R1) , F4SUBI R1 , R1 , #8BNEZ R1 , Loop (2) 编译器可以通过对相关链上存储器访问偏移量的直接调整,将前3条SUBI指令消除掉,从而得到下面一个14条指令构成的指令序列,如下所示:Loop: LD F0 , 0(R1)ADDD F4 , F0 , F2SD 0(R1) , F4LD F0 , -8(R1)ADDD F4 , F0 , F233, ,SD -8(R1) , F4LD F0 , -16(R1)ADDD F4 , F0 , F2SD -16(R1) , F4LD F0 , -24(R1)ADDD F4 , F0 , F2SD -24(R1) , F4SUBI R1 , R1 , #32BNEZ R1 , Loop (3) 通过寄存器换名,消除名相关。F0、F4:用于展开后的第1个循环体;F2:保存常数;F6和F8:用于展开后的第2个循环体;F10和F12:用于第3个循环体;F14和F16:用于第4个循环体。Loop: LD F0 , 0(R1)ADDD F4 , F0 , F2SD 0(R1) , F4LD F6 -8(R1)34LD F6 , -8(R1)ADDD F8 , F6 , F2SD -8(R1) , F8LD F10 , -16(R1)ADDD F12 , F10 , F2SD -16(R1) , F12LD F14 , -24(R1)ADDD F16 , F14 , F2SD -24(R1) , F16SUBI R1 , R1 , #32BNE R1 , Loop 换名后,才能跨循环遍次对指令序列进行优化调度指令流入时钟Loop: LD F0,0(R1) 1LD F6,-8(R1) 2LD F10,-16(R1) 3LD F14,-24(R1) 4ADDD F4,F0,F2 5ADDD F8 F6 F2 635ADDD F8,F6,F2 6ADDD F12,F10,F2 7ADDD F16,F14,F2 8SD 0(R1),F4 9SD -8(R1),F8 10SUBI R1,R1,#32 12SD 16(R1),F12 11BNEZ R1,Loop 13SD 8(R1),F16 14 3、控制相关分析 再来看一个控制相关的例子。典型的程序结构是“if-then”结构。 。if p1 then{S1;}S;if p2 then{36S2;};实际上,if语句编译后都转换成了分支指令。S1与p1控制相关,S2与p2控制相关;S与p1、p2无关。 控制相关会带来两方面的限制:(1)与控制相关的语句或指令不能移到分支语句或指令之前执行。例如ifthen语句中,then后面的语句不能移到if之前执行。(2)与控制无关的语句或指令不能移到该分支语句或指令之37后,从而受这个分支控制。例如ifthen语句中,if前的语句不能移到then后面部分执行。 再考察例4-1,假设循环展开时,循环控制分支指令没有去除,则指令序列如下所示:Loop : LD F0 , 0(R1)ADDD F4 , F0 , F2SD 0(R1) , F4SUBI R1 , R1 , #8BEQZ R1 , ExitLD F0 , 0(R1)DD F4 , F0 , F2SD 0(R1) , F4SUBI R1 , R1 , #8BEQZ R1 , Exit38BEQZ R1 , ExitLD F0 , 0(R1)ADDD F4 , F0 , F2SD 0(R1) , F4SUBI R1 , R1 , #8BEQZ R1 , ExitLD F0 , 0(R1)ADDD F4 , F0 , F2SD 0(R1) , F4SUBI R1 , R1 , #8BNEZ R1 , LoopExit : 由于上述指令段中BEQZ R1 , Exit,BEQZ R1 , Exit,BEQZ R1 , Exit三条分支指令的存在,引起控制相关,导致其后的4条指令不能跨越分支指令进行调度,即不同循环遍次里的指令不能够跨越循环遍次进行调度。在去除这三条指令后 就消除了程序中的控制相关 从而39在去除这三条指令后,就消除了程序中的控制相关,从而才有可能在不同循环遍次之间进行全局调度,以有效提高程序在流水线 指令的动态调度在第三章的模型机中,如果流水线的指令在ID级检测到没有相关,或者与前面指令有数据相关但可以通过相关专用通路消除相关(相关隐藏),则指令就可以正常流出。如果相关不能隐藏,硬件就会从使用结果的指令开始,暂停流水线,直到相关消除,这时流水线为了减少或消除停顿,首先需要编译器确定程序中存在的相关指令,然后进行指令调度和优化,这个过程称为静态调度。(静态调度在20世纪60年代有并行机时出现,在其后的阵列机、向量机、RISC早期深入研究和广泛应用,后面讨论的VLIW处理器中几乎完全依靠静态调度提高指令级并行) 静态调度 依靠编译器对代码进行静态调度,以减少相关和冲突。 它不是在程序执行的过程中、而是在编译期间进行代码调度和优化。 通过把相关的指令拉开距离来减少可能产生的停顿。 动态调度(乱序执行)41 动态调度(乱序执行) 在程序的执行过程中,依靠专门硬件重新安排指令的执行顺序,来调整相关指令实际执行时的关系,减少数据相关导致的停顿。可以处理编译时未发现的相关如存储器数据相关。动态调度不能完全消除数据相关,但它能在出现数据相关时尽量避免处理机停顿。 4.2.1 动态调度的原理到目前为止我们所使用流水线的最大的 局限性: :指令是顺序流出顺序执行看下面一段代码:42: S1: DIVD F0 , F2 , F4 ;: S2: ADDD F10 , F0 , F8 ; S2对S1数据相关, S2被阻塞S3:S2对S1数据相关, S2被阻塞S3: SUBD F12 , F8 ,F14; ; S3与S1、S2都没有相关,但也被阻塞 指令乱序执行可能引起名相关,即先读后写、写后写相关。例4-3:先读后写(WAR)相关代码序列:DIVD F0 , F2 , F4ADDD F10 , F0 , F843SUBD F8 , F8 , F14例:写后写相关ADDD F2 , F0 , F6SUBD F2 , F4 , F8SD 10(R1) , F2因此,在乱序调度算法中,既要保证先写后读(数据相关)执行顺序,也要保证名相关指令的正确执行。 回忆顺序执行的模型机中的ID段检测数据相关,例如检测到有load相关,模型机会暂停即阻塞该指令一个时钟周期,等待load指令读数据到D。如果允许乱序执行,就不能因为数据相关阻塞指令(否则其后的指令就发射不出去) 因此需要将顺序执行44(否则其后的指令就发射不出去),因此需要将顺序执行的ID级再细分为两个流水线个段不检测数据相关(这样才能尽可能快地发射出多条指令到对应的功能部件);在第2个段才检测数据相关。显然,为了支持多条指令同时执行,需要有多个执行部件。 在记分牌算法中,设指令预取到指令队列中,乱序执行需要将基本流水线的译码阶段再分为两个阶段:(1)流出(发射Issue,IS):指令译码,检查是否存在结构相关(还有写后写相关),没有本指令就流出到对应功能部件。(2)读操作数(Read Operands,RO):检查数据相关,当没有数据相关引发的阻塞时就读操作数。读到操作数就进45没有数据相关引发的阻塞时就读操作数。读到操作数就进入到执行段。IS之前是IF段,RO之后是EXE段。 由于不同指令的执行时间不同,可能会引起指令乱序结束,随之带来的最大问题是:由于不同指令的执行时间不同,可能会引起指令乱序结束,随之带来的最大问题是:异常处理比较复杂:(精确异常处理如模型机的异常处理、不精确异常处理)对于乱序执行及结束的动态流水线精确的,因为出现异常的指令其后的指令可能先执行完。出现异常后,难以恢复现场。其后的指令可能先执行完。出现异常后,难以恢复现场。 4.2.2 计分牌动态调度算法 记分牌技术的目标:处理机在 没有结构相关 时,尽可能早地执行没有数据相关的指令, 以保持每个时钟周期由流47水线完成一条指令的速率。即,当某条将要执行的指令被停顿时,其他没有相关于任何正在执行的指令或停顿的指令的指令,能够继续发射、执行下去。水线完成一条指令的速率。即,当某条将要执行的指令被停顿时,其他没有相关于任何正在执行的指令或停顿的指令的指令,能够继续发射、执行下去。  指令乱序执行,需要多条指令同时处于执行阶段,这就要求有多个功能部件或功能部件流水化或者两者兼有。 处理器采用多个功能部件。如,CDC 6600具有16个功能部件(采用记分牌):4个浮点部件5个存储器访问部件485个存储器访问部件7个整数操作部件下面,在DLX中,记分牌技术主要用于浮点部件(其延迟大,乱序执行可有效提高性能)。假设有2个浮点乘法器、1个浮点加法器、1个浮点除法部件和1个整数部件。 1、采用记分牌技术的DLX处理器的基本结构 寄 存 器 ● ● ● ● ● 浮 点 除 法 浮 点 乘 法 浮 点 乘 法 数 据 总 线 整 数 部 件 记 分 牌 控 制 /状 态 控 制 /状 态浮 点 加 法 记分牌电路负责记录资源的使用,并负责相关检测,控制指令的流出和执行。 2.每条指令在流水线中的执行过程分为四段(设有指令预取部件,因此设指令已经在指令队列中):(1) 流出(发射Issue,记为IS)判断:如果本指令所需的功能部件有空闲;并且本指令使用的目的寄存器与其它正在执行或停顿的指令的不同,就进行操作。50(判结构相关、写后写相关)操作:记分牌就向功能部件发射本指令,并修改记分牌内部的数据记录。 (2) 读操作数(Read Operand,记为RO)判断:如果本指令的源操作数寄存器与前面指令无关,或者一个正在工作的功能部件已经完成了对源寄存器的写操作,那么此操作数有效。(判数据相关,即先写后读(RAW)相关)操作:当操作数有效后,记分牌将启动本指令的功51能部件读操作数。通过以上IS、RO二个步骤,记分牌动态检测到结构相关、写后写相关、数据相关,并暂时阻塞相关指令用延迟解决相关问题。。 (3) 执行(Execution,记为EX)取到操作数后就可以由功能部件执行指令,允许多条指令同时且乱序执行,不同功能部件需要的时钟周期不同。(4) 写结果(Write Result,记为WR)判断:如果本指令的目的寄存器与前面的某条指令的一个源操作数寄存器不同,或者相同但是前面指令52的 个源操作数寄存器不同,或者相同但是前面指令已经读取了操作数,就可以操作。(检测先读后写(WAR)相关)操作:如果没有先读后写相关,目标寄存器空闲,就将结果写入到目标寄存器中,然后释放本指令使用的所有资源。以上过程表明,指令在IS段按序流出,从RO段开始乱序执行。 3. 记分牌需要纪录的信息分为三部分:(1) 指令状态表记录正在执行的各条指令已经经过或进入记分牌DLX流水线) 功能部件状态表纪录各个功能部件的状态。每个功能部件在状态表中都由以下九个域来纪录:53Busy: 指示功能部件是否在工作Op: 功能部件当前执行的操作Fi: 目的寄存器编号Fj,Fk:源寄存器编号Qj,Qk: 有数据相关时,记录向Fj,Fk中写结果的功能部件Rj,Rk:表示Fj,Fk是否就绪(IS段);是否已经被使用过(RO、EXE、WR段) (3)结果寄存器状态表每个寄存器在表中有一个域,用于纪录写入本目的寄存器的功能部件(编号)。如果当前正在运行的功能部件没有需要写入本寄存器结果的,则相应域置为空。例4-4 后面的三个表给出下列代码运行过程中记分牌保存的信息。54LD F6 , 34(R2)LD F2 , 45(R3)MULTD F0 , F2 , F4SUBD F8 , F6 , F2DIVD F10 , F0 , F6ADDD F6 , F8 , F2 采用记分牌技术的DLX处理器的基本结构 寄 存 器 ● ● ● ● ● 浮 点 除 法 浮 点 乘 法 浮 点 乘 法 数 据 总 线 整 数 部 件 记 分 牌 控 制 /状 态 控 制 /状 态浮 点 加 法 记分牌电路负责记录资源的使用,并负责相关检测,控制指令的流出和执行。 DLX记分牌信息组成和记录的信息指 令指令状态表IS RO EX WRLD F6 , 34(R2) LD F2 , 45(R3) 56, ( )MULTD F0 , F2 , F4 SUBD F8 , F6 , F2 DIVD F10 , F0 , F6 ADDD F6 , F8 , F2结构相关 部件名称功能部件状态表Busy Op Fi Fj Fk Qj Qk Rj Rk整数 yes LD F2 R3 no乘法1 yes MULTDR3 no乘法1 yes MULTD F0 2 F2 4 F4 整数 no yes乘法2 noyes乘法2 no加法 SUBD F F8 8 F F6 6 F F2 2 整数已读走数据(EX )未就绪( IS )57加法 s yes SUBD F F8 8 F F6 6 F F2 2 数 整数 yes no除法 yes DIVD F10 0 F0 6 F6 乘法1 1 no yes结果寄存器状态表F0 F2 F4 F6 F8 F10 F30部件名称F30部件名称 乘法 1 整数 加法 除法 例4-5 假设浮点流水线中执行的延迟如下:加法需2个时钟周期乘法需10个时钟周期除法需40个时钟周期代码段和记分牌信息的起始点状态跟例4-4一样。分别给出MULTD和DIVD准备写结果之前的记分牌状态。58解: 在分析记分牌状态之前,首先需要分析指令之间存在的相关性,因为相关性会影响指令进入记分牌DLX流水线) 第二条LD指令 到 MULD和SUBD、MULTD到DIVD之间以及 SUBD到ADDD之间 存在着 先写后读相关;(2) DIVD和ADDD之间存在着相关;(2) DIVD和ADDD之间存在着 先读后写相关;(3) ADDD和SUBD指令关于浮点加法部件还存在着相关;(3) ADDD和SUBD指令关于浮点加法部件还存在着 结构相关 。表4-4 、4-5 、4-6 和表4-7 、4-8 、4-9分别给出了MULTD指令和DIVD指令将要写结果时记分牌的状态。分别给出了MULTD指令和DIVD指令将要写结果时记分牌的状态。59LD F6 , 34(R2)LD F2 , 45(R3)MULTD F0 , F2 , F4SUBD F8 , F6 , F2DIVD F10 , F0 , F6ADDD F6 , F8 , F2 表4-4 执行到MULTD将要写结果时记分牌的状态(指令状态表)指 令指令状态表IS RO EX WRLD F6 , 34(R2) 60LD F2 , 45(R3) MULTD F0 , F2 , F4 SUBD F8 , F6 , F2 DIVD F10 , F0 , F6 ADDD F6 , F8 , F2 表4-5 执行到MULTD将要写结果时记分牌的状态(功能部件状态表)部件名称功能部件状态表Busy Op Fi Fj Fk Qj Qk Rj Rk整数 no乘法61乘法 D 1 yes MULTD F0 F2 F4 no no乘法2 no加法 yes ADDD F6 F8 F2 no no除法 yes DIVD F10F2 F4 no no乘法2 no加法 yes ADDD F6 F8 F2 no no除法 yes DIVD F10 F0 6 F6 乘法1 1 no yes 表4-6 执行到MULTD将要写结果时记分牌的状态(结果寄存器状态表) 结果寄存器状态表62F0 F2 F4 F6 F8 F10 F30部件名称 乘法1 加法 除法F30部件名称 乘法1 加法 除法 表4-7、4-8、4-9 是程序段执行到 DIVD将要写结果时记分牌的状态。表4-7 执行到DIVD将要写结果时记分牌的状态(指令状态表)指 令指令状态表IS RO EX WRLD F6 , 34(R2) 63, ( )LD F2 , 45(R3) MULTD F0 , F2 , F4 SUBD F8 , F6 , F2 DIVD F10 , F0 , F6 ADDD F6 , F8 , F2 表4-8 执行到DIV.D将要写结果时记分牌的状态(功能部件状态表)部件名称功能部件状态表Busy Op Fi Fj Fk Qj Qk Rj Rk整数 no64整数乘法1 no乘法2 no加法 no除法 yes DIVD F10 F0 F6 no no乘法1 no乘法2 no加法 no除法 yes DIVD F10 F0 F6 no no 结果寄存器状态表F0 F2 F4 F6 F8 F10 F30表4-9 执行到DIV.D将要写结果时记分牌的状态(结果寄存器状态表)65部件名称 除法 4.分析记分牌是如何控制指令执行的 。操作在记分牌流水线中前进时,记分牌必须记录与操作有关的信息,如功能状态表中的各项。操作在记分牌流水线中前进时,记分牌必须记录与操作有关的信息,如功能状态表中的各项。约定:: FU : 指令使用的功能部件D D : : 目的寄存器的名字66D D : : 目的寄存器的名字: S1和S2: 源操作数寄存器的名字,: Op: 进行的操作: Fj(FU): 功能部件FU的Fj域Fj (FU )  S1 : 将寄存器S1 的名字送入Fj (FU )result(D):结果寄存器状态表中对应于目的寄存器D的内容,是结果寄存器状态表中对应于目的寄存器D的内容,是 产生目的寄存器D中结果的 功能部件名 。  流出(发射,IS)(1) 进入条件not Busy(FU) and not result(D D);//判断结构阻塞和写后写);//判断结构阻塞和写后写) (2) 计分牌记录内容67(2) 计分牌记录内容Busy(FU)yes;OP(FU)Op;Fi(FU)Busy(FU)yes;OP(FU)Op;Fi(FU)D D;Fj(FU);Fj(FU) S1 ;Fk(FU) S2 ; DLX记分牌信息组成和记录的信息, MULTD进入IS段时指 令指令状态表IS RO EX WRLD F6 , 34(R2) LD F2 , 45(R3) 68, ( )MULTD F0 , F2 , F4 SUBD F8 , F6 , F2DIVD F10 , F0 , F6ADDD F6 , F8 , F2 MULTD 进入IS 段时记分牌的状态部件名称功能部件状态表Busy Op Fi Fj Fk Qj Qk Rj Rk整数 yes LD F2 R3 no乘法1 yes MULTD F0R3 no乘法1 yes MULTD F0 2 F2 4 F4 整数 no yes乘法2yes乘法2加法69MULTD F0 , F2 , F4加法除法结果寄存器状态表F0 F2 F4 F6 F8 F10 F30部件名称F30部件名称 1 乘法1 整数 Qjresult( S1 ); //处理S1的FUQkresult(的FUQkresult( S2 ); //处理S2的FURjnot Qj; //Fj是否可用?Rknot Qk; //Fk是否可用?的FURjnot Qj; //Fj是否可用?Rknot Qk; //Fk是否可用?70result(D D )FU; //D D 被FU用作目的寄存器 读操作数(RO)(1)进入条件Rj Rk;//解决先写后读,两个源操作数须同时就绪 (2)计分牌记录内容Rjno; //已经读走了就绪的数据RjRkno; //已经读走了就绪的数据RkQj0; //不需要等待其它FU的计算结果Rjno; //已经读走了就绪的数据RjRkno; //已经读走了就绪的数据RkQj0; //不需要等待其它FU的计算结果71Qk0; 执行(EX)结束条件功能部件操作结束  写结果(WR)(1)进入条件  f((Fj(f) Fi(FU) or Rj(f)=no(不是IS))and (Fk(f)Fi(FU) or Rj(f)=no(不是IS))and (Fk(f) o Fi(FU) or Rk(f)=no ( 不是IS ));//检查是否存在先读后写,f是指任何功能单元);//检查是否存在先读后写,f是指任何功能单元(2)计分牌记录内容72 f(if Qj(f)=FU then Rj(f)yes);//有等结果的指令,则数据可用f(if Qj(f)=FU then Rj(f)yes);//有等结果的指令,则数据可用 f(if Qk(f)=FU then Rk(f)yes);result(Fi(FU))0;//没有FU使用寄存器Fi为目的寄存器busy(FU)=no //释放FUf(if Qk(f)=FU then Rk(f)yes);result(Fi(FU))0;//没有FU使用寄存器Fi为目的寄存器busy(FU)=no //释放FU 表4-4 执行到MULTD将要写结果时记分牌的状态(指令状态表)指 令指令状态表IS RO EX WRLD F6 , 34(R2) LD F2 , 45(R3) MULTD F0 , F2 , F4 73SUBD F8 , F6 , F2 DIVD F10 , F0 , F6 ADDD F6 , F8 , F2 MULT.D F0 , F2 , F4 ;该指令EXE执行没有结束ADD.D F6 , F8 , F2 ;等待DIVD进入RO读走F6数据,才能进入WR 执行到MULTD进入写结果WR时记分牌的状态(指令状态表)指 令指令状态表IS RO EX WRLD F6 , 34(R2) LD F2 , 45(R3) MULTD F0 , F2 , F4 74SUBD F8 , F6 , F2 DIVD F10 , F0 , F6 ADDD F6 , F8 , F2 执行到MULTD进入写结果WR时记分牌的状态(功能部件状态表)部件名称功能部件状态表Busy Op Fi Fj Fk Qj Qk Rj Rk整数 no乘法1 no整数 no乘法1 no MULTD F0 F2 F4 no no乘法2 no75加法 yes ADDD F6 F8 F2 no no除法 yes DIVD F10加法 yes ADDD F6 F8 F2 no no除法 yes DIVD F10 F0 F6 yes yes结果寄存器状态表F0 F2 F4 F6 F8 F10 F30部件名称F30部件名称 乘法1 加法 除法 5. 记分牌的性能受限于以下几个方面:(1) 程序指令中可开发的并行性,即是否存在可以并行执行的是否存在可以并行执行的 不相关 的指令。(2) 记分牌容量。记分牌的容量决定了流水线能在多大范围内寻找不相关指令。记分牌中,能够被检测相关性指令的集合(2) 记分牌容量。记分牌的容量决定了流水线能在多大范围内寻找不相关指令。记分牌中,能够被检测相关性指令的集合称为 指令窗口 。76称为 指令窗口 。本节中假设窗口包含的是一个简单基本块的线性代码,不考虑转移指令。(3)本节中假设窗口包含的是一个简单基本块的线性代码,不考虑转移指令。(3) 功能部件的数目和种类。功能部件的总数决定了。功能部件的总数决定了 结构冲突的严重程度。(4)的严重程度。(4) 反相关和输出相关。引起计分牌中先读后写和写后写阻塞。。引起计分牌中先读后写和写后写阻塞。  记分牌技术允许 在资源充足时乱序执行 。对于 数据相关 、名相关 ,通过检测后延迟相关指令的执行解决相关。由于乱序执行会引起的名相关,因此写后写与先读后写导致的阻塞会降低处理机的性能。的执行解决相关。由于乱序执行会引起的名相关,因此写后写与先读后写导致的阻塞会降低处理机的性能。 下面,将讨论的Tomasulo 算法,采用 寄存器换名技术 ,77使用了大量的缓冲器即 保留站作为虚拟寄存器暂时替代指令中的寄存器,以作为虚拟寄存器暂时替代指令中的寄存器,以 动态消除名相关 。 4.2.3 Tomasulo动态调度算法1.基本思想Tomasulo算法将记分牌的关键部分和寄存器换名技术结合在一起。通过寄存器换名消除写后写、先读后写相关引起的停顿。该算法首先在IBM 360/91(比CDC 6600晚3年)浮点部件使用,早于Cache技术应用于商业计算机。IBM当时计划在360系列78只设计一个指令系统和一个编译器,并且在各种档次的机器上要达到相应性能。360/91要求具有很高的浮点性能,但不是通过专用编译器实现;而且360只有4个双精度浮点寄存器,编译器调度的有效性受限。因此,采用Tomasulo动态调度算法,同时也解决360/91访存时间与浮点运算时间长的问题,以及支持循环的多次迭代重叠执行。 编译器通过寄存器换名可以解决写后写、先读后写相关。在Tomasulo算法中,寄存器换名通过硬件保留站实现,它保存已经发射和正在发射指令所需的操作数。其基本思想是: 只 要 操 作 数 有 效 , 就 将 其 取 到 保 留 站 , 避 免发射指令读操作数时才到寄存器中取数据。只 要 操 作 数 有 效 , 就 将 其 取 到 保 留 站 , 避 免发射指令读操作数时才到寄存器中取数据。 指 令 的 执 行 结 果 直 接 送 到 等 待 数 据 的 其 它 保79留站中去。 一 条 指 令 发 射 时 , 存 放 操 作 数 的 寄 存 器 名 被换成为对应于该寄存器保留站的名称(编号)。一 条 指 令 发 射 时 , 存 放 操 作 数 的 寄 存 器 名 被换成为对应于该寄存器保留站的名称(编号)。保留站的数目远多于实际的寄存器,保留站就是存放操作数与结果的虚拟寄存器,对系统结构层透明。 (1).采用Tomasulo算法的DLX浮点部件的基本结构 指 令 队 列 浮点寄存器组 1 2 3 4 从指令部件来地址部件存-取操作浮点操作操作数总线 浮点加法器 浮点乘法器公共数据总线(CDB) 存的数据 保留站存储器部件 取缓冲 6 5 4 3 2 1地址取的数据 操作数总线 操作总线个):保存已发射并等待到本功能部件执行的操作(指令)。保存已发射并等待到本功能部件执行的操作(指令)。包括操作数、运算符和用来检测和解决相关的信息。包括操作数、运算符和用来检测和解决相关的信息。 如果该操作的源操作数在寄存器中已经就绪 , 指令队列:指令从指令单元送入指令队列,指令队列中的指令按FIFO顺序发射。指令从指令单元送入指令队列,指令队列中的指令按FIFO顺序发射。81如果该操作的源操作数在寄存器中已经就绪 ,就将该操作数取来,保存到保留站中; 如果操作数还没有计算出来,则保留站中记录这个操作数将由谁计算出来,即如果操作数还没有计算出来,则保留站中记录这个操作数将由谁计算出来,即指明它由哪个功能部件产生。指明它由哪个功能部件产生。  取缓冲或load缓存(6个),三个功能:* 保存有效地址的各个部分直至计算完成;* 等待将要访问存储器的load指令;* 为已经完成且正在等待CDB的load指令保留结果。* 保存有效地址的各个部分直至计算完成;* 等待将要访问存储器的load指令;* 为已经完成且正在等待CDB的load指令保留结果。 存缓冲 (3 3 个 ) 保存的是写存储器的地址 、 数据 。82 存缓冲 (3 3 个 ) 保存的是写存储器的地址 、 数据 。* 保存有效地址的各个部分直至计算完成;* 为正在等待数据的store指令保存存储器目标地址;* 在存储单元可用之前保存地址和要写的数据。* 保存有效地址的各个部分直至计算完成;* 为正在等待数据的store指令保存存储器目标地址;* 在存储单元可用之前保存地址和要写的数据。  两个运算功能部件* 浮点乘法器完成乘法和除法操作* 浮点加法器完成加法和减法操作* 浮点乘法器完成乘法和除法操作* 浮点加法器完成加法和减法操作 浮点寄存器:通过一对操作数总线连到功能部件的保留站,通过其中浮点寄存器:通过一对操作数总线连到功能部件的保留站,通过其中一条总线连到公共数据总线,再到存缓冲。一条总线连到公共数据总线,再到存缓冲。公用数据总线 CDB : 来自运浮点算部件的 结果 、83 公用数据总线 CDB : 来自运浮点算部件的 结果 、load从存储器 读取的数据 都送到 CDB 上,再由 CDB送到浮点寄存器、 保留站 、 store缓存 。 采用Tomasulo算法的DLX浮点部件的基本结构 指 令 队 列 浮点寄存器组 1 2 3 4 从指令部件来地址部件存-取操作浮点操作操作数总线 浮点加法器 浮点乘法器公共数据总线(CDB) 存的数据 保留站存储器部件 取缓冲 6 5 4 3 2 1地址取的数据 操作数总线 操作总线存缓冲 除了寄存器换名, Tomasulo算法与记分牌在结构上有2处明显不同:除了寄存器换名, Tomasulo算法与记分牌在结构上有2处明显不同: 分布式相关检测和控制。一个功能部件的指令何时开始执行,由其保留站分布式相关检测和控制。一个功能部件的指令何时开始执行,由其保留站/ 缓冲控制,而记分牌是集中控制。 计算/ 取出的结果通过相关专用数据通路(公共数据总85线CDB )直接传送到保留站/存缓冲暂存,而不一定是写到寄存器。存缓冲暂存,而不一定是写到寄存器。 (2).指令流水线的分段情况使用Tomasulo算法的流水线) 流出(发射,Issue):使用Tomasulo算法的流水线) 流出(发射,Issue): 从指令队列中取一条指令:* 如果是浮点操作且有空的保留站就发射,如其中的操作数在寄存器就绪就将其送入保留站,如果未就绪就在保留站中记录产生该操作数的保留站编号(操作数寄存器名换成了保留站名,从指令队列中取一条指令:* 如果是浮点操作且有空的保留站就发射,如其中的操作数在寄存器就绪就将其送入保留站,如果未就绪就在保留站中记录产生该操作数的保留站编号(操作数寄存器名换成了保留站名, 寄存器换名消除名相关)。* 如果是访存操作且有空的缓冲就发射到缓冲。)。* 如果是访存操作且有空的缓冲就发射到缓冲。* * 如果没有空的保留站和缓冲 , 即 有结构相关 , 就不发射 。86* * 如果没有空的保留站和缓冲 , 即 有结构相关 , 就不发射 。(2) 执行(Execute): 如果保留站的操作数未计算出,就用保留站编号监视CDB,一旦有结果就取到保留站中,当二个操作数就绪,就执行指令操作。解决如果保留站的操作数未计算出,就用保留站编号监视CDB,一旦有结果就取到保留站中,当二个操作数就绪,就执行指令操作。解决 先写后读 相关。(3) 写结果( Write Result) ) : 功能部件完成计算后,将结果连同产生该结果的保留站号一起送到CDB上。根据发射时的记录,所有功能部件完成计算后,将结果连同产生该结果的保留站号一起送到CDB上。根据发射时的记录,所有 等待本保留站本保留站 结果 的 保留站 、 存缓冲 、 目标寄存器 将同时从CDB上获得所需数据。 采用Tomasulo算法的DLX浮点部件的基本结构 指 令 队 列 浮点寄存器组 1 2 3 4 从指...

本文链接:http://f-taiken.net/zhilingjibingxing/494.html