近年、ソフトウェア業界では並列コンピューティングの対応に追われています。MPP では、90 年代半ばに各種メッセージパッシング API が開発され、それらをまとめたものが MPI という標準規格になりました。共有メモリー型マルチプロセッサー・コンピューターでも同様の動きがあり、次の 2 つの標準規格にまとめられました。

• pthreads: スレッドを明示的に制御
• OpenMP: 宣言子によるマルチスレッディング

そして、これらの標準規格に基づいたアプローチが定着する過程で、さまざまな並列プログラミング・モデル (データ並列言語 (HPF)、関数型言語 (SISAL)、並行論理プログラミング言語 (Parlog)、オブジェクト指向プログラミング (POOMA) など) が試みられました。各モデルとも、並列プログラミングを容易にし、エラーを減らすという目的は同じでした。

使用する並列言語が違っても、並列ソフトウェアの基本的な考え方は同じです。どのプログラムでも、一貫した 4 つのステップが含まれます。

1. 並行性 (コンカレンシー) の有無を特定する
2. 並行性の可能性があるコード領域を構成し直して、並行領域を明確にする
3. 並列プログラミング言語を使用して、プログラムを並列化し、並行性を引き出す
4. 作成したプログラムを並列実行し、チューニングを行う

このトピックは、多数の書籍で取り上げられています。ここで並列プログラミングに関するすべての問題に触れることはできないので、最も簡単な並列プログラミング言語の 1 つである OpenMP* とその主要ないくつかの構文について紹介し、実際にサンプルコードを使ってこの 4 つのステップを見ていきましょう。

OpenMP*

OpenMP* は並列プログラミングを非常に簡単に表現でき、共有メモリー型のコンピューターで動作します。つまり、明示的にデータを分割しなくてもタスクを使用できるのです。便利である一方、これにより、意図しないデータの共有を含むプログラムを作成してしまう可能性もあります。そうした場合、パート 3 で触れたデータ競合を引き起こすことがあります。

OpenMP* を使用するには、いくつかの基本的な概念を知っていれば十分です。OpenMP* 構文のほとんどは「プラグマ」というコンパイラーへのヒントとして表現されます。コンパイラーは認識できないプラグマを無視するので、OpenMP* に対応していないコンパイラーでもコンパイルし実行できます。つまり、1 つのソースコードを 2 つの異なる環境に使用できるのです。

OpenMP* プログラムは、シリアルプログラムをベースに作成します。まず、追加スレッドが必要なポイントに「parallel」プラグマを追加して、スレッドのチームを作成します。

#pragma omp parallel

そして、作成されたスレッドのチームがプラグマに続く文を実行します (プラグマに続く文は、波かっこで囲まれた複数の文によって定義された複合文である場合もあります)。デフォルトでは、parallel プラグマより前に宣言された変数は、すべてのスレッド間で共有されます。スレッドごとにこれらの変数のプライベート・コピーを作成する場合は private 節を使用します。

#pragma omp parallel private(list_of_variables)

parallel プラグマだけの場合、各スレッドは同じコードを実行します。「for」プラグマを使用することで、スレッド間でループの反復を分割できるようになります。

#pragma omp for

for プラグマと parallel プラグマは 1 つにまとめて簡潔に記述することができます。

#pragma omp parallel for

これにより、スレッドのチームが作成され、直後に続く for ループの反復がスレッド間で分割されます。OpenMP* の使用例に移る前に、OpenMP* の節をあと 3 つ紹介しましょう。1 つ目は、スレッドのチームがアクセス可能なデータを管理するためのものです。スレッドごとに一時変数のプライベート・コピーが必要になるのはよくあることです。そのためには、parallel プラグマや for プラグマに private 節を追加します。

#pragma omp for private(list_of_variables)

2 つ目は reduction 節で、これもよく使用されます。複数のスレッドが操作を実行し、それぞれの結果を 1 つの変数にまとめる場合、リダクションを行います。基本的には、各スレッドで計算された複数の値が 1 つのグローバル値にマージされます。

#pragma omp for reduction(+:sum)

これらの説明だけではイメージが掴みにくいかもしれませんが、いくつかの使用例を見るとはっきりしてくるでしょう。

使用例

ここでは、2 つの使用例について考えてみましょう。

1 つ目は π の値を推定する数値積分問題で、並列プログラミングでは古くから使用されています。この例は単純でありながら、並列プログラミングの主要な問題の多くを含んでおり、並列コンピューターで実行した場合、実際にスピードアップを確認できます。

2 つ目はやや複雑で、リンクリストの各要素のフィボナッチ数列を計算します。

