3

各反復で呼び出される行列乗算を並列化することにより、かなり複雑な反復アルゴリズムのパフォーマンスを向上させようとしています。このアルゴリズムには 500 回の反復と約 10 秒かかります。しかし、行列の乗算を並列化した後は、13 秒まで遅くなります。しかし、同じ次元の行列乗算のみをテストしたところ、速度が向上しました。(私は 100x100 行列について話しています。)

最後に、アルゴリズム内の並列化をオフにし、反復ごとに次のコードを追加しました。これはまったく何もせず、おそらく長くはかからないはずです。

int j;

#pragma omp parallel for private(j)

for (int i = 0; i < 10; i++)
j = i;

繰り返しになりますが、このコードを使用しない同じアルゴリズムと比較すると、30% 遅くなります。

したがって、メイン アルゴリズム内で openmp を使用して並列化を 500 回呼び出すと、処理が遅くなります。この動作は私には非常に奇妙に見えますが、問題が何か手がかりはありますか?

メイン アルゴリズムは、VS2010、Win32 リリースによってコンパイルされたデスクトップ アプリケーションによって呼び出されます。私は Intel Core i3 (並列化により 4 つのスレッドが作成されます)、64 ビット Windows 7 で作業しています。

プログラムの構造は次のとおりです。

int internal_method(..)

{
...//no openmp here


 // the following code does nothing, has nothing to do with the rest of the program  and shouldn't take long,
 // but somehow adding of this code caused a 3 sec slowdown of the Huge_algorithm()
 double sum;
 #pragma omp parallel for private(sum)
 for (int i = 0; i < 10; i++)
    sum = i*i*i / (1.0 + i*i*i*i);

...//no openmp here
}


int Huge_algorithm(..)
{

 ...//no openmp here

    for (int i = 0; i < 500; i++)
    {
     .....// no openmp

     internal_method(..);

     ......//no openmp
    }

...//no openmp here
}

つまり、最後のポイントは、並列コードを 500 回呼び出すだけで (残りのアルゴリズムを省略した場合)、0.01 秒未満しかかからないが、巨大なアルゴリズム内で 500 回呼び出すと、3 秒の遅延が発生することです。アルゴリズム全体。そして、私が理解していないのは、小さな並列部分がアルゴリズムの残りの部分にどのように影響するかということです.

4

2 に答える 2

2

10 回の反復と単純な割り当ての場合、計算自体に比べて OpenMP のオーバーヘッドが多すぎると思います。ここで軽量に見えるのは、実際には、スレッド プールからではない複数のスレッドを管理および同期することです。ロックが関係している可能性があり、並列化するかどうかを見積もる際に MSVC がどれほど優れているかはわかりません。

ループ本体を大きくするか、反復回数を増やしてみてください (たとえば、1024*1024 回の反復を試してみてください)。

OpenMP Magick の例:

#pragma omp parallel for private(j)
for (int i = 0; i < 10; i++)
    j = i;

これは、コンパイラによって次のようにほぼ拡張される可能性があります。

const unsigned __cpu_count = __get_cpu_count();
const unsigned __j  = alloca (sizeof (unsigned) * __cpu_count);
__thread *__threads = alloca (sizeof (__thread) * __cpu_count);
for (unsigned u=0; u!=__cpu_count; ++u) {
    __init_thread (__threads+u);
    __run_thread ([u]{for (int i=u; i<10; i+=__cpu_count)
                          __j[u] = __i;}); // assume lambdas
}

for (unsigned u=0; u!=__cpu_count; ++u)
    __join (__threads+u);

で__init_thread()、特定のシステム コール__run_thread()を__join()呼び出す重要な関数です。

スレッドプールが使用されている場合は、最初のalloca()ものをそのようなものに置き換えます__pick_from_pool()。

(これ、名前と出力されたコードはすべて想像上のものであり、実際の実装は異なるように見えることに注意してください)

更新された質問について：

間違った粒度で並列化しているようです。スレッドにできるだけ多くのワークロードを配置するため、代わりに

 for (...) {
     #omp parallel ...
     for (...) {} 
 }

試す

 #omp parallel ...
 for (...) {
     for (...) {} 
 }

経験則: 相対的なオーバーヘッドを減らすために、ワークロードをスレッドごとに十分な大きさに保ちます。

于 2012-07-13T10:35:21.597 に答える
0

たぶん、j=iだけではコアCPU帯域幅の高利回りではありません。多分あなたはもっと譲歩する計算を試みるべきです。（たとえば、i * i * i * i * i*iをi+i + iで割った場合）

これをマルチコアCPUまたはGPUで実行していますか？

于 2012-07-13T10:07:01.470 に答える