パラレルRAM

コンピュータサイエンスにおいて、並列ランダムアクセスマシン（並列 RAMまたはPRAM）は、共有メモリ 抽象マシンです。その名前が示すように、PRAM はランダムアクセスマシン(RAM) の並列コンピューティングのアナロジーとして意図されています（ランダムアクセスメモリと混同しないでください）。^[1] RAM がシーケンシャルアルゴリズム設計者によってアルゴリズムのパフォーマンス（時間計算量など）をモデル化するのに使用されるのと同様に、PRAM は並列アルゴリズム設計者によって並列アルゴリズムのパフォーマンス（時間計算量など、想定されるプロセッサの数も通常指定される）をモデル化するのために使用されます。 RAM モデルがキャッシュメモリとメインメモリへのアクセス時間などの実際的な問題を無視するのと同様に、PRAM モデルは同期や通信などの問題を無視しますが、任意の数のプロセッサ（問題のサイズに依存）を提供します。たとえば、アルゴリズムのコストは、2 つのパラメーター O(時間) と O(時間 × プロセッサ数) を使用して推定されます。

同じ共有メモリ位置に同時にアクセスする際に一般的にインターロックと呼ばれる読み取り/書き込みの競合は、次のいずれかの戦略によって解決されます。

1. 排他的読み取り/排他的書き込み (EREW) - 各メモリセルは、一度に 1 つのプロセッサによってのみ読み取りまたは書き込みが可能です。
2. 同時読み取り排他書き込み (CREW) - 複数のプロセッサがメモリセルを読み取ることができますが、一度に書き込むことができるのは 1 つだけです。
3. 排他的読み取り同時書き込み（ERCW）—ほとんどの場合、電力消費量が増えないため考慮されないことが多い^[2]
4. 同時読み取り同時書き込み（CRCW）—複数のプロセッサが読み取りと書き込みを行うことができます。CRCW PRAMは、同時ランダムアクセスマシンと呼ばれることもあります。^[3]

ここで、E と C はそれぞれ「排他的」と「同時」を表します。読み取りでは矛盾は発生しませんが、同時書き込みはさらに次のように定義されます。

共通- すべてのプロセッサが同じ値を書き込む。それ以外の場合は不正

恣意的- 恣意的な試みは1つだけが成功し、他の試みは失敗する

優先度- プロセッサのランクは誰が書き込みできるかを示します

SUM、論理 AND、MAX などの別の種類の配列削減操作。

PRAM のアルゴリズムの開発を検討する際には、いくつかの単純化された仮定が立てられます。これらは次のとおりです。

1. マシン内のプロセッサの数に制限はありません。
2. どのメモリ位置もどのプロセッサからでも一様にアクセスできます。
3. システム内の共有メモリの量に制限はありません。
4. リソースの競合はありません。
5. これらのマシンで作成されたプログラムは、一般にSIMD型です。

こうした種類のアルゴリズムは、並行性の活用を理解し、元の問題を類似のサブ問題に分割して並列に解決するのに役立ちます。Wyllie の 1979 年の論文^{[4]で正式な「P-RAM」モデルが導入された目的は、}チューリング マシンに類似した方法で並列アルゴリズムの分析を定量化することだった。分析は、CREW モデルを使用した MIMD プログラミング モデルに焦点を当てていましたが、CRCW モデルの実装や SIMD マシンへの実装など、多くのバリエーションが一定のオーバーヘッドのみで可能であることが示されました。

PRAM アルゴリズムは、 CPUとダイナミック ランダム アクセス メモリ(DRAM)の組み合わせで並列化することはできません。これは、DRAM では単一のバンクへの同時アクセス (バンク内の異なるアドレスも不可) が許可されないためです。ただし、ハードウェアで実装したり、フィールド プログラマブル ゲート アレイ(FPGA) の内部スタティック ランダム アクセス メモリ(SRAM) ブロックへの読み取り/書き込みを行うことはできます。これは、CRCW アルゴリズムを使用して実行できます。

