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

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

101

Литература

1. Гергель В.П. Теория и практика параллельных вычислений. –

М.: Интернет-Университет информационных технологий;

БИНОМ. Лаборатория знаний, 2007. 423 с.

2. Гришагин В.А., Свистунов А.Н. Параллельное

программирование на основе MPI: Учебное пособие. –

Нижний Новгород: Изд-во ННГУ им.Н.И.Лобачевского, 2005.

93 с.

3. Алексеев В.Е., Таланов В.А. Графы

. Модели вычислений.

Структуры данных: Учебник. - Нижний Новгород: Изд-во

ННГУ им.Н.И.Лобачевского, 2005. 307 с.

4. Гергель В.П. Общая характеристика учебного курса

"Многопроцессорные вычислительные системы и

параллельное программирование". Научный сервис в сети

Интернет: технологии распределенных вычислений: Труды

Всероссийской научной конференции – М.: Изд-во МГУ, 2005.

С.303-306.

5. Gergel V.P., Strongin R.G. Parallel computing for globally optimal

decision making on cluster systems. Future Generation Computer

Systems 21, 2005, 673-678.

МОДЕЛИРОВАНИЕ

ДИНАМИКИ АПОПТОЗА,

ИНДУЦИРОВАННОГО ГРАНЗИМОМ В

Е.Н. Головченко, М.А. Ханин

Институт математического моделирования РАН, Москва

Центр теоретических проблем физико-химической фармакологии

РАН, Москва

Введение

Апоптозом называют запрограммированную смерть клеток.

Механизм апоптоза используется иммунной системой для

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

вредными для организма. Это относится,

в частности, к клеткам

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

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

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

онкологических заболеваний.

102

Апоптоз осуществляется внутриклеточной биохимической

системой, состоящей главным образом из белков, называемых

прокаспазами. Прокаспазы активируются, превращаясь в ферменты –

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

также проникают в клеточное ядро и разрушают ДНК. Одним из

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

две функции. Одна из них связана с активацией

прокаспаз, и,

следовательно, с запуском механизма апоптоза. Вторая функция

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

гранзимом В.

Динамика апоптоза, индуцированного гранзимом В, описывается

системой обыкновенных нелинейных дифференциальных уравнений

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

биохимических реакций известны лишь частично. Для определения

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

подход, основанный на

принципе минимального потребления белков

биохимической системой. Данный принцип ранее использовался в

работах [2, 3]. Оптимизационные задачи для системы апоптоза,

индуцированного гранзимом В, были решены при помощи

многомерного алгоритма глобального поиска из [1].

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

возможным исследование динамики апоптоза, индуцированного

гранзимом В.

Для уменьшения времени решения обратной оптимизационной

задачи был

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

глобального поиска из [1].

Модель динамики апоптоза, индуцированного гранзимом В

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

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

103

Рис. 1. Модель динамики апоптоза, индуцированного гранзимом В

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

