Реферат

Динамічна топологія при розподіленому логічному моделюванні цифрових систем

Вступ
Огляд досліджень і розробок з теми
Основні результати
1. Дослідження алгоритмів моделювання
2. Класифікація методів балансування навантаження при розподіленому моделюванні
3. Опис архітектури обчислювальної мережі
4. Розробка програмної системи
Висновки
Література

1. Актуальність роботи

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

2. Цілі та наукові завдання

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

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

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

   Наукові завдання:

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

3. Наукова новизна

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

4. Практичні значущість:

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

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

   У ДонНТУ розробки, що пов'язані з розподіленим моделюванням проводять Скобцов Ю.А., Фельдман Л.П., Ладиженський Ю.В. Також питаннями, що пов'язані з розподіленим моделюванням займається к.т.н. Попов Ю.В.

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

   Моделювання як науковий напрямок досліджувався в інституті кібернетики академіком АН СРСР Глушковим В.М. Роботи, що пов'язані з різноманітними напрямками в імітаційному моделюванні належать таким вченим як Мар'янович Т.П., Литвинов В.В., Коваленко I.Н., Калініченко Л.А., Гусєв В.В., Жук К.Д., Бакаєв А.А.

   Розподілене моделювання як один із напрямків наукових досліджень почав розвиватися наприкінці 70-х – на початку 80-х років XX століття. Найважливішим етапом у розробці систем розподіленого моделювання є розробка алгоритмів синхронізації, які необхідні для коректного виконання процесу моделювання з одночасним використанням декількох комп'ютерів у мережі. Перші алгоритми синхронізації було запропоновано наприкінці 70-х років. Ці алгоритми належать до класу консервативних алгоритмів. Вони описані у роботах Chandy K. M. і Misra J. (1987) і Bryant R.E. (1977).

   На початку 80-х років D. Jefferson запропонував Time Warp алгоритми (алгоритми деформації часу). Ці алгоритми було покладено за основу оптимістичних алгоритмів синхронізації.

   Необхідно відзначити також таких вчених як Fersha A., Fujimoto R.M., які провели багато досліджень та опублікували велику кількість матеріалів, що пов'язані із розподіленим моделюванням. Динамічна топологія і балансування навантаження у системах розподіленого моделювання досліджувалися такими вченими, як Theodoropoulos G., Logan B., Schlagenhaft R., Ruhwandl M., Sporrer C., Jla V., Bagrodia R. та ін.

1. Дослідження алгоритмів моделювання

   Змінення, яким піддається система моделювання, оформлені у вигляді подій і станів. Поточне значення у вузлах схеми – це стан системи, а змінення сигналів у часі – це події. Моделювання виконується у дискретному віртуальному часі [1,5,6]. Алгоритми моделювання розрізняються чергою обробки та планування нових подій [6] (див. рис. 1).

Рис. 1. Класифікація алгоритмів моделювання

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

   Прискорення моделювання може бути отримане завдяки використанню паралельних та розподілених обчислювальних систем. Передбачається, що моделювання системи на n комп'ютерах дозволяє прискорити процес моделювання у n разів [4].

   При паралельному моделюванні прискорення можна досягнути завдяки тому, що окремі частини алгоритму моделювання виконуються паралельно [1]. Моделювання виконується на багатопроцесорній обчислювальній системі з загальною пам'яттю [5].

   При розподіленому моделюванні використовується декілька комп'ютерів, які об'єднані у обчислювальну мережу. При цьому система, що моделюється, розрізається на частини, кожна з яких моделюється на окремому комп'ютері (процесорі моделювання – МодПр) [2]. За таким засобом моделювання важливим є збереження взаємозв'язків між частинами системи та синхронізація роботи МодПр [7].

   Найбільш простий засіб синхронізації – використання у системі моделювання глобального віртуального часу, з яким повинен співпадати локальний віртуальний час усіх МодПр. Цей алгоритм розподіленого моделювання є синхронним [2,5].

   У асинхронних алгоритмах моделювання кожний МодПр працює у своєму локальному віртуальному часі LVT. Оскільки LVT розрізняється для всіх МодПр, тому в системі можуть виникати події, виконання яких є неможливим. Наприклад, можуть виникнути події, час виконання яких уже відбувся для МодПр, який повинен їх виконати. Це може призвести до неправильних результатів та глухих кутів [2]. Тому важливий етап організації системи розподіленого моделювання – це організація коректної обробки подій у часі [1].

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

   В оптимістичних алгоритмах МодПр не очікує дозволу на обробку подій. Припустимим є виникнення подій у локальному минулому, при цьому відбувається повернення системи до попереднього стану, що дозволяє виконувати ці події [2]. Поданий підхід дозволяє МодПр не витрачати час на очікування одне одного, що прискорює процес моделювання [1,3]. Недолік поданого алгоритму – це необхідність використання пам'яті задля зберігання різноманітних станів системи.

   При використанні комбінованих протоколів МодПр обробляють події, що заплановані на моменти часу від LVT до LVTH+∆t,
