c - 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. 共通部分式の削除
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、

生成されたコードには、いくつかの最適化を行ったにもかかわらず、元のコードよりも多くの行があり、実行時間は短くなりますが、元のコードほどではありません. 私は何を間違っていますか？

アセンブリ コードは両方とも非常に広範囲に及ぶため、貼り付けないでください。そのため、メインで関数「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

最初に:

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) ;
}

書き換え:

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
Sum(i ³ , i = 0..n) = n ² (n + 1) ² /4

Answer 2

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。数学を使用して、それらすべてを外側のループにプッシュします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
• Sum（x ³、x = 1..n）= n 2 ^（ n + 1）^2/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を排除することができます（あなたがしたように）。

残っているのは、2 つのforループと乱雑な表現です。依存しない式の部分を因数分解することjは、次のステップです。そのような式を 1 つ削除しましたが、(i<<3)(つまり、i * 8) は内側のループに残っており、削除できます。

パスカルの答えは、ループストライドの最適化を使用できることを思い出させてくれました。最初(i<<3) * tに内側のループから出て (それを と呼びますi1)、ループの初期化時に にj1等しい値を計算します(i<<2) * t。各反復で(事前に計算された定数である)だけインクリメントj1します。4 * t内部表現を に置き換えますx = x + i1 + j1;。

2 つのループを 1 つに組み合わせる何らかの方法があるのではないかと疑っていますが、私はそれを手に負えないとは考えていません。

Answer 5

私が見ることができるいくつかの他のもの。は必要ないのでy、その宣言と初期化を削除できます。

また、 と に渡された値は実際には使用されないためa、 との代わりにbこれらをローカル変数として使用できます。xt

また、毎回 512 に加算するのではなく、512 から始まり、反復ごとに 1 ずつ増加する iことに注意してください。t

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

この時点に到達すると、初期化とは別に、 と がそれぞれ 1 つの複数でのみ使用されることもj確認できます。これをループ ロジックで直接コーディングできます。したがって、次のようになります。iji<<3j<<2

int foobar(int a, int b, int N) {
    int i, j, iLimit, jLimit;
    a = 0;
    b = 512;
    iLimit = N << 3;
    jLimit = N << 2;
    for (i = 0; i <= iLimit; i+=8) {
        for (j = i >> 1 + 4; j <= jLimit; j+=4) {
            a = a + (i + j)*b;
        }
        b++;
    }
    return a;
}

Answer 6

わかりました...ここに私の解決策と、私が何をどのように行ったかを説明するインラインコメントがあります。

int foobar(int N)
{ // We eliminate unused arguments 
    int x = 0, i = 0, i2 = 0, j, k, z;

    // We only iterate up to N on the outer loop, since the
    // last iteration doesn't do anything useful. Also we keep
    // track of '2*i' (which is used throughout the code) by a 
    // second variable 'i2' which we increment by two in every
    // iteration, essentially converting multiplication into addition.
    while(i < N) 
    {           
        // We hoist the calculation '4 * (i+2*k)' out of the loop
        // since k is a literal constant and 'i' is a constant during
        // the inner loop. We could convert the multiplication by 2
        // into a left shift, but hey, let's not go *crazy*! 
        //
        //  (4 * (i+2*k))         <=>
        //  (4 * i) + (4 * 2 * k) <=>
        //  (2 * i2) + (8 * k)    <=>
        //  (2 * i2) + (8 * 512)  <=>
        //  (2 * i2) + 2048

        k = (2 * i2) + 2048;

        // We have now converted the expression:
        //      x = x + 4*(2*i+j)*(i+2*k);
        //
        // into the expression:
        //      x = x + (i2 + j) * k;
        //
        // Counterintuively we now *expand* the formula into:
        //      x = x + (i2 * k) + (j * k);
        //
        // Now observe that (i2 * k) is a constant inside the inner
        // loop which we can calculate only once here. Also observe
        // that is simply added into x a total (N - i) times, so 
        // we take advantange of the abelian nature of addition
        // to hoist it completely out of the loop

        x = x + (i2 * k) * (N - i);

        // Observe that inside this loop we calculate (j * k) repeatedly, 
        // and that j is just an increasing counter. So now instead of
        // doing numerous multiplications, let's break the operation into
        // two parts: a multiplication, which we hoist out of the inner 
        // loop and additions which we continue performing in the inner 
        // loop.

        z = i * k;

        for (j = i + 1; j <= N; j++) 
        {
            z = z + k;          
            x = x + z;      
        }

        i++;
        i2 += 2;
    }   

    return x;
}

説明のないコードは、次のようになります。

int foobar(int N)
{
    int x = 0, i = 0, i2 = 0, j, k, z;

    while(i < N) 
    {                   
        k = (2 * i2) + 2048;

        x = x + (i2 * k) * (N - i);

        z = i * k;

        for (j = i + 1; j <= N; j++) 
        {
            z = z + k;          
            x = x + z;      
        }

        i++;
        i2 += 2;
    }   

    return x;
}

これが役立つことを願っています。

Answer 7

int foobar(int N) //未使用の引き渡しを避けるため

{

int i, j, x=0;   //Remove unuseful variable, operation so save stack and Machine cycle

for (i = N; i--; )               //Don't check unnecessary comparison condition 

   for (j = N+1; --j>i; )

     x += (((i<<1)+j)*(i+512)<<2);  //Save Machine cycle ,Use shift instead of Multiply

return x;

}