なぜ並列化? それは処理を高速化するためです。以前、MPI並列を紹介したところ、もっと簡単な並列はないの? と聞かれましたので、複数コアがあれば簡単にできる並列を紹介します。2core以上のCPUを持つマシンでお試しください。Linuxを対象にしていますが、それ以外のOSでは「チャレンジ」してみてください。

1. はじめに

対象になるプログラムを用意します。お手元に配列を使用したプログラムがあれば、それでお試しください。配列サイズとしては1000程度欲しいところです。無ければ、次のようなプログラムを用意しました。コピーしてお試しください。

#include <stdio.h>
#include <time.h>

int main()
{
  int n,m,i,j,k;
  double a[5000][600];
  double b[600][5000];
  double us,t0,t1,t2,sum;
      t0=clock();
      us = 10.0 ;
      n=5000 ;
      m=600 ;
     for (j =0;j<m;j++){
        for (i =0;i<n;i++){
            b[j][i] = (j+i+2)/10.0  ;
         }
      }
      for (k=0;k<200;k++) {
        for (j =0;j<m;j++){
          for (i =0;i<n;i++){
            a[i][j] = b[j][i] + us  ;
          }
        }
        us = us + 1.2 ;
      }
      sum=0.0 ;
     for (j =0;j<m;j++){
        for (i =0;i<n;i++){
            sum=sum+a[i][j] ;
         }
      }
      t1=clock();
      t2 = (t1 - t0) * 1.0e-6 ;
      printf(" TIME=%f data= %f\n",t2,sum);
}

このプログラムに物理的な意味はありません。単に配列に値を入れて集計しているだけのチョットわざとらしい練習用プログラムです。

2. 計測

これをベースにしてみましょう。ファイル名を仮にsample2.cとします。(*.cならなんでもよい)

[]$ gcc sample2.c
[]$ ./a.out
Segmentation fault
[]$

おやおや、何と無粋な。。制限は外しましょう。

[]$ ulimit -s unlimited
[]$ ./a.out
 TIME=3.898616 data= 1586700000.000000
[]$

最適化オプションを付けてみます。

[]$ gcc -O2 sample2.c
[]$ ./a.out
 TIME=3.840020 data= 1586700000.000000
[]$

最適化オプションはあまり効いていないみたいです。ちょっとアンロールをかけてみましょうか。

[]$ vi sample2a.c  (sample2.cに変更を加えて保存しています)
[]$ gcc sample2a.c
[]$ ./a.out
 TIME=1.300404 data= 1586700000.000000
[]$

効くようです。ここで、最適化を付加してみましょう。

[]$ gcc -O2 sample2a.c
[]$ ./a.out
 TIME=1.192950 data= 1586700000.000000
[]$

良い感じに効いているようです。今回はSMP並列が主題なので、高速化のためのチューニングは後でちょっと触れますが、機会があれば後日やりたいと思います。

3. 並列

では、いよいよ並列実行しましょう。

3.1 プログラムへ指示行の挿入

素のプログラムに並列化指示行を入れてみましょう。とりあえず、一番重い部分は次のループですので、OpenMPの並列化指示行を以下のように挿入します。

[]$ cp sample2.c  sample2b.c
[]$ vi sample2b.c

      for (k=0;k<200;k++) {
#pragma omp parallel for private(i,j)
        for (j =0;j<m;j++){
          for (i =0;i<n;i++){
            a[i][j] = b[j][i] + us  ;
          }
        }
        us = us + 1.2 ;
      }

ループは3箇所ありますが、ここが一番重い3重ループですから指定位置を入れ替えて試してみてください。また、オプションや指示の仕方はいろいろありますので、ご自分で調べたり試したりしてお使いください。
他のループでも指定可能ですが、粒度が小さいので効果は限定的です。でも、お試しください。総和ループでは reduction(+:sum) を付加します。こんな感じです。

      sum=0.0 ;
#pragma omp parallel for private(i,j)  reduction(+:sum) 
     for (j =0;j<m;j++){
        for (i =0;i<n;i++){
            sum+=a[i][j] ;
         }
      }

ここでは、入れる指示行は基本形のみにします。では、コンパイルしましょう。オプションに「-fopenmp」を付加します。

[]$ gcc -O2 -fopenmp sample2b.c

これでOKです。

3.2 実行

実行してみましょう。

[]$ ./a.out
 TIME=3.932937 data= 1586700000.000000
[]$

