仮眠プログラマーのつぶやき

自分がプログラムやっていて、思いついたことをつぶやいていきます。

自作ゲームやツール、ソースなどを公開しております。
①ポンコツ自動車シュライシュラー
DOWNLOAD
②流体力学ソース付き
汚いほうDOWNLOAD
綺麗なほうDOWNLOAD
③ミニスタヲズ
DOWNLOAD
④地下鉄でGO
DOWNLOAD
⑤ババドン
DOWNLOAD
⑥圧縮拳(ツール)
DOWNLOAD
⑦複写拳
DOWNLOAD
⑧布シミュレーション
DOWNLOAD
⑨minecraft巨大電卓地形データ
DOWNLOAD
⑩フリュードランダー
デジゲー博頒布α版
DOWNLOAD
⑪パズドラルート解析GPGPU版
DOWNLOAD
⑫ゲーム「流体de月面着陸」
DOWNLOAD

2013年02月

グラフを使った速度比較!パズドラルート解析GPGPUベンチマーク考察

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

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



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

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

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

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




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

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


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

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

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

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

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





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

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

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



ルート解析長 新しく発生したルート 新しいルートは何倍になっているか
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


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




・コンボ発生パターン

画像1



このグラフから分かることは、コンボ発生パターンのルート数は解析長が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

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


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


画像2


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

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



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

・GPU time
画像3

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

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




・CPUtime


画像4

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

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

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

画像5

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





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



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

画像7




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

6色あるドロップ配列より、4色しかないほうが解析が約1.4~1.6倍早くなる事がわかる!

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




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


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

パズドラルート解析GPGPU版αマイナーアップデート、これでエジプト神さえいれば!

ダウンロードはこちら
新しいビットマップ イメージ



パズドラルート解析GPGPU版αマイナーアップデートでは、課題であったほぼ全部の機能が実装された!
・スクリーンショット読み込み機能
・ベンチマークツイート機能
・起動時の高速化
・解析条件の設定
・計算の高速化


あとはグラフィックの更新のみである。


ところでパズドラは1ヶ月くらいやっていなかったのだが、ソフトを使うために久しぶりに起動してみた。今は10コンボで味方全員の攻撃力が10倍になるモンスターがいるらしく、他にも5属性同時攻撃で攻撃力6倍のモンスターなど。
今までよりさらにコンボ数が重要になってきているのがわかった。
(一応、5属性同時攻撃の経路検索などもルート解析で設定できるようにした)

でもそういうモンスターってやっぱ手に入りにくい・・?レアガチャ?

それになんかスキルのインフレもすごい。
光属性で攻撃2倍の太陽龍プテラドスにあこがれてやっと最近最終進化したと思ったのに、もう光属性の攻撃&回復が2倍のやつでてきているし・・
こいつは太陽龍プテラドスからさらに進化するみたいだな


ダメージインフレもすごくて、10コンボで攻撃10倍のやつをフレンドでも使って得意属性が相手なら、ダメージは200倍×コンボ数のダメージ上乗せというとんでもないダメージとなる・・・・。

そのうちダメージが2147483648 (2^31) を超えてカンストかオーバーフローしてマイナスとかになるんじゃ??
とか変なプログラムバグの心配をしてみる(大きなお世話だ)


というわけでガンホーに怒られない限りはパソコン用ソフト、パズドラルート解析GPGPU版のサポートは続けていくつもりです。



(GPGPUといえばGeforce Titanでの解析ベンチマーク見てみたいな・・)

HSPSHAD ver1.7リリースしようか、でも・・・

パズドラルート解析PC版ではGPGPUの技術を使うため、現在製作中の自作プラグインHSPSHADを使っての作成であった。
当初は、HSPSHADのバグがあったら直したり、HSPSHADにこんな機能があったらプログラムしやすいなという課題を、解析ツールの開発をしながらピックアップしてプラグインにフィードバックしていくつもりであった。


