=Paper=
{{Paper
|id=Vol-1787/289-294-paper-49
|storemode=property
|title=Оптимизация алгоритмов вычисления опционов на гибридной системе
(Optimization algorithm for computing options for the hybrid system)
|pdfUrl=https://ceur-ws.org/Vol-1787/289-294-paper-49.pdf
|volume=Vol-1787
|authors=Dmitry Khmel,Eduard Stepanov,Alexsandr Bogdanov
}}
==Оптимизация алгоритмов вычисления опционов на гибридной системе
(Optimization algorithm for computing options for the hybrid system)==
https://ceur-ws.org/Vol-1787/289-294-paper-49.pdf
Оптимизация алгоритмов вычисления опционов на
гибридной системе
Д. С. Хмельа, Э. А. Степановb, А. В. Богдановс
Ñàíêò-Ïåòåðáóðãñêèé ãîñóäàðñòâåííûé óíèâåðñèòåò,
îññèÿ, 199034, Ñàíêò-Ïåòåðáóðã, Óíèâåðñèòåòñêàÿ íàá. ä.7-9.
E-mail: a dskhmel .spbu.ru, b e.an.stepanovgmail. om, bogdanov sa.ru
 ñòàòüå ðàññìîòðåíà ïðîáëåìà îïòèìèçàöèè àëãîðèòìîâ öåíîîáðàçîâàíèÿ îïöèîíîâ íà
GPGPU. Îñíîâíàÿ öåëü äîáèòüñÿ ìàêñèìàëüíîé ý åêòèâíîñòè îò èñïîëüçîâàíèÿ ãèáðèä-
íîé ñèñòåìû. Àâòîðàìè áûëè ïðåäëîæåíû íåêîòîðûå ïðåîáðàçîâàíèÿ àëãîðèòìà, ïîëó÷åí-
íîãî èç ìîäåëè Áëåêà-Øîóëçà, äëÿ öåíîîáðàçîâàíèÿ åâðîïåéñêîãî è àçèàòñêîãî îïöèîíà ïî
ìåòîäó Ìîíòå-Êàðëî ñ ó÷åòîì îñîáåííîñòåé àðõèòåêòóðû GPGPU. Îñíîâíîé èäååé îïòè-
ìèçàöèè ÿâëÿåòñÿ ïîñòîÿííàÿ ðàáîòà ñ îäíèì áîëüøèì ìàññèâîì äàííûõ.
Êëþ÷åâûå ñëîâà: åâðîïåéñêèé îïöèîí, àçèàòñêèé îïöèîí, ãèáðèäíàÿ ñèñòåìà, GPGPU,
CUDA, ìåòîä Ìîíòå-Êàðëî
àáîòà âûïîëíåíà ïðè ïîääåðæêå ãðàíòîâ ÔÔÈ:
17-57-80111 FTRC-HPC: Âûñîêîïðîèçâîäèòåëüíûå âû÷èñëåíèÿ ñ ñåòåâûìè ðåêîí èãóðèðóåìûìè îòêàçî-
óñòîé÷èâûìè âû÷èñëèòåëüíûìè óñòðîéñòâàìè,
16-57-48005 Ìóëüòè-FPU íà êðèñòàëëå (MFoC) äëÿ ïðèëîæåíèé âûñîêîïðîèçâîäèòåëüíûõ âû÷èñëåíèé,
16-07-01111 Ïîñòðîåíèå Unix-ïîäîáíîãî îêðóæåíèÿ äëÿ óïðàâëåíèÿ âèðòóàëüíûì ñóïåðêîìïüþòåðîì.
2016 Äìèòðèé Ñåðãååâè÷ Õìåëü, Ýäóàðä Àíàòîëüåâè÷ Ñòåïàíîâ, Àëåêñàíäð Âëàäèìèðîâè÷ Áîãäàíîâ
289
Введение
Çà ïîñëåäíåå âðåìÿ ïðîèñõîäèò çíà÷èòåëüíîå óâåëè÷åíèå îáúåìà òîðãîâ íà ðûíêå
öåííûõ áóìàã. Çàäà÷à ïîèñêà öåíû òîé èëè èíîé öåííîé áóìàãè ñ ìàòåìàòè÷åñêîé òî÷êè
çðåíèÿ èìååò äîâîëüíî ñïåöè è÷åñêèé õàðàêòåð. Îñíîâíûì òðåáîâàíèåì ÿâëÿåòñÿ ñêîðîñòü
âû÷èñëåíèé, ãäå âàæíû äàæå ìèëëèñåêóíäû, òàê êàê íà ïðàêòèêå îíè ìîãóò ñòîèòü áîëü-
øèõ äåíåã ó÷àñòíèêó òîðãîâ. Ñ äðóãîé ñòîðîíû, èç ïðèíöèïîâ óíêöèîíèðîâàíèÿ ðûíêà
ñëåäóåò, ÷òî â äàííîé çàäà÷å íå òðåáóåòñÿ âûñîêîé òî÷íîñòè âû÷èñëåíèé.
Ïðè ðåøåíèè ðàññìàòðèâàåìîé çàäà÷è áîëüøóþ ïîïóëÿðíîñòü ñåãîäíÿ èìååò ìåòîä
Ìîíòå-Êàðëî. Îí ïîçâîëÿåò äîñòè÷ü íåîáõîäèìîé òî÷íîñòè âû÷èñëåíèé, íî ïðè ýòîì íå
îáëàäàåò äîñòàòî÷íîé ý åêòèâíîñòüþ. Ýêñïåðèìåíòû ïîêàçûâàþò, ÷òî â çàâèñèìîñòè îò
òî÷íîñòè, ïîèñê öåíû îïöèîíà ìîæåò çàíèìàòü äî íåñêîëüêèõ äåñÿòêîâ ñåêóíä èëè äàæå äî-
õîäèòü äî íåñêîëüêèõ ìèíóò. Ïîìèìî óâåëè÷åíèÿ âû÷èñëèòåëüíîé ìîùíîñòè èñïîëüçóåìûõ
ÝÂÌ, â äàííîé çàäà÷å ïðèñóòñòâóþò çíà÷èòåëüíûå âîçìîæíîñòè îïòèìèçàöèè íà àëãîðèò-
ìè÷åñêîì è ïðîãðàììíîì óðîâíå, êîòîðûå è áóäóò ðàññìîòðåíû íèæå.
 ïðåäñòàâëåííîé ñòàòüå ðàññìàòðèâàåòñÿ âîçìîæíîñòü ðàñ÷åòà öåíû îïöèîíà íà ãè-
