並列ランダムアクセス機械

並列ランダムアクセス機械（へいれつランダムアクセスきかい、）は、並列コンピューティングに適用可能なアルゴリズムを設計するための抽象機械である。同期や通信といった細かな部分を省き、並行性をいかに引き出すかに集中することが可能となる。フリンの分類によれば、PRAM は MIMD 型コンピュータに相当する。
種類.
同期式PRAMでは、複数のCPUが同時並行的に共有メモリ上の同じ位置にアクセスする可能性がある。PRAMモデルにはいくつかの種類があり、それらの違いは主にそのような同じ位置への同時アクセスを許すか禁止するかである。さらにアクセスには「読み取り」と「書き込み」があるので、以下のような4種類に分類される。
問題から並列性を引き出し、分割して並行的にそれを解くことを可能にするアルゴリズムの発見に役立つ。
実装.
CPU と DRAM の組み合わせでは、DRAM が同時アクセスできないため、これらのアルゴリズムを実現できないが、ハードウェアとして実装したり、FPGAで内蔵メモリ(SRAM)に対して読み書きすると、CRCWになる。
コード例.
これは、わずか2クロックで配列の最大値の値を探す SystemVerilog の例。1クロック目で全ての配列の要素の組み合わせの比較を行い、2クロック目でその結果をマージしている。メモリは Common CRCW で、codice_1 と codice_2 は同時に書き込まれている。アルゴリズムが同じメモリには同じ値を書き込むことを保証しているので問題ない。このプログラムは FPGA 上で実行できる。
module FindMax #(parameter int len = 8)
 (input bit clock, resetN, input bit[7:0] data[len], output bit[7:0] maxNo);
 typedef enum bit[1:0] {COMPARE, MERGE, DONE} State;
 State state;
 bit m[len];
 int i, j;
 always_ff @(posedge clock, negedge resetN) begin
 if (!resetN) begin
 for (i = 0; i < len; i++) m[i] <= 0;
 state <= COMPARE;
 end else begin
 case (state)
 COMPARE: begin
 for (i = 0; i < len; i++) begin
 for (j = 0; j < len; j++) begin
 if (data[i] < data[j]) m[i] <= 1;
 end
 end
 state <= MERGE;
 end
 MERGE: begin
 for (i = 0; i < len; i++) begin
 if (m[i] == 0) maxNo <= data[i];
 end
 state <= DONE;
 end
 endcase
 end
 end
endmodule
外部リンク.
University Of Maryland's prototype PRAM