第5回　タスク並列とデータ並列の違い

マルチスレッドプログラムの実際

　プログラムの並列化を行う前に、対象となる問題をよく知ることが重要です。

　その問題を従来どおりのプログラミングで実装した場合に、処理が遅く要求を満たせないことを試算あるいは実測し、高速化が必要であることを確認します。

　さて、並列プログラムを設計する場合に、どこからどのように手をつけていたらいいでしょうか。

　ソフトウェアの設計の方法には、さまざまな方法論があり、それぞれのプログラマにとってやり易いやり方があります。

　しかし、それぞれが好きにやればいいというのではこの連載の意味がなくなってしまうので、ここでは並列プログラムを設計する上での1つの指針について示します。

分割と依存関係

　どこが並列実行できるかについて考える場合、大きく2つの視点で考えられます。

1. どこが分割可能か
2. それらに依存関係はあるか

　まず、対象となる問題の並列化を行うためには、何らかの形で複数の部分に分割する必要があります。そして、その分割した部分や分割できない部分には、往々にして依存関係が存在します。

　依存関係があると並列化できませんので、どこにどのような依存関係があるのか、その依存関係をなくすことはできないかについて考えます。

　さらに詳しく分割方法を分類すると、タスク分割（task decomposition）とデータ分割（data decomposition）に分かれます。

　一般にプログラムは複数の処理から成り立っていますが、それぞれの処理で分割するのがタスク分割です。それとは別に、プログラムは複数のデータを持っていますが、それぞれのデータで分割するのがデータ分割です。

　次に、タスク分割やデータ分割やそれ以外も含めた依存性解析（dependency analysis）をします。依存性解析では次のような視点で考えてます。

1. 関連するタスクはどれか
2. それらの実行に順序関係があるか
3. タスクはどのデータを読み書きするか

　まず、あるタスクの出力が別のタスクの入力になる場合や、データ分割で分割されたデータを扱っていて同時実行が必要な場合など、関連するタスクをグループ化（group tasks）します。

　次に、グループ化されたタスクが並列で、かつ、正しく動作するように、タスクの実行順序（order tasks）を決めます。

　最後に、どのデータが複数のタスクから読み書きされ、排他制御や同期が適切に行われレースコンディションがないよう、データを共有化（data sharing）します。

並列化のためのアルゴリズム

　分割と依存関係について問題の整理を行った後、それを並列実行するための具体的なアルゴリズムを考えて行きますが、これには大きく2つあります。

• タスクを並列化する
• データを並列化する

　各視点について色々な状況やアルゴリズムが考えられますが、それぞれの基本的なアルゴリズムをここでは次のように呼ぶこととします。

• タスク並列
• データ並列

　タスク並列とは、タスク分割と依存関係の解析結果として各タスク間に依存関係のないものを集め、それを並列化するアルゴリズムです。

　高速化のためにタスク分割の必要条件として重要なのは、独立したタスクが十分にあることです。極端な場合、タスクが1つしかないと並列実行を行うことができません。大きなタスクは、より小さい複数のタスクに分割できないか考えてみましょう。

　また、タスク分割したプログラムを実行する環境が持つ並列化可能な数を下回る場合にも性能を十分に発揮できません。例えば、4個のコアを持つプロセッサで2つのタスクをタスク並列で実行しても、速度は4倍ではなく2倍にしかなりません。

　データ並列とは、処理対象となるデータがサブデータへ分割可能で、サブデータへの処理を行うと全体として元のデータへの処理と同じになる場合、各サブデータへの処理を並列化するアルゴリズムです。

　高速化のためにデータ並列を行う上で重要なのは、タスク並列の場合と同様に独立したサブデータが十分にあることです。

1/3

Index
タスク並列とデータ並列の違い
	Page1 マルチスレッドプログラムの実際 分割と依存関係 並列化のためのアルゴリズム
	Page2 スレッドによる並列化
	Page3 データ並列で実装してみる 処理の流れを比べてみよう

Think Parallelで行こう！