8

Java で並行プログラミングを学んでいて、Game of Life のシミュレーションを書いています。

これが私が考えていることです：

  • int[][] を使用してセルの状態を保存します
  • int[][] を t 個のセグメントに分割し、t 個のワーカー スレッドを使用する
  • t スレッドはセグメントから読み取り、セグメント内のすべてのセルの新しい値を計算し、セルを更新します。
  • 計算が終了すると、障壁で他のワーカーが終了するのを待ちます
  • バリアを越えると、メイン スレッドが UI を更新します。
  • ワーカーは次の状態の計算に進みます。

現在、セグメントの共通の境界で競合が発生しています。隣接セルが前の値を読み取る前にスレッドが境界セルの状態を上書きした場合、隣接セルの計算は間違っています。

私のオプションは何ですか？

  • runnable の代わりに callable を使用し、ワーカー スレッドが新しい値を返すようにします (セグメント自体を更新するのではなく)。バリアを越えた後、メイン スレッドはマトリックスを更新できます。このオプションでは、ワーカー スレッドによって返された結果をマトリックスにコピーします。
  • 2 つのバリアを使用します。ワーカー スレッドは、隣接するセグメントから境界セルのコピーを作成し、最初のバリアで待機します。このバリアを通過すると、次の状態の計算に進み、その場でセグメントを更新します。その後、2 番目のバリアで待機します。メイン スレッドが UI を更新します。

私の質問は、データのコピーを伴わない、または上記の 2 つのオプションよりも効率的な境界セルでの競合に対処する他の方法はありますか? ReaderWriterLock、揮発性変数、またはその他の同期メカニズムを使用している可能性がありますか?

更新: これまでのところ、Peter によるダブル バッファリング ソリューションが最もクリーンなソリューションです。しかし、質問があります。2 つの配列は共有データであり、同期 (同期アクセスまたは揮発性変数) を使用していないため、可視性の問題は発生しませんか? 複数の CPU が配列の値をキャッシュし、各反復で配列の一部のみを更新できますか? 次に、スレッドは境界セルの古い値を取得します。これは可能ですか？そうでない場合は、その理由。はいの場合、どうすれば解決できますか? 2 つの配列を volatileと宣言しても、個々の要素が volatile にならないようです。

4

5 に答える 5

5

2つのint[][]配列を使用することをお勧めします。それらをAおよびBと呼びましょう。Aはすべての奇数番号の「ティック」の値を保持し、Bは偶数番号のティックを保持します。

Aを初期状態に初期化します。次に、スレッドを緩めて各セルの次の状態を計算し、結果をBの対応するセルに配置します。すべてのスレッドが完了すると、新しい状態がBになります。次に、Bを使用して次の状態を計算します。各セルに結果を保存し、結果をAに格納します。常に、一方の配列は読み取り専用で、もう一方の配列は書き込み専用であるため、競合が発生することはありません。

利点：

  • 現在行っていることと比較して、データのコピーはありません。セルごとに1つの書き込みのみが発生しています。
  • アルゴリズムが単純なので、エッジ/コーナーの場合を心配する必要はありません。
  • 継続的なメモリの割り当てはありません。開始時に2つのアレイを割り当てるだけです。

短所：

  • 2倍のメモリを割り当てる必要があります。
于 2010-02-24T20:47:20.383 に答える
1

私は次のアプローチを試します：

  • ワーカーに計算を実行させますが、値を内側のセルに書き戻すだけです。
  • 境界セルの場合、結果を保存します。
  • 計算が完了したら、バリアで待機します。
  • すべてのワーカーが最初のバリアに到達したら、解放し、それぞれが境界セルを書き込めるようにします。
  • UI が更新される間、2 番目のバリアで待機します

n x mタイルに必要なストレージは です2 * (n + m - 1)。そのため、一般に、より大きなタイル (8x8 以上) は、キャッシュされた値に比例して少ないメモリを必要とします。

于 2010-02-24T20:31:35.077 に答える
1

実際の質問には答えませんが、私の推奨は最初のオプションです...ワーカースレッドに更新させるのではなく、新しい値を返すことをお勧めします。さらに一歩進んで、「アグリゲーター」にワーカースレッドからの結果を新しいボード状態配列に結合させ、最初の配列を破棄させます。私の推論は、心配する必要がある「グローバルな相互作用」がほとんどまたはまったくないため、ロジックの全体的な読みやすさが向上するということです。

そうは言っても、そうしない強い理由がある場合を除いて、機能的な方法でプログラミングすることを好むので、私は少し偏っています。

于 2010-02-24T20:22:09.703 に答える
0

私はちょうどつまずいたjava.util.concurrent.Exchanger<V>。それは交換のポイントとして機能します。おそらく、隣接するスレッド間でセル状態のリストを交換するために使用できます。隣接するワーカー間でのみ同期する必要があるため、バリアよりも優れています。

于 2010-02-24T22:17:59.520 に答える
0

ダブル バッファリングによるキャッシングの問題に関する最新情報に答えるために、それは問題ではありません。CPU にはコヒーレントなキャッシュがあり、データが別の CPU キャッシュで変更されたときを認識しています。

于 2010-02-25T19:01:36.893 に答える