Резервування розподілених обчислювальних ресурсів в мережах Grid

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

Національна академія наук України

Інститут проблем моделювання в енергетиці ім. Г.Є.Пухова

УДК 004.75

Автореферат

дисертації на здобуття наукового ступеня кандидата технічних наук

Резервування розподілених обчислювальних ресурсів в мережах Grid

05.13.05 - Комп'ютерні системи та компоненти

Ільяшенко Матвій Борисович

Київ - 2008

Дисертацією є рукопис.

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

Науковий керівник: к.т.н., доцент, Кудерметов Равіль Камілович, зав. каф. «Комп'ютерні системи та мережі» Запорізького національного технічного університету.

Офіційні опоненти:

д.т.н., професор, Святний Володимир Андрійович, зав. кафедрою ЕОМ Донецького національного технічного університету;

к.т.н., ст. наук. співр., Кисельов Геннадій Дмитрієвич, доцент кафедри Системного проектування ННК ІПСА НТУУ «КПІ».

Захист відбудеться «30» жовтня 2008 р. о 14 годині на засіданні Спеціалізованої вченої ради Д 26.185.01 Інституту проблем моделювання в енергетиці ім. Г.Є.Пухова НАН України за адресою: 03164, м. Київ, вул. Генерала Наумова, 15.

З дисертацією можна ознайомитися у бібліотеці Інституту проблем моделювання в енергетиці ім. Г.Є.Пухова НАН України за адресою: 03164, м. Київ, вул. Генерала Наумова, 15.

Автореферат розісланий «25» вересня 2008 р.

Вчений секретар спеціалізованої вченої ради, к.т.н. Е.П. Семагіна.

Загальна характеристика роботи

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

засоби збирання, обліку й зберігання інформації про наявні обчислювальні ресурси;

механізми резервування, на які опирається прошарок кооперації, і, зокрема, запуск паралельних завдань;

засоби контролю за подіями, що відбуваються в системі керування (звільнення ресурсів, запуск/завершення завдань);

керування, попереднє резервування ресурсів пам'яті, призначення пріоритетів мережному трафіку, резервування пропускної смуги мережі.

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

Проблемам проектування нових багатопроцесорних, кластерних архітектур, GRID-технологій присвячені роботи груп учених під керівництвом К.Г. Самофалова, А.І. Петренка, О.В. Забродіна, Я. Фостера. Методи підвищення ефективності спеціалізованих паралельних обчислювальних систем досліджувалися в працях Б.Н. Маліновського, В.П. Боюна, І.А. Каляєва, Г.Р. Ендрюса. Питаннями резервування ресурсів у мережах GRID займаються В.М. Коваленко, Є.І. Коваленко, Д.О. Корягін Е.З. Любимський. Незважаючи на результати численних досліджень в галузі підтримки паралельних обчислень, роботи в цьому напрямку не втрачають свого значення й вимагають подальшого розвитку у зв'язку з масовим поширенням технологій паралельного й розподіленого оброблення даних.

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

Засоби менеджменту ресурсів для систем пакетного оброблення (PBS, Condor, тощо) не підтримують важливих для паралельних обчислень структурних даних при розподілі завдань.

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

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

Зв'язок роботи з науковими програмами, планами, темами. Основні дослідження з теми дисертації проводилися на кафедрі КСтаМ ЗНТУ в рамках науково-дослідницької роботи за держбюджетною НТР №IT506-2007 "Створення національної Grid інфраструктури для забезпечення наукових досліджень" (номер державної реєстрації 0107U007931), що проводиться в рамках державної програми "Інформаційні та телекомунікаційні технології в освіті і науці", у якій здобувач брав участь як виконавець.

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

Для досягнення цієї мети необхідно вирішити такі основні завдання:

- дослідити наявні методи й підходи до резервування ресурсів у мережах GRID;

- проаналізувати граф-аналітичні методи вирішення завдань структурної ідентифікації (знаходження підмереж заданої конфігурації);

- розробити алгоритми встановлення морфізму на графах (алгоритми встановлення ізоморфізму на графах, граф-підграф ізоморфізму, знаходження найбільшого загального підграфу) і вдосконалити їх для роботи зі зваженими й поміченими графами;

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

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

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

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

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

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

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

Наукова новизна отриманих результатів:

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

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

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

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

