並列ランダムアクセス機械
同期式PRAMでは、複数のCPUが同時並行的に共有メモリ上の同じ位置にアクセスする可能性がある。PRAMモデルにはいくつかの種類があり、それらの違いは主にそのような同じ位置への同時アクセスを許すか禁止するかである。さらにアクセスには「読み取り」と「書き込み」があるので、以下のような4種類に分類される。
排他的読み取り/排他的書き込み(Exclusive Read Exclusive Write、EREW) - 各メモリセルはある時点では1つのプロセッサだけが読み書きできる。
並行的読み取り/排他的書き込み(Conccurrent Read Exclusive Write、CREW) - 読み取りは同時に行えるが、書き込みは一度に1つのプロセッサのみである。
排他的読み取り/並行的書き込み(Exclusive Read Conccurrent Write、ERCW) - 考慮されない。
並行的読み取り/並行的書き込み(Conccurrent Read Conccurrent Write、CRCW) - 複数のプロセッサが自由に読み書きできる。 Common CRCW - プロセッサ群が同じ値を同時に書き込むのはOKだが、そうでない場合は不正な操作となる。 Arbitrary CRCW - 同時に書き込もうとしたうちの1つだけが成功し、他は失敗する(どれが成功するかは不明)。 Priority CRCW - 優先順位によって書き込みが成功するプロセッサが決められる。
問題から並列性を引き出し、分割して並行的にそれを解くことを可能にするアルゴリズムの発見に役立つ。