並列ランダムアクセスマシン

Parallel Random Access Machines (PRAM)はモデルであり、ほとんどの並列アルゴリズムで考慮されています。ここでは、複数のプロセッサが1つのメモリブロックに接続されています。PRAMモデルには次のものが含まれます-

同様のタイプのプロセッサのセット。
すべてのプロセッサは共通のメモリユニットを共有します。プロセッサは、共有メモリを介してのみ相互に通信できます。
メモリアクセスユニット（MAU）は、プロセッサを単一の共有メモリに接続します。

ここに、 n 多数のプロセッサが独立した操作を実行できます n特定の時間単位でのデータの数。これにより、異なるプロセッサが同じメモリ位置に同時にアクセスする可能性があります。

この問題を解決するために、次の制約がPRAMモデルに適用されています。

Exclusive Read Exclusive Write (EREW) −ここでは、2つのプロセッサが同じメモリ位置から同時に読み取りまたは書き込みを行うことはできません。
Exclusive Read Concurrent Write (ERCW) −ここでは、2つのプロセッサが同じメモリ位置から同時に読み取ることはできませんが、同じメモリ位置に同時に書き込むことはできます。
Concurrent Read Exclusive Write (CREW) −ここでは、すべてのプロセッサが同じメモリ位置から同時に読み取ることは許可されていますが、同じメモリ位置に同時に書き込むことは許可されていません。
Concurrent Read Concurrent Write (CRCW) −すべてのプロセッサは、同じメモリ位置から同時に読み取りまたは書き込みを行うことができます。

PRAMモデルを実装する方法はたくさんありますが、最も顕著な方法は次のとおりです。

共有メモリモデル
メッセージパッシングモデル
データ並列モデル

共有メモリモデル

共有メモリは control parallelism 上より data parallelism。共有メモリモデルでは、複数のプロセスが異なるプロセッサで独立して実行されますが、それらは共通のメモリ空間を共有します。プロセッサのアクティビティが原因で、メモリの場所に変更があった場合、それは残りのプロセッサに表示されます。

複数のプロセッサが同じメモリ位置にアクセスすると、特定の時点で、複数のプロセッサが同じメモリ位置にアクセスする場合があります。一方がその場所を読み取り、もう一方がその場所に書き込んでいるとします。混乱を招く可能性があります。これを回避するために、次のようないくつかの制御メカニズムlock / semaphore, 相互排除を確実にするために実装されます。

共有メモリプログラミングは、以下で実装されています。

Thread libraries−スレッドライブラリは、同じメモリ位置で同時に実行される複数の制御スレッドを許可します。スレッドライブラリは、サブルーチンのライブラリを介したマルチスレッドをサポートするインターフェイスを提供します。のサブルーチンが含まれています
- スレッドの作成と破棄
- スレッドの実行のスケジューリング
- スレッド間でデータとメッセージを渡す
- スレッドコンテキストの保存と復元

スレッドライブラリの例には、-Solaris用のSolarisTMスレッド、Linuxで実装されているPOSIXスレッド、WindowsNTおよびWindows2000で使用可能なWin32スレッド、および標準のJavaTM Development Kit（JDK）の一部としてのJavaTMスレッドが含まれます。

Distributed Shared Memory (DSM) Systems− DSMシステムは、ハードウェアのサポートなしで共有メモリプログラミングを実装するために、疎結合アーキテクチャ上に共有メモリの抽象化を作成します。これらは標準ライブラリを実装し、最新のオペレーティングシステムに存在する高度なユーザーレベルのメモリ管理機能を使用します。例としては、トレッドマークシステム、ムニン、IVY、シャスタ、ブラゾス、カシミアなどがあります。
Program Annotation Packages−これは、均一なメモリアクセス特性を持つアーキテクチャに実装されています。プログラム注釈パッケージの最も注目すべき例はOpenMPです。OpenMPは機能的な並列処理を実装しています。これは主にループの並列化に焦点を当てています。

共有メモリの概念は、共有メモリシステムの低レベルの制御を提供しますが、面倒で誤っている傾向があります。アプリケーションプログラミングよりもシステムプログラミングに適しています。

共有メモリプログラミングのメリット

グローバルアドレス空間は、メモリへのユーザーフレンドリーなプログラミングアプローチを提供します。
メモリがCPUに近いため、プロセス間のデータ共有は高速で均一です。
プロセス間のデータ通信を明確に指定する必要はありません。
プロセス通信のオーバーヘッドはごくわずかです。
学ぶのはとても簡単です。

共有メモリプログラミングのデメリット

持ち運びできません。
データの局所性の管理は非常に困難です。

メッセージパッシングモデル