Практичне значення отриманих результатів. На основі запропонованих методів і підходів створені аналітичні, алгоритмічні й програмні засоби:

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

- запропоновано послідовний і паралельний алгоритми для одержання повних наборів неізоморфних графів і повних наборів графів, що мають спеціальні властивості;

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

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

- вирішено завдання про кількість способів, якими можна скласти повний граф на 11 вершин з 11 циклів довжиною 5, та отримані повні набори неізоморфних графів із кількістю вершин до 10 включно й повні набори дерев і лісів із кількістю вершин до 20 включно.

Отримані результати використовуються в навчальному процесі на кафедрі КСтаМ при викладанні дисциплін «Комп'ютерні мережі» і «Паралельне програмування», а також при проведенні робіт з НТР №IT506-2007 «Створення національної GRID інфраструктури для підтримки наукових досліджень» (номер державної реєстрації 0107U007931).

Особистий внесок здобувача. Всі основні положення й результати дисертаційної роботи, що виносяться на захист, отримані автором самостійно.

Апробація результатів дисертації. Основні положення й результати дисертаційної роботи доповідалися, обговорювалися й одержали позитивну оцінку на таких конференціях і семінарах: Міжнародна наукова конференція молодих учених, аспірантів і студентів “Політ-2001” (м. Київ, 2001 р.); Міжнародна наукова конференція “Актуальні проблеми державного керування й місцевого самоврядування” (м. Запоріжжя, 2001 р.); Второй международный конгресс студентов, молодых ученых и специалистов "Молодежь и наука- третье тысячелетие" (г. Москва, 2002 г.); 9-й міжнародний молодіжний форум “Радіоелектроніка й молодь в XXI столітті” (м. Харків, 2005р.); Перша міжнародна студентська науково-технічна конференція “Інформатика й комп'ютерні технології 2005” (м. Донецьк, 2005р.); Міжнародна практична конференція “Сучасні проблеми й досягнення в галузі радіоелектроніки, телекомунікацій й інформаційних технологій” (м. Запоріжжя, 2006р.); Друга міжнародна наукова конференція студентів, аспірантів і молодих вчених “Комп'ютерний моніторинг й інформаційні технології” (м. Донецьк, 2006р.); Третя міжнародна конференція “Теоретичні й прикладні аспекти побудови програмних систем” (м. Київ, 2006р.); Науково-технічні конференції “Тиждень науки” (м. Запоріжжя, 2007-2008р.); Міждержавна науково-методична конференція “Проблеми математичного моделювання” (м. Дніпродзержинськ, 2007р.); Seventh international conference on parallel processing and applied mathematics PPAM-2007 (Gdansk, Poland, 2007); Седьмая международная конференция-семинар “Высокопроизводительные Параллельные Вычисления на Кластерных Системах” (г. Нижний Новгород, 2007г.); 9-та міжнародна науково-практична конференція “Сучасні інформаційні й електронні технології” (м. Одеса, 2008р.); Десята міжнародна науково-технічна конференція “Системний аналіз й інформаційні технології” (м. Київ, 2008р.).

Публікації. Основні результати дисертаційної роботи опубліковані в 18 друкованих працях, з них: 5 статей у виданнях, які включено до списку ВАК України, 13 у працях міжнародних наукових конференцій і семінарів, 15 наукових праць написані без співавторів.

Структура й обсяг роботи. Дисертаційна робота обсягом 147 машинописних сторінок складається зі вступу, чотирьох розділів, висновків, списку використаних джерел, що складається з 102 найменувань і розташований на 11 сторінках, 3 додатків. Дисертація містить 22 малюнки і 8 таблиць.

Основний зміст роботи

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

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

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

Алгоритм установлення ізоморфності базується на методі гілок і границь. Для прискорення переборної частини алгоритму запропоновано використання матриці можливих суміщень. Матриця можливих суміщень - це матриця розміром , де - кількість вершин у порівнюваних графах. Кожен елемент цієї матриці може приймати значення 0 або 1 залежно від того, чи можуть бути сполучені вершини графу і графу . Використання матриці дозволяє виконувати значний обсяг попередніх перевірок і формувати на їх основі просту умову, яка використовується в переборній частині алгоритму для обмеження глибини пошуку. У межах матриці реалізується перевірка всіх обмежень, не базованих на інформації, отриманій у процесі накладання вершин. grid алгоритм морфізм

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

