依存関係のあるfor文に対するOpenMP

質問

初めて質問させていただきます。これまでC言語を勉強していましたが、最近になってgccでも並列計算ができることを知り、その勉強を始めています。今、並列化の醍醐味を味わってみようと思い、組み合わせ数の計算（nCk）に取り組んでいます。まず、OpenMPを使っていない場合のプログラムを作りました。下記のプログラムが、それです。正しく動作していると思います。
しかし、このプログラムでは、for文の前後に依存関係があるため、このままでは並列化ができません。
if文を使って依存関係がないバージョンも試してみましたが、物凄く遅くなってしまいした。
このようなプログラムでOpenMPを活用するには、どのように工夫すれば良いでしょうか？
どなたかご教授をお願いいたします。

追伸
下記のプログラムでは、１００個の中から５つ取り出す際の組み合わせ数を計算しています。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define PARA_NUM 100

int main(void)
{
unsigned long long int i;
unsigned int kk0, kk1, kk2, kk3, kk4;
unsigned int parameter_num = 5;
unsigned int pn[parameter_num];

for( i = 0; i < parameter_num; i++ ) {
pn[i] = PARA_NUM - parameter_num + (i+1);
}

i = 0;
for( kk0 = 0; kk0 < pn[0]; kk0++ ) {
for( kk1 = kk0+1; kk1 < pn[1]; kk1++ ) {
for( kk2 = kk1+1; kk2 < pn[2]; kk2++ ) {
for( kk3 = kk2+1; kk3 < pn[3]; kk3++ ) {
for( kk4 = kk3+1; kk4 < pn[4]; kk4++ ) {
i++;
}
}
}
}
}

printf("%d_C_%d: %lld\n", PARA_NUM, parameter_num, i);
return 0;
}

回答No.5

ki073 · ベストアンサー

No.4のお礼欄について

配列kをprivateにしていますがちゃんと機能するのか心配です。
（ポインタみたいなものなので問題があるように思いますがどうなんでしょうか？）
それとcriticalが一番中のループにあるのでものすごい回数実行されます。効率はがた落ちになります。なるべく外にした方が良いです。

書き直したものを後に示します。（不必要だと思われるところは取り除いています）
openMPなしで、real 0m8.614sです。
openMPあり(core数4)だとreal 0m2.571sで約3倍になっています。それなりに速くなっています。
time ./a.out
で測定した結果です。

#include <stdio.h>

#define PARA_NUM 200

int main(void)
{
long kk0, kk1, kk2, kk3, kk4;
long i;
long parameter_num = 5;
long pn[parameter_num];
long sum;
long sum_max = 0;
long sum_min = PARA_NUM*parameter_num;
long sum_min0, sum_max0;

for( i = 0; i < parameter_num; i++ ) {
pn[i] = PARA_NUM - parameter_num + (i+1);
}

#pragma omp parallel for private(kk0, kk1, kk2, kk3, kk4, sum, sum_min0, sum_max0) schedule(static, 1)
for( kk0 = 0; kk0 < pn[0]; kk0++ ) {
sum_max0=0;
sum_min0=PARA_NUM*parameter_num;
for( kk1 = kk0+1; kk1 < pn[1]; kk1++ ) {
for( kk2 = kk1+1; kk2 < pn[2]; kk2++ ) {
for( kk3 = kk2+1; kk3 < pn[3]; kk3++ ) {
for( kk4 = kk3+1; kk4 < pn[4]; kk4++ ) {
sum = kk0+kk1+kk2+kk3+kk4;
if ( sum_max0 < sum ) {
sum_max0 = sum;
}
if ( sum_min0 > sum ) {
sum_min0 = sum;
}
}
}
}
}
#pragma omp critical
{
if ( sum_max < sum_max0 ) {
sum_max = sum_max0;
}
if ( sum_min > sum_min0 ) {
sum_min = sum_min0;
}
}
}
printf("max: %d\n", sum_max);
printf("min: %d\n", sum_min);
return 0;
}

お礼

ki073さま、

お返事有り難うございました。教えていただいたプログラムを実際に自分でも試してみました。物凄く早くて感動しました。
また、１つ前のプログラムのうように配列 k を使って計算させてみたところ、物凄く遅くなりました。こういうところを工夫すると、格段に計算が早くなるのですね。とても良い勉強となりました。
critical宣言についても、意味することがよく分かりました。for文の一番内側では計算の待ち時間の問題もあり、一番外側にしなければならないことが良く分かりました。
schedule は本などで見たことはありましたが、scheduleの有無でどれだけ計算時間が変わるかは試したことがありませんでした。今回、schedule を付けたり外したりしながら、その効果を確認することができました。
これからも少しずつ並列計算の勉強していきます。また分からないことが出てきたら、こちら質問したいと思っておりますので、その際もよろしくお願いいたします。今回は何度も丁寧に教えてくださり、本当に有り難うございました。

補足

「お礼の欄」に書き忘れたことがありましたので、ここに少しですが書かせていただきます。今後の僕にとって、配列やfor文の中の関数に対する並列化の処理が必要になります。今回教えていただいたプログラムを参考にしながら、少しずつ勉強を進めていきたいと思っています。分からないことがあった場合、改めてこちらのサイトで質問させていただこうと思いますので、その際もよろしくお願いいたします。
これで質問を終了したいと思います。
今回は、何度も教えてくださり、本当に有り難うございました。

回答No.4

ki073

No.3の修正
綴りの間違いです。ciritalではなくcriticalですね。

お礼

ki073さま、

ご連絡が遅くなりました。
いただいたアドバイスを活用しながら、いろいろと試してみました。
最終的に、正しく動作したプログラムを下記に添付します。
ki073さんがおっしゃっている通り、critical宣言を使うと、物凄く効率が落ちますね。やはり配列に一旦入れて、for文を抜けた後に処理する工夫が必要なようです。
今後は、一番内側のfor文の中に関数がある場合についても取り組みたいと思っています。どのようにすべきかなど、まだまだ知らないことや分からないことがありますので、改めてOKWave上で質問したいと思っております。
もしよろしければ、その際も、アドバイスをいただければと思います。
今回は、とても有益なアドバイスを有り難うございました。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <malloc.h>
#include <time.h>
#include <omp.h>

#define PARA_NUM 200

int main(void)
{

unsigned long long int i;
int j;
unsigned long long int ii;
unsigned long long int kk0, kk1, kk2, kk3, kk4;
unsigned int parameter_num = 5;
unsigned int pn[parameter_num];
unsigned int k[parameter_num];
int sum;
int sum_max = 0;
int sum_min = 1000;
double t1, t2;

for( i = 0; i < parameter_num; i++ ) {
pn[i] = PARA_NUM - parameter_num + (i+1);
}

i = 0;
t1 = omp_get_wtime();
omp_set_num_threads(THREADS_NUM);
#pragma omp parallel for private(ii, kk0, kk1, kk2, kk3, kk4, k, sum, j ) \
shared(sum_max, sum_min) \
reduction(+:i)
for( kk0 = 0; kk0 < pn[0]; kk0++ ) {
ii = 0;
for( kk1 = kk0+1; kk1 < pn[1]; kk1++ ) {
for( kk2 = kk1+1; kk2 < pn[2]; kk2++ ) {
for( kk3 = kk2+1; kk3 < pn[3]; kk3++ ) {
for( kk4 = kk3+1; kk4 < pn[4]; kk4++ ) {
ii++;
k[0] = kk0;
k[1] = kk1;
k[2] = kk2;
k[3] = kk3;
k[4] = kk4;

sum = 0;
for( j = 0; j < parameter_num; j++ ) {
sum += k[j];
}

#pragma omp critical
{
if ( sum_max < sum ) {
sum_max = sum;
}

if ( sum_min > sum ) {
sum_min = sum;
}
}
}
}
}
}
i += ii;
}

t2 = omp_get_wtime();

printf("\n");
printf("# wall clock time: %lf sec\n", t2-t1 );
printf("%d_C_%d: %lld\n", PARA_NUM, parameter_num, i);
printf("max: %d\n", sum_max);
printf("min: %d\n", sum_min);
printf("#-----------------------------------------------\n");

return 0;
}

回答No.3

ki073

No.2の補足欄について

No.1の回答と同じように考えればできるはずです。
j=0;
の位置で各threadのmaxとminを覚えておくprivate変数を初期化します。
カウンタとして使った
i += j;
の位置には、最大値、最小値の計算をreductionではできないので（FORTRANは使えるようです）
効率の落ちるのを覚悟でcirital宣言して各ループで計算した値から、最大値最小値を求めるか、
それとも、最大値用と最小値用にpn[0]個分の配列を確保して、一旦その配列に記憶させておいて、ループを抜けた後に計算する方法が使えるように思います。

お礼

