0

C++ でミューテックス/セマフォをロックまたは使用せずに競合状態を回避するにはどうすればよいですか? 配列に値を設定するネストされた for ループを扱っています。

for (int i = 0; i < m; ++i)
  for (int j = 0; j < n; ++j)
    for (int k = 0; k < o; ++k)
      array[k] += foo(...);

多かれ少なかれ、同時に実行されている異なるスレッドが同時に array[k] に書き込まないように、これに対処したいと考えています。これにアプローチする方法について何か提案はありますか?

編集: Linux マシンで実行していますが、Intel コンパイラも使用する必要があります。「gcc」の代わりに「icc」を使用してコードをコンパイルします。

4

7 に答える 7

4

この特定のループでは、裏返しにします。外側につけて、それから別の糸にkファームアウトします。k=0k=1

k != 現在の k である array[k] に依存しない限りfoo()、あなたはゴールデンです。

于 2010-04-26T06:27:29.050 に答える
3

ウィンドウを想定し、次のようなことができるarrayタイプの要素が含まれていると仮定します。LONG

for (int i = 0; i < m; ++i) 
   for (int j = 0; j < n; ++j) 
      for (int k = 0; k < o; ++k)  {
          LONG val = foo(...);
          InterlockedAdd( &array[k], val);
      }

Windows で作業していない場合、プラットフォームに同様の API セットがある可能性があります。プラットフォームに API のタイプがある限りInterlockedCompareExchange()、独自のバージョンの を作成できますInterlockedAdd()。

次のようなもの (免責事項 - 未テスト):

 int InterlockedAdd( int volatile* pDest, int operand)
 {
      int curval = *pDest;
      int oldval;

      do {
           oldval = curval;
           curval = InterlockedCompareExchange( pDest, oldval + operand, oldval);
      } while (curval != oldval);

      return oldval+operand;
 }

私の知る限り、Boost はアトミック/インターロック操作のサポートが限定的であり、明らかに参照カウントのアトミック操作をサポートするのに十分なだけです。Boost での連動操作のサポートは、実装の詳細以上のものではないと思います (現在、Boost のやや古いバージョンを扱っているため、これはもう当てはまらない可能性があります)。

インターフェースの文書化された部分として、アトミックな比較と交換およびその他のアトミック操作をサポートする移植可能なライブラリがいくつかあります。

また、C++0x では比較/交換などのアトミック操作がサポートされることに注意してください。現在の C++ コンパイラでのサポートのレベルはわかりません (VS 2010 ではないようです)。

于 2010-04-26T06:27:41.123 に答える
2

配列が整数を保持していると仮定して、gcc のアトミック組み込み関数を使用します。__sync_fetch_and_addトリックを行う必要があります。

于 2010-04-26T06:26:52.640 に答える
2

あなたが望むように、それはできません！（sbiのコメント参照）

共有メモリを使用することもできますが、それでもロックが発生します。
配列への書き込みと読み取りに 1 つのスレッドのみを使用することもできます。適切なプロトコルを設定する方が簡単だと思われる場合は、続行してください。

とにかく、ロックを使用して (直接的または間接的に) 与えられた優れたソリューションが既にあります。1つだけ選んでください:)

于 2010-04-26T06:54:46.533 に答える
0

最も内側のループをスレッド間で分割します。スレッドT1は[0、L）の範囲のインデックスを処理し、スレッドT2は[L、2L）の範囲のインデックスを処理します。L= o / nここで、nはスレッドの数です。これは、foo（）呼び出しが、同時に計算される可能性のある他の場所を使用しないことを前提としています。

編集：他の人が示唆しているように、インターロックされた操作を使用すると正しい結果が得られますが、パフォーマンスが大幅に低下する可能性があります。（内部ループが短い場合、多くのスレッドが少数のメモリ位置をめぐって競合し、プログラムを効果的にシリアル化します。）

于 2010-04-26T06:28:58.720 に答える
0

最も簡単な方法（最も効率的ではありませんが！）は、ループを「クリティカル」セクションでラップすることです。

ウィキペディアを参照してください 。これにより、ループコードが常に単一のスレッドに制限されます。

于 2010-04-26T06:34:50.627 に答える
0

他の人が示唆しているように、連動操作を使用すると正しい結果が得られますが、パフォーマンスが大幅に低下する可能性があります。(内側のループが短い場合、多くのスレッドが少数のメモリ ロケーションをめぐって競合するため、プログラムを効果的にシリアル化できます)。

違うよ、友よ。実際、連動操作はすべての種類のロックよりも優れています。より正確には、すべての同期オブジェクト (クリティカル セクション、ミューテックス、イベントなど) は、連動操作に関して確実に実装されます。実際、インターロック操作は、同期の一貫性を保証できる唯一のプロセッサ命令です。連動操作をまったく使用せずに同期オブジェクトを実装することは、まったく不可能です。

もう 1 つの問題は、ロックの範囲です。おそらく、内部ループ内の同期スコープ (同期オブジェクトまたは連動操作で直接実装) は、何度も実行されるため、パフォーマンスの低下につながる可能性があると言いたかったのでしょう。

まあ、これは本当です。しかし一方で、必要な期間だけ必要なものだけをロックします。したがって、潜在的な同期の衝突を防ぐことができます。

于 2010-04-26T14:03:01.680 に答える