速度比較といえばグラフである！！考察である！！！
※2019/12追記：ここでいうグラフはグラフ理論とは全く関係ありません。ごめんなさい。
今回のはかなり久しぶりに速度比較でグラフを使った記事となる！とても胸が高まる。
このためにGPGPU版を作ったようなものだからな。

比較する項目は以下のものだ



「ルート長と全経路総パターン等の関係」

「ルート長と計算時間の関係、違うデバイスでの計算速度の比較」

「ベンチマークモードと通常解析モードの速度比較」

「４色対応高速化機能付きと機能なしの速度比較」




一応解説しておくと
このソフトでは、全てのとりうるルートを全検索している。
「解析長」というのは、計算上ドロップを動かす距離で、ソフトで設定できる値は16までだ。これは最大16マス分移動する経路まで計算できるということだ。

１マス解析長が伸びれば単純計算で３倍の計算量になる。
この前の記事にも書いたとおり、移動方向は上下左右の４つのとりうる範囲があり、さっきと正反対の方向へは行けないからだ。
実際は、６×５マスの範囲外に行く例も除外するため３倍より若干低くなる。
では2.？何倍なのか。また計算時間も2.？倍ずつ増えているのか、などを比較してみようと思う。


次に４色対応高速化機能についてだ。これは土日ダンジョンのステージや、コンボを生む可能性のあるドロップ色が４種類以下であることがわかれば、解析前に自動でコンボ計算省略化機能が作動するというものだ。
４色対応高速化機能はα版のマイナーアップデート版から付いているため、どのくらい高速になったか比較してみようと思う。

そしてこのソフトの目玉、ベンチマーク機能について。
べ題

これはレジストリをいじって画面が落ちないように設定してから、全負荷をかけてルート解析をするというもの。
なかば強引な手法であるが、そうしないと、ディスプレイ出力をしているGPUでGPGPUをする時画面出力に回すタスクがなくなり、２秒以上の信号停止が続くとOSがドライバを強制再起動させてしまう。
それで画面落ちが発生し、計算途中のデータもパーになってしまう。

レジストリをいじればOSにドライバを再起動させない設定にできる。
詳しくは上の画像にもある通り本ソフトの「ヒント」ボタンで確認してほしい。

そしてそのモードが「ベンチマーク高速解析」モードだ。
通常解析と比べどのくらい早くなるか検証してみようと思う。





「ルート長と全経路総パターン等の関係」
・全経路総パターン
画像0

ルート解析長 総経路数
9 196779
10 480712
11 1174882
12 2871769
13 7018349
14 17151003
15 41913267
16 102427430

対数グラフにとってみた。
このグラフから分かることは、総経路数は解析長が１増えるごとに2.44倍ずつになるということだ。
ここで注意してほしいのは総経路数。これは仮に解析長が１０なら、１０までに計算してきた解析長９や８の経路も全部含まれているということだ。
解析長９から１０の時点で新しく計算しなければいけない経路数は引き算で求めることができる。



ルート解析長 新しく発生したルート 新しいルートは何倍になっているか
10 283933 2.4448373384
11 694170 2.4444833398
12 1696887 2.4436394409
13 4146580 2.4436171496
14 10132654 2.4438083053
15 24762264 2.4438057441
16 60514163


ここから分かることは、欄外に出るルートを除外するだけで計算量が３倍ではなく2.444倍にすむ
ということだ。指数が3なのと2.444なのでは大いに違う。効率的な計算を行うには欄外にでるルートは除外すべきだろう。




・コンボ発生パターン

画像1



このグラフから分かることは、コンボ発生パターンのルート数は解析長が１増えるごとに2.50倍ずつになるということだ。
これもそこまでの解析長の総計なので↑と同じく引き算をする。


