Supercomputing Contest 2013/本選問題

宇宙の起源を探せ!(宇宙の起源探索問題) †

ビッグバン直後の宇宙の極々初期の状態変化を解明するGK理論がスーパーコン研究所の菊池・権藤両博士によって提唱された.一方,ビッグバン直後の粒子*1 の状況については,遠藤博士が提唱した理論により, K 種類のパターンしかないことがわかっている.さらに遠藤博士の調査により,宇宙がある程度進化した時刻(仮に T 時刻と呼ぶ)の粒子の分布状況については, L 種類( L は K に比べてかなり小さい)の候補に絞られることを突き止めた.この新たな調査結果を用い,GK理論で時刻をさかのぼり,宇宙の初期状態の候補を K 種類から L 種類に絞り込みたい.

この計算をGPUを使って高速に解くことを今回の目標にしよう.

• ダウンロード用PDF

課題 †

2次元の N × N の格子平面上に 3 色の粒子が各々 M 個存在し,各々が一定の速さ(向きは異なる)で,ある法則に従って移動する宇宙モデルを考える.入力としては,A群と呼ばれる K 個の宇宙状態の集合とB群と呼ばれる L 個の宇宙状態の集合が与えられる.ここで, 宇宙状態 とは,その宇宙における全粒子の 状態 (=粒子の位置と速度(向き))の全体のことである.

A群は初期の宇宙状態の候補である.一方,B群は約 T 時刻後の可能な宇宙状態として遠藤博士が絞り込んだ宇宙状態の集合である.これらの入力に対して,B群の各状態に対応する初期の宇宙状態をA群の中から選び出せ.
注意! 粒子には色の違いはあるが同色の粒子は同一視される.

GK理論における粒子の動き †

1. 時刻は整数で刻まれており,各粒子は毎時刻ごとに格子点の上からその隣の格子点に移動する (止まっている粒子はいない).なお,格子点 (x,y) の隣とは,(x,y±1), (x±1,y), (x±1,y±1) の 8 通りの格子点のこと.また,宇宙はドーナツ状(トーラスという)で,座標 N は座標 0に戻ってくるものとする.
   
   
2. A群ならびにB群の宇宙状態では,1 つの格子点の上には高々 1 つの粒子しか存在しないが, 一般には 1 つの格子点の上に複数の粒子が存在する場合がある.これは直観的には粒子が衝 突した状況を表わしている.
   
   
   図1: 粒子の動き
   
   
3. ある時刻 t において,1 つの格子点 (x, y) 上に粒子が複数いたとする.その場合には,その 各粒子は時刻 t − 1 の時点で (x, y) の隣の格子点にいるはず.その各粒子の位置が時刻 t + 1 の各粒子の位置を決める(詳細は付録の表参照).たとえば,粒子は図 1 のように動く.図に おける矢印は各時刻での粒子の速度(動く向き)を表わしている.
   注意! この課題を通して,時刻tの粒子の 向き とは次に進むべき向きのこととする.つまり,時刻 t で衝突していた場合には,衝突後の向きが時刻 t の向きである.
   
   
4. 各粒子に対して,その直前や直後の時刻での粒子の位置は通常,相対位置を表わす 0 〜 7 の 数字で表わされる.これを 相対位置番号 と呼ぶ.つまり,図 2 のように,今考えている粒子を中心 c に,その隣の格子点の位置を 0 〜 7 で表わす.
   この番号は粒子の速度(向き)を表わすときにも使う.「向き」は次に進む方向なので,次 の場所を表わす相対位置番号を向きと見なすのである.
   
   
   
   c の座標を (x, y) とすると
   0 = (x−1, y+1), 1 = (x, y+1),
   2 = (x+1, y+1), 3 = (x+1, y),
   4 = (x+1, y−1), 5 = (x, y−1),
   6=(x−1,y−1), 7=(x−1,y)
   図2: 相対位置

1.パラメータの定義ならびにデータの入出力方法 †

入出力は規定のテンプレート sc13 template.c を用いること(コンパイルにはヘッダーファイル transition rule.h も必要).それに従うと標準入出力を使ってデータのやり取りが行われる.
以下では,パラメータと用語の解説,入力データと出力データの意味,テンプレートで用いられる変数の意味をそれぞれ述べる.

1.1. 用語,パラメータの説明(パラメータ名はそのまま変数名としてテンプレートでも使用) †

N

宇宙の格子点座標の上限.座標 (x, y) の範囲は,{0, . . . , N − 1} とする.

M

各色の粒子の個数.したがって,粒子の総数は 3M 個.

T

B群の宇宙状態までの経過時刻の概数.
注意! 実際の経過時刻は各宇宙状態ごとに (0.5T,1.5T) の範囲で異なる.

K

A群の宇宙状態数.

L

B群の宇宙状態数.

1.2. 入出力と関連の変数 †

入力はテンプレート中の変更不可の部分で行われ,以下の変数に必要なデータが得られる.

	入出力用構造体
	
	typedef struct Star_{ // 粒子の状態情報のための構造体
		int x; // x 座標
		int y; // y 座標
		int dir; // 速度=向き=次時刻の位置(相対位置番号)
		int color; // 色
	} Star;
	Star A[ MAXK ][ 3 * MAXM ]; // A群を表すデータ
	Star B[ MAXL ][ 3 * MAXM ]; // B群を表すデータ