де 0<=∆t<=+∞ – визначає ступінь оптимістичності протоколу [2]. Горизонт розширення локального віртуального часу LVTH використовується у консервативних алгоритмах синхронізації і є значенням LVT, за яким МодПр перейде у режим очікування. Отже, при ∆t=0 комбінований протокол синхронізації стає консервативним, а при ∆t=+∞ – оптимістичним [3].

2. Класифікація методів балансування навантаження при розподіленому моделюванні

   Класифікація методів балансування навантаження наведена на рисунку 2. При використанні статичного балансування навантаження не враховуються особливості, що мають суттєвий вплив на загальний час виконання моделювання: змінення обчислювального середовища, змінення приступної обчислювальної потужності [10]. Для прискорення моделювання необхідно використовувати динамічне балансування навантаження, яке базується на обчисленні параметрів, що використовуються для прийняття рішень про змінення топології. Комбіноване балансування складається із попереднього аналізу системи, що моделюється та механізму контролю навантаження [9].

Рис. 2. Класифікація методів балансування навантаження

    Для балансування навантаження характерним є блокування системи що моделюється під час виконання процедури перерозподілу. Глобальне блокування потребує призупинення моделювання на усіх логічних процесорах (ЛП). Це може призвести до простою окремих МодПр та нераціонального використання обчислювальних ресурсів. Локальне блокування означає, що моделювання призупиняється тільки на тих процесорах, які приймають безпосередню участь у перерозподілі. Можливість виконання тільки локального блокування без необхідності блокування усіх процесорів надається для архітектури обчислювальної системи, у якій використовуються комунікаційні логічні процесори [8].

    Змінення топології на фізичному рівні – це переміщення частин системи що моделюється з одного МодПр на інший. Використання поданого метода описане у [9,10]. Наприклад, система розподіленого моделювання Triad.Net [9] організована так, як зображено на рисунку 3.

Рис. 3. Органiзація системи розподіленого моделювання Triad.Net

   Підсистема балансування визначає навантаження процесорів, на яких виконується моделювання, навантаження на лiніях зв'язку, частоту обмінів між об'єктами, що моделюються. На основi аналізу цих даних пiдсистема балансування не перериває процес моделювання і виконує перерозподіл об'єктів системи, яка моделюється [9].

   У [10] запропоновано два методи, що дозволяють прискорити процес моделювання: мультикластерне подання частини схеми (див. рис. 4) на ЛП та динамічне балансування навантаження, що базується на переміщенні кластерів під час моделювання задля отримання рівномірного навантаження на всі МодПр.

