- 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化することを考えていきます.

List1. Cによるオイラー法のプログラム(SSEのシミュレーション)
float g_Const_ODE_Func[4] = { 1.0f, 2.0f, 3.0f, 4.0f };

float ODE_Func_C( float t, float x, float constant )
{
        return ( t * ( constant - x ) ); // (1)
}


void EulerKernel_C( float* p_t, float x[4], float StepSize )
{
        x[0] += ( StepSize * ODE_Func_C( *p_t, x[0], g_Const_ODE_Func[0] ) ); //
        x[1] += ( StepSize * ODE_Func_C( *p_t, x[1], g_Const_ODE_Func[1] ) ); // 
        x[2] += ( StepSize * ODE_Func_C( *p_t, x[2], g_Const_ODE_Func[2] ) ); //
        x[3] += ( StepSize * ODE_Func_C( *p_t, x[3], g_Const_ODE_Func[3] ) ); // (2)
        *p_t += StepSize; // (3)
}

 EulerKernel_C( )の(1),(2),(3)がSSE化する部分のプログラムです.
 オーラー法の核になる部分は, かなりコンパクトなので簡単にSSE化することができそうです.
 
6. SSEによる実装
 
List2. プログラムで使用するマクロ
#define ALIGNED         __declspec( align(16) ) // 16 byteに境界する  e.g. ALIGNED float x[4];
#define NAKED           __declspec( naked )

 List2. のALIGNEDは, SSEで配列を宣言する場合, 必ず書いておく必要があります. NAKEDを関数の前に書いておくと, 関数のプロローグ( push ebx, esi, edi )とエピローグ( pop, edi, esi, ebx, ret )が挿入されなくなります. (自分でプロローグとエピローグを書く必要がある) こうすることで, 関数のオーバーヘッドが少し削減されます. ちなみに, インテルの Approximate Math Library for Intel Streaming SIMD Extensions では必ず関数にnaked属性が付けられています. 詳しくはMSDNライブラリを参照して下さい.

List3. 今回の常微分方程式をSSE化したプログラム(ver.1)
// Name         ODE_Func_SSE_v1()   
// Function     dx/dt = t * ( Const - x )
// Input
//              XMM0 : [temp] t
//              XMM1 : [temp] x
//              XMM2 : [temp] Const
// Output
//              XMM0 : t * ( Const - x )
NAKED void ODE_Func_SSE_v1()
{
        __asm {
                subps xmm2, xmm1
                mulps xmm0, xmm2
                ret
        }
}

 List3. がList1. にあったODE_Func_C( )をSSE化したものです. ODE_Func_SSE_v1( )をコールする前に, XMM0〜XMM2に値をロードしておく必要があります. 計算した結果はXMM0に格納されます.

List4. オイラー法の核(Kernel)になる部分をSSE化したプログラム(ver.1)
ALIGNED float g_StepSize[4]         = { 0.01f, 0.01f, 0.01f, 0.01f }; // t[]のキザミ値
ALIGNED float g_Const_ODE_Func[4]   = { 1.0f,  2.0f,  3.0f,  4.0f  }; // 常微分方程式の特性を決定する定数


// Name         EulerKernel_SSE_v1()        
// Function     オイラー法で常微分方程式を4つ同時に計算する
// Input
//              XMM0 : [temp] ODE_Func_v1()のパラメータt
//              XMM1 : [temp] ODE_Func_v1()のパラメータx
//              XMM2 : [temp] ODE_Func_v1()のパラメータConst
//
//              XMM6 : [static] tの初期値がロード済みのレジスタ
//              XMM7 : [static] xの初期値がロード済みのレジスタ
// Output
//              XMM6 : 1ステップ進んだ時のt[]の値
//              XMM7 : 1ステップ進んだ時のx[]の値
NAKED void EulerKernel_SSE_v1()
{
        __asm {
                movaps xmm0, xmm6 // t[]をロード
                movaps xmm1, xmm7 // x[]をロード
                movaps xmm2, [g_Const_ODE_Func]

                call ODE_Func_SSE_v1

                mulps xmm0, [g_StepSize] //
                addps xmm7, xmm0         // x[] += ( g_StepSize[] * result[] )

                addps xmm6, [g_StepSize] // t[] += g_StepSize[]
                ret
        }
}

 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です.

