Методы Монте-Карло для параллельных вычислений

Серия
Суперкомпьютерное 
Образование

Координационный совет
Системы научно-образовательных центров
суперкомпьютерных технологий

Председатель Координационного совета
В. А.  Садовничий,
ректор МГУ имени М. В.  Ломоносова,
академик

Заместители председателя совета
Е. И.  Моисеев,
декан факультета вычислительной математики и кибернетики
МГУ имени М. В.  Ломоносова, 
академик

А. В.  Тихонравов,
директор Научно-исследовательского вычислительного центра
МГУ имени М. В.  Ломоносова, 
профессор

Члены совета

В. Н. Васильев, ректор Санкт-Пе тер  бургского национального исследовательского госу дар ственного университета инфор ма ционных технологий, механики 
и оптики, чл.-корр. РАН, профессор; В. Г. Захаревич, ректор Южного федерального университета, профессор; Н. Н. Кудрявцев, ректор Московского физико-технического института, чл.-корр. РАН, профессор; Г. В. Майер, 
ректор национального исследовательско го Томско го государственного университета, профессор; А. А. Фаткулин, проректор по науке и инновациям 
Дальневосточного федерального университета, профессор; Е. В. Чупрунов, 
ректор националь ного исследовательского Ниже городского го су дарственного 
университета, про фессор; А. Л. Шестаков, ректор национального исследовательского Южно- Уральского государственного университета, профессор; 
В. Н. Чубариков, декан механико-математического факультета МГУ имени 
М. В. Ломоносова, профессор; М. И. Панасюк, директор Научно-ис сле дова тельского института ядерной физики МГУ имени М. В.  Ломоно сова, профессор; Вл. В. Воеводин, заме ститель директора Научно-исследо ва тель ского 
вычислительного центра МГУ имени М. В.  Ломоносова, исполнительный директор 
НОЦ «СКТ-Центр», член-корреспондент РАН.

Издательство Московского университета
2013

Нижегородский гоударственный университет 
им. Н. И. Лобачевского

Методы Монте-Карло 
для параллельных 
вычислений

А. В. Зорин, М. А. Федоткин

Допущено 
УМО по классическому университетскому образованию 
в качестве учебного пособия для студентов высших учебных заведений, 
обучающихся по направлениям ВПО 
010400 «Прикладная математика и информатика» 
и 010300 «Фундаментальная информатика 
и информационные технологии»

© А.В.Зорин, М.А.Федоткин, 2013 
© Издательство Московского университета, 2013
ISBN 978-5-211-06530-7

Зорин А. В., Федоткин М. А. 
Методы Монте-Карло для параллельных вычислений: Учебное пособие / Предисл.: В. А. Садовничий. – М.: Издательство Московского университета, 2013. – 192 с., ил. – (Серия «Суперкомпьютерное образование»)

ISBN 978-5-211-06530-7

З 86

В книге излагаются методы решения задач с помощью статистического моделирования. Рассматриваемые алгоритмы предназначены для использования в параллельных вычислениях на компьютерных комплексах различной архитектуры. Последовательно излагаются методы получения независимых потоков псевдослучайных чисел и случайных векторов с заданным законом распределения, методы 
приближенного вычисления интегралов высокой размерности и численного решения некоторых классов дифференциальных уравнений в обыкновенных и частных 
производных, методы имитационного моделирования.
Книга ориентирована на студентов, знакомящихся с элементами вычислительной математики и параллельного программирования, а также на исследователей, 
применяющих численное моделирование для решения прикладных задач.
Ключевые слова: статистическое моделирование, имитационное моделирование, 
методы Монте-Карло, численные методы, методы параллельных вычислений.

УДК 007 (075) 
ББК 32.973.2

УДК 007 (075) 
ББК 32.973.2
З 86

Уважаемый читатель!