У дисертації розроблений новий інваріант Zero2. Інваріант Zero2 являє собою впорядкований вектор ступенів вершин, суміжних даній і є розвитком інваріанта Zero.

Нехай - інваріант Zero2 графу , тоді

, - вектор, що зберігає ступені вершин графу .

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

Елементи вектора і рядка матриці лексикографічно впорядковуються за зменшенням.

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

Крім того, досліджено застосування інваріантів на підставі матриці відстаней між вершинами графів, -інваріанта першого порядку First та ін.

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

Реалізовано такі попередні перевірки, що формують матрицю можливих суміщень:

, , (1)

ступінь вершини графу ;

, , (2)

кількість вхідних ребер вершини графу ;

,, (3)

кількість вихідних ребер вершини графу ;

, , (4)

рядок інваріанта Zero2 графу , що відповідає вершині ;

, , (5)

кількість вершин у хвильовому розкладанні графу , починаючи з вершини ;

, , (6)

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

, , (7)

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

, , (8)

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

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

Нехай - кількість ребер інцидентних вершинам з меншими номерами й - сумарна кількість варіантів суміщення вершини графу з вершинами графу . Тоді порядок сортування вершин графу наступний:

, де .(9)

, , .(10)

Тобто вершини графу сортуються в порядку зменшення кількості зв'язків із вершинами, що мають менші номери, або в порядку зменшення кількості варіантів суміщення вершин, якщо кількість зв'язків однакова.

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

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

Нехай - кількість зв'язків вершини графу із вершинами , а - кількість зв'язків вершини графу із вершинами .

Початковому стану відповідає часткове підставлення, при якому не сполучено ще жодної пари вершин.

Для одержання -го стану для вершини шукається відповідність серед вершин , які відповідають умовам:

; (11)

;(12)

, , .(13)

Якщо виконані всі три умови, з яких третя є прямим наслідком визначення ізоморфізму, то відповідна пара вершин входить у часткове підставлення й формується новий стан .

Чисельна оцінка обчислювальної складності алгоритму. Як вихідні дані для дослідження були взяті випадково згенеровані графи зі щільністю реберного заповнення від 0.1 до 0.5 і кількістю вершин від 20 до 1000. Як результат, на графіках використовувався усереднений час перевірки 100 пар графів. Усі пари графів, що перевірялися, були ізоморфні, оскільки цей випадок є більш складним для перевірки, ніж неізоморфні графи, підтвердження неізоморфності яких можна одержати в більшості випадків на етапі попередніх перевірок і перетворень.

Результати досліджень наведені на рис. 1 і 2.

Рис. 1. Залежність часу перевірки на ізоморфність від кількості вершин для різних значень щільності реберного заповнення в експонентній системі координат

Рис. 2. Залежність часу перевірки на ізоморфність від кількості вершин для різних значень щільності реберного заповнення в логарифмічній системі координат

Значення Y₀, Y₁, Y₂, Y₃ й Y₄ відповідають щільності реберного заповнення 10%, 20%, 30%, 40% й 50%, відповідно.

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

Порівняння з аналогами на графах еталонної бази графів. У роботах Паскаля Фогія пропонується еталонна база графів для оцінки продуктивності алгоритмів установлення морфізму на графах. Склад еталонної бази наведений у табл. 1.

Таблиця 1. Склад бази графів для порівняння продуктивності алгоритмів перевірки на ізоморфність

Тип графів	Кількість пар	Параметри	Розміри (вершин)
Випадково згенеровані графи (3000)	1000	з=0.01	20-1000
	1000	з=0.005	20-1000
	1000	з=0.001	20-1000
Регулярні мережі	1000	2D мережі	16-1024
	800	3D мережі	27-1000
	500	4D мережі	16-1296
Нерегулярні мережі	3000	Нерегулярні 2D мережі с={0.2,0.4,0.6}	16-1024
	2400	нерегулярні 3D мережі с={0.2,0.4,0.6}	27-1000
	1500	нерегулярні 4D мережі с={0.2,0.4,0.6}	16-1296
Регулярні графи з обмеженим ступенем вершин	1000	ступінь=3	20-1000
	1000	ступінь=6	20-1000
	1000	ступінь=9	20-1000
