5

オブジェクトの (二重に) リンクされたリスト (C++) が与えられた場合、マルチスレッドで各オブジェクトに対して実行したい操作があります。操作のコストは、オブジェクトごとに均一ではありません。リンクされたリストは、さまざまな理由から、このオブジェクトのセットに適したストレージです。各オブジェクトの最初の要素は、次のオブジェクトへのポインターです。2 番目の要素は、リスト内の前のオブジェクトです。

ノードの配列を構築し、OpenMP を適用することで問題を解決しました。これにより、まともなパフォーマンスが得られました。次に、独自のスレッド ルーチン (Windows プリミティブに基づく) に切り替え、InterlockedIncrement() (配列へのインデックスに作用する) を使用することで、全体的な CPU 使用率を高め、スループットを高速化することができます。基本的に、スレッドは要素に沿って「跳躍」することによって機能します。

最適化への次のアプローチは、リンクされたリスト内の要素の配列の作成/再利用を排除しようとすることです。ただし、この「リープフロッグ」アプローチを続行し、「InterlockedCompareDereference」と呼ばれる存在しないルーチンを何らかの方法で使用して、NULL (リストの最後) とアトミックに比較し、条件付きで逆参照して保存し、逆参照された値を返したいと思います。 .

ポインターをアトミックに逆参照してこの Interlocked() メソッドを呼び出すことができないため、 InterlockedCompareExchangePointer() が機能するとは思いません。私はいくつかの読書をしましたが、他の人はクリティカルセクションまたはスピンロックを提案しています。ここではクリティカル セクションが重く見えます。スピンロックを試してみたくなりましたが、最初にここで質問をして、他の人が何をしているのか聞いてみようと思いました. InterlockedCompareExchangePointer() メソッド自体がスピンロックのように使用できるとは確信していません。次に、取得/解放/フェンスのセマンティクスも考慮する必要があります...

アイデア？ありがとう！

4

4 に答える 4

1

Casta にはいくつかの良い点があると思います。自分でポニーアップします。この問題の解決策は、各ノードで行われるアイデアの変換、それらが相互に依存しているかどうか、および達成されたタスクがリストの単一のスイープで実行できるかどうかに大きく依存します。

操作が相互に依存しておらず、スイープ アプローチが理にかなっている場合は、ブローカ フェッチ システムを提案します。これは、作業員のアプローチと実質的に同じです。各スレッドには、リストを管理するブローカへの参照が渡されます。各スレッドは、処理するコンテンツが必要なため、ブローカにコンテンツを要求します。ブローカはロックし、次のノードを取得し、内部スイープ イテレータを進め、ロックを解放して、要求元スレッドへのノード。これは、リストの列挙が終了するまで続きます。各ノードが異なるスレッドによって複数回アクセスされる可能性があるアキュムレータの問題については、循環リストまたはその他のそのようなコンテナを使用できます。才能のあるブローカーは、新しい挿入、削除などを含むリストを、ディスパッチと同じ方法で管理できます: ロック、アクション、ロック解除。明らかに、ブローカー側で特定のニーズに合わせて調整できる多くのアクティビティがあります。これらのニーズは精巧なプール管理システムを実現できますが、ロックの競合に関しては非常に効率的です (つまり、ほとんど競合しません)。

ただし、結論は明らかです。問題セットと、各スレッドが現在のノードで達成したいことの詳細を理解してください。

于 2012-09-25T21:36:37.367 に答える
1

クリティカル セクションはそれほど重くはありません。ロックをすばやく取得できると仮定すると、スピンロックのように動作します。

問題の解決策は、リストを変更するかどうかによって異なります。リストを変更していない場合は、0 に初期化されたオブジェクトの値に対して InterlockedCompareExchange などを実行するだけで済みます。交換値は 1 です。0 が返された場合はアクションを実行し、1 が返された場合は、あなたはスキップします。次にリストに対してアクションを実行するときは、2 で交換し、0/1 の代わりに 1/2 をチェックします。

リストを変更する場合は、すべて依存します。前方にのみ移動し、現在のノードのみを削除する場合は、比較交換ビットを実行するとき、リープフロッグ (次のノードを取得する) とき、および削除するときにロックするアイテムに次のロックを設定するのが最善の策です。ノード。

于 2012-09-25T21:19:39.927 に答える
0

アラインメントにより、リストポインタの下位ビットにはゼロが含まれます。コンペアアンドスワップ命令を使用してオブジェクトを処理中としてマークすることにより、ポインターの1つにこれらのビットの1つをアトミックに設定することにより、これを利用できます。

各スレッドは次のことを行います。

  1. リストの先頭からトラバースを開始します。
  2. リストノードごとに、次のポインタに下位ビットが設定されているかどうかを確認します。
  3. ビットが設定されている場合は7に進みます。
  4. リストノードの次のポインタをと比較して交換します(next | 1)。
  5. コンペアアンドスワップが失敗した場合は、7に進みます。
  6. オブジェクトを処理します。
  7. 次のノードに移動し、2に進みます。

別のオプションは、リストノードが基本クラスまたはオブジェクトのメンバーでない限り、このビットマークをオブジェクト自体に未使用のビットがある整数に入れることです。

このようにして、スレッドは、待機なしでスピンをブロックしたりビジー状態にしたりすることなく、リストからオブジェクトを取得します。

于 2012-09-26T16:37:06.713 に答える
0

基本的に、リストをできるだけ速く実行するには、避けるべきことがいくつかあります。

  • 衝突をロックします。スピンロックを使用しても、ループの反復はすべて、作業を完了する機会を逃します。
  • メモリバリア。アトミック操作を行うたびに、メモリバリアが実行を停止します。
  • リストをスキャンして実行する作業など、不要な作業。

私はあなたの読書に同意し、スピンロックの側に立つ必要があります。

リストの先頭へのポインターを揮発性ポインターに置きます。

次に、各スレッドが順番に;

  • スピンロックを取ります
  • ポインタの値を一時的に保存します
  • 次のリストエントリへのポインタを更新します
  • スピンロックを解除します。

その後、一時的にポイントされたエントリの作業を開始できます。

これには、エントリごとのロックを使用してリストを検索することにはいくつかの利点があります。

  • アイテムごとの作業が完了するまでに取るに足らない時間がかかる場合、ポインターを更新する短時間の間、衝突はほとんど発生しません。
  • 衝突を除けば、リストアイテムごとに2つのメモリバリアしかありません。1つはロック用、もう1つはロック解除用です。
  • 新しい作業項目を取得するためにリストをスキャンする必要はありません。「キュー」から作業を取得するだけです。
于 2012-09-26T15:50:42.637 に答える