Supercomputing Contest 2013/本選問題
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
]
since1995
開始行:
*宇宙の起源を探せ!(宇宙の起源探索問題) [#p582f346]
ビッグバン直後の宇宙の極々初期の状態変化を解明するG...
この計算をGPUを使って高速に解くことを今回の目標にしよう.
-&ref(kadai-130819pm.pdf,,ダウンロード用PDF);
*課題 [#qa520de3]
2次元の '''N''' × '''N''' の格子平面上に 3 色の粒子が各...
A群は初期の宇宙状態の候補である.一方,B群は約 '''T''' 時...
''注意!'' 粒子には色の違いはあるが同色の粒子は同一視さ...
**GK理論における粒子の動き [#z97bb4d2]
+時刻は整数で刻まれており,各粒子は毎時刻ごとに格子点...
+A群ならびにB群の宇宙状態では,1 つの格子点の上には高...
一般には 1 つの格子点の上に複数の粒子が存在する場合が...
&ref(fig1.png);&br;図1: 粒子の動き&br;&br;
+ある時刻 t において,1 つの格子点 (x, y) 上に粒子が複数...
''注意!'' この課題を通して,時刻tの粒子の %%%向き%%% とは...
+各粒子に対して,その直前や直後の時刻での粒子の位置は通...
この番号は粒子の速度(向き)を表わすときにも使う.「向き」は...
#ref(fig2.png,around)
c の座標を (x, y) とすると&br;
0 = (x−1, y+1), 1 = (x, y+1),&br;
2 = (x+1, y+1), 3 = (x+1, y),&br;
4 = (x+1, y−1), 5 = (x, y−1),&br;
6=(x−1,y−1), 7=(x−1,y)
#clear
図2: 相対位置
**1.パラメータの定義ならびにデータの入出力方法 [#t5...
入出力は規定のテンプレート sc13 template.c を用いること...
以下では,パラメータと用語の解説,入力データと出力テ...
***1.1. 用語,パラメータの説明(パラメータ名はそのまま...
:'''N'''| 宇宙の格子点座標の上限.座標 (x, y) の範囲は,{0,...
:'''M'''| 各色の粒子の個数.したがって,粒子の総数は 3'''...
:'''T'''| B群の宇宙状態までの経過時刻の概数.&br;
''注意!'' 実際の経過時刻は各宇宙状態ごとに (0.5'''T''',...
:'''K'''| A群の宇宙状態数.
:'''L'''| B群の宇宙状態数.
***1.2. 入出力と関連の変数 [#wb1d1638]
入力はテンプレート中の変更不可の部分で行われ,以下の変...
入出力用構造体
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] には...
なお,同色の粒子間には差が無い.したがって,1 つの宇宙状...
出力もテンプレート中の変更不可の部分で行われ,以下の変...
int answer[ MAXL ]; // 出力用
// answer[ i ] = B[ i ] の過去であるA群の宇宙状態イン...
答えは単純に,B群の各宇宙状態インデックスの順で,その状...
(補足:入力の仕様)以上のように,入出力はテンプレートで...
-1 行目に N, M, T, K, L が空白区切りで与えられる.
-それ以降の K*3*M 行にA群を表すデータが与えられる.B群...
-各 3*M 行で一つの宇宙状態を与える.各宇宙状態の各行で...
最初の M 行で色 0 の粒子,次の M 行で色 1 の粒子,最後...
-各粒子の状態は x y direction の形で与える.
***1.3. テンプレートにおけるその他の主要変数 [#o68f808b]
最も重要なのは衝突後の速度(向き)の変化「遷移ルール」を表...
struct TransitionRule{ // 遷移ルールを表現する構造体
int id; // 遷移ルールid. 0 から始まる.多分使うことはない
int length; // 衝突に関わる粒子数. length 番目以降のpat...
int pattern[8];// 衝突の直前時刻の各粒子の相対位置番号
int next[8]; // 衝突の直後時刻の各粒子の相対位置番号=衝...
};
int TRANSITION_RULES_NUM = 255; // 遷移ルールの総数
TransitionRule transition_rules[ 255 ]; // 遷移ルールの表
その他に以下のような変数も定数として定義されている.
#define MAXN 500 // 空間の最大サイズ
#define MAXM 4000 // 1色あたりの粒子の最大数 ( 粒子の最...
#define MAXT 5000 // 最大予測経過時間
#define MAXK 250 // A群の最大宇宙状態数
#define MAXL 100 // B群の最大宇宙状態数
**2.パラメータの範囲,審査方法 [#u0a34ef1]
審査では以下のようパラメータを用いる予定.プログラ...
N = 500 M = 4000 T = 5000
なお,初期宇宙状態の形はテスト用データとは異なるものを用...
***2.1. 審査方法について(あくまで予定です) [#b74f91e5]
審査は,提出されたプログラムに対して,第一次選抜を行い...
**3.プログラミングの注意 [#zb03d3cb]
+プログラミング言語は C 言語.プログラムは C 言...
+CPU並列化はしない.実行はTSUBAME1ノード上で行われる....
+今回は GPU 上の並列化をうまく利用するのが鍵となる.GPU ...
+データの読み込みと解答の出力には審査委員会で用意した...
+使用可能メモリサイズは CPU 側で約 48GB.その範囲内て...
+その他,補足の説明,コンテスト中の質問への回答,細かな注意...
終了行:
*宇宙の起源を探せ!(宇宙の起源探索問題) [#p582f346]
ビッグバン直後の宇宙の極々初期の状態変化を解明するG...
この計算をGPUを使って高速に解くことを今回の目標にしよう.
-&ref(kadai-130819pm.pdf,,ダウンロード用PDF);
*課題 [#qa520de3]
2次元の '''N''' × '''N''' の格子平面上に 3 色の粒子が各...
A群は初期の宇宙状態の候補である.一方,B群は約 '''T''' 時...
''注意!'' 粒子には色の違いはあるが同色の粒子は同一視さ...
**GK理論における粒子の動き [#z97bb4d2]
+時刻は整数で刻まれており,各粒子は毎時刻ごとに格子点...
+A群ならびにB群の宇宙状態では,1 つの格子点の上には高...
一般には 1 つの格子点の上に複数の粒子が存在する場合が...
&ref(fig1.png);&br;図1: 粒子の動き&br;&br;
+ある時刻 t において,1 つの格子点 (x, y) 上に粒子が複数...
''注意!'' この課題を通して,時刻tの粒子の %%%向き%%% とは...
+各粒子に対して,その直前や直後の時刻での粒子の位置は通...
この番号は粒子の速度(向き)を表わすときにも使う.「向き」は...
#ref(fig2.png,around)
c の座標を (x, y) とすると&br;
0 = (x−1, y+1), 1 = (x, y+1),&br;
2 = (x+1, y+1), 3 = (x+1, y),&br;
4 = (x+1, y−1), 5 = (x, y−1),&br;
6=(x−1,y−1), 7=(x−1,y)
#clear
図2: 相対位置
**1.パラメータの定義ならびにデータの入出力方法 [#t5...
入出力は規定のテンプレート sc13 template.c を用いること...
以下では,パラメータと用語の解説,入力データと出力テ...
***1.1. 用語,パラメータの説明(パラメータ名はそのまま...
:'''N'''| 宇宙の格子点座標の上限.座標 (x, y) の範囲は,{0,...
:'''M'''| 各色の粒子の個数.したがって,粒子の総数は 3'''...
:'''T'''| B群の宇宙状態までの経過時刻の概数.&br;
''注意!'' 実際の経過時刻は各宇宙状態ごとに (0.5'''T''',...
:'''K'''| A群の宇宙状態数.
:'''L'''| B群の宇宙状態数.
***1.2. 入出力と関連の変数 [#wb1d1638]
入力はテンプレート中の変更不可の部分で行われ,以下の変...
入出力用構造体
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] には...
なお,同色の粒子間には差が無い.したがって,1 つの宇宙状...
出力もテンプレート中の変更不可の部分で行われ,以下の変...
int answer[ MAXL ]; // 出力用
// answer[ i ] = B[ i ] の過去であるA群の宇宙状態イン...
答えは単純に,B群の各宇宙状態インデックスの順で,その状...
(補足:入力の仕様)以上のように,入出力はテンプレートで...
-1 行目に N, M, T, K, L が空白区切りで与えられる.
-それ以降の K*3*M 行にA群を表すデータが与えられる.B群...
-各 3*M 行で一つの宇宙状態を与える.各宇宙状態の各行で...
最初の M 行で色 0 の粒子,次の M 行で色 1 の粒子,最後...
-各粒子の状態は x y direction の形で与える.
***1.3. テンプレートにおけるその他の主要変数 [#o68f808b]
最も重要なのは衝突後の速度(向き)の変化「遷移ルール」を表...
struct TransitionRule{ // 遷移ルールを表現する構造体
int id; // 遷移ルールid. 0 から始まる.多分使うことはない
int length; // 衝突に関わる粒子数. length 番目以降のpat...
int pattern[8];// 衝突の直前時刻の各粒子の相対位置番号
int next[8]; // 衝突の直後時刻の各粒子の相対位置番号=衝...
};
int TRANSITION_RULES_NUM = 255; // 遷移ルールの総数
TransitionRule transition_rules[ 255 ]; // 遷移ルールの表
その他に以下のような変数も定数として定義されている.
#define MAXN 500 // 空間の最大サイズ
#define MAXM 4000 // 1色あたりの粒子の最大数 ( 粒子の最...
#define MAXT 5000 // 最大予測経過時間
#define MAXK 250 // A群の最大宇宙状態数
#define MAXL 100 // B群の最大宇宙状態数
**2.パラメータの範囲,審査方法 [#u0a34ef1]
審査では以下のようパラメータを用いる予定.プログラ...
N = 500 M = 4000 T = 5000
なお,初期宇宙状態の形はテスト用データとは異なるものを用...
***2.1. 審査方法について(あくまで予定です) [#b74f91e5]
審査は,提出されたプログラムに対して,第一次選抜を行い...
**3.プログラミングの注意 [#zb03d3cb]
+プログラミング言語は C 言語.プログラムは C 言...
+CPU並列化はしない.実行はTSUBAME1ノード上で行われる....
+今回は GPU 上の並列化をうまく利用するのが鍵となる.GPU ...
+データの読み込みと解答の出力には審査委員会で用意した...
+使用可能メモリサイズは CPU 側で約 48GB.その範囲内て...
+その他,補足の説明,コンテスト中の質問への回答,細かな注意...
ページ名: