並列ランダムアクセス機械
並列ランダムアクセス機械（Parallel Random Access Machine、PRAM）は、並列コンピューティングにおけるアルゴリズムを設計するための抽象的な計算モデルです。このモデルは、複数のプロセッサが並行して共有メモリにアクセスする状況を想定しており、アルゴリズムの並行性を分析し、最適化するのに役立ちます。
PRAMの大きな特徴は、同期やプロセッサ間の通信といった、並列計算の複雑さを抽象化している点です。これにより、アルゴリズム設計者は、並列処理の本質的な部分、すなわち、どのように問題を分割し、並行して解決するかという点に集中できます。フリンの分類では、PRAMはMIMD（Multiple Instruction, Multiple Data）型コンピュータに分類されます。
PRAMモデルは、複数のプロセッサが同時にメモリの同じ場所にアクセスする際の制約によって、いくつかの種類に分けられます。アクセスには「読み取り」と「書き込み」の2種類があり、これらの組み合わせによって以下の4つの主要なモデルが定義されます。
1. 排他的読み取り/排他的書き込み（EREW）: このモデルでは、任意のメモリセルに対して、ある時点にアクセスできるプロセッサは1つだけです。読み取りと書き込みの両方で、複数のプロセッサが同時に同じメモリセルにアクセスすることは許可されません。
2. 並行的読み取り/排他的書き込み（CREW）: このモデルでは、複数のプロセッサが同時に同じメモリセルから読み取ることが許可されますが、書き込みは1つのプロセッサのみが行うことができます。複数のプロセッサが同時に同じメモリセルに書き込もうとすると、競合が発生します。
3. 排他的読み取り/並行的書き込み（ERCW）: このモデルは通常考慮されません。複数のプロセッサが同時に同じメモリセルに書き込むことは許可されていますが、排他的読み取りという制約が強く、実用的なモデルとは言えません。
4. 並行的読み取り/並行的書き込み（CRCW）: このモデルでは、複数のプロセッサが自由に同じメモリセルに対して読み書きできます。CRCWモデルにはさらに細かな種類があり、同時に書き込みが発生した場合の動作が異なります。
Common CRCW: 複数のプロセッサが同時に同じメモリセルに同じ値を書き込もうとする場合は許可されますが、異なる値を書き込もうとすると不正な操作となります。
Arbitrary CRCW: 同時に書き込もうとした複数のプロセッサのうち、1つのプロセッサの書き込みが成功し、他のプロセッサの書き込みは失敗します。ただし、どのプロセッサの書き込みが成功するかは不定です。
Priority CRCW: プロセッサに優先順位が付けられており、最も優先順位の高いプロセッサの書き込みが成功します。
PRAMモデルは、並列アルゴリズムを設計する際に、問題から並行性を引き出すための優れたモデルを提供します。これにより、問題を複数の小さな部分に分割し、それらを並行して解決するアルゴリズムを見つけるのに役立ちます。
実際のCPUとDRAMの組み合わせでは、DRAMが同時に複数のアクセスを処理できないため、PRAMアルゴリズムをそのまま実装することは困難です。しかし、FPGAなどのハードウェアを用いることで、SRAMのような高速なメモリを使用し、CRCWモデルを実装できます。また、PRAMモデルは、並列アルゴリズムの理論的な分析を行うための基盤としても重要です。
以下は、SystemVerilogで記述された、配列の最大値を2クロックで求めるコード例です。このコードでは、Common CRCWモデルが使用されており、複数のプロセッサが同時に同じメモリセルに書き込むことが可能です。
systemverilog
// 仮定: data[N] にはデータが格納されている
// m[N] と maxNo は共有メモリ
// クロック1: 並列比較
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
if (data[i] >= data[j])
m[i] <= 1; // iがjより大きいか等しい場合は、m[i]を1にする
else
m[i] <= 0;
// クロック2: 結果のマージ
maxNo <= 0; // 初期化
for (int i=0; i < N; i++)
if (m[i] == 1) // m[i]が1の場合は、data[i]が最大値候補
maxNo <= data[i];
このコード例では、1クロック目で全ての配列要素の比較が並列して行われ、2クロック目でその結果を統合しています。`m[i] <= 1`と`maxNo <= data[i]`は、同時に複数のプロセッサによって書き込まれます。このアルゴリズムは、同じメモリ位置に同じ値を書き込むことが保証されているため、Common CRCWモデルで正しく動作します。この例のように、PRAMモデルは並列処理を理解し、並列アルゴリズムを設計する上で非常に有用です。
フリンの分類
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
PRAMの大きな特徴は、同期やプロセッサ間の通信といった、並列計算の複雑さを抽象化している点です。これにより、アルゴリズム設計者は、並列処理の本質的な部分、すなわち、どのように問題を分割し、並行して解決するかという点に集中できます。フリンの分類では、PRAMはMIMD（Multiple Instruction, Multiple Data）型コンピュータに分類されます。
PRAMの種類
PRAMモデルは、複数のプロセッサが同時にメモリの同じ場所にアクセスする際の制約によって、いくつかの種類に分けられます。アクセスには「読み取り」と「書き込み」の2種類があり、これらの組み合わせによって以下の4つの主要なモデルが定義されます。
1. 排他的読み取り/排他的書き込み（EREW）: このモデルでは、任意のメモリセルに対して、ある時点にアクセスできるプロセッサは1つだけです。読み取りと書き込みの両方で、複数のプロセッサが同時に同じメモリセルにアクセスすることは許可されません。
2. 並行的読み取り/排他的書き込み（CREW）: このモデルでは、複数のプロセッサが同時に同じメモリセルから読み取ることが許可されますが、書き込みは1つのプロセッサのみが行うことができます。複数のプロセッサが同時に同じメモリセルに書き込もうとすると、競合が発生します。
3. 排他的読み取り/並行的書き込み（ERCW）: このモデルは通常考慮されません。複数のプロセッサが同時に同じメモリセルに書き込むことは許可されていますが、排他的読み取りという制約が強く、実用的なモデルとは言えません。
4. 並行的読み取り/並行的書き込み（CRCW）: このモデルでは、複数のプロセッサが自由に同じメモリセルに対して読み書きできます。CRCWモデルにはさらに細かな種類があり、同時に書き込みが発生した場合の動作が異なります。
Common CRCW: 複数のプロセッサが同時に同じメモリセルに同じ値を書き込もうとする場合は許可されますが、異なる値を書き込もうとすると不正な操作となります。
Arbitrary CRCW: 同時に書き込もうとした複数のプロセッサのうち、1つのプロセッサの書き込みが成功し、他のプロセッサの書き込みは失敗します。ただし、どのプロセッサの書き込みが成功するかは不定です。
Priority CRCW: プロセッサに優先順位が付けられており、最も優先順位の高いプロセッサの書き込みが成功します。
PRAMモデルは、並列アルゴリズムを設計する際に、問題から並行性を引き出すための優れたモデルを提供します。これにより、問題を複数の小さな部分に分割し、それらを並行して解決するアルゴリズムを見つけるのに役立ちます。
実装
実際のCPUとDRAMの組み合わせでは、DRAMが同時に複数のアクセスを処理できないため、PRAMアルゴリズムをそのまま実装することは困難です。しかし、FPGAなどのハードウェアを用いることで、SRAMのような高速なメモリを使用し、CRCWモデルを実装できます。また、PRAMモデルは、並列アルゴリズムの理論的な分析を行うための基盤としても重要です。
コード例
以下は、SystemVerilogで記述された、配列の最大値を2クロックで求めるコード例です。このコードでは、Common CRCWモデルが使用されており、複数のプロセッサが同時に同じメモリセルに書き込むことが可能です。
systemverilog
// 仮定: data[N] にはデータが格納されている
// m[N] と maxNo は共有メモリ
// クロック1: 並列比較
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
if (data[i] >= data[j])
m[i] <= 1; // iがjより大きいか等しい場合は、m[i]を1にする
else
m[i] <= 0;
// クロック2: 結果のマージ
maxNo <= 0; // 初期化
for (int i=0; i < N; i++)
if (m[i] == 1) // m[i]が1の場合は、data[i]が最大値候補
maxNo <= data[i];
このコード例では、1クロック目で全ての配列要素の比較が並列して行われ、2クロック目でその結果を統合しています。`m[i] <= 1`と`maxNo <= data[i]`は、同時に複数のプロセッサによって書き込まれます。このアルゴリズムは、同じメモリ位置に同じ値を書き込むことが保証されているため、Common CRCWモデルで正しく動作します。この例のように、PRAMモデルは並列処理を理解し、並列アルゴリズムを設計する上で非常に有用です。
関連項目
フリンの分類
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
もう一度検索
【記事の利用について】
タイトルと記事文章は、記事のあるページにリンクを張っていただければ、無料で利用できます。
※画像は、利用できませんのでご注意ください。
【リンクついて】
リンクフリーです。