並列プログラミング手法について

並列プログラミング手法について質問です。
具体的に、100dot　X　100dotのイメージデータ2つのを重ね合わせる処理を実現したいです。
単純に考えると前面に表示するAイメージと背面に表示するBイメージを以下のように
比較すると、重ね合わせができると思います。

Aイメージ Aimg[100][100];
Bイメージ Bimg[100][100];
重ね合わせた結果 Cimg[100][100];

for (y=0; y<100; y++) { //y座標
for (x=0; x<100; x++) { //x座標
if (Aimg[y][x] != 透過) {
Cimg[y][x] = Aimg[y][x];
}
else {
Cimg[y][x] = Bimg[y][x];
}
}
}

これをマルチコア、マルチスレッド、その他の技術を使い、より高速に実現する方法はあるでしょうか？
CPUの数、GPUの有無など、条件付でも何でもいいので、より高速にする手段をご存知の方、ご教授いただけるでしょうか？

私の調べた限り、並列処理を行うのに、
・OpenCL
・ARM neon
・ループカウンタはデクリメントにする。
というのが、有効みたいでした。
そもそも画像処理を行うには、
・OpenGL
・OpenVG
が有効みたいです。

ループカウンタをデクリメントにするのは多少効果がありましたが、他は
やり方が良くなかったのか、あまり効果が見られませんでした。
ちなみに、32ms定期で処理が必要です。
恐らく、一回の実行に最低限、数ms必要になる、などの条件がボトルネックになっていると思いますが、その辺の改善策、その他の手法をご存知の方はご教授ください。

また、パフォーマンスのブラッシュアップ手法も募集しております。

tiitoi

2018/10/07 18:51

「アルファブレンディング」を行いたいのでしょうか？OpenCV の関数を使えば、最適化されてるので高速に計算できますが、それでは駄目ですか？

退会済みユーザー

2018/10/13 08:53

返事が遅くなり申し訳ございません。おっしゃる通り、アルファブレンディングが目的です。OpenCV、試したことがありませんでした。というか知りませんでした。OpenXXといったライブラリ(？)がいくつかあるのは知っていたのですが、CL、GL、VGを検証したところで心が折れました。OpenCVについて調査してみたいと思います。

行動規範の内容に同意します

回答2件

条件分岐が 1 つ程度の単純演算では、結局メモリアクセスがボトルネックになるため、半端に並列化するくらいならまともにループを回したほうが高速だと思われます。仮に1GHzのCPUだったとして、32msで 10,000pixel処理するということは、1pixelあたりで3,200clockもある計算になりますので、他のことをやらないのであればCPU処理的には並列などしなくても余裕でしょう。

　よって実務的には、コンパイラの最適化に任せてしまう、その上でメインとしては他の処理を進めたいので別スレッド（プロセス）を立ててそっちにやらせて自分は次の処理を行えるようにする、処理的にアルファチャンネルブレンディングという処理そのものっぽいのでそれ用のライブラリを使う、というあたりになると思われます。

　それらを踏まえた上で、実際どのように最適化されるものなのか、という話を知りたいという質問だと思うので、コンパイラが使うものも含めて代表的な最適化手法をいくつか提示しておきます。なおサンプルコードとかは超適当にその場のノリで書いているので細かいことは気にせず雰囲気だけ感じてください。

１．「max_x」を x の最大値とした場合（例で言うなら max_x=100）、

a[x][y]＝a[x*(max_x+1)+y]

であることを使って101100～0の一重ループにしてしまう。

２．ループ内の処理を条件分岐ではなく演算で処理するようにする。仮に最下位bitが0なら透過、1なら非透過な場合、

	flg=(Aimg & 1) * (~0);
	Cimg=(Aimg & flg) + (Bimg & (~flg)) ;

とかそんな感じ。四則演算でなくビット演算だけでやれるとさらに速くなることが期待できるが、あまり変な書き方をしなければ最適化でいい感じにしてもらえるはず。

３．２のように変形した上でSIMD（single instruction multiple data）命令を使って並列処理する。仮にAimg～Cimgが32bit数の配列だったとした場合、A[0]A[1]A[2]A[3]とB[0]B[1]B[2]B[3]のように、それぞれを4つ繋げて128bit数とした状態にしてSIMD命令へ引き渡し、そのまま1命令で「同じ演算を」複数（この場合4つ）同時に実行し、C[0]C[1]C[2]C[3]な128bit数の答えを得るといった感じ。

４．GPU等には、SIMT(single instruction multiple threads) 命令というものがあり、SIMD命令のように1命令で「同じプログラムを」複数のデータに対して同時に実行することで高速化できるようになっているので、それらの命令（を使って最適化されたライブラリ）を使う。

投稿2018/10/08 07:33

himazin.blm

総合スコア581

退会済みユーザー

2018/10/13 09:41

返事が遅くなり申し訳ございません。OpenCLで検証を行った時に感じたのが、「OpenCLは並列処理で高速化」、というネット情報を信じ、結果が出ないのは使い方が良くない、と思い、ひたすらコーディング方法を調べていました。でも、自分が求めている程度では意味がないのでは？と思い、挫折しました。(まだ使用方法の誤りか、並列実行のボトルネックか分かっていません) SIMDと類似した技術でARM neon(開発環境の都合上)を試してみましたが、1000×1000のような領域では効果はありそうですが、小領域では、やはり一回の実行にかかる最低限の処理速度がボトルネックになりそうでした。

himazin.blm

2018/10/15 23:49

画像処理分野においては、とにかくメモリアクセスがボトルネックになりがちですので、いかに無駄にデータを移動・コピーさせることなく処理するかが重要です。ライブラリを利用するならこの処理のためだけに利用するのではなく、その前後の処理でも利用するようにして、できるだけデータを同じところに置きっぱなしのまま処理するような形にしないと、このような軽い処理では最低限の処理時間＝オーバーヘッドの分だけ遅くなります。また、上記に挙げた 1-3 くらいの最適化は今どきのコンパイラだと自動で行われていたりすることもありますので、評価時にはその可能性も捨てず、大規模なデータ(100-1000 倍) で処理させたりして性能傾向を比較し、コードを書き換えたことで本当に違いができているのかも確認すべきでしょう。

行動規範の内容に同意します