Нерегулярні графи з обмеженим ступенем вершин	1000	ступінь=3, б=0.1	20-1000
	1000	ступінь=6, б=0.1	20-1000
	1000	ступінь=9, б=0.1	20-1000
Разом	18200

Для порівняння продуктивності алгоритмів перевірки графів на ізоморфність використовувалися алгоритми того ж класу (тобто точні алгоритми, базовані на методі гілок і границь та його модифікаціях). Серед наявних алгоритмів були обрані найбільш швидкі (алгоритми VF і VF2), найпоширеніші при реалізації систем, що використовують операцію встановлення ізоморфності, добре досліджені (алгоритми SD й ULL), алгоритм, розроблений В.П. Пінчуком (ISOMORF).

Як операційна система для проведення досліджень був обраний Linux Mandrake 9.2, компілятор gcc 3.3.1. Розрахунки виконувалися на комп'ютері AMD Athlon XP 1700+, 512 Mb RAM. Ліміт часу на порівняння 100 пар графів становив 200 секунд машинного часу.

Дослідження показали, що розроблений алгоритм для класів регулярних 2D мереж і випадкових графів має найбільшу продуктивність серед наявних аналогів.

Рис. 3. Час перевірки регулярних 2D мереж (параметри N=16..1024, с=0.0)

Рис. 4. Час перевірки випадково згенерованих графів (параметри N=20..1000, з=0.01)

Далі в роботі наводяться приклади застосування розробленого алгоритму встановлення ізоморфізму для одержання повних наборів неізоморфних графів і графів, що мають спеціальні характеристики, зокрема два паралельних алгоритми. Чисельно отримані повні набори неізоморфних графів з кількістю вершин до 10 включно і набори дерев і лісів з кількістю вершин до 20 включно. Наводиться розв'язання задачі про кількість способів, якими можна одержати повний граф на 11 вершин з 11 циклів довжиною 5 - 1040257906329600 способами.

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

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

, , (14)

ступінь вершини графу ;

, , (15)

кількість вхідних ребер вершини графу ;

, , (16)

кількість вихідних ребер вершини графу ;

, , (17)

кількість вершин у хвильовому розкладанні підграфу оточення вершини графу ;

, , (18)

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

, , (19)

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

, , (20)

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

Як і в алгоритмі встановлення ізоморфності виконується сортування вершин графів. У переборній частині алгоритму умова 2 замінена на .

Чисельне дослідження алгоритму знаходження граф-підграф ізоморфізму було проведено на графах еталонної бази для оцінки продуктивності алгоритмів встановлення морфізму на графах. Для порівняння використовувалися алгоритми ULL - алгоритм Улмана й VF й VF2 - алгоритми Паскаля Фогія.

Розроблений у роботі алгоритм показав найбільшу продуктивність для випадкових графів і нерегулярних 2D мереж. Характерні результати наведені на рис. 5 і 6.

Рис. 5. Нерегулярні 2D мережі

Рис. 6. Випадково згенеровані графи

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

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

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

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

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

Таблиця 2. Результати дослідження характеристик паралельного алгоритму (усереднені дані на підставі порівняння 37 пар графів; параметри алгоритму, )

Кількість процесорів	Час роботи (сек)	Прискорення	Ефективність
1 (послідовний)	1080,31	-	-
3	328,23	3,29	1,09
7	228,04	4,73	0,67
11	182,69	5,91	0,54
15	172,90	6,24	0,42
19	159,75	6,76	0,36

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

Алгоритм знаходження найбільшого загального підграфу є розвитком алгоритмів знаходження ізоморфізму і граф-підграф ізоморфізму. Це також точний, переборний алгоритм, базований на методі гілок і границь. Його продуктивність досліджувалася на графах еталонної бази графів. Результати дослідження показали, що для всіх графів еталонної бази знаходження підграфу займало не більше 0.2 секунди машинного часу при переборі не більш ніж 6000 вузлів дерева рішень. Така продуктивність дає можливість використовувати розроблений алгоритм знаходження найбільшого загального підграфу в сучасних прикладних задачах.

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

