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

並列ランダムアクセス機械（へいれつランダムアクセスきかい、英: Parallel Random Access Machine, PRAM）は、並列コンピューティングに適用可能なアルゴリズムを設計するための抽象機械である。同期や通信といった細かな部分を省き、並行性をいかに引き出すかに集中することが可能となる。フリンの分類によれば、PRAM は MIMD 型コンピュータに相当する。

種類

同期式PRAMでは、複数のCPUが同時並行的に共有メモリ上の同じ位置にアクセスする可能性がある。PRAMモデルにはいくつかの種類があり、それらの違いは主にそのような同じ位置への同時アクセスを許すか禁止するかである。さらにアクセスには「読み取り」と「書き込み」があるので、以下のような4種類に分類される。

1. 排他的読み取り/排他的書き込み（Exclusive Read Exclusive Write、EREW） - 各メモリセルはある時点では1つのプロセッサだけが読み書きできる。
2. 並行的読み取り/排他的書き込み（Conccurrent Read Exclusive Write、CREW） - 読み取りは同時に行えるが、書き込みは一度に1つのプロセッサのみである。
3. 排他的読み取り/並行的書き込み（Exclusive Read Conccurrent Write、ERCW） - 考慮されない。
4. 並行的読み取り/並行的書き込み（Conccurrent Read Conccurrent Write、CRCW） - 複数のプロセッサが自由に読み書きできる。
   • Common CRCW - プロセッサ群が同じ値を同時に書き込むのはOKだが、そうでない場合は不正な操作となる。
   • Arbitrary CRCW - 同時に書き込もうとしたうちの1つだけが成功し、他は失敗する（どれが成功するかは不明）。
   • Priority CRCW - 優先順位によって書き込みが成功するプロセッサが決められる。

問題から並列性を引き出し、分割して並行的にそれを解くことを可能にするアルゴリズムの発見に役立つ。

実装

CPU と DRAM の組み合わせでは、DRAM が同時アクセスできないため、これらのアルゴリズムを実現できないが、ハードウェアとして実装したり、FPGAで内蔵メモリ(SRAM)に対して読み書きすると、CRCWになる。

コード例

これは、わずか2クロックで配列の最大値の値を探す SystemVerilog の例。1クロック目で全ての配列の要素の組み合わせの比較を行い、2クロック目でその結果をマージしている。メモリは Common CRCW で、m[i] <= 1 と maxNo <= data[i] は同時に書き込まれている。アルゴリズムが同じメモリには同じ値を書き込むことを保証しているので問題ない。このプログラムは 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

関連項目

• フリンの分類
• Lock-freeとWait-freeアルゴリズム
• ランダムアクセス機械

外部リンク

University Of Maryland's prototype PRAM

参考文献

• Keller, Jörg; Christoph Keßler, Jesper Träff (2001年). Practical PRAM Programming. John Wiley and Sons. 0471353515