が、その開発は困難を極めた。


ツイッターでもつぶやき発狂していたが、 バグには3種類のバグが有る。

コンパイルエラー
ランタイムエラー
理論エラー




コンパイルエラーはF5でエラーが出るタイプのバグで、ランタイムエラーは例えば0で除算しました等というやつだ。
そして理論エラーは一見正常に動いているが、プログラミングしている側がみて予想外の挙動を示してしまっているバグだ。
この理論エラーが非常に厄介。
このタイプのバグを発見するには挙動の違っている箇所を見つけ、その原因となるプログラム記述を見つけ出さなくてはならない。
そのためには、プログラム動作中に変数の中身をチェックしながら、どのタイミングで意図しない値が生まれているかはかることも必要になってくる。
最悪、同じプログラムをコピペしないで1から作り直すという究極のデバッグ方法を取らざるを得なくなる。


今回開発したルート解析GPGPU版でも、GPUの計算結果があっているのかイマイチ確信が持てず、CPUのみで動くプログラムも1から作ったのだ。
そして動かしてみたところ、計算結果は全く異なるものであった。

ここで問題なのが、計算結果が違う原因バグがどちらにあるか、または両方にあるかどうかということだ。
もしCPUのみで動く方のプログラムが完璧に合っていれば、GPGPU版の方のプログラムに問題があると言えデバッグのしがいがあるというものだ。

ではもしCPUのみで動く方のプログラムが間違っていたら?
それではGPGPU版のソースといくらにらめっこしても解決にはたどり着けない。
最初はGPGPU版にバグがあると仮定してバグを探すだろうが、なかなか原因が見当たらないとなった時、CPU動作のプログラムが絶対に合っているか確信が持てなくなってくる。
そのためにまたあってるか確かめるプログラムを作るといったイタチごっこだ。
イタチごっこといったが、たいていは、確かめプログラムは簡略化して作るので、確かめプログラムの確かめプログラム・・といつかは単純なソースになってバグが発見できるかもしれないけど。

だがそれでもやっぱり、非常に骨の折れる作業であることに間違いない!


理論エラーとはプログラマーが一番恐れるバグである。
今回の開発でも理論エラーを起こしているのを確かめるプログラムが理論エラーを起こしてしまい、嵌って多くの時間が徒労に終わった。
今回の開発でその理論エラー多発の巨悪の根源はというと「GPUでのfloat型、int型数値演算の変な仕様」のせいだと言っても過言ではない。
恐ろしいことに、同じプログラムで書いてもGPUによって計算結果が異なってしまうのだ!!

それでは、ルート解析ツールの開発途中で私が遭遇したとんでもないバグたちを紹介していこう。





・同じプログラムなのにパソコンによってレンダリングターゲットに描画できたりできなかったりする

原因1=GPUによってテクスチャの大きさが2の累乗サイズでないと使えない場合があるため。
原因2=GPUによって使えないレンダーターゲットフォーマットがあるため。
2はもっともなバグであるが、1が意外とキツい。本当は1024*1025でいいところを1024*2048で作らなくてはいけない状況があるからだ。これでは無駄なテクスチャメモリが消費されるだけでなく、そのテクスチャ上でシェーダーをかける際にも無駄な領域での演算が増えてしまう。
これを解決するにはシェーダーを掛けられる範囲を指定できるような命令を新たに追加しなくてはいけなかった。
だがこれだけですんだのでまだいい方。


・R8G8B8A8はrgbaの4要素に0~255までの値を格納できるフォーマット。だが代入した値が0~128までは合うが129~255の値は1ずれている。
原因=シェーダでは整数型テクスチャへの出力の値は全て0.0~1.0で管理するため。
0.0~0.99609375(255.0/256.0)ではない。つまりシェーダ記述内で出力(代入したいint型変数)を「float(int型)/256.0」ではなく「float(int型)/255.0」としないといけない。同じようにR16G16B16A16では「65535」で割らないといけない。