Алгоритм резервування ресурсів базується на розробленому в роботі алгоритмі знаходження граф-підграф ізоморфізму для зважених графів. Граф описує структуру мережі GRID, при цьому ваги, приписані вершинам графу відповідають обчислювальній продуктивності вузлів мережі, виміряної в MIPS або MFLOPS, а ваги, приписані ребрам графу, відповідають пропускній здатності мережних з'єднань в Mbps. Граф описує потреби в розподілених ресурсах завдання, для якого виконується резервування, при цьому ваги, приписані вершинам графу, відповідають потребам процесів завдання в процесорних ресурсах вузла мережі, на якому вони будуть розміщені, а ваги, приписані ребрам графу, очікуваний трафік генеровуваний між двома відповідними процесами завдання. Розв'язанням задачі резервування ресурсів у термінах теорії графів є знаходження граф-підграф ізоморфізму для двох зважених по вершинах і ребрах графів і .

Оптимізація виділення розподілених ресурсів може відбуватися за такими критеріями:

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

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

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

4. За критерієм мінімальної сумарної нерозподіленої пропускної смуги каналів зв'язку. Розв'язок знаходиться відповідно до пункту два, для реберних графів обчислювальної мережі і резервовуваної зони.

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

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

, де (21)

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

, , (22)

де - множина ваг, приписаних вершинам графу мережі , задіяних у повному підставленні.

