openMPによる人口のシミュレーション

前へ 次へ
このQ&Aのポイント
  • openMPを使用して人口のシミュレーションを高速化する方法を模索しています。
  • 人口が増えるたびに計算回数が増えるため、効率的な方法を見つけたいと考えています。
  • 現在のソースコードの一部を示しましたが、文字制限のため全てを掲載できません。
回答を見る
  • ベストアンサー

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にしたいのですがなかなか上手くいきません。 人口のシミュレーションなのですが、人が増えるたびに計算回数が増えるのでなんとかしたいのですが・・・ すべてのソースコードを記載ようとしたのですが、文字制限で載せられませんでした・・・ どうかお助けください。。 よろしくお願いいたします。

質問者が選んだベストアンサー

  • ベストアンサー
  • ki073
  • ベストアンサー率77% (491/634)
回答No.5

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の場合も、同じくような考え方でいけますので。

asuka_1026
質問者

お礼

返信が遅くなってしまい申し訳ございませんでした。 mainのfor文にやはり依存性があり、 ポインタを使っているのでなかなか並列できない状態でございます。 また質問するかと思いますのでその都度はまたお願いできますでしょうか？ 親切に教えていただきありがとうございました！！

その他の回答 (4)

  • ki073
  • ベストアンサー率77% (491/634)
回答No.4

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 指示節」

asuka_1026
質問者

補足

卒論の練習みたいです。 ストーリーまで考えていただいてありがとうございます！！！！ コンパイルはlinaxです。 帰って遅くなってしまうのですか・・・ reductionとschedule試してみます♪ 質問なのですが、 profilerの利用がうまくいきません・・・　 -------------------------------------------------------------------------------------------- gprofを使うには「-pg」オプションをつけてコンパイルする必要があります。 $ gcc -pg -o test.o test.c あとは、実行ファイルを普通に実行します。このとき、gprofのデータファイルが同じディレクトリに生成されます。 $ ./test.o 「gprof 実行ファイル データファイル」とすると、解析結果が出力されます。 $ gprof test.o test.o.gmon --------------------------------------------------------------------------------------------- ってやりかたでよいのでしょうか？？

  • ki073
  • ベストアンサー率77% (491/634)
回答No.3

たびたびすみません、 大事なことを書き忘れていました。 プログラムを実行したときにメモリは十分足りていますよね。 実行中に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で並列化はできません。 まずは、メモリ不足になっていないか確認してみてはいかがでしょうか（これがかなり怪しい）

asuka_1026
質問者

補足

