Black-Scholes option calculation in MUDA

by syoyo

MUDA で Black-Scholes オプションプライシングの計算をやってみました.

http://lucille.svn.sourceforge.net/viewvc/lucille/angelina/haskellmuda/examples/BlackScholes/

参考にしたのは CUDA の SDK から.


static always_inline vec cndMUDA(vec d)
{
        vec A1 = 0.31938153f;
        vec A2 = -0.356563782f;
        vec A3 = 1.781477937f;
        vec A4 = -1.821255978f;
        vec A5 = 1.330274429f;
        vec RSQRT2PI = 0.3989422804f;

        vec K = 1.0f /. (1.0f + 0.2316419f * abs(d));

        vec cnd = RSQRT2PI * exp(-0.5f * d * d) * (K * (A1 + K * (A2 + K * (A3 + K * (A4 + K * A5)))));

        vec one_minus_cnd = 1.0f - cnd;

        vec ret = sel(cnd, one_minus_cnd, d > 0.0);

        return ret;
}

void BlackScholesMUDA(
        out vec retCall,
        out vec retPut,
        vec S,                  // Stock price
        vec X,                  // Option strike
        vec T,                  // Option years
        vec R,                  // Riskfree rate
        vec V)                  // Volatility rate
{

        vec sqrtT = sqrt(T);
        vec d1 = (log(S /. X) + (R + 0.5f * V * V) * T) /. (V * sqrtT);
        vec d2 = d1 - V * sqrtT;

        vec cnd_d1 = cndMUDA(d1);
        vec cnd_d2 = cndMUDA(d2);

        vec expRT = exp(-1.0f * R * T);

        retCall = S * cnd_d1 - X * expRT * cnd_d2;
        retPut  = X * expRT * (1.0f - cnd_d2) - S * (1.0f - cnd_d1);

}


[Perf] CPU = 57.740000 (msec) 13.855213 MOps/sec
[Perf] MUDA = 23.450000 (msec) 34.115139 MOps/sec

(on Core2 2.16 GHz, 64bit, using 1 core)

うーん、SIMD 化(MUDA 化)しても 3 倍程度ですね.

この BlackScholes 関数は put と call を同時に計算するので、関数は

34.11M / 2 = 17 M 回/sec

呼ばれていることになります.

理論 GFLOPS と比べると、

2.16 GHz * 4(SIMD) * 2(add/mul) / 17 M = 1016.5 flops / function

となります.

関数の disassemble 結果は約 560 instruction なので、
実行効率はピークの 1/2 程度ということになります.

ただ、今回の BlackScholes 関数は、1つの put & call の計算に必要な
演算子数(exp や log も 1 とカウント)はおよそ 67 個なので、
インストラクション数と大きなへだたりがあります.

この原因は、exp や log などの特殊関数によります.
CPU(SSE) ではこれらに相当する関数がないので、
SW で対応しなければりません.

MUDA では, ほぼ libm の結果と一致する特殊関数の実装を使っていて、
だいたい 1 関数あたり 100 ~ 160 インストラクションくらいかかります.

特殊関数を除いた BlackScholesMUDA 関数は、
およそ 135 instructions になり,
Mops/sec も 130 Mops/sec になります
(結果はもちろんリファレンスと一致しませんが)

つまり 3/4 ほどが、exp, log などの演算に費やされていることになります.
精度が必要なければ、特殊関数はより演算量の少ない近似計算に置き換えることもできますが、
すこし試してみたところでは誤差がひどかったので、今回は考えないことにしました.
(金融分野での利用ということもあり、そこそこの精度が必要だろうし)

特殊関数を除くと

特殊関数を除いたバージョンでも、265.85 flops/function となり、
135 instructions / function と比較すると、
理論ピークの半分くらいのパフォーマンスしか出せていません.
add/mul/mov 同時実行を考慮して、
ピーク値の 2/3 くらいは出るかなと思ったのですが.
演算部分ではなく、デコーダや帯域の部分がネックなのかもしれません.

GPU では

対して、g80 では 4.7 Gops/sec できると報告されています.
(ここでも、put & call を同時に計算するので ops の値は 2 倍)

1.35(GHz) * 128(SP) / (4.7 / 2) = 147 flops / function

SFU の flops も考慮する必要が本当はある(SPU はまた mul も可能)が、
ここでは考えないことにした.

対応する .ptx のコードは約 138 instructions.
SFU の演算量を考慮したとしても、
ほぼ理論ピーク値で実行できていると言えるだろう.

まとめ

– exp や log などの特殊関数の計算は、CPU ではネック.

今回の BS 計算の例題においては、特殊関数の計算は 3/4 を占める.
対して、GPU では HW 実装されているので効率的に処理できている.
(latency はちょっと大きいですが、pipeline 実行で隠蔽できているようだ)
ここが GPU が x100 とか x400 早いなどと、
理論 GFLOPS 以上の乖離が出来る原因と言えよう.

特殊関数がネックというのは、これは

Application Optimization and Performance Evaluation of a Multithreaded GPU Using CUDA

でも指摘されている.

– CPU は、理論 FLOPS に対して 1/2 程度のパフォーマンス

add/mul 同時実行はきちんと実行できるているのだろうか?
やはりインストラクションシミュレータがほしい.

– BlackScholes 計算が早いことの有益度は?

で、結局のところ、このような多量のインプットに対して classic な Black-Scholes
を計算する需要というのはベンチマーク以外にどれくらいあるのだろうか?

front トレーダーはたぶん financial cad とか使うだろうし,
algorithm trading や back office で使うにしても、
classic な Black-Scholes analysic 解なんていまさら dominant に使わないだろうし.

近年だと analysic に求められない option pricing のほうが
主要だと思う(バリアオプションとかね).

そんなわけで次やるとしたら, プレインバニラじゃなくて、
もうちょっとエキゾチックなやつとか、
MC(monte carlo) option pricing かな.

おまけ

金融 IT フォーカス 2008 年 4 月号
交通渋滞と株式投資
http://www.nri.co.jp/opinion/kinyu_itf/index.html

交通渋滞の理論と株式投資の理論には関連性があるのではないか、
というエッセイ.

日本も金融立国が叫ばれて久しい, というかそうしていかないとヤバいわけですが、
レンダラ(大域照明)と金融の融合ももっとあっていいような気がします.
すでに LDS とか関連項目はありますが, まだまだあっていいかなと.

大域照明が扱う関数は discontinuity ありまくりで、
株価でいえば $100 だった株価が次の日には $0.1 に、
その次の日には $100 などというような極端な株価推移をすることに
相当します(一方は関数は spatial, 他方は temporal という違いはありますが).

このような関数に対する研究は、金融方面にもなにか役立つと思うんですよね.
一応 jump を考慮した 株価モデルや option 計算モデルとか提案されているようですが、
まだまだ大域照明が扱っている関数はそんなヤワなもんじゃないよ、と.

Advertisements