宇宙の起源を探せ!(宇宙の起源探索問題) †ビッグバン直後の宇宙の極々初期の状態変化を解明するGK理論がスーパーコン研究所の菊池・権藤両博士によって提唱された.一方,ビッグバン直後の粒子*1 の状況については,遠藤博士が提唱した理論により, K 種類のパターンしかないことがわかっている.さらに遠藤博士の調査により,宇宙がある程度進化した時刻(仮に T 時刻と呼ぶ)の粒子の分布状況については, L 種類( L は K に比べてかなり小さい)の候補に絞られることを突き止めた.この新たな調査結果を用い,GK理論で時刻をさかのぼり,宇宙の初期状態の候補を K 種類から L 種類に絞り込みたい. この計算をGPUを使って高速に解くことを今回の目標にしよう. 課題 †2次元の N × N の格子平面上に 3 色の粒子が各々 M 個存在し,各々が一定の速さ(向きは異なる)で,ある法則に従って移動する宇宙モデルを考える.入力としては,A群と呼ばれる K 個の宇宙状態の集合とB群と呼ばれる L 個の宇宙状態の集合が与えられる.ここで, 宇宙状態 とは,その宇宙における全粒子の 状態 (=粒子の位置と速度(向き))の全体のことである. A群は初期の宇宙状態の候補である.一方,B群は約 T 時刻後の可能な宇宙状態として遠藤博士が絞り込んだ宇宙状態の集合である.これらの入力に対して,B群の各状態に対応する初期の宇宙状態をA群の中から選び出せ. GK理論における粒子の動き †
1.パラメータの定義ならびにデータの入出力方法 †入出力は規定のテンプレート sc13 template.c を用いること(コンパイルにはヘッダーファイル transition rule.h も必要).それに従うと標準入出力を使ってデータのやり取りが行われる. 1.1. 用語,パラメータの説明(パラメータ名はそのまま変数名としてテンプレートでも使用) †
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 色粒子の状態が,各々与えられる. int answer[ MAXL ]; // 出力用 // answer[ i ] = B[ i ] の過去であるA群の宇宙状態インデックス 答えは単純に,B群の各宇宙状態インデックスの順で,その状態の過去に当たるA郡の宇宙状態インデックスを空白区切りで出力する.&brl (補足:入力の仕様)以上のように,入出力はテンプレートで行うので,具体的に入力としてデータを与える方法については,とくに詳細を知る必要はないかもしれないが,参考のため以下に簡 単に紹介しておく.
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.プログラミングの注意 †
|