Loading article…
データ並列処理とは、並列コンピューティング環境において複数のプロセッサ間で並列処理を行うことです。これは、データを複数のノードに分散させ、各ノードがデータを並列に処理することに重点を置いています。配列や行列などの通常のデータ構造に適用でき、各要素を並列に処理します。これは、並列処理の別の形態であるタスク並列処理とは対照的です。
n個の要素を持つ配列に対するデータ並列ジョブは、すべてのプロセッサに均等に分割できます。与えられた配列のすべての要素を合計したいと仮定し、1 つの加算演算にかかる時間を Ta 時間単位とします。逐次実行の場合、プロセスが配列のすべての要素を合計するのにかかる時間はn × Ta 時間単位になります。一方、このジョブを 4 つのプロセッサでデータ並列ジョブとして実行すると、かかる時間は ( n /4)×Ta + マージオーバーヘッド時間単位に短縮されます。並列実行は、逐次実行に比べて 4 倍の高速化をもたらします。データ参照の局所性は、データ並列プログラミングモデルのパフォーマンスを評価する上で重要な役割を果たします。データの局所性は、プログラムによって実行されるメモリアクセスとキャッシュのサイズに依存します。
データ並列性の概念の活用は、1960年代にソロモンマシンの開発とともに始まりました。[ 1 ]ソロモンマシンは、ベクトルプロセッサとも呼ばれ、大きなデータ配列（連続する時間ステップで複数のデータを操作する）で数学演算の実行を高速化するために開発されました。データ操作の並行性も、単一の命令を使用して複数のデータを同時に操作することによって活用されました。これらのプロセッサは「アレイプロセッサ」と呼ばれました。[ 2 ] 1980年代には、このプログラミングスタイルを説明するために用語が導入されました[ 3 ]。これは、 C*などのデータ並列言語でコネクションマシンをプログラミングするために広く使用されました。今日、データ並列性はグラフィックス処理ユニット（GPU）で最もよく例示されており、単一の命令を使用して空間と時間の両方の複数のデータを操作する技術の両方を使用しています。
ほとんどのデータ並列ハードウェアは、並列レベルの数が固定されており、多くの場合1つしかサポートしていません。これは、並列処理内で再帰的に複数の並列処理を起動することができず、プログラマがネストされたハードウェア並列性を利用できないことを意味します。プログラミング言語NESLは、フラット並列マシン上でネストされたデータ並列プログラミングモデルを実装する初期の試みであり、特にネストされたデータ並列性をフラットなデータ並列性に変換するフラット化変換を導入しました。この取り組みは、 Data Parallel HaskellやFutharkなどの他の言語によって引き継がれましたが、現在のデータ並列プログラミング言語では、任意のネストされたデータ並列性は広く利用できません。
マルチプロセッサシステムにおいて、単一の命令セット（SIMD）を実行する場合、各プロセッサが異なる分散データに対して同じタスクを実行することでデータ並列性が実現されます。状況によっては、単一の実行スレッドがすべてのデータに対する操作を制御します。また、異なるスレッドが操作を制御しつつ、同じコードを実行する場合もあります。
例えば、例で説明したように、行列の乗算と加算を順次行う場合を考えてみましょう。
以下は、2つの行列の乗算と加算を順次実行し、結果を行列Cに格納する擬似コードです。乗算の擬似コードは、2つの行列AとBの内積を計算し、その結果を出力行列Cに格納します。
以下のプログラムを順次実行した場合、結果を計算するのにかかる時間は（両行列の行長と列長をnと仮定）それぞれ乗算と加算に対応します。
// 行列の乗算for ( int i = 0 ; i < A . rowLength (); i ++ ) { for ( int k = 0 ; k < B . columnLength (); k ++ ) { int sum = 0 ; for ( int j = 0 ; j < A . columnLength (); j ++ ) { sum += A [ i ][ j ] * B [ j ][ k ] ; } C [ i ][ k ] = sum ; } }// 配列の加算for ( int i = 0 ; i < c . size (); i ++ ) { c [ i ] = a [ i ] + b [ i ] ; }前述のコードでは、演算がループに依存しないため、データ並列性を利用して高速に実行できます。行列乗算コードの並列化は、OpenMPを使用することで実現されます。OpenMP ディレクティブ「omp parallel for」は、コンパイラに for ループ内のコードを並列に実行するように指示します。乗算の場合、行列 A と B をそれぞれ行と列に沿ってブロックに分割できます。これにより、行列 C の各要素を個別に計算できるため、タスクを並列化できます。たとえば、A[mxn] ドット B[nxk]は、の代わりにm×k個のプロセッサを使用して並列実行した場合。
//並列での行列乗算#pragma omp parallel for schedule ( dynamic , 1 ) collapse ( 2 ) for ( int i = 0 ; i < A.rowLength (); i ++ ) { for ( int k = 0 ; k < B.columnLength ( ); k ++ ) { int sum = 0 ; for ( int j = 0 ; j < A.columnLength ( ) ; j ++ ) { sum += A [ i ] [ j ] * B [ j ] [ k ] ; } C [ i ] [ k ] = sum ; } }例からわかるように、行列のサイズが大きくなるにつれて、多くのプロセッサが必要になります。実行時間を短く保つことが最優先事項ですが、行列のサイズが大きくなると、システムの複雑さやそれに伴うコストなど、他の制約に直面します。したがって、システム内のプロセッサ数を制限しても、同じ原理を適用してデータをより大きなチャンクに分割し、2 つの行列の積を計算することができます。[ 4 ]
データ並列実装における配列の加算について、2つの中央処理装置（CPU）AとBを備えた比較的小規模なシステムを想定してみましょう。CPU Aは配列の上半分からすべての要素を加算し、CPU Bは配列の下半分からすべての要素を加算します。2つのプロセッサが並列に動作するため、配列の加算処理にかかる時間は、1つのCPUのみを使用して同じ操作を直列に実行する場合の半分になります。
以下の擬似コードで表されたプログラムは、foo配列のすべての要素に対して任意の操作 を適用するもので、dデータ並列性を示しています。[ nb 1 ]
CPU = "a"の場合 lower_limit := 1 upper_limit := round(d.length / 2) そうでなければ、 CPU = "b"の場合、 lower_limit := round(d.length / 2) + 1 upper_limit := d.length for i from lower_limit to upper_limit by 1 do foo(d[i])
2プロセッサシステム上で実行されるSPMDシステムでは、両方のCPUがコードを実行します。
データ並列性は、処理（タスク並列性）とは対照的に、データの分散（並列）特性を重視します。実際のプログラムのほとんどは、タスク並列性とデータ並列性の中間のどこかに位置します。
逐次プログラムを並列化するプロセスは、4つの個別のステップに分解できます。[ 5 ]
データ並列処理とタスク並列処理は、同じアプリケーションに対してこれらを組み合わせることで同時に実装できます。これは混合データ並列処理と呼ばれます。混合並列処理には、高度なスケジューリングアルゴリズムとソフトウェアサポートが必要です。通信速度が遅く、プロセッサ数が多い場合に、これは最適な並列処理です。[ 7 ]
データ並列処理とタスク並列処理の混合処理には多くの応用例があります。特に以下の用途で利用されています。
現在、さまざまなデータ並列プログラミング環境が利用可能であり、その中でも最も広く使用されているのは以下のとおりです。
データ並列処理は、物理学、化学、生物学、材料科学から信号処理まで、さまざまな分野で応用されています。科学分野では、分子動力学[ 9 ] 、ゲノムデータの配列解析[ 10 ]、その他の物理現象などのモデルをシミュレートするためにデータ並列処理が用いられています。信号処理におけるデータ並列処理の推進力としては、ビデオエンコーディング、画像およびグラフィックス処理、無線通信[ 11 ]などが挙げられます。
データ集約型コンピューティングは、通常テラバイトまたはペタバイトの大容量データ（一般的にビッグデータと呼ばれる）を処理するためにデータ並列アプローチを使用する並列コンピューティングアプリケーションのクラスです。実行時間の大部分を計算要件に費やすコンピューティングアプリケーションは計算集約型と見なされ、大量のデータを必要とし、処理時間の大部分をデータの入出力と操作に費やすアプリケーションはデータ集約型と見なされます。 [ 12 ]
d.length1 と評価され、round0 に向かって丸められる場合 [これは単なる例であり、どのような種類の丸めが使用されるかについての要件はありません]) がlower_limitより大きくなることupper_limitが、その場合、ループは直ちに終了する (つまり、反復回数は 0 回になる) と想定されます。