MatsuLab. Lecture Note/sougouenshu2007/round2/2

MatsuLab. Lecture Note/sougouenshu2007/round2

第２回 †

前回の課題の報告 †

問題 †

問題として与えられる無向グラフG(V, E)中のノード(偶数個)を2つのノード集合LおよびRに等分する分割方法を求める。ただし、

• 分割後に生成されるノード集合LおよびRに続するノード数は同じでなければならない。
• 異なるノード集合にまたがるエッジ数がより少ない分割方法を良い解と定義する。
  
• MPIを利用して、限られた時間で、なるべく良い解を得られるようなプログラムを作成する。
  

問題として与えられるグラフ情報は以下のように与えられる。

ノードID (X座標, Y座標) 隣接するノード数　隣接するノードID...

• ノードID: ノードの識別子で、データファイル内では１から始まり、１ずつ増えていく。
• (X座標,Y座標): ２次元空間内におけるノードの位置を表す。
• 隣接するノード数: ノードからエッジによって結ばれているノードの個数。どのノードとも結ばれていない場合,0となる。
• 隣接するノードID: 隣接する各ノードのノードID。隣接するノード数に依存するため、可変個となる。

出典 : Grid Challenge 2006

注意 †

• 問題を解く際に利用するライブラリ(問題取得と回答のために用いる)と上記の問題を逐次プログラムで解いたものを配布するので、利用するとよい。。
• 逐次プログラムは、下記の論文を参考にして、作られている。一読のこと。
  

  K. Fujisawa, M. Kubo and S. Morito,
  ``Experimental Analyses of the Tabu Search for the Graph Partitioning Problem(in Japanese),''
  The Institute of Electrical Engineers of Japan, Vol 114-C(4), 1994, 430--437.

• 詳細はGrid Challenge 2006 で。

配布ライブラリの簡単な解説 †

コンパイル・リンクの方法 †

• 逐次版の場合

  gcc -I/path/to/header -L/path/to/library -o userprog userprog.c -lgrch -lcrypto

• MPIの場合

  mpicc -I/path/to/header -L/path/to/library -o userprog userprog.c -lgrch -lcrypto

問題取得用API †

• 書式
  

  int GetProblem(const int problem_number, char **filename, char *key);

• 概要
  プログラムは開始時にGetProblem?()を呼ぶことにより，データファイルの場所とキー文字列を取得する必要がある．
  全プロセスを通して一つのプロセスのみがGetProblem?()を呼ぶこと.
  
• 引数と戻り値
  
  • problem_number : 問題番号を指定する．
  • filename : データファイルの場所を示す文字列へのポインタが*filenameに返される．
  • key : キー文字列がkeyから始まる領域に返される．
  • return value : 正常に終了した場合は0，そうでない場合は1が返される．

解答用API †

• 書式
  

  int AnswerProblem(const int problem_number, const char *key, const int *belong_to, int *out_edge_cnt, double *elapsed_time, char *check_string);

• 概要
  プログラムは計算結果を引数としてAnswerProblem?()に渡し，解答に関する情報(集合間の枝の本数，経過時間，終了時刻，解答チェック用文字列)を取得する． GetProblem?()を呼び出したプロセスのみがAnswerProblem?()を呼び出すことができる．
• 引数と戻り値
  
  • problem_number: 問題番号を指定する．
  • key: キー文字列へのポインタを指定する．
  • belong_to: グラフ内のノードの所属情報を指定する．例えばノード数が500の場合，配列 belong_to[1]〜[500] に所属する集合(1または2)を格納する．インデックスが1から始まることに注意．
  • out_edge_cnt: 引数として渡された配列 belong_to を用いてAnswerProblem?()が計算した集合間の枝の本数へのポインタが返される．
  • elapsed_time: GetProblem?() 呼び出し以降の経過時間(ミリ秒単位)へのポインタが返される．
  • check_string: 解答チェック用文字列がcheck_stringから始まる領域に返される．
  • return value: 正常に終了した場合は0，そうでない場合は1が返される．

経過時間取得用API †

• 書式
  

  int GetElapsedTime(const int problem_number, const char *key, double *elapsed_time);

• 概要
  GetProblem?()呼び出しからの経過時間を取得する．
• 引数と戻り値
  
  • problem_number: 問題番号を指定する．
  • key: キー文字列へのポインタを指定する．
  • elapsed_time: GetProblem?()呼び出し以降の経過時間(ミリ秒単位)へのポインタが返される．
  • return value: 正常に終了した場合は0，そうでない場合は1が返される．

課題 †

上記の問題に取り組む。どんどん進めてもらってかまわない。

• ヒント
  • まず、配布プログラム、配布ライブラリを実行してみたり、配布資料を読むところから始めると良い。