どちらの使用例でも同じ要点をカバーしているので、両方読むことができない場合は、どちらか 1 つだけを読んでもかまいません。(注: この使用例で紹介している結果は、インテルのデュアルコア・プロセッサー 1.83 GHz と IA-32 対応アプリケーション用インテル® コンパイラー 11.0.074 を使用して測定した結果です。)

使用例 1: 単純な π プログラム

1 つ目は単純な数値積分問題です。この問題については、さまざまなところで詳しく説明されているので、ここでは要点だけを見ていきたいと思います。以下が、このプログラムのシリアルバージョンです。

for (i=1;i<= num_steps; i++){
    x = (i-0.5)*step;
    sum = sum + 4.0/(1.0+x*x);
}
pi = step * sum;

このプログラムは、一連の幅の狭い長方形の面積の総和を求め、各長方形の中点を結んだ曲線から円周率を推定します。この例では、結果が π と等しくなるように曲線と計算区間が選択されています。このプログラムを並列化するには、前述の 4 つのステップを行います。

1. 並行性 (コンカレンシー) の有無を特定する: 原則として、ループの反復は並行に実行できます。
2. 並行領域を明確にする: それぞれのスレッドに一時変数 x のプライベート・コピーを渡し、sum 変数へのリダクションを行うようにします。
3. 並行性を引き出す: OpenMP* のプラグマを 1 つ追加して、プログラムを並列化します。
   

   #pragma omp parallel for private(x) reduction(+:sum)

4. 並列で実行する: 完成したプログラムは次のようになります。
   

   #pragma omp parallel for private(x) reduction(+:sum)
   for (i=1;i<= num_steps; i++){
       x = (i-0.5)*step;
       sum = sum + 4.0/(1.0+x*x);
   }
   pi = step * sum;
   

ループ制御変数 i は、デフォルトで各スレッドに対してプライベートになります。OpenMP* プラグマはスレッドのチームを作成し (parallel 構文)、直後に続くループの反復を割り当てます (for 構文)。このとき、各スレッドに対して変数 x のプライベート・コピーを作成することで、複数のスレッドが変数 x への読み取り/書き込みを行ってもデータ競合が発生しないようにします。

reduction(+:sum) 節は、各スレッドに対して sum 変数のプライベート・コピーを作成し、操作の単位元 (加算の場合は 0) を割り当てます。各スレッドの処理結果がプライベート・コピーに格納され、ループが終了すると、それぞれのプライベート・コピーの値が 1 つのグローバル・コピーにマージされます。

このプログラムをデュアルコアのラップトップで実行したところ、次のような結果が得られました。

Serial code:     Pi = 3.141593 in 1.73  seconds
OpenMP, 1 thread Pi = 3.141593 in 1.73  seconds
OpenMP, 2 thread Pi = 3.141593 in 0.877 seconds

この結果では、1 スレッドの OpenMP* プログラムとオリジナルのシリアルプログラムの実行時間が同じですが、常にそうなるわけではありません。実際には、並列に実行するために追加した構文により、オーバーヘッドが増える傾向にあります (そのため、並列プログラマーがシリアルコードの実行時間を見せたがらないのは珍しいことではありません)。

使用例 2: リンクリストの並列処理

偏微分方程式の解を求めることに重点を置いた科学計算 (典型的な「グリッド」コード) 以外の問題では、データ構造とその制御構造がかなり複雑になります。配列や単純なループに代わり、リンクリストや while ループが使用されます。

次のサンプルコードについて考えてみましょう。

p = head;
while (p != NULL) {
    processwork(p);
    p = p->next;
}

ここで、関数 processwork() が実際にどのような処理を行っているかは関係ありません。重要なのは、この関数で CPU 時間が大量に消費され、並列オーバーヘッドに見合う十分な作業量があるかどうかです。この例では、processwork() を呼び出すたびに異なるフィボナッチ数列を計算します。

このプログラムでも、前述の 4 つのステップを行いましょう。

1. 並行性 (コンカレンシー) の有無を特定する: processwork(p) への各呼び出しは個別に実行可能で、この問題には並行性があるといえます。
2. 並行領域を明確にする: この問題では並行性を明確にすることは難しいでしょう。リンクリストでは、リスト中の各ノードはその前のノードに依存しているため、一見すると並行性がないように思われがちです。しかし、リンクリストをスキャンして、リスト中の各要素を配列に格納することで、配列の要素を並列に処理できるようになります。
   

   // リスト中の要素数をカウントする
    p = head;
    while (p != NULL) {
      	    p = p->next;
            count++;
    }
   <p> // リストから各要素を配列に複製する
    p = head;
    for(i=0; i<count; i++) {
          parr[i] = p;
          p = p->next;
       }
   