гранзимом B, имеет вид:

},,,,{)},(),(),(),({)(

,)0(),,,(

)(

00000

TICCUtTtItCtCtu

UuGrBKuf

tud

rrr

(1)

где

)(tC

- вектор концентраций прокаспаз,

)(tC

- вектор

концентраций каспаз,

)(tI

- вектор концентраций ингибиторов каспаз,

)(tT

- вектор концентраций мишеней. Ингибиторы снижают

активность соответствующих каспаз.

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

линии К562.

Фоновое состояние системы апоптоза

При допороговой концентрации индуктора система апоптоза не

функционирует (фоновое состояние системы апоптоза).

Система уравнений, описывающих фоновое состояние апоптоза,

имеет вид:

0),,,,(

)(

000

== GrBKTICq

tCd

rrr

. (2)

Неустойчивость фонового состояния может привести к случайной

индукции апоптоза, обусловленной флуктуациями концентраций

прокаспаз. Используя критерий Рауса-Гурвица, приходим к

неравенству вида:

0),,,,(

000

<GrBKTICp

. (3)

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

ограничения при решении прямой оптимизационной задачи.

104

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

Функция потребления белков системой апоптоза в единицу

времени имеет вид:

∑

⋅

(4)

где

- молекулярный вес i-ой прокаспазы,

- концентрация i-ой

прокаспазы,

- среднее время жизни i-ой прокаспазы. Суммирование

осуществляется по всем прокаспазам (N), входящим в систему

апоптоза.

Система динамики апоптоза (1) состоит из 30 уравнений, в нее

входит 11 неизвестных кинетических констант. Процесс нахождения

неизвестных кинетических констант основан на двух

оптимизационных задачах: прямой и обратной. На каждом шаге

решения обратной оптимизационной задачи происходит решение

прямой оптимизационной задачи.

Прямая оптимизационная задача:

Заданы величины всех кинетических констант

Определяются оптимальные начальные концентрации

прокаспаз

опт

из условия минимума функции S при

следующих ограничениях:

 устойчивость фонового состояния апоптоза (неравенство (3));

 выполнение системой своей физиологической функции;

 среднее время разрушения мешеней должно быть меньше

своего экспериментального значения.

Обратная оптимизационная задача:

Заданы начальные концентрации прокаспаз

эксп

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

Кинетические константы

определяются из условия

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

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

опт

от найденных

биохимическими методами

эксп

105

})CC(min{

∑

−

эксп

опт

Кривая Пеано

Кривая Пеано – кривая, являющаяся непрерывным образом

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

Кривая Пеано строится по рекурсии: кривая 1-го порядка, 2-го порядка

и т.д. На рис. 2 изображена кривая Пеано 4-го порядка на двумерной

области.

Рис. 2. Кривая Пеано 4-го порядка на 2-мерной области

Многомерный алгоритм глобального поиска

Существующие методы поиска экстремума функции многих

переменных (метод покоординатного спуска, метод градиента, метод

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

экстремум. Поэтому для поиска глобального условного экстремума

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

(Multidimensional Index Method) из [1] для функций, удовлетворяющих

условию Липшица. В нем строится кривая Пеано, отображающая

отрезок [0,1] на область поиска условного

экстремума. В [1]

доказывается, что таким образом задача сводится к задаче поиска

глобального экстремума одномерной функции, удовлетворяющей

условию Гельдера.

Данный метод является обобщением метода поиска минимума

одномерной функции, удовлетворяющей условию Липшица [1],

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

(см. рис. 3). На каждом шаге оценивается константа Липшица.

Строится ломаная с локальными максимумами

в уже полученных

106

точках и с углами наклона, соответствующими константе Липшица.

Следующая точка выбирается в глобальном минимуме ломаной, то

есть на отрезке с наибольшей вероятностью содержания глобального

минимума функции.

1−i

1+i

)(x

Рис. 3. Выбор

q-ой точки при поиске минимума одномерной функции,

удовлетворяющей условию Липшица

Параллельный многомерный алгоритм глобального поиска

При отображении отрезка [0,1] на область D с помощью кривой

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

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

многомерного алгоритма глобального поиска. Для устранения данной

проблемы в [1] предлагается искать минимум одновременно на

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

добавлением условия попадания

в исходную область. На рис. 4

изображены области D

, D

для двумерного случая.

)

Рис.4. Области D

, D

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

nprocM ≥

узлы

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

одинаковы. Такое построение позволяет добиться того, что при

107

1−>> nprocM

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

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

расположены достаточно близко на отрезке [0,1].

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

Обратная оптимизационная задача была решена параллельным

алгоритмом на общей памяти. Для решения прямой оптимизационной

задачи использовался последовательный метод.

На кластере regatta.cs.msu.su (2хPower4 процессора, 4 GB памяти)

были получены следующие результаты (см. Табл. 1):

Время, с

Минимум

квадратичной

формы

Последовательный метод 5951 1.72e-14

2 процессора 660 2.12e-14

3 процессора 426 2.45e-14

Параллельный метод

4 процессора 360 2.45e-14

Таблица 1. Порядок кривой Пеано M = 4, размерность задачи (кинетические

параметры)

N = 4, погрешность метода ε=0.09

Большое ускорение параллельного алгоритма объясняется тем, что

основные временные затраты связаны с проверкой ограничений и с

нахождением прообразов на отрезке [0,1] для точек, найденных

другими процессами. В проверку ограничений при решении обратной

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

задачи, в частности многократное решение системы

дифференциальных уравнений. Время, затрачиваемое на решение

прямой оптимизационной

задачи, составляет 20 ÷ 70 секунд. Время

вычисления прообразов - 0.001 ÷ 0.003 секунды. То есть вычисление

прообразов намного выгоднее по времени, чем решение прямой

оптимизационной задачи.

Исследования динамики апоптоза, индуцированного

гранзимом В

При найденных кинетических константах была исследована

динамика активации каспаз и разрушения мишеней системы апоптоза,

индуцированного гранзимом В.

На рис. 5 представлена динамика каспазы-3 при различных

концентрациях гранзима В.

108

С3а

0.0

0.3

0.5

0.8

1.0

0 1 2 3

время в часах

концентрация в отн. ед.

100нМ

1нМ

10пМ

Рис. 5. Динамика каспазы-3 при различных концентрациях гранзима В

Заключение

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

индуцированного гранзимом B, с помощью решения прямой и

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

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

глобального условного экстремума многомерных многоэкстремальных

функций, основанные на сведении к одномерной задаче с помощью

кривой Пеано. Разработан комплекс программ, с помощью которого

определены кинетические константы

биохимических реакций системы

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

Список литературы

1. Strongin R.G., Sergeyev Y.D. Global Optimization with non-

convex constraints: sequential and parallel algorithms. Kluwer

Academic Publ., 2000.

Тюрин К.В., Ханин М.А., Оптимальность ферментативных

физиологических систем // Изв. Акад. Наук, Сер. Биол.,2000.

Т.6. с. 713-720.

Tyurin K.V., Khanin M.A. Optimality principle and determination

of kinetic constants for biochemical reactions // Math. Med.Biol.,

2005. Vol. 22. Pp. 1-14.

109

СРАВНЕНИЕ МАТЕМАТИЧЕСКИХ БИБЛИОТЕК INTEL MKL

И AMD ACML НА ПРИМЕРЕ РЕШЕНИЯ ЗАДАЧИ

УПРАВЛЕНИЯ ПОРТФЕЛЕМ ИНВЕСТОРА

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

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

Введение

Актуальность использования математических библиотек в

научных исследованиях определятся их богатой функциональностью и

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

Целью данной работы является сравнение производительности

популярных библиотек Intel MKL и AMD ACML на примере задачи

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

Задача управления портфелем инвестора представляет большой

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

обусловливает ее

принадлежность к области применения

высокопроизводительных вычислений. Один из вариантов

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

бумаг – опционов Бермудского типа [1, 2], которые могут быть

предъявлены к исполнению в любой из конечного количества

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

аналитического решения для определения цены и доходности таких

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

затруднительным. Популярный

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

Монте-Карло и средств имитационного моделирования, что

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

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

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

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

Intel MKL и AMD ACML, в скорость и качество решения задачи

оптимального управления портфелем инвестора. Суть

управления при

этом состоит во включении/исключении акций из портфеля, на

который выпускается опцион Бермудского типа. В качестве критерия

оптимальности рассматривается максимизация цены лота, состоящего

из некоторого фиксированного количества опционов, обеспечивающих

заданный уровень доходности.

110

Постановка задачи

Рассмотрим N-мерный финансовый рынок, эволюционирующий в

непрерывном времени [1]:

, 0

dB rB dt B=>

, (1)

()

() , 0,

iiii ii i

tt t

dS S dt dW S

θδ σ

=−+ >

(2)

Пусть инвестор формирует портфель акций для выпуска

опционного контракта в момент времени t

, а

1,...,in

–

начальные стоимости акций. Будем рассматривать max-call опционы

Бермудского типа, которые могут быть предъявлены к исполнению в

любой из d заранее фиксированных моментов времени

012 1

{0,,,..., }

tTime t tt t T

−

∈== =

, где

задает истечение срока

действия опциона. В качестве функции выплат будем рассматривать

1...

(, ) (max( ) )

htS S P

=−

, где положительная константа P

определяется опционным контрактом,

max( , 0)

. Условимся, что

опцион может включать любую комбинацию акций из набора

{,...}

SSS=

Введём обозначения:

( ,..., ) ( ,..., )

niim

xxx

– проекция

на

≤

{ ( ,..., ): ( ,..., ) , 1,..., }

xxxRm n

ππ

=∈=

– множество всех

допустимых проекций.

((,...,))

cc S S

– цена опциона, выпущенного на набор

акций

( ,..., )

(max( ( ,..., )) )

ttt

SS K

=−

– выплаты по опциону,

выпущенному на набор акций

( ,..., )

Пусть

(, , )RT f w

– доходность опциона со сроком погашения T,

функцией выплат f и случайным исходом w. Определим

(,())

(, , )

RT f w

−

, где τ – момент исполнения опциона,

зависящий от случайного исхода. Пусть

(, ) (, , )RT f ERT f w=

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