・ピクセルシェーダ内で操作している画素X座標を取得するため、テクスチャーカラー(これも座標によって0.0~1.0の値が入っている)に画面横ピクセルサイズをかけたのに、どうも(0,1,2,3,・・)というようになっていない。それもパソコンによって合ったり合ってなかったり。

原因=float型の誤差 + float型→int型に変換するときの切り捨て。
テクスチャーカラーの値は、例えば3*1の1次元テクスチャでは(0.0  , 0.33333・・ , 0.66666・・)という値が入っている。
なので3をかければ(0,1,2)となるはずなのだが、ここでfloat型の精度の問題がでてくる。
0.33333333・・・はfloat精度だとせいぜい0.333299994468689にごまかされてしまう。これでは3倍しても1.0にはならず0.9998・・といった具合になり、それをint型に変換すると0になってしまうのだ。

さてここで問題なのは、2進法で割り切れない数で乗算したときにそれが起こるということだ。例えばテクスチャの大きさが8192×8192だと、テクスチャーカラーの値は(0/8192,1/8192,2/8192・・)で、これらは全て2進法では割り切れる数字のみだ。ということは、横サイズの8192をかけたらしっかりと(0,1,2,3・・)となる。これがこのバグの発見を遅らせる罠であった。
さらに大きい罠で、GPUによってはご丁寧にfloat乗算後の四捨五入(丸め込みと言うやつ?)をしてくれるものがある。0.333299994468689×3.0が0.9998でなく1.0になってしまうのだ(いい事なんだけど)。どうりでパソコンによって演算結果が違うわけだ。
これも、このバグの発見を大きく遅らせた非常にたちの悪いバグ仕様である。

余談だがなぜテクスチャカラーの方は値のとりうる範囲が0.0~1.0ではなく0.0~(1.0-1.0/WIDTH) なのだろう。(ここでWIDTHはテクスチャ横サイズ)
先ほどの整数フォーマットのテクスチャに出力するときはしっかりと0.0~1.0にしなくてはダメなのに。本当にHLSLは謎仕様である。


・16777216+1が16777217にならない

原因=sm_30ではint型変数の四則演算は全てfloat型の回路で代用されるため。(ニセint型)
ここでfloatの内部構造を説明しよう。32bit floatは先頭1bitが正負、次の8bitが指数部、最後の23bitが仮数部である。ここで16777216 (2^24) は非常に大きい値であるためfloat型にとっては仮数部に入りきらない細かい1の位の誤差など気にしていらないのだ。16777216の次の値は仮数部の最小bitに1を加えても16777218になる。だからどうしてもfloatで16777217は表せない。仮数部が23bitしかないfloatの宿命、精度の限界というやつだ。

ではなぜシェーダーでint型の宣言はできても計算はfloatに従うのか。それはsm_30の仕様だからというもっともな回答はおいておいて、恐らくsm_30に対応した頃の古いGPUでは、まだint型の計算そのものが行なえなかったからなのではないかと推測する。
ともあれ、HSPSHADがなるべく多くの環境で実行できるようにと対応シェーダモデルを4.0でなく3.0にしてしまったのが、ここに来てとんでもない悪さをした。
この時点で、int型は-16777216~16777216までしか正しい計算ができないという縛りプレイをプログラマーに要求することになったわけだ。


・29を6で割った余りが4になる

原因=ニセint型と余剰を求める%演算子の仕様
とんでもないバグである。先ほど申したfloatの丸め込みを行なうGPUでは29%6の値はちゃんと5になる。だが丸め込みをしないGPUでは29%6が4になる。まぁint型同士の「+」演算子による加算も無理やりfloatでやられてしまうことは分かっていたから「%」演算子がfloatでやられてしまうのにはなんら不思議ではない。丸め込み機能付きGPUでしか正しい結果が得られないことを見ると、この罠は2つの合わせ技、応用トラップだということが分かる。それを示すかのように29%8の値は、どちらも同じ値を出力してくれた。8は2の累乗だからだ。

