- SSEによる常微分方程式の並列計算(オイラー法) -
yosirin-hello / yosi-s@galaxy.ocn.ne.jp
| 1. はじめに |
|
| もし, 常微分方程式の高速化(並列化)ができれば,
例えば, 運動方程式で表される物体の挙動の計算の負荷を軽減することができます.
その他にも常微分方程式の計算なら何でも適用できるので,
これを研究する価値が十分にあると思いました. 研究を開始し, 机上で文献を読みながら考えていると, オイラー法ならすぐにでも高速化できると確信しました. 今回は オイラー法を用いて, 簡単のため, 1階の常微分方程式を解く計算を, SSEで並列計算させてみます. |
|
| 2. オイラー法とは |
|
オイラー法について説明する前に, 必ず理解しておかねばならない事をFig1.
にまとめました.![]() その他にも微分方程式についての知識が必要になるので[3.], [4.]を参照してください. それではオイラー法について説明します. オイラー法とは, Fig1.の方程式が表している勾配と初期条件を利用して, 次々に線形近似で解(x)の値を決定していくという方法です.(数値積分で言うと台形公式に近い考え方) その様子はFig2.のようになります.
Fig2. を見ると, 線形近似して次のxの値を計算しているので, 勾配が大きいと, すなわちhが大きいと誤差の累積が大きくなることがわかります. だから, オイラー法は, 計算を続けると誤差の累積が大きくなっていくという欠点があります. しかし, オイラー法でも初期条件で与えられた時間から, 短時間の間の範囲ならばhをうまくとってやれば実用的でしょう. |
|
| 3. オイラー法のSSE化 |
|
さて, 本題に入ります. オイラー法のSSE化は,
2つのパターンあることに気づきました. 1つ目のパターンはFig3.
です.![]() Fig3.を見ると, 従来のオイラー法とh/4の間隔で計算していくSSE化したオイラー法の誤差を比較すると, その差は明確でだということがわかります. 次の2つ目のパターンはFig4. です. ![]() Fig4. のSSE化パターン2は, 微分方程式の型が同じで, 係数だけが異なるという制約が付きますが, 4つ同時に計算できるのが魅力的です. パターン2に適用できる例としてFig5. を考えてみます.
パターン2は欠点はありますが, 互いに独立している物体のシミュレーションには最適だとおもいます. パターン1の研究をしていると重大な問題があることに気がつきまいた. その問題とは, Fig5.にあるように, SSE化できる方程式が限定されてしまうので, 実用的でないということです. ただし, 解析的に積分できない関数でも, 数値計算では離散的に解くことができるので, パターン1の考え方が将来何か役に立つかもしれません. ![]() でも, パターン1の方のSSE化は今回考えないことにします. 私は, パターン2の考え方のほうが, 気に入っているので, これをSSE化する方向で考えていきます. |
|
| 4. 並列計算させる常微分方程式の設定 |
|
今回はFig1. のような常微分方程式をSSEで並列計算させてみようとおもいます. この常微分方程式は, 初期条件でxの値をどんな値にしても, 最終的にConstに収束するという面白い性質があります. なぜ, この常微分方程式を採用したのかというと, 単に文献[3.]にそれが載っていたのと, 数値計算での解の挙動が文献と一致しているか判断しやすいからで, 特別な意味はありません. |
|
| 5. Cによる実装(SSEのシミュレーション) |
|||
まず, SSEのシミュレーションをするプログラムをCで作ってみて,
それからSSE化することを考えていきます.
EulerKernel_C( )の(1),(2),(3)がSSE化する部分のプログラムです. オーラー法の核になる部分は, かなりコンパクトなので簡単にSSE化することができそうです. |
|||
| 6. SSEによる実装
|
|||||||||||
List2. のALIGNEDは, SSEで配列を宣言する場合, 必ず書いておく必要があります. NAKEDを関数の前に書いておくと, 関数のプロローグ( push ebx, esi, edi )とエピローグ( pop, edi, esi, ebx, ret )が挿入されなくなります. (自分でプロローグとエピローグを書く必要がある) こうすることで, 関数のオーバーヘッドが少し削減されます. ちなみに, インテルの Approximate Math Library for Intel Streaming SIMD Extensions では必ず関数にnaked属性が付けられています. 詳しくはMSDNライブラリを参照して下さい.
List3. がList1. にあったODE_Func_C( )をSSE化したものです. ODE_Func_SSE_v1( )をコールする前に, XMM0〜XMM2に値をロードしておく必要があります. 計算した結果はXMM0に格納されます.
List4. はList1. にあったEulerKernel_C( )をSSE化したものです. EulerKernel_SSE_v1( )をコールする前に, XMM6にtの初期値を, XMM7にxの初期値をロードしておく必要があります. 計算した結果はXMM7に格納されます. このプログラムはXMM6, XMM7を静的(static)に使用しているので, このプログラムの外でXMM6, XMM7の値を変更するコードを書かないように心がける必要があります. XMM6, XMM7をテンポラルな形で使えるようにすればいいのですが, そうすると, 一度メモリーに計算結果を退避させる必要があるので, 最大のパフォーマンスを発揮することができません. 次に, ODE_Func_SSE_v1( )とEulerKernel_SSE_v1( )を改良したものがList5, List6です.
ODE_Func_SSE_v2( )のXMM0 〜XMM2は, 読み込み専用で使用しているので, ODE_Funcが内部でXMM0〜XMM2を変更しないようにプログラムする必要があります. だから, ODE_Func_SSE_v1( )と比べると, かなり制約が付いてプログラムが複雑になってしまうので, 不便です. しかも, プログラムのステップ数が4行も増えているので, 逆に遅くなっているようにも見えます. けれども, EulerKernel_SSE_v2( )のステップ数が減っているのと, メモリーへのアクセスがすべて無くなったことに注目して下さい. メモリーへのアクセスが無くなったことにより, EulerKernel_SSE_v1( )よりも高速に計算できる可能性が高くなります.
EulerKernel_SSE_v2( )は, かなりシンプルですが, XMM0〜XMM3を静的に(static)にしているので, EulerKernel_SSE_v1( )と同様に, このプログラムの外でXMM0〜XMM3の値を変更するコードを書かないように心がける必要があります. |
|||||||||||
| 7. SSE化したオイラー法のパフォーマンスの計測 |
|||
| パフォーマンスの計測はList7.のようにして行いました. CycleMeasureは, 計測開始ポイントから終了ポイントまでのCPUが消費したサイクル数を計測するクラスで, これをDLL化したもの使用しています.
PRE_CALCULATE=100というのは, 並列計算する常微分方程式を100ステップ先まで計算するという意味です. こうすることによって, まとめて計算させるので, CPUの計算効率を上げることができます. |
|||
| 8. 実験結果 |
|
EulerKernel_C( )とEulerKernel_SSE_v1( )とEulerKernel_SSE_v2(
)のパフォーマンスの計測結果をまとめたのがTable1.です.![]() Table1. からわかるように, SSE化することで約3倍高速化することができました. EulerKernel_SSE_v2( )はEulerKernel_SSE_v1( )と比べると若干高速化しましたが, EulerKernel_SSE_v1( )の方がプログラムのメンテナンスや使用しているレジスタを把握しやすいので, 実用ではEulerKernel_SSE_v1( )を使った方がよいでしょう. |
|
| 9. 応用例 |
|
| EulerKernel( )をコンソールアプリケーションで出力された数字の羅列だけ見ていても全然面白くありません.
EulerKernel( )を応用して, DirectXやOpenGLなどの3D系のAPIと組み合わせてみたら絶対に面白いアプリケーションが出来るとおもいます. DirectXを使用するアプリケーションで応用するとしたら, Fig8. のように, 頂点の位置の計算をする所で使用できます. ![]() Fig8. で上げた例をもっと具体化してみたものがFig9.です. 8個くらいの常微分方程式のリアルタイムでの計算ならC言語で作ったEulerKernel( )でも十分ですが, おそらく, もっと常微分方程式の数を増やしていけば, SSE化した効果が出てくるとおもいます.
|
|
| 10. 最後に |
|
| 今回の研究で, SSEで常微分方程式の並列計算が本当にできることがわかりました. これをうまく利用してやれば, 今まで以上に複雑なことができるアプリケーションができるとおもいます. 次は, オイラー法より計算精度が高いルンゲクッタ法のSSE化の研究をしようと考えています. | |
| 10. 参考文献 |
|||||||||||||
|
|||||||||||||
| 11. 改訂履歴 |
|||||||
|
|||||||
Copyright © 2002 yosirin-hello All rights
reserved.