3. 並行性を引き出す: リスト中の要素を配列に格納したら、parallel for を使用してプログラムを並列化できます。
   

   #pragma omp parallel

4. 並列で実行する:

完成したプログラムは次のようになります。

p  = head;
while (p != NULL) {
	 p = p->next;
       count++;
 }
 p = head;
 for(i=0;i<count; i++) {
       parr[i] = p;
       p = p->next;
    }
 #pragma omp parallel for
      for(i=0; i<count; i++)
         processwork(parr[i]);
 }

実行時間は、オリジナルのシリアルプログラムが 26.0 秒、1 スレッドの OpenMP* バージョンが 26.4 秒でした。リンクリストの要素を配列に格納する処理が追加されていることを考えると、OpenMP* バージョンの方がオリジナルのシリアルプログラムより長くかかるのは当然といえるでしょう。2 スレッドでは、実行時間が 21.0 秒にまで減りました。

多少のスピードアップが見られますが、期待していたほどではないのは 何が原因でしょう?　 OpenMP* の for 構文は、ループの反復を最良のスケジュールでスレッドに分配しようとします。コンパイラーはベストを尽くしますが、データについては何も知りません。このサンプルコードでは、リストの要素によって、フィボナッチ配列の計算にかかる時間が大きく異なることが考えられます。そのため、作業を 2 分割し、前半の反復を 1 つ目のスレッドに、後半の反復を 2 つ目のスレッドに振り分けただけでは、負荷不均衡が発生するでしょう。

そこで、OpenMP* に別のスケジュールを使用するように指示します。ここでは、ラウンドロビン方式 (総当り) で反復をスレッドへ振り分けると良いでしょう。次のように、プラグマに schedule (static,1) 節を追加します。

#pragma omp parallel for schedule(static, 1)

この新しいスケジュールにより、2 スレッドの実行時間は 16.6 秒に減りました。

この例では並列化に伴い多くの変更が必要になりましたが、OpenMP* ではオリジナルのシリアルプログラムへの変更を最小限に抑えるべく取り組んでいます。最新バージョンの OpenMP 3.0 では、明示的な task 構文を追加することで、より簡単にこの問題を並列化できます。この方法では、タスクがキューに追加され、作業が完了するまで、スレッドのチームがタスクの処理にあたります。以下は、OpenMP* 3.0 のタスクを使用した場合のコードです。

#pragma omp parallel
{
   #pragma omp single
  {
      p=head;
      while (p) {
	     #pragma omp task firstprivate(p)
                  processwork(p);
            p = p->next;
      }
   }
}

このコードについて考えてみましょう。最初の single 構文は、囲まれた作業をチーム内の 1 つのスレッドだけが実行するよう指定しています。つまり、while ループを実行し、キューにタスクを追加できるのは 1 つのスレッドだけです。すべてのタスクをキューに追加し終わると、そのスレッドはチームのほかのスレッドとともにタスクを処理します。次に注目したいのは、task プラグマです。

#pragma omp task firstprivate(p)

この task プラグマは、直後に続く文 (processwork(p) 関数) をキューにタスクとして追加することを定義します。firstprivate(p) 節は、指定した変数とプラグマに到達した時点の値のコピーを作成し、タスク内で使用するよう指定しています。

この単純なコードは、オリジナルのプログラムの基本構造を維持しているため、明示的なタスクのキューという考え方に慣れれば、分かりやすいものになるでしょう。さて、どれ程度のスピードアップが達成できたのでしょうか?実行時間は 15.8 秒に減りました。つまり、このコードは分かりやすいだけでなく、ほかのコードよりもやや高速であるという結果になりました。

まとめ

このシリーズでは、4 つのパートにわたりさまざまなトピックをカバーしてきました。パート 1 では並列プログラミング問題の概要、パート 2 では並列ハードウェア、パート 3 では並列プログラマーが知っておくべき主要な問題について説明しました。そして、このパート 4 では並列プログラミングの基本的な概念について触れました。詳細は非常に複雑なこともありますが、大事なことは 1 つだけです。それは、並列ハードウェアで並行性を活用して、プログラムの実行時間を短縮することです。

このシリーズを読んだだけで、並列プログラミングのエキスパートになるのは難しいでしょう。しかし、少なくとも並列プログラミングの要点を理解し、「エキスパートのように」なることはできるでしょう。

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

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