3

モンテカルロ法を使用して PI を計算する小さなプログラムを C で実装しました (主に個人的な関心とトレーニングのため)。基本的なコード構造を実装した後、計算をスレッド化して実行できるようにするコマンドライン オプションを追加しました。

大幅な高速化を期待していましたが、がっかりしました。コマンドラインの概要は明確である必要があります。PI を概算するために行われる反復の最終回数は、コマンドライン経由-iterationsで渡された回数の積です。-threads空白-threadsのままにすると、デフォルトで1スレッドになり、メイン スレッドで実行されます。

以下のテストは、合計 8000 万回の反復でテストされています。

Windows 7 64 ビット (Intel Core2Duo マシン) の場合:

Windows 統計

Cygwin GCC 4.5.3 を使用してコンパイル:gcc-4 pi.c -o pi.exe -O3

Ubuntu/Linaro 12.04 (8 コア AMD) の場合:

Linux 統計

GCC 4.6.3 を使用してコンパイル:gcc pi.c -lm -lpthread -O3 -o pi

パフォーマンス

Windows では、スレッド化されたバージョンは非スレッド化よりも数ミリ秒高速です。正直なところ、もっと良いパフォーマンスを期待していました。Linux では、うーん！一体何？なぜ 2000% も長くかかるのでしょうか? もちろん、これは実装に大きく依存するため、ここで説明します。コマンドライン引数の解析が完了し、計算が開始された後の抜粋:

    // Begin computation.
    clock_t t_start, t_delta;
    double pi = 0;

    if (args.threads == 1) {
        t_start = clock();
        pi = pi_mc(args.iterations);
        t_delta = clock() - t_start;
    }
    else {
        pthread_t* threads = malloc(sizeof(pthread_t) * args.threads);
        if (!threads) {
            return alloc_failed();
        }

        struct PIThreadData* values = malloc(sizeof(struct PIThreadData) * args.threads);
        if (!values) {
            free(threads);
            return alloc_failed();
        }

        t_start = clock();
        for (i=0; i < args.threads; i++) {
            values[i].iterations = args.iterations;
            values[i].out = 0.0;
            pthread_create(threads + i, NULL, pi_mc_threaded, values + i);
        }
        for (i=0; i < args.threads; i++) {
            pthread_join(threads[i], NULL);
            pi += values[i].out;
        }
        t_delta = clock() - t_start;

        free(threads);
        threads = NULL;
        free(values);
        values = NULL;

        pi /= (double) args.threads;
    }

Whilepi_mc_threaded()は次のように実装されます。

struct PIThreadData {
    int iterations;
    double out;
};

void* pi_mc_threaded(void* ptr) {
    struct PIThreadData* data = ptr;
    data->out = pi_mc(data->iterations);
}

完全なソース コードはhttp://pastebin.com/jptBTgwrにあります。

質問

どうしてこれなの？Linux でこの極端な違いが生じるのはなぜですか? 計算にかかる時間は、少なくとも元の時間の 3/4 になると予想していました。pthreadもちろん、単にライブラリの使い方を誤った可能性もあります。この場合に正しい方法を明確にすることは非常に良いでしょう。

4

3 に答える 3

5

問題は、glibc の実装では、rand()が呼び出され__random()、それが

long int
__random ()
{
  int32_t retval;

  __libc_lock_lock (lock);

  (void) __random_r (&unsafe_state, &retval);

  __libc_lock_unlock (lock);

  return retval;
}

__random_r実際の作業を行う関数への各呼び出しをロックします。

したがって、 を使用するスレッドが複数あるとすぐに、rand()へのほぼすべての呼び出しで各スレッドが他のスレッドを待機するようになりrand()ます。random_r()各スレッドで独自のバッファを直接使用すると、はるかに高速になります。

于 2013-05-26T15:08:36.757 に答える
1

