algorithm - 並列処理の計算順序

Question

ソートされていない配列が与えられた場合、n-square プロセッサを使用して O(1) の複雑さで配列の最大要素を取得できるという記事を読みました。その背後にあるメカニズムを説明できる人はいますか?

Answer 1

アルゴリズムの背後にあるメカニズムは、私が汚いトリックとしか呼べないものに基づいています。つまり、すべてのプロセッサが同じ共有メモリの場所に同時に書き込むことができます。それらがすべて同じ値を書き込む場合、結果は明確に定義されていると見なされます。

これは、並列 AND および並列 OR 演算子を実装するために使用できます。並列 OR の例を次に示します。

result := false
for i in 0 to N-1 parallel do
  if a[i] then
    result := a[i]

同時読み取りも可能です。

MAXアルゴリズムは次のとおりです。

N := a.length

for i in 0 to N-1 parallel do
    m[i] := true

for i in 0 to N-1 parallel do
  for j in 0 to N-1 parallel do
    if a[i] < a[j]               /* dirty trick: simultaneous read by many processors */
      then m[i] := false         /* dirty trick: many processors write to m[i] at once */

for i in 0 to N-1 parallel do
    if m[i]
        then max := a[i]         /* dirty trick: many processors write to max at once */

return max

これらのトリックを可能にする抽象的なアーキテクチャはCRCW PRAMと呼ばれます。

Answer 2

これは |V|ad の回答 (削除されました) のフォローアップです。

サイズの追加の配列を使用しnます (それを B と呼びましょう)。次に、プロセッサを使用して、任意の要素を他のすべてのn-1要素と比較します。それを見つけた各プロセッサは、それを見つけ、適用します。さらに、もしそうなら、チェックします。、要素 i が最大要素であることを発表します。a[i], i=0,...,n-1a[0],...,a[i-1],a[i+1],...,a[n-1]j={1,...,n-1}a[0] > a[j]B[i]=B[i]+1B[i]=n-1