PRAM モデル（PRAM: ピーラム）
英語表記: PRAM Model (Parallel Random Access Machine Model)
概要
PRAMモデルは、「アルゴリズムと計算量」の分野において、並列処理アルゴリズムの効率を理論的に分析するために用いられる抽象的な計算モデルです。これは、複数の処理装置（プロセッサ）が単一の共有メモリを介して完全に同期しながら動作することを前提とする理想的な「並列処理モデル」です。現実のハードウェアの制約（通信遅延やネットワークトポロジーなど）を排除し、純粋にアルゴリズムが持つ並列性のみに焦点を当てて計算量を評価する際の、基礎的なベンチマークとして機能します。
詳細解説
PRAMモデルが「並列・分散アルゴリズム」の文脈でなぜ重要かというと、現実の複雑な並列計算機（分散メモリやキャッシュコヒーレンシの問題を抱えるマシン）上でアルゴリズムの性能を評価しようとすると、ハードウェアの影響が大きすぎてアルゴリズム本来の計算量を把握しづらくなるためです。PRAMモデルは、これらの物理的な制約をすべて取り払い、「理想的な並列環境」を定義することで、アルゴリズムの性能を純粋に比較できるようにします。これは計算機科学において大変強力なツールです。
構成要素と動作原理
PRAMモデルは、主に以下の2つの要素で構成されています。
- プロセッサ（P: Processors）: 複数の独立した処理装置です。これらはすべて同じ命令セットを持ち、完全に同期して動作します。つまり、すべてのプロセッサはクロックサイクルに合わせて同時にステップを実行します。
- 共有グローバルメモリ（M: Shared Global Memory）: すべてのプロセッサが均一な時間でアクセスできる単一のメモリ空間です。プロセッサ間の通信は、この共有メモリの読み書きを通じて行われます。
PRAMモデルの分類（並列処理モデルの核心）
PRAMモデルの理論的な複雑さの大部分は、複数のプロセッサが同時に同じメモリセルにアクセスしようとした場合（競合：コンフリクト）をどのように処理するか、という点にあります。この競合の許容度によって、PRAMモデルは厳密に4種類に分類され、これが「アルゴリズムと計算量」の分析において非常に重要な要素となります。
| モデル名 | 読み出し (Read) | 書き込み (Write) | 計算能力の強さ |
| :— | :— | :— | :— |
| EREW (Exclusive Read, Exclusive Write) | 排他的 | 排他的 | 最も弱い |
| CREW (Concurrent Read, Exclusive Write) | 並行許容 | 排他的 | 中程度 |
| ERCW (Exclusive Read, Concurrent Write) | 排他的 | 並行許容 | 中程度 |
| CRCW (Concurrent Read, Concurrent Write) | 並行許容 | 並行許容 | 最も強い |
これらのモデルの強さは、アルゴリズムの並列時間計算量に直接影響します。例えば、CRCWモデルでO(1)（定数時間）で解ける問題が、より制約の厳しいEREWモデルではO(log N)の時間を要することがあります。並列アルゴリズムを設計する際は、どのPRAMモデルを前提とするかで、実現可能な最高速度が変わってくるため、この分類は「並列処理モデル」の議論において欠かせない知識となります。
CRCWの競合解決ルール
最も強力なCRCWモデルでは、複数のプロセッサが同時に同じメモリセルに書き込むことを許容します。この場合、最終的にどのデータがメモリに残るかを決めるためのルールが必要です。
- Common (共通): 書き込まれるデータがすべて同じ場合にのみ書き込みを許可します。
- Arbitrary (任意): 競合が発生した場合、ランダムに選ばれたプロセッサのデータのみが書き込まれます。
- Priority (優先度): プロセッサにあらかじめ優先度を割り当てておき、最も高い優先度のプロセッサのデータが採用されます。
このようにPRAMモデルは、理想化された環境を設定することで、アルゴリズムが持つ真の並列性能、すなわち「計算量」を厳密に測定することを可能にしているのです。
具体例・活用シーン
PRAMモデルは理論モデルであるため、現実のコンピュータそのものを指すわけではありませんが、その考え方は並列アルゴリズム設計の基礎となっています。
具体例：並列処理アルゴリズムの設計
- 並列プレフィックス和 (Parallel Prefix Sum): N個の要素の累積和を求める問題は、逐次処理ではO(N)かかりますが、PRAMモデル（特にCREWやCRCW）を仮定することで、O(log N)の時間で解けることが証明されています。これは、アルゴリズムの並列性を最大限に引き出す設計の指針となります。
- 行列の並列乗算: 大規模な行列乗算を複数のプロセッサに割り当てる際、PRAMモデルは理想的な通信環境を提供するため、理論上の最速時間を計算するのに使われます。
アナロジー：白い巨大な会議室とルールブック
PRAMモデルの動作を理解するための最も分かりやすい比喩は、「白い巨大な会議室」を使うチームの物語です。
ある大規模なプロジェクトチーム（プロセッサたち）が、共同で一つの問題を解決しようとしています。会議室の中央には、全員がアクセスできる巨大な「共有ホワイトボード」（共有メモリ）があります。
- 同期（クロック）: チームメンバーは全員、秒針の音に合わせて一斉に作業を開始し、一斉に作業を終えなければなりません。誰か一人が遅れることは許されません。
- 理想的な通信: メンバーは、ホワイトボードのどこにいても、書き込まれた内容を瞬時に、同じ時間で読むことができます。
- ルールブック（PRAMの分類）: チームには、ホワイトボードを使うための厳しいルールがあります。
- EREWチーム: 「誰かが読んでいる最中や書いている最中は、誰も触ってはいけない」という最も厳しいルールです。効率は悪いですが、競合は絶対に起きません。
- CRCWチーム: 「みんな同時に読んでいいし、同時に書いてもいい。ただし、同時に書き込むときは、事前に決めた優先順位の高い人の内容だけが残る」という最も自由なルールです。これは極めて高速ですが、ルールの設計が複雑になります。
このように、PRAMモデルは、現実の通信遅延（会議室の端と端の人が話す時間）を無視し、いかに「ルールブック（モデルの分類）」を工夫して、最短時間（計算量）で問題を解決できるか、という理論的な限界を探るために使われているのです。
資格試験向けチェックポイント
PRAMモデルは、特に「応用情報技術者試験」や「高度試験」の午前問題において、並列処理の基礎知識として問われる可能性があります。「ITパスポート」や「基本情報技術者試験」では、PRAMという名称そのものよりも、「並列アルゴリズムの計算量分析」という文脈で重要になります。
| 試験レベル | 重点的に抑えるべきポイント |
| :— | :— |
| 基本情報技術者試験 | PRAMが「並列処理モデル」であり、共有メモリ（Shared Memory）を使用する理論モデルであること。並列アルゴリズムの効率（計算量）を評価するために使われること。 |
| 応用情報技術者試験 | PRAMの基本的な定義に加え、メモリ競合の扱いによる分類（EREW, CREW, CRCW）とその計算能力の強さの順序を理解すること。CRCW > CREW > EREW の関係は頻出です。 |
| 共通の注意点 | PRAMモデルは理想的な同期と均一なアクセス時間を仮定している点に着目しましょう。現実の分散システム（ネットワーク遅延があるもの）との違いを問われることがあります。PRAMはハードウェアの制約を無視して、アルゴリズムの並列性のみを評価するツールである、という認識が重要です。 |
関連用語
PRAMモデルは、並列処理の理論的な土台ですが、現実の並列計算機の分類やアーキテクチャと対比して学ぶと理解が深まります。
- Flynnの分類 (フリンの分類): 現実のコンピュータアーキテクチャを命令とデータの流れで分類する手法（SISD, SIMD, MISD, MIMD）。
- 分散メモリモデル: 共有メモリを持たず、プロセッサがネットワークを介してメッセージ交換により通信を行うモデル。PRAMモデルと対比されることが多いです。
- 並列計算量理論: 並列アルゴリズムの実行に必要な時間やプロセッサ数を分析する理論。
※上記以外にも多くの関連用語が存在しますが、提供されたインプット材料には具体的なリストがないため、情報不足です。アルゴリズムの計算量を扱う上で重要な「計算複雑性クラス」や「ネットワークトポロジー」なども関連します。
