より多くのスレッドを使用すると、プログラムの実行が遅くなる原因は何ですか?

https://stackoverflow.com/questions/612860

03-07-2019
|

質問

この質問は私と同じプログラムに関するものです以前に質問された. 。要約すると、次のようなループ構造を持つプログラムがあります。

for (int i1 = 0; i1 < N; i1++)
  for (int i2 = 0; i2 < N; i2++)
    for (int i3 = 0; i3 < N; i3++)
      for (int i4 = 0; i4 < N; i4++)
        histogram[bin_index(i1, i2, i3, i4)] += 1;

bin_index は引数の完全に決定的な関数であり、この質問の目的では、共有状態を使用または変更しません。つまり、明らかにリエントラントです。

私は最初、単一のスレッドを使用するためにこのプログラムを作成しました。次に、複数のスレッドを使用するように変換しました。 n 外側のループのすべての反復を実行します。 i1 % nthreads == n. 。したがって、各スレッドで実行される関数は次のようになります

for (int i1 = n; i1 < N; i1 += nthreads)
  for (int i2 = 0; i2 < N; i2++)
    for (int i3 = 0; i3 < N; i3++)
      for (int i4 = 0; i4 < N; i4++)
        thread_local_histogram[bin_index(i1, i2, i3, i4)] += 1;

そしてすべての thread_local_histogramはメインスレッドの最後に合計されます。

奇妙なことは次のとおりです。特定のサイズの計算に対して 1 スレッドだけでプログラムを実行すると、約 6 秒かかります。2 つまたは 3 つのスレッドでまったく同じ計算を実行すると、約 9 秒かかります。何故ですか？デュアルコア CPU を使用しているため、2 スレッドを使用した方が 1 スレッドよりも高速になると予想されます。このプログラムはミューテックスやその他の同期プリミティブを使用しないため、2 つのスレッドを並行して実行できるはずです。

参考のために：からの典型的な出力 time (これは Linux 上です) 1 つのスレッドの場合:

real    0m5.968s
user    0m5.856s
sys     0m0.064s

そして 2 つのスレッド:

real    0m9.128s
user    0m10.129s
sys     0m6.576s

コードは次のとおりです http://static.ellipsix.net/ext-tmp/distintegral.ccs

追伸まさにこの種のことのために設計されたライブラリがあり、おそらくパフォーマンスが向上する可能性があることは知っていますが、それが私の最後の質問に関するものでしたので、それらの提案を再度聞く必要はありません。(さらに、学習体験として pthread を使用したかったのです。)

解決

あなたの質問は何が「できる」かということでしたので、他の返信でこれまで述べたことはすべて一般的に当てはまります...しかし、実際のコードを見たので、私の最初の推測は、random() 関数の使用によりすべてが遅くなっているということです。なぜ？

見てください、random はメモリ内にグローバル変数を保持し、そこで計算された最後のランダム値を保存します。random() を呼び出すたびに (1 つの関数内で 2 回呼び出していることになります)、このグローバル変数の値が読み取られ、計算が実行されます (それほど高速ではありません。random() 単独では遅い関数です)、結果を返す前に結果をそこに書き込みます。このグローバル変数はスレッドごとではなく、すべてのスレッド間で共有されます。したがって、キャッシュポイズニングに関して私が書いたことは、ここでは常に当てはまります (スレッドごとに配列を分離することで配列に対してキャッシュポイズニングを回避した場合でも、これはとても賢いですね！）。この値はいずれかのコアのキャッシュで常に無効になるため、メモリから再フェッチする必要があります。ただし、スレッドが 1 つしかない場合は、そのようなことは起こりません。この変数は永続的に何度も何度もアクセスされるため、最初に読み取られた後はキャッシュから離れることはありません。

さらに悪いことに、glibc には、random() のスレッドセーフバージョンがあります。私はソースを見てそれを確認しました。これは実際には良いアイデアのように見えますが、random() 呼び出しごとにミューテックスがロックされ、メモリがアクセスされ、ミューテックスがロック解除されることを意味します。したがって、2 つのスレッドがまったく同じ瞬間にランダムを呼び出すと、1 つのスレッドが数 CPU サイクルの間ブロックされます。ただし、これは実装固有のものですが、私の知る限り、random() がスレッドセーフである必要はありません。C 標準ではそもそもスレッドの概念さえ認識していないため、ほとんどの標準 lib 関数はスレッドセーフである必要はありません。同時に呼び出していない場合、ミューテックスは速度に影響しません (単一のスレッドアプリでもミューテックスをロック/ロック解除する必要があるため) が、キャッシュポイズニングが再び適用されます。

各スレッドに必要な数の乱数を含む、各スレッドの乱数を含む配列を事前に構築できます。スレッドを生成する前にメインスレッドでそれを作成し、すべてのスレッドに渡す構造体ポインターにそれへの参照を追加します。次に、そこから乱数を取得します。

あるいは、地球上で「最良の」乱数が必要ない場合は、独自の乱数ジェネレーターを実装してください。これは、状態を保持するためにスレッドごとのメモリで動作します。その乱数ジェネレーターは、システムの組み込みジェネレーターよりもさらに高速である可能性があります。

Linux のみのソリューションがうまく機能する場合は、以下を使用できます。ランダム_r. 。これにより、呼び出しごとに状態を渡すことができます。スレッドごとに一意の状態オブジェクトを使用するだけです。ただし、この関数は glibc 拡張機能であり、おそらく他のプラットフォーム (C 標準の一部でも POSIX 標準の一部でもありません) ではサポートされていません。私の知る限り、この関数は Mac OS X には存在しません。たとえば、Solaris にも存在しない可能性があります。 FreeBSD)。