ルート解析長 新しく発生したコンボルート 新しいコンボ発生パターンルート数は何倍になっているか
10 126276 2.5592986791
11 323178 2.458988545
12 794691 2.5329417346
13 2012906 2.4481421388
14 4927880 2.5156474995
15 12396809 2.4428066932
16 30283008 0

ここからわかることは、全経路パターン中にあるコンボ発生パターンは、解析長を伸ばすほどその割合が高くなってくる。
最初のドロップ配列では１つもコンボが発生しない、という条件があるためある意味当然の結果かもしれない。
解析前の時点で確定コンボがあれば、高くなる割合は低くなるだろう。


・デバイス間データ転送量


画像2


ここから分かることは、デバイス間転送量は2.52倍ずつになるということだ。

正直、ここらへんは「全経路総パターン」と似たような値になるのは当たり前なのでこのくらいにしておく。



「解析長と計算時間の関係、違うデバイスでの計算速度の比較」

・GPU　time
画像3

ノーパとデスクトップでの速度比と、解析長を伸ばすとGPUの計算時間が何倍になっていくかを表したグラフだ。
ここから分かることは、ノーパはデスクトップより計算が４倍遅い
また、intel HD Graphicsでは経路長が1伸びるごとに2.59倍、nVidia Geforce GT520では経路長が1伸びるごとに2.40倍になっている。
どちらも、計算量にほぼリニアに比例しているのが分かる。

（ところでなんでcore i7 3820にGT520なんか積んでいるのかっていうツッコミどころはありますが、そのうちちゃんとハイエンドグラフィックボードを搭載してあげるつもりなので気にしないでください。）




・CPUtime


画像4

ここから分かることは、やっぱりノーパはデスクトップより計算が４倍遅い
また、intel HD Graphicsでは経路長が1伸びるごとに2.56倍、nVidia Geforce GT520では経路長が1伸びるごとに2.47倍になっている。
CPUに関してはcore i5 450m は2.4Ghz  、一方core i7 3820　は3.6Ghz なので単純計算では４倍の差が出るのはおかしいが、ここはキャッシュやメモリ転送能力などが関与しているものと思われる。

GPUとCPUの２つのタイムを比較したが、若干intel HD Graphicsだと、計算量の伸びに対する計算時間の伸びが大きい。これは計算が多くなるほど性能の悪いグラボだと余計時間がかかる
ということになりそうだ。

 
 
「ベンチマークモードと通常解析モードの速度比較」

画像5

intel HD Graphicsだとレジストリいじって高速解析してもほとんど速度は上がらないようだ。





画像6
Geforce GT 520では解析ルート長が大きければ、高速解析の意味がありそうだ。約1.32倍とかなり早くなっているのが分かる。



「４色対応高速化機能付きと機能なしの速度比較」

画像7




 4色解析 6色解析 比
解析長16マス 50210.5 68762 1.3694745123
解析長14マス 5067.5 8504.5 1.6782437099

６色あるドロップ配列より、４色しかないほうが解析が約1.4～1.6倍早くなる事がわかる！

６色というのは当然回復ドロップも合わせたものだ。
解析が早くなるのは４色しかない方といっても、ドロップ数が２つまでならコンボを生まないので実際は６色でも計算が早くなる可能性はあるということだ。




つまり、レジストリいじって計算ドロップがほぼ４色だと、今までより２倍近く早く計算できることになる！
ということはスマホアプリのパズドラルート解析君の2000倍・・というアヌビスもびっくりな倍率で計算できるわけだ！


以上、パズドラルート解析GPGPU版の性能を徹底解析してみた！こんなグラフを書いてバカみたいに楽しんでいるのは俺だけだが、改めてGPGPUのちからは凄いと実感！
そして偶然必然かGPGPU用（？）ビデオカードのGeforce Titanの足音が近づいてきた・・倍精度1.3Tflopsらしい。化け物・・だが出荷数が10000未満という噂もある。余計に高くなりそうだ
どちらにしろ、今のGPUにはもっと働いてもらうことになりそうだ。