ПАРАЛЕЛЬНІ МЕТОДИ ІНТЕГРУВАННЯ. ВИКОРИСТАННЯ ФУНКЦІЙ КОЛЕКТИВНОГО ОБМІНУ MPI

Мета роботи: продовжити вивчення функцій обміну бібліотеки MPI, зокрема, функцій колективного обміну. Вивчити деякі прийоми їх використання для розподілення даних та обчислень між паралельними процесорами.

5.1 Паралельний метод обчислення визначених інтегралів

5.1.1 Теоретичні відомості

Для тестування паралельних систем часто використовують задачу наближеного обчислення числа (пі) за допомогою відомої формули:

. (5.1)

Даний інтеграл можна обчислити, наприклад, за допомогою методу прямокутників:

, (5.2)

де , ;

– крок дискретизації;

– кількість підінтервалів.

Підінтегральний вираз (функція ) в наведеній формулі методу прямокутників може обчислюватись в кожній i-й точці дискретизації незалежно, тому задача добре розпаралелюється (має внутрішній паралелізм). Можлива реалізація алгоритму у вигляді паралельної програми наводиться нижче.

Програма 5.1

#include <mpi.h>

#include <math.h>

#include <stdio.h>

int main(int argc,char **argv)

{

int done=0,n,myid,numprocs,i;

double PI25DT=3.141592653589793238462643;

double mypi,pi,h,sum,x;

MPI_Init(&argc,&argv);

MPI_Comm_size(MPI_COMM_WORLD,&numprocs);

MPI_Comm_rank(MPI_COMM_WORLD,&myid);

while (!done)

{

if(myid==0)

{

printf("Enter the number of intervals: (0-quit)");

scanf("%d",&n);

}

MPI_Bcast(&n,1,MPI_INT,0,MPI_COMM_WORLD);

if(n==0)

break;

h=1.0/(double)n;

sum=0.0;

for(i=myid+1;i<=n;i+=numprocs)

{

x=h*((double)i-0.5);

sum+=4.0/(1.0+x*x);

}

mypi=h*sum;

MPI_Reduce(&mypi,&pi,1,MPI_DOUBLE,MPI_SUM,0,

MPI_COMM_WORLD);

if(myid==0)

printf("pi is approximately %.16f,

Error is %.16f\n",pi,fabs(pi-PI25DT));

}

MPI_Finalize();

return 0;

}

5.1.2 Завдання

5.1.2.1 Розробити послідовні алгоритм та программу обчислення числа з можливістю вимірювання часу роботи програми для заданого n та визначення помилки апроксимації інтеграла. Для цього використовуйте функцію вимірювання часу бібліотеки MPI, як еталонне значення числа прийміть 3.141592653589793238462643.

Дослідіть точність та швидкодію програми обчислення для значень кількості інтервалів 10³, 10⁴, 10⁵, 10⁶, 10⁷, 10⁹. Результати подайте у звіті у вигляді таблиці.

5.1.2.2 Реалізуйте власну паралельну програму обчислення інтеграла (1) з використанням наведеної програми 1,додайте до неї функцію обчислення часу її виконання. Визначте прискорення паралельної програми для чотирьох процесорів.

5.1.2.3 Використовуючи опановану техніку інтегрування, розробіть послідовні алгоритм та програму обчислення інтеграла у відповідності до наведених нижче варіантів. В програмі реалізуйте введення кількості інтервалів з клавіатури. Дослідіть точність та швидкодію програми для значень кількості інтервалів 10³, 10⁴, 10⁵, 10⁶, 10⁷, 10⁹. Результати подайте у звіті у вигляді таблиці.

Перший варіант. Обчислити інтеграл .

Другий варіант. Обчислити інтеграл .

5.2 Паралельна реалізація метода Монте-Карло

5.2.1 Теоретичні відомості

При інтегруванні складних функцій та складній формі області інтегрування можна використовувати метод Монте-Карло, для якого в деяких випадках необхідно менше обчислень підінтегральної функції.

Пояснимо суть методу на простому прикладі.

Площа кола та площа описаного навколо неї квадрата обчислюються за формулами:

, .

За допомогою генератора випадкових чисел будемо генерувати координати точок, що рівномірно розподілені усередині квадрата R, одночасно підраховуючи кількість точок, які опинились в межах кола С (рис.5.1). Припустимо, кількість згенерованих точок дорівнює n, а кількість точок, які опинились в межах кола дорівнює m (). Тоді, при досить великому n відношення m до n буде пропорційним відношенню площі кола до площі квадрата (внаслідок рівномірності розподілу), тобто:

, (5.3)

отже:

(5.4)

Рисунок 5.1 – Обчислення числа методом Монте-Карло

Отримане значення числа є випадковим. Виконаємо серію N незалежних реалізацій обчислення числа таким способом. Позначимо отримані значення числа як , , …, , а їх середнє

.

Тоді при досить великому N для похибки середнього обчисленого значення числа внаслідок центральної граничної теореми і згідно з відомим правилом "трьох сигм" можна записати

, (5.5)

тобто нерівняння виконується з ймовірністю, досить близькою до одиниці (), де – дисперсія випадкової величини , .

Розглянемо інтеграл

. (5.6)

Нехай – рівномірно розподілена на відрізку [0, 1] випадкова величина, тобто, її щільність розподілу ймовірностей:

Тоді також буде деякою випадковою величиною, до того ж її математичне сподівання

Таким чином,

, (5.7)

де – незалежні реалізації рівномірно розподіленої на відрізку [0, 1] випадкової величини .

Якщо – задана припустима похибка обчислення інтеграла, то відповідно до (5.5) з ймовірністю, близькою до одиниці, має бути

, (5.8)

звідки випливає, що для досягнення похибки порядку необхідно обчислити

(5.9)

значень функції f.

Кратні інтеграли обчислюють аналогічно:

, (5.10)

де , – незалежні реалізації рівномірно розподілених на [0, 1] випадкових величин , .

Інтегрування методом Монте-Карло також зручно використовувати, якщо необхідно обчислити кратний інтеграл по деякій області , яка має складну форму.

В цьому випадку припускають

, (5.11)

де R – квадрат, який містить задану область (рис. 5.2),

Далі використовують формулу (5.10).

Рисунок 5.2 – – область інтегрування.

Розв’язання задач методом Монте-Карло добре розпаралелюється, оскільки генерувати випадкові числа та обчислювати від них функції можна незалежно в різних процесах. При цьому, як правило, загальна кількість необхідних обчислень (генерування випадкових чисел, обчислення функцій та їх підсумовування) рівномірно розподіляють між процесорами.

Нижче наведена програма для обчислення числа методом Монте-Карло за формулою (5.4).

Програма 5.2

#include "mpi.h"

#include <stdio.h>

#include <math.h>

#include <time.h>

#define n_in_proc 1000000

#define RAND_MAX 2147483647

int main(int argc,char *argv[])

{

time_t t;

int rank,numprocs,i,N_in_proc;

long j,in_circle=0L,total_in_circle,total;

double x,y,R=0.5,approx,

pi=3.141592653589793238462643;

MPI_Init(&argc,&argv);

MPI_Comm_size(MPI_COMM_WORLD,&numprocs);

MPI_Comm_rank(MPI_COMM_WORLD,&rank);

if(rank==0) N_in_proc=atoi(argv[1]);

MPI_Bcast(&N_in_proc,1,MPI_INT,0,MPI_COMM_WORLD);

for(i=0;i<N_in_proc;i++)

{

srand((unsigned)time(&t));

for (j=0L;j<n_in_proc;j++)

{

x=rand()/(double)RAND_MAX-0.5;

y=rand()/(double)RAND_MAX-0.5;

if(x*x+y*y<R*R)

in_circle++;

}

MPI_Reduce(&in_circle,&total_in_circle,1,MPI_INT,

MPI_SUM,0,MPI_COMM_WORLD);

if(rank==0)

{

total=n_in_proc*(i+1)*numprocs;

approx=4.0*((double)total_in_circle/total);

printf("pi=%.16f; error=%.16f, points=%ld\n",

approx,fabs(pi-approx),total);

}

}

MPI_Finalize();

return 0;

}

В даній програмі кожний процес виконує N_in_proc реалізацій обчислення числа , кількість реалізацій визначається з командного рядку. В кожній реалізації n_in_proc раз генеруються "випадкові" значення координат x та y точки всередині квадрата [-0.5, 0.5]´[-0.5, 0.5] та визначається кількість точок (змінна in_circle), які опинились в межах кола з радіусом 0.5.

5.2.2 Завдання 1

5.2.2.1 Програму 5.2 доповніть функцією обчислення часу її виконання та функцією обчислення дисперсії випадкової величини значення

, (5.12)

причому, оскільки середнє значення заздалегідь не відомо, зручніше використати формулу

. (5.13)

5.2.2.2 Використовуючи формули (5.9) визначити N таке, щоб похибка обчислення числа наближено дорівнювала 10^-4.

5.2.2.3 Підібрати для знайденого N параметри N_in_proc та n_in_proc для випадку використання двох та чотирьох процесів і за допомогою доповненої програми обчислити число , показати, що виконується відношення (5.8).

5.2.2.4 Визначити прискорення паралельної програми для двох та чотирьох процесорів.

5.2.2.5 Проведені розрахунки та експериментальні результати навести у звіті.

Программа 5.3 реалізує послідовний алгоритм обчислення інтеграла (5.1) методом Монте-Карло.

Програма 5.3

#include <stdio.h>

#include <math.h>

#include <time.h>

#define N 1000000000L

#define RAND_MAX 2147483647L

int main(int argc, char *argv[])

{

time_t t;

long i;

double x, mc_pi=0.0,

pi=3.141592653589793238462643;

srand((unsigned) time(&t));

mc_pi=0.0;

for(i=0L;i<N;i++)

{

x=rand()/(double)RAND_MAX;

mc_pi+=(4.0/(1.0+x*x))/N;

}

printf("mc_pi=%.16lf err=%.15lf

points=%ld\n", mc_pi,fabs(pi-mc_pi),i);

return 0;

}

5.2.3 Завдання 2

5.2.3.1 Розробити паралельну програму інтегрування методом Монте-Карло, використовуючи програму 5.3.

5.2.3.2 Допрацювати програму та провести дослідження аналогічно завданню за п. 5.2.2.

5.2.3.3 Виконати наступні варіанти завдання.

Варіант 1: Розробити паралельну програму для обчислення кратного інтеграла , де , S – область, яка міститься між , та , (точне значення інтеграла дорівнює ).

Варіант 2: Розробити паралельну програму для обчислення кратного інтеграла , де , S – чверть кола , , (точне значення інтеграла дорівнює ).

5.3 Зміст звіту

5.3.1 Мета лабораторної роботи.

5.3.2 Тексти програм.

5.3.3 Результати розрахунків.

5.3.4 Відповіді на контрольні питання.

5.4 Контрольні питання

3.1 Проаналізуйте програму 5.1. Нехай інтервал інтегрування складається з 10 підінтервалів (0, 1, 2 і т.д.), а кількість процесорів дорівнює чотирьом. Назвіть номери підінтервалів, в яких обчислює підінтегральну функцію кожний з процесорів.

3.2 Чи залежить прискорення обчислення числа за допомогою програми 1 від кількості підінтервалів?

3.3 Порівняйте точності обчислень числа за допомогою програм 5.1 та 5.3. Які Ваші висновки щодо точності реалізованих в програмах 5.1 та 5.3 методів?

3.4 Як в MPI визначити розмір буфера, необхідного для прийому повідомлень?

3.5 Що таке групи процесів в MPI? За допомогою яких функцій бібліотеки MPI їх можна створити?

3.6 Як здійснити обмін даними між процесами групи?

3.7 Поясніть призначення і роботу функції

MPI_Comm_split(MPI_Comm comm,int split,

int key,MPI_Comm *newcomm);

3.8 Чи можуть декілька комунікаторів в одній паралельній програмі мати однакові ідентифікатори?

ЛАБОРАТОРНА РОБОТА № 6

Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычис­лить, когда этот...

Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом...

Что способствует осуществлению желаний? Стопроцентная, непоколебимая уверенность в своем...

Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: