プログラムを 4 つのスレッドに分割すると、単一スレッドよりも遅くなります

https://stackoverflow.com/questions/8980056

12-11-2019
|

質問

私はここ 1 週間レイトレーサを書いてきましたが、マルチスレッドが意味を成すほど十分に機能するところまで来ました。OpenMP を使用して並列化しようとしましたが、より多くのスレッドで実行すると、1 つのスレッドで実行するよりも実際には遅くなります。

他の同様の質問、特に OpenMP に関する質問を読んだところ、gcc はシリアルコードをより適切に最適化するという提案が 1 つありました。ただし、以下のコンパイルされたコードを実行すると、 export OMP_NUM_THREADS=1 の2倍の速さです export OMP_NUM_THREADS=4. 。つまり、どちらの実行でも同じコンパイルされたコードです。

プログラムを実行すると、 time:

> export OMP_NUM_THREADS=1; time ./raytracer
real    0m34.344s
user    0m34.310s
sys     0m0.008s


> export OMP_NUM_THREADS=4; time ./raytracer
real    0m53.189s
user    0m20.677s
sys     0m0.096s

ユーザー時間は実際よりもはるかに短い, これは、複数のコアを使用する場合には珍しいことです。 ユーザー より大きい必要があります本物複数のコアが同時に実行されているためです。

OpenMPを使用して並列化したコード

void Raytracer::render( Camera& cam ) {

    // let the camera know to use this raytracer for probing the scene
    cam.setSamplingFunc(getSamplingFunction());

    int i, j;

    #pragma omp parallel private(i, j)
    {

        // Construct a ray for each pixel.
        #pragma omp for schedule(dynamic, 4)
        for (i = 0; i < cam.height(); ++i) {
            for (j = 0; j < cam.width(); ++j) {
                cam.computePixel(i, j);
            }
        }
    }
}

読むときこの質問自分の答えを見つけたと思いました。スレッド間で乱数を生成するための状態を保持するために、それ自体への呼び出しを同期する gclib rand() の実装について説明します。私はモンテカルロサンプリングに rand() を頻繁に使用しているので、それが問題だと思いました。rand への呼び出しを削除し、単一の値に置き換えましたが、複数のスレッドを使用すると依然として速度が低下します。 編集：おっと これは正しくテストできなかったことがわかりました。ランダムな値だったのです。

これらの説明は終わりましたので、各通話で何が行われているかの概要を説明します。 computePixel, 、解決策が見つかることを願っています。

私のレイトレーサーには基本的にシーンツリーがあり、その中にすべてのオブジェクトが含まれています。この木は期間中に何度も横切られます computePixel ただし、オブジェクトの交差がテストされる場合、このツリーまたは他のオブジェクトへの書き込みは行われません。 computePixel 基本的にシーンを何度も読み取り、オブジェクトのメソッド (すべて const メソッド) を呼び出し、最後に単一の値を独自のピクセル配列に書き込みます。これは、複数のスレッドが同じメンバー変数に書き込もうとすることを私が知っている唯一の部分です。2 つのスレッドがピクセル配列内の同じセルに書き込むことができないため、どこにも同期はありません。

何らかの競合が発生する可能性のある場所を誰かが提案できますか?試してみるべきことは何ですか？

よろしくお願いします。

編集：申し訳ありませんが、私のシステムに関する詳細情報を提供しなかったのは愚かでした。

コンパイラ gcc 4.6 (-O2 最適化あり)
Ubuntu Linux 11.10
OpenMP3
Intel i3-2310M クアッドコア 2.1Ghz (現時点では私のラップトップ上)

ピクセルを計算するコード:

class Camera {

    // constructors destructors
    private:
        // this is the array that is being written to, but not read from.
        Colour* _sensor; // allocated using new at construction.
}

void Camera::computePixel(int i, int j) const {

    Colour col;

    // simple code to construct appropriate ray for the pixel
    Ray3D ray(/* params */);
    col += _sceneSamplingFunc(ray); // calls a const method that traverses scene. 

    _sensor[i*_scrWidth+j] += col;
}

提案によると、速度低下の原因はツリートラバースである可能性があります。その他のいくつかの側面:サンプリング関数が呼び出されると、かなり多くの再帰が含まれます (光線の再帰反射)。これがこれらの問題を引き起こす可能性がありますか?

解決

提案してくれた皆さんに感謝します。ただし、さらにプロファイリングを行い、他の要因を取り除いた後、乱数を生成します。した犯人であることが判明する。

上記の質問で概説したように、 rand() は呼び出しから次の呼び出しまでその状態を追跡する必要があります。複数のスレッドがこの状態を変更しようとすると、競合状態が発生するため、glibc のデフォルトの実装は次のようになります。 すべての通話をロックする, 、関数をスレッドセーフにします。これはパフォーマンスにとってひどいことです。

残念ながら、スタックオーバーフローで私が見たこの問題の解決策はすべてローカルなものです。問題に対処する rand() が呼び出されるスコープ内. 。その代わりに、私は誰でも自分のプログラムで使用でき、同期を必要とせずにスレッドごとに独立した乱数生成を実装できる「手っ取り早くて汚い」ソリューションを提案します。

コードをテストしたところ、正常に動作しました。ロックは発生せず、threadrand の呼び出しの結果として顕著な速度低下もありませんでした。明らかな間違いがありましたら遠慮なくご指摘ください。

スレッドランド.h

#ifndef _THREAD_RAND_H_
#define _THREAD_RAND_H_

// max number of thread states to store
const int maxThreadNum = 100;

void init_threadrand();

// requires openmp, for thread number
int threadrand();

#endif // _THREAD_RAND_H_

スレッドランド.cpp

#include "threadrand.h"
#include <cstdlib>
#include <boost/scoped_ptr.hpp>
#include <omp.h>

// can be replaced with array of ordinary pointers, but need to
// explicitly delete previous pointer allocations, and do null checks.
//
// Importantly, the double indirection tries to avoid putting all the
// thread states on the same cache line, which would cause cache invalidations
// to occur on other cores every time rand_r would modify the state.
// (i.e. false sharing)
// A better implementation would be to store each state in a structure
// that is the size of a cache line
static boost::scoped_ptr<unsigned int> randThreadStates[maxThreadNum];

// reinitialize the array of thread state pointers, with random
// seed values.
void init_threadrand() {
    for (int i = 0; i < maxThreadNum; ++i) {
        randThreadStates[i].reset(new unsigned int(std::rand()));
    }
}

// requires openmp, for thread number, to index into array of states.
int threadrand() {
    int i = omp_get_thread_num();
    return rand_r(randThreadStates[i].get());
}

これで、スレッドのランダムな状態を初期化できるようになりました。 main を使用して init_threadrand(), 、その後、次を使用して乱数を取得します threadrand() OpenMP で複数のスレッドを使用する場合。

他のヒント

答えは、これを実行しているマシンを知らず、コードを実際に見なくても、ということです。 computePixel 機能、それは依存します。

コードのパフォーマンスに影響を与える可能性のある要因は数多くありますが、思い浮かぶのはキャッシュのアライメントです。おそらく、データ構造 (ツリーについて言及しましたが) はキャッシュに理想的ではなく、CPU はデータをキャッシュに収めることができないため、最終的に RAM からのデータを待つことになります。キャッシュラインのアライメントが間違っていると、そのような問題が発生する可能性があります。CPU が RAM からの情報の取得を待機する必要がある場合、スレッドはコンテキストでスイッチアウトされ、別のスレッドが実行される可能性があります。

OS のスレッドスケジューラは非決定的であるため、いつスレッドが実行されるかどうかは予測できないため、スレッドがあまり実行されていないか、CPU コアを競合している場合には、動作が遅くなる可能性があります。

スレッドの親和性も重要な役割を果たします。スレッドは特定のコアでスケジュールされ、 通常は このスレッドを同じコア上に維持しようとします。複数のスレッドが 1 つのコアで実行されている場合、それらのスレッドは同じコアを共有する必要があります。動作が遅くなる可能性があるもう 1 つの理由。パフォーマンス上の理由から、特定のスレッドがコア上で実行されると、別のコアに交換する正当な理由がない限り、通常はそこに保持されます。

他にもいくつかの要因がありますが、それは頭からは思い出せませんが、スレッドについて少し読んでおくことをお勧めします。それは複雑で広範な主題です。そこにはたくさんの材料があります。

最後に書き込まれるデータは、他のスレッドが実行できる必要があるデータですか computePixel ?

一つの有力な可能性は、 フォールスシェアリング. 。ピクセルを順番に計算しているように見えるため、各スレッドがインターリーブされたピクセルを処理している可能性があります。これは通常、非常に悪いことです。

何が起こっている可能性があるかというと、各スレッドが別のスレッドで書き込まれたピクセルの値の隣にピクセルの値を書き込もうとしているということです (すべてのスレッドがセンサーアレイに書き込みます)。これら 2 つの出力値が同じ CPU キャッシュラインを共有する場合、CPU はプロセッサ間でキャッシュをフラッシュする必要があります。これにより、CPU 間で過剰な量のフラッシュが発生し、動作が比較的遅くなります。

これを修正するには、各スレッドが独立した領域で実際に動作することを確認する必要があります。現時点では、行で分割しているようです (OMP がわからないので、確信はありません)。これが機能するかどうかは行の大きさによって異なりますが、それでも各行の終わりは (キャッシュラインの観点から) 次の行の始まりと重なります。画像を 4 つのブロックに分割し、各スレッドが一連の連続した行 (1..10 11..20 21..30 31..40 など) を処理するようにしてみるとよいでしょう。これにより、共有が大幅に削減されます。

定数データの読み取りについて心配する必要はありません。データブロックが変更されない限り、各スレッドはこの情報を効率的に読み取ることができます。ただし、定数データに含まれる変更可能なデータには注意してください。

ちょうど見たところ、インテル i3-2310M 実際には 4 コアではなく、2 コアとハイパースレッディングを備えています。たった 2 つのスレッドでコードを実行してみて、それが役立つかどうかを確認してください。一般に、大量の計算がある場合、ハイパースレッディングはまったく役に立たないことがわかりました。私のラップトップではハイパースレッディングをオフにしたので、プロジェクトのコンパイル時間が大幅に短縮されました。

実際、BIOS にアクセスして HT をオフにするだけです。これは開発/計算マシンには役に立ちません。

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow