parallel_for を調べてみよう #C++

parallel_for

OpenCV_3.0.0ではparallel_forを使った並列動作の記述がある。
これを学んで、自分の書く関数にも応用したいと思う。(注1)

前置き
Intel Threading Building Blocks
には
parallel_forクラス　ループ間で依存性がない単純なループの並列処理
があって、IntelのCPUでは、Windows,Linux,MacOSで利用可能とのことだ。

OpenCVは、IntelのCPUに限らず、ARMのCPUでも動作しているので、OpenCVの中ではTBBが使えるときと使えないときで、処理を切り分けられるようにしている（はず）。

OpenCV_2.4.11ではtbb::parallel_for自体の記述は次のものが見つかった。

sources\modules\core\include\opencv2\core\internal.hpp(221): tbb::parallel_for(range, body);
sources\modules\core\src\parallel.cpp(246): tbb::parallel_for(tbb::blocked_range(stripeRange.start, stripeRange.end), pbody);

internal.hpp

略
#ifdef HAVE_TBB
　　略
　　　TBBがあるときの処理として、次のような処理などをしている。
    template<typename Body> static inline
    void parallel_for( const BlockedRange& range, const Body& body )
    {
        tbb::parallel_for(range, body);
    }
　　略
#else
　　略
    template<typename Body> static inline
    void parallel_for( const BlockedRange& range, const Body& body )
    {
        body(range);
    }
　　略　　　
#endif
略

OpenCV ではparallel_forそのものではなくてparallel_for_の記述がある。
parallel_for_()は次のようにして、TBBがあるとき、それ以外の高速化の枠組みが利用できるときのコードが書かれている。

parallel.cpp

略
/* ================================   parallel_for_  ================================ */

