東京大学大学院 情報理工学系研究科 コンピュータ科学専攻 金田研究室 工藤 誠

Presentation on theme: "東京大学大学院 情報理工学系研究科 コンピュータ科学専攻 金田研究室 工藤 誠"— Presentation transcript:

1 東京大学大学院 情報理工学系研究科 コンピュータ科学専攻 金田研究室 工藤 誠
3機種優勝への道 ～遥かなるPSC～ 東京大学大学院 情報理工学系研究科 コンピュータ科学専攻 金田研究室 工藤 誠

2 自己紹介と参加の動機(1) 東京大学大学院 情報理工学系研究科 コンピュータ科学専攻（旧理学系研究科 情報科学専攻） 金田研究室所属(情報基盤センター スーパーコンピューティング部門) PSCは初出場 金田研究室では、大学院生はPSCに参加するというのが恒例 3月の申し込み期間の時点で参加可能な大学院生は一人 当然、PSC2001に参加する

3 PSCには当然参加する、かつ上位入賞しなければならない
自己紹介と参加の動機(2) 毎年、金田研ではPSC参加者は上位入賞を果たしてきた 年 優勝 2位 3位 1995 黒田(SR2201) 高橋(SP-2) 1996 高橋(IBM,日立) 富松、黒田、渡辺(IBM,日立) 富松、黒田、渡辺(富士通) 1997 名取(AP3000,SR2201) 名取(Cenju-3)、片桐(SR2201) 片桐(AP3000) 1998 黒田(Cenju-3) 黒田(AP-3000,SR-2201) 片桐(Cenju-3)、黒田(SUN E10000) 1999 2000 大澤(SR2201) PSCには当然参加する、かつ上位入賞しなければならない

4 問題説明(1) 3次元空間中のn個の粒子P(0)…P(n-1)の質量、初期速度、位置が与えられる これら粒子が相互に力を及ぼしあう
微小時間後の粒子の位置を計算するという処理を繰り返す 最終的に、T step後の粒子の位置を求める

5 問題説明(2) 粒子P(j)が粒子P(i)に及ぼす力によって生じるP(i)の加速度A(i) f(X)、r(i,j)は以下のように与えられる
ここで、roundとは小数点以下を四捨五入する関数 微小時間dt後の位置p(t)と速度v(t)の更新

6 アルゴリズム概要(1) do i=1,N do j=1,N calculate X 粒子間の距離 if(X < 1024)
すべての粒子の、すべての粒子に対して及ぼす力を計算するようなナイーブなアルゴリズム do i=1,N do j=1,N calculate X if(X < 1024) calculate a end do 粒子間の距離 加速度 すべての粒子間の距離を計算 非効率！

7 アルゴリズムの概要(2) 距離計算の回数を減らしたい 今回の問題にはカットオフが設定されている
領域全体を小さな直方体（セル）に分割し、セル同士の 距離を計算しカットオフを考慮することで、総計算回数を減らす

8 セル分けによる計算量の削減 カットオフ距離よりも 近いので計算する カットオフ距離よりも遠いので計算しない

9 セルのプロセッサへの割り当て セル分けは、領域を３次元的に分割する 領域をz軸方向に分割した柱状の領域を各PEに割り当てる

10 セル分割の方法 セル分割の方法は、プロセッサ間のロードバランスに影響する 領域を分割する３つの方針 等間隔分割 粒子数一定に分割
距離計算数を一定に分割 このどちらかを採用

11 セルの領域からはみ出る粒子も出てくるが、
セル分けの頻度 セル分けは逐次処理なので、時間がかかる 毎stepセル分けしなくても、計算量、ロードバランスはそれほど悪くならない セル分けは10stepに一度行う セルの領域からはみ出る粒子も出てくるが、 セルの境界をずらすことで対応した

12 AutoTuning機構 セルの個数 xyz各方向の分割数 最適値は、粒子の個数、分散形状によって違う
実行時に、動的にこれらのパラメータを決定する AutoTuning機構をつけた 実行時になってみないと、最適なパラメータは わからない！ 200stepに一度パラメータを再設定

13 距離計算の回数を約半分におさえることができる
相互作用の対称性 粒子iと粒子jが相互に及ぼす加速度ai,aj 位置の差のベクトル 質量 (1)式と(2)式には対称性がある 2粒子間の距離やr(i,j)を使い回すことができる。 距離計算の回数を約半分におさえることができる

