0

この配列 (A) には、ソートされることが保証されている n 個の要素があり、並列システムでそれらに対してバイナリ検索を実行する必要があります。このバイナリ検索アルゴリズムを作成することから始めました。再帰を並列処理に組み込む方法がまだわからないため、反復的です。

/* Looking for element k in array A of length n */
min = 0;
max = n - 1;
while(min <= max)
{
    midpoint = min + ((max-min)/2); //index
    if(A[midpoint] > k) //discard upper half
        max = midpoint - 1;
    else if(A[midpoint] < k) //discard lower half
        min = midpoint + 1;
    else
        return midpoint; //Found k, return index
}
return -1; //not found

並列アルゴリズムでは、p 個のプロセッサにアクセスできます。これは、同時読み取りが可能なシステムですが、書き込みは排他的です。本当の問題は、私がまだ順番に考えていることです。つまり、中間値の観点から自分がどこにいるのかを最初に知らずに配列の不要な部分を「捨てる」ことができないため、これを複数のプロセッサで実行できる方法はないようです。それは本質的に連続しているように見えます。

疑似コード:

Global:  //Variables accessible by all processors
  index; //index of k
  p;     //number of processors
  i;     //the i^th processor
  n;     //number elements in array A
  A[0, 1, ... , (n-1)];
local:   //Variables accessible by only the owning processor
         //Not sure what I need yet
Begin
  Spawn(P1, P2 . . . P(p-1)); //"create" the p processors
  for all P where 0 <= i <= (p-1) do //each processor does the following code
    //I'm stuck here
  endfor
End

最後に 1 つ: 並列処理で二分探索を行う方法があるかどうかを尋ねるユーザーからの質問が投稿されているのを見ました。該当する 2 つの回答が両方とも 1 票を獲得したため、その質問に対する決定的な回答はありませんでした。1 人は、これは段階的なプロセスであるため事実上不可能であると述べましたが、もう 1 人は、実装が非常に簡単であると確信しているように見えました。あなたの考えは何ですか？

前 並列二分探索問題

4

2 に答える 2

3

並行して解決するすべての問題と同様に、これはデータのサイズ、メッセージ/共有メモリの速度、および要件に大きく依存します。

書き込みロックの速度と同期の速度はどれくらいですか？それらが十分に高速であり（たとえば、単一のマシンで共有メモリを使用している場合）、データサイズが十分に大きい場合は、特定の種類の「分割して実行」する手法が機能する可能性があります。あなたはそれを次のように考えることができます：

二分探索は分割統治法であり、各反復の後に調査している範囲を更新します。範囲は各反復で半分になります。p現在の範囲を2に分割する代わりに、各プロセスが1つの部分を担当する部分に分割することができます。各反復で、「勝者」の部分（範囲内にターゲット値を持つ部分）が検索対象の新しい範囲をメモリに書き込み、次の反復を開始する前にプロセスを同期します。p十分なデータがある場合は、データを半分にすることから、毎回データを減らすことへの移行が成功する可能性があります。$ O（log_2（x））$から$ O（log_p（x））$に移動します。

この種のアプローチは、多くの書き込みと同期を行うことに依存するため、書き込みと同期が十分に高速である場合にのみ機能します。クラスタ全体でこれを行う場合、これらは高価になります。プロセス間の通信が難しい場合、おそらくあなたができる最善のことは、あなたがリンクした他の投稿で提案されている「分割して実行する」ことです。具体的にpは、ソートされたリストの各要素を取得し、それを別のノードに配置します。次に、リクエストが届いたら、すべてのノードでバイナリ検索を実行します。配列の値が一意である場合、答えを見つけるのは1つのノードのみであり、そのノードは結果を返すことができます。多くの作業を繰り返しているため、並列処理は比較的不十分です。間に存在する順序を無視しているためです。異なるノード上のアレイ。ただし、$ O（log_2（x））$から$ O（log_2（x / p））$へのスピードアップが得られます。

実際には、ハードウェアでどのアプローチがうまく機能するかを事前に知るのは難しい場合があります。多くの場合、すべてのプロセスが常にアクティブであることを確認することと、通信のオーバーヘッドに多くの時間を無駄にしないことを確認することとの間で経験的なバランスをとる必要があります。

于 2012-11-27T03:44:52.017 に答える
3

二分探索を並行して実行することは技術的に可能ですが、私はお勧めしません。

並列実行に最適なアルゴリズムは、同時に実行できる個別の要素が互いに分離されているアルゴリズムです。たとえば、3D グラフィックスをビデオにレンダリングすることは、各フレームが独立しており、別のプロセッサに与えることができるため、優れています。

ツリーをセグメントに分割して、各プロセッサが何かを処理できるようにすることもできますが、二分探索の性質を考慮すると、多数のプロセッサのうちの 1 つだけが答えを見つけるため、答えを見つけられなかった他のすべての計算作業が無駄になります。セグメントに検索要素があります。これは、スレッド化のオーバーヘッドを考慮していません。

一方、単一の二分木に対して一連の検索を行う場合は、別の問題になります。すべてのスレッドがフィードするジョブキューを持ち、バイナリ検索を実行して応答することができます。このようにして、検索の一部ではなく、多くの検索を並行して実行できます。さらに最適化する場合は、キャッシュを実装することもできます。

要するに、個々のバイナリ検索をプロセッサ間で分割しようとしないでください。プロセッサ時間を浪費する以外に何も得られないからです。しかし、多くの検索を行っている場合は、多くの検索を並行して実行することで得ることができます。

于 2012-11-27T03:42:42.783 に答える