並列化

並列化︵へいれつか、英: parallelization︶は、コンピュータにおいて、同時に複数の演算処理を実行すること︵並列計算︶によって処理のスループットを上げるプログラミング手法である。対義語は逐次化︵英: serialization︶。ハードウェアの資源を有効活用するための最適化手法のひとつである。

概要

コンピュータにおいて処理を実行する場合、もっとも単純な方法は、与えられたプログラムステップを最初から最後までひとつずつ順番に実行していくことである。これを逐次処理 (serial processing) と呼ぶ。一方、SIMD命令をサポートするプロセッサや、複数のプロセッサ︵マルチソケットプロセッサあるいはマルチコアプロセッサ︶を搭載するコンピュータでは、複数の異なるデータを同時に処理したり、複数の異なるステップを同時に実行したりすることもできる。これを並列処理 (parallel processing) と呼ぶ。逐次処理を並列処理にすることを並列化という。シングルコア性能の向上が頭打ちになるにつれ、並列化による高速化は重要性を増している手法である。

複数の異なるステップ︵タスク︶を並列実行できることをタスク並列性、複数の異なるデータに対して同じ処理を並列実行できることをデータ並列性という。

並列化の主な内容は、全体の問題をいくつかの独立したタスクあるいはデータストリームに分割し、タスクあるいはデータストリームを複数のプロセッサ (具体的にはCPUやGPUなどにおける各コア) に割り当て、処理を同時実行させ、最後に分割されたタスクを同調させたり、あるいはデータストリームを統合したりして最終結果を得ることである。ソフトウェアレベルでは並列化の実装単位にプロセスやスレッドが利用される。並列化は本質的に並列化可能な︵主にデータ間に相互依存性のない︶問題にのみ適用できる。問題の分割手法には領域分割︵データ分割︶、機能分割︵タスク分割︶があり、両方を組み合わせることもある。

並列化には主に2つのアプローチがある。


明示的な並列化または手動での並列化

プログラマが明示的にプログラムおよびデータの分割方法を指定する

暗黙的な並列化または自動並列化

処理系︵コンパイラなど︶が自動的に問題のタスクおよびデータを分割する


多くの要因・手法が並列化のパフォーマンスに影響を及ぼす。並列化により、プロセッサの数︵あるいはSIMD命令により同時処理できるデータの数︶に比例してプログラムの処理速度が倍速化されるが、実際にはプログラム中に占める並列化可能な領域の割合に左右されたり、並列アルゴリズムの内容やハードウェアのキャッシュ能力に依存したりする。アムダールの法則や偽共有も参照。

ロードバランシングは負荷の高いプロセッサから負荷の低いプロセッサへとタスクを移すことで、すべてのプロセッサをビジーに保とうとする。

単一CPUのシステムで正しく動作するプログラムでも並列環境ではそうではないこともある。これは同一のプログラムの複数のコピーが互いに干渉しあう︵例えば、同時に同じメモリ領域を読み書きする︶からである。そのため、並列環境では入念なプログラミング︵排他制御︶が必要となる。

もしコンピュータにプロセッサがひとつしかなく、なおかつSIMD命令をサポートしない場合は逐次処理しかできず、並列処理︵並列計算︶はできない。一方、並行処理︵並行計算︶は可能である場合もある。例えば汎用的なオペレーティングシステムではごく短時間で実行タスクを切り替えて複数のタスクを疑似的に同時実行することのできるマルチタスクシステムが採用されることが多い。並行処理はスループットの改善のためではなく、主にシステムの応答性の改善のために利用される。

自動並列化

自動並列化とは、並列化コンパイラを使用して、字面的にそのまま解釈すれば逐次的に計算を行うようなプログラムのソースコードを変換し、並列計算を行うようなオブジェクトコードを得る手法である。並列計算機の並列計算能力を活用するために行われる。自動並列化の目的はプログラマを退屈でエラーの起きやすい並列化作業から解放することである。技術的には非常に進歩したが、必要なプログラム解析の複雑さやコンパイル時には不明な要因︵例えば、入力データの範囲︶などのために、逐次的なプログラムの完全な自動並列化は未だ達成されていない。

自動並列化で主に焦点が当てられるプログラム制御構造はループである。なぜなら、一般的にプログラムの実行時間のほとんどは何らかのループの中で消費されるからである。自動並列化コンパイラはループを分解し、繰り返しが別々のプロセッサで並行に実行されるようにする。

並列プログラミングモデル

並列プログラミングモデルとは、並列なアルゴリズムを表現し、アプリケーションを動作環境である並列システムに適合させるためのソフトウェア群である。これらのソフトウェアは並列化ツールキットなどとも呼ばれる。並列プログラミングモデルが扱う領域には、アプリケーション、言語、コンパイラ、ライブラリ、通信システム、並列入出力などがある。これは明示的な並列化の手法であり、自動並列化の適用の難しさを避けている。並列プログラムの生産性を高めるため、並列アプリケーションの開発者は適切な︵単一または複数の︶並列プログラミングモデルを選んで使用する。

並列プログラミングモデルの実装方法にはいくつか種類がある。既存の逐次処理言語用のライブラリ、言語の拡張仕様、またはまったく新しい実行モデルなどである。それらはさらに2種類に大まかに分類される。メモリ共有型とメモリ分散型である。しかしながら、この2つの境界は曖昧なものとなっている。

並列プログラミングモデルの例

• OpenMP
• MPI
• PVM
• Linda
• ストリーム・プロセッシング (stream processing)
• 並行論理プログラミング (concurrent logic programming)
• Intel Threading Building Blocks
• X10

関連項目

• 制御依存
• 演算の独立性
• 並列アルゴリズム
• グローバルコンピューティング
• データフローコンピューティング
• グリッドコンピュータ
• スーパーコンピュータ
• スレッド (コンピュータ)
• VLIW
• スーパースカラー
• Lock-freeとWait-freeアルゴリズム
• イベンチュアル・コンシステンシー