Размещено на http://www.allbest.ru/

ЗАВДАННЯ

Теоретична частина.

1) Методи сортування лінійних масивів й можливі способи їх розпаралелювання. Їхні переваги, недоліки. (варіант № 10)

Практична частина.

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

2) Розробити паралельну програму множення матриць або сортування

Множення квадратної матриці на вектор. (варіант № 1)



ЗМІСТ

ВСТУП

1. ТЕОРЕТИЧНА ЧАСТИНА. ВАРІАНТ 10. МЕТОДИ СОРТУВАННЯ ЛІНІЙНИХ МАСИВІВ Й МОЖЛИВІ СПОСОБИ ЇХ РОЗПАРАЛЕЛЮВАННЯ. ЇХНІ ПЕРЕВАГИ, НЕДОЛІКИ

1.1 Сортування простими обмінами, сортування бульбашкою

1.2 Паралельна реалізація методу бульбашкового сортування

1.3 Сортування Шелла

1.4 Паралельна реалізація сортування Шелла

1.5 Швидке сортування

1.6 Паралельна реалізація швидкого сортування

2. ПРАКТИЧНА ЧАСТИНА

2.1 Програма паралельного розрахунку визначеного інтеграла

2.2 Розробка паралельної програми множення квадратної матриці на вектор

ВИСНОВКИ

ПЕРЕЛІК ПОСИЛАНЬ



ВСТУП

Створення багатопроцесорних (паралельних) обчислювальних систем (ПОС) є стратегічною лінією розвитку комп'ютерної техніки, що обумовлюється існуванням в теперішній момент часу актуальних завдань фундаментальної і прикладної науки, для аналізу і дослідження яких продуктивності існуючих засобів обчислювальної техніки виявляється недостатньо. Основними стримуючими чинниками широкого розповсюдження ПОС являються:

- висока вартість ПОС;

- різноманітність архітектурної побудови ПОС;

- трудомісткість розробки ефективних паралельних алгоритмів і програм.

Подолання першого стримуючого чинника по широкому використанню паралельних обчислень (висока вартість ПОС) може бути отримано шляхом побудови кластерних обчислювальних систем (clusters). Під кластером зазвичай розуміється безліч окремих комп'ютерів, об'єднаних в мережу, для яких за допомогою спеціальних апаратно-програмних засобів забезпечується можливість уніфікованого управління, надійного функціонування і ефективного використання. Застосування кластерів може також в деякій мірі зменшити проблеми, пов'язані з розробкою паралельних алгоритмів і програм, оскільки підвищення обчислювальної потужності окремих процесорів дозволяє будувати кластери з порівняно невеликої кількості (декілька десятків) окремих комп'ютерів. Це призводить до того, що для паралельного виконання в алгоритмах рішення обчислювальних завдань досить виділяти тільки великі незалежні частини розрахунків, що, у свою чергу, знижує складність побудови паралельних методів обчислень і зменшує потоки передачі даних між комп'ютерами кластера. Вирішення проблеми різноманітності архітектури паралельних обчислювальних систем і забезпечення можливості створення мобільних програм полягає у розробці стандартизованого базового системного програмного забезпечення для організації паралельних обчислень. Основним стандартом, що широко використовується нині в практичних застосуваннях, є інтерфейс передачі повідомлень (message passing interface - MPI).



1. ТЕОРЕТИЧНА ЧАСТИНА. ВАРІАНТ 10. МЕТОДИ СОРТУВАННЯ ЛІНІЙНИХ МАСИВІВ Й МОЖЛИВІ СПОСОБИ ЇХ РОЗПАРАЛЕЛЮВАННЯ. ЇХНІ ПЕРЕВАГИ, НЕДОЛІКИ

1.1 Сортування простими обмінами, сортування бульбашкою

Сортування простими обмінами, сортування бульбашкою (англ. bubble sort)- простий алгоритм сортування. Для розуміння і реалізації цей алгоритм - найпростіший, але ефективний він лише для не великих масивів. Складність алгоритму: O (n 2).

