卒業論文中間発表
2004/11/10
上田研究室 描画班 B4
飛田伸一
資料の置き場
• 描画班のページ
(http://www.ueda.info.waseda.ac.jp/~wakat
suki/pukiwiki/pukiwiki.php)
発表の流れ
•
•
•
•
研究の目的
今までやったこと
研究内容
これからの課題
研究の目的
• 多体問題という問題がある。これはシミュレーション
において、物体の数が増えると、それに伴い計算量
が爆発的に増大するという問題である。HCCでもこ
の問題が発生する
• 現在、Grifonではビリヤードの問題を描画すること
が出来る。ここで、ビリヤードの玉の数を増やして
いった場合、計算量の爆発という問題が出てくる
• 計算量の増大による、処理時間の増加を抑える。即
ち、HCC処理系による待ち時間を少なくし、多体問
題のアニメーションを容易にするという事を目標とす
る
今までやったこと
•
•
•
•
•
処理系にタイマーを入れる
マニュアルの読み込み
性能評価法の提案
多体問題のサーベイ
（研究室に慣れる）
HCC処理系における多体問題
• 多体問題は問題依存の部分がある
– ビリヤードの球の数を増やした問題
– 天体の問題
• よってプログラムを各部分での工夫が有効だ
と思われる
ビリヤード型多体問題
• ビリヤードの球を増やしていく問題
• 衝突系なので、微小時間で見れば２球の問
題となる
• ２つの球の衝突を判定するためだけにforall
を使っている
プログラム
一部抜粋
Collisions = (){
O(n^2)
always forall Ball(A) do forall Ball(B) do
if (A < B) then
//not the same ball
if ((B.px - A.px)^2 + (B.py - A.py)^2 = 4*radius^2) then {
Collision,
if (A.px = B.px) then {
A.ChangeY, B.ChangeY,
A.vy = prev(B.vy),
B.vy = prev(A.vy)
},
if (A.px < B.px) then {
A.ChangeX, B.ChangeX,
A.ChangeY, B.ChangeY,
new c in new ix in {
c = (A.py - B.py)/(A.px - B.px),
ix = (prev(B.vx - A.vx) + c*prev(B.vy - A.vy))/(1+c^2),
B.vx = prev(B.vx) - ix,
B.vy = prev(B.vy) - c*ix,
A.vx + B.vx = prev(A.vx + B.vx), // X-momentum
A.vy + B.vy = prev(A.vy + B.vy) // Y-momentum
}
}
}
},
Ball(B1, 10, 10, 25, 25),
Ball(B2, 20, 11, -35, 55),
Ball(B3, 80, 51, -15, 49),
Edges(),
Collisions(),
Pockets()
天体型多体問題
• 太陽系など重力場の天体の問題
• 重力が全ての物体に影響を及ぼすことから
起こる
• forallは物体にかかる重力を知るために使っ
ている
プログラム
Planet = (initvx, initvy, initpx, initpy, m)[px, py, mass]{
px = initpx, py = initpy,
px' = initvx, py' = initvy,
sample(px),
sample(py),
always {
cont(px), cont(py),
mass = m,
px'' = sum(F.x, Force(F), F.Target = Self),
py'' = sum(F.y, Force(F), F.Target = Self)
}
},
always Force = (S, T)[Target, x, y]{
Target = T,
new tmp in {
tmp = g * S.mass /((S.px - T.px)^2 + (S.py -T.py)^2)^1.5,
x = tmp * (S.px - T.px),
y = tmp * (S.py - T.py)
}
},
always forall Planet(X) do forall Planet(Y) do
if (X != Y) then new F in Force(F, X, Y),
always g = 0.00011792,
Planet(Sun, 0, 0.00205455, 0, 0, 332948.34),
Planet(Mercury, 0, 8.1987, 0.4666, 0, 0.055271),
Planet(Venus, 0, 7.3365, 0.72794, 0, 0.81476),
Planet(Earth, 0, 6.179, 1.0167, 0, 1),
Planet(Mars, 0, 5.006367, 1.6657754, 0, 0.10745),
Planet(Jupiter, 0, -2.8928, -4.9505, 0, 317.94),
Planet(Saturn, 0, 1.9244, 10.0695, 0, 95.181),
Planet(Uranus, 0, 1.36838, 20.088, 0, 14.535),
Planet(Neptune, 0, 1.13635, 30.3155, 0, 17.135),
Planet(Pluto, 0, 0.77826, 49.33957, 0, 0.0021586)
O(n^2)
HCC処理系における多体問題の評
価（ビリヤード）
billiard多体問題RKQC
1
1
0
2
0.01
3
0.04
4
0.06
5
0.09
6
0.12
7
0.16
8
0.2
9
0.28
10
0.35
11
0.43
12
0.54
13
0.65
14
1.12
15
0.95
16
1.6
17
2.35
18
2.96
19
3.44
20
4.02
2
0.01
0.02
0.05
0.07
0.13
0.14
0.2
0.25
0.34
0.46
0.56
0.79
0.96
1.68
1.79
2.78
4.16
5.12
6.18
7.22
横軸: -rオプションで指定した時間
縦軸: 物体の数
値の単位は秒(CPUTime)
4
0.01
0.03
0.07
0.11
0.2
0.22
0.29
0.36
0.47
0.64
0.86
1.16
1.33
1.93
2.57
4.09
7.18
8.67
8.15
10.5
8
0.02
0.07
0.13
0.17
0.29
0.4
0.57
0.72
1.01
1.4
1.84
2.31
2.49
3.7
4.27
7.16
10.93
13.35
17.51
23.03
16
0.02
0.14
0.24
0.27
0.47
0.73
0.92
1.35
1.75
2.49
2.81
3.33
3.52
6.65
8.62
11.44
13.78
16.51
25.64
31.61
32
0.02
0.18
0.44
0.49
0.73
1.13
1.28
2.02
2.43
3.4
3.51
4.38
4.55
9.39
11.91
16.11
16.11
18.71
33.61
35.92
64
0.03
0.28
0.82
0.7
0.94
1.58
1.74
2.75
3.17
4.49
4.41
5.48
5.67
11.71
15.08
20.24
17.5
20.06
42.06
38.09
HCC処理系における多体問題の評
価（ビリヤード）
処理に掛かった時間(s)
Billiard(RKQC)
4.5
4
3.5
3
2.5
2
1.5
1
0.5
0
Billiard(RKQC)
0
5
10
15
ボールの数
-r 1（1UnitTime）の時のグラフ
20
25
HCC処理系における多体問題の評
価（天体）
planetの多体問題(RKQC)
1
2
1
0
0
2
0.02
0.02
3
2.59
5.14
4
5.94
11.79
5
11.56
23.05
6
19.87
39.18
7
31.7
8
52.73
9
287.9
10 1616.07
4
0
0.02
10.2
23.72
46.27
8
0
0.02
20.46
47.38
92.89
16
0
0.03
40.58
94.98
188.21
32
0
0.04
81.5
191.95
横軸: -rオプションで指定した時間
縦軸: 物体の数
値の単位は秒(CPUTime)
※実行に時間が掛かったため、ところどころ計測していない
64
0
0.06
163.19
393.54
HCC処理系における多体問題の評
価（天体）
処理に掛かった時間(s)
planet(RKQC)
1800
1600
1400
1200
1000
800
600
400
200
0
-200 0
planet(RKQC)
2
4
6
惑星の数
-r 1（1UnitTime）の時のグラフ
8
10
12
ビリヤード型多体問題（空間分割）
• 空間を分割して、一度に見ていく物体の数を
減らす方法
• うまく分ければ、計算量をO(N^2)からO(N
log N)に近づけることが出来る
空間分割
天体型多体問題（ツリー法）
• 天体型多体問題に有効
• 計算量をO(N^2)からO(N log N)に近づける
ことが出来る
ツリー法のアルゴリズム
平面内の適当な領域に粒子が分布しているとする
粒子は有限個なので、その全てを含む正方形を考えられる
1. まず、その正方形を4つに分ける
2. 正方形に粒子が2個以上入っていたら、さらに正方形を4つ
に分けるという方法で、まず空間を分割する。
3. 分割した空間に対応したツリー構造を考えると、根に全体の
正方形に対応する節点があり、その下に4つの小正方形、
…と続いていって、ツリーの葉には粒子1つ1つが来ることに
なる
4. 一つ一つの粒子への重力は、ツリーのある節点があらわす
正方形の粒子全体からのある粒子への力を計算すれば出
てくる
ツリー法のアルゴリズム
つまり
｛
ある節点からある粒子（天体）への力＝
その節点の重心からの力
(節点と粒子が「十分離れている」)
その節点の子節点からの力の合計
(それ以外)
となる。
「十分離れている」というものを判断するために
l/d < θ
というものを使う。Dは粒子と節点の重心の距離、lは節点に対応する正方形の
一辺の長さ、θは見込み角である。
見込み角は計算精度と計算量を制御するものである。
ツリー法
これからの課題
• HCCの環境整備及び興味あることの研究
– 性能評価法
– mathlib
– 刻み幅と収束の調整など（Euler法）
• 実装
– どのようにHCCで実装するか？
参考文献
•
牧野淳一郎 重力多体系の数値計算 2001
http://jun.artcompsci.org/~makino/papers/bussei-nbody/bussei-nbody.html
•
Bj"orn Carlson. Vineet Gupta. The hcc Programer’s Manual
© Copyright 2024 ExpyDoc
