Стронгин Р.Г (ред.) Высокопроизводительные параллельные вычисления на кластерных системах

Подождите немного. Документ загружается.

111

((,...,)) max

(,())

(, ) max

cc S S

Ef T w C

RT f

==>

−

==>

(3)

где максимум ищется по всем

Далее необходимо найти оптимальное по Парето решение –

комбинацию акций, которая не может быть улучшена по обоим

критериям одновременно. Способ, позволяющий это сделать, описан в

[5].

Обозначим требуемый уровень доходности как R, а количество

выпускаемых опционов – M. Если полученное Парето-оптимальное

решение содержит опцион, уровень доходности которого равен R, то

цена этого

опциона Smax будет максимальной для уровня доходности

R. Поэтому максимальная цена лота, состоящего из M опционов и

обеспечивающего уровень доходности R, будет равна M * Smax. Если

же Парето-оптимальное решение не содержит такого опциона,

выберем из решения два опциона, наиболее близких по уровню

доходности к R.

Рис. 1. Пример Парето-оптимального решения

Пример такой ситуации представлен на рис. 1, опционам на

графике соответствуют выделенные точки P1 и P2. При этом отрезок,

проходящий через эти две точки, обязательно пересечет

горизонтальную прямую, соответствующую уровню доходности R.

Представим точку их пересечения как линейную комбинацию точек P1

и P2 с коэффициентами a и (1-a) соответственно. При этом будем

считать

решением задачи цену лота, состоящего из a*M опционов,

112

соответствующих точке P1, и (1-a)*M опционов, соответствующих

точке P2.

Метод исследования

Для решения задачи необходимо найти оптимальное по Парето

решение – комбинацию акций, которая не может быть улучшена по

обоим критериям одновременно. Нами было рассмотрено 2 способа

получения решения: крайне затратный по времени расчета полный

перебор («точное решение»

) и генетический алгоритм

(«приближенное решение»). Оба этих метода применительно к задаче

управления портфелем инвестора в рассмотренной постановке

описаны в [5].

Для проведения сравнения библиотек мы использовали

генетический алгоритм ввиду высокой скорости его сходимости на

данном классе задач [5]. Для понимания степени близости

«приближенного решения» к «точному» с помощью полного перебора

были

вычислены «точные» Парето-границы.

В итоге нами было разработано многопоточное приложение,

позволяющее в режиме реального времени визуализировать процесс

поиска решения задачи управления портфелем инвестора с

использованием библиотек Intel MKL и AMD ACML, а также

сравнивать полученные решения с решением, предварительно

вычисленным с помощью метода полного перебора.

Приложение основано на клиент-серверной архитектуре. В роли

клиента

выступает графический интерфейс, отображающий

полученные на текущей итерации максимальные цены портфеля,

подсчитанные с помощью сравниваемых библиотек, разницу этих

решений между собой и отставание от «точного решения». Сервером

является приложение, состоящее из двух потоков, в каждом из

которых происходит вычисление цены с помощью соответствующей

библиотеки. Графический интерфейс разработан на языке Java,

вычислительная

часть реализована на C++. Графический интерфейс

приложения представлен на рис. 2.

В связи с тем, что алгоритмы вычисления обоих критериев не являются

детерминированными, в случае полного перебора всех комбинаций акций мы получаем

некоторое решение, которое отличается от точного в пределах статистической

погрешности.

113

Рис. 2. Графический интерфейс

Результаты вычислительных экспериментов

Результаты были получены с использованием следующего

программного и аппаратного обеспечения:

Intel® Core™2 Duo T7500 2,2GHz, 2 Gb RAM, L2 cache 4Mb.

Intel® Math Kernel Library (Intel® MKL) 10.0 beta, AMD® Core

Math Library 4.0.

Intel® C/C++ Compiler 9.1, Microsoft ® Visual Studio 2005.

В качестве базового генератора рассматривается генератор

псевдослучайных чисел Mersenne Twister

.

Рассмотрим результаты расчетов следующей тестовой задачи:

114

Количество акций (N) 15

Процентная ставка 7%

Начальные цены акций (111, 120, 110, 125, 104, 107, 121, 109, 119, 105,

107, 102, 129, 119, 115)

Страйк (K) 100

Коэффициент корреляции 0,43

Нормы возврата (r) (0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,0.05,

0.05,0.05,0.05,0.05, 0.05, 0.05)

Срок погашения (T) 1 год

Количество моментов

