OpenMPのことで悩んでいます

質問

現在、OpenMPを用いてOpenCVのライブラリを並列実行可能な形にしています。
その中で、配列のリダクションを行う場所があるのですが、その部分をどう書き換えればいいのか悩んでいます。

for( i = 0; i < height; i++ )//画像の高さ
{
for( j = 0; j < width; j++ )//画像の幅
{
if( image[i * step + j] != 0 )　//エッジ抽出後の画像データ
for(int n = 0; n < numangle; n++ )
{
int r = cvRound( j * tabCos[n] + i * tabSin[n] ); //極座標空間への変換
r += (numrho - 1) / 2;
int index = (n + 1) * (numrho + 2) + r + 1;

//#pragma omp critical
//{
accum[index]++; //極座標に対応する配列accumへの軌跡の投票
//}

}
}
}

上がそのコードです。配列accumの要素をインクリメントする際に、データアクセスの競合が起こってしまいます。
その部分の上に「#pragma omp critical」と入れればアクセスの競合は防げるのですが、速度が200倍程度遅くなってしまい、使い物になりません。
なんとか配列の要素に対するリダクション処理を行いたいです。
OpenMPで配列のリダクションをする際の定石等あれば教えていただきたいです。

回答No.4

ki073 · ベストアンサー

if文がどの程度足を引っ張るか興味があったので、計算時間を測ってみました。
質問欄のプログラム、ただし、外側のループを２０回実行して時間稼ぎをしています。
2.98秒
一番内側のループを外側に出したもの、
11.48秒
改造して共通する計算をできるだけループ外に出したもの
8.3秒
やっぱりif文の影響がかなり大きいようです。

ついでに、
No.1の方法　11.9秒
No.2の方法　8.7秒

ちなみに第一世代のCore i5で2.66GHz 4 coreです。
プログラムが正しいかほとんどチェックしていませんので、結果を保証しかねますのでその点はご了承ください。

結局は元の方法が一番速い結果でした。
accum[index]++がデータの依存関係が有りまくりなのが敗因のようです。
どうしても速くしたいのであれば、ここだけではなく全体のアルゴリズムを見直す必要があるようです。

お礼

ありがとうございます。

私の方でもいろいろとやってみたのですが、やはりアルゴリズムの大幅な変更が必要だという結論になりました。
OpenMPにはアドレス単位のアトミック演算がないというのが痛いですね・・・。

回答No.3

ki073

考えてみましたが、No.2以上は難しそうです。

if文を考慮に入れないと600*800*180回ループを回りますので、それに比べると計算量がそんなに増える訳ではないので、まあ効果は期待できるのではないかと思います。CPUコアが2つだと苦しいような気がします。

変数がどのような値をとるのか分かりませんので
他の考え方ができるか判断できませんが、numrhoは定数じゃ有りませんよね。定数なら別のやり方も。

また、思い切って一番内側のfor文を一番外に出すのも面白いかも知れません。
それによって、if文が一番内側にありますので、当然これが足を引っ張ります。
cvRound( j * tabCos[n] + i * tabSin[n] )が
cvRound( j * tabCos[n] )+cvRound( i * tabSin[n] )に置き換え可能なら、多くの計算をループの外に出せるようになります。
その辺りがどの程度効果があるか不明ですが、計算量はかなり減少させることができます。iやjに対してindexが単調増加になりますので、何か利用できる可能性もあります。if文のimage[i * step + j]もi*step分平行移動しただけですので、計算量減少に利用できるかも知れません。いずれにしても、大幅な改変が必要ですので、そこまでやる必要があるかも分かりません、
こちらは、そんな気がするという程度ですので、まだ深くは考えていません。

回答No.2

ki073

>クリティカルに加えるという事でいいのでしょうか。クリティカルな操作の回数を減らせるのですね。
そうです。

質問欄のものよりも速くはなるはずですが、openMPを使わない状態に比べて速くならないかもしれません。
height*width* numangle回criticalの発生が(if文が途中にあるのでもっと少ないはずですが)、height回まで減りますが、こんどは配列の初期化と加算が増えてしまします。

No.1の後半に書いている方法が良いように思います。
#pragma omp parallel for schedule(static, 1)
for(k=0; k<NumThread; k++){
// increment_accum[]を確保して初期化、
int i_start=height/NumThread*k;
int i_end=(k==NumThread) ? height : height/NumThread*(k+1);
for(int i=i_start i < i_end; i++ ){
のようにして（iの範囲が正しいか確認してください）、
}
//accum[]にincrement_accum[]を加える
}
のようにすると、NumThread回に減らせます。if文がありますので、heightを均等に分けても偏りが生じる可能性もあります。
その時は、NumThreadをCPUコア数ではなく、2～数倍多めにしておくとスレッドの偏りが減ります。

CPUコア数が4以上でないと、速度的には苦しいと思います。

高速化の基本は、回数が一番多い一番内側のループの最適化をまず考えて並列化に進むのですが、難しそうですね。

それと、
height, width, numangleの数とaccum[]の配列サイズ、
if( image[i * step + j] != 0 )が成立する大まかな比率はどれくらいになりますか？

accum[]のサイズがあまり大きくなく、if文が成立する割合が比較的高い前提ですので、条件によっても高速化の手法が変わる可能性があります。

補足

詳しくありがとうございます。

height = 600 width = 800 numangle = 180
accum[]のサイズは280000要素程度
ifが成立する比率は４０％程度なのですが、どうでしょうか？

回答No.1

ki073

並列化が一番外のループで行われており、accum[index]++だけがデータ依存関係があるとして書きます。

その場合には、依存関係にある計算を、できるだけ外側のループに移せないか考えます。
そのままでは無理そうなので、
for( j = 0; j < width; j++ )の前に、increment_accum[]のような配列を確保して初期化、
accum[index]++の位置に、increment_accum[index]++
for( j = 0; j < width; j++ )ループを抜けたところで、accum[]にincrement_accum[]を加えることで、外に出せます。

これでも遅い場合は,並列実行されるCPU数に分割するために新たにループを作成して、increment_accum[]を確保、
for( i = 0; i < height; i++ )をCPU数に応じて分割し後は同様、

前者の方法で解決しそうな気がします。

補足

widthループを抜けたとろでaccumにincrement_accumを加えるという事ですが、increment_accumはプライベートな配列であり、accumはグローバルな配列なため、クリティカルに加えるという事でいいのでしょうか。クリティカルな操作の回数を減らせるのですね。