メッセージパッシングは、分散メモリシステムで最も一般的に使用される並列プログラミングアプローチです。ここで、プログラマーは並列処理を決定する必要があります。このモデルでは、すべてのプロセッサに独自のローカルメモリユニットがあり、通信ネットワークを介してデータを交換します。

プロセッサは、メッセージパッシングライブラリを使用してプロセッサ間の通信を行います。送信されるデータに加えて、メッセージには次のコンポーネントが含まれています-

メッセージの送信元のプロセッサのアドレス。
送信側プロセッサのデータのメモリ位置の開始アドレス。
送信データのデータ型。
送信データのデータサイズ。
メッセージの送信先のプロセッサのアドレス。
受信プロセッサのデータのメモリ位置の開始アドレス。

プロセッサは、次のいずれかの方法で相互に通信できます。

ポイントツーポイント通信
集合的コミュニケーション
メッセージパッシングインターフェイス

ポイントツーポイント通信

ポイントツーポイント通信は、メッセージパッシングの最も単純な形式です。ここで、メッセージは、次の転送モードのいずれかによって送信プロセッサから受信プロセッサに送信できます。

Synchronous mode −次のメッセージは、メッセージの順序を維持するために、前のメッセージが配信されたという確認を受信した後にのみ送信されます。
Asynchronous mode −次のメッセージを送信するために、前のメッセージの配信確認の受信は必要ありません。

集合的コミュニケーション

集合通信には、メッセージパッシング用に3つ以上のプロセッサが含まれます。以下のモードは集合的なコミュニケーションを可能にします-

Barrier −通信に含まれるすべてのプロセッサが特定のボックを実行している場合、バリアモードが可能です（ barrier block）メッセージパッシング用。
Broadcast −放送には2つのタイプがあります−
- One-to-all −ここでは、1回の操作で1つのプロセッサが、他のすべてのプロセッサに同じメッセージを送信します。
- All-to-all −ここでは、すべてのプロセッサが他のすべてのプロセッサにメッセージを送信します。

ブロードキャストされるメッセージには、次の3つのタイプがあります。

Personalized −他のすべての宛先プロセッサに一意のメッセージが送信されます。
Non-personalized −すべての宛先プロセッサが同じメッセージを受信します。
Reduction −リダクションブロードキャストでは、グループ内の1つのプロセッサが、グループ内の他のすべてのプロセッサからすべてのメッセージを収集し、それらを1つのメッセージに結合して、グループ内の他のすべてのプロセッサがアクセスできるようにします。

メッセージパッシングのメリット

並列処理の低レベルの制御を提供します。
ポータブルです。
エラーが発生しにくい。
並列同期とデータ配布のオーバーヘッドが少なくなります。

メッセージパッシングのデメリット

並列共有メモリコードと比較して、メッセージパッシングコードは一般により多くのソフトウェアオーバーヘッドを必要とします。

メッセージパッシングライブラリ

多くのメッセージパッシングライブラリがあります。ここでは、最もよく使用される2つのメッセージパッシングライブラリについて説明します。

メッセージパッシングインターフェイス（MPI）
Parallel Virtual Machine（PVM）

メッセージパッシングインターフェイス（MPI）

分散メモリシステム内のすべての並行プロセス間で通信を提供することは、普遍的な標準です。一般的に使用される並列コンピューティングプラットフォームのほとんどは、メッセージパッシングインターフェイスの少なくとも1つの実装を提供します。これは、と呼ばれる事前定義された関数のコレクションとして実装されています。library また、C、C ++、Fortranなどの言語から呼び出すことができます。MPIは、他のメッセージパッシングライブラリと比較して高速で移植性があります。

Merits of Message Passing Interface

共有メモリアーキテクチャまたは分散メモリアーキテクチャでのみ実行されます。
各プロセッサには独自のローカル変数があります。
大規模な共有メモリコンピュータと比較して、分散メモリコンピュータは安価です。

Demerits of Message Passing Interface

並列アルゴリズムには、さらにプログラミングの変更が必要です。
デバッグが難しい場合があります。そして
ノード間の通信ネットワークではうまく機能しません。

Parallel Virtual Machine（PVM）

PVMはポータブルメッセージパッシングシステムであり、別々の異種ホストマシンを接続して単一の仮想マシンを形成するように設計されています。これは、単一の管理可能な並列コンピューティングリソースです。超伝導研究、分子動力学シミュレーション、行列アルゴリズムなどの大規模な計算問題は、多くのコンピューターのメモリと総電力を使用することで、よりコスト効率よく解決できます。互換性のないコンピュータアーキテクチャのネットワークで、すべてのメッセージルーティング、データ変換、タスクスケジューリングを管理します。

Features of PVM