Оптимизация алгоритмов вычисления опционов на гибридной системе Д. С. Хмельа, Э. А. Степанов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 ongurable 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