Розробка підходів до розпаралелювання алгоритмів

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

ЗМІСТ

Вступ

1. Топологічний аналіз початкового графу

2. Розробка послідовного рішення поставленої задачі

3. Розробка підходів до розпаралелювання

4. Розробка паралельної програми

5. Аналіз ефективності паралельних рішень

Висновок



ВСТУП

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

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



1. ТОПОЛОГІЧНИЙ АНАЛІЗ ПОЧАТКОВОГО ГРАФУ

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

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

Задано граф вентиляційної мережі (рисунок 1.1), яка являє собою МДО (параметри наведені у таблиці 1.1).

Рисунок 1.1 - Граф МДО

Таблиця 1.1 - Параметри МДО

	Q1	Q2	Q3	Q4	Q5	Q6	Q7	Q8	Q9
R, Н·с2/м8	1.35	1.53	2.34	3.17	1.35	2.32	2.35	1.25	1.51
K, кг/м4	140	131	61	94	94	63	87	101	114
H, Н/м2	4000	0	0	0	0	0	0	0	0

Для вентиляційних мереж потік повітря в окремому елементі можна спрощено (зневажаючи стиском потоку) описати наступним диференційним рівнянням:

, (1.1)

де K - коефіцієнт, що характеризує інерційність повітряного потоку; R - аеродинамічний опір; Q - потік (витрата) повітря; H - депресія (різниця тисків у початковому і кінцевому вузлах гілки).

Також сума потоків повітря у вузлі описується:

, (1.2)

де k - кількість потоків, які проходять через вузол.

Для аналітичного рішення даного МДО (рисунок 1.1) необхідно скласти n-1 рівнянь (де n - кількість вузлів, яка дорівнює 4, тобто n-1 = 3) для вузлів за формулою 1.2 та m-n+1 рівнянь (де m - кість ланцюгів, яка дорівнює 9, тобто m-n+1 = 6) для ланцюгів за формулою 1.1:

(1.3)

До рівнянь підставляються відомі значення, частини дорівнюються нулю, тому що перехідний процес вже завершений. Система рівнянь приймає наступний вигляд:

(1.4)

Система рівнянь розрішається у середовищі програми MatLAB:

(1.5)

Для топологічного аналізу даного МДО (рисунок 1.1) спочатку необхідно визначити дерево та антидерево графа. Дерево - це незамкнутий контур, який з'єднує усі вузли графа. Гілки антидерева - це ті гілки, які не увійшли до дерева. Граф, розбитий на дерево та антидерево, зображений на рисунку 1.2.

Рисунок 1.2 - Граф у вигляді дерева та антидерева

Необхідною є побудова матриць інциденцій та контурів.

У матриці інциденцій кількість рядків дорівнює n-1 = 3. Якщо за напрямком гілка входить до вузла, то у відповідну комірку записується «1», якщо виходить - «-1». Для інших гілок записується «0». Матриця інциденцій наведена у таблиці 1.2.



Таблиця 1.2 - Матриця інциденцій

	X1	X2	X3	Y1	Y2	Y3	Y4	Y5	Y6
В1	1	-1	-1	-1	0	0	0	0	0
В2	0	1	0	0	-1	-1	-1	0	0
В3	0	0	1	0	0	-1	0	-1	-1

Кількість контурів m-n+1 = 6. Контури вибрані таким чином, щоб вони включали максимальну кількість гілок дерева і мінімальну кількість гілок антидерева (одну гілку). Матриця контурів наведена у таблиці 1.3.

Таблиця 1.3 - Матриця контурів

	X1	X2	X3	Y1	Y2	Y3	Y4	Y5	Y6
V1	1	0	0	1	0	0	0	0	0
V2	1	1	0	0	1	0	0	0	0
V3	0	1	-1	0	0	1	0	0	0
V4	1	1	0	0	0	0	1	0	0
V5	1	0	1	0	0	0	0	1	0
V6	1	0	1	0	0	0	0	0	1

Далі групуються параметри за деревом-антидеревом: R наведено у таблиці 1.4, K - у таблиці 1.5, H - у таблиці 1.6.

Таблиця 1.4 - Параметри R

