11

同じ計算を 2 つの異なる方法で実行する次の 2 つのプログラムを考えてみましょう。

// v1.c
#include <stdio.h>
#include <math.h>
int main(void) {
   int i, j;
   int nbr_values = 8192;
   int n_iter = 100000;
   float x;
   for (j = 0; j < nbr_values; j++) {
      x = 1;
      for (i = 0; i < n_iter; i++)
         x = sin(x);
   }
   printf("%f\n", x);
   return 0;
}

と

// v2.c
#include <stdio.h>
#include <math.h>
int main(void) {
   int i, j;
   int nbr_values = 8192;
   int n_iter = 100000;
   float x[nbr_values];
   for (i = 0; i < nbr_values; ++i) {
      x[i] = 1;
   }
   for (i = 0; i < n_iter; i++) {
      for (j = 0; j < nbr_values; ++j) {
         x[j] = sin(x[j]);
      }
   }
   printf("%f\n", x[0]);
   return 0;
}

gcc 4.7.2 を使用してそれらをコンパイルし-O3 -ffast-math、Sandy Bridge ボックスで実行すると、2 番目のプログラムは最初のプログラムの 2 倍の速度になります。

何故ですか？

疑わしい点の 1 つは、 のiループの連続する反復間のデータ依存性v1です。ただし、完全な説明が何であるかはよくわかりません。

(なぜ私の python/numpy の例は純粋な C 実装よりも速いのか? に触発された質問)

編集：

の生成されたアセンブリは次のv1とおりです。

        movl    $8192, %ebp
        pushq   %rbx
LCFI1:
        subq    $8, %rsp
LCFI2:
        .align 4
L2:
        movl    $100000, %ebx
        movss   LC0(%rip), %xmm0
        jmp     L5
        .align 4
L3:
        call    _sinf
L5:
        subl    $1, %ebx
        jne     L3
        subl    $1, %ebp
        .p2align 4,,2
        jne     L2

およびv2:

        movl    $100000, %r14d
        .align 4
L8:
        xorl    %ebx, %ebx
        .align 4
L9:
        movss   (%r12,%rbx), %xmm0
        call    _sinf
        movss   %xmm0, (%r12,%rbx)
        addq    $4, %rbx
        cmpq    $32768, %rbx
        jne     L9
        subl    $1, %r14d
        jne     L8
4

2 に答える 2

15

ループ構造をまとめて無視し、 への呼び出しの順序だけを考えてsinください。 v1次のことを行います。

x <-- sin(x)
x <-- sin(x)
x <-- sin(x)
...

つまり、 の各計算はsin( )、前の呼び出しの結果が利用可能になるまで開始できません。前の計算が完了するまで待機する必要があります。これは、 への N 回の呼び出しにsin必要な合計時間は、1 回の評価の待ち時間の 819200000 倍であることを意味しsinます。

一方v2、 では、次のことを行います。

x[0] <-- sin(x[0])
x[1] <-- sin(x[1])
x[2] <-- sin(x[2])
...

sinへの各呼び出しは、前の呼び出しに依存しないことに注意してください。事実上、呼び出しsinはすべて独立しており、プロセッサは、必要なレジスタと ALU リソースが利用可能になるとすぐに (前の計算が完了するのを待たずに)、それぞれの呼び出しを開始できます。したがって、所要時間はレイテンシではなく、sin 関数のスループットv2の関数であるため、大幅に短い時間で終了する可能性があります。

また、DeadMG は正しく、v1とv2は形式的に同等であり、完全な世界では、コンパイラは両方を 100000 回の評価の単一のチェーンに最適化しますsin(またはコンパイル時に結果を単に評価します)。悲しいことに、私たちは不完全な世界に住んでいます。

于 2013-01-22T21:51:39.483 に答える
0

最初の例では、sin を 100000 ループ、8192 回実行します。

2 番目の例では、sin の 8192 ループを 100000 回実行します。

それ以外は、結果の保存方法が異なりますが、違いはありません。

ただし、違いを生むのは、2 番目のケースではループごとに入力が変更されていることです。したがって、ループ内の特定の時点で、sin 値の計算がはるかに簡単になると思われます。そして、それは大きな違いを生む可能性があります。sin の計算は完全に自明ではなく、終了条件に達するまでループする一連の計算です。

于 2013-01-22T22:02:17.040 に答える