普通に動くと思います。続いて、いよいよ並列で動作させます。
まずは、おまじないから、

[]$ export OMP_NUM_THREADS=2
[]$ ./a.out
 TIME=3.945268 data= 1586700000.000000
[]$

んっ、遅くなった。。。?
おおっ、忘れていました。Cの場合スレッド時間を足してしまうんでした。時間計測コマンド time を使いましょう。「real」で表示される部分が実行時間です。では、続けて実行してみます。

[]$ export OMP_NUM_THREADS=1
[]$ time ./a.out
 TIME=3.826071 data= 1586700000.000000

real	0m3.836s
user	0m3.816s
sys	0m0.012s

[]$ export OMP_NUM_THREADS=2
[]$ time ./a.out
 TIME=3.908159 data= 1586700000.000000

real	0m1.960s
user	0m3.895s
sys	0m0.016s

[]$ export OMP_NUM_THREADS=4
[]$ time ./a.out
 TIME=5.014193 data= 1586700000.000000

real	0m1.284s
user	0m4.974s
sys	0m0.044s
[]$

どうでした。速くなりましたか。もっとコアがあるマシンでしたらコア数までトライしてください。今回使用したマシンは4coreなので、ちょっと早くなったくらいでしたが、core数があればばっちり行けると思います。配列を少し大きくしてお試しあれ。
もし、結果が変化してしまうようなことがあれば、それは、並列化できない部分に指示行を入れたことになります。その場合でも正しく並列化できる可能性はありますのでチャレンジしてみてください。並列化されない場合、指示行の記述を間違えている場合と、gccが古すぎてサポートしていない場合があります。バージョンを尋ねてみると普通は次の例以上の数字が出てくると思います。確認ください。

[]$ gcc --version
gcc (GCC) 4.9.3
Copyright (C) 2015 Free Software Foundation, Inc.

3.3 まとめ

大量処理の必要があり、ノード内にCPUの余裕がある場合はOpenMPによる並列(今回紹介)を検討してみてください。さらにマシン環境が許すならMPI(前回紹介)を検討してみてください。
データ量があまり多くない場合、アンロールをかけただけのほうが速い場合もあります。データ量に合わせて高速化を検討してみてください。

4.おまけ

4.1 アンロール

アンロールが気になる場合は以下を参照ください。これは、8段の例です。
ループ内の演算密度を大きくして一気に計算させます。最適段数は、演算によって違いますのでお試しください。注意点は配列数が段数で割れること。そうでない場合、きちんと端数処理をしないとSegmentation faultが出るか、結果が変化してしまいます。

      for (k=0;k<200;k++) {
        for (j =0;j<m;j+=8){
          for (i =0;i<n;i++){
            a[i][j] = b[j][i] + us  ;
            a[i][j+1] = b[j+1][i] + us  ;
            a[i][j+2] = b[j+2][i] + us  ;
            a[i][j+3] = b[j+3][i] + us  ;
            a[i][j+4] = b[j+4][i] + us  ;
            a[i][j+5] = b[j+5][i] + us  ;
            a[i][j+6] = b[j+6][i] + us  ;
            a[i][j+7] = b[j+7][i] + us  ;
          }
        }
        us = us + 1.2 ;
      }

最内側ループは、パイプライン処理をさせるように連続にしておき、外側のループを飛び処理させます。例は、わざと添え字のそろわない配列を使っていますが、揃えたほうが速くなりますし、キャッシュチューニングのブロック化も効果あるようです。お試しあれ。
並列のテーマなので、チューニング後も確認してみましょう。

[]$ gcc -fopenmp sample2a.c
[]$ export OMP_NUM_THREADS=2
[]$ time ./a.out
TIME=2.066413 data= 1586700000.000000

real	0m1.038s
user	0m2.053s
sys	0m0.016s
[]$ export OMP_NUM_THREADS=4
[]$ time ./a.out
 TIME=5.264482 data= 1586700000.000000

real	0m1.344s
user	0m5.206s
sys	0m0.062s
[]$

4並列では遅くなってしまいました。これは、処理の粒度が小さくなってしまい、並列化で増加した前後の手続き(forkとjoin)が並列化の効果を上回ってしまったためと考えられます。このあたりの限界値は、処理の内容、処理量、マシン性能によって違いますのでご自身の環境に合わせて確認してご使用ください。
今回は i5 4coreマシン + VirtualBox + vinelinux で実施しました。

以上