独自の乱数ジェネレーターを作成するのは、実際にはそれほど難しくありません。実際の乱数が必要な場合は、そもそもrandom()を使用すべきではありません。Random は、擬似乱数 (一見ランダムに見えますが、ジェネレーターの内部状態を知っていれば予測可能な数値) のみを作成します。適切な uint32 乱数を生成するコードは次のとおりです。

static uint32_t getRandom(uint32_t * m_z, uint32_t * m_w)
{
    *m_z = 36969 * (*m_z & 65535) + (*m_z >> 16);
    *m_w = 18000 * (*m_w & 65535) + (*m_w >> 16);
    return (*m_z << 16) + *m_w;
}

何らかの方法で m_z と m_w を「シード」することが重要です。そうしないと、結果はまったくランダムになりません。シード値自体はすでにランダムになっているはずですが、ここではシステム乱数ジェネレーターを使用できます。

uint32_t m_z = random();
uint32_t m_w = random();
uint32_t nextRandom;

for (...) {
    nextRandom = getRandom(&m_z, &m_w);
    // ...
}

この方法では、すべてのスレッドでrandom()を2回呼び出すだけで済み、その後は独自のジェネレータを使用します。ところで、二重ランダム (0 から 1 の間) が必要な場合は、上記の関数を簡単にラップできます。

static double getRandomDouble(uint32_t * m_z, uint32_t * m_w)
{
    // The magic number below is 1/(2^32 + 2).
    // The result is strictly between 0 and 1.
    return (getRandom(m_z, m_w) + 1) * 2.328306435454494e-10;
}

コードにこの変更を加えてみて、ベンチマークの結果がどうなるか教えてください :-)

他のヒント

これに関するさらなるコメントを避けるために：返信を書いたとき、質問者は彼のソースへのリンクをまだ投稿していないので、返信を特定の問題に合わせることができませんでした。「できる」という一般的な質問にのみ答えていました。そのような問題を引き起こすので、私はこれが彼のケースに必ずしも当てはまるとは言いませんでした。彼が彼のソースへのリンクを投稿したとき、私は別の返信を書きました。それはまさに彼の問題にのみ焦点を当てています（これは他の返信で説明したようにrandom（）関数の使用が原因です）。ただし、この投稿の質問はまだ「より多くのスレッドを使用するとプログラムの実行速度が遅くなるのはなぜですか」です。「特定のアプリケーションの実行速度を遅くする理由」ではなく、一般的な回答（一般的な質問-＆gt;一般的な回答、特定の質問-＆gt;特定の回答）を変更する必要はありません。

