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

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

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

Вступ

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

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

Імітаційне моделювання як новий науковий напрямок розпочало інтенсивно розвиватися наприкінці 1960-х років, коли стали широко впроваджуватися і використовуватися складні технічні системи в космосі, медицині, економіці й інших галузях людської діяльності. В Україні становлення моделювання як наукової дисципліни пов'язане з ім'ям академіка АН СРСР Глушковим В.М. Методологічною основою для розвитку імітаційного моделювання є роботи Глушкова В.М., Пухова Г.Е. Мар'яновича Т.П., Бусленка Н.П., Моісеєва Н.Н.

Перші алгоритми синхронізації процесів при розподіленому моделюванні були розроблені наприкінці 1970-х - початку 1980-х років. Оптимістичний протокол синхронізації (Time Warp) уперше описав Jefferson. Консервативний протокол синхронізації вперше описали Chandy, Misra і Bryant.

У теперішній час питанням розподіленого логічного моделювання активно займаються Скобцов Ю.О., Фельдман Л.П., Томашевський В.Н., Советов Б.Я. Серед закордонних дослідників слід зазначити Ferscha A., Fujimoto R.M.

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

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

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

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

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

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

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

Для досягнення поставленої мети необхідно вирішити наступні основні задачі дослідження:

1)розробити організацію обчислювальної мережі для розподіленого логічного моделювання цифрових систем;

2)розробити методи підвищення ефективності процесу моделювання за рахунок оптимізації локальних списків подій;

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

4)розробити методи оцінки та виконати теоретичне й експериментальне дослідження часової й ємнісної складності мережних моделюючих процесорів;

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

6)розробити Інтернет-портал розподіленого моделювання для організації online-доступу до мережі моделюючих процесорів.

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

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

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

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

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

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

Розглянуто організацію моделюючих процесорів (МодПр). Показано, що послідовний МодПр містить список подій EVL, віртуальні годинники VT, структурно-функціональну модель схеми СФМС і координатор процесу моделювання КПМ. Запропоновано архітектуру послідовного МодПр.

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

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

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

3. Методи оптимального розміщення даних при розподіленому логічному моделюванні

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

Запропоновано критерії для оцінки оптимальності результату відображення. Оцінки містять методи визначення дисбалансу навантаження (1), ступеня зв'язку (2) та ступеня досяжності (3) графа процесорів.

, (1)

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

змінюється від 0 у найкращому випадку (коли ваги всіх процесорів рівні між собою) до 1 у найгіршому випадку (коли всі елементи перебувають на одному процесорі).

(2)

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

змінюється від 0 у випадку, якщо в графі процесорів немає жодного каналу зв'язку до 1, якщо є канал зв'язку від кожного процесора до кожного.

 (3)

де - вартість найкоротшого шляху від вершини до вершини ; - ознака наявності шляху від вершини до вершини ;

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

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

,

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

Значення критеріїв оптимальності для вибору пари вершин:

1) - сума ваг пари вершин (для мінімізації дисбалансу навантаження):

.

2) - сума ваг з'єднуючих дуг. Використовується для мінімізації каналів зв'язків у графі процесорів:

3) - ознака відсутності шляху між парою вершин. Якщо вершини не досяжні друг для друга, то частини схеми, що відповідають цим вершинам, працюють паралельно незалежно один від одного:

4) - ознака наявності шляхів в обох напрямках. При стягуванні вершин сильної компоненти, може зменшитися кількість циклів:

5) - ознака наявності альтернативного шляху. Стягування таких вершин приведе до появи циклів:

,

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

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

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

Зроблений розрахунок пам'яті для всіх об'єктів системи. Для деяких об'єктів зроблене дослідження залежності обсягу пам'яті від параметрів схеми, що моделюється. Загальний обсяг пам'яті для одного моделюючого процесора визначається як сума обсягів пам'яті структурно-функціональної моделі схеми SFSM, локального списку подій EventContainer і координатора процесу моделювання SimProc. Обсяги пам'яті цих трьох об'єктів залежать від обсягів пам'яті комунікаційного інтерфейсу CommunicationInterface, об'єкта для обчислення глобальних станів GlobalState, хеш-таблиць, які дозволяють по деякому ключу швидко знаходити дане, асоційоване із цим ключем HashTable, динамічного списку з хеш-таблицею HashList, і простого динамічного списку DynamicListSimple.

(4)

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

Зроблено розрахунок пам'яті для всіх об'єктів системи (5) - (11). Для деяких об'єктів проведене дослідження залежності обсягу пам'яті від параметрів схеми, що моделюється.

(5)

(6)

(7)

(8)

(9)

(10)

(11)

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

Визначено теоретичний сумарний обсяг пам'яті, необхідний для роботи моделюючих процесорів (12).

 (12)

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

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

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

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

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

Експерименти проводилися на комп'ютерах P4 2.4 Ггц. Мережне обладнання - 100 Мбіт. На машинах встановлена операційна система Windows-98 SE. Для комунікації моделюючих процесорів використався Direct 8.0. При проведенні всіх експериментів одному комп'ютеру відповідав рівно один моделюючий процесор. Як приклади були обрані схеми з набору ISCAS-89 і ITC-99.

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

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

