Высокопроизводительные парал. вычисления на кластерных системах. Воеводин (2005) (1186026), страница 13
Текст из файла (страница 13)
При этом существенное воздействие на процесс моделирования оказывает наличие факторов неопределенности. Как следствие, решение многих задач финансовой математики требует применения методов Монте-Карло и средств имитационного моделирования [1]. Успех применения этих методов существеннозависит от качества используемых генераторов случайных чисел и, какправило, требует больших вычислительных затрат. По этой причинеразработка параллельных реализаций расчетных алгоритмов для решения задач финансовой математики оказывается особенно актуальной.В этой работе мы рассматриваем одну из частных задач финансовой математики – вычисление цены опционов Бермудского типа.
Эффективное решение этой задачи, являющееся крайне важным для практического применения, достигается с помощью параллельной реализации алгоритма Broadie–Glasserman Random Trees [2].Постановка задачиРассмотрим N-мерный финансовый рынок, эволюционирующий внепрерывном времени (подробнее о модели Блэка–Шоулса и ее много60численных обобщениях, см., например, [0, 3] и библиографию там):dBt = rBt dt, B0 > 0,(1)dS ti = S ti ((θi − δ i )dt + σ i dW i ), S 0i > 0, (2)где процессы B = ( Bt )t ≥ 0 и S i = ( Sti )t ≥ 0 , i =1, …, N описывают поведение облигации B и i-й акции в каждый момент времени t ≥ 0, соответственно.
Поведение облигации B задается процентной ставкой r, изменение стоимости акции S i определяется волатильностью σ i и нормойвозврата θ i, δ i – ставка дивиденда. Случайные возмущения в цене акции S i описываются i-й компонентной векторного Винеровского процесса W i = (Wti ) t ≥0 (W = (W 1 , ..., W N )).Предположим, что σi и µi θ i – δi , i = 1, …, N являются функциямивремени, а ковариационная матрица COV = (covij)i, j = 1…N отражает зависимости между ценами рисковых активов финансового рынка в каждый момент времени.Рассмотрим одну из часто встречающихся разновидностей опциона – max-call опцион, для которого функция выплаты h(t, St) имеетследующий вид:h(t , S t ) = ( max ( S ti ) − P ) + ,i =1... N(3)где положительная константа P определяется опционным контрактом,x+ = max(x, 0).Решим задачу вычисления стоимости опциона Бермудского типа,который может быть предъявлен к исполнению в любой из заранеефиксированных моментов t ∈ Time = {t 0 = 0, t1 , t 2 , ..., t d = T }, где момент времени T задает истечение срока действия опциона.Математический метод решения задачиМатематически поиск стоимости опциона сводится к решениюстохастической оптимизационной задачи (подробнее см.
[2])Q = max E (h( S τ ) Bτ ).(4)Q(t , x) = max (h(t , x), E{Q(t + 1, S t +1 ) Bt / Bt +1 ) S t = x}),(5)τ∈TimeПусть61Q(t, ST) = h(T, ST).Стоимость опциона Бермудского типа определяется как C = Q(0, S0).Описание алгоритмаДля решения задачи был использован популярный алгоритмBroadie–Glasserman Random Trees [2], основанный на Монте-Карломоделировании. Так одиночный эксперимент состоит в генерации дерева стоимостей акций на основе модели Блэка–Шоулса, [3].Корень дерева содержит N-мерный вектор цен акций в начальныймомент времени, каждая вершина дерева хранит N-мерный вектор ценакций в соответствующий момент времени ti из множества Time.
Такимобразом, каждый уровень дерева соответствует некоторому моментуисполнения опциона ti. Количество уровней соответствует количествумоментов применения опциона (d), а количество ветвей дерева (K) является параметром алгоритма. Значения цен акций в узлах рассчитываются путем численного интегрирования системы стохастическихдифференциальных уравнений (2) (приращения Винеровского процесса формируются с помощью генератора случайных чисел гауссова распределения). Пример дерева при N = 1, K = 3 и d = 3 приведен на рис.
1.В работе [2] авторы алгоритма указывают на сложность построениянесмещенной оценки стоимости опциона и предлагают вычислять двеоценки, первая из которых сходится к точному решению справа, а вторая – слева. Способы построения оценок подробно описаны в статье.ss21s22s23s11s0s24s25s12s26s27s28s13s290t0t1t2 = TtРис. 1.
Пример дерева стоимостей акций для N = 1, K = 3, d = 362Повторяя указанные действия многократно, мы получаем средниезначения верхней и нижней оценок стоимости Бермудского опциона,их дисперсию и определяем соответствующий доверительный интервал для цены актива.Последовательная реализация алгоритмаРеализация описанного выше алгоритма проводилась на языкепрограммирования C с использованием библиотек Intel® Math KernelLibrary (MKL) 8.0, MPICH for Windows**, MPICH2 for Windows** иоптимизирующего компилятора Intel® C/C++ Compiler 9.0 for Windows**.Из-за необходимости генерации и обходов дерева стоимостей акций (см.
рис. 1) алгоритм является экспоненциальным по количествумоментов исполнения Бермудского опциона. «Наивная» реализацияалгоритма требует хранения дерева стоимостей акций и оценок в каждом узле, что приводит к экспоненциальному росту требуемой памятии крайне неэффективной работе алгоритма. В связи с этим мы создалиоптимизированную для невырожденного случая (d > 1) реализациюалгоритма. Основные изменения по сравнению с «наивной» реализацией состоят в следующем:1. Оптимизированная реализация алгоритма предполагает изменение схем обхода дерева с уменьшением объема памяти, используемойдля хранения исходных и промежуточных данных,c C(1 + K + K 2 + … + K d –1) size of (type)до N(d + K – 1) size of (type) + 2((d – 2)K + 1) size of (type),где N, d и K – параметры задачи, а type – тип данных для представления стоимости акций.
Как следствие, затраты памяти зависят линейным образом от количества моментов исполнения опциона.2. Эксперименты показали, что использование одинарной точностине ухудшает качество решения и уменьшает временные затраты.Проведенные изменения позволяют получить ускорение в 2,7 разапо сравнению с «наивной» реализацией алгоритма, однако, время работы программы по-прежнему остается достаточно большим.Параллельная реализация алгоритмаОсновная идея распараллеливания алгоритма базируется на томфакте, что генерация ветвей в дереве стоимостей акций происходитнезависимо друг от друга. Следующий за этим подсчет верхней и ниж63ней оценок начинается с последнего уровня, далее проходит все уровни дерева до первого, используя на каждом шаге лишь результаты предыдущего шага (работает схема динамического программирования).Лишь на нулевом уровне (в корне дерева) происходит агрегация результатов, собранных на различных ветвях дерева.Схема распараллеливания состоит в следующем:1) головной процесс формирует первый уровень дерева;2) построение ветвей дерева равномерно распределяется междупроцессами (в том числе и головным) в соответствии с рис.
2;3) по окончании построения дерева каждый процесс пересчитывает оценки от листьев дерева к корню вплоть до первого уровня;4) получив оценки первого уровня, процессы пересылают результат головному процессу;5) головной процесс агрегирует полученные результаты и вычисляет верхнюю и нижнюю оценки стоимости опциона.Процесс 1Головной процесс12KПроцесс kРис. 2. Схема распараллеливанияРезультаты вычислительных экспериментовРезультаты вычислительных экспериментов получены на Intel®Itanium® 2 системе (4x900MHz, 3MB L3, 2GB RAM, SCSI 2x73.4 GB).Для проведения экспериментов использовались MPICH** 1.2.5,MPICH** 2.0, Intel® MPI.Для экспериментов были выбраны следующие значения параметров:64N5K32D5, 6 и 7 в разных экспериментахT (дней)365R7%S0(100; 110; 120; 130; 140)P100Коэффициент0,43корреляции(0,03; 0,035; 0,04; 0,045; 0,05)µ(0,34; 0,345; 0,35; 0,355; 0,36)σСледующие результаты демонстрирует результаты работы последовательной реализации алгоритма для 5, 6 и 7 моментов исполненияопциона и демонстрирует экспоненциальный рост временных затрат.Описание Нижняя Верхняя Время, с Количество выполоценкаоценканенных тестовd=539,828267 40,870916829,2110d=639,602242 40,773254750,8310d=740,484818 41,732002 27797,471Для параллельной версии алгоритма, учитывая небольшой объемпересылок, схема обеспечивает почти линейное ускорение.
Данныйфакт подтверждается вычислительными экспериментами на различныхархитектурах (IA-32, IA-64 и процессорах Intel® с EM64T технологией) под ОС Windows** и Linux**.Приведем в качестве примера анализ ускорения вычислений для1, 2-х и 4-х процессоров Intel® Itanium® 2.t27797,47250002000015000100005000029,21d=5750,83d=6d=7d65N = 5; K = 323,02,01,00d=5d=6d=7111122,00145472,00120044243,9784001883,954061983,975712074Выводы1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
