Топологічний аналіз початкового графу. Розробка підходів до розпаралелювання і послідовного рішення задачі – розрахунку потоків повітря у кожній гілці мережевого динамічного об’єкту – вентиляційної мережі. Аналіз ефективності паралельних рішень.
Аннотация к работе
Ціллю курсової роботи є розробка підходів до розпаралелювання алгоритмів вирішення задач різної складності, закріплення та подальше формування практичних навичок паралельного програмування для 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. Розробка послідовного рішення поставленої задачі