O无回路的循环间相关(2/4)- Example: A, B, C, d distinct nonoverlapping for(i=1;<=100;i=i+1){ Iteration i i+1 A[]=A+B];/*S1 B[+1]=C]+D[]}/*S2* B[+1] Non-Circular Loop-Carried Dependence S2 S2 Dependency Graph 1.S1和S2没有相关,S1和S2互换不会影响程序的正确性 2.在第一次循环中,S1依赖于前一次循环的B1] 3.51依赖上一次循环的S2,但S2不依赖S1 计算机体系结构
2021/2/7 计算机体系结构 27 无回路的循环间相关（2/4)- Example:A,B,C,D distinct & nonoverlapping for (i=1; i<=100; i=i+1) { A[i] = A[i] + B[i]; /* S1 */ B[i+1] = C[i] + D[i];} /* S2 */ Non-Circular Loop-Carried Dependence 1. S1和S2没有相关，S1和S2互换不会影响程序的正确性 2. 在第一次循环中，S1依赖于前一次循环的B[1]. 3. S1依赖上一次循环的S2，但S2不依赖S1
O循环间相关(3/4)-循环变换 OLD for(i=1;<=100;|=计+1){ A[]=A+B];/*S1 B[+]=C[]+D[i];}/*S2 NEW A[1]=A[1]+B[1] for(=1;iK=99;i=i+1){ B[+1]=C印]+Dj A[+1]=A[i+1]+B[i+1]; B[101]=C[100]+D[100]; 计算机体系结构
2021/2/7 计算机体系结构 28 循环间相关（3/4）-循环变换 OLD: for (i=1; i<=100; i=i+1) { A[i] = A[i] + B[i]; /* S1 */ B[i+1] = C[i] + D[i];} /* S2 */ NEW: A[1] = A[1] + B[1]; for (i=1; i<=99; i=i+1) { B[i+1] = C[i] + D[i]; A[i+1] = A[i+1] + B[i+1]; } B[101] = C[100] + D[100];
◎循环相关(4/4)- Dependence Distance 通常循环间相关呈现为递推关系 for(i=1;i<N;++)A印]=A[-1]+B[j 相关的距离可能大于1 for(i=4;i<N;计+)A[=A[i4]+B[]; 可以通过循环展开增加循环内的并行性 for(i=4;i<N;ⅰ=i+4) A[]=A[ⅰ4]+B[i]; A[+1]=A[i3]+B[+1]; A[+2]=A[i2]+B[i+2]; A[+3]=A[i1]+B[+3]; 计算机体系结构
2021/2/7 计算机体系结构 29 循环间相关（4/4）-Dependence Distance 通常循环间相关呈现为递推关系 for (i=1; i<N; i++) A[i] = A[i-1] + B[i]; 相关的距离可能大于1 for (i=4; i<N; i++) A[i] = A[i-4] + B[i]; 可以通过循环展开增加循环内的并行性 for (i=4; i<N; i=i+4) { A[i] = A[i-4] + B[i]; A[i+1] = A[i-3] + B[i+1]; A[i+2] = A[i-2] + B[i+2]; A[i+3] = A[i-1] + B[i+3]; }
循环展开示例小结 循环展开对循环间无关的程序是有效降低 stal的手段(对循环级并行) 指令调度,必须保证程序运行的结果不变 注意循环展开中的Load和 Store不同次循环 的Load和 Store是相互独立的。需要分析对 存储器的引用,保证他们没有引用同一地址 不同次的循环,使用不同的寄存器 删除不必要的测试和分支后,需调整循环步长 等控制循环的代码 移动SD到SUB和BNEz后,需要调整SD中的 偏移 计算机体系结构
2021/2/7 计算机体系结构 30 循环展开示例小结 • 循环展开对循环间无关的程序是有效降低 stalls的手段(对循环级并行）. • 指令调度，必须保证程序运行的结果不变 • 注意循环展开中的Load和Store,不同次循环 的Load 和Store 是相互独立的。需要分析对 存储器的引用，保证他们没有引用同一地址. • 不同次的循环，使用不同的寄存器 • 删除不必要的测试和分支后，需调整循环步长 等控制循环的代码. • 移动SD到SUBI和BNEZ后，需要调整SD中的 偏移
04/10-Review 指令级并行LP):流水线的平均CPI Pipeline cp= Ideal Pipeline cpl+ Struct Stalls RAW Stalls War Stalls WaW stalls Control Stalls 提高指令级并行的方法 软件方法:指令流调度,循环展开,软件流水线, trace scheduling 硬件方法 软件方法:指令流调度-循环展开 指令调度,必须保证程序运行的结果不变 ·偏移量的修改 寄存器的重命名 循环步长的调整 计算机体系结构
2021/2/7 计算机体系结构 31 04/10-Review • 指令级并行(ILP) : 流水线的平均CPI – Pipeline CPI = Ideal Pipeline CPI + Struct Stalls + RAW Stalls + WAR Stalls + WAW Stalls + Control Stalls +…… – 提高指令级并行的方法 • 软件方法：指令流调度，循环展开，软件流水线，trace scheduling • 硬件方法 • 软件方法：指令流调度-循环展开 • 指令调度，必须保证程序运行的结果不变 • 偏移量的修改 • 寄存器的重命名 • 循环步长的调整