|
ПАРАЛЕЛЬНІ МЕТОДИ ІНТЕГРУВАННЯ. ВИКОРИСТАННЯ ФУНКЦІЙ КОЛЕКТИВНОГО ОБМІНУ MPIМета роботи: продовжити вивчення функцій обміну бібліотеки MPI, зокрема, функцій колективного обміну. Вивчити деякі прийоми їх використання для розподілення даних та обчислень між паралельними процесорами.
5.1 Паралельний метод обчислення визначених інтегралів 5.1.1 Теоретичні відомості Для тестування паралельних систем часто використовують задачу наближеного обчислення числа
Даний інтеграл можна обчислити, наприклад, за допомогою методу прямокутників:
де
Підінтегральний вираз (функція Програма 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 Розробити послідовні алгоритм та программу обчислення числа Дослідіть точність та швидкодію програми обчислення 5.1.2.2 Реалізуйте власну паралельну програму обчислення інтеграла (1) з використанням наведеної програми 1,додайте до неї функцію обчислення часу її виконання. Визначте прискорення паралельної програми для чотирьох процесорів. 5.1.2.3 Використовуючи опановану техніку інтегрування, розробіть послідовні алгоритм та програму обчислення інтеграла у відповідності до наведених нижче варіантів. В програмі реалізуйте введення кількості інтервалів з клавіатури. Дослідіть точність та швидкодію програми для значень кількості інтервалів 103, 104, 105, 106, 107, 109. Результати подайте у звіті у вигляді таблиці. Перший варіант. Обчислити інтеграл Другий варіант. Обчислити інтеграл 5.2 Паралельна реалізація метода Монте-Карло
5.2.1 Теоретичні відомості При інтегруванні складних функцій та складній формі області інтегрування можна використовувати метод Монте-Карло, для якого в деяких випадках необхідно менше обчислень підінтегральної функції. Пояснимо суть методу на простому прикладі. Площа кола
За допомогою генератора випадкових чисел будемо генерувати координати точок, що рівномірно розподілені усередині квадрата R, одночасно підраховуючи кількість точок, які опинились в межах кола С (рис.5.1). Припустимо, кількість згенерованих точок дорівнює n, а кількість точок, які опинились в межах кола дорівнює m (
отже:
Рисунок 5.1 – Обчислення числа Отримане значення числа
Тоді при досить великому N для похибки середнього обчисленого значення числа
тобто нерівняння
Розглянемо інтеграл
Нехай Тоді Таким чином,
де Якщо
звідки випливає, що для досягнення похибки порядку
значень функції f. Кратні інтеграли обчислюють аналогічно:
де Інтегрування методом Монте-Карло також зручно використовувати, якщо необхідно обчислити кратний інтеграл по деякій області В цьому випадку припускають
де R – квадрат, який містить задану область Далі використовують формулу (5.10).
Рисунок 5.2 –
Розв’язання задач методом Монте-Карло добре розпаралелюється, оскільки генерувати випадкові числа та обчислювати від них функції можна незалежно в різних процесах. При цьому, як правило, загальна кількість необхідних обчислень (генерування випадкових чисел, обчислення функцій та їх підсумовування) рівномірно розподіляють між процесорами. Нижче наведена програма для обчислення числа
Програма 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 реалізацій обчислення числа
5.2.2 Завдання 1
5.2.2.1 Програму 5.2 доповніть функцією обчислення часу її виконання та функцією обчислення дисперсії
причому, оскільки середнє значення
5.2.2.2 Використовуючи формули (5.9) визначити N таке, щоб похибка 5.2.2.3 Підібрати для знайденого N параметри N_in_proc та n_in_proc для випадку використання двох та чотирьох процесів і за допомогою доповненої програми обчислити число 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: Розробити паралельну програму для обчислення кратного інтеграла Варіант 2: Розробити паралельну програму для обчислення кратного інтеграла 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 Чи залежить прискорення обчислення числа 3.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 ![]() ![]() Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам... ![]() Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)... ![]() ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала... ![]() Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|