データ並列性

データ並列性（英: data parallelism）は、複数のプロセッサを用いて演算を行う並列コンピューティングの形態の一つである。データ並列性は、異なる並列計算ノードにデータを分配することに焦点を置いている。並列性の別の形態であるタスク並列性と対照をなす。ループレベル並列性 (loop-level parallelism) とも。

詳細

並列計算が可能な環境、例えばマルチソケットあるいはマルチコアによるマルチプロセッサのシステムにおいて、データ並列性は、各プロセッサが分配された各データ領域（データ中の別々の部分）に対して同じタスクを処理することによって得られる。

ある状況では、一つの実行スレッドがすべてのデータの演算を制御し、またある状況では、複数のスレッドが演算を制御するが、すべて同じコードを実行している。

たとえば、CPU A と B を持つ2プロセッサシステム上にて、あるデータ D に対してコードを実行する場合、CPU A に D の前半部分を処理させ、同時に CPU B に D の残り後半部分を処理させることで、実行時間を削減することができる。

より具体的な例として、二つの行列の加算を考える。データ並列性を実現するためには、CPU A は行列の前半のすべての要素を加算し、CPU B は行列の後半のすべての要素を加算する。二つのプロセッサが並列に動作するため、行列の加算は（理想的な場合）単一の CPU で同じ処理を実行する場合の半分の時間で完了する。

データ並列性は、データの処理（タスク並列性）ではなくデータの分散した（並列化された）性質に焦点を置く。実際のプログラムのほとんどはタスク並列性とデータ並列性の間のどこかに落ち着く。

ソフトウェアレベルでは並列化の実装単位にプロセスやスレッドが利用される。通常、タスクを実行するCPUをアプリケーションソフトウェアレベルで明示的に指定することはほとんどなく、プロセスまたはスレッドといった抽象化された実行単位を割り当てるだけにとどめて、実際の計算ノードへのプロセス／スレッド割り当てはオペレーティングシステムやフレームワークが担当する。また、プロセッサの命令レベルでのデータ並列化の概念および機構として、SIMD^[1]およびSIMT（英語版）がある。

データ量が十分に多く、かつデータごとの処理内容が十分に長い場合は、通例シングルコアCPUで処理を逐次実行するよりもマルチコアCPUで並列実行したほうが高速になるが、データ量が少なかったり、データごとの処理内容が極端に短かったり、あるいはキャッシュの偽共有（英語版）が発生してしまったりする場合は、かえって並列化のためのデータ分割処理やスレッドの起動および待ち合わせといった準備にかかるオーバーヘッドなどのほうがかさんでしまい、結果として逐次実行した場合よりも低速になるということもありえる。

例

下記の擬似コードでデータ並列性を示す。データは下記に示すようなif文で割り当てることができる。

program:
...
if CPU="a" then
    lower_limit := 1
    upper_limit := 50
else if CPU="b" then
    lower_limit := 51
    upper_limit := 100
end if
do i := lower_limit, upper_limit
    Task on d(i)
end do
...
end program

このプログラムの目標は、(たとえば)サイズ 100 のデータの配列 "d" を処理することである。上記のようなコードを記述し、2プロセッサシステム上で動作させると、ランタイムではそれを下記のように実行する。

• 並列演算環境では、両方の CPU が "d" にアクセスしなければならない。
• 各 CPU が互いに独立な lower_limit と upper_limit のコピーを作成する機構があることを仮定する。
• "if" 節が CPU ごとの処理を変化させる。CPU "a" では、"if" 節で真となり、CPU "b" では、"else if" 節で真となる。結果として、それぞれ独自の lower_limit と upper_limit を持つ。
• ここで、いずれの CPU も "d(i)のタスク" を実行するが、各 CPU が異なる "limits" を持っているため、"d" の異なる部分を同時に演算することができ、プロセッサ間にタスクをうまく配分することができる。

CPU "a" で実行されるコード:

program:
...
lower_limit := 1
upper_limit := 50
do i := lower_limit, upper_limit
    Task on d(i)
end do
...
end program

CPU "b" で実行されるコード:

program:
...
lower_limit := 51
upper_limit := 100
do i := lower_limit, upper_limit
    Task on d(i)
end do
...
end program

この概念は、任意の数のプロセッサに対して一般化できる。

脚注

参考文献

• Hillis, W. Daniel and Steele, Guy L., Data Parallel Algorithms Communications of the ACM December 1986
• Blelloch, Guy E, Vector Models for Data-Parallel Computing MIT Press 1990. ISBN 0-262-02313-X

関連項目

• タスク並列性
• ストリーム・プロセッシング