Топологічний аналіз початкового графу. Розробка підходів до розпаралелювання і послідовного рішення задачі – розрахунку потоків повітря у кожній гілці мережевого динамічного об’єкту – вентиляційної мережі. Аналіз ефективності паралельних рішень.
Ціллю курсової роботи є розробка підходів до розпаралелювання алгоритмів вирішення задач різної складності, закріплення та подальше формування практичних навичок паралельного програмування для MIMD-систем, освоєння методик відлагодження паралельних програм за допомогою емуляторів.Мережеві обєкти характеризуються топологією звязків між гілками та вузлами, розташуванням активних елементів в мережі та фізичними процесами динаміки потоків в гілках та вузлах. Основна мета топологічного опису - дати чітке однозначне уявлення про структуру динамічної системи, характери складових елементів і взаємозвязків між ними, автоматизувати формування математичного опису динамічної системи у вигляді систем рівнянь як композицію опису окремих елементів топології. Для вентиляційних мереж потік повітря в окремому елементі можна спрощено (зневажаючи стиском потоку) описати наступним диференційним рівнянням: IMG_99862a88-987b-4db2-b114-80f6af65f913 , (1.1) де K - коефіцієнт, що характеризує інерційність повітряного потоку; R - аеродинамічний опір; Q - потік (витрата) повітря; H - депресія (різниця тисків у початковому і кінцевому вузлах гілки). Також сума потоків повітря у вузлі описується: IMG_085ec368-a041-4ec2-bde3-f6aafc23647d , (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: IMG_ae48a68e-a41c-4552-b07c-b28d77b83435 (1.3)Послідовна програма повинна реалізовувати алгоритм Ейлера згідно розробленої моделі для заданої вентиляційної мережі. Аналізуючи систему та рівняння, видно, що програма повинна виконувати матричні операції: додавання, віднімання, множення, обернення. Розраховуються матриці W=Ax-1*Ay і W1=(Sy*Ky-Sx*Kx*W)-1, які зберігаються незмінними під час роботи програми і не потребують перерахунку на кожній ітерації. Далі починається цикл алгоритму Ейлера, який завершиться коли один з приростів буде менше ніж встановлений рівень можливої похибки ?, і тоді програма відобразить матриці Х і Y на останньому кроці обчислень. У вигляді функцій зроблено частини коду, які виконують арифметичні операції над матрицями (додавання, віднімання, множення, обернення), алгоритми яких реалізовано у функціях matrix_add, matrix_multiply, matrix_reverse.MIMD-архітектури класифікуються залежно від фізичної організації памяті, тобто чи має процесор свою власну локальну память і звертається до інших блоків памяті, використовуючи комутуючу мережу, або комутуюча мережа підєднує всі процесори до загальнодоступної памяті. Виходячи з організації памяті, розрізняють наступні типи паралельної архітектури: компютери з розподіленою памяттю (distributed memory), компютери із загальною (що розділяється) памяттю (true shared memory). В компютерах з розподіленою памяттю (рисунок 3.2) процесор може звертатися до локальної памяті, може посилати і отримувати повідомлення, що передаються по мережі, що сполучає процесори. Наприклад, в архітектурі, де пари з процесора і модуля памяті (процесорний елемент) сполучені мережею з топологією решітка, кожен процесор має одне і те ж число підключень до мережі незалежно від числа процесорів компютера. З іншого боку, в архітектурі, що має мережу з топологією гіперкуб, число зєднань процесора з мережею є логарифмічною функцією від числа процесорів, а пропускна спроможність мережі росте швидше по відношенню до числа процесорів.Використовуючи результати попередньої глави, для програмування обирається розпаралелювання МДО по підграфам, тому у програмі використовуються два процеси. Далі перший процес обчислює матриці W, W1 і відсилає другому процесу матрицю W. Перший процес обчислює матрицю Y, пересилає її другому процесу. Другий процес завдяки отриманим матриця W і Y обчислює матрицю X та відсилає її першому процесу. Це досить обємна і складна бібліотека, що складається приблизно з 130 функцій, у число яких входять: функції ініціалізації і закриття MPI-процесів; функції, що реалізують комунікаційні операції типу крапка-крапка; функції, що реалізують колективні операції; функції для роботи з групами процесів і комунікаторами; функції для роботи із структурами даних; функції формування топології процесів.На кожній ітерації роботи програм потоки Q у гілках поступово від початкових умов доходять до сталого режиму. Графіки залежності Q від номеру ітерації, або фізично, залежності Q від часу, що пройшов з початку увімкнення вентилятора, можна побудувати по результатам роботи (таблиця 5.1) послідовної програми (рисунок 5.1). Графіки Q результатів роботи паралельної програми повністю відповідають результатам послідовної програми, тому що алгоритми цих програм відрізняються лише розпаралелюванням, а не загальним методом рішення - методом Ейлера. При візуалізації результатів програм також виводиться час роботи, який потрібен для виконання програми. Згідно з резуль
План
ЗМІСТ
Вступ
1. Топологічний аналіз початкового графу
2. Розробка послідовного рішення поставленої задачі
3. Розробка підходів до розпаралелювання
4. Розробка паралельної програми
5. Аналіз ефективності паралельних рішень
Висновок
Вы можете ЗАГРУЗИТЬ и ПОВЫСИТЬ уникальность своей работы
