第 4 章 多物体衝突問題の高速化 34
4.2 空間分割したボールの衝突問題のモデル
4.2.1 仕様
4.2.2 実装
実装は以下のようになされた. 実装されたプログラムを機能別に説明する.
リストのDelete機能の実装
lists2.hccはlists.hccにDelete機能を付け加えたものである.
¶ ³
always Delete = (Elem, List, NewList){
if (List = NIL) then always NewList = List
else if (List.Car = Elem) then always NewList = List.Cdr else
new ResList in {
Delete(Elem,List.Cdr,ResList), Cons(List.Car,ResList,NewList) }
},
µ ´
Delete closureはリストListから要素Elemを取り除いたリストNewListを作る. 変数はElem,List,NewListで,それぞれListから取り除きたい要素,取り除く要素が あるリスト,取り除いたリストを保持するためのリストである. 内部ではAppend と同じように再帰的構造をしている. まず,if文でListがNILかどうかを判定し ている.これが再帰の終了条件となる. もしListがNILだったらNewList=Listと いう制約を加える. ListがNILでなく,Listの先頭要素List.Carが取り除きたい要 素Elemと等しかった時は, NewList=List.Cdrという制約を加えている. それ以 外のときは,ResListというローカル変数を作り, 取り除きたい要素ElemとListの 先頭要素を除いたリストList.CdrでDeleteを実行し,出来たリストをResList と する. また,同時にListの先頭要素とResListをConsしてNewListという新たな リストをつくる. このようにDeleteは実装されている.
¶ ³
always MutableListClass = ()[Root, ConsList,
AppendList, DeleteList]{
new Changed in {
do always Root = NIL watching Changed, always ConsList = (Elem){
Changed, new L in {
evalexpr K = prev(Root) in Cons(Elem, K, L), do always Root = L hencewatching Changed }
},
always DeleteList = (Elem){
Changed, new L in {
evalexpr K = prev(Root) in Delete(Elem, K, L), do always Root = L hencewatching Changed
} },
always AppendList = (List){
Changed, new L in {
evalexpr K = prev(Root) in Append(List, K, L), do always Root = L hencewatching Changed
} } } }
µ ´
lists2.hccのMutableListClassはlists.hccのMutableListClassをDeleteを使える ように拡張したものである. DeleteListというclosureがクラスの内部で新たに作 られている. このclosureはリストから要素を取り除くために使われる. 内部では 新たにDeleteListというclosureを使うための宣言のための変数DeleteListが定 義されている.
ボールの衝突問題1分割モデルの実装
これは空間分割のテスト用として実装されたプログラムである. 空間の1分割 が実装されている. BallクラスとEdges closureはballCollision.hcc(前述)と同じ ものを使用しているので,説明は省略する.
¶ ³
#include include/lists2.hcc
#define radius 3
#define xMax 150
#define yMax 300
#INTEGRATION_INIT 0.03
#INTEGRATOR RK4
µ ´
プログラムの定数定義とオプションを記述している部分である. まず#includeを 使って外部からhccファイルを読み込む. 今回はincludeフォルダにあるライブラ リファイルlists2.hcc(前で説明)を読み込んでいる. 他の部分はballCollision.hcc と同じなので説明は省略する.
¶ ³
Collisions = (){
always forall MutableListClass(L) do {
if (L.Root != NIL) then MapBall(L.Root.Cdr, L.Root.Car) }
},
µ ´
ボールの衝突を扱うclosure Collisionsである. ballCollisionのCollisionsとはか なり違っている. 内部ではまずforallを使ってMutableListClassのオブジェクト の全てのリストLに対してif以下の処理を行っている. if文ではLの根リストが NILかどうかを判定している. もしNILでなければclosure MapBallに引数とし てL.Root.CdrとL.Root.Carを渡して実行する. 実際の衝突の処理はここではし ていない.
¶ ³
always MapBall = (DList1, TempElement1){
if(DList1 != NIL) then {
MapBallSub(DList1.Cdr, TempElement1), MapBall(DList1.Cdr, DList1.Car),
CollisionCompute(DList1.Car, TempElement1) }
},
µ ´
closure MapBallはBallオブジェクトの衝突を判定するCollisionCompute closure を呼び出すclosureである. Ballオブジェクトがリストの中に入っているので,呼 び出し方を工夫しなければならない. そのために作られたclosureである. 内部 は再帰的に定義されている. 判定はNILかどうかを調べるという方法のほかに
lengthが0かどうかを調べるという方法もあったが, ここではリスト処理らしく
するためにNILで判定した.
¶ ³
always MapBallSub = (DList2, TempElement2) { if(DList2 != NIL) then {
MapBallSub(DList2.Cdr, TempElement2), CollisionCompute(DList2.Car, TempElement2) }
},
µ ´
MapBallSubは
¶ ³
always CollisionCompute = (Elem1, Elem2){
if((Elem1.px-Elem2.px)^2+(Elem1.py-Elem2.py)^2=4*radius^2) then{
Collision,
if (Elem2.px = Elem1.px) then { Elem2.ChangeY, Elem1.ChangeY, Elem2.vy = prev(Elem1.vy), Elem1.vy = prev(Elem2.vy) },
if (Elem2.px != Elem1.px) then { Elem2.ChangeX, Elem1.ChangeX, Elem2.ChangeY, Elem1.ChangeY, new c in new ix in {
c = (Elem2.py - Elem1.py)/(Elem2.px - Elem1.px),
ix=(prev(Elem1.vx-Elem2.vx)+c*prev(Elem1.vy-Elem2.vy)) /(1+c^2),
Elem1.vx = prev(Elem1.vx) - ix, Elem1.vy = prev(Elem1.vy) - c*ix,
Elem2.vx + Elem1.vx = prev(Elem2.vx + Elem1.vx), Elem2.vy + Elem1.vy = prev(Elem2.vy + Elem1.vy) }
} } },
µ ´
実際の衝突の処理をするのがCollisionComputeである. Elem1,Elem2という2つ の引数があり,それらの衝突を判定している. 内部の処理はballCollision.hccの Collisions closureのA,BをElem1,Elem2に置き換えて, if(A ¡ B)というボールの 同一性を排除する判定を除いたものとなっている. MapBall closureがあるので ボールの同一性を気にしなくても良くなった.
¶ ³
MutableListClass(L1),
next { ListClassJudge(B1), next { ListClassJudge(B2), next { ListClassJudge(B3), next { ListClassJudge(B4), next { ListClassJudge(B5), next { ListClassJudge(B6), next { ListClassJudge(B7), next { ListClassJudge(B8), next { ListClassJudge(B9), next { ListClassJudge(B10), next { ListClassJudge(B11), next { ListClassJudge(B12), next { ListClassJudge(B13), next { ListClassJudge(B14), next { ListClassJudge(B15), next { ListClassJudge(B16), next { ListClassJudge(B17), next { ListClassJudge(B18), next { ListClassJudge(B19), next { ListClassJudge(B20) }}}}}}}}}}}}}}}}}}}},
always ListClassJudge = (X){
L1.ConsList(X) },
µ ´
MutableListClassのオブジェクトL1を作っている. これでリストが作られ,その 操作が出来るようになった. ListClassJudge closureはボールの場所によって,ボー ルが所属するリストを決定するためのものである. 今回は分割1なのでそのまま ボールをL1に加えている. next ListClassJudge. . .,部分でボール1つ1つに対し てListClassJudgeを行っている. ここでnextを使わないと,複数個のボールが同
時にConsListされてしまう. そうすると制約エラーがでてしまうので,next構文
を使いListに加える順番をつけることでエラーを回避している. ここではボール を20個としているが,もっと増やしたい時などは,ここもその数に応じて変えて いかなければならない.
¶ ³
Ball(B1,23,41,-7,-26), Ball(B2,17,83,-2,-49), Ball(B3,35,287,-82,79), Ball(B4,17,90,-54,63), Ball(B5,41,131,17,-67), Ball(B6,101,227,-52,-99), Ball(B7,89,41,-64,37), Ball(B8,71,83,26,78), Ball(B9,71,281,-55,97), Ball(B10,119,71,35,-54), Ball(B11,137,65,-5,-2), Ball(B12,83,119,30,69), Ball(B13,113,35,-91,-88), Ball(B14,107,95,-17,-19), Ball(B15,53,221,96,-69), Ball(B16,11,101,-32,3), Ball(B17,95,185,-89,27), Ball(B18,47,47,-71,87), Ball(B19,71,29,-8,-18), Ball(B20,23,34,28,-74), Edges(),
Collisions(), forall Ball(B) do sample(B.px, B.py),
µ ´
ボールの生成と各closureの実行とサンプルの宣言を行っている部分である. ボー ルの数が変わっているだけで,後はbilliard.hccと同じ構造になっている.
ボールの衝突問題2分割モデルの実装
ballCollisionDevided2.hccは上記のballCollisionDevided1.hccを改良して空間 を2つに分割したものである. 改良した部分のみ説明する.
¶ ³
BallListJudge = (){
always forall Ball(X) do {
if(X.py=147.0) then {if (X.py’>0) then L2.ConsList(X), if (X.py’<0) then L2.DeleteList(X) },
if(X.py=153.0) then {if (X.py’>0) then L1.DeleteList(X), if (X.py’<0) then L1.ConsList(X) }
} },
BallListJudge(),
µ ´
BallListJudge closureはボールがどの空間にあるかを判断して,その空間のリス トにボールを入れたり,空間から出たとき,リストから消したりする機能を持って いる. 内部では,全てのBallオブジェクトに対してもしy座標が147になったら,
ボールの速度を見にいく. ボールの速度がy座標正方向であれば,ボールがL2の 空間に入ろうとしているという事なのでL2.ConsList(X)を実行してボールXを L2に加える. ボールの速度がy座標負方向であれば,ボールがL2空間から出よう としているという事なのでL2.DeleteList(X)を実行してボールXをL2から削除 する.
同様にy座標が153 になったら,ボールの速度を見にいく. ボールの速度が y座標正方向であれば,ボールがL1空間から出ようとしているということなの で. L1.DeleteList(X)を実行してボールXをL1から削除する. ボールの速度 がy座標負方向であれば,ボールがL1空間に入ろうとしているという事なので, L1.ConsList(X)を実行してボールXをL1に加える.
これらの処理をしてリストの操作をしている.
¶ ³
MutableListClass(L1), MutableListClass(L2),
always ListClassJudge = (X){
if(X.py >= 0.0 && X.py <= 153.0) then L1.ConsList(X), if(X.py >= 147.0 && X.py <= yMax) then L2.ConsList(X) },
µ ´
最初にMutableListClassを二つつくりそれぞれL1,L2としている. L1は0≤px≤ 150,0 ≤py ≤ 153の空間にあるボールを保持しておくリストである. またL2は 0≤px≤150,147≤py ≤300の空間にあるボールを保持しておくリストである.
重複空間があるのはボールが大きさを持っているからである.
ListClassJudge closureはボールが初期状態でL1空間にあるのか,L2空間にあ るのかを判断する. そして,所属する空間が分かったらリストにConsListするた めのclosureである.
ボールの衝突問題4分割モデルの実装
¶ ³
BallListJudge = (){
always forall Ball(X) do { if(X.py=147.0) then {
if(X.py’<0) then {
if (X.px>=72.0) then L4.DeleteList(X), if (X.px<=78.0) then L2.DeleteList(X) },
if(X.py’>0) then {
if (X.px>=72.0) then L4.ConsList(X), if (X.px<=78.0) then L2.ConsList(X) }
},
if(X.py=153.0) then { if(X.py’ < 0) then {
if (X.px >= 72.0) then L3.ConsList(X), if (X.px <= 78.0) then L1.ConsList(X) },
if(X.py’ > 0) then {
if (X.px >= 72.0) then L3.DeleteList(X), if (X.px <= 78.0) then L1.DeleteList(X) }
},
if(X.px = 72.0) then { if(X.px’ < 0) then {
if (X.py >= 147.0) then L4.DeleteList(X), if (X.py <= 153.0) then L3.DeleteList(X) },
if(X.px’ > 0) then {
if (X.py >= 147.0) then L4.ConsList(X), if (X.py <= 153.0) then L3.ConsList(X) }
},
if(X.px = 78.0) then { if(X.px’ < 0) then {
if (X.py >= 147.0) then L2.ConsList(X), if (X.py <= 153.0) then L1.ConsList(X) },
if(X.px’ > 0) then {
if (X.py >= 147.0) then L2.DeleteList(X), if(X.py <= 153.0) then L1.DeleteList(X) }
} } },
BallListJudge(),
µ ´
¶ ³
MutableListClass(L1), MutableListClass(L2), MutableListClass(L3), MutableListClass(L4),
always ListClassJudge = (X){
if(X.py>=0.0 && X.py<=153.0 && X.px>=0.0 && X.px<=78.0) then L1.ConsList(X),
if(X.py>=147.0 && X.py<=yMax && X.px>=0.0 && X.px<=78.0) then L2.ConsList(X),
if(X.py>=0.0 && X.py<=153.0 && X.px>=72.0 && X.px<=xMax) then L3.ConsList(X),
if(X.py>=147.0 && X.py<=yMax && X.px>=72.0 && X.px<=xMax) then L4.ConsList(X)
},
µ ´
第 5 章 実験とその結果
前章で実装したHCCプログラムを使いプログラムの実行時間を計ってみる.
実験環境
• OS Windows XP Home Edition Version 2002 Service Pack 2
• Memory 256MB
• CPU Mobile Intel Pentium 3 Processor-M 1000MHz
• 1次キャッシュ 32KB
• 2次キャッシュ 512KB
今回はボールの数を変えて時間がどのように変化するかを調査した. また,分 割したモデルと分割なしのモデルとで実行時間がどのように変化するかも調査し た. ボールが所属する空間が変わる時,リストの操作が必要になる. 今の実装だと ここで制約エラーが発生する可能性がある. そこでボールの所属する空間がなる べく変わらないようにボールの位置とその速度を設定した. シミュレーション時 間は10である.また各5回ずつ測定した. 実験結果は次表のようになった.
表 5.1: 低速
ボールの数 ballCollision Devide1 Devide2 Devide4
0 0.04 0.04 0.04 0.05
4 0.09 0.14 0.14 0.13
8 0.25 0.33 0.27 0.29
12 0.39 0.6 0.5 0.5
16 0.64 0.97 0.73 0.72
20 0.95 1.44 0.97 1
24 1.4 2.03 1.47 1.42
28 1.89 2.97 1.99 1.87
32 2.58 4.04 2.63 2.57
36 3.34 5.22 3.38 3.5
40 4.21 6.75 4.28 4.82
44 5.36 8.45 5.31 6.29
48 6.4 210.68 6.39 7.28
52 7.83 400.64 7.82 8.79
56 295.95 542.93 9.33 10.13
60 579.86 710.16 10.87 11.66
64 766.17 960.35 207.61 13.91
68 1024.35 1211.39 352.02 16.1
72 1342.14 1553.27 437.19 18.48
76 1694.19 1934.07 552.32 76.36
80 2121.59 2360.59 652.36 296.7
84 2691.32 2863.08 795.39 396
表 5.2: 中速
ballCollision Devide1 Devide2 Devide4
0 0.03 0.04 0.05 0.04
4 0.11 0.17 0.15 0.19
8 0.26 0.38 0.33 0.58
12 0.51 0.76 0.61 1.23
16 0.93 1.33 0.95 2.14
20 1.59 2.21 1.52 3.85
24 2.68 3.63 2.46 6.09
28 4.39 6.19 3.77 8.8
32 7.11 9.71 5.72 DE
36 10.8 14.43 8.34 DE
40 14.84 20.12 10.69 DE
44 22.08 29.17 14.82 DE
48 31.22 307.94 19.76 DE
52 44.63 425.88 25.54 DE
56 427.96 583.35 33.35 DE
60 600.52 766.81 41.19 DE
64 815.09 1029.1 300.3 DE
68 1109.86 1317.55 373.99 DE 72 1452.34 1675.58 458.87 DE
76 1820.1 2091.47 582.74 DE
80 2280.57 2560.48 694.1 DE
84 2745.87 3116.31 865.28 DE
表 5.3: 高速
ballCollision Devide1 Devide2 Devide4
0 0.03 0.05 0.04 0.04
4 0.41 0.52 0.5 1.2
8 1.46 1.86 1.63 5.18
12 3.77 4.84 3.75 15.57
16 8.2 10.93 7.37 37.79
20 16.62 20.83 13.81 84.79
24 28.98 34.36 22.94 172.3
28 45.8 58.15 34.11 322.46
32 72.47 89.9 51.61 DE
36 106.56 130.61 72.57 DE
40 147.87 183.24 90.55 DE
44 218.63 263.57 124.89 DE
48 304.28 510.83 164.32 DE
52 425.61 692.52 212.81 DE
56 738.81 966.25 278.76 DE
60 1006.31 1281.62 341.37 DE 64 1368.79 1739.64 514.72 DE 68 1854.45 2252.56 635.93 DE 72 2454.16 2876.89 788.48 DE 76 3101.9 3626.76 1006.38 DE 80 3877.32 4471.49 1206.96 DE 84 4558.92 5507.88 1520.46 DE
第 6 章 考察
分割なしのモデルの場合,ボールの数が56になった時に実行時間が爆発的に増え てしまっている. 原因を探ってみたところ実験に使用したパラメータ(ボールの 位置,速度)に依存しているらしいことが分かった.しかし原因ははっきりとは分 からなかった.今後の調査が必要である. 分割なしと2分割ではボールの数が40 までは分割なしの方が速い. ボールの数が少ない時は,リストの操作に時間が掛 かってしまっているため2分割よりも遅くなってしまっている. ボールの数が56 を越えた辺りから2分割の方の実行時間が目に見えて速くなり,最終的には,実行 時間が約3分の1となった. 考察によると実行時間は約2分の1となるはずであ る. それよりも良くなった理由は,HCCの構文であるforallの仕様と今回実装した リストによる衝突判定の差異によるものだと考えられる. 4分割の時は,ボールの 数が64以上の時2分割よりも速くなっている.
第 7 章 まとめと今後の課題
今回はプログラム上の工夫で多物体衝突問題の高速化を図った. しかし,プログラ ム上の工夫では限界があることが分かった. リストを使って空間を分割する方法 では,並行にリストを操作する事が出来ないからである. これを克服するためには 処理系をいじらなければならない. すなわちgroupという概念を作ってやる事が 必要である. groupは並列に動作する事が可能である. 同時にあるグループに要 素を加えたり,同時にあるグループから要素を取り除く事が出来る. これが出来れ ば,リストを使わなくても空間の分割が出来るのでプログラムも非常に簡単にな る. groupの実装が今後の課題となる.
多物体衝突問題は空間分割という手法で高速化を図る事が出来たが,その他の 問題については今だ不明のままである. 例えば,同じ多数の物体が相互干渉するよ うなシミュレーションの問題に惑星の多体問題がある. これは,今回研究した衝突 問題より難しい問題だ.全ての物体が相互関係を持っているからである. この問 題の高速化手法として,ツリー法という方法がある. 空間を適当に分割をしていっ てから近似をする方法である. この手法をHCCプログラム上で実装する方法は まだ良く分からない. 実装できるかどうかも不明である.しかし高速化が可能であ れば実装する必要がある.
このように高速化できたといってもシミュレーションモデルの一部であるので, これから色々なモデルにおける高速化も考えなければならない. また汎用化出来 る部分については,汎用化してライブラリ化していくことが不可欠である.