Рис. 4. Моделювання з використанням розділення на кластери

   В [10] для отримання рівномірного навантаження МодПр передбачено механізм переміщення кластерів. Переміщення декотрого кластера на інший МодПр виконується у наступній послідовності [10]:

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

   Змінення топології на логічному рівні використовується у підході, описаному в [8]. Згідно з цим методом, кожний логічний процесор виконує моделювання частини схеми у своїй сфері впливу. Керуванням сферами впливу керують спеціальні комунікаційні логічні процесори (КЛП). Зв'язок між ЛР відсутній, інформація може передаватися тільки через відповідний КЛП. Якщо наприклад необхідно передати дані між двома ЛП, які не зв'язані одним КЛП, тоді дані будуть передаватися вгору по дереву зв'язків КЛП [8].

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

    Змінення станів вузлів схеми оформляється у вигляді подій. Тому декотрий вузол схеми vj – це частина сфери впливу подій. Логічний процес ЛПi шляхом передачі повідомлень про події може впливати на vj. Нехай ранг змінної vj для процеса ЛПi – це кількість подій, що приходять від ЛПi і змінюють значення змінної vj в інтервалі часу [t1; t2] [8].

   Вартість доступу логічного процеса ЛПi до змінної vj (ранг vj для ЛПi – r(vj, ЛПi)) – це кількість КЛП, які повинні бути пройденими, щоб досягнути змінення vj у інтервалі часу [t1;t2]. Вартість звертання до локальних змінних l(vj, ЛПi) у власному КЛП дорівнює 0 [8].

   Вартість доступу деякого ЛП до всіх змінних у сфері впливу S(ЛПi) визначається за формулою (1) [8]:

(1)

   Загальна вартість доступу до всіх ЛПi, i=1..n всіх ЛП конкретного розподілення в інтервалі часу [t1;t2] визначається за формулою (2) [8]:

(2)

   Найкращою декомпозицією в iнтервалі часу [t1;t2] є та, за якою загальна вартість є мінімальною. Задача кожного КЛП – наближення загальної вартості доступу всіх логічних процесорів до мінімальної [8].

   Механізм контролю навантаження, що характерний для динамічного балансування навантаження, описаний у [10]. Він реалізований у вигляді алгоритму у головному контролюючому процесі (див. рис. 5).

Рис. 5. Механізм контролю навантаження

    Під час моделювання виконується розрахунок деяких величин, які дозволяють визначати поточне навантаження на ЛП: віртуальній час просування та час беззбитковості [10].

3. Опис архітектури обчислювальної мережі

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

Рис. 6. Розподілене моделювання системи, яка розрізана на частини

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

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

   У системі моделювання містяться:

• адміністратор процесу моделювання;
• логічні процесори (ЛП);
• комунікаційні логічні процесори (КЛП).

   Адміністратор процесу моделювання необхідний для керування завданнями моделювання на процесорах моделювання (ЛП та КЛП) та реєстрації приступних для моделювання процесорів. При зміненні топології системи моделювання він може виконувати перерозподіл завдань завдяки використанню цієї інформації.

    Логічні процесори виконують моделювання частини схеми, що входить до їх сфери впливу. Логічний процесор містить список подій EVL, віртуальні годинники VT, структурно-функціональну модель схеми (SFSM) та перелік тих вузлів, котрі він повинен моделювати (свою сферу впливу).

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

   За попереднім описанням структура системи моделювання виглядає так, як показано на рисунку 7.

Рис. 7. Структура системи моделювання

    Моделювання однієї цифрової схеми – це одне завдання моделювання. Для завантаження завдань для виконання використовується проект адміністратора процесу моделювання у вигляді файла [3]. Для виконання кожного завдання адміністратор процесу моделювання визначає спочатку один головний КЛП (см. рис. 7). Далі на головний КЛП завантажуються всі завдання моделювання (СФМС, вхідний вплив), пiсля чого для даного КЛП виділяються підлеглі ЛП. При моделюванні на базі поточного завантаження підлеглих процесорів кожний КЛП може прийняти рішення про необхідність виділення йому додаткових ЛП, які не зайняті та про перерозподіл сфер впливу між ними. При виявленні груп ЛП, між якими відбувається найбільш частий обмін повідомленнями можливим є виділення для них окремого КЛП для зменшення навантаження на інші КЛП (див. рис. 8).

Рис. 8. Перерозподіл дерева КЛП

(анімація: 7 кадрів, 7 циклів повтору, затримка між кадрами 0,3 с; розмір 13 К; Adobe Photoshop CS3)

   Прийняття рішень про змінення топології системи моделювання приймається на базі параметрів, запропонованих у [2] і описаних у п.2.

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

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

   Визначимо основні вимоги, що пред'являються до системи у вигляді діаграми прецедентів (див. рис. 9).

