Parallel-algorithm-parallel-random-access-machines
並列ランダムアクセスマシン
- Parallel Random Access Machines（PRAM）*はモデルであり、ほとんどの並列アルゴリズムで考慮されています。 ここでは、複数のプロセッサがメモリの単一ブロックに接続されています。 PRAMモデルには以下が含まれます-
- 同様のタイプのプロセッサーのセット。
- すべてのプロセッサは、共通のメモリユニットを共有します。 プロセッサは、共有メモリを介してのみ相互に通信できます。
- メモリアクセスユニット（MAU）は、プロセッサを単一の共有メモリに接続します。
ここで、 n 個のプロセッサは、特定の時間単位で n 個のデータに対して独立した操作を実行できます。 これにより、異なるプロセッサが同じメモリ位置に同時にアクセスする可能性があります。
この問題を解決するために、次の制約がPRAMモデルに適用されています-
- * Exclusive Read Exclusive Write（EREW）*-ここでは、2つのプロセッサが同じメモリ位置から同時に読み書きすることはできません。
- 排他的読み取り同時書き込み（ERCW）-ここでは、2つのプロセッサが同じメモリ位置から同時に読み取ることはできませんが、同じメモリ位置に同時に書き込むことはできません。
- 同時読み取り排他書き込み（CREW）-ここでは、すべてのプロセッサが同じメモリ位置から同時に読み取ることができますが、同じメモリ位置に同時に書き込むことはできません。
- 同時読み取り同時書き込み（CRCW）-すべてのプロセッサは、同じメモリ位置から同時に読み取りまたは書き込みを行うことができます。
PRAMモデルを実装する多くの方法がありますが、最も顕著なものは次のとおりです-
- 共有メモリモデル
- メッセージパッシングモデル
- データ並列モデル
共有メモリモデル
共有メモリは、 data parallelism よりも control parallelism を重視しています。 共有メモリモデルでは、複数のプロセスが異なるプロセッサで独立して実行されますが、共通のメモリ空間を共有します。 プロセッサのアクティビティにより、メモリの場所に変更があった場合、残りのプロセッサから見えるようになります。
複数のプロセッサが同じメモリロケーションにアクセスするため、特定の時点で、複数のプロセッサが同じメモリロケーションにアクセスすることがあります。 1人がその場所を読み取り、もう1人がその場所に書き込みを行っているとします。 混乱を招く可能性があります。 これを回避するために、 lock/semaphore などの制御メカニズムを実装して、相互排除を保証します。
共有メモリプログラミングは次のように実装されています-
- スレッドライブラリ-スレッドライブラリは、同じメモリ位置で同時に実行される複数の制御スレッドを許可します。 スレッドライブラリは、サブルーチンのライブラリを介してマルチスレッドをサポートするインターフェイスを提供します。 サブルーチンが含まれています
- スレッドの作成と破棄
- スレッドの実行のスケジューリング
- スレッド間でデータとメッセージを渡す
- スレッドコンテキストの保存と復元
スレッドライブラリの例には、Solaris用のSolarisTMスレッド、Linuxで実装されたPOSIXスレッド、Windows NTおよびWindows 2000で使用可能なWin32スレッド、標準JavaTM Development Kit（JDK）の一部としてのJavaTMスレッドが含まれます。
- 分散共有メモリ（DSM）システム-DSMシステムは、ハードウェアサポートなしで共有メモリプログラミングを実装するために、疎結合アーキテクチャで共有メモリの抽象化を作成します。 標準ライブラリを実装し、最新のオペレーティングシステムに存在する高度なユーザーレベルのメモリ管理機能を使用します。 例には、Tread Marks System、Munin、IVY、Shasta、Brazos、Cashmereが含まれます。
- プログラム注釈パッケージ-これは、均一なメモリアクセス特性を持つアーキテクチャに実装されています。 プログラム注釈パッケージの最も注目すべき例は、OpenMPです。 OpenMPは機能的な並列処理を実装しています。 主にループの並列化に焦点を当てています。
共有メモリの概念は、共有メモリシステムの低レベルの制御を提供しますが、退屈で誤っている傾向があります。 アプリケーションプログラミングよりもシステムプログラミングに適しています。
共有メモリプログラミングのメリット
- グローバルアドレス空間は、メモリに対するユーザーフレンドリーなプログラミングアプローチを提供します。
- メモリはCPUに近いため、プロセス間のデータ共有は高速で均一です。
- プロセス間でデータの通信を明確に指定する必要はありません。
- プロセス通信のオーバーヘッドは無視できます。
- 学ぶのはとても簡単です。
共有メモリプログラミングのデメリット
- ポータブルではありません。
- データの局所性の管理は非常に困難です。
メッセージパッシングモデル
メッセージパッシングは、分散メモリシステムで最も一般的に使用される並列プログラミングアプローチです。 ここでは、プログラマーが並列処理を決定する必要があります。 このモデルでは、すべてのプロセッサに独自のローカルメモリユニットがあり、通信ネットワークを介してデータを交換します。
プロセッサは、メッセージパッシングライブラリを使用して、プロセッサ間の通信を行います。 送信されるデータとともに、メッセージには次のコンポーネントが含まれます-
- メッセージの送信元のプロセッサのアドレス。
- 送信プロセッサのデータのメモリ位置の開始アドレス。
- 送信データのデータ型。
- 送信データのデータサイズ。
- メッセージの送信先のプロセッサのアドレス。
- 受信プロセッサのデータのメモリ位置の開始アドレス。
プロセッサは、次のいずれかの方法で相互に通信できます-
- ポイントツーポイント通信
- 集団コミュニケーション
- メッセージパッシングインターフェース
ポイントツーポイント通信
ポイントツーポイント通信は、メッセージパッシングの最も単純な形式です。 ここでは、次の転送モードのいずれかによって、メッセージを送信プロセッサから受信プロセッサに送信できます-
- 同期モード-次のメッセージは、メッセージのシーケンスを維持するために、前のメッセージが配信されたことの確認を受信した後にのみ送信されます。
- 非同期モード-次のメッセージを送信するには、前のメッセージの配信確認の受信は必要ありません。
集団コミュニケーション
集団通信では、メッセージの受け渡しに3つ以上のプロセッサが必要です。 次のモードは、集団通信を可能にします-
- バリア-通信に含まれるすべてのプロセッサがメッセージパッシングのために特定のブロック（バリアブロック）を実行している場合、バリアモードが可能です。
- ブロードキャスト-ブロードキャストには2つのタイプがあります-
- One-to-all -ここでは、1つの操作を持つ1つのプロセッサが他のすべてのプロセッサに同じメッセージを送信します。
- All-to-All -ここでは、すべてのプロセッサが他のすべてのプロセッサにメッセージを送信します。
ブロードキャストされるメッセージには3つのタイプがあります-
- Personalized -他のすべての宛先プロセッサに一意のメッセージが送信されます。
- 非パーソナライズ-すべての宛先プロセッサが同じメッセージを受け取ります。
- リダクション-リダクションブロードキャストでは、グループの1つのプロセッサがグループ内の他のすべてのプロセッサからすべてのメッセージを収集し、グループ内の他のすべてのプロセッサがアクセスできる単一のメッセージに結合します。
メッセージパッシングのメリット
- 並列性の低レベル制御を提供します。
- ポータブルです。
- エラーが発生しにくい。
- 並列同期とデータ配布のオーバーヘッドが少なくなります。
メッセージパッシングのデメリット
- 並列共有メモリコードと比較して、メッセージパッシングコードは一般により多くのソフトウェアオーバーヘッドを必要とします。
メッセージパッシングライブラリ
多くのメッセージパッシングライブラリがあります。 ここでは、最もよく使用される2つのメッセージパッシングライブラリについて説明します-
- メッセージパッシングインターフェース（MPI） *並列仮想マシン（PVM）
メッセージパッシングインターフェース（MPI）
分散メモリシステム内のすべての並行プロセス間で通信を提供することは、普遍的な標準です。 一般的に使用される並列コンピューティングプラットフォームのほとんどは、メッセージパッシングインターフェイスの少なくとも1つの実装を提供します。* library *と呼ばれる定義済み関数のコレクションとして実装されており、C、C ++、Fortranなどの言語から呼び出すことができます。 MPIは、他のメッセージパッシングライブラリと比較して高速で移植性があります。
メッセージパッシングインターフェイスのメリット
- 共有メモリアーキテクチャまたは分散メモリアーキテクチャでのみ実行されます。
- 各プロセッサには独自のローカル変数があります。
- 大規模な共有メモリコンピュータと比較して、分散メモリコンピュータは安価です。
メッセージパッシングインターフェースのデメリット
- 並列アルゴリズムには、さらにプログラミングを変更する必要があります。
- デバッグが難しい場合があります。そして
- ノード間の通信ネットワークではうまく機能しません。
並列仮想マシン（PVM）
PVMは、個別の異種ホストマシンを接続して単一の仮想マシンを形成するように設計された、ポータブルなメッセージパッシングシステムです。 これは、単一の管理可能な並列コンピューティングリソースです。 超伝導研究、分子動力学シミュレーション、マトリックスアルゴリズムなどの大規模な計算上の問題は、多くのコンピューターのメモリと総処理能力を使用することで、よりコスト効率よく解決できます。 互換性のないコンピューターアーキテクチャのネットワークで、すべてのメッセージルーティング、データ変換、タスクスケジューリングを管理します。
- PVMの機能*
- インストールと設定が非常に簡単です。
- 複数のユーザーが同時にPVMを使用できます。
- 1人のユーザーが複数のアプリケーションを実行できます。
- それは小さなパッケージです。
- C、C ++、Fortranをサポート。
- PVMプログラムの所定の実行について、ユーザーはマシンのグループを選択できます。
- これはメッセージパッシングモデルです。
- プロセスベースの計算。
- 異種アーキテクチャをサポートします。
データ並列プログラミング
データ並列プログラミングモデルの主な焦点は、データセットの操作を同時に実行することです。 データセットは、配列、ハイパーキューブなどの構造に編成されます。 プロセッサは、同じデータ構造に対して操作をまとめて実行します。 各タスクは、同じデータ構造の異なるパーティションで実行されます。
すべてのアルゴリズムをデータ並列性の観点から指定できるわけではないため、制限的です。 これが、データの並列性が普遍的でない理由です。
データ並列言語は、データの分解とプロセッサへのマッピングを指定するのに役立ちます。 また、プログラマがデータ（たとえば、どのデータをどのプロセッサに送信するか）を制御して、プロセッサ内の通信量を削減できるようにするデータ配布ステートメントも含まれています。