R	=	Rx	0	=	1.35	0	0	0	0	0	0	0	0
					0	2.34	0	0	0	0	0	0	0
					0	0	3.17	0	0	0	0	0	0
		0	Ry		0	0	0	1.53	0	0	0	0	0
					0	0	0	0	1.35	0	0	0	0
					0	0	0	0	0	2.32	0	0	0
					0	0	0	0	0	0	2.35	0	0
					0	0	0	0	0	0	0	1.25	0
					0	0	0	0	0	0	0	0	1.51



Таблиця 1.5 - Параметри K

K	=	Kx	0	=	140	0	0	0	0	0	0	0	0
					0	61	0	0	0	0	0	0	0
					0	0	94	0	0	0	0	0	0
		0	Ky		0	0	0	131	0	0	0	0	0
					0	0	0	0	94	0	0	0	0
					0	0	0	0	0	63	0	0	0
					0	0	0	0	0	0	87	0	0
					0	0	0	0	0	0	0	101	0
					0	0	0	0	0	0	0	0	114

Таблиця 1.6 - Параметри H

H	=	Hx	0	=	4000
					0
					0
		0	Hy		0
					0
					0
					0
					0
					0

Для чисельного рішення необхідно привести рівняння до виду, який є зручним для чисельного рішення.

Увівши до формул 1.1 та 1.2 вектори потоків Q=(Q1,Q2,...,Qm)T, діагональні матриці параметрів R, K, вектори нелінійної залежності Z=(Q12,Q22,...,Qm2)T, тисків турбомашин H=(H1,H2,...,Hm)T, можна записати матрично-векторні рівняння мережних об'єктів у вигляді:

(1.6)

Матриці поділяються: Q=(X Y)T; A=(Ax Ay); S=(Sx Sy); Z=(X2 Y2)T; H=(Hx Hy)T.

Тоді перше рівняння змінюється таким чином: А*Q=0 => Ax*X+Ay*Y=0 => Ax*X=-Ay*Y => Ax-1*Ax*X=-Ax-1*Ay*Y => X=-W*Y, де W=Ax-1*Ay.

Друге: S*K*dQ/dt+S*R*Z=S*H => Sx*Kx*dX/dt+Sy*Ky*dY/dt=S*H- S*R*Z => (Sy*Ky-Sx*Kx*W)*dY/dt=S*H-S*R*Z => dY/dt=(Sy*Ky-Sx*Kx*W)-1*S*(H - R*Z).

Система рівнянь для розрахунку приймає вигляд:

(1.7)

Згідно з завданням, систему необхідно вирішувати методом Ейлера, в якому спочатку встановлюються початкові дані, далі на кожній ітерації вираховуються прирости ДY, ДХ та нові Y, X. Ітерації завершуються, якщо один із приростів на ітерації менше ніж встановлений рівень можливої похибки д.

Дискретна модель для вирішення системи методом Ейлера: Y0=0; X0=-W*Y0=0; dY/dt=(Yi+1-Yi)/(ti+1-ti)=(Yi+1-Yi)/h=(Sy*Ky-Sx*Kx*W)-1*S*(H-R*Z); Yi+1=Yi+h*(Sy*Ky-Sx*Kx*W)-1*S*(H-R*Z); Xi+1=-W*Yi+1. Остаточно:

(1.8)

2. РОЗРОБКА ПОСЛІДОВНОГО РІШЕННЯ ПОСТАВЛЕНОЇ ЗАДАЧІ

Послідовна програма повинна реалізовувати алгоритм Ейлера згідно розробленої моделі для заданої вентиляційної мережі. Аналізуючи систему та рівняння, видно, що програма повинна виконувати матричні операції: додавання, віднімання, множення, обернення.

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

Розраховуються матриці W=Ax-1*Ay і W1=(Sy*Ky-Sx*Kx*W)-1, які зберігаються незмінними під час роботи програми і не потребують перерахунку на кожній ітерації. Далі починається цикл алгоритму Ейлера, який завершиться коли один з приростів буде менше ніж встановлений рівень можливої похибки д, і тоді програма відобразить матриці Х і Y на останньому кроці обчислень.

Блок-схема алгоритму послідовної програми наведена на рисунку 2.1.

Рисунок 2.1 - Блок-схема алгоритму послідовної програми



Програма була написана під Borland C++ Compiler 5.5. Вона зроблена консольною - це спрощує відображення інформації.

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