Алгоритм вважається навчальним і практично не застосовується поза навчальної літератури, замість нього на практиці застосовуються більш ефективні алгоритми сортування. У той же час метод сортування обмінами лежить в основі деяких більш досконалих алгоритмів, таких як шейкерні сортування, пірамідальна сортування і швидке сортування.

Алгоритм складається з повторюваних проходів по масиву. За кожен прохід елементи послідовно порівнюються попарно і, якщо порядок у парі невірний, виконується обмін елементів. Проходи по масиву повторюються N -1 раз або до тих пір, поки на черговому проході не буде зрозуміло, що обміни більше не потрібні, що означає - масив відсортований. Під час кожного проходу алгоритму по внутрішньому циклу, черговий найбільший елемент масиву ставиться на своє місце в кінці масиву, поруч з попереднім найбільшим елементом. Найменший елемент переміщається на одну позицію до початку масиву («спливає» до потрібної позиції як бульбашка у воді, звідси і назва алгоритму).

Приклад:

Візьмемо масив з числами «5 1 4 2 8» і відсортуємо значення за зростанням, використовуючи сортування бульбашкою. Виділено ті елементи, які порівнюються на даному етапі.

Перший прохід:

(5 1 4 2 8) (1 5 4 2 8), тут алгоритм порівнює два перших елемента і змінює їх місцями.

(1 5 4 2 8) (1 4 5 2 8), міняє місцями, так як 5> 4

(1 4 5 2 8) (1 4 2 5 8), міняє місцями, так як 5> 2

(1 4 2 5 8) (1 4 2 5 8), Тепер, з огляду на те, що елементи стоять на своїх місцях (8> 5), алгоритм не міняє їх місцями.

Другий прохід:

(1 4 2 5 8) (1 4 2 5 8)

(1 4 2 5 8) (1 2 4 5 8), міняє місцями, так як

4> 2 (1 2 4 5 8) (1 2 4 5 8)

(1 2 4 5 8) (1 2 4 5 8)

Тепер масив повністю відсортований, але алгоритм не знає чи це так. Тому йому необхідно зробити повний прохід і визначити, що перестановок елементів не було.

Третій прохід:

(1 2 4 5 8) (1 2 4 5 8)

(1 2 4 5 8) (1 2 4 5 8)

(1 2 4 5 8) (1 2 4 5 8)

(1 2 4 5 8) (1 2 4 5 8)

Тепер масив відсортований і алгоритм може бути завершений.

1.2 Паралельна реалізація методу бульбашкового сортування

