第4章-指令级并行

LOGO顾一禾制作2013第5版2020/5/9第4章指令级并行主讲：顾一禾2020/5/92本章学习内容指令级并行的基本概念指令的动态调度动态分支预测技术多指令流出技术2020/5/934.1指令级并行指令之间存在的潜在并行性称为指令级并行。（ILP：Instruction-LevelParallelism）只有将硬件技术和软件技术互相配合，才能够最大限度地挖掘出程序中存在的指令级并行。2020/5/941.流水线处理机的实际CPI流水线处理机的实际CPI就是理想流水线的CPI加上各类停顿的时钟周期数：CPI流水线=CPI理想+停顿结构冲突+停顿数据冲突+停顿控制冲突CPI理想即理想CPI，是衡量流水线最高性能的指标之一。2020/5/95IPC（InstructionsPerCycle）IPC：每个时钟周期内完成的指令条数。IPC是CPI的倒数。提高IPC的途径之一是减少CPI流水线。2020/5/962.基本程序块基本程序块：一段除了入口和出口以外不包含其他分支的一个线性代码段。因为程序往往平均每5～7条指令就会有一个分支，而且指令之间还可能存在相关，所以在基本程序块中能开发的并行性是很有限的，很可能比基本块的大小要小很多。为了明显地提高性能，必须跨越多个基本块开发指令的并行性。2020/5/973.开发指令级并行常用的方法（1）开发循环级并行循环级并行（Loop－levelparallelism）：循环程序不同迭代之间存在的并行性。例：for（i=1；i≤500；i=i＋1）a[i]=a[i]＋s；在每一次循环的内部，没有任何的并行性。每一次循环都可以与其他的循环重叠并行执行。开发循环级并行性是增加指令之间并行性的最简单和最常用的方法。2020/5/98开发循环级并行的基本技术采用循环展开技术采用向量指令和向量数据表示2020/5/99（2）解决相关与流水线冲突问题相关是程序固有的一种属性，它反映了程序中指令之间的相互依赖关系。相关的三种类型：数据相关、名相关、控制相关。如果两条指令相关，它们就不能并行执行，或只能部分重叠执行。由于相关的存在，使得指令流中的下一条指令不能在指定时钟周期执行，就是发生了流水线冲突。相关的存在限制了指令级并行（ILP）的开发。2020/5/910流水线冲突的三种类型：结构冲突、数据冲突、控制冲突。结构冲突：由硬件资源冲突造成。数据冲突：由数据相关和名相关造成。控制冲突：由控制相关造成。具体的一次相关是否会导致实际冲突的发生以及该冲突会带来多长的停顿，根据流水线的属性而定。2020/5/911解决相关与冲突的方法①保持相关，但避免发生冲突。方法：指令调度，包括静态调度和动态调度。②通过代码变换，消除相关。2020/5/912解决相关与冲突时需注意的问题由于相关的存在，在开发指令级并行时，如果可能影响到程序的正确性，就必须注意保持程序顺序。程序顺序：由源程序确定的在完全串行方式下指令的执行顺序。控制相关并不是一个必须严格保持的关键属性。当存在控制相关时，在对程序的正确性没有影响的前提下，可以不遵守控制相关的依赖关系，执行本来不该执行的指令。2020/5/913必须保持的最关键的两个属性要正确地执行程序，必须保持的最关键的两个属性是：数据流和异常行为。保持异常行为：无论怎么改变指令的执行顺序，都不能改变程序中异常的发生情况。原来程序中是怎么发生的，改变执行顺序后还是怎么发生。可弱化为：指令执行顺序的改变不能导致程序中发生新的异常。如果能做到保持程序的数据相关和控制相关，就能保持程序的数据流和异常行为。2020/5/914例：DADDUR2，R3，R4BEQZR2，L1LWR1，0（R2）L1：如果不保持关于R2的数据相关，程序的执行结果就会改变。如果不保持控制相关，把LW指令移到BEQZ之前，就有可能产生一个新的“访存保护”异常（如果R2＝0）。2020/5/915数据流：指数据值从其产生者指令到其消费者指令的实际流动。分支指令使得数据流具有动态性，因为它使得给定指令的数据可以有多个来源。仅仅保持数据相关性是不够的，一条指令可能与多条先前的指令数据相关，程序顺序决定了哪条指令真正是所需数据的产生者。只有再加上保持控制顺序，才能够保持程序顺序。2020/5/916例：DADDUR1，R2，R3BEQZR4，L1DSUBUR1，R5，R6L1：…ORR7，R1，R8OR指令中使用的R1值取决于BEQZ指令分支的是否成功。即OR与DADDU或DSUBU指令相关。必须通过保持控制相关，避免对数据流的修改，以保证数据流的正确。★DSUBU不能被移到BEQZ之前。2020/5/917有时，不遵守控制相关既不影响异常行为，也不改变数据流。在这种情况下，可以大胆地进行指令调度，把失败分支中的指令调度到分支指令之前。2020/5/918例：DADDUR1，R2，R3BEQZR12，SkipnextDSUBUR4，R5，R6DADDUR5，R4，R9Skipnext：ORR7，R8，R9如果已知R4在Skipnext后不再被使用，而且DSUBU指令不会产生异常，那么就可以把DSUBU指令移到BEQZ之前。因为这个移动不会改变数据流。2020/5/919开发指令的并行性的方法硬件方法：指令的动态调度、动态分支预测、多指令流出技术。软件方法：指令的静态调度、循环展开技术。软硬件结合方法：显式并行指令计算EPIC。2020/5/9204.5循环展开和指令调度4.5.1循环展开和指令调度的基本方法为了充分发挥流水线的作用，必须设法让它满负荷工作。因此要充分开发指令之间存在的并行性，找出不相关的指令序列，让它们在流水线上重叠并行执行。增加指令间并行性最简单和最常用的方法开发循环级并行性—循环的不同迭代之间存在的并行性。在把循环展开后，通过重命名和指令调度来开发更多的并行性。2020/5/921编译器指令调度能力的限制编译器完成指令调度的能力受限于两个特性：程序固有的指令级并行性；流水线功能部件的执行延迟。2020/5/922浮点流水线延迟Load指令的结果可以通过定向路径及时送给store指令，所以延迟为0，不用插入停顿。产生结果的指令使用结果的指令延迟（时钟周期数）浮点计算另一个浮点计算3浮点计算浮点store（S.D）2浮点load（L.D）浮点计算1浮点load（L.D）浮点store（S.D）02020/5/923例4.6对于下面的源代码，转换成MIPS汇编语言，在不进行指令调度和进行指令调度两种情况下，分析其代码一次循环所需的执行时间。for(i=1；i=1000；i++)x[i]=x[i]+s；解：该循环的不同迭代之间不存在相关，所以多次迭代可以并行执行。2020/5/924MIPS汇编语言代码：假设R1的初值指向第一个元素，8（R2）指向最后一个元素。Loop：L.DF0,0(R1)//取一个向量元素放入F0ADD.DF4,F0,F2//加上在F2中的标量S.DF4,0(R1)//存结果DADDIUR1,R1,#－8//将指针减8（每个数据占8个字节）BNER1,R2,Loop//若R1不等于R2，表示尚未结束，//转移到Loop继续执行其中：整数寄存器R1：指向向量中的当前元素。（初值为向量中最高端元素的地址）浮点寄存器F2：用于保存常数s。2020/5/925不进行指令调度的情况下，程序的实际执行情况Loop:L.DF0,0（R1）1（空转）2ADD.DF4,F0,F23（空转）4（空转）5S.DF4,0（R1）6DADDIUR1,R1，#－87（空转）8BNER1,R2,Loop9（空转）10每个元素的操作需要10个时钟周期，其中5个是空转周期。2020/5/926指令调度以后，程序的执行情况Loop:L.DF0,0（R1）（空转）ADD.DF4,F0,F2（空转）（空转）S.DF4,0（R1）DADDIUR1,R1,#－8（空转）BNER1,R2,Loop（空转）Loop:L.DF0,0（R1）DADDIUR1,R1,#－8ADD.DF4,F0,F2（空转）BNER1,R2,LoopS.DF4,8（R1）因为修改指针R1的减8操作提前了，所以S.D指令中变址指针的偏移量要从0改为8.2020/5/927指令流出时钟Loop:L.DF0,0(R1)1DADDIUR1,R1,#-82ADD.DF4,F0,F23（空转）4BNER1,Loop5S.DF4，8(R1)6一个元素的操作时间从10个时钟周期减少到6个,其中5个周期是有指令执行的，1个为空转周期。2020/5/928例子中的问题及解决方案只有L.D、ADD.D和S.D这3条指令是有效操作，占用3个时钟周期。而DADDIU、空转和BEN这3个时钟周期都是附加的循环控制开销。有效操作比例不高。循环展开技术把循环体的代码复制多次并按顺序排列，然后相应调整循环的结束条件。2020/5/929例4.7将例4.6中的循环展开3次得到4个循环体，然后对展开后的指令序列在不调度和调度两种情况下，分析代码的性能。设R1的初值为32的倍数，即循环次数为4的倍数。因此不需要在循环体后面增加补偿代码。方法：消除冗余的指令，并且不重复使用寄存器。2020/5/930分配寄存器（不重复使用寄存器）F0、F4：用于展开后的第1个循环体F2：用于保存常数F6、F8：用于展开后的第2个循环体F10、F12：用于展开后的第3个循环体F14、F16：用于展开后的第4个循环体2020/5/931展开后没有调度的代码指令流出时钟Loop:L.DF0,0(R1)1（空转）2ADD.DF4,F0,F23（空转）4（空转）5S.DF4,0（R1）6L.DF6,-8(R1)7（空转）8ADD.DF8,F6,F29（空转）10（空转）11S.DF8,-8（R1）12L.DF10,-16(R1)13（空转）14指令流出时钟ADD.DF12,F10,F215（空转）16（空转）17S.DF12,-16(R1)18L.DF14,-24(R1)19（空转）20ADD.DF16,F14,F221（空转）22（空转）23S.DF16,-24(R1)24DADDIUR1,R1,#-3225（空转）26BNER1,R2,Loop27（空转）282020/5/932结果分析这个循环每遍共使用了28个时钟周期。有4个循环体，完成4个元素的操作。平均每个元素使用28/4=7个时钟周期原始循环的每个元素需要10个时钟周期。节省的时间：从减少循环控制的开销中获得的。在整个展开后的循环中，实际指令只有14条，其他14个周期都是空转。结论：效率并不高2020/5/933对指令序列进行优化调度指令流出时钟Loop:L.DF0,0(R1)1L.DF6,-8(R1)2L.DF10,-16(R1)3L.DF14,-24(R1)4ADD.DF4,F0,F25ADD.DF8,F6,F26ADD.DF12,F10,F27ADD.DF16,F14,F28S.DF4,0(R1)9S.DF8,-8(R1)10DADDIUR1,R1,#-3212S.DF12,16(R1)11BNER1,R2,Loop13S.DF16,8(R1)142020/5/934结果分析没有数据相关引起的空转等待。整个循环仅仅使用了14个时钟周期。平均每个元素的操作使用14/4=3.5个时钟周期。通过循环展开、寄存器重命名和指令调度，可以有效地开发出指令级并行。2020/5/935循环展开和指令调度时要注意的问题保证正确性。在循环展开和调度过程中尤其要注意两个地方的正确性：循环控制，操作数偏移量的修改。注意有效性。只有能够找到不同循环体之间的无关性，才能有效地使用循环展开。使用不同的寄存器。（否则可能导致新的冲突）删除多余的测试指令和分支指令，并对循环结束代