исполнения (

Волатильности (

)

(0.24, 0.31, 0.28, 0.22, 0.15, 0.23, 0.19, 0.27, 0.11,

0.46, 0.33, 0.29, 0.25, 0.21, 0.16)

Уровень доходности (R) 12,7%

Количество опционов (M) 1000000

При решении получены следующие результаты:

Цена, полученная с использованием библиотеки MKL (у.е.) 64 849 028

Цена, полученная с использованием библиотеки ACML (у.е.) 55 894 089

Цена, полученная с помощью метода полного перебора (у.е.) 66 812 919

Отрезки Парето-границ, проведенные через точки,

соответствующие опционам со значениями доходности наиболее

близкими к требуемому уровню, отображены на рис. 3.

115

Рис. 3. Парето-оптимальные решения

В результате работы нами было создано демонстрационное

приложение-тренажер, позволяющее задать параметры тестовой

задачи, желаемый уровень доходности и предварительно

подсчитанную «точную» Парето-границу, а затем в режиме реального

времени наблюдать, как расчетные модули, построенные на базе

функциональности Intel MKL и AMD ACML, сходятся к «точному»

решению. При этом для оценки степени близости к «точному

решению

» использовались величины отставания цен пакетов

опционов, соответствующих «приближенным решениям», полученным

расчетными модулями, от «точного решения». Анализ нескольких

тестовых задач и уровней доходности показал, что обсчитывая

большее количество пробных точек в пространстве поиска решения,

вычислительная часть на базе Intel MKL приближается к «точному

решению» быстрее, чем вычислительная часть на базе AMD ACML.

Поскольку в реальных

условиях время принятия решения о выпуске

пакета опционов ограничено, разница в скорости приближения к

оптимуму является важным преимуществом, позволяя принимать

более оптимальные решения в смысле максимизации цены лота при

заданном уровне доходности.

Заключение

Кратко сформулируем основные результаты работы:

Приведена постановка задачи максимизации цены пакета

опционов при заданном уровне доходности, описан подход к

ее решению.

На основе указанной задачи создано демонстрационное

приложение-тренажер для исследования в режиме реального

116

времени скорости сходимости к «точному решению»

вычислительных частей, построенных с использованием

функциональности Intel MKL и AMD ACML.

Приложение опробовано на ряде тестовых задач.

Анализ результатов показал, что преимущество в

производительности генераторов псевдослучайных чисел в

Intel MKL в данной задаче позволяет повысить качество

принимаемых решений в смысле рассмотренного критерия.

Литература

1. Ширяев А. Н. Основы стохастической финансовой

математики. В 2 томах. – М.:Фазис, 1998.

Broadie M., Glasserman P. Pricing American-style securities using

simulation // Journal of Economic Dynamics and Control, June

1997. Vol. 21. Pp. 1323-1352.

Горбунова А.С., Козинов Е.А., Мееров И.Б., Николаев А.Ф.,

Шишков А.В. Параллельная реализация одного алгоритма

нахождения цены опционов Бермудского типа //

Высокопроизводительные параллельные вычисления на

кластерных системах: Материалы пятого Международного

научно-практического семинара / Под ред. проф. Р.Г.

Стронгина. – Нижний Новгород: Изд-во Нижегородского

госуниверситета, 2005. – С. 60-67.

Горбунова А.С., Козинов Е.А., Мееров И.Б., Шишков А.В.

Применение параллельных вычислений для определения

справедливой цены опционов бермудского типа с

использованием стохастической сети // Научный сервис в сети

Интернет: технологии параллельного программирования:

Труды Всероссийской научной конференции (г.

Новороссийск).–М.: Изд-во МГУ, 2006.–С.140-143.

Мееров И.Б., Горбунова А.С., Козинов Е.А., Шишков А.В.. Об

одном подходе к решению задачи управления портфелем

ценных бумаг // Параллельные вычислительные технологии

(ПАВТ'2007): Труды Международной научной конференции

(Челябинск, 29 января – 2 февраля 2007 г.). – Челябинск: Изд-

во ЮУрГУ, 2007. – Т.1. – С. 135-139.

117

ЗАДАЧА ПАРАМЕТРИЧЕСКОЙ ОПТИМИЗАЦИИ

ПРОСТРАНСТВЕННЫХ МЕХАНИЗМОВ С ПАРАЛЛЕЛЬНЫМИ

ВЫЧИСЛЕНИЯМИ КИНЕМАТИКИ НА ГРАФИЧЕСКОЙ

КАРТЕ

Е.С. Городецкий

Нижегородский государственный университет

Введение

Пространственные рычажные механизмы являются важной

составляющей современной техники и производственных технологий.

Механические системы часто выполняют весьма серьёзные задачи,

требующие высокой надёжности и точности. Конструктору обычно

требуется знать, как будет действовать разработанный им механизм

ещё до его окончательного изготовления. В связи с этими

требованиями к процессу создания механизмов крайне важными

являются возможности

выполнения полного проектирования

механизмов и моделирования их работы.

Процесс проектирования механизма состоит в определении

конструкции механизма (задания связей между его звеньями), выборе

варьируемых параметров для выполнения конструктивных

ограничений и оптимизации его работы. Задачей данной работы

является разработка автоматизированных методов оптимизации

моделей пространственных механизмов с реализацией кинематических

вычислений на графической карте

для достижения максимальной

производительности.

Краткое введение в предметную область и основные термины

Предметной областью решаемой задачи является теория

механизмов и машин (ТММ). Под механизмом понимается

совокупность взаимосвязанных твёрдых тел, предназначенная для

преобразования движения входов на одном или нескольких твёрдых

телах в движение на других твёрдых телах (выходах). Механизм может

быть представлен своей структурной схемой, на которой выделяют

звенья (твёрдые тела), соединяющиеся в подвижные

кинематические

пары с помощью различных типов геометрических элементов

(вращательных, сферических, поступательных и др.) [2]. На рис. 1 приведено

конструктивное изображение V-образного авиационного двигателя, а

справа – его структурная схема.

118

Рис. 1

При конструировании механизмов важно учитывать число

степеней подвижности, которое должен обеспечивать создаваемый

механизм. Существуют общие закономерности в строении самых

различных механизмов, связывающие число степеней подвижности

механизма с числом звеньев и числом и видом его кинематических

пар.

В основе методов конструирования механизмов и расчета кинематики

лежит принцип образования механизмов по Ассуру, утверждающий

что

“Всякий механизм представляет собою совокупность одного или

нескольких двухзвенных (первичных) механизмов и одной или нескольких

групп нулевой подвижности (структурных групп)” [2].

Важно ещё до выполнения вычислений диагностировать ситуации,

когда расчет положений выполнить невозможно, либо он не имеет

смысла. Структура механизма считается корректной, если механизм

связный и каждая его непустая группа

является либо первичной

группой (содержит ровно одну пару, движение звеньев которой

определено), либо структурной группой, которая, в свою очередь

удовлетворяет требованиям связности (все пары группы соединены

звеньями) и статической определимости (число степеней подвижности

группы равно нулю). Очевидно также, что механизм должен содержать

как минимум одну первичная группу.

119

Методы решения прямой задачи кинематики механизмов

В работе рассматривается класс пространственных рычажных

механизмов, которые могут быть образованы согласно принципу

Ассура наслоением одноконтурных структурных групп. Рассмотрим

математические модели звена и пары.

Рис. 2.

Звено L

i,i+1

(рис. 2) соединяется со смежными звеньями группы

посредством двух кинематических пар. Для моделирования этих пар

на звене в общем случае должны быть определены две оси, каждая из

которых задана точкой и единичным вектором (ортом) направления.

Точки и орты направлений осей пар рассматриваются как первичные

элементы модели звена. Объединение звеньев L

i-1,i

и L

i,i+1

в i-той паре

налагает на первичные, а значит, и на вторичные элементы модели

звена различные условия, зависящие от геометрии сочленения.

Геометрические условия замкнутости звеньев в i-той кинематической

паре можно использовать как условия замкнутости группы в целом [4].

Прямая задача о положении для механизмов ставится следующим

образом. Задано движение всех входных

звеньев, удовлетворяющее

связям, которые накладывают кинематические пары, соответствующих

первичных механизмов. Необходимо найти движение всех остальных

звеньев механизма либо сообщить о невозможности реализации

положения в тот или иной момент времени. Закон Асура играет

фундаментальную роль при решении задачи о положении для

пространственных механизмов. Прямая задача о положениях

механизма сводится к решению

ряда отдельных более простых

подзадач расчета положений структурных групп механизма.

Для решения прямой задачи кинематики механизма необходимо

установить последовательность расчета его структурных групп.

Последовательность строится таким образом, чтобы положения

120

поводков группы, необходимые для вычисления её собственного

положения были определены на предыдущих шагах.

На рис. 3 приведён пример механизма выдвижения закрылков

самолёта. Механизм состоит из одного первичного механизма и 4

структурных групп ВВВ (из 3 вращательных пар), связанных друг с

другом. Каждая группа имеет два входа, необходимых для расчета её

положения. Исходя из

этих требований, строится последовательность

расчета структурных групп, показанная на рис. справа - вычисления

производятся последовательно по уровням 0, 1, 2, и т.д., сверху вниз

(стрелками показаны соединения групп друг с другом). Положения

структурных групп ВВВ вычисляются аналитически. Произведя

вычисления положений механизма для разных углов

поворота

входного звена, получим движение всех звеньев механизма.

Рис. 3

В общем случае алгоритм вычисления положений механизма

плохо распараллеливается, поскольку вычисление положения

отдельной группы может зависеть от набора связанных групп. Но

вычисления положений одного механизма в разные моменты времени

могут выполняться независимо, а значит, параллельно.

Решение задачи о положениях для структурных групп

В задаче расчета положения структурной группы для

присоединяемых поводков группы заданы положения присоединяемых

точек и направлений осей пар, нужно найти все неизвестные

положения внутренних точек и направлений осей пар данной группы.

Эта задача имеет конечное число решений, поскольку структурная

группа, по определению, имеет нулевую подвижность – т.е. является

статически определимой конструкцией

. Существует два основных

подхода к расчету структурной группы [5]: