6

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

特にOpenMPに関する他の同様の質問を読んで、1つの提案は、gccがシリアルコードをより適切に最適化することでした。ただし、以下のコンパイル済みコードの実行は、の場合のexport OMP_NUM_THREADS=12倍の速度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つのスレッドがピクセル配列の同じセルに書き込むことができないため、どこにも同期はありません。

誰かが何らかの論争があるかもしれない場所を提案できますか？試してみませんか？

前もって感謝します。

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

  • コンパイラgcc4.6（-O2最適化あり）
  • Ubuntu Linux 11.10
  • OpenMP 3
  • 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;
}

提案から、速度低下を引き起こすのはツリートラバーサルである可能性があります。他のいくつかの側面：サンプリング関数が呼び出されると、かなり多くの再帰が発生します（光線の再帰的なバウンス）-これはこれらの問題を引き起こす可能性がありますか？

4

4 に答える 4

4

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

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

残念ながら、stackoverflowで見たこの問題の解決策はすべてローカルです。つまり、rand（）が呼び出されるスコープで問題を処理します。代わりに、同期を必要とせずに、スレッドごとに独立した乱数生成を実装するために、誰でもプログラムで使用できる「迅速で汚い」ソリューションを提案します。

私はコードをテストしましたが、それは機能します-ロックはなく、threadrandの呼び出しの結果として目立った速度低下はありません。露骨な間違いを指摘してください。

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_

threadrand.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これで、を使用してスレッドのランダム状態を初期化し、その後、OpenMPで複数のスレッドを使用するときにを使用しinit_threadrand()て乱数を取得できます。threadrand()

于 2012-02-02T05:58:55.990 に答える
2

答えは、これを実行しているマシンがわからず、computePixel関数のコードを実際に確認していなくても、依存しているということです。

コードのパフォーマンスに影響を与える可能性のある要因はかなりありますが、頭に浮かぶのはキャッシュの配置です。おそらく、データ構造、およびツリーについて言及したことは、キャッシュにはあまり理想的ではなく、CPUは、データがRAMから来るのを待つことになります。これは、データがキャッシュに収まらないためです。キャッシュラインの配置が間違っていると、そのようなことが発生する可能性があります。CPUがRAMからのものが来るのを待たなければならない場合、スレッドがコンテキストスイッチアウトされ、別のスレッドが実行される可能性があります。

OSスレッドスケジューラは非決定論的であるため、スレッドがいつ実行されるかは予測できません。そのため、スレッドがあまり実行されていない場合、またはCPUコアをめぐって競合している場合は、処理速度が低下する可能性があります。

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

他にもいくつかの要因がありますが、頭のてっぺんからは覚えていませんが、スレッドについて読んでみることをお勧めします。それは複雑で広範囲にわたる主題です。そこにはたくさんの資料があります。

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

于 2012-01-23T23:45:28.140 に答える
1

1つの強力な可能性は、偽共有です。ピクセルを順番に計算しているように見えるため、各スレッドがインターリーブされたピクセルで作業している可能性があります。これは通常、非常に悪いことです。

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

これを修正するには、各スレッドが本当に独立した領域で機能することを確認する必要があります。現在、あなたは行を分割しているようです（OMPを知らないので、私はポジティブではありません）。これが機能するかどうかは、行の大きさによって異なりますが、それでも各行の終わりは次の行の始まりと重なります（キャッシュラインの観点から）。画像を4つのブロックに分割し、各スレッドを一連の連続した行で機能させることをお勧めします（1..10 11..20 21..30 31..40など）。これにより、共有が大幅に減少します。

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

于 2012-01-24T08:24:56.170 に答える
1

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

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

于 2012-01-24T15:10:01.813 に答える