openMPにしたいのですが

質問

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include "dSFMT.h"
#include <sys/time.h>
#include <omp.h>

#define T_END 100
#define BIRTH_RATE 1.0
#define DEATH_RATE 0.1
#define ALLEE_EFFECT 0.5
#define T_DENSITY 10.0
#define PROPAGULE_SIZE 5

#define SD_INTERACTION 1.0
#define SD_DISPERSAL 1.0

struct timeval start_timeval,end_timeval;

int getutimer (struct timeval *start,struct timeval *end) {
return ( ((int)end->tv_sec - (int)start->tv_sec)*1000000+((int)end->tv_usec - (int)start->tv_usec) );
}

/* Properties of an individual */
typedef struct individual {
double x, y, local_density;
struct individual *next_indiv;
}INDIVIDUAL;

void calc_local_density(INDIVIDUAL *);
double birth_rate(double);
double death_rate(double);
void birth(INDIVIDUAL*);
void death(INDIVIDUAL*);
void dispersal(INDIVIDUAL*);
void display_list(INDIVIDUAL*);
void write_to_file(INDIVIDUAL*, int, double, double);
INDIVIDUAL *make_new_indiv();
INDIVIDUAL *add_next_indiv(INDIVIDUAL*);
double weight(double);
double distance(INDIVIDUAL*, INDIVIDUAL*);
double sqr(double);
int number_of_indivs(INDIVIDUAL*, double*, double*);

dsfmt_t dsfmt;
FILE *fp;

int main(){
int seed;
INDIVIDUAL *list_head, *indiv;
int i, t;
double xcenter, ycenter;

gettimeofday(&start_timeval,NULL);
seed=(long)time(NULL);
dsfmt_init_gen_rand(&dsfmt, seed);
fp = fopen("output.dat","w");
list_head = make_new_indiv();
indiv = list_head;

for(i=0; i<PROPAGULE_SIZE; i++){
indiv = add_next_indiv(indiv);
indiv->x = 0.0;
indiv->y = 0.0;
indiv->local_density = 0.0;
}
write_to_file(list_head, 0, 0.0, 0.0);
for(t = 1; t <= T_END; t++){
dispersal(list_head);
death(list_head);
calc_local_density(list_head);
birth(list_head);
printf("Time = %d, Population size =%d\n", t, number_of_indivs(list_head, &xcenter, &ycenter));
write_to_file(list_head, t, xcenter, ycenter);
}
time(&time2);

gettimeofday(&end_timeval,NULL);

printf("%d %d, %d\n", time1, time2, time2 - time1); //??
printf("マイクロ秒:%d \n",getutimer(&start_timeval, &end_timeval));
return 0;
}
・
・
・
・
int number_of_indivs(INDIVIDUAL *list_head, double *xcenter, double *ycenter){
int count = 0;
double xsum = 0.0, ysum = 0.0;
INDIVIDUAL *indiv;
for(indiv = list_head->next_indiv; indiv != NULL; indiv = indiv->next_indiv){
xsum += indiv->x;
ysum += indiv->y;
count++;
}
*xcenter = xsum/(double)count;
*ycenter = ysum/(double)count;
return count;
}

をopenMpにしたいのですがなかなか上手くいきません。

人口のシミュレーションなのですが、人が増えるたびに計算回数が増えるのでなんとかしたいのですが・・・

すべてのソースコードを記載ようとしたのですが、文字制限で載せられませんでした・・・

どうかお助けください。。

よろしくお願いいたします。

回答No.5

ki073 · ベストアンサー

ANo.4の補足について

gprof test.o test.o.gmon
は多分
gprof test.o gmon.out
となると思うのですが、まずはやってみてください。

reductionはたぶん直ぐに必要になると思うのですが、
scheduleはもう少し先でということでいかがでしょうか？

リンクしていたpdfファイルはOpenMP 入門 (2)ですが
これの（1）にはreductionなどが分かりやすく書かれていますので、まずそちらを読んでみてください。
http://www.cc.kyushu-u.ac.jp/scp/system/library/OpenMP/OpenMP.html