Для паралельної реалізації методу бульбашкового сортування використовуютьється модифікація, звана методом парно-непарної перестановки [. У найпростішомувипадку, сортування полягає в чергуванні двох етапів. На першому етапі масив розбивається на пари (а0, а1), (а2, а3), (а4, а5),. . . , (Ап-2, ап- 1), починається з парних індексів. У кожній парі ліворуч поміщається найменший елемент з двох, праворуч - найбільший з них. На другому етапі аналогічна обробка виконується в парах (а1, а2), (а3, а4), (а5, а6),. . . , (Ап-3, ап-2), починається з непарних індексів. Максимум через п повторень масив впорядковується. У розглянутому методі мається на увазі, що число процесорів дорівнює числу п елементів масиву. Така реалізація може бути використана в многопроцессорном комп'ютері, але для кластера робочих станцій вона не годиться, тому що витрати на пересилання сусідніх елементів будуть перевищувати час на виконання операцій з сортування. Щоб пристосувати метод до реалізації в розподіленої обчислювальної системі з p процесорів, всі п сортируємих елементів діляться на частини, що містять по п / p елементів. Кожна з частин розсилається в локальну пам'ять відповідного процесора і попередньо сортується в ньому яких-небудь швидким методом. Потім чергуються два етапи: Обмін фрагментами, що складаються з п / p елементів, між сусідніми процесорами (рис. 1.2.2). Цей обмін виконується по черзі: всередині парних пар процесорів з номерами (0,1), (2,3), (4,5)...; всередині непарних пар процесорів з номерами (1,2), (3,4), (5,6)...

Рис. 1.2.2 Порядок обміну фрагментами в парно-непарном сортуванні

У кожному процесорі виконується операція «порівняти і розділити». При її виконанні процесор об'єднує два упорядкованих фрагмента в один порядкований подвоєної довжини 2п / p. Для цього можна використовувати метод сортування злиттям («злити» два в один). Потім лівий процесор пари залишає у себе ліву половину результату, а правий процесор - праву половину Для виконання злиття необов'язково виконувати злиття елементів до отримання результату довжиною 2n / p. Досить у лівому процесорі зливати фрагменти, починаючи зліва, до отримання результату довжиною n / р, а у правому процесорі зливати, починаючи справа, також до отримання результату довжиною n / p. Обчислювальна трудомісткість методу дорівню:

Tp = (n / p) log (n / p) + 2n.

Показники прискорення та ефективності для р процесорів визначаються як:

Sp = n log n / ((n / p) log (n / p) + 2n),

Ep = n log n / (p ((n / p) log (n / p) + 2n)).

1.3 Сортування Шелла

Сортування Шелла (англ. Shell sort) - алгоритм сортування, що є вдосконаленим варіантом сортування вставками. Ідея методу Шелла полягає в порівнянні елементів, що стоять не тільки поруч, але і на певній відстані один від одного. Іншими словами - це сортування вставками з попередніми «грубими» проходами. Аналогічний метод удосконалення бульбашкового сортування називається сортування гребінцем.

Під час сортування Шелла спочатку порівнюються і сортуються між собою значення, віддалені один від одного на деякій відстані (про вибір значення див. нижче). Після цього процедура повторюється для деяких менших значень, а завершується сортування Шелла упорядкуванням елементів при (тобто звичайної сортуванням вставками). Ефективність сортування Шелла в певних випадках забезпечується тим, що елементи «швидше» встають на свої місця (в простих методах сортування, наприклад, бульбашкової, кожна перестановка двох елементів зменшує кількість інверсій у списку максимум на 1, а при сортуванні Шелла це число може бути більше).

Незважаючи на те, що сортування Шелла в багатьох випадках повільніше, ніж швидке сортування, вона має ряд переваг:

- відсутність потреби в пам'яті під стек;

- відсутність деградації при невдалих наборах даних - швидке сортування легко деградує до O (n 2), що гірше, ніж найгірше гарантований час для сортування Шелла.

Приклад (рис. 1.3.1):

Нехай дано список: А = (32,95,16,82,24,66,35,19,75,54,40,43,93,68) і

виконується його сортування методом Шелла, а в якості значень вибрані: 5, 3, 1.

На першому кроці упорядковаются підсписки А, складені з усіх елементів А, що розрізняються на 5 позицій, тобто підсписки А51 = (32,66,40), АБ2 = (95,35,43), Л5,3 = (16,19,93), Л5,4 = (82,75,68), Л5,5 = (24,54).

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

Процес завершується звичайної сортуванням вставками отриманого списку.

Рисунок 1.2.4. Сортування Шелла

1.4 Паралельна реалізація сортування Шелла

Щоб отримати паралельну реалізацію методу Шелла, необхідно об'єднати процесори комунікаційної мережі в топологію N-мірного гіперкуба. Для цього в мережі має бути 2N процесорів. Тоді максимальна відстань між елементами буде дорівнює N (2N вузлів, пов'язаних послідовно, мали б найбільшу відстань 2N - 1). На рис. 1.4.1 представлений приклад 3-мірного гіперкуба (має вигляд звичайного куба), у якого послідовність нумерації вершин (вузлів мережі) дозволяє використовувати код Грея при обході в порядку 0-1-3-2-6-7-5-4. Код Грея, який використовується для встановлення відповідності двох систем нумерації, характеризується тим, що номери сусідніх процесорів відрізняються тільки одним бітом двійкового подання.

На попередньому етапі виконується поділ вихідного масиву на 2N частин і розсилка кожної з них відповідного вузла кластера. Потім всі вузли кластера сортують свої частини масиву яким-небудь швидким методом.

Перед початком процесу сортування між вузлами, які є сусідніми, в структурі гіперкуба, організовуються комунікаційні зв'язки. На першому етапі послідовної реалізації методу Шелла обмін повинен виконуватися між віддаленими один від одного парами вузлів з номерами: 0 - 4, 1 - 5, 2 -6, 3 - 7. У паралельній реалізації операція «порівняти і розділити» також буде виконуватися між цими ж парами вузлів. Однак відстань між вузлами в структурі гіперкуба буде дорівнювати не чотирьом, а одиниці.

