优化C代码

Question

对于高性能计算课程的分配,我需要优化以下代码片段:

int foobar(int a, int b, int N)
{
    int i, j, k, x, y;
    x = 0;
    y = 0;
    k = 256;
    for (i = 0; i <= N; i++) {
        for (j = i + 1; j <= N; j++) {
            x = x + 4*(2*i+j)*(i+2*k);
            if (i > j){
               y = y + 8*(i-j);
            }else{
               y = y + 8*(j-i);
            }
        }
    }
    return x;
}

使用一些建议,我设法优化代码(或至少我认为如此),例如:

1. 不断传播
2. 代数简化
3. 复制传播
4. 常见的Subexpression消除
5. 死代码消除
6. 循环不变量删除
7. 按位移位而不是乘法,因为它们更便宜.

这是我的代码:

int foobar(int a, int b, int N) {

    int i, j, x, y, t;
    x = 0;
    y = 0;
    for (i = 0; i <= N; i++) {
        t = i + 512;
        for (j = i + 1; j <= N; j++) {
            x = x + ((i<<3) + (j<<2))*t;
        }
    }
    return x;
}

根据我的导师的说法,优化良好的代码指令应该在汇编语言级别中具有更少或更少成本的指令.因此必须运行,指令在比原始代码更短的时间内,即使用::

执行时间=指令计数*每条指令的周期

当我使用命令生成汇编代码:gcc -o code_opt.s -S foobar.c,

尽管已经进行了一些优化,但生成的代码拥有比原始代码多得多的行,并且运行时间较低,但没有原始代码那么多.我究竟做错了什么？

不要粘贴汇编代码,因为两者都非常广泛.所以我在main中调用函数"foobar",我在linux中使用time命令测量执行时间

int main () {
    int a,b,N;

    scanf ("%d %d %d",&a,&b,&N);
    printf ("%d\n",foobar (a,b,N));
    return 0;
}

Answer 1

y 不影响代码的最终结果 - 删除:

int foobar(int a, int b, int N)
{
    int i, j, k, x, y;
    x = 0;
    //y = 0;
    k = 256;
    for (i = 0; i <= N; i++) {
        for (j = i + 1; j <= N; j++) {
            x = x + 4*(2*i+j)*(i+2*k);
            //if (i > j){
            //   y = y + 8*(i-j);
            //}else{
            //   y = y + 8*(j-i);
            //}
        }
    }
    return x;
}

k 只是一个常数:

int foobar(int a, int b, int N)
{
    int i, j, x;
    x = 0;
    for (i = 0; i <= N; i++) {
        for (j = i + 1; j <= N; j++) {
            x = x + 4*(2*i+j)*(i+2*256);
        }
    }
    return x;
}

内部表达式可以转换为:x += 8*i*i + 4096*i + 4*i*j + 2048*j.使用math将所有这些推送到外部循环:x += 8*i*i*(N-i) + 4096*i*(N-i) + 2*i*(N-i)*(N+i+1) + 1024*(N-i)*(N+i+1).

您可以展开上面的表达式,并应用平方和和多维数据集公式的总和来获得一个紧密的表单表达式,它应该比双嵌套循环运行得更快.我把它作为锻炼留给你.因此,i也j将被删除.

a并且b还应如果可能的话删除-因为a和b作为参数提供,但在你的代码从来没有使用过.

平方和和方块总和公式:

• Sum(x ²,x = 1..n)= n(n + 1)(2n + 1)/ 6
• 总和(X ³,X = 1..N)= N ²(N + 1)² /4

Answer 2

原来:

for (i = 0; i <= N; i++) {
    for (j = i + 1; j <= N; j++) {
        x = x + 4*(2*i+j)*(i+2*k);
        if (i > j){
           y = y + 8*(i-j);
        }else{
           y = y + 8*(j-i);
        }
    }
}

删除y计算:

for (i = 0; i <= N; i++) {
    for (j = i + 1; j <= N; j++) {
        x = x + 4*(2*i+j)*(i+2*k);
    }
}

拆分i,j,k:

for (i = 0; i <= N; i++) {
    for (j = i + 1; j <= N; j++) {
        x = x + 8*i*i + 16*i*k ;                // multiple of  1  (no j)
        x = x + (4*i + 8*k)*j ;                 // multiple of  j
    }
}

从外部移动它们(并删除运行N-i时间的循环):

for (i = 0; i <= N; i++) {
    x = x + (8*i*i + 16*i*k) * (N-i) ;
    x = x + (4*i + 8*k) * ((N*N+N)/2 - (i*i+i)/2) ;
}

Rewritting:

for (i = 0; i <= N; i++) {
    x = x +         ( 8*k*(N*N+N)/2 ) ;
    x = x +   i   * ( 16*k*N + 4*(N*N+N)/2 + 8*k*(-1/2) ) ;
    x = x +  i*i  * ( 8*N + 16*k*(-1) + 4*(-1/2) + 8*k*(-1/2) );
    x = x + i*i*i * ( 8*(-1) + 4*(-1/2) ) ;
}

重写 - 重新计算:

for (i = 0; i <= N; i++) {
    x = x + 4*k*(N*N+N) ;                            // multiple of 1
    x = x +   i   * ( 16*k*N + 2*(N*N+N) - 4*k ) ;   // multiple of i
    x = x +  i*i  * ( 8*N - 20*k - 2 ) ;             // multiple of i^2
    x = x + i*i*i * ( -10 ) ;                        // multiple of i^3
}

外部的另一个移动(并删除i循环):

x = x + ( 4*k*(N*N+N) )              * (N+1) ;
x = x + ( 16*k*N + 2*(N*N+N) - 4*k ) * ((N*(N+1))/2) ;
x = x + ( 8*N - 20*k - 2 )           * ((N*(N+1)*(2*N+1))/6);
x = x + (-10)                        * ((N*N*(N+1)*(N+1))/4) ;

上述循环删除都使用求和公式:

Sum(1,i = 0..n)= n + 1
Sum(i ¹,i = 0..n)= n(n + 1)/ 2
Sum(i ²,i = 0..n)= n第(n + 1)(2N + 1)/ 6
萨姆(I ³,I = 0..N)= N ²(N + 1)² /4

Answer 3

此函数与以下公式等效,该公式仅包含4个整数乘法和1个整数除法:

x = N * (N + 1) * (N * (7 * N + 8187) - 2050) / 6;

为此,我只需将嵌套循环计算的总和输入Wolfram Alpha:

sum (sum (8*i*i+4096*i+4*i*j+2048*j), j=i+1..N), i=0..N

这是解决方案的直接链接.在编码前思考.有时你的大脑可以比任何编译器更好地优化代码.

Answer 4

简单地扫描第一个例程,你注意到的第一件事是涉及"y"的表达式是完全未使用的并且可以被删除(正如你所做的那样).这进一步允许消除if/else(就像你一样).

剩下的是两个for循环和凌乱的表达.j下一步就是将不依赖的表达式分解出来.你删除了一个这样的表达式,但是(i<<3)(即,i*8)保留在内部循环中,并且可以被删除.

Pascal的回答提醒我,你可以使用循环步幅优化.首先移出(i<<3) * t内循环(调用它i1),然后在初始化循环时计算一个j1等于的值(i<<2) * t.在每次迭代增量j1通过4 * t(这是预先计算的常数).用你的内心表达替换x = x + i1 + j1;.

有人怀疑可能有某种方法可以将两个循环合二为一,但是我没有看到它.