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

С одерж ание
Введение 5
Глава 1. Оптимизация статистического моделирования
диффузионных процессов. 20
1.1. Статистическое моделирование траекторий диффузионных процессов. Функционалы от приближенных траекторий и соответствующие рекуррентные оценки................. 20
1.2. Вычисление вероятности не достижения границы области диффузионным процессом за определенное время......... 25
1.2.1. Аналоговая оценка вероятности не достижения границы области.......................................... 26
1.2.2. Применение метода расщепления для улучшения аналоговой оценки вероятности не достижения границы области......................................... 27
1.2.3. Весовая оценка вероятности не достижения границы области. Применение принципа выборки по важности для улучшения весовой оценки..................... 31
1.2.4. Численные результаты.......................... 37
1.2.5. Исследование порядка детерминированной погрешности оценки функционала методом зависимых испытаний ............................................. 43
1.3. Вычисление полной концентрации траекторий диффузионного процесса в заданной точке в определенном интервале впемени.................................................. 48
ж
1.3.1. Аналоговая оценка концентрации траекторий диффузионного процесса в точке. Интегральное уравнение второго рода для концентрации.................... 49
2
1.3.2. Весовая оценка концентрации траекторий диффузионного процесса в точке. Моделирование по ценности.................................................. 51
1.3.3. Комбинирование методов расщепления и моделирования по ценности для улучшения оценки концентрации траекторий диффузионного процесса в точке................................................... 55
1.3.4. Численные результаты........................... 58
1.3.5. Исследование порядка детерминированной погрешности оценки функционала методом зависимых испытаний ............................................. 63
Глава 2. Параллельная реализация статистического
моделирования и генераторов случайных чисел. 66
2.1. Некоторые особенности параллельной реализации статистического моделирования.................................. 66
2.2. Параллельная реализация генераторов случайных чисел. 68
2.3. Параллельная реализация конкретного конгруэнтного 128-битного генератора........................................ 72
2.4. Сравнение численных результатов решения конкретных диффузионных задач при использовании предложенного генератора и известного конгруэнтного генератора с параметрами г — 40, М = 517................................. 76
Глава 3. Система МСЖС - комплекс программ для параллельной реализации статистического моделирования в сети персональных компьютеров. 78
о .л. шет ОдО.' 1О1 и ческие принципы СПСТ МСЖС........... 78
3.2. Функциональные возможности системы МСЖС.............. 82
3.3. Требования к Проекту пользователя.................... 86
3
3.4. Пример решения конкретной диффузионной задачи с использованием системы МСЖС................................ 90
Приложение 1. Необходимые для использования модифицированного 128-битного генератора вычислительные программы, константы и инструкции для использования. 95
Приложение 2. Инсталляция и использование системы MONC. . 101
2.1. Описание служебного программного обеспечения системы MONC. Инструкции по инсталляции......................101
2.2. Описание интерфейса системы MONC. Инструкции по использованию........................................104
Заключение 108
Литература 109
4
В ведение
Для описания различных явлений в физике и технике широко используются математические модели, в основе которых лежит понятие стохастического диффузионного процесса. Подобные модели применяются, например, при расчете концентрации загрязнений в водной и воздушной средах; при исследовании оценок устойчивости и надежности радиотехнических, и телекоммуникационных систем ( см., например, [26, 23, 19, 18]). В общем случае, стохастическая диффузионная задача может рассматриваться как вычисление функционала, представляющего собой математическое ожидание некоторой функции от случайной траектории диффузионного процесса. Как известно, математические модели диффузионных процессов определяются системами стохастических дифференциальных уравнений (СДУ) [26, 23] и поэтому диффузионная задача состоит в вычислении функционала от траекторий решения СДУ.
Для численной оценки подобных функционалов обычно применяется метод статистических испытаний или метод Монте-Карло ( см., например, [2, 15]). Для этого решение СДУ аппроксимируется с помощью подходящей дискретной стохастической схемы, обеспечивающей сходимость численного решения к точному с некоторым порядком в среднеквадратическом смысле (см., например, [26, 19,). Соответственно, значение функционала Ф от точных диффузионных траектории аппроксимируется значением функционала р от приближенных траекторий. В общем виде метод Монте-Карло заключается в оценке функционала ср выборочным средним от независимых реализаций О, г = 0,1,..., N случайной оценки являющейся некоторой функцией от приближенных траекторий:
¥=ес“^,14'
5
При этом предполагается, что у случайной величины С существуют и конечны ее математическое ожидание Е£, и дисперсия
Практически важной проблемой при практическом использовании метода Монте-Карло является построение случайных оценок с малой трудоемкостью ( см., например, [2, 15]). Вообще говоря, трудоемкость случайной оценки следует определять в зависимости от существа конкретной задачи. Разберем это положение подробнее. Пусть *(С) - среднее время ЭВМ, затрачиваемое на моделирование одного
выборочного значения случайной оценки £. Как известно, случайная N
величина ЛГ-1 XI 0 при достаточно большом N имеет нормальное рас-»=1
пределение и при заданном уровне доверия р выполняется следующее
неравенство:
|ЕС-^Е61<^
N ’
где константа у зависит от величины р. На основе этого неравенства, абсолютная статистическая погрешность статистической оценки определяется величиной
\
ос
. а относительная статистическая по-
А
О
грешность - величиной ^ -.—г»——. В случае малых значении функ-
(Ец) • А
ционала \р = 1 точность расчетов целесообразно определять
величиной относительной погрешности, и поэтому в этом случае под трудоемкостью 5(£) случайной оценки следует понимать среднее количество вычислительной работы, необходимой для достижения заданной относительной погрешности (см., например, [21), а именно:
5(0 = «<)р§5.
Диссертационная работа посвящена проблемам вычисления именно малых функционалов и поэтому в ней по существу будет использоваться это определение трудоемкости. Подчеркнем, что целью исследований является построение случайных оценок диффузионных функ-
6
циоыалов с малой трудоемкостью, а не только с малой дисперсией.
В диссертационной работе разработаны методы улучшения статистического моделирования для широкого класса диффузионных задач. При этом детально исследовались методы оптимизации случайных оценок следующих практически важных функционалов: во-первых, вероятности не достижения границы заданой области диффузионным процесом в определенном интервале времени и, во-вторых, полной концентрации траекторий диффузионного процесса в заданной точке в определенном интервале времени [15]. В первом случае особенностью задачи является большая величина временного интервала, а во втором случае - большое расстояние от источника траекторий до заданной точки, что в обоих случаях приводит к весьма малой величине искомых функционалов. Прямое моделирование для статистических оценок для таких функционалов трудоемко, поэтому встает вопрос об улучшении вычислений.
Для решения вопроса уменьшения трудоемкости статистических оценок диффузионных функционалов существует целый ряд подходов (см., например, [2, 15, 24, 21, 31]). В применении к решаемым проблемам наиболее подходящими представляются методы оптимизации случайных оценок многократных интегралов и случайных оценок решений интегральных уравнений второго рода [2, 15]. Эти соображения основаны на том, что функционал от приближенных траекторий диффузионных процессов можно либо выразить в виде многократного интеграла, либо представить в виде решения интегрального уравнения второго рода.
В диссертационной работе для уменьшения трудоемкости случайной оценки вероятности не достижения границы заданной области диффузионным процессом использовались, с одной стороны, метод расщепления и, с другой стороны, весовое моделирование на основе принципа выборки по важности [2, 15]. При этом проделан сравни-
7
тельный анализ целесообразности применения этих методов оптимизации.
Для задачи расчета полной концентрации траекторий диффузионного процесса в заданной точке в определенном интервале времени использовалось представление концентрации в виде решения интегрального уравнения второго рода и далее для уменьшения трудоемкости оценки решения этого уравнения применялась комбинация метода расшепления и моделирования по ценности [2, 15].
Во многих случаях эффективной методикой ускорения расчетов на ЭВМ служит их распараллеливание [4, 15]. При этом методы Монте-Карло находятся, безусловно, в более ” привилегированном” положении по отношению, к примеру, к конечно-разностным алгоритмам вычислительной математики. Это прямо следует из их структуры -методы Монте-Карло, по сути, заключаются в моделировании независимых реализаций случайных процессов. Поэтому алгоритмически задача эффективного распределения независимых реализаций по независимым процессорам может быть с успехом решена. Как известно, основное машинное время многопроцессорного вычислительного комплекса уходит на обмен данными между процессорами и на время простоя процессоров г4]. При распараллеливании методов Монте-Карло подобные временные затраты сведены к минимуму: здесь время, затраченное на распределение заданий по процессорам и на финальное осреднение независимых результатов практически не играет роли, особенно если выполняется моделирование большого числа независимых реализаций случайных оценок [15]. При этом, структура методов Монте-Карло позволяет добиться обратно пропорциональной зависимости величины трудоемкости случайных оценок от числа процессоров (при условии, что используемые процессоры имеют одинаковую производительность).
В связи с задачей распараллеливания статистического моделиро-
8
вания возникает, без преувеличений, основополагающая проблема -использование специально приспособленных для этого генераторов псевдослучайных чисел. Традиционно, в основе моделирования случайных процессов лежит использование равномерно распределенных на единичном интервале случайных величин, для численной реализации которых можпо использовать конгруэнтный генератор псевдослучайных чисел [2, 15]. Естественно, в параллельной системе необходимо использовать обоснованные и проверенные статистическими тестами методы распределения псевдослучайных чисел по независимым процессорам.
Здесь, для полноты освещения проблемы, следует упомянуть об одном недостаточно обоснованном, с точки зрения автора диссертационной работы, подходе. В работах [27, 22] для распределения псевдослучайных чисел по процессорам на каждом из них предлагается использовать свой множитель конгруэнтного генератора, т.е. по сути, разные генераторы на каждом из процессоров. Однако, например, одна только проблема обоснования некоррелированности получаемых последовательностей псевдослучайных чисел и подбора соответствующих параметров генераторов представляется весьма сложной.
Для моделирования независимых реализаций оценки на каждом независимом процессоре можно использовать свою, непересекающу-юся с другими, подпоследовательность исходной последовательности псевдослучайных чисел [2, 15]. При этом, для практического применения распараллеливания необходимо быть уверенным в том, что для конкретного генератора указанные подпоследовательности псевдослучайных величин в совокупности удовлетворяют необходимым статистическим тестам.
В диссертационной работе предлагается модифицированный генератор псевдослучайных чисел, равномерно распределенных в единичном интервале, с ’’астрономически” длинным периодом. В его осно-
9