何度も回答してくださり、本当に有り難うございます。
private変数の初期化とcritical宣言を試してみます。
配列の処理やfor文の中の処理が出来ると、今後、様々なことが出来きるようになるので、僕にとってはとても重要な内容です。
ただ、実際にそれらを試せるのは来週の月曜日になります。お返事が遅くなりますが、自分の力で上手く出来たかどうかや新たな質問などを、来週の月曜日か火曜日にご報告させていただきます。

また、ki073さんの方で追加のアイデアがありましたら、ぜひ、教えてください。
今回も、本当に有り難うございました。

回答No.2

ki073

今回のものは変数iがループの中で他から参照されていませんので特殊なケースです。
依存関係はありつつもループ自体どの順番に実行しても答えは変わらないので、もっとエレガントな方法があるかも知れません。

実際に実行してみると、実行時間は並列化してもそう速くなりませんでした。
kk0の小さい時は、内部のループの回数がものすごく多く、kk0が大きくなるにつれて、回数が少なくなってきます。
threadをkk0の値に関わらず均等に割り振っているようで、kk0の小さいthreadが最後まで残ってしまいそれが律速になっているかもしれません。schedule 指示節を加えて調整した方がよいように思います。

お礼

再度の回答、有り難うございます。
今後、進みたい方向は、変数iの計算そのものではなく、for文の一番内側で行う計算を、効率良く処理することです。
例えば、下記のような感じです。
そこで、for文の前後の依存関係を適切に処理しなければ、効率の良い並列化が難しいと思い、まずは、最初の質問に書いた問題を解いてみようと思いました。

for( kk0 = 0; kk0 < pn[0]; kk0++ ) {
for( kk1 = kk0+1; kk1 < pn[1]; kk1++ ) {
for( kk2 = kk1+1; kk2 < pn[2]; kk2++ ) {
calc(num, parameter_num, output, A);
}
}
}

補足

「お礼の欄」に書いた内容とプログラムでは、正しく説明できていませんでしたので、ここに改めて書かせていただきました。下記のプログラムのように、組み合わせられる値、0-1-2-3-4や1-2-3-4-5の数値の和を求めて、その最大値と最小値を求めたいとします。これが変数iそのものを求めるではなく、for文を効率よく並列化して、素早く求めたいと思っているという意味です。何度も説明をして申し訳ありません。

for( kk0 = 0; kk0 < pn[0]; kk0++ ) {
for( kk1 = kk0+1; kk1 < pn[1]; kk1++ ) {
for( kk2 = kk1+1; kk2 < pn[2]; kk2++ ) {
for( kk3 = kk2+1; kk3 < pn[3]; kk3++ ) {
for( kk4 = kk3+1; kk4 < pn[4]; kk4++ ) {
k[0] = kk0;
k[1] = kk1;
k[2] = kk2;
k[3] = kk3;
k[4] = kk4;

sum = 0;
for( j = 0; j < parameter_num; j++ ) {
sum += k[j];
}

if ( sum_max < sum ) {
sum_max = sum;
}
if ( sum_min > sum ) {
sum_min = sum;
}

}
}
}
}
}

回答No.1

ki073

変数iが依存関係がありますねえ。
並列化はできるだけ外のforで行う方が良いので5重のforの一番外でできないか考えてみます。プログラムの骨格をできるだけ変えないようにしてみました。
変更場所だけだけを書きますと、

i = 0;
#pragma omp parallel for private(j, kk0, kk1, kk2, kk3, kk4) reduction(+:i)
for( kk0 = 0; kk0 < pn[0]; kk0++ ) {
j=0;
for( kk1 = kk0+1; kk1 < pn[1]; kk1++ ) {
for( kk2 = kk1+1; kk2 < pn[2]; kk2++ ) {
for( kk3 = kk2+1; kk3 < pn[3]; kk3++ ) {
for( kk4 = kk3+1; kk4 < pn[4]; kk4++ ) {
j++;
}
}
}
}
i += j;
}

こんな感じでいかがでしょうか。jはあらかじめ宣言しておいてください。
これで一番外側のforで依存関係がなくなるはずです。
短時間で実行が終わるので全然効果は分かりませんが、適当に時間がかかるように内部にループを追加したら、並列化していることは確認できました。

お礼

お返事、有り難うございます。
依存関係を解消するのに、このようなアイデアがあるとは、まったく思いつきませんでした。今後、さらに多くのfor文を追加していきたいと思っているので、このアイデアを使って、より内側のfor文も並列化できないか取り組んでみます。
もし、ki073さんの方で追加のアイデアがありましたら、ぜひ、教えてください。
今回は、本当に有り難うございました。