Рисунок 1.3.1. Топологія гіперкуб

На наступному етапі, як і в послідовній реалізації методу, в групах з номерами 0-2-4-6 і 1-3-5-7 виконуються етапи звичайного парно-непарного сортування до тих пір, поки не припиниться зміна порядку значень. Операція «порівняти і розділити» завжди проводиться таким чином, що менша частина блоку залишається в процесорі, відповідної вершини гіперкуба з меншим номером, а більша частина - у процесорі з більшим номером.

На заключному етапі впорядковані частини збираються в єдиний впорядкований масив. Обмін фрагментами на всіх етапах (попередньому, основному і заключному) в топології гіперкуба виконується істотно швидше, ніж у лінійної топології. Чим більше розмірність гіперкуба, тим більш ефективно використання методу Шелла.

Трудомісткість розглянутого методу при числі ітерацій L (від 2 до р) визначається значенням:

Tp = (n / p) log (n / p) + (2n / p) log p + L (2n / p).

1.5 Швидке сортування

Швидке сортування (англ. quicksort), часто звана qsort на ім'я реалізації в стандартній бібліотеці мови Сі - широко відомий алгоритм сортування, розроблений англійським інформатиком Чарльзом Хоаром в МДУ в 1960 році. Один з швидких відомих універсальних алгоритмів сортування масивів (в середньому O (n log n) обмінів при упорядкуванні n елементів), хоча і має ряд недоліків.

Швидке сортування використовує стратегію «розділяй і володарюй». Кроки алгоритму такі:

- вибираємо в масиві певний елемент, який будемо називати опорним елементом. З точки зору коректності алгоритму вибір опорного елемента байдужий. З точки зору підвищення ефективності алгоритму вибиратися повинна медіана, але без додаткових відомостей про сортируемих даних її зазвичай неможливо отримати. Відомі стратегії: вибирати постійно один і той же елемент, наприклад, середній або останній за положенням; вибирати елемент з випадково вибраним індексом;

- операція поділу масиву: реорганізуємо масив таким чином, щоб всі елементи зі значенням меншим або рівним опорному елементу, виявилися ліворуч від нього, а всі елементи, що перевищують за значенням опорний - праворуч від нього. Звичайний алгоритм операції:

- два індекса - l і г, прирівнюються до мінімального і максимального індексу розділяється масиву, відповідно;

- обчислюється індекс опорного елемента m;

- індекс l послідовно збільшується до тих пір, поки l-й елемент не виявиться більше або дорівнює опорному;

- індекс г послідовно зменшується до тих пір, поки г-й елемент не виявиться менше або дорівнює опорному;

- якщо г = l - знайдена середина масиву - операція поділу закінчена, обидва індекси вказують на опорний елемент;

- якщо l <г - знайдену пару елементів потрібно обміняти місцями і продовжити операцію розділення з тих значень l і г, які були досягнуті. Слід врахувати, що якщо яка-небудь кордон (l або г) дійшла до опорного елемента, то при обміні значення m змінюється на г-й або l-й елемент відповідно, змінюється саме індекс опорного елемента і алгоритм продовжує своє виконання;

- бекурсивно упорядковуємо подмассіви, що лежать ліворуч і праворуч від опорного елемента;

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

Оскільки в кожній ітерації (на кожному наступному рівні рекурсії) довжина оброблюваного відрізка масиву зменшується, щонайменше, на одиницю, термінальна гілку рекурсії буде досягнута обов'язково і обробка гарантовано завершиться.



1.6 Паралельна реалізація швидкого сортування

Для паралельної реалізації методу швидкого сортування (розширення Брюса Вагара - т. зв. гіпербистре сортування) так само, як і у випадку методу Шелла, створюється комунікаційна топологія у вигляді N-мірного гіперкуба для кластера, що містить 2N процесорів. Для сортування n значень попередньо кожному вузлу розсилається блок з n / p елементів. Потім N раз виконується наступна послідовність дій:

