プログラムを並列コンピューターで実行するのは、そのほうが高速に実行できるからです。そして、並列プログラミングを行うのは、実行時間を増やすことなくより多くのデータを処理できるからです。どちらの場合も、重要な点はパフォーマンスです。並列プログラミングとは、すなわちパフォーマンスにほかなりません。

その一方で、実行時間が短くても結果が不正確なプログラムでは意味がありません。並列コンピューティングについてエキスパートのように語るためには、並列プログラミング固有の問題を知っておく必要があります。

ここでは、パフォーマンスと正当性に関する専門用語について説明します。

並列コンピューターのパフォーマンス

コンピューターのパフォーマンスには、関連するキーワードが 2 つあります。1 つ目はタスクの「レイテンシー」で、これは 1 つのタスクを完了するのにかかる経過時間を表します。インタラクティブなコンピューティング・アプリケーションではレイテンシーが重要になります。例えば、コンピューター・ゲームでは、ジョイスティックを操作したら、瞬時に対応する動作が行われるよう求められます。つまり、レイテンシーは非常に短くなければなりません。

2 つ目は「スループット」です。タスク群全体のパフォーマンス、つまり一定時間内にどれだけのタスクを完了できるかを表します。個々のタスクには時間がかかるものもあるかもしれませんが、タスク群全体の実行時間が短くなれば問題ありません。典型的なスループット・コンピューティングに動画フレームのレンダリングがあります。この場合、1 つのフレームに少し長く時間がかかってもかまいませんが、妥当な時間内に次のシーンのすべてのフレームを表示しなければなりません。

スループットかレイテンシーかにかかわらず、どちらの場合も並列プログラミングのエキスパートとして並列処理のパフォーマンスを正確に説明できなければなりません。これには、「スピードアップ」という用語を使用します。スピードアップとは、プログラムの並列での実行時間と、同じアルゴリズムで最速なシーケンシャルコードでの実行時間との比率です。

S = t(sequential)/t(parallel)

完全に並列化されたプログラムでは、スピードアップがプロセシング要素数=コア数 (P) に対して線形的にスケーリングします。つまり、S は P と等しくなります。これを「完全に線形的なスピードアップ」と呼びます。完全に線形的なスピードアップでは、コア数を倍に増やすと、プログラムの実行時間が半分に減ります。しかしこのようなスピードアップが得られるのは極めてまれです。なぜならば、高度に並列化されたプログラムであっても、至るところでオーバーヘッドが発生し、パフォーマンスが制限されるからです。

ここで重要なのは、プログラムのシリアル領域とスピードアップへの影響について考察することです。この関係にはアムダールの法則が適用されます。まず、アムダールの法則について簡単に説明しましょう。プログラムの合計実行時間を T(s) とします。これは、並列に実行できる割合 (fp) とシリアルにしか実行できない割合 (fs) の 2 つに分けられます。シリアルの割合には、I/O オーバーヘッド、スタートアップ・コスト、並列ジョブからの結果を収集する処理に要する作業などの操作が含まれます。利用可能なプロセッサー数 (P) を増やすと、次のように並列領域だけがスピードアップします。

T(P) = (fs + fp/P)T(s)  = (fs + (1-fs)/P)T(s)

この式をスピードアップの定義に代入すると次のようになります。

S = T(s)/(fs+(1-f(s))/P)T(s) = 1/(f(s) + (1-f(s))/P)

P が最大の場合、次のスピードアップを達成できます。

S = 1/f(s)

このように、並列アルゴリズムを考える上で、アルゴリズムのシリアル領域がスピードアップに与える影響は非常に重大です。例えば、アルゴリズムの 80% しか並列化されていない場合、プロセッサー数に関係なく最大スピードアップは 5 です。そして、プロセッサー数が 2 で、アルゴリズムの 80% が並列化されている場合、アムダールの法則による最大スピードアップは 1.4 です。ハイパフォーマンスを達成するには、アルゴリズムに含まれるシリアルでしか実行できない作業を、できるだけ減らさなければなりません。

並列プログラミングの難しいところは、並列アルゴリズムのパフォーマンス問題に加えて、シリアルプログラムと同じ処理にも対応しなければならないことです。例えば、プロセシング要素 (コア) と使用するデータが近くになるように、メモリーアクセスにも注意を払う必要があります。これは、マルチプロセッサー・システム、特にプロセッサー数の多いものや、異なるメモリー領域へのアクセスコストがプロセッサーごとに違う NUMA システムではさらに重要になります。

並列プログラミング固有の問題