つまり,各 i, 0 ≤ i ≤ K − 1, に対して,配列 A[i] にはA群 i 番目の宇宙状態の情報が格納される(なお,i をA群の 宇宙状態インデックス と呼ぶことにする).より具体的には,A[i][0 〜 M − 1]には,その宇宙状態の 0 色粒子の状態(位置と向き)が,A[i][M 〜 2M − 1] には 1 色粒子の状態が,A[i][2M 〜 3M − 1] には 2 色粒子の状態が,各々与えられる.
なお,同色の粒子間には差が無い.したがって,1 つの宇宙状態を表わす配列 A[i] 内(同様に配列 B[j] 内)の同色の粒子の順番には意味がない.
出力もテンプレート中の変更不可の部分で行われ,以下の変数に得られた答えが出力される.

	int answer[ MAXL ]; // 出力用
	// answer[ i ] = B[ i ] の過去であるA群の宇宙状態インデックス

答えは単純に,B群の各宇宙状態インデックスの順で,その状態の過去に当たるA郡の宇宙状態インデックスを空白区切りで出力する.&brl (補足:入力の仕様)以上のように,入出力はテンプレートで行うので,具体的に入力としてデータを与える方法については,とくに詳細を知る必要はないかもしれないが,参考のため以下に簡 単に紹介しておく.

• 1 行目に N, M, T, K, L が空白区切りで与えられる.
• それ以降の K*3*M 行にA群を表すデータが与えられる.B群も同様.
• 各 3*M 行で一つの宇宙状態を与える.各宇宙状態の各行では,各粒子の状態を与える:
  最初の M 行で色 0 の粒子,次の M 行で色 1 の粒子,最後の M 行で色 2 の粒子の 位置と速度(向き=相対位置番号)を与える.
• 各粒子の状態は x y direction の形で与える.

1.3. テンプレートにおけるその他の主要変数 †

最も重要なのは衝突後の速度(向き)の変化「遷移ルール」を表わす表だろう.これは transition rule.hというヘッダーファイルで,次のように与えらえる.

	struct TransitionRule{ // 遷移ルールを表現する構造体
		int id; // 遷移ルールid. 0 から始まる.多分使うことはない
		int length; // 衝突に関わる粒子数. length 番目以降のpattern, nextは未定義
		int pattern[8];// 衝突の直前時刻の各粒子の相対位置番号
		int next[8]; // 衝突の直後時刻の各粒子の相対位置番号=衝突時刻の粒子の向き
	};
	int TRANSITION_RULES_NUM = 255; // 遷移ルールの総数
	TransitionRule transition_rules[ 255 ]; // 遷移ルールの表

その他に以下のような変数も定数として定義されている.

	#define MAXN 500 // 空間の最大サイズ
	#define MAXM 4000 // 1色あたりの粒子の最大数 ( 粒子の最大数は 3 * MAXM )
	#define MAXT 5000 // 最大予測経過時間
	#define MAXK 250 // A群の最大宇宙状態数
	#define MAXL 100 // B群の最大宇宙状態数

2.パラメータの範囲,審査方法 †

審査では以下のようパラメータを用いる予定.プログラミングの際に用いるテスト用データも,このサイズのものを用意しておくが,最初のうちは小さいサイズで実験することをお勧めする.

	N = 500     M = 4000    T = 5000

なお,初期宇宙状態の形はテスト用データとは異なるものを用いる予定.

2.1. 審査方法について(あくまで予定です) †

審査は,提出されたプログラムに対して,第一次選抜を行いチーム数を少し絞った後で,最終審査を行う.第一次選抜では K = 25, L = 10 程度の宇宙状態数のデータを用いる.一方,最終審査では K = 250, L = 100 程度の宇宙状態数のデータを用いる.

3.プログラミングの注意 †

1. プログラミング言語は C 言語.プログラムは C 言語規格(ANSI C や C99 など)に準拠する C 言語で書くこと.GCC や Visual C++ などに特有の仕様は,スーパーコンピュータ TSUBAME2.0 では使えない可能性が高い.PC でコンパイルできたものが TSUBAME 上でコンパイルできるとは限らないことに注意.
   
   
2. CPU並列化はしない.実行はTSUBAME1ノード上で行われる.その上には複数コア,複数 GPU が割り当てられているが,プログラム上で使ってよいのは 1CPU コア,1GPU のみとする.(CPU の)pthread や MPI による並列化は禁止とする.(厳密には,CUDA が内部的に pthread を用いる可能性があるが,それは違反とはしない.)
   
   
3. 今回は GPU 上の並列化をうまく利用するのが鍵となる.GPU に関する配布資料や講習などを参考にして欲しい.
   
   
4. データの読み込みと解答の出力には審査委員会で用意したテンプレート sc13 template.c を使う.テンプレートの限られた部分のみを書き換えてプログラミングすること.
   
   
5. 使用可能メモリサイズは CPU 側で約 48GB.その範囲内であれば,ひとつの配列として取れるサイズに上限はない.いっぽう,GPU 側での使用可能メモリサイズは約 2.5GB.これを超えるデータを扱う場合には,GPU 上の同じメモリ領域を使いまわす等の工夫が必要となる.
   
   
6. その他,補足の説明,コンテスト中の質問への回答,細かな注意などは,コンテスト Wiki に掲載するので参照すること.