áðèäíûõ ñèñòåìàõ ñ èñïîëüçîâàíèåì àðõèòåêòóðû CUDA.  êà÷åñòâå îñíîâû äëÿ ÷èñëåííûõ
ýêñïåðèìåíòîâ áûëè âûáðàíû åâðîïåéñêèé è àçèàòñêèé îïöèîíû. Äëÿ ïîèñêà èõ öåíû ðàñ-
ñìàòðèâàåòñÿ ìîäåëü, êîòîðàÿ îïèñûâàåòñÿ êîíòèíóàëüíûì èíòåãðàëîì.
Постановка задачи
 ðàìêàõ äàííîé ñòàòüè áóäóò èñïîëüçîâàòüñÿ ñëåäóþùèå îáîçíà÷åíèÿ: S (t) óíê-
öèÿ âðåìåíè, îïèñûâàþùàÿ äèíàìèêó èçìåíåíèÿ öåíû áàçîâîãî àêòèâà. Áóäåì ðàññìàòðè-
âàòü îïöèîííûé êîíòðàêò ñ ïåðèîäîì äåéñòâèÿ [0, T ] è öåíîé èñïîëíåíèÿ K . Ïðåäïîëîæèì,
÷òî S 0 = S (0), x =R ln S , Ceu (S , t) öåíà åâðîïåéñêîãî îïöèîíà, Cas (S , I, t) öåíà àçèàòñêîãî
T
îïöèîíà, ãäå I = 0 S (τ)dτ.
Èñõîäíûé âðåìåííîé ïðîìåæóòîê ðàçîáüåì íà ðàâíûå ÷àñòè äëèíîé ∆t òî÷êàìè t0 <
t1 < · · · < tn < tn+1 , ïðè÷åì t0 = 0, tn+1 = T . Ïðè ðåøåíèè çàäà÷è öåíîîáðàçîâàíèÿ îïöèîíîâ
íà ãèáðèäíîé ñèñòåìå áûëà ïðèìåíåíà ìîäåëü, îñíîâàííàÿ íà êîíòèíóàëüíîì èíòåãðàëå:
Z+∞ Z+∞
Ceu (S 0 , 0) = e−rT . . . dx1 . . . dxn dxn+1 max{exn+1 − K, 0} ×
−∞ −∞
n+1 " (1)
#
1
X
1
2
× 2 (n+1)/2
exp − 2
[xi − (xi−1 + µ∆t)]
(2πσ ∆t) 2σ ∆t
i=1
σ2
µ=r−
2
ãäå r áåçðèñêîâàÿ ïðîöåíòíàÿ ñòàâêà, σ âîëàòèëüíîñòü. Ïîäðîáíîñòè ìîæíî íàéòè â
ðàáîòàõ [Montagna, Ni rosini, Moreni, 2002℄, [Lientsky, 1997℄.
Ïðè ïîìîùè äàííîãî êîíòèíóàëüíîãî èíòåãðàëà îïðåäåëÿåòñÿ öåíà áàçîâîãî àêòèâà â
ìîìåíò èñïîëíåíèÿ îïöèîíà.
Äëÿ ïðîãðàììèðîâàíèÿ ïðèâåäåííîãî âûøå âûðàæåíèÿ íåîáõîäèìî âûïîëíèòü ñëå-
äóþùèå îñíîâíûå ñòàäèè àëãîðèòìà:
290
1. åíåðàöèÿ íàáîðà ñëó÷àéíûõ ÷èñåë ( x0 , x1 , . . . , xn , xn+1 ), òàêèì îáðàçîì, ÷òîáû ïëîò-
íîñòü ðàñïðåäåëåíèÿ êàæäîãî x áûëà ðàâíà:
( )
1 1
f (x) = √ exp − 2 [x − (xi−1 + µ∆t)] . 2
(2)
2πσ2 ∆t 2σ ∆t
2. Ïîäñòàâèòü xn+1 â ïîäûíòåãðàëüíóþ óíêöèþ:
S (T ) = max{exn+1 − K, 0}. (3)
3. Âû÷èñëèòü îïöèîí ïî îðìóëå:
N
1 X
C(S , t) = e−rT S i.
N i=1
Äëÿ ðàñ÷åòà èíòåãðàëà íåîáõîäèìî ñãåíåðèðîâàòü íàáîð ñëó÷àéíûõ ÷èñåë òàêèì îá-
ðàçîì, ÷òî ïëîòíîñòü êàæäîãî èç íèõ çàâèñèò îò ïðåäûäóùåãî. Â ýòîì êðîåòñÿ îñíîâíàÿ
ïðîáëåìà äëÿ ïàðàëëåëèçìà.  ñëó÷àå åâðîïåéñêîãî îïöèîíà íåîáõîäèìî âçÿòü ïîñëåäíåå
ñëó÷àéíîå ÷èñëî èç íàáîðà è ïîäñòàâèòü â óíêöèþ S(T).
Ïåðâûé è âòîðîé ýòàï ÿâëÿþòñÿ îäíîé èòåðàöèåé Ìîíòå-Êàðëî. Äëÿ òî÷íîñòè âû÷èñ-
ëåíèé íåîáõîäèìî âûïîëíèòü êàê ìîæíî áîëüøå òàêèõ èòåðàöèé. Ïîñëå ÷åãî ïîäñòàâèòü
ïîëó÷åííûé ðåçóëüòàò â îðìóëó âû÷èñëåíèÿ îïöèîíà.
Äëÿ èçáàâëåíèÿ îò çàâèñèìîñòè íåîáõîäèìî ïðîâåñòè íåñêîëüêî ìàòåìàòè÷åñêèõ ïðå-
îáðàçîâàíèé.
Модернизация алгоритма
Èç îðìóëû ïëîòíîñòè ðàñïðåäåëåíèÿ ñëó÷àéíîé âåëè÷èíû xi (2) ñëåäóåò, ÷òî îíà
ðàñïðåäåëåíà ïî íîðìàëüíîìó çàêîíó
√
xn ∼ N(µ∆t + xn−1 , σ ∆t),
√
ñ ìàòåìàòè÷åñêèì îæèäàíèåì M[x] = µ∆t + xn−1 è äèñïåðñèåé D[x] = σ ∆t.
Òîãäà xi ìîæíî ïîëó÷èòü èç ñëó÷àéíîé âåëè÷èíû ξi ∼ N(0, 1) ñëåäóþùèì îáðàçîì:
xn = M[x] + D[x] ξn .
Èëè, ïîäñòàâëÿÿ âûðàæåíèÿ äëÿ M[x] è D[x], èìååì:
√
xn = µ∆t + xn−1 + σ ∆t ξn . (4)
Ïðåîáðàçóåì äàííîå âûðàæåíèå ê áîëåå óäîáíîìó âèäó, äëÿ ýòîãî çàìåòèì:
√ √ √
xn+1 = ξn+1 σ ∆t + µ∆t + xn = ξn+1 σ ∆t + µ∆t + ξn σ ∆t + µ∆t + xn−1 =
√ √ X n+1
= (ξn+1 + ξn )σ ∆t + 2µ∆t + xn−1 = σ ∆t ξi + (n + 1)µ∆t + x0 .
i=1
Òàêèì îáðàçîì èìååì:
√ X n+1
xn+1 = σ ∆t ξi + (n + 1)µ∆t + x0 .
i=1
291
 êîíå÷íîì èòîãå, äëÿ ïîëó÷åíèÿ ñëó÷àéíîé âåëè÷èíû xn+1 òðåáóåòñÿ ïðîñóììèðî-
âàòü ñãåíåðèðîâàííûé ìàññèâ
√ ñëó÷àéíûõ ÷èñåë ñî ñòàíäàðòíûì íîðìàëüíûì ðàñïðåäåëå-
íèåì, ïîìíîæèòü åãî íà σ ∆t è ïðèáàâèòü çíà÷åíèå âûðàæåíèÿ (n + 1)µ∆t + x0 , êîòîðîå
ðàññ÷èòûâàåòñÿ çàðàíåå.
Ïðåèìóùåñòâî äàííîé ìîäè èêàöèè çàêëþ÷àåòñÿ â òîì, ÷òî â íåé îòñóòñòâóþò çà-
âèñèìîñòè, ïîýòîìó å¼ ìîæíî ëåãêî çàïðîãðàììèðîâàòü è ïîëó÷èòü óñêîðåíèå, èñïîëüçóÿ
CUDA èëè OpenCL íà ãèáðèäíîé ñèñòåìå.
Îòëè÷èå àçèàòñêîãî îïöèîíà ñîñòîèò ëèøü â òîì, ÷òî åãî ñòîèìîñòü âû÷èñëÿåòñÿ ïî
îðìóëå:
Z+∞ Z+∞ !N/2
−rT 1
Cas (S 0 , I0 , 0) = e . . . dxN . . . dx1 ×
2πσ2 ∆t
−∞ −∞
N
X 1
2
(5)
× exp − 2 ∆t
[xn − (x n−1 + µ∆t)] ×
2σ
n=1
PN
∆t n=1 I(xn , xn−1 , ∆t)
× max − K, 0 ,
T
ãäå
σ2 ∆t σ2 ∆t σ2 ∆t σ2 ∆t
! !
xn 1 xn−1 1
I(xn , xn−1 , ∆t) = e + − +e − + + ,
∆xn 2∆x2n ∆x3n ∆xn 2∆x2n ∆x3n
Òàêèì îáðàçîì, âñå ðàññóæäåíèÿ äëÿ åâðîïåéñêîãî îïöèîíà îñòàþòñÿ ñïðàâåäëèâûìè è äëÿ
ñëó÷àÿ àçèàòñêîãî îïöèîíà, òîëüêî îðìóëà (3) áóäåò èìåòü âèä:
PN
∆t n=1 I(xn , xn−1 , ∆t)
S (T ) = max − K, 0 .
T
Эксперименты
èñ. 1. Óñêîðåíèå âû÷èñëåíèé íà GPU
292
Âîïðîñ ñõîäèìîñòè ïðåäñòàâëåííîãî àëãîðèòìà áûë èññëåäîâàí ðàíåå â ðàáîòå
[Bogdanov, Stepanov, Khmel, 2015℄. Â äàííîì ýêñïåðèìåíòå ñðàâíèâàåòñÿ âðåìÿ ðàáîòû ïî-
ñëåäîâàòåëüíîãî àëãîðèòìà íà CPU (Intel Xeon) è ïàðàëëåëüíîãî íà GPU (Tesla K40M). Íà
ðèñ. 1 ïðèâåäåíî óñêîðåíèå âû÷èñëåíèé íà GPU. Ìîæíî çàìåòèòü, ÷òî ãðà èê èìååò òè-
ïè÷íîå íàñûùåíèå. Ýòî îçíà÷àåò, ÷òî íà áîëüøèõ íàáîðàõ óñêîðåíèå ñèëüíî íå èçìåíèòñÿ.
 ðåçóëüòàòå èñïîëüçîâàíèÿ ãðà è÷åñêîé êàðòû Tesla K40M óäàëîñü ïîëó÷èòü óñêîðåíèå
â 110 ðàç. Òàêæå ïðîâîäèëñÿ ýêñïåðèìåíò ïî ìàñøòàáèðîâàíèþ ýòîé çàäà÷è íà íåñêîëüêî
GPU (ðèñ. 2). åçóëüòàòû ïîêàçàëè, ÷òî ìåòîä Ìîíòå-Êàðëî ìîæíî ïåðåíåñòè íà íåñêîëüêî
ãðà è÷åñêèõ ïðîöåññîðîâ. Óâåëè÷åíèå ÷èñëà ïðîöåññîðîâ â 2 ðàçà äàåò ïðåèìóùåñòâî â
ñêîðîñòè â 1.6 ðàç. Òàêèì îáðàçîì, ìàñøòàáèðîâàíèå GPU ìîæíî èñïîëüçîâàòü ëèáî äëÿ
óñêîðåíèÿ âû÷èñëåíèé, ëèáî äëÿ óâåëè÷åíèÿ èõ òî÷íîñòè.
èñ. 2. Óñêîðåíèå âû÷èñëåíèé íà äâóõ GPU
Заключение
Ïîäâîäÿ èòîã, ñëåäóåò îòìåòèòü, ÷òî äëÿ íåêîòîðîãî êëàññà çàäà÷ èñïîëüçîâàíèå
GPGPU äàåò çíà÷èòåëüíîå ïðåèìóùåñòâî.
Àëãîðèòìû, íàïèñàííûå äëÿ GPU, òðåáóþò ãëóáîêîãî ïîíèìàíèÿ ïðèíöèïîâ ðàñïà-
ðàëëåëèâàíèÿ çàäà÷ è îñîáåííîñòåé àðõèòåêòóð ãðà è÷åñêèõ ïðîöåññîðîâ
 áóäóùåì ïëàíèðóåòñÿ çàâåðøèòü ñîçäàíèå ïðîãðàììíî-àïïàðàòíîãî êîìïëåêñà äëÿ
ðåøåíèÿ ïîñòàâëåííîé çàäà÷è.
Список литературы
G. Montagna, O. Ni rosini, N. Moreni A path integral way to option pri ing // Physi a A:
Statisti al Me hani s and its Appli ations. 2002. Vol. 310, Issues 34. P. 450466
V. Linetsky The path integral approa h to nan ial modeling and options pri ing //
Computational E onomi s. 1997. Vol. 11. Issue 1. P. 129 163
A. V. Bogdanov, E. A. Stepanov, D. S. Khmel Assessment of the dynami s of Asian and European
option on hybrid system // Journal of Physi s: Conferen e Series. 2015. Vol. 681.
P. 121 129
293
Optimization algorithm for computing options for the hybrid
system
D. S. Khmela, E. A. Stepanovb, A. V. Bogdanovc
Saint Petersburg University,
7/9 Universitetskaya emb., St. Petersburg, 199034
E-mail: a dskhmel .spbu.ru, b e.an.stepanovgmail. om, bogdanov sa.ru
In the arti le the problem of optimization of GPGPU option pri ing algorithms. The main
goal to a hieve maximum e ien y from the use of the hybrid system. The authors oered some
transformation algorithm derived from Blake-S holes model for pri ing European and Asian
option on the Monte Carlo method based on GPGPU ar hite ture features. The basi idea is the
onstant optimization of work with one large array of data.
Keywords: European option, Asian option, hybrid system, GPGPU, CUDA, Monte-Carlo
method
This work was supported by RFBR grants:
17-57-80111 FTRC-HPC: High-Performan e Computing with Networked Fault Tolerant Re on gurable
Computing Units,
16-57-48005 Multi FPU on Chip (MFoC) for HPC appli ations,
16-07-01111 Building Unix-like environment to ontrol virtual super omputer.
2016 Dmitry S. Khmel, Eduard A. Stepanov, Aleksandr V. Bogdanov
294