mainのループが本当に依存性がないのなら、そこで並列化してもよいのですが、貼付けた部分からは分かりませんので。
実際にどこを並列化するかも考えてみてください。
CUDAの場合も、同じくような考え方でいけますので。

お礼

返信が遅くなってしまい申し訳ございませんでした。

mainのfor文にやはり依存性があり、

ポインタを使っているのでなかなか並列できない状態でございます。

また質問するかと思いますのでその都度はまたお願いできますでしょうか？

親切に教えていただきありがとうございました！！

回答No.4

ki073

ANo.1～3の補足について

OPENMPもしくはCUDAの使用が優先ですね。承知しました。
質問者さんは情報系の学生で、卒論（あるいは修論）のテーマということでしょうか？
そういう前提だと、
話の筋道としてprofilerで解析し、この部分をopenMPなどで並列化したら、このように高速化できましたというストーリーが良いように思います。

ソフトから見ると端末はWindowsで、コンパイルと実行はLinux(あるいはUNIX)でしょうか？

説明が悪かったかもしれませんが、
mainのプリント文はそれだけでは依存関係はありません。人が見て順番がぐちゃぐちゃだと見づらいのと、このようなシミュレーションの場合は、前の計算結果を使っていることがほとんどなので、そう書いたまでです。

ソースコードからは並列化できそうなところはNo.3にも書きましたように
for(indiv = list_head->next_indiv; indiv != NULL; indiv = indiv->next_indiv){
xsum += indiv->x;
ysum += indiv->y;
count++;
}
の部分です。先に書きましたように並列化してもかえって遅くなるでしょうから全然実用的でないのですが、練習としていかがでしょうか？
http://www.cc.kyushu-u.ac.jp/scp/system/library/OpenMP/openmp0201.pdf
の説明をもとに書きますと
xsum, ysum, count
は「3.8 reduction 指示節」を使うと並列化できます。
このループが実行回数がかなり多いとなると、（ループ１回を１スレッドにするのではなく）例えば100回分を１つのスレッドにまとめて実行して高速化する方法もあります「4.1 schedule 指示節」

補足

卒論の練習みたいです。

ストーリーまで考えていただいてありがとうございます！！！！

コンパイルはlinaxです。

帰って遅くなってしまうのですか・・・

reductionとschedule試してみます♪

質問なのですが、 profilerの利用がうまくいきません・・・　
--------------------------------------------------------------------------------------------
gprofを使うには「-pg」オプションをつけてコンパイルする必要があります。

$ gcc -pg -o test.o test.c
あとは、実行ファイルを普通に実行します。このとき、gprofのデータファイルが同じディレクトリに生成されます。

$ ./test.o
「gprof 実行ファイル データファイル」とすると、解析結果が出力されます。

$ gprof test.o test.o.gmon
---------------------------------------------------------------------------------------------
ってやりかたでよいのでしょうか？？

回答No.3

ki073

たびたびすみません、

大事なことを書き忘れていました。
プログラムを実行したときにメモリは十分足りていますよね。
実行中にCPU使用率を見れば分かりますので、確認してください。
使用率が低いようでしたら、メモリ不足の可能性が大きいです。
（single threadですので、1 core分が100%になっているはず）

ソースコードをざっと見ました。
基本は先に書いたようにループを見つけて、そこを並列化します。
main()の真ん中にある
for(t = 1; t <= T_END; t++){
が時間のかかるところだと思いますが、
printf("Time = %d, Population size =%d\n", t,
があるし（表示の順番は多分大事）、依存関係が多分ありますよね。
（直感的には、ループの順番を入れ替えても正しい答えが出れば基本的には問題ない）

そうすると次にループの中にある
dispersal(list_head);
death(list_head);
calc_local_density(list_head);
birth(list_head);
のサブルーチンの中に並列化できる部分がないか見ていきます。

下の方の
int number_of_indivs(
中の
for(indiv = list_head->next_indiv; indiv != NULL; indiv = indiv->next_indiv){
xsum += indiv->x;
ysum += indiv->y;
count++;
}
はxsumで合計を計算しています。これは前の計算で出したxsumに加えているので依存関係はあるのですが、ループの実行順序を入れ替えても正しい結果が出ますので、この部分は並列化可能です。ysumとcount++も同様ですので、このループはやろうと思えば並列化できます。
ただし、このような短い繰り返しはわざわざ並列化しても効率的でないので、通常はやりません。

長めのループで並列化するのがコツですが、長いとその中に依存関係がでてきやすいので、そこを見つけるのが難しいということになります。
並列化できるところは、コンパイラの自動並列化機能で見つけられますので、それを利用するのが良いと思います。
現実的には、最適化メッセージを見ながら、並列化できるようにソースコードを修正していく作業になります。

ANo.1にも書きましたように、並列化できるところを見つけないと、openMPで並列化はできません。

まずは、メモリ不足になっていないか確認してみてはいかがでしょうか（これがかなり怪しい）

補足

実行中にCPU使用率を確認したのですがあまり変わりませんでした・・・

参考になるかわからないのですが
・tera term
・WinSCP
というものを先生から使えといわれています。

for(t = 1; t <= T_END; t++){
が時間のかかるところなんですか！！

確かに表示は重要です・・・これが依存なんですね！！

サブルーチンの中も見なければいけないのですか・・・

mainだけかと思っていました。。

長めのループを見つけるようにしてみます！！！！

ki073さんによければ全てのプログラムを見ていただきたかったのですが

メッセージとかは送れないのですね・・・
残念です・。。・

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

回答No.2

ki073

ANo.1の続きです。
現実的には何倍くらい高速にしたいのでしょうか？
それのよっていろいろ選択肢はあります。
プロフィールによれば学生さんなので、最悪学内のコンピュータで力ずくという手も。

補足

何倍早くしたいとかはないのですが・・・
もちろんできるだけ早く動いたほうがうれしいです♪

並列化するとどれだけ早くなるかを見てみよう
って感じでやってみなさいと。。

力ずくって気になります！！

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

回答No.1

ki073

まず確認しておきたいのですが、openMPを使いたいというよりも、プログラムを高速化したいということですよね。

コンパイラは何をお使いでしょうか？市販のintelやPGIのものは自動的に並列化してくれるオプションがあります。gccはよく分かりまでんが搭載されているかもしれませんので確認ください。openMPより効率はわるいけども、ソースコードを変えずにそこそこの速度はでます。（IntelのコンパイラはLinux限定ですが、個人かつ非商用であれば無料で使えます。PGIは期間限定で試用はできます。）
それに加えて、SSEが使えれば更に高速化できます。

高速化の手順ですが。
まずは、profilerでどのルーチンが時間がかかっているか調べます。
そこに集中して最適化を進めていきます。
最適化できるのは、ループになっているところです。
そこを並列化（あるいはSSEで実行できるように）できるか調べます。
ループ間の依存関係があればできませんし、無ければコンパイラが自動でやってくれます。
（並列化できる条件がいろいろありますので、依存関係があってもできる場合もあります）
並列化については検索すれば概要はわかると思いますし、専門の本もあります。

いずれにしても、自動であれopenMPであれ、ループの中でデータの依存関係がない（あるいは並列化できるレベルの依存関係）ことが大切です。

それともうCで全部書いてしまったのでしょうか？
高速化のプロでなければ、Fortranで書いた方が有利です。
Cは自由度がある分、コンパイラが並列化できるか判断しにくいので、ソースコード中に#pragma文などを入れて依存関係を教えてやらないと最適化はなかなか進みません。

いずれにしても、コンパイルしてみて、出てくる最適化情報を見ないとなかなか判断できません。

補足

高速にしたいというものが前提なのですが、

課題でOPENMPもしくはCUDAを使用しなければいけないのです・・・

コンパイラはgccだと思います。

profiler調べてみます！！

データ依存など一通り学んでからのopenMPなのですが
実際に試そうと思ったときに理解ができませんでした・・・

もうC言語でのプログラムはできています！

ご回答とてもうれしいです！！！！