5.2.1 ビリヤードのモデルにおけるガード条件判定の処理時間
ガード条件判定の並列化の性能を評価するにあたって，ベンチマークとして2.1.1節に おけるビリヤードのモデルを使用した．並列化された処理系の性能評価を行う前に，ガー ド条件判定の並列化が有意義であることを確認するために予備実験としてビリヤードの ボールの数に対するガード条件判定を含めた処理時間の計測を行った．シミュレーション は20フェーズまで行った．また，このモデルのシミュレーションがベンチマークとして 適していることも示す．
実験結果を表5.2に，これをグラフにしたものを図5.1に示す．
図5.1より，処理時間がボールの数が増えるのに応じてO(n2)で増加していることが 確認できる．また，シミュレーション全体の処理時間に対して9割以上の時間をガード条 件判定が占めている事が確認できる．
このことから，ガード条件判定の並列化による高速化が有意義であると言える．また，
このモデルのシミュレーションはほとんどの時間をガード条件判定に費やしているため，
ガード条件判定の高速化に関するベンチマークとして適していると言える．
表5.2 1スレッド時のビリヤードにおけるボールの数に対する処理時間(µsec)
ボール数 シミュレーション全体 ガード条件判定 平均値 標準誤差 平均値 標準誤差 100 199462200 594119 161378200 533697 120 318475800 563491 268425400 483876 140 474526400 239545 410825400 227237 160 682913400 5389727 604240800 5015335 180 936403000 924577 841171600 891365 200 1254176000 1405007 1141136000 1345179
第5章 性能評価 27
0 2x108 4x108 6x108 8x108 1x109 1.2x109 1.4x109
100 120 140 160 180 200
Time[µs]
Number of balls(n) Total
(3.518412e+04)n2-1.883646e+08 Guard evaluation (3.268908e+04)n2-2.024454e+08
図5.1 1スレッド時のビリヤードにおけるスレッド数に対する処理時間
5.2.2 ビリヤードのモデルにおける並列ガード条件判定の効果
次に，ボールの個数が200個であるビリヤードのモデルのシミュレーションをベンチ マークとして，並列化したガード条件判定の効果について検証を行った．シミュレーショ ンは20フェーズまで行った．実験結果を表5.3に，これをグラフにしたものを図5.2に 示す．また，速度向上について示すため，1スレッド時の時間を各スレッド時の時間で 割った数値のグラフを図5.3に示す．
図5.2より，シミュレーション全体及びガード条件判定の処理時間両方が，スレッド数 の増加に応じて減少していることが確認できる．その上で図5.3より，ガード所件判定の 処理時間は16スレッド辺りまでほぼスレッド数倍になっていることが確認できる．32ス レッドの場合に速度向上の度合いが小さくなっているが，これはスレッド数に対してガー ド条件の個数が十分でないためであると考えられる．
シミュレーション全体の実行時間は，ガード条件判定の時間が減少するほどそれ以外の 時間の割合が増加し，速度向上の度合いが鈍くなることが確認できる．しかし，並列化の オーバーヘッドによる極端な処理時間の増大は見られず，計測した範囲ではスレッド数が
第5章 性能評価 28
0 2x108 4x108 6x108 8x108 1x109 1.2x109 1.4x109
0 5 10 15 20 25 30 35
Time[µs]
Number of threads(n)
Total 1.133457e+09/n+1.162676e+08 Guard evaluation 1.134391e+09/n+2.501023e+06
図5.2 200ボールのビリヤードにおけるスレッド数に対する処理時間
0 5 10 15 20 25 30
0 5 10 15 20 25 30 35
Speed-up
Number of threads(n) Total
Guard evaluation n
図5.3 200ボールのビリヤードにおけるスレッド数に対する速度向上
第5章 性能評価 29 増えるごとに高速化していることが分かる．
結果として，ガード条件判定については期待通り高速化することに成功した．また，全 体の実行時間に関しても高速化しており，満足できる結果が得られた．
5.2.3 ガード条件の個数を減らした場合の並列ガード条件判定の効果
続いて，ボールの個数に対する並列ガード条件判定の効果を確認する．これにより，
ガード条件の個数がどの程度以上あれば並列判定の効果が得られるかを評価する．シミュ レーションは20フェーズまで行った．計測結果を表5.4に，各ボールの数に対する速度 向上の度合いを表したグラフを図5.4から5.8に示す．
図5.4より，ボールの数が20個の場合は理想的なスレッド数倍の速度向上は見られな いものの，ガード条件判定部分は高速化していることが確認できる．一方で全体の実行時 間に関しては4スレッド以上の場合ほぼ速度向上が見られず，遅くなる場合も見られる．
図5.5から5.8より，ボールの数が40個の場合は2スレッド程度，60個の場合は4ス レッド程度，80から100個の場合は8 スレッド程度まで理想的な速度向上が見られる．
3.2.1節で述べた通り，ビリヤードの問題においてはボールの個数nに対してnC2+ 2n
回のガード条件判定が発生するため，本実験環境においては1スレッド辺り概ね500個以 上のガード条件判定が発生する場合に理想的な速度向上が見られると考えられる．
表5.3 200ボールのビリヤードにおけるスレッド数に対する処理時間(µsec)
スレッド数 シミュレーション全体 ガード条件判定 平均値 標準誤差 平均値 標準誤差 1 1253128000 1742309 1139992000 1651548 2 678760000 1040814 565639000 953385 4 394912200 140357 282054000 177611 8 255034800 329659 142062200 231174 16 186935600 691952 73200860 453325 32 160328800 874160 45390860 363574
第5章 性能評価 30
表5.4 ビリヤードにおけるボールの個数とスレッド数に対する処理時間(µsec)
ボール数 スレッド数 シミュレーション全体 ガード条件判定 平均値 標準誤差 平均値 標準誤差
20 1 7994346 35285 2889804 15203
2 6718976 24178 1655332 24134
4 6224706 23536 905842 1652
8 6346994 43344 611811 4053
16 6272884 181736 413901 1971
32 7030124 178723 336672 4488
40 1 25198440 14851 14145140 9546
2 18476220 45937 7420006 36812 4 15160640 41721 4081360 31150 8 13467500 66242 2411080 81213 16 13135380 126279 1975640 119809 32 13794260 139628 1339922 297488
60 1 58963740 117393 40312200 85268
2 40115060 196738 21418520 151482 4 29978020 62522 11237220 34832 8 24859200 64083 5897600 40611 16 22451300 156948 3266470 22276 32 21213740 50504 1994414 16777
80 1 115566000 99850 87928880 95840
2 73628720 372789 45955260 260970 4 50951560 54374 23322320 36033 8 39674220 122258 11968200 62324 16 34517680 153313 6341102 16771 32 32624180 156866 3751076 41407
100 1 199081600 115882 160971200 100561
2 120838200 269722 82760740 229615 4 79754060 88288 41728420 58560 8 59235000 45230 21252760 23048 16 49559320 194484 11113740 68430 32 45760560 634976 6203744 52690
第5章 性能評価 31
0 1 2 3 4 5 6 7 8 9
0 5 10 15 20 25 30 35
Time[µs]
Number of threads(n)
Total Guard evaluation n
図5.4 20ボールのビリヤードにおけるスレッド数に対する速度向上
0 2 4 6 8 10 12
0 5 10 15 20 25 30 35
Time[µs]
Number of threads(n)
Total Guard evaluation n
図5.5 40ボールのビリヤードにおけるスレッド数に対する速度向上
第5章 性能評価 32
0 5 10 15 20 25
0 5 10 15 20 25 30 35
Time[µs]
Number of threads(n) Total
Guard evaluation n
図5.6 60ボールのビリヤードにおけるスレッド数に対する速度向上
0 5 10 15 20 25
0 5 10 15 20 25 30 35
Time[µs]
Number of threads(n) Total
Guard evaluation n
図5.7 80ボールのビリヤードにおけるスレッド数に対する速度向上
第5章 性能評価 33
0 5 10 15 20 25 30
0 5 10 15 20 25 30 35
Time[µs]
Number of threads(n) Total
Guard evaluation n
図5.8 100ボールのビリヤードにおけるスレッド数に対する速度向上
5.2.4 その他のモデルにおける並列ガード条件判定の効果
ビリヤード以外のモデルにおける，ガード条件判定の並列化の効果を検証する．この並 列化が特に効果的であるのは，ガード条件判定が多数回発生するような，多数のオブジェ クトをシミュレーションするようなモデルである．
道路を走る車列
このモデルは，道路を走る30台の自動車が前の車との距離に応じてブレーキやアクセ ルを操作する様子を再現したものである．このモデルのHydLa プログラムを図5.9 に 示す．
このモデルを8フェーズまでシミュレーションした際の計測結果を表5.5に，グラフに したものを図5.10に，1スレッド時と比較した速度向上を表すグラフを図5.11に示す．
図5.10より，スレッド数を増やすほどガード条件判定の時間は短くなり，それに応じ てシミュレーション全体の実行時間も短くなることが確認できる．また，図 5.11より，
ガード条件判定に関してはスレッド数が増えるごとに速くなっていることが確認できる
第5章 性能評価 34 1 INIT(x,x0,v0,timer) <=> x=x0 & x’=v0 & timer=0.
2 SW_ACC(xl,xf,timer) <=> [](xf’- < 30 & xl- - xf- >= 10 => timer
’=1 & xf’’ = xf’’).
3 SW_BRK(xl,xf,timer) <=> [](xf’- > 0 & xl- - xf- <= 3 => timer
’=-1 & xf’’ = xf’’).
4 ACC(xl,xf,timer) <=> [](timer- >= 1 => xf’’=3).
5 BRK(xl,xf,timer) <=> [](timer- <= -1 => xf’’=-5).
6 CONST(x) <=> [](x’’=0).
7 TIMER_OFF(timer) <=>[](timer=0).
8
9 X := {x0..x29}.
10 T := {timer0..timer29}.
11
12 { INIT(X[i],1000-20*i,20+i/|X|,T[i]) | i in {1..|X|} }.
13 CONST(X[1]), TIMER_OFF(T[1]).
14 { ( CONST(X[i]), TIMER_OFF(T[i]) )
15 << ( SW_ACC(X[i-1],X[i],T[i]), SW_BRK(X[i-1],X[i],T[i]) ) 16 << ( ACC(X[i-1],X[i],T[i]), BRK(X[i-1],X[i],T[i]) )
17 | i in {2..|X|} }.
図5.9 HydLaによる道路を走る車列のモデル
表5.5 道路を走る車列のモデルにおけるスレッド数に対する処理時間(µsec)
スレッド数 シミュレーション全体 ガード条件判定 平均値 標準誤差 平均値 標準誤差 1 38813400 71847 17290540 42192 2 32391580 158524 9063216 42089 4 28440140 137259 4890974 35787 8 26717740 439119 2800126 55731 16 26316320 515421 1990878 241254 32 27849660 167988 1050362 39391
第5章 性能評価 35
0 5x106 1x107 1.5x107 2x107 2.5x107 3x107 3.5x107 4x107
0 5 10 15 20 25 30 35
Time[µs]
Number of threads(n)
Total 1.271884e+07/n+2.591477e+07 Guard evaluation 1.656927e+07/n+7.442228e+05
図5.10 道路を走る車列のモデルにおけるスレッド数に対する処理時間
0 2 4 6 8 10 12 14 16 18
0 5 10 15 20 25 30 35
Speed-up
Number of threads(n) Total
Guard evaluation n
図5.11 道路を走る車列のモデルにおけるスレッド数に対する速度向上
第5章 性能評価 36 が，このモデルのシミュレーションにかかる時間に対してガード条件判定の占める割合が 小さいため，全体の実行時間への効果は限定的である．よって，このモデルに関しては ガード条件判定の並列化による効果は小さいと言える．
すれ違う歩行者
このモデルは，2次元平面上に一定の速度で前進する歩行者が20人存在し，他の歩行 者と一定以上近づいた場合に左右に曲がって避けようとする様子をモデル化したものであ る．このモデルのHydLaプログラムを図5.12から5.14に示す．
このモデルを8フェーズまでシミュレーションした際の計測結果を表5.6に，グラフに したものを図5.15に，1スレッド時と比較した速度向上を表すグラフを図5.16に示す．
図5.15より，このモデルにおいてはシミュレーション全体に対してガード条件判定の 占める時間の割合が多く，ガード条件判定の並列化により大きく高速化できていることが 分かる．また，図5.16より，ガード条件判定は16スレッドまでスレッド数倍高速化され ており，全体の実行時間に関しても5倍以上高速化されている事が確認できる．よって，
このモデルについてはガード条件判定の並列化による効果が大きいと言える．
ウォータータンク
複数個の水が入るタンクがあり，それぞれのタンクが一定の速さで排水される．これら のタンクに注水できるホースが1つあり，あるタンクの水位が一定以下となったらその タンクに注水するという制御を行う．[17] このモデルのHydLaプログラムを図 5.17に 示す．
表5.6 すれ違う歩行者のモデルにおけるスレッド数に対する処理時間(µsec)
スレッド数 シミュレーション全体 ガード条件判定 平均値 標準誤差 平均値 標準誤差 1 269928800 724516 240595800 642144 2 159172400 306127 129758800 251001 4 91542820 47241 62143460 45278 8 59653920 76604 30336880 51749 16 44913680 43624 15400480 15633 32 38553920 62964 8817294 41405