OpenCVのparallel_for_バックエンドの性能評価とOpenMPバックエンドon Windowsの性能の出し方

# はじめに

[OpenCV Advent Calendar 2023](https://qiita.com/advent-calendar/2023/opencv) 18日目の記事として投稿します．他の記事は目次からご覧ください．

今日の話は，ほとんどの人が使わないOpenCVの並列化モジュールを更に，ほとんどの人が使わないバックエンド切り替え機能を使って性能評価するドマイナー記事です．

`cv::parallel_for_`は，ParallelLoopBody抽象クラスを継承したクラスをRangeで分割して並列実行する関数で，OpenCVの多くの関数で使われています．
```cpp
cv::parallel_for_ (const Range &range, const ParallelLoopBody &body, double nstripes=-1.)
```
古いですが，この記事（[OpenCVの並列化クラスParallelLoopBodyとparallel_for_](https://qiita.com/fukushima1981/items/02d6c034ca0375496b65)）で説明しています．


このparallel_for_並列化のバックエンドは複数の候補から選ぶことができ，Visual Studio on Windowsの場合下記から選択できます．
* Concurrency (**デフォルト**)
* TBB
* OpenMP
* [HPX: High Performance ParallelX](https://hpx-docs.stellar-group.org/latest/html/index.html)

デフォルト以外は，マルチプラットフォーム対応です．なお，Unix-likeなOSならpthreadバックエンドが，MacOSならGCDバックエンドがデフォルト設定になります．詳細は，[公式ドキュメント](https://docs.opencv.org/4.8.0/db/d05/tutorial_config_reference.html#tutorial_config_reference_func_core)を参照してください．

TBBに関しては，`OpenCV can download and build TBB library from GitHub, this functionality can be enabled with the BUILD_TBB option.`とある通り，cmake時にコンパイルしたら入ってくれるはずです．またOpenMPに対応していないコンパイラを使うこともレアでしょうから，cmakeでOpenMPをonにしたらOpenMPバックエンドも使えます．

なお，[HPX (Wikipedia)](https://en.wikipedia.org/wiki/HPX)は，[HPX Backend for OpenCV (Google Summer of Code (GSoC) 2018)](https://summerofcode.withgoogle.com/archive/2018/projects/4621772498403328)で拡張された機能です（OpenCV本体のライセンスとは違ってBoost Software Licenseですが問題になる人はほぼいないでしょう．）．私は，今日までテストしたことがなかったです（し，OpenCVのparallelバックエンド切り替える人は相当レアな人でしょう）．

このバックエンドですが，[OpenCVのプラグイン機能](https://qiita.com/dandelion1124/items/ffe223d7474f7be7a8ef)によって切り替えられます．詳細はリンク先の@dandelion1124さんの記事を参照してください．
parallel_for_の実装を見てみるとhppヘッダに実装すべて入っており，適切に呼ばれるバックエンドが切り替えらられることがわかり，コンパイル時にどれが呼び出せるかすべて決定します．

本記事では，各バックエンドを切り替えて，性能評価をします．
また，Visual Studio上でのOpenMPの本気（いつの間にかOpenMP2.0縛りを消せるようになってる）を見てみます．
なお，HPXのwindowsコンパイルチャレンジに失敗したので，HPXバックエンドは評価から外しました．

# Concurrencyバックエンド
Visual Studioの場合，[コンカレンシー](https://learn.microsoft.com/ja-jp/cpp/parallel/concrt/concurrency-runtime?view=msvc-170)がデフォルトバックエンドに選ばれています．何もしなかった場合はこれになっています．
私は，OpenCVバックエンド以外でこれを使ったことがないため詳細はドキュメントに任せます．

## TBBバックエンド
OpenCVの並列化フレームワークは，最初はTBBのparallel_forを使っていました．
並列化コマンドである`parallel_for_`がこのような名前になっているのはその名残かと思います．
tbbはOpenCVをcmakeするときにチェックを入れれば簡単に入るはずです．

まず，ソースコードに下記をインクルードし，設定関数を呼んでください．
そうしたらparallel_for_がtbbの並列化に代わります．
```cpp
#include <opencv2/core/parallel/backend/parallel_for.tbb.hpp>
int main()
{
cv::parallel::setParallelForBackend(std::make_shared<cv::parallel::tbb::ParallelForBackend>(), true);
...
}
```

# OpenMPバックエンド
OpenMPバックエンドを有効化する方法を示します．
まず，ソースコードに下記をインクルードし，設定関数を呼んでください．
そうしたらparallel_for_がOpenMPの並列化に代わります．
```cpp
#include <opencv2/core/parallel/backend/parallel_for.openmp.hpp>
```
その際，OpenMPを有効にしないと，
`opencv\include\opencv2\core\parallel\backend\parallel_for.openmp.hpp`の11行目で下記に引っかかってコンパイルできません．
```
#error "This file must be compiled with enabled OpenMP"
```

OpenMPを有効にするには，
* プロパティのC/C++->言語->OpenMPのサポートを，はい（/openmp）
* 上記を空欄にして，プロパティのC/C++->コマンドラインの追加オプション（D）に`/openmp`を追記
することで対応できます．

VisualStudioのOpenMPは，長年OpenMP2.0の使用制限に留まっているようですが，実は最新の機能も使えます．
`/openmp`に代わって，`/openmp:experimental` か`/openmp:llvm`を指定することで拡張できます（[マニュアル](https://learn.microsoft.com/ja-jp/cpp/build/reference/openmp-enable-openmp-2-0-support?view=msvc-170)）

4.0までの一部の機能を使うexperimentalと，LLVMコンパイラがサポートするOpenMP5.0までの機能（の一部）を指定が出来ます．experimentalのほうはVisual StudioネイティブのOpenMPのlibを使い，LLVMの方は外部から提供されたlibを使います（インストールの必要はないはず）． 
2023/12月現在では，experimentalよりもLLVMの方が速いコードが書けますが，初期化に時間がかかるようです． そのため，実験では空ループが多めに必要です．（LLVMのほうがスループットは出るがレイテンシが大きくなる傾向があります）

また，LLVMバックエンドは，スレッド番号を物理プロセシングコアにバインドする機能（OpenMP4.0以降にサポート）があります．
通常は，OpenMPの各スレッドは仮想実行ユニットを想定しており，論理コアに1対1で対応していません．
仮想で考えるメリットとして，別のプログラムにより一部のコアが完全に死んでしまっている場合やスレッド数を無限に増やすといったことも対応できますが，論理コアに1-1で割り当てたほうが最大性能を発揮することが可能になります．

設定するためには，プロパティー>デバッグー>環境にOMP_PLACES=threadsと書くか，環境変数に設定するか，実行するコマンドプロンプトの環境変数にsetしてください．

# HPXバックエンド
Windows上でのコンパイルに失敗したのでメモだけ．（全部コンパイルはできたのですが，OpenCVにくっつけるcmakeでこけました．）

必要なもの
* Boost
* hwloc
* TCMalloc
BoostのASIOをヘビーに使っており，ASIOはboostのコンパイルが必要ですが，`-DHPX_WITH_FETCH_ASIO=ON`のcmakeフラグでうまくやってくれます．
hwlocは，スレッドのマッピングに必要です．なお，TBBでも使ています．
TCMallocは無くてもいいですが，入れると速くなるらしいです．（無しでテストしてません．）

# 実験
1024x1024の画像に対してボックスフィルタ（重みが平坦な畳み込み）を21x21のカーネルで畳み込んだ計算時間を示します．
OpenCVのバージョンは4.8，Visual Studio2022でコンパイルしました．
なお，入力は，半径rでcopymakeBorderで拡張済みのものを入れています．
使用した計算機は下記2つで
* Intel Core i7 7700K (4コア8スレッド)
* Intel Core i9 13900KS（8+16コア，32スレッド）
13900KSは，Pコア，Eコアを搭載しています．

比較は，下記9種類で行います．
`cv::parallel_for_`を使ってバックエンドを切り替えてた6種類に加えて，naiveは，OpenMPのparallel_for_を使わずにOpenMPのparallel for schedule(dynamic)で並列化しました．

* Concurrency
* TBB
* OpenMP2.0 (/openmp) 
* OpenMP (experimental) (/openmp:experimental)
* OpenMP (llvm) (/openmp:llvm)
* OpenMP (llvm:bind) (/openmp:llvm + OMP_PLACES=threads)
* naive OpenMP (experimental)
* naive OpenMP (llvm)
* naive OpenMP (llvm:bind)

使用したコードはこちらです．
```cpp
class ParallelFilter : public cv::ParallelLoopBody
{
private:
	const Mat border;
	Mat& dest;
	const int r;
public:
	ParallelFilter(const Mat& border, Mat& dest_, const int r)
		: border(border), dest(dest_), r(r)
	{
		;
	}

	void operator()(const Range& range) const override
	{
		const int D = 2 * r + 1;
		const int div = D * D;
		for (int j = range.start; j < range.end; j++)
		{
			uchar* d = dest.ptr<uchar>(j);
			for (int i = 0; i < dest.cols; i++)
			{
				int sum = 0;
				for (int l = 0; l < D; l++)
				{
					const uchar* s = border.ptr<uchar>(j + l);
					for (int k = 0; k < D; k++)
					{
						sum += s[i + k];
					}
				}
				d[i] = sum / div;
			}
		}
	}
};

void parallelFilter(const Mat& border, Mat& dest, const int r)
{
	const int D = 2 * r + 1;
	const int div = D * D;
#pragma omp parallel for schedule(dynamic)
	for (int j = 0; j < dest.rows; j++)
	{
		uchar* d = dest.ptr<uchar>(j);
		for (int i = 0; i < dest.cols; i++)
		{
			int sum = 0;
			for (int l = 0; l < D; l++)
			{
				const uchar* s = border.ptr<uchar>(j + l);
				for (int k = 0; k < D; k++)
				{
					sum += s[i + k];
				}
			}
			d[i] = sum / div;
		}
	}
}

int main()
{
    Mat src = imread("1024x1024.png", 0);
    Mat dst = src.clone();
    const int r = 10;
    Mat border;
    copyMakeBorder(src, border, r, r, r, r, BORDER_DEFAULT);
    ...
    cv::parallel_for_(Range{ 0, (int)src.rows }, ParallelFilter{ border, dst, r }, -1);
    ...
    parallelFilter(border, dst, r);
}
```




結果です．
**7700K**

|backend                    |time [ms]|
|:-------------------------:|:---:|
|Concurrency                |18.23|
|TBB                        |17.95|
|OpenMP2.0                  |17.99|
|OpenMP(experimental)       |17.95|
|OpenMP(llvm)               |17.91|
|OpenMP(llvm:bind)          |17.89|
|native OpenMP2.0           |17.99|
|native OpenMP(experimental)|17.95|
|native OpenMP(llvm)        |17.67|
|native OpenMP(llvm:bind)   |17.65|

**1300KS**

|backend                    |time [ms]|
|:-------------------------:|:---:|
|Concurrency                | 3.99|
|TBB                        | 3.70|
|OpenMP2.0                  | 3.67|
|OpenMP(experimental)       | 3.67|
|OpenMP(llvm)               | 3.68|
|OpenMP(llvm:bind)          | 3.66|
|native OpenMP2.0           | 3.63|
|native OpenMP(experimental)| 3.63|
|native OpenMP(llvm)        | 3.59|
|native OpenMP(llvm:bind)   | 3.57|

さすがに，ネイティブのOpenMPで書いたの者が速くなりましたがかなり差が小さいです．
cv::parallel_for_を使った場合は，OpenMPバックエンドでllvmをコアバインドしたものがちょっとだけよかったです．

13900KSのPコアEコアがある場合のスレッドの負荷分散を見てみると，下記のようになりLLVMバックエンドでコアバインドした場合，負荷分散がきれいにいっているのが分かります．
![図1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/67908/372892ce-df57-1049-f5db-74419e90b852.png)


# まとめ
OpenCVの`cv::parallel_for_`について詳細に調べてみました．
現状は，Windows上だと現状OpenMPバックエンドをllvmを使ってコアバインドするのが最速なようです．
ただし，この方法最初の初期化が重たいため，oneTBBとくらべてどちらがいいか一概にいうのは難しいです．

明日は@nnn112358さんの予定で，
「OpenCVでThinkPad内蔵カメラを使おうとしてハマった件」です