問題タブ [false-sharing]

最初に複数のスレッド (スレッドプール) を開始する次のコードがあります ( startWorkers())。myWorkObjectその後、ある時点で、複数のワーカースレッドを同時に使用して処理したいインスタンスでいっぱいのコンテナがあります。これらmyWorkObjectは、メモリ使用量の点で完全に分離されています。ここでは、myWorkObjectdoWorkIntenseStuffHere()に計算に CPU 時間がかかるメソッドがあると仮定します。

次のコードのベンチマークを行ったところ、このコードはスレッド数に応じて適切にスケーリングされず、アクティブなスレッドが 3 ～ 4 個ない限り、ワーカー スレッドの初期化/同期のオーバーヘッドがマルチスレッドの利点を上回っていることに気付きました。私はこの問題を調査し、偽の共有の問題について読みましたが、私のコードがこの問題に苦しんでいると思います。ただし、コードをデバッグ/プロファイリングして、何らかの飢餓/偽の共有が行われているかどうかを確認したいと思います。これどうやってするの？特にメモリ/CPUとマルチスレッドについてまだ多くを学んでいるので、私のコードについて自由に批判してください.

ロックフリー/ウェイトフリー アルゴリズムについて調査を行っているときに、誤った共有の問題に遭遇しました。もう少し掘り下げていくと、Folly のソース コード (Facebook の C++ ライブラリ) にたどり着きました。具体的には、このヘッダー ファイルとFOLLY_ALIGN_TO_AVOID_FALSE_SHARINGマクロの定義 (現在は 130 行目) にたどり着きました。一見して最も驚いたのは、値が128 (つまり、64 ではなく) であるということでした...

私の知る限り、最新の CPU のキャッシュ ブロックの長さは 64 バイトであり、実際には、Intel からのこの記事を含め、これまでに見つけたすべてのリソースで、64 バイトのアラインメントとパディングについて説明されており、フォールス シェアリングを回避するのに役立ちます。

それでも、Facebook の人々は、必要に応じて、クラス メンバーを 128 バイトに調整およびパディングします。FOLLY_ALIGN_TO_AVOID_FALSE_SHARING次に、の定義のすぐ上にある説明の始まりを見つけました。

もう少し詳細が得られますが、まだいくつかの洞察が必要だと感じています. アトミック操作を多用すると、隣接するキャッシュ ラインの同期、またはそれらに対する RMW 操作がどのように相互に干渉するかについて興味があります。 誰かがこれがどのように起こる可能性があるかについて私に教えてもらえますか?

最近、私は、任意の基数の順列ごとに生成するための並列化可能なメソッドの最適化に関する質問に答えました。Parallelized, poor implementation code block list に似た回答を投稿しましたが、誰かがすぐにこれを指摘しました:

これにより、誤った共有が行われることがほぼ保証され、おそらく何倍も遅くなります。（gjvdkampのクレジット）

そして彼らは正しかった、それは死の遅さでした。そうは言っても、私はこのトピックを調査し、それに対抗するための興味深い資料と提案(アーカイブされた MSDN マガジンのみ、.NET Matters: False Sharing ) を見つけました。私が正しく理解していれば、スレッドが連続したメモリ (たとえば、それをサポートしている可能性が高い配列) にアクセスするとConcurrentStack、誤った共有が発生する可能性があります。

水平線より下のコードの場合、aBytesは次のとおりです。

私自身のテストでは、これの並列バージョンを実行して本当に高速にしたかったので、元のコードに基づいて簡単な例を作成しました。6私の側では怠惰なlimits[0]選択でした-私のコンピューターには6つのコアがあります。

シングルスレッドブロック 平均実行時間: 10s0059ms

並列化、貧弱な実装 平均実行時間: 81 秒 729 ミリ秒、～ 8700 回の競合

並列化、?? 平均実行 時間: 5 秒 833 ミリ秒、92 回の競合

シングル スレッド バージョンよりも高速な実装が得られたことを嬉しく思います。約 10 秒 / 6、つまり約 1.6 秒に近い結果になると予想していましたが、それはおそらく単純な予想です。

私の質問は、実際にはシングル スレッド バージョンよりも高速な並列化された実装についてです。操作に適用できるさらなる最適化はありますか? 値の計算に使用されるアルゴリズムの改善ではなく、並列化に関連する最適化について疑問に思っています。具体的には：

• structの代わりにとして格納および入力する最適化については知っていますbyte[]が、それは並列化とは関係ありません (またはそうですか?)
• struct必要な値は、リップルキャリー加算器を使用して遅延評価できることを知っていますが、最適化と同じです。

私は現在pthreadsCで学んでおり、False Sharingの問題に遭遇しました。私はその概念を理解していると思います。少し実験してみました。

以下は、私が遊んでいる短いプログラムです。最終的には、これをプログラムに変更して、int の大きな配列を取得し、並列に合計します。

私の質問は、パディングを使用せずに誤った共有を防ぐことは可能ですか? ここでstruct sは、各構造体が独自のキャッシュ ライン上にあるように 64 バイトのサイズを持っています (キャッシュ ラインが 64 バイトであると仮定します)。パディングなしで並列処理を実現する方法がわかりません。

また、1000 ～ 50,000 バイトのさまざまなサイズの配列を合計する場合、どうすれば偽共有を防ぐことができるでしょうか? 同様のプログラムを使用してパディングすることはできますか? 私の現在の考えは、大きな配列からの各 int を配列に入れ、struct s並列処理を使用して合計することです。ただし、これが最適なソリューションであるかどうかはわかりません。

ホグワイルドを実装しようとしています！線形 SVMアルゴリズムですが、実装で誤った共有の問題が発生しています。

私のコードは以下にありますが、背景は、どのサンプルがテストに失敗し、そのベクトルのセットによって与えられたものを作成および更新するかを計算しようとしているということです。ホグワイルド！（私が理解している限り）同じメモリで完全に非同期に更新するだけです。これにより、不適切な時間の更新により、数学的な意味で「ノイズ」が発生します。

残念ながら、これらの非同期更新を行おうとすると、L1 キャッシュが無効になり、再取得する必要があります。以下は私のコードです。

非同期を失うことなく、この誤った共有を修正する良い方法はありますか? (私はコンピューター科学者というより数学者です)。これは、異なる最適化レベルを使用するとこれを修正できることを示しています。