これでsm_30のシェーダ内での縛りが更に増え、int型は上限下限がたったの1600万程度なのに加え、除算と余剰演算子で右辺値に2の累乗以外を指定できないこととなる!
ここまでくるととんだ縛りプレイである。数値計算なんてできたのもではない。


・シェーダをかける範囲を指定したのに、パソコンによってかけられたシェーダ範囲が1ドットズレている

原因=範囲指定はfloat型で0.0~1.0の値で指定するため
さっきまでのバグありきの話だが、ここまでくればfloatの丸め込みか何かが悪さをしていると考えるだろう。
つまりこのバグを直すのは不可能、という事だけはよーく分かる。


・レンダリングターゲットテクスチャ(VRAM)を作成し、シェーダなどを通した後、そのテクスチャデータを取ってこようとすると2回目移行失敗する。

原因=不明
同じテクスチャから二回以上メインメモリにデータを転送できないようである。当然これも非常に困ったバグである。だがパズドラルート解析GPGPU版を作るまでこんな目立つバグに気が付かなかった・・





と、枚挙にいとまがないが大体こんな感じだ。

ボロクソ書いているけれど、そもそも大前提としてHLSLでsm_30でGPGPUをやろうなんていうのが間違い・・・HLSLは3Dゲームなどの画像処理に使うものであり数値計算用ではない。
それは分かっていたのだが、今回の開発で改めてHLSLでGPGPUをやるには限界があるということを痛感した。

とてもプラグインとして他の人に使ってもらうレベルではない。
いろんな環境でGPGPUができることようにとsm_30(シェーダーモデル3.0)を採用したのも大きな間違いであった。
3.0ではギリギリ、シェーダーでのint型変数を完全にサポートしていない。

実は4.0以降ではサポートしている上に、数値計算用に対応したDirect computeという技術がシェーダーモデル5.0からできるのだが、つい最近のグラボでかつOSはwindows 7以上でしか動かないというキツイ縛りがある。
以下にシェーダーモデルと対応OSを書いていくが、今時XPに対応していないプラグインというのはちょっときついかなと思ったのも事実だ。それにDirect X 11に対応しているグラボでないとダメというのも厳しい条件である。

シェーダーモデル2.0 : Direct X 8 : Windows XP
シェーダーモデル3.0 : Direct X 9 : Windows XP
シェーダーモデル4.0 : Direct X 10 : Windows VISTA
シェーダーモデル5.0 : Direct X 11 : Windows 7


ではXPなど少し古いPCでGPGPUができないのか調べていると、OpenCLがいいということが分かってきた。
CUDAではnVidia製のグラボでしか動かないという制約があるが、OpenCLはRadeon製でもIntel 製でも動くし、何よりDirect computeより早い!


さてもうここまでくると、HSPSHADに暗雲立ち込めて・・・なんて話ではなく、HLSLのsm_30はとんでもなく扱いに困るシロモノであった事がわかり、とりあえずこのプラグイン開発はここで打ち止め。
数値計算用であわよくば画像処理も使えていいとか豪語してたが、残念ながら数値計算では使えないようなので、HSPSHADは「シェーダー」の面影を全く残さず、OpneCLとHSPをつなぐプラグインとして生まれ変わらせるべく、1から作り直そうと思う!


「HSPでGPGPU」のために

パズドラルート解析超高速版、キャプチャ機能付き公開

ダウンロードはこちら
新しいビットマップ イメージ

パズドラに関するアプリはさらに増え今ではコンボを計算するアプリは合計で3つとなった。

その中で、自分の作ったルート解析君はあまりに遅い。
比較アプリ名は避けるが、現時点で無料のほうのコンボ計算アプリは、同じ全経路検索でウチの約4~6倍の早さということが分かっている。
有料のほうは、全経路検索ではないらしいので比較はできないが最近上から落ちてくるドロップも考慮してくれるようになったらしく、コンボ効率は更に上がっている。