Пошук оптимальної зони резервування за критерієм мінімальної кількості задіяних каналів зв'язку. Оптимальне резервування ресурсів за критерієм мінімальної кількості використовуваних каналів зв'язку (мережних з'єднань) базується на застосуванні алгоритму до реберних графів ( і ), отриманим з вихідного графу мережі G_N і вихідного графу завдання G_T.

Реберний граф (Line (edge) graph) - для заданого графу це граф , вершинами якого служать ребра графу і дві вершини суміжні в тоді і тільки тоді, коли відповідні ребра суміжні в .

Нехай підставлення ставить у відповідність вершинам реберного графу завдання частину вершин реберного графу мережі : .

Оптимальна зона резервування за критерієм мінімальної кількості задіяних мережних з'єднань визначається такою умовою, що накладають на повне підставлення:

, (23)

Пошук оптимальної зони резервування за критерієм максимальної завантаженості задіяних каналів зв'язку. Оптимальна зона резервування за критерієм максимальної завантаженості каналів зв'язку мережі визначається такою умовою:

, , (24)

де - множина ваг, приписаних вершинам реберного графу мережі , задіяним у повному підставленні.

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

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

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

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

3. Обмеження на програмне забезпечення сервера, наприклад, перевірка залежностей від версій установлених пакетів у середовищі Unix.

4. Чисельні обмеження, що приписані ребрам графу, наприклад, максимально припустима латентність мережних з'єднань, мінімальний пріоритет трафіку для кожного мережного з'єднання, тощо.

5. Флагові обмеження, що приписані мережним з'єднанням, наприклад, тип мережного з'єднання (Ethernet, Token ring тощо) чи є канал зв'язку захищеним чи ні, чи має канал зв'язку дублювання з'єднання для підвищення надійності чи ні.

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

Рис. 7. Схема багаторівневого резервування ресурсів у великих мережах GRID.

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

За умови застосування багаторівневої схеми резервування ресурсів, можливе розв'язання задачі резервування точними переборними алгоритмами для графів дуже великої розмірності за досить невеликий час.

Висновки

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

1. Вперше запропонований метод використання матриці попереднього суміщення і застосування інваріантів при формуванні граничних умов для підвищення продуктивності переборних алгоритмів встановлення морфізму на графах.

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

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

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

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

6. У дисертації на основі розроблених алгоритмів розв'язані задачі про кількість способів, якими можна скласти повний граф на 11 вершин з 11 циклів довжиною 5, а також отримані повні набори неізоморфних графів із кількістю вершин до 10 включно і повні набори дерев і лісів із кількістю вершин до 20 включно.

Список опублікованих автором праць за темою дисертації

1. Ильяшенко М.Б., Пинчук В.П. Численное исследование двух приближенных алгоритмов для задачи коммивояжера // Вісник Запорізького державного університету. Фізико-математичні науки. Біологічні науки. - 2003. - №1. - С. 37-42.

2. Ильяшенко М.Б. Разработка и исследование параллельного алгоритма проверки граф-подграф изоморфизма // Радиоэлектроника. Информатика. Управление. - 2006. - №1. - С. 63-69.

3. Ильяшенко М.Б. Унифицированный подход к решению задач морфизма на графах // Электронное моделирование. - 2008. - №1. - С. 19-43.

4. Ильяшенко М.Б. Алгоритм нахождения граф-подграф изоморфизма для взвешенных графов и его применение // Радиоэлектроника. Інформатика. Управление. - 2007. - №1. - С. 62-68.

5. Ильяшенко М.Б. Алгоритм оптимального резервирования распределенных вычислительных ресурсов по критерию эффективного использования вычислительных узлов // Радиоэлектроника. Інформатика. Управление. - 2007. - №2 - С. 64-69

6. Matviy Il'yashenko, Distributed resources reservation algorithm for GRID networks // Parallel Processing and Applied Mathematics, Springer-Verlag, Lecture Notes in Computer Science. - 2008. - vol. 4967. - pp. 922-931.

7. Ильяшенко М.Б. Проблемно-ориентированная библиотека и интегрированная среда для решения задач на графах // Тезисы второго Международного конгресса студентов, молодых ученых и специалистов «Молодежь и наука - третье тысячелетие/YSTM'02» - М.: МГТУ им. Баумана, 15-19 апреля 2002. - Часть 2. - C. 47.

8. Ільяшенко М.Б. Проблемно-орієнтована бібліотека та інтегроване середовище для рішення задач на графах // Тези Всеукраїнської студентської наукової конференції «Політ-2001» - К.: НАУ, 2001. - С. 29.

9. Ильяшенко М.Б. Технология резервирования ресурсов в сетях GRID // Тезисы докладов Межгосударственной научно-методической конференции «Проблемы математического моделирования». - Днепродзержинск: ДДТУ, 2007. - С. 178.

10. Ильяшенко М.Б., Кудерметов Р.К. Параллельный алгоритм получения полных наборов неизоморфных графов // Сборник трудов Первой международной студенческой научно-технической конференции «Информатика и компьютерные технологии 2005». - Донецк: ДонНТУ, 2005. - С. 385.

11. Ильяшенко М.Б., Кудерметов Р.К. Быстрый алгоритм установления изоморфности графов // Сборник трудов Первой международной студенческой научно-технической конференции «Информатика и компьютерные технологии 2005». - Донецк: ДонНТУ, 2005. - С. 387.

12. Ильяшенко М.Б. Быстрый алгоритм установления граф-подграф изоморфизма и его параллельная реализация. Сборник трудов Международной практической конференции «Сучасні проблеми і досягнення в галузі радіотехніки, телекомунікацій та інформаційних технологій». - Запорожье: ЗНТУ, 2006. - С.144.

13. Ильяшенко М.Б. Точный алгоритм нахождения наибольшего общего подграфа // Сборник трудов конференции «Комп'ютерний моніторинг та інформаційні технології». - Донецк: ДонНТУ, 2006. - С. 218-219.

14. Ильяшенко М.Б. Направления оптимизации резервирования ресурсов в сетях GRID // Тези доповідей науково-технічної конференції, Запоріжжя, 23-28 квітня 2007 р. - Запоріжжя: ЗНТУ, 2007. - С. 34-35.

15. Ильяшенко М.Б. Оптимальное резервирование распределенных вычислительных ресурсов // Высокопроизводительные параллельные вычисления на кластерных системах. Материалы Седьмой международной конференции-семинара. - Нижний Новгород: Из-во Нижегородского университета, 2007. - С. 170-176.

16. Ильяшенко М.Б. Оптимальное резервирование ресурсов в сетях GRID // Тезисы 9-й международной научно-практической конференции «Современные информационные и электронные технологии», Одесса, 19-23 мая 2008 г. - Одесса: ОНПУ. - 2008. - С. 114.

17. Ильяшенко М.Б. Резервирование ресурсов в сетях GRID для поддержки параллельных вычислений // Системный анализ и информационные технологии: Материалы Х Международной научно-технической конференции (20-24 мая 2008г., Киев). - К.: НТТУ «КПИ», 2008. - С. 295.

18. Matviy Il'yashenko, Distirbuted resources reservation algorithm for GRID networks // In Processing of 7-th International Conference on Parallel Processing and Applied Mathematics (9-12 september 2007, Gdansk, Poland). - Gdansk, 2007. - P. 86.

У роботах, опублікованих у співавторстві, дисертанту належить: [1] - жадібний алгоритм розв'язання задачі комівояжера із регульованою глибиною перегляду; [10] - паралельний алгоритм отримання повних наборів неізоморфних графів; [11] - алгоритм установлення ізоморфності. Роботи [2-9, 12-18] написані без співавторів.

Анотація

Ільяшенко М.Б. Резервування розподілених обчислювальних ресурсів в мережах GRID. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.05 - Комп'ютернi системи та компоненти. - «Запорізький національний технічний університет», Запоріжжя, 2008.

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

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

Ключові слова: резервування розподілених ресурсів, мережі GRID, ізоморфізм, граф-підграф ізоморфізм, інваріант, матриця можливих суміщень, оптимізація резервовуваної зони, паралельні обчислення.

Аннотация

Ильяшенко М.Б. Резервирование распределенных вычислительных ресурсов в сетях GRID. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.05 - Компьютерные системы и компоненты. - ГВУЗ «Запорожский национальный технический университет», Запорожье, 2008.

Диссертация посвящена разработке методов резервирования распределенных вычислительных ресурсов как части системы управления заданиями в сетях GRID с целью гарантированного предоставления необходимых для выполнения параллельных и распределенных приложений ресурсов в заданный момент времени и оптимизация резервируемой области с целью максимальной эффективности использования имеющихся вычислительных мощностей.

Для решения задач резервирования предложено использование точных переборных алгоритмов на графах, на основе алгоритма установления граф-подграф изоморфизма для взвешенных графов.

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

Проведена численная оценка производительности и сравнение с аналогами разработанных алгоритмов установления изоморфности и нахождения граф-подграф изоморфизма на базе эталонной базы графов для оценки производительности алгоритмов установления морфизма на графах. Результаты исследования показали, что разработанные алгоритмы имеют наибольшую производительность среди точных переборных алгоритмов установления морфизма для случайных графов (не обладающих специальными свойствами) и нерегулярных 2D сетей.

На основе разработанных алгоритмов установления морфизма на графах решена задача о числе способов, которыми можно составить полный граф на 11 вершин из 11 циклов длиной 5, получены полные наборы неизоморфных графов с числом вершин до 10 включительно и полные наборы деревьев и лесов с числом вершин до 20 включительно.

Алгоритм установления граф-подграф изоморфизма доработан для работы с взвешенными и помеченными графами. Разработанный алгоритм лег в основу алгоритма резервирования распределенных вычислительных ресурсов.

Впервые предложены методы оптимального резервирования распределенных вычислительных ресурсов на основании точного переборного алгоритма нахождения граф-подграф изоморфизма на графах по критериям минимального числа использованных вычислительных узлов или сетевых соединений и максимальной эффективности использования задействованных вычислительных узлов или сетевых соединений.

Предложены методы многоуровневой оптимизации резервируемой области для сетей большого размера и глобальной оптимизации резервируемой области за счет использования составного графа резервируемых ресурсов.

Разработанные в работе методы использовались в работах по гранту «Создание национальной GRID инфраструктуры» на базе Запорожского национального технического университета.

Материалы диссертации использовались в учебном процессе при выполнении научно-исследовательских, дипломных и магистерских работ, при подготовке лекционных курсов «Компьютерные сети» и «Параллельное программирование» на кафедре компьютерных систем и сетей ЗНТУ.

Ключевые слова: резервирование распределенных ресурсов, сети GRID, изоморфизм, граф-подграф изоморфизм, инвариант, матрица возможных совмещений, оптимизация резервируемой области, параллельные вычисления.

Annotation

Ilyashenko M.B. Distributed computing resources reservation in GRID networks. - Manuscript.

Thesis for candidate's degree in technical science by specialty 05.13.05 - computer systems and components. - Zaporozhie National Technical University, Zaporozhie, 2008.

Dissertation is devoted development of distributed resources reservation methods. As part of tasks management system for GIRD networks, with goal in guarnateeing required resources allocation for parallel and distributed applications at specified moment of time and with goal to most effective allocation of existed distributed resources of network.

In dissertations algorithms for optimal distributed resources reservation proposed based on minimal amount of used computational nodes or network connections usage criterions or based on most effective using of allocated computational nodes and network connections criterions. Also multi-level resources reservation method proposed for large GRID networks and global distributed resources reservation optimisation method based on compound tasks graph.

Key words: distributed resources reservation, GRID networks, isomorphism, subgraph isomorphism, invariants, possible superposition matrix, reserved area optimization, parallel computations.

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