Loading article…
データ並列処理は、並列コンピューティング環境における複数のプロセッサ間の並列化です。これは、データを並列に操作する異なるノードにデータを分散することに重点を置いています。各要素を並列に処理することで、配列や行列などの通常のデータ構造に適用できます。これは、別の形式の並列処理として タスク並列処理とは対照的です。
n要素の配列のデータ並列ジョブは、すべてのプロセッサ間で均等に分割できます。特定の配列のすべての要素を合計すると仮定し、1 回の追加操作にかかる時間は Ta 時間単位です。順次実行の場合、プロセスにかかる時間は、配列のすべての要素を合計するため、 n ×Ta 時間単位になります。一方、このジョブを 4 つのプロセッサでデータ並列ジョブとして実行すると、かかる時間は ( n /4)×Ta + マージ オーバーヘッド時間単位に短縮されます。並列実行により、順次実行よりも 4 倍高速になります。注目すべき重要な点の 1 つは、データ参照の局所性が、データ並列プログラミング モデルのパフォーマンスを評価する上で重要な役割を果たすことです。データの局所性は、プログラムによって実行されるメモリ アクセスとキャッシュのサイズによって異なります。
歴史
データ並列性の概念の活用は、1960年代にソロモンマシンの開発から始まりました。[1]ソロモンマシンはベクトルプロセッサとも呼ばれ、大規模なデータ配列を処理する（連続した時間ステップで複数のデータを操作する）ことで数学演算のパフォーマンスを高速化するために開発されました。データ操作の並行性も、単一の命令を使用して複数のデータを同時に操作することによって活用されました。これらのプロセッサは「アレイプロセッサ」と呼ばれていました。[2] 1980年代に、この用語が導入されました[3]このプログラミングスタイルは、 C*などのデータ並列言語でコネクションマシンをプログラムするために広く使用されました。今日、データ並列性は、単一の命令を使用して空間と時間の両方で複数のデータを操作する手法を使用するグラフィックス処理装置（GPU）で最もよく例証されています。
ほとんどのデータ並列ハードウェアは、固定数の並列レベルのみをサポートしており、多くの場合は 1 つだけです。つまり、並列操作内では、より多くの並列操作を再帰的に起動することはできず、プログラマはネストされたハードウェア並列性を利用できません。プログラミング言語NESL は、フラットな並列マシン上にネストされたデータ並列プログラミング モデルを実装する初期の取り組みであり、特に、ネストされたデータ並列性をフラットなデータ並列性に変換するフラット化変換を導入しました。この作業は、Data Parallel Haskell やFutharkなどの他の言語によって継続されましたが、任意のネストされたデータ並列性は、現在のデータ並列プログラミング言語では広く利用できません。
説明
単一の命令セット ( SIMD ) を実行するマルチプロセッサ システムでは、各プロセッサが異なる分散データに対して同じタスクを実行することで、データの並列処理が実現されます。状況によっては、単一の実行スレッドがすべてのデータに対する操作を制御します。また、異なるスレッドが操作を制御しますが、同じコードを実行します。
たとえば、例で説明したように 、行列の乗算と加算を順番に実行することを検討します。
例
以下は、 2 つの行列の乗算と加算を行う連続的な疑似コードです。結果は行列Cに格納されます。乗算の疑似コードは、2 つの行列A、Bのドット積を計算し、その結果を出力行列 C に格納します。
次のプログラムを順番に実行した場合、結果の計算にかかる時間は、乗算と加算でそれぞれ (両方の行列の行の長さと列の長さが n であると仮定)とになります。
// 行列の乗算
for ( i = 0 ; i < row_length_A ; i ++ ) { for ( k = 0 ; k < column_length_B ; k ++ ) { sum = 0 ; for ( j = 0 ; j < column_length_A ; j ++ ) { sum += A [ i ][ j ] * B [ j ][ k ]; } C [ i ][ k ] = sum ; } }
// 配列の追加
for ( i = 0 ; i < n ; i ++ ) { c [ i ] = a [ i ] + b [ i ]; }
演算はループに依存しないため、前述のコードでデータ並列処理を利用してコードをより高速に実行できます。行列乗算コードの並列化は、OpenMP を使用して実現されます。OpenMP ディレクティブ「omp parallel for」は、for ループ内のコードを並列に実行するようにコンパイラに指示します。乗算では、行列 A と B をそれぞれ行と列に沿ってブロックに分割できます。これにより、行列 C のすべての要素を個別に計算できるため、タスクが並列化されます。たとえば、A[mxn] dot B [nxk] は、m*kプロセッサを使用して並列に実行すると、ではなく で終了できます。
// 並列行列乗算
#pragma omp parallel for schedule(dynamic,1) collapse(2)
for ( i = 0 ; i < row_length_A ; i ++ ){ for ( k = 0 ; k < column_length_B ; k ++ ){ sum = 0 ; for ( j = 0 ; j < column_length_A ; 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"の場合
下限:= 1
上限:=round(d.length / 2)
そうでない場合、 CPU = "b"の場合
下限:=round(d.length / 2) + 1
上限:= d.長さ
iをlower_limit から upper_limit まで 1 ずつ増やす
foo(d[i])
2 プロセッサ システムで実行されるSPMDシステムでは、両方の CPU がコードを実行します。
データ並列性は、処理 (タスク並列性) ではなく、データの分散 (並列性) の性質を重視します。実際のプログラムのほとんどは、タスク並列性とデータ並列性の間のどこかに位置します。
並列化へのステップ
逐次プログラムを並列化するプロセスは、4つの個別のステップに分けることができます。[5]
データ並列性とタスク並列性
データ並列性とモデル並列性
[6]
混合データとタスクの並列処理
データとタスクの並列処理は、同じアプリケーションで組み合わせることで同時に実装できます。これは、混合データとタスクの並列処理と呼ばれます。混合並列処理には、高度なスケジューリング アルゴリズムとソフトウェア サポートが必要です。これは、通信が遅く、プロセッサの数が多い場合に最適な並列処理です。[7]
混合データとタスクの並列処理には多くの用途があります。特に、次のアプリケーションで使用されます。
- 混合データとタスクの並列処理は、地球規模の気候モデリングに応用されています。地球の大気と海洋を表すデータのグリッドを作成することで、大規模なデータの並列計算が実行され、タスクの並列処理は物理プロセスの機能とモデルのシミュレーションに使用されます。
- タイミングベースの回路シミュレーションでは、データは異なるサブ回路に分割され、タスクのオーケストレーションによって並列処理が実現されます。
データ並列プログラミング環境
現在、さまざまなデータ並列プログラミング環境が利用可能ですが、その中で最も広く使用されているものは次のとおりです。
- メッセージ パッシング インターフェース: 並列コンピュータ用のクロスプラットフォーム メッセージ パッシング プログラミング インターフェースです。ライブラリ関数のセマンティクスを定義し、ユーザーが C、C++、Fortran で移植可能なメッセージ パッシング プログラムを作成できるようにします。
- Open Multi Processing [8] (Open MP): マルチプロセッサシステムの複数のプラットフォームで共有メモリプログラミングモデルをサポートするアプリケーションプログラミングインターフェイス (API) です。バージョン 4.5 以降、OpenMP は一般的な CPU 以外のデバイスもターゲットにできるようになりました。FPGA、DSP、GPU などをプログラムできます。OpenACC のように GPU に限定されません。
- CUDAとOpenACC : CUDA と OpenACC は、ソフトウェア エンジニアが GPU の計算ユニットを汎用処理に利用できるように設計された並列コンピューティング API プラットフォームです。
- Threading Building BlocksとRaftLib : どちらも、異種リソースにわたる C/C++ 環境での混合データ/タスク並列処理を可能にするオープン ソース プログラミング環境です。
アプリケーション
データ並列処理は、物理学、化学、生物学、材料科学から信号処理まで、さまざまな分野で応用されています。科学では、分子動力学[9] 、ゲノムデータの配列分析[10]、その他の物理現象などのモデルをシミュレートするためにデータ並列処理が求められます。データ並列処理のための信号処理の原動力としては、ビデオエンコーディング、画像およびグラフィックス処理、無線通信[11]などが挙げられます。
データ集約型コンピューティング
参照
注記
- ^ 一部の入力データ（たとえば、
d.lengthが 1 に評価され、roundゼロに向かって丸められる場合 [これは単なる例であり、どのような丸めタイプが使用されるかについての要件はありません]）はlower_limitより大きくなりますがupper_limit、その場合、ループは直ちに終了する（つまり、反復が 0 回発生する）ものと想定されます。
参考文献
- ^ 「ソロモンコンピュータ」。
- ^ 「SIMD/Vector/GPU」(PDF) . 2016年9月7日閲覧。
- ^ Hillis, W. DanielおよびSteele, Guy L.、データ並列アルゴリズムCommunications of the ACM 1986 年 12 月
- ^ Barney, Blaise. 「並列コンピューティング入門」. computing.llnl.gov . 2013-06-10 にオリジナルからアーカイブ。2016-09-07に取得。
- ^ ヤン・ソリヒン (2016).並列アーキテクチャの基礎。フロリダ州ボカラトン：CRC Press。ISBN 978-1-4822-1118-4。
- ^ 「GPU でディープラーニングを並列化する方法 パート 2/2: モデルの並列化」Tim Dettmers 2014 年 11 月 9 日2016 年 9 月 13 日閲覧。
- ^ 「Netlib」（PDF） .
- ^ "OpenMP.org". openmp.org . 2016年9月5日時点のオリジナルよりアーカイブ。2016年9月7日閲覧。
- ^ Boyer, L. L; Pawley, G. S (1988-10-01). 「超並列コンピュータを用いた、対力と相互作用する粒子クラスターの分子動力学」。Journal of Computational Physics . 78 (2): 405–423. Bibcode :1988JCoPh..78..405B. doi :10.1016/0021-9991(88)90057-5.
- ^ Yap, TK; Frieder, O.; Martino, RL (1998). 「生物学的配列分析における並列計算」. IEEE Transactions on Parallel and Distributed Systems . 9 (3): 283–294. CiteSeerX 10.1.1.30.2819 . doi :10.1109/71.674320.
- ^ Singh, H.; Lee, Ming-Hau; Lu, Guangming; Kurdahi, FJ; Bagherzadeh, N.; Filho, EM Chaves (2000-06-01). 「MorphoSys: データ並列および計算集約型アプリケーション向けの統合再構成可能システム」. IEEE Transactions on Computers . 49 (5): 465–481. doi :10.1109/12.859540. ISSN 0018-9340.
- ^ クラウド コンピューティング ハンドブック、「クラウド コンピューティング向けのデータ集約型テクノロジ」、AM Middleton 著。クラウド コンピューティング ハンドブック。Springer、2010 年。
- Hillis, W. DanielおよびSteele, Guy L.、データ並列アルゴリズムCommunications of the ACM 1986 年 12 月
- Blelloch, Guy E,データ並列コンピューティングのベクトルモデルMIT Press 1990. ISBN 0-262-02313-X