Вы держите в руках одну из книг серии «Суперкомпьютерное образование», выпущенную в рамках реализации проекта комиссии Президента 
РФ по модернизации и технологическому развитию экономики России 
«Со здание системы подготовки высококвалифицированных кадров в области суперкомпьютерных технологий и специализированного программного обеспечения». Инициатором издания выступил Суперкомпьютерный консорциум университетов России.
Серия включает более 20 учебников и учебных пособий, подготовленных ведущими отечественными специалистами в области супер ком пьютерных технологий. В книгах представлен ценный опыт преподавания 
супер компьютерных технологий в таких авторитетных вузах России, как 
МГУ, ННГУ, ТГУ, ЮУрГУ, СПбГУ ИТМО и многих других. При подготовке изданий были учтены рекомендации, сформулированные в Своде знаний и умений в области суперкомпьютерных технологий, подготовленном 
группой экспертов Суперкомпьютерного консорциума, а также международный опыт.
Современный уровень развития вычислительной техники и методов 
математического моделирования дает уникальную возможность для перевода промышленного производства и научных исследований на качественно новый этап. Эффективность такого перехода напрямую зависит 
от наличия достаточного числа высококвалифицированных специалистов. Данная серия книг предназначена для широкого круга студентов, 
аспирантов и специалистов, желающих изучить и практически использовать параллельные компьютерные системы для решения трудоемких вычислительных задач.

Издание серии «Суперкомпьютерное образование» наглядно де мон стрирует тот вклад, который внесли участники Суперкомпьютерного консорциума университетов России в создание национальной системы подготовки высококвалифицированных кадров в об ласти суперкомпью терных 
технологий, а также их четкое понимание ответственности за подготовку 
высококвалифицированных специалистов и формирование проч ного научного фундамента, столь необходимого для эффективного использования суперкомпьютерных технологий на практике.

Ректор Московского университета,
Президент Суперкомпьютерного консорциума 
университетов России,
академик РАН  В. А. Садовничий

Оглавление

Предисловие
10

Часть I. Основные понятия и методы
12

Глава 1. Модели и системы параллельных вычислений
13
1.1
Параллельные вычисления с общей памятью . . . . . . .
13
1.2
Параллельные вычисления с разделенной памятью
. . .
18

Глава 2. Генераторы псевдослучайных чисел
21
2.1
О генераторах псевдослучайных чисел . . . . . . . . . . .
21
2.2
Линейный конгруэнтный генератор . . . . . . . . . . . . .
25
2.3
Векторный линейный конгруэнтный генератор . . . . . .
27
2.4
Обобщенный генератор Фибоначчи с запаздыванием
. .
30
2.5
Векторный обобщенный генератор Фибоначчи с запаздыванием
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
2.6
Методы перетасовывания и комбинации . . . . . . . . . .
35
2.7
«Вихрь Мерсенна»
. . . . . . . . . . . . . . . . . . . . . .
37
2.8
Методы получения псевдослучайных последовательностей с равномерным распределением для параллельных
вычислений . . . . . . . . . . . . . . . . . . . . . . . . . . .
39
2.9
Некоторые реализации генераторов для параллельных
вычислений . . . . . . . . . . . . . . . . . . . . . . . . . . .
44

Глава 3. Моделирование случайных величин и векторов с
произвольным законом распределения
46
3.1
Моделирование дискретных случайных величин . . . . .
46
3.2
Моделирование непрерывных случайных величин . . . .
51
3.3
Моделирование случайных векторов . . . . . . . . . . . .
59

7

3.4
Моделирование случайных векторов с помощью многомерных цепей Маркова . . . . . . . . . . . . . . . . . . . .
70

Глава 4. Приближенное вычисление определенных интегралов методом Монте-Карло
74
4.1
Геометрический метод Монте-Карло . . . . . . . . . . . .
74
4.2
Метод математического ожидания . . . . . . . . . . . . .
77
4.3
Сравнение точности геометрического метода и метода математического ожидания. Мера трудоемкости . . . . . . .
81
4.4
Способы уменьшения дисперсии
. . . . . . . . . . . . . .
83
4.5
Метод Монте-Карло в параллельных вычислениях . . . .
87

Часть II. Примеры решения прикладных задач
101

Глава 5. Решение уравнений телеграфного типа
102
5.1
Пуассоновский процесс и его моделирование
. . . . . . .
102
5.2
Связь функционалов от пуассоновского процесса с дифференциальными уравнениями
. . . . . . . . . . . . . . .
106
5.3
Решение уравнений телеграфного типа методом МонтеКарло . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
110

Глава 6. Имитационное моделирование
118
6.1
Методы имитационного моделирования систем массового
обслуживания . . . . . . . . . . . . . . . . . . . . . . . . .
118
6.2
Оптимизация системы массового обслуживания в классе
алгоритмов разделения времени с переналадками
. . . .
126

Глава 7. Моделирование распространения зондирующего
излучения в многослойных биологических тканях
147
7.1
Постановка задачи на физическом уровне . . . . . . . . .
148
7.2
Алгоритм моделирования распространения зондирующего излучения в многослойных биологических тканях
. .
149
7.3
Результаты численных экспериментов . . . . . . . . . . .
155

