このブログでも前に扱ったOpenCVという画像処理のライブラリがあります。OpenCVには色々な画像処理のアルゴリズムが実装されていますが、実際に使って見ると、自分で実装したときよりもかなり早いなぁということがあります。
「なぜ、速いのだろうか？」と思い、公開されているソースコードから勉強しようと思いたち、探ってみました。
高速化の鍵は並列化にある?
画像処理はピクセル単位で処理するので、元々並列化に向いている処理だと思います。
各ピクセルの値の計算は他のピクセルの処理後の値を必要としないので、各ピクセルは独立して処理が可能です。
独立して処理するのであれば、それが並列して処理されようが、飛び飛びのランダムに処理されようが結果には影響しません。
アルゴリズムによっては独立した処理ができないものもありますが、それでも、どこかしらに独立した処理が可能なブロックが存在することが多いです。
並列化することができれば、CPUのコアに分散させて同時に処理できるので、順番に処理するよりも高速に処理することが可能になります。
OpenCVの並列化の手法は？
OpenCVは複数の並列化手法に対応しています。OpenCV 4.3.0では次のような方法に対応しています。
- TBB (Thread Bulding Blocks)
- HPX
- OpenMP
- GCD
- WINRT
- Concurrency
- Pthread
Appleプラットフォームの場合の選択肢は、TBB, HPX, OpenMP, GCDです。
OpenMPはIntel C++ CompilerなどのOpenMP対応のコンパイラを使ったり、llvm project の libomp を利用します。
デフォルトはGCDです。
GCD (libDispatch) を使った並列化の方法
GCDはOSの標準機能なので、特別な準備は必要なく使えます。GCDを使った並列処理を実行している部分のコードを探してみると、次のところだと思います。
// modules/core/src/parallel.cpp
dispatch_queue_t concurrent_queue = dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0);
dispatch_apply_f(stripeRange.end - stripeRange.start, concurrent_queue, &pbody, block_function);
考察
GCDを使った並列化の方法は標準機能なので、使うための敷居が低いと思います。それでいて使った場合の効果は大きいので、自分の開発するプログラムでも上手く利用したい手法だと思います。
ネストの深い、長い関数を書いてしまうと上手く組み込むことができません。コツは次のようなところだと思います。
- ネストの深い長い関数を作らない
- 既に長い関数はリファクタリングし、機能単位で分割する
- ループはループする処理とループ本体を分けて、ループする処理は関数化する
これらはGCDを使った並列化以外にも有効です。