そこで、計算速度改善のため抜本的な見直しを行った。


1、iPhone用に作るのではなくパソコン用に作る。 
まず一番計算速度に影響するのが、CPUのスペックである。動作周波数そのまま速度に比例する。モバイル機器のCPUはせいぜい1.5GHzとかそんなものなので、パソコンのスペックには到底かなわない。
そしてパソコンのCPUですら今では頭打ち。そこで登場するのがGPGPU技術!
これはグラフィックボードの演算能力を使ってCPUより高速に計算するというもの。

2、GPUで計算する。
現在のグラフィックボードの能力は凄まじく、1枚あれば3.7TFlofs(テラフロップス)計算できるものもある。
これはメニーコアCPUの3~100倍とも言われている。
つまるところ、単純に演算能力の高いデバイスの能力をフルに使って、ガンガン計算させようというものだ。究極の計算高速化手段だがなんとも外国人っぽい発想である。
私は1年くらい前から、シミュレーションのプログラムを高速に動かすためにGPGPUの研究を続けていた。今ちょうどHLSLを使ってGPGPUを手軽にできるHSP向けプラグインの開発をしていた所であったため、プラグイン開発と並行してパズドラルート解析の高速化バージョンを作ることとなった。
(結果的に、GPGPUソフトの開発で必要と思われる機能がうまくピックアップできプラグイン開発に昇華できた)

3、計算アルゴリズムの改善
今までは、コンボの計算アルゴリズムは非常に複雑なものであった。

1つの画面内に6×5マスの30個のドロップがある。
その中で、横3つが同じ色である、又は縦3つが同じ色である場合に、その3つのドロップをコンボ発生フラグ1とする。
次にコンボ発生フラグのあるドロップで、ドロップが縦横でつながっている、かつ同じ色ならば、それが1コンボとして計算する。
繋がっていない同色なら別コンボとして計算する。
ここで一番重要なのが「つながっている 」か判定することだ。これには塗りつぶしのアルゴリズムを使って判定していたのだが、これでは毎回コンボ発生時にコンボの数だけ塗りつぶしを実行することになり、非常に時間がかかる。

そこで、あらかじめ全てのコンボ発生パターンを記録したコンボシートなるものを作成することにした。
30ドロップを1列に直線に並べる。1つのドロップは、コンボ発生フラグ有る無しの2つのどちらかの状況しかとりえない。
このとき、30個のドロップのコンボ有る無しがとる全ての場合の数は2の30乗、つまり1073741824パターンである。
この1073741824パターンで、コンボがいくつ発生するか、全体攻撃がつくかどうかを記録したもの、それがコンボシートである。

・・・つまり、塗りつぶしの部分が要らなくなったということである。(予め計算してある。)

他にも、同色ドロップから始まる事実上全く同じといえるルートを計算から除外したり、細かい所でアルゴリズムの改善が行なわれた。


4、使用言語の変更
iPhoneアプリではインタプリタ型のHSPをつかていたので、どうしても速度に不安があった。
今回、主要な計算部分はGPUでやっているし、CPUでやらないといけない部分に関してもC++で作成してある。
だいたいHSPとC++の速度差は10倍くらいである。



という徹底した計算高速化を追求した。
そして以上の改善より、なんとアプリ版より
1086倍も高速になった!!!!!
 それもグラフィックボードがnVidia GT520の時である。これがハイエンドのものとなればさらにもう10倍は早くなろう!
これがGPGPUの威力である。
 新しいビットマップ イメージ
これはルート長16マスの設定で、1億パターンを計算し結果は47秒であった!!


他にも解析中の「計算中・・」という文字がずっと動かなくてフリーズかと思われないよう、進行度合いを表示するようにした。