パフォーマンスとスレッド化は黒魔術です。答えは、スレッド化に使用されるコンパイラとライブラリの詳細、カーネルがそれをどれだけうまく処理するかなどによって異なります。もっとゆっくり 。これが、私たちがスレッド作業を行っている多くの作業が JVM または JVM に似た言語で機能するようになった理由の 1 つです。ランタイム JVM の動作は信頼できます。全体的な速度はプラットフォームによって異なる場合がありますが、そのプラットフォームでは一貫しています。さらに、Windows では表示されない可能性があるタイミングが原因で明らかになった、隠れた待機/競合状態がいくつかある場合があります。

言語を変更する立場にある場合は、Scala または D を検討してください。Scala は Java のアクター駆動モデルの後継であり、D は C の後継です。どちらの言語もルーツを示しています。C で記述できる場合は、D を使用する必要があります。問題ありません。ただし、どちらの言語もアクター モデルを実装しています。スレッドプールや競合状態などはもうありません!!!!!!

于 2013-05-26T15:08:21.283 に答える
1

比較のために、あなたのアプリを Borland C++ でコンパイルして Windows Vista で試してみたところ、2 スレッド バージョンはシングル スレッドのほぼ 2 倍の速さで実行されました。

pi.exe -iterations 20000000 -stats -threads 1
3.141167

Number of iterations:  20000000
Method:                Monte Carlo
Evaluation time:       12.511000 sec
Threads:               Main


pi.exe -iterations 10000000 -stats -threads 2
3.142397

Number of iterations:  20000000
Method:                Monte Carlo
Evaluation time:       6.584000 sec
Threads:               2

これは、スレッドセーフなランタイム ライブラリに対してコンパイルされます。シングル スレッド ライブラリを使用すると、どちらのバージョンもスレッドセーフな速度の 2 倍で実行されます。

pi.exe -iterations 20000000 -stats -threads 1
3.141167

Number of iterations:  20000000
Method:                Monte Carlo
Evaluation time:       6.458000 sec
Threads:               Main


pi.exe -iterations 10000000 -stats -threads 2
3.141314

Number of iterations:  20000000
Method:                Monte Carlo
Evaluation time:       3.978000 sec
Threads:               2

したがって、2 スレッド バージョンは依然として 2 倍高速ですが、シングル スレッド ライブラリの 1 スレッド バージョンは、スレッド セーフ ライブラリの 2 スレッド バージョンよりも実際には高速です。

Borland の rand 実装を見ると、彼らはスレッド セーフな実装のシードにスレッド ローカル ストレージを使用しているため、スレッド化されたコードに glibc のロックと同じような悪影響を与えることはありませんが、スレッド セーフな実装は明らかにシングルスレッド実装。

ただし、randどちらの場合も、コンパイラの実装がおそらく主なパフォーマンスの問題であるということです。

アップデート

rand_01シードにローカル変数を使用して呼び出しを Borland の関数のインライン実装に置き換えようとしrandたところ、結果は 2 スレッドの場合で一貫して 2 倍速くなりました。

更新されたコードは次のようになります。

#define MULTIPLIER      0x015a4e35L
#define INCREMENT       1

double pi_mc(int iterations) {
    unsigned seed = 1;
    long long inner = 0;
    long long outer = 0;
    int i;
    for (i=0; i < iterations; i++) {
        seed = MULTIPLIER * seed + INCREMENT;
        double x = ((int)(seed >> 16) & 0x7fff) / (double) RAND_MAX;

        seed = MULTIPLIER * seed + INCREMENT;
        double y = ((int)(seed >> 16) & 0x7fff) / (double) RAND_MAX;

        double d = sqrt(pow(x, 2.0) + pow(y, 2.0));
        if (d <= 1.0) {
            inner++;
        }
        else {
            outer++;
        }
    }

    return ((double) inner / (double) iterations) * 4;
}

実装が進むにつれてそれがどれほど良いかはわかりませんがrand、少なくとも Linux で試して、パフォーマンスに違いがあるかどうかを確認する価値はあります。

于 2013-05-26T15:56:10.890 に答える