1）キャッシュポイズニング
すべてのスレッドは、メモリのブロックである同じ配列にアクセスします。各コアには、メモリアクセスを高速化するための独自のキャッシュがあります。配列から読み取るだけでなく、コンテンツも変更するため、コンテンツは実際のキャッシュではなく、実際のメモリでのみ変更されます（少なくともすぐには変更されません）。問題は、他のコア上の他のスレッドがメモリの重複部分をキャッシュする可能性があることです。コア1がキャッシュ内の値を変更した場合、この値が変更されたことをコア2に通知する必要があります。コア2のキャッシュコンテンツを無効にし、コア2がメモリからデータを再読み取りする必要があるため、処理が遅くなります。キャッシュポイズニングは、マルチコアまたはマルチCPUマシンでのみ発生します。 CPUが1つでコアが1つだけの場合、これは問題ありません。そのため、それが問題であるかどうかを確認するには、1つのコアを無効にし（ほとんどのOSでは可能です）、テストを繰り返します。ほぼ同じ速度になった場合、それが問題でした。

2）メモリバーストの防止
ファイルがHDから読み取られる場合と同様に、メモリをバーストで連続して読み取る場合、最も速く読み取られます。 PCが市場で最高のメモリを搭載している場合でも、メモリ内の特定のポイントのアドレス指定は実際には非常に遅くなります（HDの「シーク時間」のように）。ただし、この点に対処すると、順次読み取りは高速になります。最初のアドレス指定では、行インデックスと列インデックスを送信し、最初のデータにアクセスする前に常に待機時間を設けます。このデータが存在すると、CPUはバーストを開始します。データはまだ途中ですが、次のバーストの要求を既に送信しています。（常に「次の行をお願いします」リクエストを送信することで）バーストを維持している限り、RAMは可能な限り高速でデータをポンプアウトし続けます（実際、これは非常に高速です！）。バーストが機能するのは、データが連続して読み取られ、メモリアドレスが上方に増加した場合のみです（高アドレスから低アドレスにバーストすることはできません）。現在2つのスレッドが同時に実行され、両方がメモリの読み取り/書き込みを続けている場合、両方とも完全に異なるメモリアドレスから、スレッド2がデータの読み取り/書き込みを行うたびに、スレッド1のバーストを中断する必要があります。さらに多くのスレッドがある場合、この問題は悪化します。この問題は、シングルコアCPUが1つしかないシステムでも発生します。

BTWはコアよりも多くのスレッドを実行しているため、プロセスが速くなることはありません（3つのスレッドについて述べたように）、むしろ遅くなります（スレッドコンテキストスイッチには処理スループットを低下させる副作用があります）-実行するのとは異なります一部のスレッドが特定のイベントでスリープまたはブロックしているため、アクティブにデータを処理できないため、スレッドが増えます。その場合、コアよりも多くのスレッドを実行するのが理にかなっています。

キャッシュラインのバウンスが表示されます。ヒストグラムバケットの競合状態により、間違った結果が得られないことに本当に驚いています。

1つの可能性は、スレッドの作成にかかる時間が、スレッドを使用することで得られる節約を超えることです。 O（n ^ 4）操作の経過時間が6秒しかない場合、Nはそれほど大きくないと思います。

複数のスレッドが異なるコアまたはCPUで実行されるという保証もありません。 Linuxでのデフォルトのスレッドアフィニティが何なのかわかりません。両方のスレッドがシングルコアで実行されるため、このようなCPUを集中的に使用するコードの利点が無効になる可能性があります。

この記事では、デフォルトのスレッドアフィニティとその方法について詳しく説明しています。特定のコアでスレッドが実行されるようにコードを変更します。

スレッドは配列の同じ要素に同時にアクセスしませんが、配列全体がいくつかのメモリページに配置される場合があります。 1つのコア/プロセッサがそのページに書き込むとき、他のすべてのプロセッサのキャッシュを無効にする必要があります。

同じメモリ空間で動作する多くのスレッドを避ける。作業するスレッドごとに個別のデータを割り当て、計算が終了したらそれらを結合します。

頭の上から：

コンテキストスイッチ

リソースの競合

CPUの競合（複数のCPUに分割されていない場合）。

キャッシュのスラッシング

デビッド、

複数のプロセッサをサポートするカーネルを実行しますか？システムでプロセッサが1つしか使用されていない場合、CPUを集中的に使用するスレッドを追加すると、プログラムの速度が低下します。

そして、システムのスレッドのサポートは実際に複数のプロセッサーを実際に利用していますか？たとえば、topは、プログラムの実行時にプロセッサの両方のコアが使用されたことを示していますか？

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

所属していません StackOverflow