计算机系统结构第6章.pptVIP

例6.1 对于下面的源代码，转换成MIPS汇编语言，在不进行指令调度和进行指令调度两种情况下，分析其代码一次循环所需的执行时间。 for (i=1000; i0; i--) x[i] = x[i] + s; 解： 先把该程序翻译成MIPS汇编语言代码 Loop： L.D F0, 0(R1) ADD.D F4, F0, F2 S.D F4, 0(R1) DADDIU R1, R1, #-8 BNE R1, R2, Loop 6.1 基本指令调度及循环展开 在用编译器对上述程序进行指令调度以后，程序的执行情况如下： 指令流出时钟 Loop： L.D F0, 0(R1) 1 DADDIU R1, R1, #-8 2 ADD.D F4, F0, F2 3 (空转) 4 BNE R1, R2, Loop 5 S.D F4, 8(R1) 6 6.2 跨越基本块的静态指令调度 实例分析 由于分支条件为true(转移)的概率大，全局指令调度时会将语句1、2、3、5合并为一个更大的基本块。 6.2 跨越基本块的静态指令调度 将上图中的代码转换为下面的MIPS汇编指令 6.2 跨越基本块的静态指令调度 调度指令I1 直接将I1移到BEQZ前是否会产生错误结果？ 向基本块elsepart中增加补偿代码 补偿代码有可能带来额外时间开销 调度指令I2 将I2移动到基本块thenpart中，同时复制到elsepart中。 若不影响执行结果，将I2调度到BEQZ前，同时删除elsepart中的副本。 6.2 跨越基本块的静态指令调度 全局指令调度是一个很复杂的问题 以I1的调度为例： 需要确定分支中基本块thenpart和elsepart的执行频率各是多少？ 在分支语句前完成I1所需的开销是多大？ 调度I1是否能够缩短thenpart块的执行时间？ I1是否是最佳的被调度对象？ 是否需要向elsepart块中增加补偿代码，补偿代码开销如何？怎样生成补偿代码？ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 存储别名分析 什么是存储别名 一个元素可能同时拥有多个合法的地址表达式 A[i+5]、A[j*2-6]、A[k] 数组是仿射的 如果一个一维数组A[m:n]的下标可以被表示为形如 a×i+b的形式，那么就称该数组是仿射的（affine）。 一个多维数组，如果它每一维的下标都是仿射的，那 么它就是仿射的。 6.5 开发更多的指令级并行 GCD测试法 算法描述 如果GCD(c, a)可以整除(d-b)，那么有可能存在存储别名。 如果GCD测试的结果为假（不能整除），那么一定没有存储别名存在。 例6.9 使用GCD测试方法判断下面的循环中是否存在存储别名。 for（i=1；i=100；i=i+1） x[2*i+3] = x[2*i] * 5.0； 解 在这个循环中，a=2，b=3，c=2，d=0， 那么GCD(a, c)=2，而d-b=-3。 由于2不能整除-3，因此没有存储别名，即无论i取何值，x[2*i+3] 与x[2*i]都将表示数组x的不同元素。 6.5 开发更多的指令级并行 数据相关分析 除了检测指令之间是否存在数据相关外，编译器还会将识别出的数据相关进一步细分为真数据相关、输出相关和反相关等不同类型，以便利用不同的优化技术消除这些相关。 常用的优化有重命名、值传播、高度消减等。 6.5 开发更多的指令级并行 重命名优化实例 例6.10 找出下面循环中的所有数据相关，指出它们究竟是真数据 相关、输出相关、还是反相关，并利用重命名技术消除其中的输出 相关和反相关。 for（i=1；i=100；i=i+1）{ Y[i] = X[i] / a； /* S1 */ X[i] = X[i] + a； /* S2 */