C言語プログラムの並列化について

質問

OpenMPを用いて以下のC言語プログラムを並列化させようと考えています。
(sumの部分は今は単純な足し算ですが、kk0~kk4を用いた複雑な計算を考えています。)
------------------------------------------------------------------------------
#include <stdio.h>
#include <time.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 = PARA_NUM*parameter_num;
long sum_max0 = 0;

for( kk0 = 0; kk0 < PARA_NUM-4; kk0++ ) {
for( kk1 = kk0+1; kk1 < PARA_NUM-3; kk1++ ) {
for( kk2 = kk1+1; kk2 < PARA_NUM-2; kk2++ ) {
for( kk3 = kk2+1; kk3 < PARA_NUM-1; kk3++ ) {
for( kk4 = kk3+1; kk4 < PARA_NUM; kk4++ ) {
sum = kk0+kk1+kk2+kk3+kk4;
if ( sum_max0 < sum ) {sum_max0 = sum;}
if ( sum_min0 > sum ) {sum_min0 = sum;}
}}}}}
printf("max: %d\n", sum_max0);
printf("min: %d\n", sum_min0);
return 0;
}
------------------------------------------------------------------------------
以上のプログラムを以下のように書き変えました。

------------------------------------------------------------------------------
#include <stdio.h>
#include <time.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 = PARA_NUM*parameter_num;
long sum_max0 = 0;

#pragma omp parallel for private(kk0, kk1, kk2, kk3, kk4, sum, sum_min0, sum_max0) schedule(static,1)
for( kk0 = 0; kk0 < PARA_NUM-4; kk0++ ) {
sum_max0=0;
sum_min0=PARA_NUM*parameter_num;
for( kk1 = kk0+1; kk1 < PARA_NUM-3; kk1++ ) {
for( kk2 = kk1+1; kk2 < PARA_NUM-2; kk2++ ) {
for( kk3 = kk2+1; kk3 < PARA_NUM-1; kk3++ ) {
for( kk4 = kk3+1; kk4 < PARA_NUM; 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;
}
------------------------------------------------------------------------------
インテルコンパイラ(icl)にてコンパイルした後、
windows7に標準で搭載されているelapsedtimeで実行時間を測定した結果、
上のプログラムは 2239milliseconds
下のプログラムは446millisecondsとなりました。(cpuは8コア)

8コア使うため実行時間は1/8に近づくと考えていましたが1/5程度となってしまいました。

下のプログラムより良い並列処理をするアルゴリズムはあるのでしょうか。
また#pragma omp criticalの構文は現在の位置が最適なのでしょうか。

回答No.1

ki073 · ベストアンサー

criticalではなく、reductionを使った方が書き換えがなくて良いと思います。

不要な変数を取り除いて、少し整理してみました。 scheduleをdynamicにしています。
気持ち程度しか速くはなっていませんが、ご参考に

それとsumの部分によっては、最適化方法がいろいろありますので、気が向けば書き込んでください。

#include <stdio.h>
#include <time.h>
#define PARA_NUM 200

int main(void)
{
long parameter_num = 5;
long sum_min0 = PARA_NUM*parameter_num;
long sum_max0 = 0;
#pragma omp parallel for schedule(dynamic) reduction(max:sum_max0) reduction(min:sum_min0)
for(int kk0 = 0; kk0 < PARA_NUM-4; kk0++ ) {
for(int kk1 = kk0+1; kk1 < PARA_NUM-3; kk1++ ) {
for(int kk2 = kk1+1; kk2 < PARA_NUM-2; kk2++ ) {
for(int kk3 = kk2+1; kk3 < PARA_NUM-1; kk3++ ) {
for(int kk4 = kk3+1; kk4 < PARA_NUM; kk4++ ) {
long sum = kk0+kk1+kk2+kk3+kk4;
if ( sum_max0 < sum ) {sum_max0 = sum;}
if ( sum_min0 > sum ) {sum_min0 = sum;}
}
}
}
}
}
printf("max: %d\n", sum_max0);
printf("min: %d\n", sum_min0);
return 0;
}

お礼

回答ありがとうございます。

reductionを使うことでここまで分かりやすくなるんですね・・。
reductionでmaxやminのようなことができるのは初めて知りました。
実行時間も446ms→350msと明らかにはやくなり、とても感動しております。

sumの部分については、また躓いたら投稿してみようと思います

本当にありがとうございました！