针对以下矩阵相乘的C循环语句

1、针对以下矩阵相乘的C循环语句，直接在其源程序基础上做出循环优化（代码外提、强度消弱等）设矩阵如下：int a2020,b2020,c2020;/width of an integer is 4/ a = b * c;for(i=0;i20;i+) for(j=0;j20;j+)for(k=0;k20;k+)aij = aij + bik*ckj;(1) 首先考虑代码外提。n 对于k循环而言，aij和bi为循环不变式，可以外提至k循环外（j循环内），程序变换如下：for(i=0;i20;i+) for(j=0;j20;j+) t1 = addr(aij);t2 = addr(bi);for(k=

2、0;k20;k+) *t1 = *t1 + t2k*ckj; / k-loop / j-loop / i-loopn 考虑ai和bi在中间层循环j-loop中仍然是循环不变式，可以进一步外提出j-loop(提到i-loop中)，程序变换为：for(i=0;i20;i+) t3 = addr(ai);t4 = addr(bi);for(j=0;j20;j+) t1 = addr(t3j);t2 = t4;for(k=0;k20;k+) *t1 = *t1 + t2k*ckj; / k-loop / j-loop / i-loopn 考虑复写传播，可以删除变量t2。程序变换如下：for(i=0;i

3、20;i+) t3 = addr(ai);t4 = addr(bi);for(j=0;j20;j+) t1 = addr(t3j);for(k=0;k20;k+) *t1 = *t1 + t4k*ckj; / k-loop / j-loop / i-loop(2) 然后考虑数组下标的情况（设数组元素按行优先排列），即将其变换为指针形式，即地址计算的展开形式。t3 = addr(ai);其地址表述为：i*20*4+A-0 = i*80+A/A 为数组a的起始地址；/C语言数组下标从0开始。这是一个基本归纳变量i族的归纳表达式t4 = addr(bi);其地址表述为：i*20*4+B-0 = i*

4、80+B/B 为数组b的起始地址；/C语言数组下标从0开始。这是一个基本归纳变量i族的归纳表达式t1 = addr(t3j);其地址表述为：j*4+t3-0 = j*4+t3/C语言数组下标从0开始。这是一个基本归纳变量j族的归纳表达式t4k的地址表述为：k*4+t4-0 = k*4+t4/C语言数组下标从0开始。这是一个基本归纳变量k族的归纳表达式ckj的地址表述为：k*20*4+j*4+C-0=k*80+j*4+C/C 为数组c的起始地址；/C语言数组下标从0开始。这是一个基本归纳变量k族的归纳表达式/因为上面式子中的j*4+C在k-loop中不变(3) 现在进行强度消弱。注意每次的强度消

5、弱分三个步骤完成，即，a) 引入新的变量s，并将原归纳表达式替换为变量s；b) 在循环中基本归纳变量增值语句后，添加变量s的增值语句；c) 在循环外基本归纳变量的初值后（一般在前置块末尾）添加变量s的初值计算语句；t4k:针对上面的归纳表达式k*4+t4引入变量t5ckj:针对上面的归纳表达式k*80+j*4+C引入变量t6;addr(t3j):针对上面的归纳表达式j*4+t3引入变量t7;addr(bi):针对上面的归纳表达式i*80+B引入变量t8;addr(ai):针对上面的归纳表达式i*80+A引入变量t9;程序继续变换为：t8 = B;/ addr(bi)的初值t9 = A; / a

6、ddr(ai)的初值for(i=0;i20;i+) t3 = t9;t4 = t8;t7 = t3; / addr(t3j)的初值；for(j=0;j20;j+) t1 = t7;t5 = t4; /t4k的初值t6 = j * 4 + C /ckj的初值；它是j-loop中的归纳表达式for(k=0;k20;k+) *t1 = *t1 + (*t5)*(*t6);t5 = t5 + 4;t6 = t6 + 80; / k-loopt7 = t7 + 4; / j-loopt8 = t8 + 80;t9 = t9 + 80; / i-loop此时发现，j*4+C也是归纳表达式；引入新的变量t1

7、0;则程序变换为：注意看其中红色部分为强度消弱的三个步骤！t8 = B;/ addr(bi)的初值t9 = A; / addr(ai)的初值for(i=0;i20;i+) t3 = t9;t4 = t8;t7 = t3; / addr(t3j)的初值；t10 = C;/ j * 4 + C的初值for(j=0;j20;j+) t1 = t7;t5 = t4; /t4k的初值t6 = t10;/将j * 4 + C替换为变量t10for(k=0;k20;k+) *t1 = *t1 + (*t5)*(*t6);t5 = t5 + 4;t6 = t6 + 80; / k-loopt7 = t7 + 4;t10 = t10 + 4;/t10的增值语句 / j-loopt8 = t8 + 80;t9 = t9 + 80; / i-loop(4) 此时再次考虑复写传播，删除变量t3、t4和t1，分别由变量t9、t8和t7来代替！ 程序最终变换为：t8 = B;/ addr(bi)的初值t9 = A; / addr(ai)的初值for(i=0;i20;i+) t7 = t9;t10 = C; for(j=0;j20;j+) t5 = t8; /t4k的初值t6 = t10;for(k=0;k20;k+) *t7