Глава 8. Обзор задач, решаемых методом Монте-Карло
159
8.1
Приближенное вычисление интегралов Римана высокой
размерности
. . . . . . . . . . . . . . . . . . . . . . . . . .
159
8.2
Задача о приближенном решении линейного неоднородного интегрального уравнения . . . . . . . . . . . . . . . .
159

8

8.3
Решение задач Коши и граничных задач для основных
уравнений математической физики . . . . . . . . . . . . .
160
8.4
Вычисление континуальных интегралов . . . . . . . . . .
161
8.5
Линейное интерполирование функций многих переменных 162
8.6
Оценка абсолютного экстремума функций многих переменных . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
162
8.7
Численное решение стохастических дифференциальных
уравнений Ито . . . . . . . . . . . . . . . . . . . . . . . . .
162
8.8
Вычисление справедливой цены опционов . . . . . . . . .
163
8.9
Имитационное моделирование реальных систем
. . . . .
165
8.10 Картографирование и локализация для роботов . . . . .
166
8.11 Задачи математической статистики . . . . . . . . . . . . .
167

ПРИЛОЖЕНИЕ. Векторные вычисления
168

Обзор источников
176

Список алгоритмов
178

Предметный указатель
179

Литература
185

9

Предисловие

Идея использования случайных чисел многократно возникала в
умах математиков в разных странах и в разные времена. Одно из первых упоминаний о методе решения задачи с помощью случайных чисел
историки науки относят к 1876 году, когда статистик Эраст Лайман де
Форест использовал метод обратной функции для экспериментального исследования поведения остатков при сглаживании временного ряда. В работах отечественных ученых метод обратной функции носит
имя преобразования Н.В. Смирнова [10]. Еще ранее швейцарский астроном Рудольф Вольф в серии статей 1849–1850 годов использовал физический датчик случайности — натурный эксперимент — для оценки
по методу наименьших квадратов вероятности пересечения тонкой иглой одной из параллельных линий, нанесенных на плоскость (точное
решение задачи было получено ранее французским естествоиспытателем Ж. Бюффоном). Термин «метод Монте-Карло» восходит к другому
замечательному математику Станиславу Уламу, который использовал
датчик псевдослучайных чисел на только что появившейся электронной
вычислительной машине для моделирования ветвящихся процессов при
ядерном распаде. По его словам, название процедуры обязано присутствию в ней «. . . своеобразного элемента везения — получения случайных чисел, с которыми играют в соответствующие игры» (С. Улам, в
своей книге воспоминаний «Приключения математика», 1976). Отсюда
следует, что первые применения метода Монте-Карло относились как к
сфере интересов классических численных методов, так и к сфере имитационного моделирования реальных процессов (в физике).
Дальнейшее развитие метода статистического испытания неразрывно связано с развитием вычислительной техники. Рост быстродействия позволил генерировать выборки большого объема для получения оценок исследуемых характеристик — с заданной надежностью и
за приемлемое время. Соответственно расширилась сфера применений
методов Монте-Карло [9, 10, 11, 12, 13, 17, 19, 29, 30, 36, 41].
В настоящее время исследователям в области прикладной математики становятся доступны вычислительные системы параллельного
действия. Оказывается при этом, что методы Монте-Карло позволяют получать высокую эффективность использования параллельных вычислительных процессов. Причина эффективности в том, что большую
часть времени занимает генерирование и обработка независимых копий некоторой случайной величины. Пусть имеется K вычислительных

10

устройств, а S > 0 и P > 0, S + P = 1 — доли последовательной и параллельной частей программы по отношению к общему времени выполнения программы одним процессом. Для метода Монте-Карло может
оказаться верным соотношение S ≪ P. Тогда, по известному второму
закону Амдала [2], максимальное ускорение

R =
1

S + P/K

приблизится к предельному значению K — числу процессоров.
Хотя имеется обширная журнальная и монографическая литература, посвященная теоретическим основам и приложениям методов
Монте-Карло, практически нет учебников и научных монографий, излагающих различные возможности применения параллельных вычислений к статистическим испытаниям, а информация рассеяна по публикациям в научных журналах и трудах конференций. Предлагаемая книга
собирает разрозненный материал и может служить вспомогательным
источником для студентов и заинтересованных лиц, встречающихся с
применением методов статистических испытаний в своей деятельности.
Материал книги может быть использован в общих и специальных курсах по методам вычислений и методам параллельного программирования. У читателя предполагается знание математического анализа и
основных понятий теории вероятностей, алгоритмических языков программирования высокого уровня (в книге для примеров используется
язык программирования С++) в объеме бакалавриата по математическим и физическим специальностям в ВУЗе.
Часть раздела 6.1, касающаяся кибернетического подхода, и раздел 6.2 отражают результаты исследований авторов. Приведенные примеры программ также написаны авторами. Раздел 7 книги предоставлен В.П. Гергелем и А.В. Горшковым. Большая часть книги написана на
основе литературы, указанной в списке литературы в конце книги. При
этом все неточности изложения, разумеется, лежат на совести авторов.
Авторы выражают признательность декану факультета вычислительной математики и кибернетики Нижегородского государственного университета им. Н.И. Лобачевского профессору В.П. Гергелю за
предложение написать эту книгу, равно как за внимание, поддержку и
конструктивные замечания в процессе работы. Авторы также считают
необходимым выразить благодарность рецензентам, чей труд позволил
существенно улучшить окончательный текст.

11

Часть I

ОГлава 1. Модели и системы параллельных
вычислений

1.1. Параллельные вычисления с общей памятью

Для выполнения последовательных программ достаточно компьютера, схематически изображенного на рис. 1.1. Такой компьютер
имеет центральный процессор и оперативную память, к которой процессор обращается для выбора очередной команды и данных для обработки. Память здесь может пониматься в достаточно широком смысле
и включать как оперативную, так и внешнюю память. Процессор принципиально последовательный: в каждый момент времени он может выполнять команды только из одной программы (задачи, потока команд).
На аппаратном уровне такой процессор может включать механизм переключения между программами. Каждой из присутствующих в компьютере программ выделяется некоторый квант процессорного времени, и
процессор в определенном порядке предоставляет свои ресурсы программе за программой. Со стороны пользователя возникает иллюзия
параллельной работы многих программ. Ответственность за переключение между программами и сохранность их рабочих данных ложится
на операционную систему.

Процессор

Память

Данные

Рис. 1.1. Схема компьютера для последовательных вычислений

Рассмотрим две программы, выполняющие различные функции,
например, текстовый редактор и проигрыватель видео. Запущенные
вместе эти программы практически не должны взаимодействовать друг

13

с другом и основной функцией операционной системы будет разграничение памяти для обеих программ. В этом случае каждая программа
будет реализована в виде отдельного процесса. Каждый процесс, таким
образом, характеризуется своей областью памяти (под команды и данные), возможностями доступа к устройствам ввода-вывода и прочим системным ресурсам, в том числе и к функциям операционной системы.
Как правило, порождение нового процесса операционной системой —
достаточно времязатратная операция, а взаимодействие процессов осуществляется через специальные процедуры передачи данных. Создание
разделяемых участков памяти, видимых несколькими процессами, также возможно, но должно тщательно планироваться программистом и
требует вызова специальных функций операционной системы.
В то же время, работа текстового редактора может заключаться
в одновременной обработке нового вводимого пользователем текста и в
проверке орфографии с грамматикой. Обе задачи должны выполняться
в рамках одной программы, видеть один и тот же рабочий материал,
активно взаимодействовать друг с другом — оперативно реагировать
на ввод и редактирование пользователя, начинать грамматический разбор сначала при добавлении или удалении слов и знаков препинания.
При открытии файла с диска можно проверять орфографию одновременно на разных страницах. Более того, некоторые функции должны
легко приостанавливаться и возобновлять выполнение. В этом случае
используют второе средство организации параллельной работы — потоки. Один процесс может порождать потоки, которые будут исполняться
параллельно друг с другом (то есть в режиме разделения времени процессора). Все потоки, имеющие общего родителя, разделяют общую память (область данных), но каждый поток имеет свой собственный стек.
Как правило, поток создается для выполнения конкретной функции.
Однако эта функция может вызывать другие функции.
Чтобы обеспечить действительно одновременное исполнение команд из разных процессов и потоков, были разработаны многопроцессорные компьютеры с общей памятью (рис. 1.2). В настоящее время
появились также доступные многоядерные процессоры, реализующие
в принципе ту же архитектуру. Теперь за один квант времени могут
исполняться команды стольких процессов (потоков), сколько имеется
физических процессоров (ядер).
Рассмотрим задачу о вычислении суммы

zi = xi + yi,
i = 1, 2, . . . , n
(1.1)

14