ただし、PRAM (または RAM) アルゴリズムの実用的妥当性のテストは、そのコスト モデルがコンピューターの効果的な抽象化を提供するかどうかによって決まります。そのコンピューターの構造は、抽象モデルとはまったく異なる場合があります。挿入する必要があるソフトウェアとハ​​ードウェアのレイヤーに関する知識は、この記事の範囲外です。ただし、Vishkin (2011) などの記事では、明示的なマルチスレッド(XMT) パラダイムによって PRAM のような抽象化がどのようにサポートされるかが示されており、Caragea & Vishkin (2011) などの記事では、最大フロー問題に対する PRAM アルゴリズムが、同じ問題に対する最速のシリアル プログラムに比べて大幅な高速化を実現できることが示されています。Ghanim、Vishkin、Barua (2018) の記事では、PRAM アルゴリズムをそのまま使用しても、XMT 上のマルチスレッド プログラムとしてキャストするための追加の作業がなくても、競争力のあるパフォーマンスを実現できることが示されました。

これは、わずか 2 クロック サイクルで配列内の最大値を見つけるSystemVerilogコードの例です。最初のクロックで配列内の要素のすべての組み合わせを比較し、2 番目のクロックで結果をマージします。CRCW メモリを使用しm[i] <= 1、maxNo <= data[i]同時に書き込まれます。アルゴリズムによって同じ値が同じメモリに書き込まれることが保証されるため、同時実行によって競合は発生しません。このコードはFPGAハードウェアで実行できます。

module FindMax #(パラメーターint len = 8 ) (入力ビットclock 、resetN 、入力ビット[ 7 : 0 ]データ[ len ]、出力ビット[ 7 : 0 ] maxNo ); typedef enum bit [ 1 : 0 ] { COMPARE 、MERGE 、DONE } State ; State state ; bit m [ len ]; int i 、j ; always_ff @(ポーズドエッジclock 、ネゲドリセットN ) 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 ];
終了状態<= DONE ;終了ケース終了終了終了モジュール                    
                      
                
            
        
    

• PRAMアルゴリズムの分析
• フリンの分類法
• ロックフリーおよび待機フリーのアルゴリズム
• ランダムアクセスマシン
• 並列プログラミングモデル
• エクストリーム
• パラレル外部メモリ（モデル）

• Eppstein, David; Galil, Zvi (1988)、「組み合わせ計算のための並列アルゴリズム技術」、Annu. Rev. Comput. Sci.、3 : 233–283、doi :10.1146/annurev.cs.03.060188.001313
• JaJa, Joseph (1992)、『並列アルゴリズム入門』、Addison-Wesley、ISBN 0-201-54856-9
• Karp, Richard M.; Ramachandran, Vijaya (1988)、「共有メモリマシンの並列アルゴリズムの調査」、カリフォルニア大学バークレー校、EECS 学部、技術報告書、UCB/CSD-88-408
• ケラー、ヨルグ。クリストフ・ケスラー;イェスパー・トラフ (2001)。実践的な PRAM プログラミング。ジョン・ワイリー・アンド・サンズ。ISBN 0-471-35351-5。
• Vishkin, Uzi (2009)、Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques、104ページ(PDF)、1992年以来メリーランド大学カレッジパーク校、テルアビブ大学、テクニオンで教えられている並列アルゴリズムに関するコースの授業ノート
• Vishkin, Uzi (2011)、「単純な抽象化を使用して並列処理コンピューティングを再発明する」、Communications of the ACM、54 : 75–85、doi : 10.1145/1866739.1866757
• Caragea, George Constantin; Vishkin, Uzi (2011)、「簡単な発表: 並列最大フローの高速化の向上」、アルゴリズムとアーキテクチャにおける並列処理に関する第 23 回 ACM シンポジウムの議事録 - SPAA '11、p. 131、doi :10.1145/1989493.1989511、ISBN 9781450307437、S2CID  5511743
• Ghanim, Fady; Vishkin, Uzi; Barua, Rajeev (2018)、「ICE を使用した簡単な PRAM ベースの高性能並列プログラミング」、IEEE Transactions on Parallel and Distributed Systems、29 (2): 377–390、doi : 10.1109/TPDS.2017.2754376、hdl : 1903/18521

• ザールラント大学のプロトタイプPRAM
• メリーランド大学のPRAM-On-Chipプロトタイプ。このプロトタイプは、多数の並列プロセッサとそれらを相互接続するためのファブリックを1つのチップに搭載することを目指しています。
• XMTC: PRAM のようなプログラミング - ソフトウェア リリース