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

Анотація наукової статті з комп'ютерних та інформаційних наук, автор наукової роботи - Лебедєв Борис Костянтинович, вінцем Микола Миколайович


ADAPTIVE MANAGEMENT INFORMATION FLOW DISTRIBUTED CAD VLSI

In work is presented adaptive algorithm, control process of the shaping the current route of the issue design given in distributed CAD. The key component of the algorithm, have charge of production of the decisions, are an automatons to adaptation and method to ants colony


Область наук:
  • Комп'ютер та інформатика
  • Рік видавництва: 2009
    Журнал: Известия Південного федерального університету. Технічні науки

    Наукова стаття на тему 'Адаптивне управління інформаційними потоками розподіленої САПР НВІС'

    Текст наукової роботи на тему «Адаптивне управління інформаційними потоками розподіленої САПР НВІС»

    ?Розділ II. Автоматизація проектування

    УДК 681.31

    Б.К. Лебедєв, М.М. Вінців АДАПТИВНЕ управління інформаційними потоками розподілу САПР НВІС *

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

    Управління даними; оптимізація; автомати адаптації; мурашині алгоритми.

    B.K. Lebedev, N.N. Vencov

    ADAPTIVE MANAGEMENT INFORMATION FLOW DISTRIBUTED

    CAD VLSI

    In work is presented adaptive algorithm, control process of the shaping the current route of the issue design given in distributed CAD. The key component of the algorithm, have charge of production of the decisions, are an automatons to adaptation and method to ants colony.

    Management data; optimization; automatons to adaptation; ants algorithms.

    Вступ. Розбиття вихідної проектної задачі дозволяє організувати паралельне рішення отриманих підзадач засобами розподілених САПР (РСАПР). В процесі реалізації запитів до віддалених вузлів виникає завдання адаптивного управління вибором маршруту передачі проектних даних. Необхідність адаптивного управління обумовлена ​​відсутністю єдиного теоретичного підходу до прогнозування мережевого трафіку [1], і, як наслідок, непередбачуваними змінами пропускних спроможностей каналів передачі даних. Розробляються в даний час для стандартних телекомунікаційних систем підходи до адаптивного управління маршрутами передачі даних не в повній мірі прийнятні для РСАПР. Наприклад, представлений в [2,3] алгоритм апостеріорної К-потокової маршрутизації передбачає планування в кожному вузлі маршруту, починаючи з вузла джерела, К>2 оптимальних (субоптимальних) маршрутів передачі даних до вузла одержувачу, тобто вимагає надання обчислювальних ресурсів кожним вузлом, що входять в маршрут. Вузли РСАПР, крім завдань телекомунікаційного характеру, вирішують ресурсомісткі проектні завдання. З цієї причини необхідно розробити адаптивний алгоритм маршрутизації, що вимагає мінімум обчислювальних ресурсів [4].

    Формулювання завдання. Як динамічну систему обміну даними РСАПР можна уявити графом

    G (t) = G (A (t), R (t), W (t)), (1)

    * Робота виконана за підтримки: РФФД (гранти № 10-07-90017, № 09-01-00509), г / б № 2.1.2.1652.

    де А - безліч вершин графа (комп'ютери-вузли РСАПР); R - безліч ребер графа (канали зв'язку); W - ваги ребер (параметри каналів зв'язку).

    Кожному ребру rij? R, що з'єднує вершини ai? A і aj? A, відповідають дві характеристики wij - максимально можлива пропускна здатність і wij (t) - пропускна здатність момент часу t. Елементи wij (t) (i, j = 1,2, ... | A |)

    У

    утворюють матрицю W (t) розмірності | А | Л | А |, де | А | - число вершин в графі описує пропускну здатність каналів зв'язку РСАПР в момент часу t. Маршруту Lip, по якому передаються дані від вершини ai? A (вузла-відправника) до вершини ap? A (вузлу-одержувачу), також відповідають дві характеристики P (Lip) - максимальна пропускна здатність маршруту і P (Lip (t)) - пропускна здатність маршруту в момент часу t. Під максимальною пропускною здатністю розуміється швидкість передачі даних відносяться до розв'язуваної задачі при монопольному доступі до відповідних каналів зв'язку. Під пропускною спроможністю розуміється швидкість фактичної або можливої ​​передачі даних відносяться до розв'язуваної задачі. Ребро в маршруті з найменшою пропускною здатністю визначає пропускну здатність всього маршруту передачі даних:

    P (Lip (t)) = min {wij (t) 1 e Lp (t)} (2)

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

    дискретизації становить одну секунду), за допомогою двох автоматів адаптації (АА) [5,6]. Рішення про те, який з АА буде активний в даний момент, тобто буде здійснювати вибір реалізованої альтернативи, приймається на основі аналізу стану середовища. Основним є АА, схема якого зображена на рис. 1. У ситуаціях, коли пропускна здатність каналу зв'язку зростає більш, ніж на 40% протягом однієї ітерації, активується АА, схема якого наведена на рис. 2. Застосовувані АА підтримують дві альтернативи:

    | А1 - пошук нового маршруту методом мурашиної колонії, з подальшою передачею по ньому даних протягом n тимчасових інтервалів;

    | А2 - передача даних по поточному маршруту протягом n тимчасових інтервалів.

    Д1 А2

    Мал. 2. Схема АА, що реагує на різке зростання пропускної здатності 60

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

    На кожній ітерації виконується чотири кроки:

    1. Стан мережі аналізується в дискретні моменти часу 1г, ..., 1г + п-1,

    і + п, 1, + п + 1, і + п + 2, ..., і + 2п + 1., де 1г + п + 1 - момент початку реалізації поточної альтернативи. Визначаються значення величин Р (Ьр (1г)) Р (Ьгр (1г + п-1)), Р (Ьгр (1г + п)),

    Р (^ 1р (1г + п + 1))> Р (Ьгр (1г + п + 2) '), ---, Р (Ьгр (1г + 2п + 1)') '

    2. На основі аналізу значень Р (Ь, р (1г)), ..., Р (Ь1р (1г + п_1)), Р (Ьгр (1г + п)), Р (Ь, р (1г + п + 1)), Р (Ьгр (і + п + 2)), ~, Р (Ргр (і + 2п + д) приймається рішення про активації необхідного АА, а також вироблення активним АА сигналу заохочення або покарання.

    3. Під дією виробленого сигналу активний АА переходить в новий стан.

    4. Реалізується одна з двох альтернатив А! або А2, відповідна нового стану активного АА.

    Розглянемо правила вироблення керуючих сигналів, які є загальними для використовуваних АА. Якщо АА знаходиться в стані відповідному альтернативі Ль то сигнал заохочення виконується в разі, якщо істинно умова:

    г + п + п + 1 г + п

    «|? Р (ь, «,) >? Р ( «-,)> (3)

    3 = г + п + 1 г = г

    де ь - маршрут, отриманий на попередній ітерації; Ь _ - маршрут, підлозі-

    гр гр

    ченний безпосередньо перед маршрутом Ь; 1 ... 1 - моменти часу, в

    гр г г + п

    які дані передавалися по маршруту Ь (тобто безпосередньо предшест-

    гр

    вующие реалізації альтернативи Ль); 1г + і + 1 ... 1г + і + і + 1 - моменти часу, в які дані передавалися по маршрутуЬ (тобто настали після реалізації

    гр

    альтернативи Ль; а - емпірично визначається коефіцієнт, що дорівнює 0,7-0,9.

    Якщо АА знаходиться в стані, відповідному альтернативі Л2, то сигнал покарання виробляється в разі, якщо істинно умова:

    (Г + п + п + 1 г + п \ (1 г + п + п + 1 Л

    ? Р (Ь (Г)) <в? Р (Ь. (1,) агу Р (Ьр) >-|? Р (Ь (+1 з))

    >г> |> >п І-ЛФ

    \ "3 = г + п + 1 у

    (4)

    де 1г ... 1 - моменти часу безпосередньо передують реалізації

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

    0,7-0,8; у - емпірично визначається коефіцієнт в діапазоні 0,1-0,3.

    Метод мурашиної колонії. При реалізації альтернативи Л1 в якості механізму пошуку оптимального маршруту використовується метод мурашиної колонії. Основна ідея методу полягає в тому, що кожен мураха здійснює пошук маршруту самостійно, але при цьому використовує досвід своїх передує-

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

    Програмної генерації першого мурашки передує створення матриці розподілу феромону Р {к) розмірності | А | Х | А |, де до - кількість мурах, досвід яких врахований при формуванні матриці. На початку роботи мурашиного алгоритму к = 0, елементи матриці ^ (0), визначаються за правилом

    де / ег0 = 0.001.

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

    генерації к-1 мурах.

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

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

    Кількість феромону А / відкладали на ребрах, що входять в маршрут, Рр (() визначається за формулою:

    Випаровування феромона моделюється перерахунком елементів матриці Р (к) за правилом:

    якщо Ту є Я; якщо Ту? Я,

    (5)

    (6)

    де уг до (/) - ймовірність переходу до-го мурашки з вершини аг в суміжну вершину

    ау в момент часу М! у (/) - швидкість передачі даних між суміжними вір-

    шинами а й ау в момент часу і; уу (до _ 1) - рівень феромону на ребрі Ту після

    (7)

    де п = 2..5.

    Матриця Р (к) визначається на основі матриці Р (к-1) за правилом

    (8)

    де у є {1,2, ... | А \}

    ) _ \ FV (к) - 5 | f - ^ Якщо f) - 5 | f - 1 - fer °

    У {.М, якщо fy (к) -5 fy (до -1) < / Егй, (9)

    де 5 - коефіцієнт випаровування феромону (Q.1-Q.3).

    Після того, як розраховані елементи матриці F (k), генерується до + 1 мураха, робота мурашиного алгоритму повторюється до тих пір, поки не буде згенеровано вказану кількість мурах т. Оптимальний маршрут вибирається на основі матриці F (m).

    Висновок. Основними достоїнствами розробленого алгоритму, в порівнянні з алгоритмом апостеріорної К-потокової маршрутизації є:

    | Пошук тільки одного маршруту з'єднує вузол-відправник з вузлом-одержувачем, що зменшує ВСА пропонованого алгоритму;

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

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

    БІБЛІОГРАФІЧНИЙ СПИСОК

    1. Стецько А.А. Автоматизоване проектування обчислювальних мереж великих проектних організацій: Автореф. дис. докт. техн. наук. - Ульяновськ, 2QQ8. - 38 з.

    2. SyrtzevA.V., TimofeevA.V. Neural and Multi-Agent Routing in Telecommunicational Networks.

    - International Journal "Information Theories and Their Applications". - 2QQ3. - Vol. 1Q, №2.

    - P. 167-172.

    3. Курейчик В.В., Курейчик В.М., Родзин С.І. Концепція еволюційних обчислень, інспірованих природними системами // Известия ПФУ. Технічні науки. Тематичний випуск "Інтелектуальні САПР". - 2QQ9. - № 4 (93). - C. 16-24.

    4. Чернишов Ю.О., Белявський П.Г., Полуян А.Ю. Еволюційний підхід до вирішення завдання про призначення через визначення найкоротшого шляху // Известия ПФУ. Технічні науки. Тематичний випуск "Інтелектуальні САПР". - № 9 (86). - С. 18-24.

    5. Курейчик В.М., Лебедєв Б.К., Лебедєв О.Б. Пошукова адаптація: теорія і практика.

    - М .: ФИЗМАТЛИТ, 2QQ6.

    6. Лебедєв Б.К. Методи пошукової адаптації в задачах автоматизованого проектування НВІС: Монографія. - Таганрог: Изд-во ТРТУ, 2QQQ.

    Лебедєв Борис Костянтинович

    Технологічний інститут федерального державного освітнього закладу вищої професійної освіти «Південний федеральний університет» в м Таганрозі.

    E-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її..

    347928, м Таганрог, пров. Некрасовський, 44.

    Тел .: 88634371743.

    Кафедра систем автоматизованого проектування; професор.

    Lebedev Boris Konstantinovich

    Taganrog Institute of Technology - Federal State-Owned Educational Establishment of Higher Vocational Education "Southern Federal University".

    Email: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її..

    44, Nekrasovskiy, Taganrog, 347928, Russia.

    Phone: 88634371743.

    Department of Computer Aided Design; professor.

    Вінців Микола Миколайович

    Ростовська-на-Дону державна академія сільськогосподарського машинобудування (РГАСХМ).

    E-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її..

    344Q23. м Ростов-на-Дону, вул. Країни Рад, 1.

    Тел .: 88632589129.

    Кафедра прикладної математики і обчислювальної техніки; доцент.

    Vencov Nikolay Nikolaevich

    Rostov-on-Don State Agricutural Engineering Academy.

    E-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її..

    1, Strana Sovetov street, Rostov-on-Don, 344Q23, Russia.

    Тел .: 88632589129.

    The applied mathematics and computer facilities: associate professor.

    УДК 645.231.11: 78

    В.В. Янушко, С.Н. Єркін ПОБУДОВА СХЕМИ ПРОЦЕСУ АВТОМАТИЗАЦІЇ ПРОЕКТУВАННЯ ВИРОБИ НА БАЗІ UML (USE CASE) діаграми *

    У статті розглядається процес автоматизації проектування вироби. Наводиться узагальнена схема автоматизації процесу проектування (АПП). На підставі функціональноїеквівалентності наводиться заміна узагальненої схеми АПП на діаграми UML (Use case).

    Процес автоматизації проектування вироби; діаграми UML.

    V.V. Janushko, S.N. Erkin

    CONSTRUCTION OF THE PROCESS AUTOMATION PRODUCT DESIGN BASED ON UML (USE CASE) DIAGRAMS

    This article discusses the process of design automation products. A generalized scheme of the automation design process (AMS). On the basis of functional equivalence provides replacement generalized scheme for AMS diagrams UML (Use case).

    Automation engineering products; UML diagrams

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

    Розглянемо процес автоматизованого проектування радіо електронного обладнання (РЕО), складові елементи якого представлені на рис. 1.

    Вихідним документом для початку проектування є технічне завдання (ТЗ). У ньому перераховані всі технічні вимоги, що пред'являються до створюваної апаратури. До складу основних вимог входять:

    | Значення вихідних характеристик і їх допустимі розкид;

    | Показники надійності: ймовірність безвідмовної роботи, час експлуатації, термін служби та ін .;

    *

    Робота виконана за підтримки: РФФД (гранти №10-01-00115, №10-01-90017), г / б № 2.1.2.1652.


    Ключові слова: УПРАВЛІННЯ ДАНИМИ / ОПТИМІЗАЦІЯ / АВТОМАТИ АДАПТАЦІЇ / мурашиний алгоритм / MANAGEMENT DATA / OPTIMIZATION / AUTOMATONS TO ADAPTATION / ANTS ALGORITHMS

    Завантажити оригінал статті:

    Завантажити