並列処理によるプログラム高速化

　こんにちは。ディマージシェアの技術担当です。以前の記事（https://qiita.com/ob_nullpo/items/0d6f8f5886fdec331f20 ）でスキャンした書類画像を水平にするプログラムを作りました。作成したプログラムを用いれば、大抵の印刷物の画像は水平にすることができます。しかし、高解像度の画像では処理に時間がかかります。印刷を想定したスキャンでは600dpi～1200dpiで設定されることが多いです。今回は、プログラムの一部を並列化することで処理時間の短縮を図ります。

並列処理

　現代のCPUはマルチコアで構成されているものがほとんどです。理由は単純で、シングルコアで性能を伸ばすよりも、コア数を増やすことで性能を伸ばす方が電力効率が良いためです。プログラムを作成する際、明示的に複数のコアを使用するように記述することで、処理性能を向上させることができる場合があります。このように処理を並列に動かすことを並列処理と呼びます。

GPGPU

　計算機の多くはGPU（Graphics Processing Unit）と呼ばれる、画面に映像を出力するハードウェアを搭載しています。GPUは画面の全ての画素に表示する色を算出する処理を行います。その処理の性質上、GPUは小規模なプロセッサの集合体として実装されます。最新のモデルでは1万個以上のプロセッサを持っているものもあります。このGPUを画像出力以外に、汎用的な計算に応用する技術がGPGPUと呼ばれています。GPUとの親和性の高い処理の場合、CPUのみで処理を行う場合の10倍以上の性能が得られることがあります。

CPUスレッド並列処理

　CPUスレッドを効率よく使うためにはOSの知識が必要不可欠です。CPUスレッド並列で実装する際、厳密にパフォーマンスチューニングしたい場合はスレッド処理を手書きします。しかし、スレッド処理を自前で実装する場合はデバッグの困難性に直面することが多いです。また、並列処理にしたからと言って必ずしも処理が速くなるわけではありません。そのため、並列化したい処理がどの程度、並列処理と親和性があるかどうかを確かめる必要があります。そのようなとき、OpenMPのようなAPIを利用します。OpenMPでは、for文の前に1行、「このfor文を並列処理にしてください」と宣言するだけで並列処理の実装ができます。

　以前作成した、画像の傾きを求める関数の一番外側のfor文を並列処理にしてみます。

 #pragma  omp parallel for schedule(dynamic, 1)
   for (x = 0; x <= split; x++) {
       float c, s;
       int32_t i;
       float t = t1 + (t2 - t1) * x / split;
       c = cos(t);
       s = sin(t);
       float const_y = -((float)out_w * 0.5) * s - ((float)out_h * 0.5 * c) + ((float)src_h * 0.5);
       float const_x = -((float)out_w * 0.5) * c + ((float)out_h * 0.5 * s) + ((float)src_w * 0.5);
       float all_sum = 0;
       float avg;
       int32_t nz_s = 0, nz_e = out_h;
       for (i = 0; i < out_h; i++) {
           float dsi = s * i, dci = c * i;
           int32_t j;
           horizontal_sum[x][i] = 0;
           for (j = 0; j < out_w; j++) {
               float dsj = s * j, dcj = c * j;
               int32_t sy = dsj + dci + const_y;
               int32_t sx = dcj - dsi + const_x;
               if (sx >= 0 && sx < src_w && sy >= 0 && sy < src_h) {
                   int32_t d_y_pad = src_w * sy;
                   horizontal_sum[x][i] += (255 - data[d_y_pad + sx]);
               }
           }
       }
       for (i = 0; i < out_h; i++) {
           all_sum += horizontal_sum[x][i];
       }
       for (i = 0; i < out_h; i++) {
           if (horizontal_sum[x][i]) {
               nz_s = i;
               break;
           }
       }
       for (i = out_h - 1; i >= 0; i--) {
           if (horizontal_sum[x][i]) {
               nz_e = i;
               break;
           }
       }
       avg = all_sum / (float)(nz_e - nz_s);
       float score = 0;
       for (i = nz_s; i <= nz_e; i++) {
           score += (avg - horizontal_sum[x][i]) * (avg - horizontal_sum[x][i]);
       }
       score /= (float)(nz_e - nz_s);
       score_arr[x] = score;
   }

　入力する画像は1200dpiでスキャンした画像です。並列化前後の実行時間を計測してみます。使用するCPUはAMD Ryzen 9 3950Xです。

1 core 1 threadでの実行時間

time = 375.211783 sec

16 cores 32 threadsでの実行時間

time = 22.088056 sec

処理を並列化したことで、およそ17倍の性能になりました。

SIMD

　CPUでは、スレッドでの並列処理以外にも、演算命令レベルでの並列処理が使えることが多いです。SIMD命令と呼ばれる処理です。例えばIntel CPUのAVX2という命令セットを用いることで、最大であと8倍程度の高速化が見込めます。しかし、SIMD命令を用いたプログラミングは非常に複雑なため、今回は割愛します。

GPGPUを試してみる

　nVidia製のGPUを搭載している計算機では、CUDAと呼ばれる、C言語を拡張したコードでGPU用のコードを記述することができます。

　nVidia GeForce RTX 2070 SUPERで実行してみます。ソースコードは本記事の末尾に付録として載せます。

time = 1.732972 sec

　CPU 1coreの216倍、CPU 32 threadsの12.7倍の性能になりました。CPUでスレッド並列+SIMDでチューニングしても、GPUの方が速そうです。

並列処理を試す勘どころ

　一言で並列処理と言っても、CPUスレッド、SIMD、GPGPU、など様々な手段が存在します。また、並列処理によって処理時間が短くなるかどうかはおおよその推測はできますが、実測値を見るまでは油断できません。また、コーディングが難しくなる世界ほど実効性能の予測が難しい傾向があります。

　私の個人的な感覚ですと、

（1）OpenMPを試す

（2）GPGPUを試す

（3）SIMDを試すかどうか決める

　のような順位が妥当かと思います。OpenMPは1行書くだけで実測値が得られるのでコストも安く、得られる性能も良いことが多いです。次に、OpenMPが良く効くような処理では、GPGPUも効く可能性が高いです（もちろん処理の内容次第ですが）。GPGPUのコーディングは少し難易度が上がりますが、SIMDを丁寧に書くほど難しくありません。GPGPUを試してみて、CPUスレッド並列の8倍（SIMDを用いた場合の論理限界）を超える性能が得られれば検証は終わりにします。8倍未満の性能だった場合、SIMDを用いることでGPGPUの実効性能を超える可能性があるのでSIMDを試します。

まとめ

　計算機リソース的に重い処理でも並列処理の技術を応用することで実用レベルの性能を得られることがあります。現代のCPUはメニーコア化の傾向が強く、シングルスレッドでの処理性能向上は既に限界を迎えています。CPU以外にもGPGPUという技術もあります。並列処理はコーディングが複雑になりますが、現代の計算機を効率よく使うためには必要不可欠な知識です。実践は難しいかもしれませんが、知識だけはアップデートしておきましょう。

付録

　ソースコードへのリンク(https://github.com/HirokiHayakawa/inclination_detection)

当社に興味を持たれた方はHPもご覧ください。