0

グラフを作成するために互いに比較する必要がある N 個の要素があります。合計で(N*N-1)/2 回の比較が得られます。

これらの比較をマルチスレッド化したいのですが、いくつかの制約もあります。

  • 各要素は非常に大きく、実際には行列であるため、各スレッドのすべての要素をコピーするとメモリが大量に消費されます。

  • 各比較が発生する必要があります。つまり、1 つをスキップすることはできません。

  • 新しい要素がリストに追加されるたびに、何が行われたかを追跡し、新しい要素だけを実行する必要があるため、これは非常に注意が必要です。

  • 比較の数は 2000 万のように膨大になる可能性があるため、キューをそれほど大きくすることはできません。

  • 最後に、いつでもプロセスを停止できます。アプリの他の実行中であっても、再開できる必要があります。

これまでのところ、スレッドプールにすべての要素といくつかのワーカーを含むマスタースレッドがあります。ワーカー スレッドは、ペアのリストまたは要素の範囲を比較します。次のX回の比較をオンデマンドで提供する比較ジェネレーターについて考えています。

このジェネレーターをどのように構築できますか?

ワーカーのすべてのペアをコピーし、ワーカーから直接 ReadWriteLock を使用して Master からデータを読み取る必要がありますか?

すべてのスレッドの進行状況を追跡するにはどうすればよいですか?

比較の状態を停止して再開するにはどうすればよいですか?

質問が多くてすみません。ありがとうございました ！

4

1 に答える 1

0

読み取りがスレッドセーフであると仮定すると (通常、誰も書き込みを行っていない限り)、単純な解決策は、事前に何らかの方法で一連のワーカー スレッド間でタスクを分割することです。たとえば、nワーカーの場合、ペア ( x , y ) をワーカーx mod nに割り当てることができます。唯一の通信は、各ワーカーにその序数 (0...<em>n-1) を知らせることです。各スレッドは、その回答をプライベート配列にドロップする必要があります。これは、他の全員が終了した後に照合できます。

さまざまなワーカーの生産性に対応するより洗練されたモデルは、すべての値 0...<em>N-1 をキューにプッシュすることです。各ワーカー スレッドは、数値xをキューから取り出し、すべての ( x , y ) ペアを評価してから、別のxに戻ります。

時間をかけたい場合は、キャッシュのスラッシングを最小限に抑えるために、ペアをキューに入れる方が効率的です。これは難しい問題です。基本的に、クラスター内のすべてのペアがほぼ同時に評価されるように、エレメントの小さなクラスターからペアをキューに入れます。これは難しいことですが、アルゴリズムの効率に大きな違いをもたらす可能性があります。

于 2013-01-22T21:30:11.537 に答える