ДонНТУ, ФОТІ, ПМИ
на тему: «Дослідження методів організації даних в задачах розбиття графів великих розмірностей»
Виконала Краснокутська Марія
Паралельні обчислення дозволяють значно підвищити ефективність і швидкість обробки інформації при вирішенні сучасних завдань. Такі завдання виникають в електромеханіки, при оптимізації складних систем, при прогнозуванні погоди, моделюванні різноманітних технічних і природних процесів.
Одна з основних проблем, яка виникає в кожному паралельному обчисленні, це розподіл обробки даних між процесорами. Рішенням може бути використання математичної моделі, в основі якої лежить граф потоків даних (ГПД). Програма представляється набором обчислювальних вузлів-подзадач, які мають фіксовану кількість інформаційних входів і виходів. Кожна подзадача виконується на окремому процесорі. Вузли-підзадачі - вершини графа потоків даних, а інформаційні потоки між ними - ребра графа. Оптимальний розподіл обробки даних між процесорами мінімізує час виконання всіх обчислень. Завдання розподілу обробки даних на процесори зводиться до задачі розбиття графа. Необхідно розбити граф потоків даних так, щоб кількість зв'язків між подграфа було мінімальним. Практичний досвід показав, що якість розподілу завдань між процесорами сильно впливає на продуктивність, що зумовило значний інтерес до алгоритмів розбиття графів [1].
На жаль, розбиття графа - NP-складна задача, і тому всі відомі алгоритми розбиття є наближеними і дають наближений до оптимального результат. Однак, не дивлячись на це обмеження, було розроблено багато алгоритмів розбиття графів, що дають високоякісне розбиття за малий час [2].
При програмної реалізації будь-якого з цих алгоритмів постає завдання вибору типу даних для представлення інформації про графа. Існують різні способи внутрішнього представлення графів в оперативній пам'яті ЕОМ, в тому числі у вигляді списків (масивів) вершин і ребер, списків (масивів) суміжності, матриць суміжності, а також у вигляді комбінацій цих структур зберігання. Вибір внутрішнього уявлення робить вирішальний вплив на ефективність виконання різних операцій над графами [3].
Метою даної роботи є дослідження методів організації даних в задачах розбиття графів великих розмірностей.
Постановка задачі про розбивку ГРАФА
Вихідним об'єктом для задач розбиття служить неорієнтовані граф. Простором рішень служить безліч всіляких розбиття графа на непересічні підграфи. На розбиття графа можуть накладатися обмеження D. Для різних завдань, природно, можливі різні обмеження.
Завдання декомпозиції мають наступний набір основних критеріїв:
• число зовнішніх з'єднань між подграфа;
• число подграфов.
Перший критерій визначається функціоналом зовнішніх зв'язків. Сенс другого критерію очевидна: він просто дорівнює числу подграфов розбиття. Постановки задач можуть варіюватися в залежності від властивостей графа, які задаються модельований об'єктом.
Нехай заданий неорієнтовний зважений граф G (V, E) порядку n, де V = 1, ..., vn> - безліч вершин; - безліч ребер.
Потрібно визначити розбиття множини вершин V графа G (V, E) на k - підмножин (V1, ..., Vk) таким чином, щоб для частин графа G1 (V1, E1), ..., Gk (Vk, Ek) виконувалися наступні вимоги:
Якщо U1. U2 ... - нормалізовані власні вектори L з відповідними власними значеннями # 955; 1 <=λ2 <= λ3 …. то матрица L имеет следующие свойства:
(I) L симетрична.
(II) Ui попарно ортогональні.
(III) U1 = n-0.51, # 955; 1 = 0
(IV) Якщо граф замкнутий, то тільки # 955; 1 приймає нульове значення.
Потім висловимо Х в термінах власних векторів L: x = # 931; # 945; i Ui. де # 945; i - речові константи, такі, що # 931; (# 945; i) 2 = n. Властивість (II) гарантує, що це завжди можливо. Заміною для x ми отримуємо функцію, для мінімізації, що залежить від власного значення матриці Лапласа # 955; 2.
f (x) = 0.25 (# 945; 2 + 2 # 955; 2 + # 945, 3 2 # 955; 3 + ... + # 945; n 2 # 955; n) починаючи з # 955; 1 = 0.
очевидно
(# 945; 2 + 2 + # 945; 3 2 ... + # 945; n 2) # 955; 2 <= (α2 2 λ2 + α3 2 λ3 +…+ αn 2 λn ) учитывая упорядоченность собственных величин f(x)>= n # 955; 2/4.
Ми можемо мінімізувати f (x) = n # 955; 2/4, вибираючи.
Отриманий вектор x - рішення безперервної завдання. Залишається вирішити задачу відображення вектора x до дискретного розподілу. Для цього знаходиться медіана значень xi, і потім відображається вершини вище значення медіани в один набір, нижче в інший. Якщо кілька вершин мають значення медіани, то вони розподіляються, не порушуючи рівноваги. Це рішення - найближча дискретна точка до безперервного оптимуму.
ДОСЛІДЖЕННЯ МЕТОДІВ ОРГАНІЗАЦІЇ ДАНИХ
Як вже говорилося, при реалізації алгоритму постає завдання вибору типу даних для представлення інформації про графа.
Завдання графів за допомогою матриць зручно для алгоритмів, що використовують матричні обчислення (наприклад, алгоритм спектральної бисекции). Однак, при обробці графа великої розмірності (n = 1000, 10000), матриці займають занадто багато пам'яті. Слід врахувати, що матриці графів потоків даних досить зріджені, т. Е. Матриці містять багато нулів.
Розглянемо наступні уявлення матриці при програмної реалізації алгоритму:- двовимірний масив;
- масив динамічних масивів (перший елемент динамічного масиву - число ненульових елементів в рядку матриці);
- три масиву: масив ненульових елементів матриці, масиви індексів рядків і стовпців, які відповідають цим елементам;
- матриця в форматі RR (C) O. Скорочена назва даного формату походить від англійського словосполучення "Row - wise Representation Complete and Ordered" (рядкове подання, повне і впорядковане) [6].