指令级并行的开发——软件方法曹强计算机学院武汉光.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 存储别名分析 什么是存储别名 一个元素可能同时拥有多个合法的地址表达式 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 */ Z[i] = Y[i] + a； /* S3 */ Y[i] = a – Y[i]； /* S4 */ } 6.5 开发更多的指令级并行 解 这4条语句中存在以下相关： 1. S3与S1和S4与S1之间分别存在真数据相关。 2. S2和S1之间存在反相关。 3. S3和S4之间存在反相关。 4. S1和S4之间存在输出相关。 for（i=1；i=100；i=i+1）{ Y[i] = X[i] / a； /* S1 */ X[i] = X[i] + a； /* S2 */ Z[i] = Y[i] + a； /* S3 */ Y[i] = a – Y[i]； /* S4 */ } 6.5 开发更多的指令级并行 将原代码变换为下面的形式，可以消除所有输出相关和反相关。 for（i=1；i=100；i=i+1）{ /* 将数组Y重命名为T以消除输出相关 */ T[i] = X[i] / c； /* 将数组X重命名为X1以消除反相关 */ X1[i] = X[i] + c； /* 将Y重命名为T以消除反相关 */ Z[i] = T[i] + c； Y[i] = c – T[i]； } 6.5 开发更多的指令级并行 值传播优化实例 优化前代码 DADDUI R1，R2，#4 DADDUI R1，R1，#4 优化后代码 DADDUI R1，R2，#8 值传播优化通过将变量替换为已知的值或表达式以达到消除数据相关 6.5 开发更多的指令级并行 高度消减优化实例 目的：缩短数据流图中关键路径的长度 优化前代码I ADD R1，R2，R3 /* I1 */ ADD R4，R1，R6 /* I2 */ ADD R8，R4，R7 /* I3 */ 优化后代码I ADD R1，R2，R3 ADD R4，R6，R7 ADD R8，R1，R4 6.5 开发更多的指令级并行 高度消减优化实例 优化前代码II sum = sum + X[i]； sum = sum + X[i+1]； sum = sum + X[i+2]； sum = sum + X[i+3]； sum = sum + X[i+4]； 优化后代