「並列ランダムアクセス機械」の版間の差分
削除された内容 追加された内容
編集の要約なし |
|||
16行目:
CPU と [[DRAM]] の組み合わせでは、DRAM が同時アクセスできないため、これらのアルゴリズムを実現できないが、ハードウェアとして実装したり、[[FPGA]]で内蔵メモリ([[Static Random Access Memory|SRAM]])に対して読み書きすると、CRCWになる。
<!-- PRAMの具体的な実装は存在しないため、アルゴリズムは[[擬似コード]]で書かれる（ただし、研究レベルの実装は[http://www.eng.umd.edu/ こちら（外部リンクも参照）]などで行われている）。-->
==コード例==
これは、わずか2クロックで配列の最大値の値を探す [[SystemVerilog]] の例。1クロック目で全ての配列の要素の組み合わせの比較を行い、2クロック目でその結果をマージしている。メモリは CRCW で、<code>m[i] <= 1</code> と <code>maxNo <= data[i]</code> は同時に書き込まれている。アルゴリズムが同じメモリには同じ値を書き込むことを保証しているので問題ない。このプログラムは [[FPGA]] 上で実行できる。
<source lang="SystemVerilog">
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
</source>
== 関連項目 ==
| |||