Були проведені експерименті на схемі b19 (мікропроцесор 80386) з набору схем ITC-99. Усього схема містить 237 962 елемента. На вхід подавалася випадкова вхідна послідовність, що складається з 1 000 000 подій. Моделювання виконувалося на МодПр із комбінованим протоколом синхронізації. Ступінь оптимізму у всіх досвідах дорівнює 1000 одиниць віртуального часу. Основними критеріями при відображенні системи на граф процесорів було зменшення дисбалансу навантаження та мінімізація числа каналів зв'язку. Схеми відображалися на граф МодПр із однаковими критеріями оптимальності. Лінія “Без циклів” була побудована при моделюванні системи, відображеної на граф процесорів так, що в ньому не було циклів.

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

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

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

6. Інтернет-доступ до мережі моделюючих процесорів для розподіленого логічного моделювання цифрових систем

Розроблений Інтернет-портал розподіленого логічного моделювання для організації віддаленого доступу до обчислювальної мережі для розподіленого моделювання цифрових систем. Портал доступний в Інтернеті за адресою http://sim.1024.info/.

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

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

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

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

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

Висновки

синхронізація мережний процесор моделюючий

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

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

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

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

3) запропонована нова об'єктна модель протоколів синхронізації логічних процесів при розподіленому логічному моделюванні, що дозволяє заміняти протоколи синхронізації без перезапуску моделюючих процесорів. Це дозволяє прискорити моделювання за рахунок використання оптимального протоколу синхронізації з набору наявних протоколів;

4) сформульовані нові критерії оптимальності та розроблений багатокритеріальний алгоритм для оптимального відображення цифрових систем, що моделюються, на граф мережних моделюючих процесорів. Запропонована система критеріїв, яка ураховує ступінь зв'язку, ступінь досяжності, наявність і розміри циклів у графі процесорів, на додаток до існуючих критеріїв оптимальності, які враховують розміри частин схеми й кількість каналів зв'язків між процесорами. Експериментально показано, що урахування цих нових критеріїв приводить до підвищення швидкості моделювання на 15-30%;

5) отримані оцінки обсягу пам'яті для всіх об'єктів системи. Наведені результати аналітичних досліджень можуть бути використані для вибору оптимальних параметрів відображення цифрових систем на граф процесорів і для оптимального налаштування мережних МодПр;

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

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

8) проведене експериментальне дослідження властивостей консервативного й комбінованого протоколів синхронізації процесів при розподіленому моделюванні цифрових систем. Проведено моделювання схем, розмірність яких перебуває в діапазоні від 12 елементів до 237 962 елементів на вхідних послідовностях до 106 подій. У тестах використалися схеми з набору ISCAS'89, ITC'99 і модель мікропроцесора 80386;

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

10) розроблений Інтернет-портал розподіленого логічного моделювання для організації вилученого доступу до мережі моделюючих процесорів. Портал доступний в Інтернеті за адресою http://sim.1024.info/.

Література

1. Ладыженский Ю.В., Попов Ю.В. Интернет-доступ к системе распределённого логического моделирования цифровых устройств // Вісник Інженерної академії України. Випуск 2-3. - Київ: ІАУ, 2006. - C. 50-54.

2. Ладыженский Ю.В., Попов Ю.В. Многокритериальный алгоритм отображения схем цифровых устройств на граф процессоров при распределенном логическом моделировании // Наукові праці Донецького національного технічного університету. Серія: Обчислювальна техніка та автоматизація. Випуск 88 - Донецьк: ДонНТУ, 2005. - C. 175 - 184.

3. Ладыженский Ю.В., Попов Ю.В. Объектно-ориентированная модель протоколов синхронизации при распределенном логическом моделировании цифровых устройств // Наукові праці Донецького национального технічного університету. Серія: Обчислювальна техніка та автоматизація. Випуск 64 - Донецк: Вид-во ДонНТУ, 2003.- C. 212-221.

4. Ладыженский Ю.В., Попов Ю.В. Программная система для исследования протоколов синхронизации при распределенном событийном логическом моделировании // Наукові праці Донецького национального технічного університету. Серія: Обчислювальна техніка та автоматизація. Випуск 74 - Донецк: Вид-во ДонНТУ, 2004.- C. 201 - 209.

5. Ладыженский Ю.В., Попов Ю.В. Система распределённого логического моделирования цифровых устройств с использованием консервативного протокола синхронизации // Наукові праці Донецького національного технічного університету. Серія: інформатика, кібернетика та обчислювальна техніка, випуск 39: - Донецьк: ДонНТУ, 2002. - C. 21-29.

6. Ладыженский Ю.В., Попов Ю.В., Тесленко Г.А. Программная система для распределённого логического моделирования с динамическим протоколом синхронизации // Радіоелектронні і комп'ютерні системи. - Харків: ХАІ, 2007. - № 8 (27). - C. 25-29.

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