List5. ODE_Func_v1( )を改良したプログラム
// Name         ODE_Func_SSE_v2()   
// Function     Dy = t * ( Const - x )
// Input
//              XMM0 : [static, read only] t
//              XMM1 : [static, read only] x
//              XMM2 : [static, read only] Const
// Outout
//              XMM7 : t * ( Const - x )
// Other
//              XMM4 : [temp] Constのコピーと復元に使用
NAKED void ODE_Func_SSE_v2()
{
        __asm {
                movaps xmm4, xmm2 // Constをxmm4にコピー
                subps  xmm2, xmm1
                mulps  xmm2, xmm0
                movaps xmm7, xmm2
                movaps xmm2, xmm4 // xmm2を復元
                ret
        }
}

 ODE_Func_SSE_v2( )のXMM0 〜XMM2は, 読み込み専用で使用しているので, ODE_Funcが内部でXMM0〜XMM2を変更しないようにプログラムする必要があります. だから, ODE_Func_SSE_v1( )と比べると, かなり制約が付いてプログラムが複雑になってしまうので, 不便です. しかも, プログラムのステップ数が4行も増えているので, 逆に遅くなっているようにも見えます.
 けれども, EulerKernel_SSE_v2( )のステップ数が減っているのと, メモリーへのアクセスがすべて無くなったことに注目して下さい. メモリーへのアクセスが無くなったことにより, EulerKernel_SSE_v1( )よりも高速に計算できる可能性が高くなります.

List6. EulerKernel_v1( )を改良したプログラム
// Name         EulerKernel_SSE_v2()        
// Function     オイラー法で常微分方程式を4つ同時に計算する
// Input
//              XMM0 : [static] ODE_Func_v2()のパラメータt
//              XMM1 : [static] ODE_Func_v2()のパラメータx
//              XMM2 : [static] ODE_Func_v2()のパラメータConst
//              XMM3 : [static] t[]のキザミ値StepSize
// Output
//              XMM0 : 1ステップ進んだ時のt[]の値
//              XMM1 : 1ステップ進んだ時のx[]の値
// Other
//              XMM7 : [temp] ODE_Func_SSE_v2()の計算結果
NAKED void EulerKernel_SSE_v2()
{
        __asm {
                call ODE_Func_SSE_v2

                mulps xmm7, xmm3 //
                addps xmm1, xmm7 // x[] += ( g_StepSize[] * result[] )

                addps xmm0, xmm3 // t[] += g_StepSize[]
                ret
        }
}

 EulerKernel_SSE_v2( )は, かなりシンプルですが, XMM0〜XMM3を静的に(static)にしているので, EulerKernel_SSE_v1( )と同様に, このプログラムの外でXMM0〜XMM3の値を変更するコードを書かないように心がける必要があります.
7. SSE化したオイラー法のパフォーマンスの計測

 パフォーマンスの計測はList7.のようにして行いました.
 CycleMeasureは, 計測開始ポイントから終了ポイントまでのCPUが消費したサイクル数を計測するクラスで, これをDLL化したもの使用しています.

List7. パフォーマンスを計測するプログラム
#include "CycleMeasure.h"
#pragma comment( lib, "CycleMeasure.lib" )

#define SAMPLE          100 // サンプル数
#define PRE_CALCULATE   100 // 1回のループで常微分方程式を計算する回数

#define PRINT_RESULT    \
                        printf("\t t = %6.2f, x = (%f,%f,%f,%f)\n", t[0], x[0], x[1], x[2], x[3] );

