問題タブ [false-sharing]

大学のコースの一環として、OpenMP の使用方法を学び始めました。ラボの演習として、並列化する必要があるシリアル プログラムが与えられました。

False Sharingの危険性を最初に認識したことの 1 つは、特に for ループで並列に配列を更新する場合です。

ただし、False Sharing を発生させずに、次のコード スニペットを並列化可能なタスクに変換するのは難しいと思います。

私の最初の反応は、ukp1を共有してみることでした:

しかし、これは明らかにシリアル バージョンと比較して大幅な速度低下を示しています。明らかな理由は、 ukp1への書き込み操作中に False 共有が発生していることです。

リダクション句を使用できるのではないかという印象を受けましたが、これは配列では使用できないことがすぐにわかりました。

このコードを並列化してランタイムを改善するために使用できるものはありますか? 聞いたことのない使用できる条項はありますか? それとも、適切な並列化を可能にするためにコードを再構築する必要があるようなタスクですか?

あらゆる形式の入力をお待ちしております。

EDIT：私のコードに間違いがあったと指摘されました。私がローカルに持っているコードは正しいです。間違って編集しただけです (コードの構造が変更されました)。混乱して申し訳ありません!

EDIT2：

@Sergeyが私に指摘してくれたいくつかの情報は、私が役に立つと感じています:

• uk または ukp1 をプライベートに設定すると、基本的に共有に設定するのと同じ効果があります。これは、両方とも同じメモリ位置へのポインターであるためです。

• 静的スケジューリングを使用すると、理論的には役立つはずですが、私はまだ同じ速度低下を経験しています。また、静的スケジューリングは、この問題を修正する最も移植性の高い方法ではないと感じています。

以下のコードでは、OpenMP の標準parallel for節を使用して並列化しています。

これにより、ランタイムが大幅に改善されました (~140 秒から~40 秒) が、実際に遅れていることに気付いた領域がまだ 1 つあります。それは、上記でマークした最も内側のループです。

上記の配列が False Sharing を引き起こしていることは確かです。なぜなら、以下の変更を加えると、パフォーマンスがさらに大幅に向上する (~40 秒から ~13 秒) ためです。

つまり、メモリの場所をプライベート変数に書き込むように変更するとすぐに、速度が大幅に向上しました。

今説明したシナリオで False Sharing を回避することでランタイムを改善する方法はありますか? 問題自体は何度も言及されていますが、この問題に役立つと思われる多くのリソースをオンラインで見つけることができないようです.

非常に大きな配列 (必要なものの 10 倍) を作成して、各要素の間に十分なマージン スペースを確保し、キャッシュ ラインに入ったときに他のスレッドがそれを取得しないようにするというアイデアがありました。ただし、これは目的の効果を生み出すことができませんでした。

そのループで見つかった False Sharing を削減または削除する簡単な (または必要に応じて難しい) 方法はありますか?

どんな形の洞察や助けも大歓迎です！

EDIT : some_calculation() が次のことを行うと仮定します:

反復ごとに計算される d_equ に依存しているため、この計算を for ループの外に移動することはできません。

対称型マルチプロセッサ (SMP) システムでは、次のコードについて、各コアの個別のキャッシュが原因で誤った共有が発生する可能性があることを理解しています: http://software.intel.com/en-us/articles/avoiding-and-identifying -false-共有間スレッド

だから私の質問は：

1. 偽共有は主に、メモリが固定バイト数で構成されるチャンクを介してアクセスされ、各プロセスが独自のキャッシュを持っているという事実に由来します。このメモリのチャンクは、一緒に書き込まれ、読み取られます。私の理解は事実に近いですか？
2. GPU のメモリ アクセス パターンはどうですか? すべてのストリーム プロセッサが 1 セットのキャッシュを共有していますか、それとも個別のキャッシュ セットを持っていますか? 偽共有は GPU コンピューティングでも懸念されますか?

コンウェイのライフ ゲーム用に openMP コードを最適化しようとしています。私の主な問題は、おそらく偽の共有に関連しています。これが私のコードです: これは私のクラス「mondo」のメソッドです。m は私のスキーム、r は行数、c は列数で、トロイダル スキームを使用しています。

今日、「偽共有」とは何かについて、並列プログラミングのクラスで教授と別の理解を得ました。私の教授が言ったことはほとんど意味をなさないので、すぐに指摘しました。彼女は、「偽の共有」がプログラムの結果に誤りを引き起こすと考えました.