- вибирається провідний елемент з розсилкою його значення всім процесорам гіперкуба;

- блок в кожному процесорі розбивається з урахуванням значення провідного елементу на дві частини;

- організовуються зв'язки між парами процесорів, двійкові коди номерів яких відрізняються тільки в N-ій позиції;

- виконується взаємний обмін частинами всередині кожної пари процесорів так, щоб у процесорів, що містять 0 в двійковому представленні свого номера, залишилося по дві частини з меншими значеннями елементів, а у процесорів з 1 у номері - дві частини з великими значеннями.

Щоразу після однократного виконання перерахованих дій гіперкуб порядку N виявляється розбитим на два гіперкуба порядку N - 1, таких, що у гіперкуба з нулем у старших розрядах двійкових номерів його процесорів всі значення упорядковуваних елементів менше всіх значень іншого гіперкуба, старший розряд двійкових номерів процесорів якого містить одиницю.

Щоб полегшити вдалий вибір провідних елементів, бажано після розсилки кожному вузлу гіперкуба блоку значень виконати їх попереднє сортування, а також забезпечити однорідний розподіл даних між процесорами. Обчислювальна складність алгоритму, що визначається часом сортування в процесорах, часом вибору провідних елементів і складністю поділу блоків, обчислюється за формулою:

T = (n / p) log (n / p) + log p + log (n / p) log

2. ПРАКТИЧНА ЧАСТИНА

2.1 Програма паралельного розрахунку визначеного інтеграла

(1/6*х-2,7)/(1,5*х3+3,9)

Інтервал інтегрування [1.0;2.2];

Шаг дискретизації 0.0025;

Використаємо метод прямокутників.

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

Види формули прямокутників:

Формула лівих прямокутників

В даному випадку береться значення функції на початку проміжку:

Похибка обчислення рівна:

Формула правих прямокутників

В даному випадку береться значення функції в кінці проміжку:



Як і впопередньому випадку похибка обчислень рівна:

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

#include "stdafx.h"

#include "math.h"

#include "mpi.h"

#include <stdlib.h>;

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

{

double Pi = 3.141592653589793238462643;

double IntervalWidth = 0.0025;

double a = 1.0;

printf("a= %.16f\n", a);

double b = 2.2;

printf("b %.16f\n", b);

int numbIntervals = (int)((b - a) / IntervalWidth);

double IntervalHeight = 0.0;

double x = 0.0;

int Interval = 0;

double summaLocal = 0.0;

double summaGlobal;

int ProcNumb;

int ProcRank;

char processor_name[MPI_MAX_PROCESSOR_NAME];

int namelen;

double t1, t2;

MPI_Init(&argc, &argv);

MPI_Comm_size(MPI_COMM_WORLD, &ProcNumb);

MPI_Comm_rank(MPI_COMM_WORLD, &ProcRank);

MPI_Get_processor_name(processor_name, &namelen);

printf("Process %d of %d running on %s\n", ProcRank, ProcNumb, processor_name); сортування масив паралельний інтеграл

if (ProcRank == 0)

{

printf("numbIntervals = %i\n", numbIntervals);

t1 = MPI_Wtime();

}

for (Interval = 1 + ProcRank; Interval <= numbIntervals; Interval += ProcNumb)

{

x = a + (IntervalWidth * ((double)Interval - 0.5));

IntervalHeight += (1/6*х-2.7)/(1.5*х3+3.9);

}

summaLocal = IntervalWidth * IntervalHeight;

printf("ProcessorName %s, summaLocal is approximately %.16f\n", processor_name, summaLocal);

MPI_Reduce(&summaLocal, &summaGlobal, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD);

if (ProcRank == 0)

{

t2 = MPI_Wtime();

printf("Integral is approximately %.16f\n", summaGlobal);

printf("Time is %f second \n", t2 - t1);

}

MPI_Finalize();

//return 0;

system("pause");

}

Результат: 0,0000000042923443

Таблиця 2.1 Результати обчислювальних експериментів по дослідженню паралельного алгоритму розрахунку визначеного інтегралу.

