Вычисление числа π методом Монте-Карло
Для
вычисления значения πможно
использовать метод ‘стрельбы’. В
применении к данному случаю метод
заключается в генерации равномерно
распределенных
на
двумерной области [0 ≤
x
≤
1,
0 ≤
y
≤
1]
точек и определении 
.
Вычисленное таким образом значение π является приближенным, в общем случае точность вычисления искомого значения повышается с увеличением числа ‘выстрелов’ и качества генетатора случайных чисел; подобные методы используются в случае трудностей точной числовой оценки.
Параллельный алгоритм вычисления числа π данным методом во многом похож на предыдущий рассмотренный нами алгоритм. Для генерации случайных чисел нужно использовать функцию srand, которой в качестве агрумента (семени последовательности) задавать ранг процесса, таким образов, у каждого процесса будет своя последовательность.
#include <stdlib.h>
void srand(unsigned seed);
Функция srand() устанавливает исходное число для последовательности, генерируемой функцией rand().
#include <stdlib.h>
int rand(void);
Функция rand() генерирует последовательность псевдослучайных чисел. При каждом обращении к функции возвращается целое в интервале между нулем и значением RAND_MAX.
Для сбора результата здесь также удобно использовать MPI_Reduce с заданием операции суммирования (MPI_SUM), затем разделить полученную сумму на число процессоров, получив среднее арифметическое.
int MPI_Reduce(void* sendbuf, void* recvbuf, int count,
MPI_Datatype datatype, MPI_Op op, int root, MPI_Comm comm);
Параметры:
sendbuf адрес посылающего буфера
recvbuf адрес принимающего буфера
count количество элементов в посылающем буфере (целое)
datatype тип данных элементов посылающего буфера
op операция редукции
root номер главного процесса (целое)
comm коммуникатор
int MPI_Bcast( void *buffer, int count, MPI_Datatype datatype, int root,
MPI_Comm comm );
Параметры:
buffer адрес посылающего/принимающего буфера
count количество элементов в посылающем буфере (целое)
datatype тип данных элементов посылающего буфера
root номер главного процесса (целое)
comm коммуникатор
Задание: в соответствии с номером варианта откомпилировать и запустить параллельную программы, вычисляющую число π по заданному алгоритму.
Запустить задачу на одном узле и с кластера, на заданном количестве узлов. Оценить время выполнения вычислений, точность и коэффициент распараллеливания Амдала с учетом сетевой задержки теоретически и по результатам выполнения работы.
Варианты заданий
№ Варианта |
Алгоритм |
Число процессоров |
Число итераций на каждом процессоре |
1 |
Численное интегрирование |
10 |
100000 |
2 |
Монте-Карло |
16 |
50000 |
3 |
Численное интегрирование |
8 |
100000 |
4 |
Монте-Карло |
9 |
10000 |
5 |
Численное интегрирование |
11 |
40000 |
6 |
Монте-Карло |
13 |
40000 |
7 |
Численное интегрирование |
12 |
50000 |
8 |
Монте-Карло |
18 |
100000 |
9 |
Численное интегрирование |
17 |
30000 |
10 |
Монте-Карло |
15 |
70000 |
11 |
Численное интегрирование |
10 |
90000 |
12 |
Монте-Карло |
14 |
100000 |
13 |
Численное интегрирование |
17 |
40000 |
14 |
Монте-Карло |
16 |
80000 |
15 |
Численное интегрирование |
11 |
200000 |
16 |
Монте-Карло |
12 |
150000 |
17 |
Численное интегрирование |
14 |
180000 |
18 |
Монте-Карло |
10 |
120000 |
19 |
Численное интегрирование |
15 |
70000 |
20 |
Монте-Карло |
18 |
140000 |