Матриці зроблені динамічними змінними, тому що спочатку невідомий розмір вхідних матриць. Лише після зчитування кількості стовпчиків і рядків у програмі виділяється потрібна пам'ять. У кінці роботи програми динамічні змінні знищуються.

Час роботи програми було знайдено за допомогою функції GetSystemTime, яка визначає час з точністю до мс. Програмі необхідно 15 мс для рішення поставленого завдання.

Вихідний текст послідовної програми наведено у додатку А.

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

Рисунок 2.2 - Результати роботи послідовної програми



3. РОЗРОБКА ПІДХОДІВ ДО РОЗПАРАЛЕЛЮВАННЯ

Для зменшення часу виконання обчислення треба використовувати паралельні алгоритми. Для МДО, який представлений у виді графу, можна виділити три рівня паралельності (рисунок 3.1).

Рисунок 3.1 - Варіанти розпаралелювання

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

MIMD-комп'ютер має N процесорів, що незалежно виконують N потоків команд і оброблюють N потоків даних. Кожен процесор функціонує під керуванням власного потоку команд, тобто MIMD-комп'ютер може паралельно виконувати абсолютно різні програми.

MIMD-архітектури класифікуються залежно від фізичної організації пам'яті, тобто чи має процесор свою власну локальну пам'ять і звертається до інших блоків пам'яті, використовуючи комутуючу мережу, або комутуюча мережа під'єднує всі процесори до загальнодоступної пам'яті. Виходячи з організації пам'яті, розрізняють наступні типи паралельної архітектури: комп'ютери з розподіленою пам'яттю (distributed memory), комп'ютери із загальною (що розділяється) пам'яттю (true shared memory).

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

Рисунок 3.2 - Комп'ютери з розподіленою пам'яттю

В комп'ютерах із загальною пам'яттю (рисунок 3.3) всі процесори спільно звертаються до загальної пам'яті, зазвичай, через шину або ієрархію шин. У ідеалізованій PRAM-моделі (Parallel Random Access Machine - паралельна машина з довільним доступом), часто використовуваній в теоретичних дослідженнях паралельних алгоритмів, будь-який процесор може звертатися до будь-якого елементу пам'яті за один і той же час. На практиці масштабованість цієї архітектури зазвичай приводить до деякої форми ієрархії пам'яті. Частота звернень до загальної пам'яті може бути зменшена за рахунок збереження копій часто використовуваних даних в кеш-пам'яті, пов'язаній з кожним процесором. Доступ до кеш-пам'яті набагато швидкіший, ніж безпосередній доступ до загальної пам'яті.

Рисунок 3.3 - Комп'ютери із загальною пам'яттю

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

Для обчислення задачі використовуються саме MIMD-архітектури з розподіленою пам'яттю. Обмін даними залежить від параметрів комунікаційних технологій. Для аналізу розглядаються наступні параметри: час затримки (latency) - характеризує мінімальний час, який є необхідним для передачі пакету даних мінімальної довжини іншому вузлу; смуга пропускання (bandwidth) - встановлена максимальна швидкість передачі даних. Комунікаційні технології та їх параметри представлені в таблиці 3.1.



Таблиця 3.1 - Параметри комунікаційних технологій

Технологія	Час затримки	Смуга пропускання
Gigabit Ethernet	4 мксек	125 Mb/sec
Myrinet	10 мксек	400 Mb/sec
QsNet	1.5 мксек	1064 Mb/sec
Memory Channel	3 мксек	100 Mb/sec
ServerNet II	29 мксек	180 Mb/sec
InfiniBand	1.2 мксек	40 Gb/sec

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

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

Нерівномірність завантаження процесорів:

W=Дt/Tpmin, (3.1)

де Дt=Tpmax-Tpmin - різниця між максимальним та мінімальним часом рішення; Tp=Q*Nрівн - час рішення; Nрівн - кількість рівнянь.

Співвідношення між об'ємами обчислювальних і обмінних операцій:

K=Tобм/Tр, (3.2)

де Tp=Q*Nрівн - час рішення; Nрівн - кількість рівнянь; Tобм=2*Тзатр+(Nвх+Nвих)*8/Fмереж - час обміну; Тзатр - фіксований час затримки передачі даних; Nвх, Nвих - кількість вхідних та вихідних змінних; Fмереж - смуга пропускання мережі.

Прискорення моделювання:

S=Tр(1)/Tр(N), (3.3)

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