さてここでこのソフトの注意点がある。
・プログラマブルシェーダーに対応していないグラフィックボードでは動かない。
(OSはXP以上、対応シェーダーモデル3.0以上 )
・最大テクスチャサイズが4096未満のものは起動しない
・計算中はGPUに非常に負荷がかかるため、動画再生やウィンドウの移動などがカクカクになる
・負荷がかかりすぎると画面が落ちる可能性がある(スペックの低いグラボだと)

と言ったもので、前者2つはかなり古いグラフィックボードで起こると予想されるが、一応少し前のノートパソコンのオンボードですら動く レベルである。
core iシリーズのIntel HD Graphicsでは確実に動くであろう。

4つめの画面落ちだが、設定で安定動作機能も付いているので低速になるがそれを試してみれば必ず動くはずだ。
設定で高速計算機能もつけた。レジストリをいじってGPUのパワーをフルに引き出せる秘技だ。これで通常解析の1.2~1.5倍は早くなうだろう!


またこれはα版である。 まだまだ、不具合が多い可能性があるので、ルートの検索結果がおかしいなどという不具合があればコメント欄にぜひ報告してほしい。
検索結果は、コンボ数の多い順ではある。


最後に完成版までに搭載する機能のピックアップだ。以下のものを予定している。
・起動時の高速化
・検索条件の設定(何色優先など)
・グラフィックの更新
・計算高速化
・ベンチマークのツイッター公開機能??


上から最優先課題として搭載していく予定だ。
 

パズドラルート解析GPGPU版は超高速!

ダウンロードはこちら
新しいビットマップ イメージ










パズドラ ドロップルート解析君 の計算の遅さは確かに自分でも問題であるとわかっていた。
 
全経路検索という手段をとっている以上、莫大な演算量を必要とするのは明らか。

というわけで今自分で開発中の「HSPSHAD」というHSP用GPGPUプラグインを使って、あったら便利だろうなと思う命令の追加や、機能向上を行ないながら同時に開発を行なっていたのが「パズドラルート解析GPGPU版」である。

そして今回、まだ精度に微妙な不安定さは残るが上からの落下も考慮したルート解析で、とりあえず正しい答えを出力することに成功!

ルート解析gpgpu

これはドロップの移動距離が11マスの時の計算結果だ。


結果

初めて正しい演算結果を出してくれたのが非常に嬉しく、思わずアップしたのだが、何が言いたいかというと驚くべきはその速度!なんとミドルレンジ(ローエンドか?)nVidia GT520で1174882通りのルート計算に、GPU 処理time 236ms(ミリ秒)、CPU 処理time 622ms。つまりルート解析アプリの300倍近い速さである!
高性能グラボならさらに早くなる!たとえノーパのオンボードGPUでもアプリの50倍以上は保証できる。

特質すべきはCPU timeというのは演算結果をコンボ数の多い順に並べたりしている時間というだけなので、ほぼ解析の本幹部分は全部GPUで演算しているということ!
つまりアプリで約3~8分くらいかけて行う計算を236msでやってのけたのである。
GPGPUの威力の高さがわかるであろう。

このプログラムはHLSLというシェーダ言語で作成されており、シェーダーモデルは3.0。
シェアードメモリも使えなければ整数演算も擬似的にしかできない。
多くのパソコン上で動くことを優先した形だが、事実上命令数制限完全撤廃されたsm5.0での動作やCUDA 上での実行ならその速度はさらに5~10倍になると予想される。

そしてまた肝心のスクリーンショット読み込みの機能が手付かずという自体になっているが、実装面ではアプリではなくPC上なのでまだ楽である。(と願いたい)


とりあえず精度を高めてインターフェイスを少し作ったら 「パズドラルート解析GPGPU版のテスト版のβ版」をアップしたいと思う。

 2/17 α版公開 ダウンロードは一番↑から
プロフィール

toropippi

記事検索
アクセスカウンター

    QRコード
    QRコード
    • ライブドアブログ