Паралельний алгоритм
Кількість процесорів	Час за який був розрахованій інтеграл
2	0,003257
3	0,005741
4	0,007261
5	0,012302
6	0,013076
7	0,022089
8	0,010710

N - кількість процесорів.

t - час виконання обчислень.

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

Рисунок 2.2 - Графік репрезентації інтегралу



2.2 Розробка паралельної програми множення квадратної матриці на вектор

Постановка завдання

Множення матриці A розміру a*b і вектору B розміру b наводить до здобуття матриці C розміру a*1, кожен елемент якої визначається відповідно до вираження:

Кожен елемент результуючої матриці C є скалярний твір відповідних рядки матриці A і елементу вектора B:

Цей алгоритм передбачає виконання m*n*l операцій множення і стільки ж операцій складання елементів вихідних матриць. При множенні квадратної матриці розміру n*n кількість виконаних операцій має порядок O(n3). Відомі послідовні алгоритми множення матриці на вектор, що володіють меншою обчислювальною складністю, але ці алгоритми вимагають великих зусиль для їх освоєння.

Послідовний алгоритм множення матриці на вектор представляється трьома вкладеними циклами.

Послідовний алгоритм множення квадратної матриці на вектор

double MatrixA[Size][Size]; double VectorB[Size]; double MatrixC[Size][Size]; int i,j,k;

for (i=0; i<Size; i++){ for (j=0; j<Size; j++){

MatrixC[i][j] = 0; for (k=0; k<Size; k++){

MatrixC[i][j]=MatrixC[i][j]+ MatrixA [i][k]*VectorB[k];

}

}

}

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

Рис. 2.4. На першій ітерації циклу по змінній і використовується перший рядок матриці A і перший елемент вектору B для того, щоб обчислити елементи першого рядка результуючої

Можливий підхід для організації паралельних обчислень полягає у використанні як базова підзадача процедури визначення одного елементу результуючої матриці С. Для проведення всіх необхідних обчислень кожна підзадача повинна містити по одному рядку матриці А і одному елементу вектора В. Загальна кількість отримуваних при такому підході підзадач виявляється рівним п2 (по числу елементів матриці С).

Розглянувши запропонований підхід, можна відзначити, що досягнутий рівень паралелізму є в більшості випадків надлишковим. Зазвичай при проведенні практичних розрахунків така кількість сформованих підзадач перевищує число наявних процесорів і робить неминучим етап укрупнення базових завдань. У цьому плані може виявитися корисною агрегація обчислень вже на кроці виділення базових підзадач. Можливе рішення може полягати в об'єднанні в рамках однієї підзадачі всіх обчислень, пов'язаних не з одним, а з декількома елементами результуючої матриці С. Для подальшого розгляду визначимо базове завдання як процедуру обчислення всіх елементів одного з рядків матриці С. Такой підхід призводить до зниження загальної кількості підзадач до величини п.

Для виконання всіх необхідних обчислень базовій підзадачі мають бути доступні один з рядків матриці А і всі елементи вектору В. Просте вирішення цієї проблеми - дублювання вектору В у всіх підзадачах - є, як правило, неприйнятним через великі витрати пам'яті для зберігання даних. Тому організація обчислень має бути побудована так, щоб в кожен теперішній момент часу підзадачі містили лише частину даних, необхідних для проведення розрахунків, а доступ до останньої частини даних забезпечувався б за допомогою передачі даних між процесорами.

Алгоритм є ітераційною процедурою, кількість ітерацій якої збігається з числом підзадач. На кожній ітерації алгоритму кожна підзадача містить по одному рядку матриці А і одному елементу вектора В. Прі виконанні ітерації проводиться скалярне множення рядків, що містяться в підзадачах, і стовпців, що наводить до здобуття відповідних елементів результуючої матриці С. По завершенні обчислень в кінці кожної ітерації елементи вектора В мають бути передані між підзадачами з тим, аби в кожній підзадачі виявилися нові елементи вектора В і могли бути обчислені нові елементи матриці C. При цьому дана передача елементів між підзадачами має бути організована так, щоб після завершення ітерацій алгоритму в кожній підзадачі послідовно виявилися всі стовпці матриці С.

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

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

#include <time.h>

