3

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

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_histograms は、最後にメインスレッドで合計されます。

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

time参考までに: 1 つのスレッドの典型的な出力(これは Linux 上にあります):

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にあります。

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

4

7 に答える 7

13

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

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

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

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

于 2009-03-04T23:25:07.863 に答える
5

あなたの質問は何が「できる」かということだったので、他の返信でこれまでに言ったことはすべて一般的に当てはまります...しかし、実際のコードを見たので、最初の賭けは、random（）の使用です。関数はすべてを遅くします。なんで？

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

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

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

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

Linuxのみのソリューションが機能する場合は、random_rを使用できます。それはあなたがすべての呼び出しで状態を渡すことを可能にします。スレッドごとに一意の状態オブジェクトを使用するだけです。ただし、この関数はglibc拡張機能であり、他のプラットフォームではサポートされていない可能性があります（C標準またはPOSIX標準AFAIKのいずれでもありません-この関数は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;
}

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

于 2009-03-04T23:48:38.713 に答える
2

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

于 2009-03-04T23:07:53.367 に答える
1

頭のてっぺんから：

  • コンテキストスイッチ
  • リソースの競合
  • CPUの競合（複数のCPUに分割されていない場合）。
  • キャッシュスラッシング
于 2009-03-04T23:21:47.823 に答える
1

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

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

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

于 2009-03-04T23:01:02.163 に答える
1

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

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

于 2009-03-04T23:14:23.427 に答える
0

デビッド、

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

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

于 2009-03-05T11:41:58.250 に答える