指令级并行.ppt

第4章 指令级并行 主讲： 顾一禾 本章学习内容 指令级并行的基本概念 指令的动态调度 动态分支预测技术 多指令流出技术 4.1 指令级并行 指令之间存在的潜在并行性称为指令级并行。（ILP：Instruction-Level Parallelism） 只有将硬件技术和软件技术互相配合，才能够最大限度地挖掘出程序中存在的指令级并行。 1. 流水线处理机的实际CPI 流水线处理机的实际CPI就是理想流水线的CPI加上各类停顿的时钟周期数： CPI流水线 = CPI理想 + 停顿结构冲突  + 停顿数据冲突+ 停顿控制冲突 CPI理想即理想CPI，是衡量流水线最高性能的指标之一。 IPC（Instructions Per Cycle ） IPC：每个时钟周期内完成的指令条数。 IPC是CPI的倒数。 提高IPC的途径之一是减少CPI流水线 。 2. 基本程序块 基本程序块：一段除了入口和出口以外不包含其他分支的一个线性代码段。 因为程序往往平均每5～7条指令就会有一个分支，而且指令之间还可能存在相关，所以在基本程序块中能开发的并行性是很有限的，很可能比基本块的大小要小很多。 为了明显地提高性能，必须跨越多个基本块开发指令的并行性。 3. 开发指令级并行常用的方法 （1）开发循环级并行 循环级并行（Loop－level parallelism）：循环程序不同迭代之间存在的并行性。 例： for （i=1； i≤500； i=i＋1） a[i]=a[i]＋s； 在每一次循环的内部，没有任何的并行性。 每一次循环都可以与其他的循环重叠并行执行。 开发循环级并行性是增加指令之间并行性的最简单和最常用的方法。 开发循环级并行的基本技术 采用循环展开技术 采用向量指令和向量数据表示 （2）解决相关与流水线冲突问题 相关是程序固有的一种属性，它反映了程序中指令之间的相互依赖关系。 相关的三种类型：数据相关、名相关、控制相关。 如果两条指令相关，它们就不能并行执行，或只能部分重叠执行。 由于相关的存在，使得指令流中的下一条指令不能在指定时钟周期执行，就是发生了流水线冲突。 相关的存在限制了指令级并行（ILP）的开发。 流水线冲突的三种类型：结构冲突、数据冲突、控制冲突。 结构冲突：由硬件资源冲突造成。 数据冲突：由数据相关和名相关造成。 控制冲突：由控制相关造成。 具体的一次相关是否会导致实际冲突的发生以及该冲突会带来多长的停顿，根据流水线的属性而定。 解决相关与冲突的方法 ① 保持相关，但避免发生冲突。 方法：指令调度，包括静态调度和动态调度。 ②通过代码变换，消除相关。 解决相关与冲突时需注意的问题 由于相关的存在，在开发指令级并行时，如果可能影响到程序的正确性，就必须注意保持程序顺序。 程序顺序：由源程序确定的在完全串行方式下指令的执行顺序。 控制相关并不是一个必须严格保持的关键属性。 当存在控制相关时，在对程序的正确性没有影响的前提下，可以不遵守控制相关的依赖关系，执行本来不该执行的指令。 必须保持的最关键的两个属性 要正确地执行程序，必须保持的最关键的两个属性是：数据流和异常行为。 保持异常行为：无论怎么改变指令的执行顺序，都不能改变程序中异常的发生情况。 原来程序中是怎么发生的，改变执行顺序后还是怎么发生。 可弱化为：指令执行顺序的改变不能导致程序中发生新的异常。 如果能做到保持程序的数据相关和控制相关，就能保持程序的数据流和异常行为。 例： DADDU R2，R3，R4 BEQZ R2，L1 LW R1，0（R2） L1 ： 如果不保持关于R2的数据相关，程序的执行结果就会改变。 如果不保持控制相关，把LW指令移到BEQZ之前，就有可能产生一个新的“访存保护”异常（如果R2＝0）。 数据流：指数据值从其产生者指令到其消费者指令的实际流动。 分支指令使得数据流具有动态性，因为它使得给定指令的数据可以有多个来源。 仅仅保持数据相关性是不够的，一条指令可能与多条先前的指令数据相关，程序顺序决定了哪条指令真正是所需数据的产生者。 只有再加上保持控制顺序，才能够保持程序顺序。 例： DADDU R1，R2，R3 BEQZ R4，L1 DSUBU R1，R5，R6 L1 ：… OR R7，R1，R8 OR指令中使用的R1值取决于BEQZ指令分支的是否成功。即OR与DADDU或DSUBU指令相关。 必须通过保持控制相关，避免对数据流的修改，以保证数据流的正确。 ★DSUB