並列ランダムアクセス機械とは? わかりやすく解説

Weblio 辞書 > 同じ種類の言葉 > 工業 > 装置 > 機械 > 並列ランダムアクセス機械の意味・解説 

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

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2020/04/19 04:52 UTC 版)

ナビゲーションに移動 検索に移動

並列ランダムアクセス機械(へいれつランダムアクセスきかい、: 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] <= 1maxNo <= 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

関連項目

外部リンク

University Of Maryland's prototype PRAM

参考文献

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






並列ランダムアクセス機械と同じ種類の言葉


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「並列ランダムアクセス機械」の関連用語

並列ランダムアクセス機械のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



並列ランダムアクセス機械のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの並列ランダムアクセス機械 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS