前回は、下記の論文で言うところのセル分割法を実装してみましたが、二つ目の手法、粒子登録法を組んでみました。

GPUによる近接相互作用に基づく粒子計算の近傍探索手法
https://ipsj.ixsq.nii.ac.jp/ej/?action=repository_uri&item_id=107323&file_id=1&file_no=1

出力結果は同じ（動画省略）。さぁ、速度はどうだ。

全粒子判定 1ステップあたり0.039175秒
セル分割法 1ステップあたり0.023670秒（1.65倍）
セル分割法＋粒子登録法 0.022526秒（1.73倍）

・・・速くなり・・・ました。ちょっぴしだけど。

論文では、セル分割法単体と比べ、3倍以上の高速化となってますが、今回はそうはなりませんでした。

コードが良くない可能性は大いにあるけども、一応、セル分割法の候補が粒子登録法によって、1/3〜半分程度に抑えられることは確認。ただし、更新頻度が多いので、そっちに処理を食っている模様。試しに更新を判定するアルゴリズムはそのままに、粒子登録法の絞り込みをコメントアウトしてみると・・・

セル分割法＋粒子登録法 0.022526（1.73倍）
セル分割法＋更新判定のみ 0.022452（1.74倍)

変わらーん。むしろ絞り込みしない方が速いー。っとの結果になりましたorz

粒子登録法は、コードがごちゃごちゃするので、いっそ無くしてしまうか・・・？まぁでも、更新頻度が少ない解析なら、効果を発揮するやもしれぬ。って事で、アルゴリズム的な改良は一旦終了させて、モデルの検討をやっていきたいと思います。

(さらに…)

やりたいことは、色々なモデルを試すこと。プログラムは遅くたって最低限動けばよし！次はモデルをいじるぞ！

っと思っていたのですが、プログラムを眺めてると、さすがに全て粒子で、全ての粒子に対する当たり判定するのは、無駄だよな～っと気になりだし、何となくアルゴリズムを考えるようになったところに、下記の論文を見つけました。

GPUによる近接相互作用に基づく粒子計算の近傍探索手法
https://ipsj.ixsq.nii.ac.jp/ej/?action=repository_uri&item_id=107323&file_id=1&file_no=1

アルゴリズムの中身がけっこう丁寧に書いてある。これなら実装できそうだ。っと思ってしまったからには・・・やりますか。

書かれてる手法は、大きく2つ。

一つは領域を格子に分割して、格子内の粒子を登録しておき、自身がある格子とその周辺の格子内の粒子に対してのみに当たり判定を行う方法。上の論文では、セル分割法と名付けられている。オーソドックスな方法みたいで、他の文献では、格子判定法だとか色々なネーミングがありました。

もう一つは、一度は全粒子に対して当たり判定をして、その際、近くの粒子を登録しておき、一定期間は、登録した粒子に対してのみに当たり判定を行う方法。上の論文では、粒子登録法とネーミングされています。

どちらも一定条件の元、情報を更新しなくてはいけない。セル分割法は粒子の数だけの一回ループで情報更新できるのに対して、粒子登録法は粒子数の2乗ループが必要になるので時間がかかる。しかし、粒子登録法はセル分割法に比べ、登録する候補粒子を少なくすることができる。また、論文では書かれていないけど、わざわざ全体の情報を更新しなくても、動きのある粒子に対してのみ情報を更新させることもできるはず。

メモリ消費量の違いもあるけど、今のところメモリは問題ない（多分、2次元なら問題にならない）ので考えません。

論文を見る前に、自分で思いついたのは、粒子登録法の方です。通常、土の解析だと激しく動く箇所は一部だから、相対移動量とか拾って、上手いこと更新範囲と回数を抑えるアルゴリズムにすれば、いい感じになるんじゃね？っと思ったのだけど、その更新判定の部分を作るの大変そう。
論文では、セル分割法と粒子登録法の両方を組み合わせたハイブリッドなやり方が書かれてあり、考えるの面倒だから、その通りやってみることにしよう。

ってことで、まずセル分割法を導入してみました。とりあえず、登録情報は毎回更新する仕様。

よしよし、結果は同じだな。さて、計算速度は？

(さらに…)

前回のプログラムを、バク直したり、使いたくないかったポインタ変数使ってみたりして、一区切りついた感じなので、投稿しときます。

この先は、土木屋っぽく土を疑似するように必要な機能を実装していく予定。

(さらに…)

前回のプログラムを要素数492ほどで試してみたら、ネットブック(Acer Aspire One HAPPY2）では、1ステップで2.55秒もかかりました。お、おう。ネットブックで解析を回すつもりは無いとはいえ、最低でも1万ステップくらい回すことを踏まえるとさすがに遅い。ノートPC（Dell Inspiron14 core i3-4010U）でも0.63秒で4倍くらい速いものの、全然遅い。勉強用とはいえ、5000要素で1万ステップくらいは１分以内でやってほしい。1ステップで0.005秒くらいとなると、100倍以上の高速化が必要だ。

Pythonが他のプログラムに比べても演算の処理速度が遅いことは知っていたので、最終段階で高速化しようと思っていたけども、現時点で、高速化しないと色々遊んでみることもままならなさそう・・・。っということで、Cython化してみました。

(さらに…)

３といっても新しいことはしていないのだけど。

前回記事のPythonプログラムは、PySideというGUIモジュールを使っているのだけど、考えてみれば、解析の様子を見せるだけなので、標準GUIの方が良いよなぁっと思って、Tkinterに書き換えました。・・・それだけ、です。

(さらに…)