1

PRAMアルゴリズムを学んでいます。次の方法を使用して、CRCW PRAM のブール OR を O(1) 時間で計算できるためです。

A[0]= A[1]|A[2]|A[3]...|A[n] は、n ビット A[1..n] のブール論理和です。そもそも A[0] がゼロであると仮定します。最初のタイム ステップで、プロセッサ i (1<= i <= n) はメモリ ロケーション A[i] を読み取り、A[i] が 1 の場合はメモリ ロケーション A[0] に 1 を書き込みます。 A[i] は 1 の場合があり、複数のプロセッサが同時に A[0] に書き込む場合があります。したがって、CRCW の場合、O(1) 時間でブール OR を計算できます。

同様に、CRCW のブール AND を解くことができます

CREW と EREW について、これをどのように解決できるか知りたいです。アルゴリズムの時間とプロセッサの境界は何ですか?

4

1 に答える 1

1

すべてのプロセッサが独自のビットを読み取っているため、排他的読み取りは問題ではないと思います。それらすべてが A[0] に書き込む必要があるため、問題は排他的書き込み部分にあります。一種のトーナメント ツリーを作成するのが最善の方法だと思います。したがって、チャンピオンが得られるまで、ビットのペアを OR して結果を次のレベルに昇格させることができます。次に、最終結果を A[0] に書き込むことができます。これは O(log n) になります。

于 2013-09-21T14:49:51.333 に答える