データ並列性

出典: フリー百科事典『ウィキペディア（Wikipedia）』

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

[編集] 詳細

一つの SIMD 命令セットを実行するマルチプロセッサのシステムにおいて、データ並列性は、各プロセッサが同じタスクを分配されたデータの別の部分を処理することによって得られる。

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

たとえば、ここで、2 プロセッサシステム (CPU A と B)上でコードを実行する場合、並列計算環境で、あるデータ D 上の CPU A に、D のある部分を実行させ、CPU B に残りの部分を同時に実行させて、実行時間を削減することができる。データは下記に示すような If文で割り当てることができる。

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

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

[編集] 例

下記の擬似コードでデータ並列性を示す：

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

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

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

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

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

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

program:
...
low_limit=51
upper_limit=100
do i = low_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