Parallel-algorithm-introduction
並列アルゴリズム-はじめに
- アルゴリズム*は、ユーザーから入力を受け取り、何らかの計算後に出力を生成する一連のステップです。 *並列アルゴリズム*は、異なる処理デバイスで複数の命令を同時に実行し、個々の出力をすべて組み合わせて最終結果を生成できるアルゴリズムです。
並行処理
インターネットの成長とともにコンピューターが容易に利用できるようになったことで、データの保存および処理方法が変わりました。 私たちは、データが豊富にある日と年齢に住んでいます。 毎日、複雑なコンピューティングを必要とする膨大な量のデータを迅速に処理しています。 時には、同時に発生する類似または相互に関連するイベントからデータを取得する必要があります。 これは、複雑なタスクを分割して複数のシステムを処理し、迅速に出力を生成できる*並行処理*が必要な場所です。
大量の複雑なデータの処理がタスクに含まれる場合、同時処理が不可欠です。 例には、大規模データベースへのアクセス、航空機試験、天文計算、原子および核物理学、生物医学分析、経済計画、画像処理、ロボット工学、天気予報、ウェブベースのサービスなどが含まれます。
並列処理とは何ですか？
- 並列*は、複数の命令セットを同時に処理するプロセスです。 合計計算時間を短縮します。 並列処理は、*並列コンピューター*を使用して実装できます。 多くのプロセッサを搭載したコンピューター。 並列コンピューターには、マルチタスクをサポートする並列アルゴリズム、プログラミング言語、コンパイラー、およびオペレーティングシステムが必要です。
このチュートリアルでは、*並列アルゴリズム*についてのみ説明します。 さらに進む前に、まずアルゴリズムとそのタイプについて説明します。
アルゴリズムとは何ですか？
- アルゴリズム*は、問題を解決するために従う一連の命令です。 アルゴリズムを設計する際には、アルゴリズムが実行されるコンピューターのアーキテクチャを検討する必要があります。 アーキテクチャごとに、2種類のコンピューターがあります-
- シーケンシャルコンピューター
- 並列コンピューター
コンピュータのアーキテクチャに応じて、2種類のアルゴリズムがあります-
- Sequential Algorithm -問題を解決するために、命令のいくつかの連続したステップが時系列で実行されるアルゴリズム。
- 並列アルゴリズム-問題はサブ問題に分割され、個々の出力を取得するために並行して実行されます。 後で、これらの個々の出力が組み合わされて、最終的な望ましい出力が得られます。
大きな問題をサブ問題に分割するのは簡単ではありません。 副問題には、データ間の依存関係がある場合があります。 したがって、問題を解決するには、プロセッサーが相互に通信する必要があります。
プロセッサが互いに通信するのに必要な時間は、実際の処理時間よりも長いことがわかっています。 したがって、並列アルゴリズムを設計する際には、効率的なアルゴリズムを得るために適切なCPU使用率を考慮する必要があります。
アルゴリズムを適切に設計するには、並列コンピューターの基本的な*計算モデル*の明確なアイデアが必要です。
計算のモデル
順次および並列コンピューターは、アルゴリズムと呼ばれる命令のセット（ストリーム）で動作します。 これらの一連の指示（アルゴリズム）は、各ステップで何をする必要があるかをコンピューターに指示します。
命令ストリームとデータストリームに応じて、コンピュータは4つのカテゴリに分類することができます-
- 単一命令ストリーム、単一データストリーム（SISD）コンピューター
- 単一命令ストリーム、複数データストリーム（SIMD）コンピューター
- 複数命令ストリーム、単一データストリーム（MISD）コンピューター
- 複数命令ストリーム、複数データストリーム（MIMD）コンピューター
SISDコンピューター
SISDコンピュータには、* 1つの制御ユニット、1つの処理ユニット*、* 1つのメモリユニット*が含まれています。
このタイプのコンピューターでは、プロセッサーは制御ユニットから命令の単一ストリームを受信し、メモリーユニットからのデータの単一ストリームで動作します。 計算中、各ステップで、プロセッサは制御ユニットから1つの命令を受け取り、メモリユニットから受け取った単一のデータを操作します。
SIMDコンピューター
SIMDコンピュータには、* 1つの制御ユニット、複数の処理ユニット*、*共有メモリまたは相互接続ネットワーク*が含まれています。
ここでは、1つの制御ユニットがすべての処理ユニットに命令を送信します。 計算中、各ステップで、すべてのプロセッサは制御ユニットから単一の命令セットを受け取り、メモリユニットからの異なるデータセットで動作します。
各処理ユニットには、データと命令の両方を保存する独自のローカルメモリユニットがあります。 SIMDコンピューターでは、プロセッサー間で通信する必要があります。 これは、*共有メモリ*または*相互接続ネットワーク*によって行われます。
一部のプロセッサが一連の命令を実行している間、残りのプロセッサは次の一連の命令を待ちます。 コントロールユニットからの命令により、どのプロセッサが*アクティブ*（命令を実行）または*非アクティブ*（次の命令を待つ）になるかが決定されます。
MISDコンピューター
名前が示すように、MISDコンピューターには*複数の制御ユニット、複数の処理ユニット*、* 1つの共通メモリユニット*が含まれています。
ここで、各プロセッサには独自の制御ユニットがあり、共通のメモリユニットを共有しています。 すべてのプロセッサは、独自の制御ユニットから個別に命令を取得し、それぞれの制御ユニットから受信した命令に従って、単一のデータストリームで動作します。 このプロセッサは同時に動作します。
MIMDコンピューター
MIMDコンピューターには、複数の制御ユニット、複数の処理ユニット、*共有メモリ*または*相互接続ネットワーク*があります。
ここでは、各プロセッサに独自の制御ユニット、ローカルメモリユニット、および算術論理ユニットがあります。 彼らは、それぞれの制御ユニットから異なる命令セットを受け取り、異なるデータセットで動作します。
Note
- 共通メモリを共有するMIMDコンピューターは「マルチプロセッサー」と呼ばれ、相互接続ネットワークを使用するMIMDコンピューターは「マルチコンピューター」と呼ばれます。
- プロセッサの物理的な距離に基づいて、マルチコンピューターには2つのタイプがあります-
- マルチコンピューター-すべてのプロセッサーが互いに非常に近い場合（例えば、同じ部屋に）。
- 分散システム-すべてのプロセッサが互いに離れている場合（例：異なる都市）
