下列是否存在名相关? 1 Loop: LD F0,O(R1 ADDD F4.F0F2 Sd O(R1),F4 drop SUBI& BNEZ LDF6,8(R1) 456789 ADDD F8.F6F2 SD -8(R1), F8 drop SuBl& BNEZ LDF10,-16(R1) ADDD F12F10F2 SD -16(R1), F12 drop sUBl& BNEZ 10LDF14,24(R1) ADDD F16F14.F2 12SD24(R1)F16 13 SUBI R1.R1#32 alter to 4*8 14 BNEZ R1LOOP 15 NOP 这种方法称为寄存器重命名( register renaming) 计算机体系结构
1 Loop:LD F0,0(R1) 2 ADDD F4,F0,F2 3 SD 0(R1),F4 ;drop SUBI & BNEZ 4 LD F6,-8(R1) 5 ADDD F8,F6,F2 6 SD -8(R1),F8 ;drop SUBI & BNEZ 7 LD F10,-16(R1) 8 ADDD F12,F10,F2 9 SD -16(R1),F12 ;drop SUBI & BNEZ 10 LD F14,-24(R1) 11 ADDD F16,F14,F2 12 SD -24(R1),F16 13 SUBI R1,R1,#32 ;alter to 4*8 14 BNEZ R1,LOOP 15 NOP 这种方法称为寄存器重命名（register renaming） 2021/2/7 计算机体系结构 22 下列是否存在名相关?
从编译器角度看代码移动(3/4) 访问存储单元时,很难判断名相关 100(R4)=20(R6 不同次的循环,20(R6)=20(R6)? 我们给出的示例要求编译器知道假设R不 变,因此 0(R1)≠-8(R1)≠-16(R1)≠-24(R1) 因此oads和 stores之间相互无关可以移动
2021/2/7 23 从编译器角度看代码移动（3/4) • 访问存储单元时，很难判断名相关 – 100(R4) = 20(R6)? – 不同次的循环，20(R6) = 20(R6)? • 我们给出的示例要求编译器知道假设R1不 变，因此: 0(R1) ≠ -8(R1) ≠ -16(R1) ≠ -24(R1) – 因此loads和stores之间相互无关可以移动
从编译器角度看代码移动(4/4) 最后一种相关称为控制相关( contro dependence) Example fp1{1 fp2{2 ·S1依赖于P1的测试结果,S2依赖于P2的测试。 处理控制相关的原则 受分支指令控制的指令,不能移到控制指令之前,以 免该指令的执行不在分支指令的控制范围 不受分支指令控制的指令,不能移到控制指令之后, 以免该指令的执行受分支指令的控制 减少控制相关可以提高指令的并行性 计算机体系结构
2021/2/7 计算机体系结构 24 从编译器角度看代码移动（4/4) • 最后一种相关称为控制相关( control dependence) • Example • if p1 {S1;}; • if p2 {S2;}; • S1 依赖于P1的测试结果，S2依赖于P2的测试。 • 处理控制相关的原则： – 受分支指令控制的指令，不能移到控制指令之前，以 免该指令的执行不在分支指令的控制范围. – 不受分支指令控制的指令，不能移到控制指令之后， 以免该指令的执行受分支指令的控制. • 减少控制相关可以提高指令的并行性
下列程序段的控制相关 1 Loop DF0,0(R1)11LDF0,o(R1) 23 ADDD F4.F0, F2 12 ADDD F4F0F2 SD0(R1),F413SD0(R1),F4 SUBI R1R18 14 SUBI R1,R18 BEQZ R1, exit 15 BEQZ R1, exit 56789 LD FO,O(R1) ADDD F4 FO F2 SD0(R1),F4 SUBI R1R18 10 BENz R1, exit
1 Loop: LD F0,0(R1) 2 ADDD F4,F0,F2 3 SD 0(R1),F4 4 SUBI R1,R1,8 5 BEQZ R1,exit 6 LD F0,0(R1) 7 ADDD F4,F0,F2 8 SD 0(R1),F4 9 SUBI R1,R1,8 10 BEQZ R1,exit 11 LD F0,0(R1) 12 ADDD F4,F0,F2 13 SD 0(R1),F4 14 SUBI R1,R1,8 15 BEQZ R1,exit .... 2021/2/7 25 下列程序段的控制相关
循环间相关(1/4) EXample:下列程序段存在哪些数据相关? Iteration i T 1 (A,B,C指向不同的存储区且不存在覆盖区) A[+1] S1 S1 for(i=1;i<=100;=i计+1){ A[+1] A[+1] A[+]=A[]+c[ji;/*S1 B[+1] S2 S2 B+1]=B[+A[+1];/*S2 Dependency Graph S2使用由S1在同一循环计算出的A+1] 2.S1使用由S1在前一次循环中计算的值;S2也使用由S2在 次循环中计算的值这种存在于循环间的相关,我们称为 " loop-carried dependence"i这表示循环间存在相关,不能并 行执行,它与我们前面的例子中循环间无关是有区别的
2021/2/7 26 循环间相关（1/4） Example: 下列程序段存在哪些数据相关? (A,B,C 指向不同的存储区且不存在覆盖区) for (i=1; i<=100; i=i+1) { A[i+1] = A[i] + C[i]; /* S1 */ B[i+1] = B[i] + A[i+1]; /* S2 */ } 1. S2使用由S1在同一循环计算出的 A[i+1]. 2. S1 使用由S1在前一次循环中计算的值；S2也使用由S2在 前一次循环中计算的值. 这种存在于循环间的相关，我们称为 “loop-carried dependence”这表示循环间存在相关，不能并 行执行，它与我们前面的例子中循环间无关是有区别的