並列プログラミングにおいて、ハイパフォーマンスは何よりも大切なことですが、短時間で誤った結果が算出されるのでは困ります。マルチスレッド・プログラムで正当性を得るのは大変なことです。すべてのスレッドが 1 つのアドレス空間を共有しているという事実は、並列プログラミングを容易にする一方、予期しない方法でスレッドがデータを共有する可能性があるため、別の問題を引き起こします。

スレッドのスケジューリングの変更に伴いプログラムの結果が変わることを「データ競合」と呼びます。これは、プログラミング・エラーの中でも最も深刻なものです。なぜならば、プログラムにデータ競合が存在しないことを証明するのはほぼ不可能だからです。例えば、最初の 1,000 回は問題なく実行できても、1,001 回目のスレッドのスケジューリングでメモリー競合が発生し、プログラムが失敗することがあります。

マルチスレッド・プログラミングでデータ競合を排除するには、命令がどのような順序で実行されても、正しい結果が出力されるようにしなければなりません。つまり、複数のスレッドによって読み取り/書き込みが行われるオブジェクトを特定し、どのアクセス順序でも正しい結果が出力されるように、同期構造を使用して保護する必要があります。

マルチスレッディングの注意点

ここからは、やや専門的な内容になります。スキップしても問題ありませんが、よりエキスパートらしくなるためには、これらについても知っておいたほうが良いでしょう。次の 2 つの独立した結果 (A と B) を計算し、それらと別の値を使用して最終的な解を算出する単純なプログラムについて考えてみましょう。この例では、2 つのスレッドを使用するマルチスレッド・プログラムで計算を行います。

スレッド 1	スレッド 2
A = BigJob()	B = BigJob()
Res += A	Res += B

A と B の計算でどちらか一方に時間がかかる場合 (例えば A のほうが B よりも時間がかかる場合)、このプログラムは多分正しい結果を生成するでしょう。しかし、両方のスレッドが同時に Res の合計を行った場合、結果は予測できません。例えば、A = 1、B = 2、Res = 3 (A と B の計算を行う前の値) の場合、次のような結果が考えられます。

Res の最終値	操作の順番
6	A と B の実行時間が大きく異なる場合。
5	スレッド 1 が Res を読み取って合計処理を行っている途中、スレッド 2 が Res を読み取って合計処理を行い、スレッド 1 が完了した後にスレッド 2 が書き込みした場合。
4	スレッド 2 が Res を読み取って合計処理を行っている途中、スレッド 1 が Res を読み取って合計処理を行い、スレッド 2 が完了した後にスレッド 1 が書き込みした場合。

これらの値はすべて、マルチスレッド・プログラムで命令の順番を正当に組み合わせた結果ですが、正しいのは最初の値だけです。プログラマーは、命令がどのように組み合わせられても正しい解になるようにする必要があります。この例では、同期構造を使用して Res への書き込みを保護することで、この問題を解決できます。

すべてのマルチスレッド API には、各種同期構造が用意されています。この例では、OpenMP* の atomic という同期構造を使用します。atomic 構造は、一度に 1 つのスレッドだけが保護された操作を行い、終了するまでほかのスレッドはその操作を行えないようにします。次のように、プログラムを変更します。

スレッド 1	スレッド 2
A = BigJob()	B = BigJob()
#pragma omp atomic	#pragma omp atomic
Res += A	Res += B

この問題は小さなコード領域では容易に見つけられますが、実際のアプリケーションではメモリー競合が多数のファイルに散らばった数千ものソース行に埋もれている可能性があり、疑わしい箇所をすべて見つけるのは非常に困難です。同様に、非効率的な並列領域をすべて見つけることも難しいでしょう。

パフォーマンス問題と正当性の問題に対処するには、そのプログラムを熟知していなければなりません。これらの問題に取り組む最良の方法は、適切なツールを使用することです。インテルでは、システムレベルのプログラム動作を解析し、マルチスレッド・プログラムのメモリー競合を検出して、並列パフォーマンスを視覚化するツール群を提供しています。効率の良いマルチスレッド・プログラムを作成するには、これらのツールが不可欠です。

次のステップ

ここでは、並列プログラムのパフォーマンスと正当性の問題に関する重要な用語 (スピードアップ、アムダールの法則、データ競合) について説明しました。パート4 では、いくつかの並列プログラムを作成してみましょう。

パート1 パート2 パート3 パート4

インテル® ソフトウェア製品のパフォーマンス/最適化製品に関する詳細は、最適化に関する注意事項 (英語) を参照してください。