#include <mpi.h>

int ProcNum; // Number of available processes

int ProcRank; // Rank of current process

// Function for random initialization of objects' elements

void RandomDataInitialization (double* pMatrix,double* pVector,int

Size) {

int i, j; // Loop variables

srand(unsigned(clock()));

for (i=0; i<Size; i++) {

pVector[i] = rand()/double(1000);

for (j=0; j<Size; j++)

pMatrix[i*Size+j] = rand()/double(1000);

}

}

// Process rows and vector multiplication

void ParallelResultCalculation(double* pProcRows, double* pVector,

double* pProcResult, int Size, int RowNum) {

int i, j;

for (i=0; i<RowNum; i++) {

pProcResult[i] = 0;

for (j=0; j<Size; j++) {

pProcResult[i] += pProcRows[i*Size+j]*pVector[j];

}

}

}

// Function for computational process termination

void ProcessTermination (double* pMatrix, double* pVector, double*

pResult,

double* pProcRows, double* pProcResult) {

if (ProcRank == 0)

delete [] pMatrix;

delete [] pVector;

delete [] pResult;

delete [] pProcRows;

delete [] pProcResult;

}

// Function for simple definition of matrix and vector elements

void DummyDataInitialization (double* pMatrix, double* pVector, int

Size) {

int i, j; // Loop variables

for (i=0; i<Size; i++) {

pVector[i] = 1;

for (j=0; j<Size; j++)

pMatrix[i*Size+j] = i;

}

}

// Function for memory allocation and definition of object's

elements

void ProcessInitialization(double* &pMatrix, double* &pVector,

double* &pResult, double* &pProcRows, double* &pProcResult,

int &Size, int &RowNum) { // Setting the size of initial matrix

and vector

// Setting the size of initial matrix and vector

if (ProcRank == 0) {

do {

printf("\nEnter size of the initial objects: ");

fflush(stdout);

scanf_s("%d", &Size);

printf("\nChosen objects size = %d\n", Size);

if (Size < ProcNum) {

printf("Size of the objects must be greater than

"

"number of processes! \n ");

}

if (Size <= 0)

printf("\nSize of objects must be greater than

0!\n");

}

while ((Size < ProcNum) || (Size%ProcNum != 0));

}

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

// Determine the number of matrix rows stored on each process

RowNum = Size/ProcNum;

// Memory allocation

pVector = new double [Size];

pResult = new double [Size];

pProcRows = new double [RowNum*Size];

pProcResult = new double [RowNum];

// Obtain the values of initial objects' elements

if (ProcRank == 0) {

pMatrix = new double [Size*Size];

DummyDataInitialization(pMatrix, pVector, Size);

// Random definition of objects' elements

//RandomDataInitialization(pMatrix, pVector, Size);

}

}

// Function for formatted matrix output

void PrintMatrix (double* pMatrix, int RowCount, int ColCount) {

int i, j; // Loop variables

for (i=0; i<RowCount; i++) {

for (j=0; j<ColCount; j++)

printf("%7.4f ", pMatrix[i*ColCount+j]);

printf("\n");

}

}

// Function for formatted vector output

void PrintVector (double* pVector, int Size) {

int i;

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

printf("%7.4f ", pVector[i]);

printf("\n");

}

// Function for distribution of the initial objects between the

processes

void DataDistribution(double* pMatrix, double* pProcRows, double*

pVector,

int Size, int RowNum) {

MPI_Status st;

MPI_Bcast(pVector, Size, MPI_DOUBLE, 0, MPI_COMM_WORLD);

MPI_Scatter(pMatrix, RowNum*Size, MPI_DOUBLE, pProcRows,

RowNum*Size,

MPI_DOUBLE, 0, MPI_COMM_WORLD);

}

// Fuction for testing the results of multiplication of matrix

stripe

// by a vector

void TestPartialResults(double* pProcResult, int RowNum) {

int i; // Loop variable

for (i=0; i<ProcNum; i++) {

if (ProcRank == i) {

printf("ProcRank = %d \n", ProcRank);

printf("Part of result vector: \n");

PrintVector(pProcResult, RowNum);

}

//MPI_Barrier(MPI_COMM_WORLD);

}

}

// Result vector replication

void ResultReplication(double* pProcResult, double* pResult, int

Size,

int RowNum) {

MPI_Gather(pProcResult, RowNum, MPI_DOUBLE, pResult, RowNum,

MPI_DOUBLE, 0, MPI_COMM_WORLD);

//MPI_Allgather(pProcResult, RowNum, MPI_DOUBLE, pResult,

RowNum,

//MPI_DOUBLE, MPI_COMM_WORLD);

}

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

double* pMatrix; // The first argument - initial matrix

double* pVector; // The second argument - initial vector

double* pResult; // Result vector for matrix-vector

multiplication

int Size; // Sizes of initial matrix and vector

time_t start, finish;

double duration;

double* pProcRows; // Stripe of the matrix on current process

double* pProcResult; // Block of result vector on current

process

int RowNum; // Number of rows in matrix stripe

MPI_Status st;

MPI_Init(&argc, &argv);

MPI_Comm_size(MPI_COMM_WORLD, &ProcNum);

MPI_Comm_rank(MPI_COMM_WORLD, &ProcRank);

if (ProcRank == 0) {

printf ("Parallel matrix-vector multiplication program\n");

//printf ("Number of available processes = %d \n",

ProcNum);

}