実行中にCPU使用率を確認したのですがあまり変わりませんでした・・・ 参考になるかわからないのですが ・tera term ・WinSCP というものを先生から使えといわれています。 for(t = 1; t <= T_END; t++){ が時間のかかるところなんですか！！ 確かに表示は重要です・・・これが依存なんですね！！ サブルーチンの中も見なければいけないのですか・・・ mainだけかと思っていました。。 長めのループを見つけるようにしてみます！！！！ ki073さんによければ全てのプログラムを見ていただきたかったのですが メッセージとかは送れないのですね・・・ 残念です・。。・ ご回答ありがとうございます！！！！

  • ki073
  • ベストアンサー率77% (491/634)
回答No.2

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

asuka_1026
質問者

補足

何倍早くしたいとかはないのですが・・・ もちろんできるだけ早く動いたほうがうれしいです♪ 並列化するとどれだけ早くなるかを見てみよう って感じでやってみなさいと。。 力ずくって気になります！！ ご回答ありがとうございます。

  • ki073
  • ベストアンサー率77% (491/634)
回答No.1

まず確認しておきたいのですが、openMPを使いたいというよりも、プログラムを高速化したいということですよね。 コンパイラは何をお使いでしょうか？市販のintelやPGIのものは自動的に並列化してくれるオプションがあります。gccはよく分かりまでんが搭載されているかもしれませんので確認ください。openMPより効率はわるいけども、ソースコードを変えずにそこそこの速度はでます。（IntelのコンパイラはLinux限定ですが、個人かつ非商用であれば無料で使えます。PGIは期間限定で試用はできます。） それに加えて、SSEが使えれば更に高速化できます。 高速化の手順ですが。 まずは、profilerでどのルーチンが時間がかかっているか調べます。 そこに集中して最適化を進めていきます。 最適化できるのは、ループになっているところです。 そこを並列化（あるいはSSEで実行できるように）できるか調べます。 ループ間の依存関係があればできませんし、無ければコンパイラが自動でやってくれます。 （並列化できる条件がいろいろありますので、依存関係があってもできる場合もあります） 並列化については検索すれば概要はわかると思いますし、専門の本もあります。 いずれにしても、自動であれopenMPであれ、ループの中でデータの依存関係がない（あるいは並列化できるレベルの依存関係）ことが大切です。 それともうCで全部書いてしまったのでしょうか？ 高速化のプロでなければ、Fortranで書いた方が有利です。 Cは自由度がある分、コンパイラが並列化できるか判断しにくいので、ソースコード中に#pragma文などを入れて依存関係を教えてやらないと最適化はなかなか進みません。 いずれにしても、コンパイルしてみて、出てくる最適化情報を見ないとなかなか判断できません。

asuka_1026
質問者

補足

高速にしたいというものが前提なのですが、 課題でOPENMPもしくはCUDAを使用しなければいけないのです・・・ コンパイラはgccだと思います。 profiler調べてみます！！ データ依存など一通り学んでからのopenMPなのですが 実際に試そうと思ったときに理解ができませんでした・・・ もうC言語でのプログラムはできています！ ご回答とてもうれしいです！！！！

  1. カテゴリ
  2. [技術者向] コンピューター
  3. プログラミング・開発
  4. C・C++・C#

関連するQ&A

  • openMPにしたいのですがお手伝いください。

    void calc_local_density(INDIVIDUAL *list){ INDIVIDUAL *indiv1, *indiv2; double sum; indiv1=list->next_indiv; for(; indiv1; indiv1=indiv1->next_indiv){ sum = 0.0; indiv2=list->next_indiv; for(; indiv2; indiv2=indiv2->next_indiv){ sum += weight( distance(indiv1, indiv2) ); } indiv1->local_density = sum; } } } この部分をopenMPにしたいのですが、 内側のfor文はreductionでできると考えたのですが 外側のfor文は依存があり上手くいきません。 (1)このopenMPのコツや知恵をお貸ししていただいたらうれしいです♪ (2)また２重for文のときにopenMPを使用する際に どのように書けばいいのかがわからず困っています。 ご協力お願いいたします。。

  • アルゴリズム　線形リスト

    最近リストについて習い始めました。入力したデータと同順に並ぶリストを作成しようと思い、コードを打ったのですが…動作中止の表示がでてしまいました。どこが間違っているのか、ずっと悪戦苦闘して組んでいるのですが、全く出口が見えてきません。何が間違えているのか、はたまた根本的に違うのか、ご指導して頂けると有難いです。 以下、コードです。 #include <stdio.h> #include <stdlib.h> #include <string.h> struct hito{ char name[20]; int age; struct hito *next; }; void main(void){ struct hito *p, *head, *dummy; char new_name[20]; int new_age; dummy = (struct hito *)malloc(sizeof(struct hito)); head = dummy; dummy->next = p; dummy = p; while (scanf("%s %d" , new_name, &new_age) != EOF) { p = (struct hito *)malloc(sizeof(struct hito)); strcpy(p->name, new_name); p->age = new_age; p->next = head; head = p; } while(p != NULL) { printf("\t%-20s %3d\n" , p->name, p->age); p = p->next; } }

  • リスト構造を使ってSortとSearchをするプログラム

    タイトルのとおりのプログラムを組んでみました ----------himajin.c----------- #include <stdio.h> #include <string.h> #include <stdlib.h> // 参考:http://www9.plala.or.jp/sgwr-t/c/sec15-5.html // コンパイラ:BCC 5.5 // アイテムの加え方が違う。 struct Item { int data; /* データ */ struct Item *next; /* 次のデータへのポインタ */ }; struct Item *head; struct Item *tail; struct Item *addItem(struct Item *p,int newdata){ struct Item *t; t->data = newdata; t->next = tail; p->next = t; return t; } int main(){ struct Item *item; int inputdata; head = item; item->next = tail; while (scanf("%d", &inputdata) != EOF) { item = addItem(item,inputdata); } /* search(5); sort(); */ return 0; } int sort(){ struct Item *j; struct Item *p; struct Item *t; p = head; t = head; while (p->next != tail){ while (p->data > t->data){ j = t; t = t->next; } j->next = p; p->next = t; p = p->next; } } int search(int searchdata){ struct Item *t; t = head; tail->data = searchdata; while (searchdata != t->data){ t = t->next; } if(t == tail){ printf("Not Found"); } else{ printf("Found"); /*後で考える*/ } return 0; } ---- ...が、コマンドラインで himajin.exe 5 と入力してみたところ、いきなりプログラムが落ちました。何がいけないのでしょうか？

  • MIPSアセンブラ言語について

    #include NULL 0 struct list{ struct list +next; int value; }; int sumvalue(sturuct list *head){ struct list *cur=NULL; int sum=0; for(cur = head; cur !=NULL; cur=cur->next){ sum += cur->value; } return sum; } このC言語で書かれた関数をMIPSアセンブラで記述するとどうなるのでしょうか？ポインタで混乱してます。

  • 線形リストについて。

    このたび線形リストを学習し、自分でサンプルコードを書くことにしました。 しかし、動かすことが出来ず、理解することが出来なかったため、ご相談致します。 コード： #include <stdio.h> #include <stdlib.h> #define N 10 typedef struct node *link; struct node { int item; link next; }; void main() { int i; link head ,t; head = NULL; //リストに要素を入れる。 for(i = 0,t = head; i < N; i++, t = t->next) { t = malloc(sizeof *t); t ->next = NULL; t ->item = i; } //リストを表示する for(t = head; t != NULL; t = t->next) { printf("%d\n", t->item); } } 実行結果： リストを表示するのfor文内、t->itemでエラー。 原因はheadを上手くポインタで指せていないことにあると思います。 お聞きしたいことは2点です。 1.なぜ意図したように上手く動かないのか。 2.このように動かしたい場合、何処を変更すれば良いのか。 以上です。 宜しくお願いします。

  • 領域を確保した後の文字の並び替え

    領域を確保した後、アドレスを書き変える勉強をしています。入力した文字を逆から表示していくことに成功したので今度はソートで小さい順に並び替えをさせようとしまして、色々試したのですが何度やっても上手くいきません。 どのように組めばいいか教えてください。よろしくお願いします。 #include<stdio.h> #define MAX 40 struct parts * ListChar(char moji[]); typedef struct parts{ struct parts *next; char moji; }PARTS; main(void){ char moji[MAX]; PARTS *list; PARTS *head; scanf("%s",moji); head = ListChar(moji); for(list=head ; list!=NULL ; list=list->next){ printf("%c",list->moji); } printf("\n"); for(list=head ; head!=NULL ; list=head){ head = list->next; free(list); } } struct parts * ListChar(char moji[]){ int i,j,len1; char dam; PARTS *head; PARTS *list; PARTS *back; PARTS *start; PARTS *list2; len1 = strlen(moji); for(i=0 ; i<len1 ; i++){ list = (struct parts *)malloc(sizeof(struct parts)); /*領域の確保*/ list->next = NULL; if(i == 0){ head =list; }else{ back->next =list; } back = list; list->moji = moji[i]; } head = back; return head; }

  • C言語　リスト

    (1) /* list.c */ #include <stdio.h> #include <stdlib.h> struct node { int num; struct node *next; }; main() { struct node *head, *p; int x; head = NULL; while(scanf("%d",&x) != EOF) { p = (struct node *)malloc(sizeof(struct node)); p->num = x; p->next = head; head = p; } //　リストの要素のnumの値を先頭から順に表示する p=head; while(p!=NULL) { printf("%d\n" ,p->num); p = p->next; } } (2) struct node *q; q = head; while(q->next != NULL) q = q->next; (1)を(2)を使い新しいノードをリストの最後に追加するようにしたいのですが どう書いたら良いのか教えていただきたいです

  • Ｃ言語のリストのソートについて質問します。

    Ｃ言語のリストのソートについて質問します。 こんばんは、aida13です。以前の質問が自己解決しました。回答者のみなさん本当にすみませんでした。 今回はそのアルゴリズムで改善したい点がありましたので投稿させていただきました。以下のソートを実行するとソート自体はうまくいくのですが、見ての通りwhileやifなどを使って何度も実行しなおさないと完全にソートできません（「5 4 3 2 1」→「4 3 2 1 5」（一回ソート））。これを一回でソートできるようにしたいのです。また、降順も同様にそのままsecondとheadを入れ替えたのですが…今度は何度やっても「1 2 3 4 5」→「2 1 3 4 5」（一回ソート）からそれ以上動きません。アドバイスをお願いします。また、出来る限りこの形を保てる形でお願いします。 以下自作ソート #include < stdio.h > #include < stdlib.h > struct ans { int data; struct ans *next; }; struct ans *sort_up(struct ans *head) { int temp; struct ans *second_head; second_head = (struct ans *)malloc(sizeof(struct ans)); second_head = head->next; if( head->next == NULL ) { return head; } else { if( head->data > second_head->data ) { temp = head->data; head->data = second_head->data; second_head->data = temp; sort_up(head->next); } else { sort_up(head->next); } return head; } } struct ans *add_list(int x, struct ans *head) { struct ans *new_head; new_head = (struct ans *)malloc(sizeof(struct ans)); new_head->data = x; new_head->next = head; return new_head; } void show_list(struct ans *head) { if( head == NULL ) { printf("\n\n"); } else { printf("%d ",head->data); show_list(head->next); } } void main() { struct ans *head; head = NULL; head = add_list(1,head); head = add_list(2,head); head = add_list(3,head); head = add_list(4,head); head = add_list(5,head); do { printf("input:"); scanf("%d",&a); if(a==0) { head = sort_up(head); show_list(head); } } while(a==0); }

  • リスト構造のソートで悩んでます。。。

    リスト構造のソートで悩んでます。プログラムの内容はファイルからデータをリスト構造の構造体に読み込み、名前順にソートし結果を表示する。というものです。データの追加や削除はできるのですがソートとなると頭が混乱してしまいお手上げ状態になってしまいました。。。。。 読み込み用のデータとプログラムソースを以下に記載するのでどなたか良きアドバイスをお願いしますm(_ _)m ○データ Sakuragi 16 Rukawa 16 Miyagi 17 Akagi 18 Mitsui 18 ○ソース #include <stdio.h> #include <stdlib.h> #include <string.h> #define MENBER 5 typedef struct data{ char name[BUFSIZ]; int age; struct data *next; }LIST; LIST *newLIST(void); LIST *sort(LIST *); int main(int argc,char *argv[]){ FILE *fp; LIST *p; LIST *np; LIST *npb; LIST *head; char namae[BUFSIZ]; int toshi,i; if((fp=fopen(argv[1],"r"))==NULL){ printf("no file\n"); exit(1); } head = newLIST(); npb =head; for(i=0;i<MENBER;i++){ np = newLIST(); fscanf(fp,"%s %d",namae,&toshi); strcpy(np->name,namae); np->age = toshi; npb->next =np; npb = np; } sort(head); for(p=head->next;p != NULL;p=p->next){ printf("%s\t%d\n",p->name,p->age); } for(p=head->next;p != NULL;p=np){ np = p->next; free(p); } fclose(fp); return(0); } LIST *newLIST(){ LIST *p; p = (LIST *)malloc(sizeof(LIST)); p->next = NULL; return(p); } LIST *sort(LIST *head){ }

  • クイックソートの処理速度に関する実験 要素１万個、

    クイックソートの処理速度に関する実験 要素１万個、２万個、３万個の配列変数にランダムな値を代入し、・その後クイックソートで小さい順に並べ替える #include<stdio.h> #include<stdlib.h> #include<time.h> #define ASIZE 10000 #define RAND_SEED 0x1131000 void my_sort(int left, int right, int a[]); int main(void){ clock_t start, end; int i,a[ASIZE]; srand(RAND_SEED); for(i=0;i<ASIZE; i++){ a[i]=rand(); } start=clock(); my_sort(0, ASIZE-1, a); end=clock(); printf("%.3f秒でした" ,(end-start)/(double)CLOCKS_PER_SEC); getchar(); return 0; } void my_sort(int left, int right, int a[]){ ここに入れるプログラムがわかりません return; }

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する