3機種優勝への道
～遥かなるPSC～
東京大学大学院
情報理工学系研究科 コンピュータ科学専攻
金田研究室
工藤 誠
自己紹介と参加の動機(1)
• 東京大学大学院 情報理工学系研究科
コンピュータ科学専攻（旧理学系研究科 情報科学専攻）
金田研究室所属(情報基盤センター スーパーコンピューティング部門)
• PSCは初出場
• 金田研究室では、大学院生はPSCに参加するというのが恒例
• 3月の申し込み期間の時点で参加可能な大学院生は一人
当然、PSC2001に参加する
自己紹介と参加の動機(2)
• 毎年、金田研ではPSC参加者は上位入賞を果たしてきた
年
優勝
2位
3位
1995
黒田(SR2201)
高橋(SP-2)
1996
高橋(IBM,日立)
富松、黒田、渡辺(IBM,日
富松、黒田、渡辺
立)
(富士通)
1997
名取
名取(Cenju-3)、片桐(SR2201) 片桐(AP3000)
(AP3000,SR2201)
1998
黒田(Cenju-3)
黒田(AP-3000,SR-2201)
片桐(Cenju-3)、黒田
(SUN E10000)
1999
2000
大澤(SR2201)
PSCには当然参加する、かつ上位入賞しなければならない
問題説明(1)
• 3次元空間中のn個の粒子P(0)…P(n-1)の質量、初期速度、位
置が与えられる
• これら粒子が相互に力を及ぼしあう
• 微小時間後の粒子の位置を計算するという処理を繰り返す
• 最終的に、T step後の粒子の位置を求める
問題説明(2)
• 粒子P(j)が粒子P(i)に及ぼす力によって生じるP(i)の加速度
A(i)
Ai
a i , j
ji
a i , j m j f r i , j
2
r i , j
• f(X)、r(i,j)は以下のように与えられる
f X X 256 X 1024
f X 0
X 1024
X 1024
r i , j round x i x j , round y i y j , round z i z j
• ここで、roundとは小数点以下を四捨五入する関数
• 微小時間dt後の位置p(t)と速度v(t)の更新
pt 1 pt v t dt
v t 1 v t At dt
アルゴリズム概要(1)
すべての粒子の、すべての粒子に対して及ぼす力を計算するようなナ
イーブなアルゴリズム
do i=1,N
do j=1,N
calculate X
if(X < 1024)
calculate a
end do
end do
粒子間の距離
加速度
すべての粒子間の距離を計算
非効率！
アルゴリズムの概要(2)
• 距離計算の回数を減らしたい
• 今回の問題にはカットオフが設定されている
領域全体を小さな直方体（セル）に分割し、セル同士の
距離を計算しカットオフを考慮することで、総計算回数を減らす
セル分けによる計算量の削減
カットオフ距離よりも
近いので計算する
カットオフ距離よりも
遠いので計算しない
セルのプロセッサへの割り当て
• セル分けは、領域を３次元的に分割する
• 領域をz軸方向に分割した柱状の領域を各PEに割り当てる
セル分割の方法
•
セル分割の方法は、プロセッサ間のロードバランスに影響する
•
領域を分割する３つの方針
1. 等間隔分割
2. 粒子数一定に分割
3. 距離計算数を一定に分割
このどちらかを採用
セル分けの頻度
• セル分けは逐次処理なので、時間がかかる
• 毎stepセル分けしなくても、計算量、ロードバラン
スはそれほど悪くならない
セル分けは10stepに一度行う
セルの領域からはみ出る粒子も出てくるが、
セルの境界をずらすことで対応した
AutoTuning機構
セルの個数
xyz各方向の分割数
最適値は、粒子の個数、分散形状によって違う
実行時になってみないと、最
適なパラメータは
わからない！
実行時に、動的にこれらのパラメータを決定する
AutoTuning機構をつけた
200stepに一度パラメータを再設定
相互作用の対称性
粒子iと粒子jが相互に及ぼす加速度ai,aj
位置の差のベクトル
質量
a i m j f r (i , j ) r i , j
1
a j m i f r ( j , i ) r j , i 2
r i , j r j , i
(1)式と(2)式には対称性がある
2粒子間の距離やr(i,j)を使い回すことができる。
距離計算の回数を約半分におさえることができる
実装上の工夫(1)
• round処理の高速化
– 大会側から与えられたround処理は、非常に遅い
– roundの引数は、-32.0～32.0と、範囲が決まっている
IEEE表現のdoubleの上位18ビットがインデックスとなる
配列を用意すれば、round処理は配列参照のみでできる
指数部
bit 0
仮数部
1112
18
色のついた部分を配列のインデックスとする
配列のサイズは、double型262144個分
大会側から与え
られたround
自作round
double round(double x){
if ( x < 0.0 ) return -floor(-x+0.5);
else return floor(x+0.5); }
#define myround(x) rbuf[*((unsigned int *)&(x)) >> 14]
実装上の工夫(2)
• Barrier同期（共有メモリマシン用）
– システムコール(semaphore等)や既存のライブラリ関数
(mutex_*,cond_*)を使うのは、非常に遅い
– ビジーウェイトで同期を取る自前のBarrier同期を作成
した
プログラムの特徴
分散メモリマシン用 共有メモリマシン用
(Scoreクラスタ)
(SGI,SUN)
実装方式
MPI
マルチプロセス
通信、共有データ
粒子の位置
セルの境界座標
各stepで計算した加
速度
相互作用の対称性
の利用
自PEが担当する粒子 すべての粒子同士の
同士の力の計算のみ 力の計算
実行結果(1)
コンテストマシン
予選問題(秒)
(20,000粒子,250step)
本選問題(秒)
(40,000粒子,500step)
Scoreクラスタ
(32PE使用)
17.58
53.45
SGI Origin2000
(32PE使用)
15.03
43.07
73.08
(38.91)
169.80
(103.04)
SUN Enterprise10000
(60PE使用）
SUNの提出プログラム
• 共有メモリマシン用のプログラムは、主にSGI上で開発
• 最終日にSUNが非常に混んでいたので、SUN用のチューニ
ングができなかった
• 結局、SGIと同じパラメータで提出した
実行結果(2)
HITACHI SR8000/MPP
１ノードが８プロセッサから成る、共有分散メモリマシン
プロセッサ
Memory(1ノード)
Communication
1.8GFlops(450MHz)
16GByte
1.6GByte/s(単方向)X2
プロセッサ台数
ピーク性能
(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)
作業日程
月日
作業
計算機使用
Score
SGI
～4月4日
逐次版の３次元セル分けプログラムを作る。
～4月9日
研究室のPCクラスタ上でMPI版のセル分け低速プログ
ラム完成。
～4月12日
MPI版のプログラムが大分速くなる。 スレッドプロ
グラムを作成。 roundの高速化を思いつく。
～4月18日
スレッド版がほぼ完成。Scoreクラスタを使い始める。
○
～4月20日
MPI版ほぼ完成。 プロセス版のプログラムを作成開
始（SystemV IPC shared memoryの勉強を始める）。
共有メモリ用プログラムの開発はSGIに変更。
○
○
プロセス版ほぼ完成。 スレッド版より速いことを確
認し、共有メモリマシンにプロセス版プログラムを採
用する。
○
○
研究室に泊り込んで最後の追い込み。 Auto Tuning
機能をつける。 Loop unrolling等の実装上の工夫で
さらに高速化を狙う。
○
○
体調をくずし、家で作業。最後のチューニングをし、
27日朝9時頃にプログラム提出。
○
○
～4月23日
～4月26日
～4月27日
SUN
○
○
○
×
TODO
• セルのPEへの割り当て方向を可変に
– 提出プログラムでは、z軸方向に分割した柱状の
領域を各PEに割り当てる
– 粒子の分散形状によっては、x軸方向、y軸方向に
分割したほうがよい場合もある
• 位置、速度配列への直接参照
– 位置、速度情報の配列のデータは終始並び替えを
しない
– セル情報からこれら配列へのアクセスは間接参照
– 直接参照になるようにデータの並び替えを行うと
高速化の可能性あり
© Copyright 2024 ExpyDoc
