работа (стр. 4 из 7)

(3.1.6)

Определим некоторую величину S_N:

(3.1.7)

Из указанных выше свойств величин s_i следует, что [1]:

	(3.1.8)
	(3.1.9)

Таким образом, получив N случайных чисел ξ_i и вычислив в них значения функции f, можем определить величину I_N, которая при N больших даст, приближенно, интеграл I.

Для случайных чисел с равномерным законом распределения получаем:

(3.1.10)

Формулы (3.1.7) и (3.1.10) определяют первый способ вычисления интегралов методом статистических испытаний или методом Монте-Карло. Назовем его методом средних значений.

Задав уровень надежности η, с которым желательно получить приближенное значение интеграла, можем применить неравенство Чебышева [1, 2] для определения условия прекращения итерационного процесса, причем это неравенство выполняется с вероятностью 1 – η:

(3.1.11)

Для законности применения неравенства Чебышева нужно выполнение предположения о независимости распределения любых точек ξ_i.

Так как нам не известна функция распределения F(ξ), на практике будем использовать следующее условие прекращения итерационного процесса (дальше – условие выхода): если модуль разности значений оценок интеграла (3.1.3) на предыдущем и текущем шагах меньше либо равен заданной величины ошибки ε, прекратить выполнение процедуры:

(3.1.12)

Кроме вариации метода Монте-Карло, описанного в предыдущем пункте, для вычисления однократного интеграла можно определить еще один способ – метод площадей. Поясним метод площадей на примере. Пусть дана некоторая, в общем случае знакопеременная, функция f(x), пределы интегрирования a и b (рис. 3.1.1). Интеграл (3.1.1) будет представлять собой, в этом случае, общую площадь заштрихованных на рисунке 3.1.1 частей. Обозначим площадь прямоугольника, в который вписана кривая f(x), – S, искомую площадь – σ. Каким-либо образом получим N случайных точек x и N случайных точек y, лежащих внутри прямоугольника.

Рис. 3.1.1

Если в заштрихованную область попало n пар точек, то искомая площадь будет выражаться формулой:

(3.1.13)

3.2. Параллельные алгоритмы вычисления

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

Если же мы обладаем параллельной системой, например, – кластером, то промежуточные расчеты в методе Монте-Карло могут осуществляться на разных узлах этого кластера, а окончательный результат обрабатываться на некоторой главной машине, так называемой корневой. Такая схема изображена на рис. 3.2.1:

Согласно рис. 3.2.1, генератор случайных чисел один для системы и, проходя сверху вниз по вычислителям, выдает каждому из них сгенерированное случайное число. Однако, из-за того, что информация должна быть передана между компьютерами, снижается производительность параллельной системы. Передаваться информация будет средствами, доступными в настоящее время. Скорость же передачи определяется для технологии Fast Ethernet до 12 Мбайт/с, более современные технологии SCI или Myrinet от 80 Мбайт/с [9]. Кроме значительной разницы в пропускной способности, последние высокоскоростные технологии имеют значительно меньшую латентность (5-10 мкс против 150-300 мкс Fast Ethernet). Основной недостаток этих технологий – стоимость, превышающая, порой, стоимость вычислительных элементов.

Рис. 3.2.1. Упрощенная схема параллельного алгоритма метода Монте-Карло

Чтобы свести обмен сообщениями к минимуму можно каждому вычислителю предоставить свой генератор случайных (псевдослучайных) чисел. Кроме того, генератором и вычислителем может быть один и тот же процесс. Кроме того, в одном, главном процессе могут быть объединены генератор, вычислитель и анализатор. Именно такая схема и была реализована в работе. Графически она изображена на рис. 3.2.2:

В работе были разработаны и реализованы три параллельных алгоритма вычисления однократных интегралов методом Монте-Карло на кластере MPI, основанные на модели рис. 3.2.2.

Все три алгоритма базируются на использовании трех функций MPI [9]:

1. MPI_BARRIER (comm): входной параметр comm (тип – дескриптор) является коммуникатором группы, в которой выполняется коллективная операция. Эта функция – функция барьерной синхронизации, блокирует вызывающий ее процесс, пока все процессы группы не вызовут функцию. В каждом процессе управление возвращается только тогда, когда все процессы в группе вызовут MPI_BARRIER.

Синхронизацией называется установление правильной очередности процессов. Необходимость в синхронизации вызывается либо распределением общего ресурса между процессами, либо логической зависимостью процессов друг от друга.

2. MPI_REDUCE (sendbuf, recvbuf, count, datatype, op, root, comm): входной параметр sendbuf (тип – альтернатива) содержит адрес буфера посылки; recvbuf (тип – альтернатива) содержит адрес принимающего буфера (используется только корневым процессом); count (тип – целое) количество элементов в посылающем буфере; datatype (тип – дескриптор) тип данных буфера посылки; op (тип – дескриптор) содержит операцию редукции; root (тип – целое) номер главного процесса; comm (тип – дескриптор) коммуникатор группы, в которой выполняется коллективная операция. Функция MPI_REDUCE объединяет элементы входного буфера каждого процесса, используя операцию op, и возвращает объединенное значение в выходной буфер процесса с номером root.

3. MPI_BCAST (buffer, count, datatype, root, comm): двусторонний (входной/выходной) параметр buffer (тип – альтернатива) содержит адрес начала буфера посылки/приема; входной параметр count (тип – целое) содержит количество записей в буфере; входной параметр datatype (тип – дескриптор) описывает тип данных в буфере; входной параметр root (тип – целое) содержит номер корневого процесса; входной параметр comm (тип – дескриптор) является коммуникатором группы, в которой выполняется коллективная операция. Функция широковещательной передачи MPI_BCAST посылает сообщение из корневого процесса всем процессам группы, включая себя. Она вызывается всеми процессами группы с одинаковыми аргументами для comm, root. В момент возврата управления содержимое корневого буфера обмена будет уже скопировано во все процессы.

Интерфейсы функций (Integral1DMK_par(…), Integral1DMK_par1(…), Integral1DMK_par2(…)), реализующих все три алгоритма приведены в приложении 3, а их реализации – в приложении 4.

Рассмотрим все три алгоритма.

1. Алгоритм, в основе которого лежит скалярный параллелизм, т.е. распараллеливание цикла, реализован в функции Integral1DMK_par(…). В этом алгоритме генерация чисел осуществляется с некоторым шагом равным отношению интервала интегрирования к количеству генерируемых точек. Это позволяет, по мере уменьшения шага, добиваться равномерного распределения чисел по оси координат. Как следствие – увеличение сходимости метода, а также повышение точности вычислений.

В этом алгоритме каждый процесс выполняет следующие основные шаги:

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

- Начало внешнего цикла.

- Инициализация переменных, содержащих значение интеграла на двух соседних итерациях (для проверки условия выхода).