14 実装上の工夫(1) round処理の高速化 大会側から与えられたround処理は、非常に遅い
IEEE表現のdoubleの上位18ビットがインデックスとなる 配列を用意すれば、round処理は配列参照のみでできる 指数部 仮数部 bit 1 2 8 色のついた部分を配列のインデックスとする 配列のサイズは、double型262144個分 double round(double x){ if ( x < 0.0 ) return -floor(-x+0.5); else return floor(x+0.5); } 大会側から与えられたround #define myround(x) rbuf[*((unsigned int *)&(x)) >> 14] 自作round

15 実装上の工夫(2) Barrier同期（共有メモリマシン用）
システムコール(semaphore等)や既存のライブラリ関数(mutex_*,cond_*)を使うのは、非常に遅い ビジーウェイトで同期を取る自前のBarrier同期を作成した

16 プログラムの特徴 分散メモリマシン用 (Scoreクラスタ) 共有メモリマシン用 (SGI,SUN) 実装方式 MPI マルチプロセス
通信、共有データ 粒子の位置 セルの境界座標 各stepで計算した加速度 相互作用の対称性の利用 自PEが担当する粒子同士の力の計算のみ すべての粒子同士の力の計算

17 実行結果(1) SUNの提出プログラム コンテストマシン 17.58 53.45 15.03 43.07 73.08 169.80
予選問題(秒) (20,000粒子,250step) 本選問題(秒) (40,000粒子,500step) Scoreクラスタ (32PE使用) 17.58 53.45 SGI Origin2000 15.03 43.07 SUN Enterprise10000 (60PE使用） 73.08 169.80 (38.91) (103.04) SUNの提出プログラム 共有メモリマシン用のプログラムは、主にSGI上で開発 最終日にSUNが非常に混んでいたので、SUN用のチューニングができなかった 結局、SGIと同じパラメータで提出した

18 １ノードが８プロセッサから成る、共有分散メモリマシン
実行結果(2) HITACHI SR8000/MPP １ノードが８プロセッサから成る、共有分散メモリマシン 1.6GByte/s(単方向)X2 16GByte 1.8GFlops(450MHz) Communication Memory(1ノード) プロセッサ プロセッサ台数 ピーク性能 (GFLOPS) 予選(秒) (20,000粒子,250step) 本選(秒) (40,000粒子,500step) 8 14.4 73.5 (4X2X20) 163 (4X2X40) 16 28.8 38.5 (4X4X15) 83.5 (4X4X25) 32 57.6 16.7 (8X4X10) 40.6 (4X8X15) 64 115.2 9.57 (8X8X10) 21.1 (8X8X10) 128 230.4 5.98 (16X8X5) 12.4 (16X8X10) 256 460.8 4.51 (16X16X5) 10.4 (16X16X10)

19 作業日程 逐次版の３次元セル分けプログラムを作る。 研究室のPCクラスタ上でMPI版のセル分け低速プログラム完成。 ○
月日 作業 計算機使用 Score SGI SUN ～4月4日 逐次版の３次元セル分けプログラムを作る。 ～4月9日 研究室のPCクラスタ上でMPI版のセル分け低速プログラム完成。 ～4月12日 MPI版のプログラムが大分速くなる。 スレッドプログラムを作成。 roundの高速化を思いつく。 ○ ～4月18日 スレッド版がほぼ完成。Scoreクラスタを使い始める。 ～4月20日 MPI版ほぼ完成。 プロセス版のプログラムを作成開始（SystemV IPC shared memoryの勉強を始める）。共有メモリ用プログラムの開発はSGIに変更。 ～4月23日 プロセス版ほぼ完成。 スレッド版より速いことを確認し、共有メモリマシンにプロセス版プログラムを採用する。 ～4月26日 研究室に泊り込んで最後の追い込み。 Auto Tuning機能をつける。 Loop unrolling等の実装上の工夫でさらに高速化を狙う。 ～4月27日 体調をくずし、家で作業。最後のチューニングをし、27日朝9時頃にプログラム提出。 ×

20 TODO セルのPEへの割り当て方向を可変に 位置、速度配列への直接参照
提出プログラムでは、z軸方向に分割した柱状の領域を各PEに割り当てる 粒子の分散形状によっては、x軸方向、y軸方向に分割したほうがよい場合もある 位置、速度配列への直接参照 位置、速度情報の配列のデータは終始並び替えをしない セル情報からこれら配列へのアクセスは間接参照 直接参照になるようにデータの並び替えを行うと高速化の可能性あり