Ефективність використання обчислювальних ресурсів:

E=S/Smax, (3.4)

де Smax=p/б(p-1)+1; p - кількість процесорів; б=Tpmax/(Tpmax+Tpmin) - частина паралельного алгоритму, що виконується послідовно.

Розрахунок параметрів виконується відповідно до кожного рівня.

Спочатку розраховуються параметри для підграфів. Вхідний граф розбивається на два підграфи: дерево та антидерево. Розрахунки:

W=Дt/Tpmin=(Tpmax-Tpmin)/Tpmin=(6Q-3Q)/3Q=1;

Tобм=2*Тзатр+(6+3)*8/Fмереж=2*Тзатр+72/Fмереж;

Kдер=Tобм/Tр=(2*Тзатр+72/Fмереж)/3Q;

Kадер=Tобм/Tр=(2*Тзатр+72/Fмереж)/6Q; Kдер>Kадер;

S=Tр(1)/Tр(N)=9Q/6Q=1.5;

E=S/Smax=S/(p/(б(p-1)+1))=S/(p/((Tpmax/(Tpmax+Tpmin))(p-1)+1))=1.5/(2/((6Q/(6Q+3Q))(2-1)+1))=1.5/1.2=1.25.

Далі виконується розрахунок параметрів для розпаралелювання на рівні гілок. Вхідний граф складається з 9 гілок. Розрахунки:

W=Дt/Tpmin=(Tpmax-Tpmin)/Tpmin=(Q-Q)/Q=0;

Tобм=2*Тзатр+(9+1)*8/Fмереж=2*Тзатр+80/Fмереж;

Kгіл=Tобм/Tр=(2*Тзатр+80/Fмереж)/Q;

Kгіл>Kдер;

S=Tр(1)/Tр(N)=9Q/Q=9;

E=S/Smax=S/(p/(б(p-1)+1))=S/(p/((Tpmax/(Tpmax+Tpmin))(p-1)+1))=9/(11/((Q/(Q+Q))(11-1)+1))=11/6=4.9.

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

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

4. РОЗРОБКА ПАРАЛЕЛЬНОЇ ПРОГРАМИ

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

Перший процес зчитує з файлу розміри матриць та самі матриці, після чого відсилає кількості рядків та стовпців матриць X, Y, W. Увесь цей час другий процес очікує ці дані. Далі перший процес обчислює матриці W, W1 і відсилає другому процесу матрицю W. Перший процес обчислює матрицю Y, пересилає її другому процесу. Другий процес завдяки отриманим матриця W і Y обчислює матрицю X та відсилає її першому процесу. Перший процес знаходить прирости і якщо вони не перевищують задану точність, то відсилає другому прапор завершення роботи, виходить з циклу, відображає результат і завершує свою роботу. Якщо ж прирости занадто великі, перший процес відсилає другому прапор продовження роботи, записує значення поточного кроку до файлу.

Блок-схема алгоритму паралельної програми наведена на рисунках 4.1, 4.2.

Рисунок 4.1 - Блок-схема алгоритму роботи першого процесу паралельної програми



Рисунок 4.2 - Блок-схема алгоритму роботи другого процесу паралельної програми

Програма була написана під Borland C++ Compiler 5.5.

Час роботи програми було знайдено за допомогою функції GetSystemTime, яка визначає час з точністю до мс. Програмі необхідно 23 мс для рішення поставленого завдання.

Вихідний текст паралельної програми наведено у додатку Б.

Результати роботи паралельної програми (рисунок 4.3) аналогічні результатам роботи послідовної програми (рисунок 2.2).



Рисунок 4.3 - Результати роботи паралельної програми

Паралелізм у програмі був досягнений завдяки бібліотеці паралельного програмування MPI.

MPI-програма являє собою набір незалежних процесів, кожний з яких виконує свою власну програму. Процеси MPI-програми взаємодіють один з одним за допомогою виклику комунікаційних процедур. Як правило, кожний процес виконується у своєму власному адресному просторі, однак допускається і режим поділу пам'яті. MPI не специфікує модель виконання процесу - це може бути як послідовний процес, так і багатопотоковий. MPI не надає ніяких засобів для розподілу процесів по обчислювальних вузлах і для запуску їх на виконання. Ці функції покладаються або на операційну систему, або на програміста. Зокрема, на кластерах - спеціальний командний файл mpirun, що припускає, що здійсненні модулі вже якимсь чином розподілені по комп'ютерам кластера. MPI не накладає жодних обмежень на те, як процеси будуть розподілені по процесорах, зокрема, можливий запуск MPI-програми з декількома процесами на звичайній однопроцесорній системі.

