1

並列計算用の PRAM モデルには、主に EREW、CREW、CRCW の 3 つの種類があります。

EREW、CREW をマルチコア マシンに実装する方法を理解できます。しかし、マルチコア CPU に CRCW モデルを実装するにはどうすればよいでしょうか? 同時書き込みは不可能であり、すべての基本的な並列プログラミングコースは競合状態に至るまで詳細に説明されているため、これは実用的なモデルでさえありますか?

基本的にこれは、競合状態を回避しようとすることと、同時書き込みを実装しようとすることは、2 つの相反する目標であることを意味します。

4

1 に答える 1

1

まず、PRAM が理論上の、または抽象的な機械であることはわかっています。並列アルゴリズムの分析/設計に使用できるように、いくつかの単純化が行われています。

次に、意味のある「同時書き込み」を行う方法について話しましょう。

同時書き込みメモリは通常、その動作に基づいてサブクラスに分けられます。

  1. 優先度ベースの CW - プロセッサには優先度があり、同じ場所への複数の同時書き込みが到着した場合、最も優先度の高いプロセッサからの書き込みがメモリにコミットされます。

  2. 任意の CW - 1 つのプロセッサの書き込みがコミットのために任意に選択されます。

  3. Common CW - 同じ場所への複数の同時書き込みは、書き込まれる値が同じである場合にのみコミットされます。つまり、すべての書き込みプロセッサは、書き込まれる値に同意する必要があります。

  4. リダクション CW - リダクション演算子は、書き込まれている複数の値に適用されます。たとえばsummation、同じ場所への複数の同時書き込みにより、書き込まれる値の合計がメモリにコミットされます。

これらのサブクラスは、いくつかの興味深いアルゴリズムにつながります。クラスで覚えている例のいくつかは次のとおりです。

  1. 同時書き込みが合計として達成されるCRCW-PRAMは、単一のタイムステップで任意の数の整数を合計できます。入力配列の整数ごとにプロセッサがあります。すべてのプロセッサは、値を同じ場所に書き込みます。終わり。

  2. すべてのプロセッサによって書き込まれた値が同じ場合にのみ、メモリが同時書き込みをコミットする CRCW-PRAM を想像してください。次に、最大値を見つける必要があるN数値を想像してください。A[1] ... A[N]方法は次のとおりです。

ステップ1。

N 2個のプロセッサが各値を他の値と比較し、結果を 2D 配列に書き込みます。

parallel_for i in [1,N]
  parallel_for j in [1,N]
    if (A[i] >= A[j])
      B[i,j] = 1
    else
      B[i,j] = 0

したがって、この 2D 配列では、最大数に対応する列はすべて 1 になります。

ステップ2：

1 だけの列を見つけます。そして、対応する値を最大値として保存します。

parallel_for i in [1,N]
  M[i] = 1
  parallel_for j in [1,N]
    if (B[i,j] = 0)
      M[i] = 0              // multiple concurrent writes of *same* value
  if M[i]
    max = A[i]

最後に、実際に実装することは可能ですか?

はい、可能です。たとえば、複数の書き込みポートを持ち、同じアドレスへの同時書き込みを意味のある方法 (上記で説明した方法のように) で調停する、レジスタ ファイル、またはメモリと関連するロジックを設計することは可能です。私が言及したサブクラスに基づいて、おそらくすでにそれを確認できます。実用的かどうかは、なんとも言えません。私のコンピューターに関する限られた経験 (現在前に座っている Core Duo マシンのような汎用ハードウェアを主に使用することを含む) では、実際に見たことがないと言えます。

編集: CRCW の実装を見つけました。PRAMに関するウィキペディアの記事では、2クロックサイクルで配列の最大値を見つけることができるCRCWマシンについて説明しています（上記と同じアルゴリズムを使用）。説明は SystemVerilog にあり、FPGA に実装できます。

于 2012-07-13T21:46:20.847 に答える