void PerformanceTest_EulerKernel_C()
{
        int i, j;
        CycleMeasure cm;
        UINT64 cycle[SAMPLE];
        ALIGNED float x[4] = { 0.5f, 0.5f, 0.5f, 0.5f };
        ALIGNED float t[4] = { 0.1f, 0.1f, 0.1f, 0.1f };

        for( i = 0; i < SAMPLE; i++ ) {
                cm.Begin();
                for( j = 0; j < PRE_CALCULATE; j++ )
                        EulerKernel_C( t, x, 0.01f );
                cm.End();
                cycle[i] = cm.GetCycle();
                // PRINT_RESULT
        }

        // printf()が上のループで影響を与えるため, ループを分離している
        printf("EulerKernel_C()のパフォーマンステストの結果\n");
        for( i = 0; i < SAMPLE; i++ )
                printf("%d [cycles]\n", cycle[i]);
}


void PerformanceTest_EulerKernel_SSE_v1()
{
        int i, j;
        CycleMeasure cm;
        UINT64 cycle[SAMPLE];
        ALIGNED float x[4] = { 0.5f, 0.5f, 0.5f, 0.5f };
        ALIGNED float t[4] = { 0.1f, 0.1f, 0.1f, 0.1f };

        __asm {
                movaps xmm6, [t] // t[]をXMM6へロード
                movaps xmm7, [x] // x[]をXMM7へロード
        }

        for( i = 0; i < SAMPLE; i++ ) {
                cm.Begin();
                for( j = 0; j < PRE_CALCULATE; j++ ) {
                        __asm {
                                call EulerKernel_SSE_v1
                                movaps [t], xmm6 // XMM6をt[]にストア
                                movaps [x], xmm7 // XMM7をt[]にストア
                        }
                }
                cm.End();
                cycle[i] = cm.GetCycle();
                // PRINT_RESULT
        }

        // printf()が上のループで影響を与えるため, ループを分離している
        printf("EulerKernel_SSE_v1()のパフォーマンステストの結果\n");
        for( i = 0; i < SAMPLE; i++ )
                printf("%d [cycles]\n", cycle[i]);
}


void PerformanceTest_EulerKernel_SSE_v2()
{
        int i, j;
        CycleMeasure cm;
        UINT64 cycle[SAMPLE];
        ALIGNED float x[4] = { 0.5f, 0.5f, 0.5f, 0.5f };
        ALIGNED float t[4] = { 0.1f, 0.1f, 0.1f, 0.1f };

        __asm {
                movaps xmm0, [t] // t[]をXMM1へロード
                movaps xmm1, [x] // x[]をXMM6へロード
                movaps xmm2, [g_Const_ODE_Func]
                movaps xmm3, [g_StepSize]
        }

        for( i = 0; i < SAMPLE; i++ ) {
                cm.Begin();
                for( j = 0; j < PRE_CALCULATE; j++ ) {
                        __asm {
                                call EulerKernel_SSE_v2
                                movaps [t], xmm0 // XMM0をt[]にストア
                                movaps [x], xmm1 // XMM1をt[]にストア
                        }
                }
                cm.End();
                cycle[i] = cm.GetCycle();
                // PRINT_RESULT
        }

        // printf()が上のループで影響を与えるため, ループを分離している
        printf("EulerKernel_SSE_v2()のパフォーマンステストの結果\n");
        for( i = 0; i < SAMPLE; i++ )
                printf("%d [cycles]\n", cycle[i]);
}

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. 参考文献

1. 情報工学入門シリーズ5 数値計算法 第2版, 森北出版株式会社
2. プログラミング入門シリーズ7 コンピュータによる数値計算, 朝倉書店
3. 理工系の数学入門コース4 常微分方程式, 岩波書店
4. 数理科学ライブラリー5 微分方程式の基礎, 朝倉書店
5. 理工系のための力学, 学術図書出版社
6. Microsoft MSDN Library
11. 改訂履歴

改訂 履歴 日付
1.0 仕上げて公開 03/17/2002


Copyright © 2002 yosirin-hello All rights reserved.