|
並列ランダムアクセス機械並列ランダムアクセス機械（へいれつランダムアクセスきかい、英: Parallel Random Access Machine, PRAM）は、並列コンピューティングに適用可能なアルゴリズムを設計するための抽象機械である。同期や通信といった細かな部分を省き、並行性をいかに引き出すかに集中することが可能となる。フリンの分類によれば、PRAM は MIMD 型コンピュータに相当する。 種類同期式PRAMでは、複数のCPUが同時並行的に共有メモリ上の同じ位置にアクセスする可能性がある。PRAMモデルにはいくつかの種類があり、それらの違いは主にそのような同じ位置への同時アクセスを許すか禁止するかである。さらにアクセスには「読み取り」と「書き込み」があるので、以下のような4種類に分類される。
問題から並列性を引き出し、分割して並行的にそれを解くことを可能にするアルゴリズムの発見に役立つ。 実装CPU と DRAM の組み合わせでは、DRAM が同時アクセスできないため、これらのアルゴリズムを実現できないが、ハードウェアとして実装したり、FPGAで内蔵メモリ(SRAM)に対して読み書きすると、CRCWになる。 コード例これは、わずか2クロックで配列の最大値の値を探す SystemVerilog の例。1クロック目で全ての配列の要素の組み合わせの比較を行い、2クロック目でその結果をマージしている。メモリは Common CRCW で、 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 参考文献
|
Portal di Ensiklopedia Dunia