Для ідентифікації наборів процесів вводиться поняття групи, що поєднує всі чи якусь частину процесів. Кожна група утворює область зв'язку, з яким зв'язується спеціальний об'єкт - комунікатор області зв'язку. Процеси усередині групи нумеруються цілим числом у діапазоні 0..groupsize-1. Усі комунікаційні операції з деяким комунікатором будуть виконуватися тільки усередині області зв'язку, описуваної цим комунікатором. При ініціалізації MPI створюється визначена область зв'язку, що містить усі процеси MPI-програми, з яким зв'язується визначений комунікатор MPI_COMM_WORLD. У більшості випадків на кожному процесорі запускається один окремий процес, і тоді терміни «процес» і «процесор» стають синонімами, а величина groupsize стає рівної NPROCS - числу процесорів, виділених задачі.

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

Набір функцій бібліотеки MPI далеко виходить за рамки набору функцій, мінімально необхідного для підтримки механізму передачі повідомлень. Користувачу належить право самому вирішувати, які засоби з наданого арсеналу використовувати, а які ні. У принципі, будь-яка паралельна програма може бути написана з використанням всього 6 MPI-функцій, а досить повне і зручне середовище програмування складає набір з 24 функцій.

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

Під час написання програми використовувались функції керування середовищем MPI та з'єднань типу «крапка-крапка».

Синтаксис функції ініціалізації MPI_Init: int MPI_Init(int *argc, char ***argv). У програмах на C кожному процесу при ініціалізації передаються аргументи функції main, отримані з командного рядка.

Функція завершення MPI-програм MPI_Finalize закриває всі MPI-процеси і ліквідує всі області зв'язку: int MPI_Finalize(void).

Функція визначення числа процесів в області зв'язку MPI_Comm_size: int MPI_Comm_size(MPI_Comm comm, int *size). IN - comm - комунікатор; OUT - size - число процесів в області зв'язку комунікатора comm. Функція повертає кількість процесів в області зв'язку комунікатора comm. До створення явно груп і зв'язаних з ними комунікаторів єдино можливими значеннями параметра COMM є MPI_COMM_WORLD і MPI_COMM_SELF, що створюються автоматично при ініціалізації MPI. Підпрограма є локальної.

Функція визначення номера процесу MPI_Comm_rank: int MPI_Comm_rank(MPI_Comm comm, int *rank). IN - comm - комунікатор; OUT - rank - номер процесу, що визвав функцію. Функція повертає номер процесу, що викликав цю функцію. Номера процесів лежать у діапазоні 0..size-1 (значення size може бути визначене за допомогою попередньої функції). Функція є локальної.

Функція передачі повідомлення MPI_Send: int MPI_Send(void* buf, int count, MPI_Datatype datatype, int dest, int tag, MPI_Comm comm). IN - buf - адреса початку розташування даних, що пересилаються; IN - count - число елементів, що пересилаються; IN - datatype - тип елементів, що посилаються; IN - dest - номер процесу-одержувача в групі, зв'язаної з комунікатором comm; IN - tag - ідентифікатор повідомлення; IN - comm - комунікатор області звязку. Функція виконує посилку count елементів типу datatype повідомлення з ідентифікатором tag процесу dest в області зв'язку комунікатора comm. Перемінна buf - це, як правило, масив чи скалярна перемінна. В останньому випадку значення count=1.

Функція прийому повідомлення MPI_Recv: int MPI_Recv(void* buf, int count, MPI_Datatype datatype, int source, int tag, MPI_Comm comm, MPI_Status *status). OUT - buf - адреса початку розташування прийнятого повідомлення; IN - count - максимальне число прийнятих елементів; IN - datatype - тип елементів прийнятого повідомлення; IN - source - номер процесу-відправника; IN - tag - ідентифікатор повідомлення; IN - comm - комунікатор області зв'язку; OUT - status - атрибути прийнятого повідомлення. Функція виконує прийом count елементів типу datatype повідомлення з ідентифікатором tag від процесу source в області зв'язку комунікатора comm.