//printf ("Rank of current process = %d \n", ProcRank);

ProcessInitialization(pMatrix, pVector, pResult, pProcRows,

pProcResult, Size, RowNum);

// Distributing the initial objects between the processes

start = clock();

DataDistribution(pMatrix, pProcRows, pVector, Size, RowNum);

// Distribution test

//TestDistribution(pMatrix, pVector, pProcRows, Size, RowNum);

ParallelResultCalculation(pProcRows, pVector, pProcResult,

Size, RowNum);

TestPartialResults(pProcResult, RowNum);

// Result replication

ResultReplication(pProcResult, pResult, Size, RowNum);

finish = clock();

duration = (finish-start)/double(CLOCKS_PER_SEC);

30

// Printing the result vector

if (ProcRank == 0) {

printf ("\n Result Vector: \n");

PrintVector(pResult, Size);

printf("\n Time of execution: %f\n", duration);

}

// Computational process termination

ProcessTermination(pMatrix, pVector, pResult, pProcRows,

pProcResult);

MPI_Finalize();}

Результати обчислювальних експериментів

Експерименти виконувалися з використанням двох, чотири і восьми процесорів.

Табліця 2.2. Результати обчислювальних експериментів по дослідженню паралельного алгоритму матричного множення при стрічковій схемі розподілу даних

Рис. 2.5. Графік залежності швидкості множення матриці на вектор від кількості використуваних процесів і від розмірності матриці



ВИСНОВКИ

Як можна відмітити з приведених результатів обчислювальних експериментів, використання паралельних обчислень прискорює процес множення матриць. Із збільшенням розмірності матриці, за інших рівних умов, зменшується ефективність використання паралельних обчислень. Це відбувається тому, що в цьому випадку багато часу витрачається на пересилку даних між процесами.



ПЕРЕЛІК ПОСИЛАНЬ

1. Воеводин В. В., Воеводин Вл.В. "Паралельні обчислення" - СПб.: БХВ-Петербург, 2002.-608 с.

2. А.С.Антонов "Паралельне програмування з використанням технології MPI" (навчальний посібник). - М. :НИВЦ МГУ, 2004.-72 с.

3. Введення в практику розробки паралельних програм в стандарті MPI :Учебно-методическое посібник з виконання лабораторних робіт/В. М. Баканів, Д.В.Осипов. - М.:МГАПИ, 2005.-63 с.

4. Тішин П.М. Паралельні розподіленні обчислення.: Посібник до самостійної роботи та виконання контрольних робіт. Одеська державна академія холоду, 2008. - 42с.

5. Тішин П.М. Паралельні розподіленні обчислення: посібник для виконання модульного контролю. Одеська державна академія холоду, 2008. - 19с.

6. Тішин П.М. Паралельні та розподілені обчислення: навчальний посібник. Одеська державна академія холоду, 2008. - 80 с.

Размещено на Allbest.ru

...