「偽共有」は、異なるメモリアドレスが同じキャッシュラインに割り当てられている場合に発生し、そのいずれかにデータを書き込むと、別のアドレスがキャッシュから追い出されると言いました。プロセッサが 2 つの誤った共有アドレスの間で書き込みを行ったり返したりすると、両方ともキャッシュにとどまることができなくなるため、すべての操作が DRAM のアクセスになります。

それがこれまでの私の意見です。実際、私が言ったことについてもはっきりとはわかりません.誤解がある場合は、それを指摘してください.

そこでいくつか質問があります。キャッシュは、64 バイトにアラインされた 4 ウェイ セット アソシアティブと見なされます。

1. 64 バイト以上離れた 2 つのアドレスが「偽共有」である可能性はありますか?
2. 単一のスレッド化されたプログラムで「偽の共有」の問題が発生した可能性はありますか?
3. 「偽の共有」を再現するための最良のコード例は何ですか?
4. 一般的に、プログラマーの「偽共有」を避けるために注意すべきことは何ですか?

いくつかの強力な行列処理を実行しようとしているコードがいくつかあるので、マルチスレッド化すると高速になると思いました。ただし、私の意図は、スレッドを存続させて、将来さらに多くの処理に使用できるようにすることです。ここに問題があります。コードのマルチスレッド バージョンは、シングル スレッドよりも遅く実行されます。問題は、スレッドにシグナルを送る/維持する方法にあると思います。

Windows と C++ で pthread を使用しています。スレッドのコードは次のとおりです。 runtest()は、行列の計算が行われる関数です。

playQueue ()関数は pthread に渡される関数であり、現在私が持っているのは、1000 個のアイテムのキュー (testQueue) があり、100 個のスレッドがあるということです。各スレッドは、キューが空になるまで実行され続けます (したがって、ミューテックス内のもの)。

マルチスレッドの実行が非常に遅い理由は、偽共有と呼ばれるもの (だと思いますか?) と、スレッドにruntest()を呼び出すように通知し、スレッドを存続させる方法が貧弱であるためだと思います。

マルチスレッドバージョンが反復バージョンよりも高速に (または少なくとも同等の速度で) 実行されるようにするには、これを行う効果的な方法は何でしょうか?

これが私のコードのフルバージョンです（マトリックスのものを除く）

したがって、ここの「matrix_exponential_tests」は許可を得てこの Web サイトから取得したもので、すべての行列計算が行われる場所です。カウンタは、デバッグしてすべてのインスタンスが実行されていることを確認するためにのみ使用されます。

このスレッドのopenMPパフォーマンスが存在することを知っています

しかし、ここで私の例は非常に単純です

C コード:

この例のタイミングは、openMP (szGlobalworkSize = 131072) で 0.045 秒に対して、openMP なしで openMP 0.015 を使用すると増加します。

私は gcc の次の行を使用します: gcc -march=native -fopenmp -O3 MyCode.c -lm

gcc (GCC) 4.8.2 20140120 (レッドハット 4.8.2-15)

編集1:

また、memalignのチャンクと同じ時間

スレッドごとのタイミングで編集 2

各スレッドは合計 0.045 に対して 0.015 かかるため、openmp には 0.03 の修正部分があります。巨大な次元であっても、openmp とスレッドのこの修正部分が見られるのは奇妙です。ここ）

ありがとう

同じキャッシュ ブロック内の異なるメモリ位置を読み書きする 2 つのコアがある場合、論理的には必要ではありませんが、両方のコアがそのキャッシュ ブロックを何度もリロードする必要があります。これは、私たちが偽の共有と呼んでいるものです。

しかし、コアがそのキャッシュ ブロックから読み取るのではなく、書き込むだけの場合はどうなるでしょうか。2 つのコアが同じキャッシュ ブロックにいくつかのビットを設定しただけで、設定したビット情報はプログラムの後のフェーズでのみ必要になるため、ブロックから読み取る必要はないと想像してください。

フォールス シェアリングは、コアが同じブロックで読み取りと書き込みを行う場合にのみ発生しますか? それとも、両方が書き込みのみを行う場合にも発生しますか?

Matrix-Vector 乗算のコードを作成しました。行列は、スレッドの数に基づいて行のブロックに分割され、各ブロックにベクトルが乗算され、ベクトルがスレッド専用の配列に格納されます。しかし、私のスピードアップは非常に貧弱です。サイズが 16 X 16 の行列の場合、1 未満です。

これは、行列とベクトルを外部で共有変数として宣言し、各スレッドが行列とベクトルから値を読み取ろうとするときに競合状態/偽の共有が発生する可能性があるためでしょうか?

偽の共有と競合状態の間で少し混乱しています。