void cv::parallel_for_(const cv::Range& range, const cv::ParallelLoopBody& body, double nstripes)
{
#ifdef CV_PARALLEL_FRAMEWORK

    if(numThreads != 0)
    {
        ProxyLoopBody pbody(body, range, nstripes);
        cv::Range stripeRange = pbody.stripeRange();

#if defined HAVE_TBB

        tbb::parallel_for(tbb::blocked_range<int>(stripeRange.start, stripeRange.end), pbody);

#elif defined HAVE_CSTRIPES

        parallel(MAX(0, numThreads))
        {
            int offset = stripeRange.start;
            int len = stripeRange.end - offset;
            Range r(offset + CPX_RANGE_START(len), offset + CPX_RANGE_END(len));
            pbody(r);
            barrier();
        }

#elif defined HAVE_OPENMP

        #pragma omp parallel for schedule(dynamic)
        for (int i = stripeRange.start; i < stripeRange.end; ++i)
            pbody(Range(i, i + 1));

#elif defined HAVE_GCD
略
}
略

以下のファイルがparallel_for あるいは parallel_for_　をソースコード中に含むcppファイルです。

> grep -l parallel_for find . -name '*.cpp' -print
./sources/apps/traincascade/boost.cpp
./sources/modules/calib3d/src/stereobm.cpp
./sources/modules/core/src/convert.cpp
./sources/modules/core/src/dxt.cpp
./sources/modules/core/src/kmeans.cpp
./sources/modules/core/src/parallel.cpp
./sources/modules/core/src/stat.cpp
./sources/modules/core/test/test_umat.cpp
./sources/modules/cuda/src/calib3d.cpp
./sources/modules/features2d/src/kaze/AKAZEFeatures.cpp
./sources/modules/features2d/src/kaze/KAZEFeatures.cpp
./sources/modules/features2d/src/kaze/nldiffusion_functions.cpp
./sources/modules/imgproc/src/blend.cpp
./sources/modules/imgproc/src/clahe.cpp
./sources/modules/imgproc/src/color.cpp
./sources/modules/imgproc/src/demosaicing.cpp
./sources/modules/imgproc/src/distransform.cpp
./sources/modules/imgproc/src/histogram.cpp
./sources/modules/imgproc/src/imgwarp.cpp
./sources/modules/imgproc/src/morph.cpp
./sources/modules/imgproc/src/smooth.cpp
./sources/modules/imgproc/src/thresh.cpp
./sources/modules/ml/src/ann_mlp.cpp
./sources/modules/ml/src/gbt.cpp
./sources/modules/ml/src/knearest.cpp
./sources/modules/ml/src/nbayes.cpp
./sources/modules/ml/src/svm.cpp
./sources/modules/objdetect/src/cascadedetect.cpp
./sources/modules/objdetect/src/haar.cpp
./sources/modules/objdetect/src/hog.cpp
./sources/modules/photo/src/denoising.cpp
./sources/modules/stitching/src/matchers.cpp
./sources/modules/superres/src/btv_l1.cpp
./sources/modules/video/src/bgfg_gaussmix2.cpp
./sources/modules/video/src/bgfg_KNN.cpp
./sources/modules/video/src/lkpyramid.cpp
./sources/modules/video/src/tvl1flow.cpp
./sources/modules/videoio/test/test_ffmpeg.cpp

物体検出の関係のモジュールをさらに見てみよう。
./sources/modules/objdetect/src/cascadedetect.cpp: parallel_for_(Range(0, nstripes), invoker);
./sources/modules/objdetect/src/haar.cpp: cv::parallel_for_(cv::Range(0, stripCount),
./sources/modules/objdetect/src/haar.cpp: cv::parallel_for_(cv::Range(startY, endY),
./sources/modules/objdetect/src/hog.cpp: parallel_for_(range, invoker);
./sources/modules/objdetect/src/hog.cpp: parallel_for_(Range(0, (int)locations.size()),

物体検出関係のモジュールでは、元画像をそれぞれの縮小倍率で縮小して、それぞれの倍率での検出結果を、元画像のスケールで合わせて、検出枠をグルーピングして、検出結果を返すという共通の処理を行っている。各スレッドで得られた結果を統合するための枠組みは、スレッドで安全に受け渡しをできるデータ構造を使っているので、スレッドを考慮しないときのデータ構造とは違っているはずである。
　先にRaspberry PI B+でのHOG検出器での検出速度は、PCでの検出速度に比べてクロック速度以上に遅いということを述べた。detectMultiScale()はRaspberryPiではなぜ遅いか
Raspberry Pi 2ではクォッドコアの部分でどうなっているだろう。

・CMake を使ってOpenCVをビルドするときの条件をチェックすること、
　　　CMakeでの設定画面を見ること、VisualStudioでの該当のモジュールのソースコードがどの#ifdefが有効になっているのかを見ることでチェックできる。
・利用しているDLLがどのような条件でビルドされたものかをチェックすること、
　　　あなたのdllはマルチコアを活かせるdllですか？
・（IntelのCPUの場合）Intelのコンパイラでコンパイルすること
　　　自動並列化でマルチコアの性能を引き出す並列処理に強い開発ツール
「インテルコンパイラー」
　　　私はまだ利用していない。職場に1ライセンスあれば、DLLを作るときに重宝しそうだ。

・利用しているプログラムでプロファイルをとること
などを考慮して、自分のプログラムに利用していきたい。

以下のリンク先を読んで勉強しなくては

インテルTBBから学ぶループの並列化
 C/C++で並列コンピューティング（並列ライブラリ編
 インテルTBBライブラリを用いた並列処理の実装
 TBB　parallel_forの超基本的な使い方

[1] parallel_for を利用するコードを書くよりも、OpenCVの標準のライブラリを使いこなすことに専念しようと思っています。２重ループのfor文は、かなりの頻度で、OpenCVの標準のライブラリを使って書くことができるものです。その使い方の中で、Releaseモードのソースコードがどれだけ効率よく動作しているかを確認することからはじめましょう。同じソースコードでもVisual　StudioでReleaseモードでコンパイルしたものとLinuxでG++でコンパイルしたものでは、実行速度が数倍違うことがあります。ますは、そのような部分での高速化を考え、parallel_for は無理に使う必要がないのかもしれません。