Рис. 9. Діаграма прецедентів

   Як показано на рисунку 9, основними виконавцями у системі є адміністратор процесу моделювання Process Administrator, комунікаційні логічні процесори Communication Processor і логічні процесори, що виконують моделювання (Logical Processor). Ці виконавці у системі можуть виконувати дії, що оформлені у вигляді прецедентів. В основному функціонування об'єктів полягає у передаванні та прийомі повідомлень різних типів.

   За вимогами, які визначені для системи, можна збудувати діаграму класів (див. рис. 10).

Рис. 10. Діаграма класів

   Діаграма класів показує організацію процесорiв моделювання у системі (ЛП и КЛП). Вони містять віртуальні годинники TVirtualClock, списки подій TEventContainer. Структурно-функціональна модель схеми (клас TSFSM) входить до завдання, яке представлене у класі TSelection. Комунікаційний логічний процесор містить iнформацію про підлеглі процесори у вигляді масиву структур FProcessors. Ця інформація відновлюється в залежності від змінення кількості приступних процесорів у методі UpdateProcessors. Також у рамках цих методів ведеться збір даних про поточну інтенсивність обміну повідомленнями між підлеглими процесорами.

Висновки

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

   У результаті досліджень отримано наступні основні результати:

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

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

Література

1. Ладиженський Ю.В., Попов Ю.В. Програмна система для дослідження протоколів синхронізації при розподіленому логічному моделюванні // Матеріали науково-практичної конференції «Сучасні технології проектування систем на мікросхемах програмованої логіки».– Харків: Харківський національний університет радіоелектроніки, 2003.– С.44.
2. Ладиженський Ю.В., Попов Ю.В. Система розподіленого логічного моделювання цифрових пристроїв з використанням консервативного протоколу синхронізації // Наукові праці Донецького національного технічного університету. Серія: інформатика, кібернетика та обчислювальна техніка, випуск 39: – Донецьк: ДонНТУ, 2002.– c. 21-29.
3. Ладиженський Ю.В., Попов Ю.В. Об'єктно-орієнтована модель протоколів синхронізації при розподіленому логічному моделюванні цифрових пристроїв // Наукові праці Донецького національного технічного університету. Серія: Обчислювальна техніка та автоматизація. Випуск 64 – Донецьк: Вид-во ДонНТУ, 2003.– c. 212-221.
4. Fujimoto R.M. Parallel and distributed simulation systems // Winter Simulation Conference 2001.– Arlington, VA, USA: ACM, 2001.– p.147-157.
5. Fersha A. Parallel and Distributed Simulation of Discrete Event Systems // Hardbound of Parallel and Distributed Computing.– McGraw-Hill, 1995.
6. Jefferson D.R. Virtual time //USC Tech. rep. TR-83-213.– Los Angeles: Univ. of Southern California.– 1983.
7. Chandy K.M., Misra J. Asynchronous distributed simulation via a sequence of parallel computations // Communications of The ACM – CACM, vol. 24, no. 4, pp. 198-206, 1981.
8. Theodoropoulos G., Logan B. An approach to interest management and dynamic load balancing in distributed simulation // 2001 European Simulation Interoperability Workshop.– London: University of Westminster, 2001.– p.566-571.
9. Міков А.И., Замятіна Е.Б., Осмехін К.А. Метод динамічної балансировки процесів імітаційного моделювання // Матеріали Всеросійської науково-технічної конференції «Методи і засоби обробки інформації МСО-2005».– Москва: МГУ, 2005.– с.472-478.
10. Schlagenhaft R., Ruhwandl M., Sporrer C., Bauer H. Dynamic load balancing of a multi-cluster simulator on a network of workstations // 9th Workshop on Parallel and Distributed Simulation.– New York: Parallel and Distributed Simulation, Workshop on, 1995.– p. 175-180.

Важливе зауваження

   При написанні автореферату магістерська робота ще не завершена. Дата завершення – 1 грудня 2011 р. Повний текст роботи, а також матеріали з теми можуть бути отримані від автора або керівника після вказаної дати.

Copyright © Балута Анжеліка, ДонНТУ, 2011