5. АНАЛІЗ ЕФЕКТИВНОСТІ ПАРАЛЕЛЬНИХ РІШЕНЬ

На кожній ітерації роботи програм потоки Q у гілках поступово від початкових умов доходять до сталого режиму. Графіки залежності Q від номеру ітерації, або фізично, залежності Q від часу, що пройшов з початку увімкнення вентилятора, можна побудувати по результатам роботи (таблиця 5.1) послідовної програми (рисунок 5.1).

Таблиця 5.1 - Результати роботи послідовної програми

Крок	Q1	Q2	Q3	Q4	Q5	Q6	Q7	Q8	Q9
0	0	0	0	0	0	0	0	0	0
1	22,1681	6,8433	8,878	6,4468	3,7757	1,0229	4,0794	2,548	2,8759
2	39,7972	12,9262	15,2889	11,5821	7,688	1,603	7,9978	4,6904	7,2888
3	47,461	16,997	16,6866	13,7774	8,7124	1,4982	8,476	8,779	8,5002
4	49,312	18,9658	16,1996	14,1466	8,6888	1,6469	7,8638	8,8937	8,606
5	49,7492	19,7726	15,8832	14,0934	8,4914	1,0965	7,2953	8,6672	8,3296
6	49,8703	20,1058	15,7603	14,0042	8,3129	1,5445	6,9028	8,4222	8,0374
7	49,9027	20,2544	15,7139	13,9344	8,1785	1,8892	6,6462	8,2329	7,8122
8	49,908	20,3286	15,6943	13,8851	8,0849	1,1257	6,4836	8,1028	7,6566
9	49,9057	20,3702	15,6843	13,8513	8,0232	1,2774	6,3836	8,0188	7,5551
10	49,9024	20,3955	15,6784	13,8286	7,984	1,3705	6,3238	7,9669	7,4912
11	49,8997	20,4114	15,6745	13,8138	7,9598	1,4258	6,2889	7,936	7,452
12	49,898	20,4216	15,672	13,8043	7,9451	1,4579	6,2691	7,9182	7,4282
13	49,8968	20,428	15,6704	13,7984	7,9362	1,4761	6,258	7,9083	7,414
14	49,8962	20,432	15,6693	13,7948	7,931	1,4863	6,2521	7,9031	7,4055
15	49,8958	20,4345	15,6686	13,7927	7,9278	1,4918	6,249	7,9005	7,4004
16	49,8957	20,436	15,6682	13,7914	7,9259	1,4959	6,2475	7,9006	7,3992
17	49,8955	20,4368	15,668	13,7907	7,9241	1,4975	6,2468	7,9018	7,3882
18	49,8954	20,4374	15,6678	13,7903	7,9235	1,4984	6,2465	7,9026	7,3885
19	49,8954	20,438	15,6676	13,7898	7,9224	1,4985	6,2467	7,9028	7,3886

Рисунок 5.1 - Графіки Q

Графіки Q результатів роботи паралельної програми повністю відповідають результатам послідовної програми, тому що алгоритми цих програм відрізняються лише розпаралелюванням, а не загальним методом рішення - методом Ейлера.

При візуалізації результатів програм також виводиться час роботи, який потрібен для виконання програми. Час обчислюється за допомогою функції GetSystemTime з бібліотеки windows.h. Згідно з результатами, послідовна програма виконала обчислення системи за 15 мс. Паралельна програма виконала розрахунок за 23 мс. За часом виконання паралельна програма виявилася менш оптимальною. Цей результат пояснюється тим, що вона, хоч і тестувалась в середовищі MPICH, але фізично для тестування використовувалася однопроцесорна машина. Отже, реального розпаралелювання не відбувалося, а виконувалася лише емуляція паралельної роботи. Тому й потребувалося більше процесорного часу для виконання. Важливо й те, що деякий час процеси нічого не роблять, тому що чекають дані від іншого процесу. Також цей результат пояснюється тим, що для тестування використовувалася дуже проста задача. Реальні мережні динамічні об'єкти мають набагато більші за обсягом графи. Задана ж задача вирішується дуже швидко, тому переваги розпаралелювання дуже важко оцінити, використовуючи її для тестування.



ВИСНОВОК

У курсовій роботі був розглянутий МДО, його формальний опис.

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

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

1. Размещено на www.allbest.ru