Автоматизоване проектування цифрових керуючих пристроїв

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

ОДЕСЬКИЙ НАЦІОНАЛЬНИЙ ПОЛІТЕХНІЧНИЙ УНІВЕРСИТЕТ

Автореферат

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

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

АВТОМАТИЗОВАНЕ ПРОЕКТУВАННЯ ЦИФРОВИХ КЕРУЮЧИХ ПРИСТРОЇВ

Виконав Защелкін Костянтин Вячеславович

Одеса - 2007



АНОТАЦІЯ

автоматизований цифровий апаратний сигнал

Защолкін К.В. Автоматизоване проектування цифрових керуючих пристроїв. - Рукопис.

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

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

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

Ключові слова: цифровий керуючий пристрій, цифровий автомат, граф-схема, математична модель керуючого пристрою, інформаційна технологія проектування.



1. ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

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

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

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

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

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

Відповідно до поставленої мети в дисертації були вирішені наступні задачі:

– виконано аналіз структурної організації САПР ЦКП, а також моделей і методів, що використовуються у процесі автоматизованого проектування ЦКП;

– досліджені моделі керування ЦОС і системами автоматики, а також методи проектування, засновані на їх використанні;

– запропоновано класифікацію моделей керування ЦОС за ознакою міри покриття простору рішень, та визначено місце відомих моделей у цій класифікації;

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

– розроблені моделі високого рівня для ЦКП, орієнтовані на використання в САПР і позбавлені основних недоліків традиційних графових моделей;

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

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

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

Об'єкт дослідження. Процес автоматизованого проектування ЦКП.

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

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

Наукова новизна отриманих результатів полягає в наступному:

– вперше розроблені моделі низького рівня для ЦКП - абстрактні композиційні автомати, які сполучають властивості автоматів Мілі та Мура в часі (СT-автомат) та в часі й просторі виходів (СST-автомат);

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

– дістали подальшого розвитку графові моделі високого рівня для ЦКП, а саме, запропоновані моделі ПГСА (паралельна граф-схема алгоритму) та модифікована ПГСА (яка в роботі отримала назву “ГВ-ГСА”), які відрізняються від традиційних моделей видом відношення суміжності вершин, правилами визначення позицій змінної стану, способами формування значень змінної стану та вихідних сигналів ЦКП;

– вперше розроблено методи синтезу ЦКП за його описом у вигляді ПГСА та модифікованої ПГСА, які засновані на переході до векторного композиційного СST-автомата з подальшим застосуванням до нього метода структурного синтезу;

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

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

Використання модифікованої ПГСА як моделі високого рівня, мікропрограмного CST-автомата як моделі низького рівня та методу синтезу на їх основі в САПР ЦКП, дозволило в середньому: на 14% зменшити час синтезу; на 40% зменшити розмірність опису ЦКП; на 8% зменшити апаратну складність ЦКП та на 5,5% підвищити продуктивність системи ЦКП - об'єкт керування (ОК) в порівнянні з результатами використання традиційних моделей та методів. Застосування запропонованих модифікацій методу квадратичного кодування, дозволило зменшити складність апаратної реалізації функції переходів ЦКП на 9%.

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

Теоретичні положення та програмне забезпечення, отримані в рамках дисертаційних досліджень, впроваджені в навчальний процес кафедри “Комп'ютерні інтелектуальні системи та мережі” Одеського національного політехнічного університету.

Особистий внесок здобувача полягає в дослідженні існуючих й розробці та розвитку нових моделей, методів і засобів автоматизованого проектування цифрових керуючих пристроїв з жорсткою логікою. Дисертант розробив нові математичні моделі ЦКП та на їх основі запропонував методи, призначені для використання в САПР, довів їх до рівня програмної реалізації і впровадження у виробництво, а також в навчальний процес. Автором запропоновано: класифікацію моделей керування ЦОС за критерієм якості покриття простору рішень [2, 10]; моделі низького рівня для ЦКП - композиційні CT і CST автомати [4, 11]; графові моделі високого рівня для ЦКП і методи їх синтезу [3, 12]; підходи до побудови САПР ЦКП на основі графових моделей [1, 6, 8]; модифікацію методу квадратичного кодування станів цифрового автомата [9].

2. ОСНОВНИЙ ЗМІСТ РОБОТИ

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

У першому розділі проведено аналіз структурної організації САПР ЦКП, а також моделей і методів, які використовуються в процесі автоматизованого проектування ЦКП (рис. 1). Відзначено, що методи синтезу ЦКП використовують у якості вхідних даних два типи моделей: моделі високого рівня, які є вихідним описом ЦКП, і моделі низького рівня, що безпосередньо втілюються в апаратну реалізацію. Методи синтезу виконують переклад опису ЦКП з моделей високого рівня у низькорівневі моделі й далі в системи булевих рівнянь, які визначають логічну схему пристрою, що проектується. Фізична реалізація пристрою виконується за рахунок використання опису систем булевих рівнянь у термінах мов опису апаратних засобів (Hardware Description Language - HDL).

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

Використання в САПР ЦКП, графових моделей високого рівня, заснованих на моделі ГСА, пов'язано з рядом проблем.

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

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

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

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

У другому розділі запропоновані моделі низького рівня для ЦКП з затримкою реакції, яка змінюється в часі - абстрактні композиційні автомати. Вони дозволяють сполучати властивості автоматів Мілі та Мура в часі (СT-автомат) та в часі й просторі виходів (СST-автомат). Показано, що композиційні автомати є самостійним класом абстрактних автоматів, а автомати Мілі, Мура та С-автомати являють собою їхні окремі випадки.

Композиційний CT-автомат визначається як кортеж з п'яти компонентів:

S_CT = A, X, Y, , ,

A= A₁A₂

множина (алфавіт) внутрішніх станів автомата (A₁A₂=);

A₁, A₂ - непусті множини станів типу 1 та 2, відповідно. В станах aA₁ та aA₂ автомат S_CT веде себе як автомат Мілі та Мура відповідно;

X = {x₁, x₂,…, x_f} та Y = {y₁,y₂,…,y_g} - множини станів входу та виходу, відповідно (вхідний та вихідний алфавіти);

- функція переходів, що реалізує відображення деякої множини D AX в A;

₁ - функція виходу, що реалізує відображення деякої множини в Y;

₂ - функція виходу, що реалізує відображення деякої множини в Y.

Оскільки СT-автомат у стані aA₁ веде себе як автомат Мілі, а в стані aA₂ - як автомат Мура, то A₁ і A₂ будуть називатися, множеною станів автоматів Мілі та Мура, відповідно.

Доведено наступні теореми.

Теорема 1. Для композиційного CT-автомата не існує рівносильного автомата Мілі.

Теорема 2. Для композиційного CT-автомата не існує рівносильного автомата Мура.

Визначено композиційний CST-автомат із двома виходами. Ця модель поширена на випадок довільної кількості виходів. Векторний CST-автомат з n виходами визначається як кортеж з шести компонентів:



= A, C, X, Y, , Л,

A=

множина внутрішніх станів, A_j A_k= для будь-яких A_j и A_k при jk;

С - двійкова утворююча матриця (УМ) розмірністю n2ⁿ виду С, C₁ - матриця розмірністю n2 у якій перший стовпець містить нульові, а другий одиничні значення, C₂ - матриця розмірністю n(2ⁿ-2), стовпці якої містять всі можливі різні двійкові комбінації відмінні від стовпців матриці C₁. УМ - це матриця, яка описує поведінку композиційного автомата на різних етапах його функціонування. Число рядків УМ дорівнює кількості виходів автомата. Число стовпців дорівнює кількості підмножин A_i, на які розбитий внутрішній алфавіт автомата. Кожний стовпець УМ значеннями своїх компонентів визначає тип виходу (“0” - вихід типу Мілі, “1” - вихід типу Мура) при приналежності поточного стану автомата тій або іншій підмножині A_i; X = {X₁, X₂,…, X_m} та Y = {Y₁, Y₂,…, Y_n} - множини, елементами яких є множини станів входів та виходів, відповідно; - функція переходів, що реалізує відображення деякої множини D в A, де D AD_X, D_X T, де T={t | tP(X₁X₂…X_m) та t{x_i,}{x_i,}, i=1..m }, P - операція отримання булеану.

Множина T містить елементи булеану множини X₁X₂…X_m, за винятком тих елементів, які одночасно містять елемент вхідного алфавіту та його інверсію.



та операції над матрицею C та множиною A.

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

D_X

чи деякої множини

* Y_i.

Якщо значення i-того виходу CST-автомата визначається в даний момент часу функцією виходу , то цей вихід є виходом типу Мілі, якщо функцією , то цей вихід у даний момент часу є вихід типу Мура.

Кількість підмножин A_i, на які розбивається внутрішній алфавіт CST-автомата з n виходами, дорівнює M=2ⁿ. Число різних моделей автоматів з n-компонентним векторним виходом, які можливо одержати на основі такої розбивки (шляхом виродження деяких підмножин A_i), дорівнює K=-1 (рис. 2). З них K_CST = K - 2ⁿ -1 моделей належать до класу композиційних CST-автоматів (у тому числі, модель у якій всі множини A_i непусті - повний CST-автомат, та інші K_CST -1 моделей, що є його окремими випадками - часткові CST-автомати).

Вводяться наступні позначення. та - непересічні множини вихідних сигналів CST-автомата, що мають місце у момент часу t на виходах, типу Мура й Мілі відповідно. та - непересічні множини вихідних сигналів на виходах типу Мура та Мілі, відповідно, у даний момент часу рівних логічній одиниці.

Дістав подальшого розвитку канонічний метод структурного синтезу (КМСС) АА, шляхом його адаптації до задач синтезу CST-автомата з двома виходами та CST-автомата з довільною кількістю виходів.

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

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

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

y_h = A₁ A₂ … A_g N₁ N₂ … N_s,

де A_q - поточний стан, якому відповідає (входить в один рядок структурної таблиці) вихідний сигнал ; N_q кон'юнкція виду a_iX_j, у якій a_i - поточний стан та X_j - множина умов переходу із цього стану, що відповідають сигналу .

У третьому розділі запропоновані графові моделі високого рівня для ЦКП, які призначені для використання в процесі автоматизованого проектування, а також методи синтезу засновані на цих моделях.

Запропонована модель - ПГСА та заснований на ній метод синтезу ЦКП. Модель ПГСА має кращі характеристики за ознакою міри покриття простору рішень ніж традиційні моделі і дозволяє відмовитися від введення порожніх вершин при певних функціональних залежностях між логічними умовами та мікроопераціями.

Модель ПГСА дістала подальший розвиток у вигляді модифікованої ПГСА, яка дозволяє: роздільно описувати функції переходів і виходів, що дає можливість зменшити час синтезу та розмірність опису пристрою; використовувати механізми прямої та непрямої зміни стану пам'яті ЦКП, що дає можливість балансувати обсяг апаратного забезпечення між ЦКП та ОАё а також залучати обчислювальні ресурсі ОА для задач організації керування.

Модифікована ПГСА - визначається як 11-ти компонентний кортеж

G = (V, Г, X, Y, F, R, P, L_X, L_Y, L_R, L_P),

V =V_X V_Y V_R V_P{v_B, v_E}



множина вершин модифікованої ПГСА; V_X, V_Y, v_B, v_E - множини логічних та операторних вершин, початкова та кінцева вершини, відповідно, аналогічні однойменним вершинам ГСА; V_R - множина операторних вершин керування; V_P - множина вершин позицій;

Г - відношення суміжності на множині V;

X та Y - множина логічних умов та мікрооперацій, відповідно;

FP - змінна стану (фішка), визначена на множині констант P та доступна ОА;

R - множина мікрооперацій, що мають на змістовному рівні вигляд:

F_t+1 := f(F_t, W),

де F_t та F_t+1 - значення фішки у поточний та наступний момент часу, відповідно; f - деяка функція, що залежить від поточного значення фішки і змінних W ОА;

P N₀ - непуста множина цілих констант, що відмічають вершини V_P, v_B, v_E;

Опис ЦКП на основі модифікованої ПГСА являє собою орієнтований (не обов'язково зв'язаний) граф, що має одну початкову (v_B) та можливо одну кінцеву вершину (v_E).

Вершина позиції v_PV_P це вершина в якій може перебувати фішка. У будь-який момент дискретного часу, фішка може перебувати тільки в одній вершині позиції. Кожна вершина vV_P {v_B, v_E} повинна бути відмічена підмножиною множини констант P. Кожна константа відмічає тільки одну вершину v_PV_P чи пару вершин {v_B, v_E}.

Активний шлях фішки (АШФ) - це такий спрямований шлях між вершиною позиції v_iV_Pv_B, у якій перебуває фішка в поточний момент часу t і вершиною позиції v_jV_Pv_E, у якій фішка повинна перебувати в момент часу t+1. АШФ може бути заданий явно або за умовчуванням. Допускаються два способи явного завдання АШФ - прямий та непрямий. При прямому способі завдання, вершини v_i та v_j зв'язані за допомогою послідовності дуг, що виходять з вершини v_i, проходить через вершини логічних умов і входять у вершину v_j. При непрямому завданні, перехід фішки з вершини v_i у вершину v_j визначений єдиною операторною вершиною vV_R, яка містить мікрооперацію rR та лежить наприкінці шляху, що виходить з вершини v_i. Активні шляхи задані коректно, якщо при будь-якому припустимому наборі значень логічних умов X(t) модифікована ПГСА має один явно заданий АШФ, або не має такого. В останньому випадку АШФ заданий за умовчуванням, при цьому F(t+1) = F(t).

Активні шляхи ініціалізації (АШІ) - це множина спрямованих, не циклічних шляхів, що виходять з вершини позиції vV_Pv_B, у якій перебуває фішка в даний момент часу, не проходять через інші вершини позицій і завершуються вершинами з множини V_Y. АШІ, які містять та не містять умовні вершини, називаються умовними та безумовними АШІ, відповідно. Безумовною частиною умовного АШІ називається та його частина, що перебуває між вихідною вершиною позицією АШІ і найближчої до неї умовною вершиною (включаючи умовну вершину). Умовна частина АШІ являє собою його доповнення до безумовної частини.

Виконання модифікованої ПГСА - це процес дискретного переміщення фішки F з вершини початкової позиції v_B у вершину кінцевої позиції v_E (чи в v_B) по деякому шляху, який складається з фрагментів, що є АШФ для кожної вершини позиції, та супроводжується ініціалізацією умовних і операторних вершин, що перебувають на АШІ.

Таким чином, АШФ визначають переходи фішки по графу, а АШІ - функцію виходу в кожній позиції розміщення фішки. Підграф переходів фішки G_П - це підграф модифікованої ПГСА, що включає всі можливі АШФ. Підграф виходів G_В - ациклічний підграф, що включає всі можливі АШІ.

Припустиму топологію графа модифікованої ПГСА визначає відношення суміжності Г. Його основні властивості полягають у наступному: образ кожного елемента з множин V_Y, V_X, V_P та {v_B} в цьому відношенні може містити будь-яке, відмінне від нуля, число елементів; вершини V_X, V_P, v_B не можуть бути кінцевими вершинами графа; множина образів вершин V_R і v_E у відношенні Г, порожня; операторній або умовній вершині повинні передувати вершини; вершині позиції чи кінцевій вершині може не передувати жодна вершина.

Довільний граф модифікованої ПГСА G має еквівалентний за результатом виконання граф G', кількість операторних вершин в якому не перевищує |Y |+|R|. Подання модифікованої ПГСА у вигляді графа G' буде називатися структурованим поданням (СП). У роботі запропонована методика перетворення довільного графа G до СП. У СП множина умовних вершин складається із трьох попарно непересічних підмножин V_X=V_X1V_X2V_X3, причому V_X1V_X2 G_В, V_X1V_X3 G_П (рис. 3).

У графі СП G' переходи фішки до вершин позицій, позначених множинами констант P₁…P_i, задані у непрямий спосіб за допомогою операторних вершин V_R. Переходи до вершин позицій P_i+1…P_k та кінцевої/початкової вершини задані у прямий спосіб за допомогою дуг, що входять у ці вершини. У граничних випадках переходи в усі вершини позиції та у кінцеву вершину можуть бути задані тільки у непрямий спосіб або навпроти винятково прямо.

Позначення вершини v_iV_P v_E множиною констант P_i P, що має потужність |P_i|>1, дозволяє за допомогою однієї мікрооперації rR виконати переходи: з різних вершин множини V_P v_B у вершину v_i; з вершини v_i в різні вершини множини V_P v_E.

В роботі запропоновано методи структурного синтезу ЦКП за його описом у вигляді ПГСА та модифікованої ПГСА. Методи засновані на переході від високорівневого графового опису ЦКП до мікропрограмного CST-автомата (перший етап) та виконанні структурного синтезу отриманого автомата (другий етап).

Перший етап методу синтезу ЦКП за його описом у вигляді модифікованої ПГСА містить тринадцять дій. Перша дія етапу виконує зіставлення множини вершин позицій ПГСА та множини вершин графа CST-автомата. Друга дія виконує зіставлення множини констант, що позначають вершини позицій ПГСА та множини станів CST-автомата. У межах третьої дії виконується зіставлення множини станів CST-автомата та множини вершин його графа. Четверта та п'ята дії ставлять у відповідність АШФ ПГСА, які задані явно, прямим способом та за умовчуванням, дуги графа CST-автомата. Шоста та сьома дії ставлять у відповідність логічним умовам ПГСА вхідні алфавіти, а мікроопераціям ПГСА - вихідні алфавіти CST-автомата. Восьма дія мікроопераціям r_kR ПГСА ставить у відповідність вихідні алфавіти

відповідних виходів CST-автомата. У межах дев'ятої дії виконується розмітка дуг графа CST-автомата елементами вхідних алфавітів, що відповідають логічним умовам ПГСА, записаним в умовних вершинах, через які проходять АШФ задані явно прямим способом та за умовчуванням. Десята дія виконує розмітку вершин графа CST-автомата мікроопераціями, записаними в операторних вершинах, які перебувають на безумовних АШІ ПГСА. Одинадцята дія виконує розмітку вершин графа CST-автомата парами позначок (, ), де другі компоненти кожної пари - це мікрооперації, які записані в операторних вершинах, розміщених на умовних частинах всіх АШІ, що виходять з вершин позицій, а перші компоненти пар - це множини логічних умов, записаних в умовних вершинах, що передують зазначеним операторним вершинам. Дванадцята дія виконує взаємне впорядкування позначок дуг та вершин графа CST-автомата. Тринадцята дія додає до множини входів CST-автомата додатковий вхід за допомогою якого виконується запуск виконання ПГСА.

Другий етап методу полягає у виконанні структурного синтезу CST-автомата, отриманого на першому етапі. Даний етап виконується відповідно до методу синтезу мікропрограмного CST-автомата, який запропоновано у другому розділі дисертації.

Проведено експерименти над програмними реалізаціями запропонованих методів та виконано зіставлення отриманих результатів з результатами використання традиційних методів. Матеріалом для експериментів виступили описи ЦКП (представлені у вигляді моделей високого рівня), отримані за допомогою розробленої програми-генератора. До даних описів були застосовані запропоновані та традиційні методи синтезу. У ході експериментів досліджувалися наступні характеристики: час синтезу, розмірність опису ЦКП, апаратна складність ЦКП, продуктивність системи ЦКП-ОК Експерименти показали ефективність застосування запропонованих моделей і методів у сенсі цілей дисертаційної роботи.

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

Завдання квадратичного кодування полягає в мінімізації цільової функції:

,

де - метрика Хеммінгу між кодами станів k-того переходу, p - кількість переходів між станами ЦА. Ефективність квадратичного кодування чисельно оцінюють коефіцієнтом ефективності

k_ЭФ=W/p.

Одним з найбільш використовуваних на практиці приблизних методів квадратичного кодування, є так званий евристичний метод (ЕМ). Він дозволяє значно скоротити перебір за рахунок вибору з множини кодових комбінацій (КК) підмножини “бажаних КК” (ПБКК) та зводе процес мінімізації функції W до мінімізації оцінних функцій ц_i, які обчислюються на кожному кроці. При цьому, на кожному кроці ЕМ виконується кодування чергового стану, для цього формується ПБКК, із якого вибирається “найкраща” КК, така, для якої ц_i має найменше значення.

У роботі було проведене дослідження ЕМ, в результаті чого виявлено два фактори, що знижують його ефективність.

Фактор 1. Оцінна функція ц_i на деяких кроках методу може приймати мінімальне значення для декількох КК з ПБКК. Для такого випадку ЕМ не передбачає ніякого конструктивного критерію вибору найкращої КК. Виникнення подібних ситуацій знижує ефективність ЕМ через те, що вибір різних КК із рівними ц_i істотно впливає на значення функції W.

Фактор 2. Для виявлення другого фактора, проведене експериментальне дослідження залежності k_ЭФ традиційного ЕМ від кількості станів (D). Розмірність T КК є деякою функцією T = f(D). Кількість можливих КК розмірності T дорівнює

t = 2^T * 2 ^f(D).

Свободою кодування буде називатися відношення кількості можливих КК до кількості станів автомата, які потрібно закодувати:

F(D) = t/D * 2^T/D * 2 ^f(D)/D.

Лівою околицею точки x₀ буде називатися інтервал (x₀-е, x₀], при е > 0 (е, x₀N).

В дисертації був проведений аналіз функції F(D) та її зіставлення з поведінкою функції k_ЭФ(D). У результаті цього, другим фактором, що знижує ефективність квадратичного кодування, була визначена низька свобода кодування при D, що приймає значення з лівої околиці цілого ступеня двійки.

З метою зменшення негативного впливу першого фактора, в роботі запропоновано чотири модифікації ЕМ (ЕМ1 - ЕМ4). Нехай K={K₁, … , K_t} - множина усіляких КК розмірності T; A={a₁, …, a_D} - множина станів автомата, які потрібно закодувати; t = 2^T, D ? t. Задача ЕМ полягає у однозначному зіставленні L_K: AKA, множині A, множини кодів станів КА={ka_i | ka_iK}. На нульовому кроці традиційного ЕМ кодуються одразу два стани, обрані за визначеними правилами. На i-му кроці ЕМ кодується черговий незакодований раніше стан a^Н. Для цього за правилами ЕМ з множини ще незакодованих КК K^НЗK вибирається ПБКК K^ЖK^НЗ. Для всіх КК, що входять до K^Ж={, , … , } за правилами ЕМ, підраховуються значення оцінних функцій ={ц₁, ц₂, … , ц_p}. Після цього, за наступним правилом, виконується кодування стану a^Н, якщо ц_j = min(), то L_K(a^Н) =.

ЕМ передбачає, що у випадку, якщо мінімальне значення мають оцінні функції для декількох КК із K^Ж (надалі цей випадок буде називатися “спеціальною ситуацією”), то для кодування на поточному кроці необхідно вибрати першу з цих КК.

Модифікація 1 (ЕМ1). Пропонується вирішення задачі розвитку ЕМ шляхом використанням методу Монте-Карло, аналогічно тому, як це робиться для рішення задачі комівояжера. Виконується традиційний ЕМ, для якого правило розв'язання “спеціальної ситуації”.

Це означає, що якщо на i-му кроці ЕМ, виникає “спеціальна ситуація”, тобто мінімум на множині міститься в декількох її елементах, то випадковим образом вибирається одна із КК, що відповідає цим мінімумам. Після завершення кодування, підраховується значення k_ЭФ. Результати кодування запам'ятовуються у вигляді двох елементів: значення k_ЭФ та множина кодів КА. Процедура кодування повторюється задане число раз N. Якщо знову отримані, на черговому кроці, результати кодування КА мають менший k_ЭФ, то вони запам'ятовуються замість попередніх результатів.

Модифікація 2 (ЕМ2). Пропонується вирішення задачі розвитку ЕМ шляхом використанням методу обмеженого пошуку в ширину. Задається параметр пошуку - ціле число R = 0…(D-2). Виконується традиційний ЕМ, для якого правило розв'язання “спеціальної ситуації” формулюється в наступному вигляді:

Правило (4) означає, що якщо на i-му кроці ЕМ виникає “спеціальна ситуація” =min(), то формується стільки варіантів процедури кодування стану a^Н, скільки є мінімальних значень у множині . Подальші кроки виконуються з урахуванням всіх отриманих на даному кроці варіантів кодування. Правило (3) означає, що правило (4) застосовується для розв'язання “спеціальної ситуації” тільки на обмеженій кількості початкових кроків.

Така процедура призводить до одержання дерева рішень. Гілкам цього дерева на кожному кроці присвоюються КК з множини {, ,…, }. Альтернативні множини результатів кодування КА₁, КА₂, … , КА_h отримуються як послідовності КК, що зустрічаються на шляху від кореня до кожної з кінцевих вершин дерева. Для кожної з множин КА₁, КА₂, …, КА_h підраховується k_ЭФ. У якості остаточного результату кодування, обирається будь-яка множина КА_i, що має найменший k_ЭФ.

Модифікація 3 (ЕМ3). Запропоновано подальший розвиток ЕМ на основі спільного застосування ЕМ1 та ЕМ2. До ЦА застосовується ЕМ2, результатом цього є множина кодів КА_min, яка складається з двох непересічних підмножин КА_min=КА₄КА₁, де КА₄ і КА₁ - підмножини КК отриманих за правилами (4) та (1), що входить до ЕМ2, відповідно. Задається параметр N і до станів, що кодуються на лінійному ланцюжку вершин дерева рішень, підмножиною кодів КА₁ застосовується ЕМ1.

Модифікація 4 (ЕМ4). Запропоновано подальший розвиток ЕМ за рахунок модифікації ЕМ3. При виконанні ЕМ3 обирається будь-яка підмножина KA, що має найменше значення k_ЭФ. Якщо таких підмножин декілька, то до кожної з них можна застосувати етапи ЕМ3 і вибрати кращий результат. Для керування процесом кодування пропонується параметр 1 ? H ? u, що визначає кількість підмножин КА, до яких застосовується ЕМ4.

З метою зменшення негативного впливу другого фактора, запропонована п'ята модифікація ЕМ (ЕМ5). Завдання усунення впливу другого фактора може бути вирішена шляхом штучного збільшення розмірності КК. Таке збільшення розмірності КК на одиницю призводить до: збільшення простору рішень задачі кодування (множини можливих КК) у два рази; збільшення пам'яті автомата на один елемент та можливо додатковим витратам апаратури. Перший із зазначених наслідків, збільшення розмірності КК, може послужити поліпшенню результатів кодування, а отже зменшенню апаратних витрат на реалізацію ЦА. Другий наслідок призводить до безумовного збільшення апаратних витрат. Рішення задачі кодування при цьому полягає в знаходженні компромісу між результатами даних двох наслідків введення штучної надмірності в розмірності КК.

Модифікація 5 (ЭМ5) полягає в наступному. Виконується кодування одним з ЕМ - (ЕМ…ЕМ4). Результатом кодування є три компоненти: KA - множина кодів станів; k_ЭФ; ціна за Квайном C для системи булевих рівнянь, що реалізують функції збудження елементів пам'яті ЦА. Задається C_П - ціна за Квайном елемента пам'яті та E[0, 1] - дійсний параметр, що визначає поріг кількості станів, починаючи з якого свобода кодування вважається “недостатньою” для ефективного кодування. Зазначений поріг обчислюється за формулою:

П = ОК(D) - {[ОК(D)]•E + 1}

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

Якщо D < П, то кодування припиняється і як остаточний результат приймається отримана множина кодів, тому що, для даного D, при заданому порозі вважається, що, свобода кодування має “достатню” величину і її збільшення не приведе до підвищення ефективності кодування. Інакше у КК вноситься надмірність, шляхом збільшення їх розмірності на один розряд і процедура кодування повторюється. Якщо сума знов отриманої ціни C та ціни C_П менша за ціну отриману до внесення надмірності, то збільшення свободи кодування дало позитивний результат і робиться спроба подальшого її збільшення.

У роботі проведено експерименти над програмними реалізаціями запропонованих модифікацій ЕМ і виконані зіставлення отриманих результатів з результатами традиційного ЕМ. Експерименти полягали в кодуванні автоматів, що розрізняються: числом станів, видами графів, призначенням. Експерименти показали доцільність застосування запропонованих модифікацій в процесі синтезу ЦКП. Узагальнені результати експериментів представлені в таблиці.

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

Запропонована технологія втілена в САПР ЦКП, результатом функціонування якої є опис пристрою на одній з мов опису апаратури: VHDL, Verilog, AlteraHDL. Ці результати обробляються з залученням програмного забезпечення сторонніх виробників (універсальних САПР цифрових систем), що дозволяє виконати моделювання синтез та імплементацію ЦКП у ВІС. Виконано опис структури розробленої САПР, її вхідної мови, форматів вхідних та проміжних файлів, структури вихідного HDL-проекту.



ВИСНОВКИ

1. В результаті виконання аналізу структурної організації САПР ЦКП, а також моделей і методів, які застосовуються у процесі автоматизованого проектування ЦКП встановлено, що зазначені методи використовують у якості вхідних даних моделі двох типів: високого та низького рівнів. Визначено, що моделі низького рівня не дозволяють адекватно описувати поведінку ЦКП з урахуванням динаміки його реакції, а моделі високого рівня мають структурну надмірність та обумовлюють необхідність виконання додаткових заходів для забезпечення еквівалентності з моделями низького рівня. Це призводить до підвищення часової складності процесу синтезу, збільшення апаратної складності ЦКП та погіршення продуктивності системи ЦКП - ОК.

2. Для усунення недоліків САПР ЦКП, пов'язаних з використанням традиційних моделей низького рівня, запропоновані нові моделі - абстрактні композиційні автомати, які дозволяють описувати поведінку ЦКП з урахуванням динаміки його реакції, що досягається сполученням властивостей автоматів Мілі та Мура в часі (СТ-автомат) та в часі й просторі виходів ЦКП (СSТ-автомат).

3. Для усунення недоліків САПР ЦКП, пов'язаних з використанням традиційних моделей високого рівня, в роботі запропоновані моделі: ПГСА та модифікована ПГСА. Використання цих моделей дозволяє зменшити часову складність синтезу ЦКП за рахунок можливості роздільного опису його функцій переходів та виходів, знизити апаратну складність ЦКП та збільшити продуктивність системи ЦКП - ОК за рахунок забезпечення однозначної відповідності моделям низького рівня.

4. На основі використання запропонованих моделей, розроблені нові ефективні методи синтезу, які засновані на переході від опису ЦКП у вигляді ПГСА чи модифікованої ПГСА до композиційного СSТ-автомата з подальшим застосуванням до нього метода структурного синтезу. Практичним ефектом використання цих методів у САПР ЦКП є зменшення в середньому: часу синтезу на 14%, розмірності опису ЦКП на 40%, апаратної складності ЦКП на 8%; та підвищення продуктивності системи ЦКП-ОК в середньому на 5,5%.

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

6. Розроблено ІТАП ЦКП, яка об'єднала використання запропонованих та традиційних моделей, методів та методик в єдиний формалізований процес, спрямований на підвищення ефективності автоматизованого проектування. На основі ІТАП створена САПР, яка була використана для проектування ЦКП різного функціонального призначення.

7. Розроблені інформаційна технологія та САПР впроваджені на виробничо-комерційному підприємстві “Телекарт - прилад” (м. Одеса) і використовуються там при проектуванні керуючих пристроїв для цифрових телекомунікаційних систем. Отримані в дисертаційній роботі теоретичні результати та САПР ЦКП впроваджені в навчальний процес Одеського національного політехнічного університету.



СПИСОК ОПУБЛІКОВАНИХ РОБІТ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

Николенко А.А. Алгоритмические особенности автоматизированного проектирования микропрограммных автоматов / Николенко А.А., Ковалев Ю.А., Защелкин К.В. // Електромашинобудування та електрообладнання. - Київ. - 2000. - Вып. 54. - С. 91 - 95.

Полин Е.Л. Классификация моделей параллельных вычислительных процессов по признакам ширины и общности / Полин Е.Л., Защелкин К.В. // Тр. Одес. политехн. ун-та. - Одесса. -2004. - Вып. 1(21). - С. 102 - 107.

Полин Е.Л. Параллельная модель языка граф-схем алгоритмов и ее интерпретация абстрактными автоматами / Полин Е.Л., Защелкин К.В. // Електромашинобудування та електрообладнання. - Київ. - 2005. - Вып. 65. - С. 70 - 79.

Полин Е.Л. Абстрактные композиционные автоматы / Полин Е.Л., Защелкин К.В. // Тр. Одес. политехн. ун-та. - Одесса. - 2006. - Вып. 1(25). - С. 88 - 94.

Защелкин К.В. Повышение эффективности квадратичного кодирования состояний цифрового автомата // Холодильная техника и технология. - Одесса. - 2007. - Вып. 2(106). - С. 86 - 93.

Николенко А.А. Лингвистическое и алгоритмическое обеспечение автоматизированного проектирования микропрограммных автоматов / Николенко А.А., Ковалев Ю.А., Защелкин К.В. // Перспективи. - Одеса. -1999. - №1(5). -С. 177 - 182.

Защелкин К.В. Параллельная модель языка граф - схем алгоритмов и ее интерпретация абстрактными автоматами // Тр. Междунар. конф. “Физические и компьютерные технологии в народном хозяйстве”. - Харьков. - 2000. - С. 536 - 539.

Ковалев Ю.А. О подходе к автоматизации проектирования и моделирования микропрограммных управляющих автоматов / Ковалев Ю.А., Защелкин К.В. // Тр. Всеукр. конф. “Комп'ютерне моделювання та інформаційні технології в науці, економіці та освіті”. - Кривий Ріг. -2001. - С. 127 - 133.

Николенко А.А. Модификация эвристического алгоритма кодирования состояний конечного автомата / Николенко А.А., Защелкин К.В. // Тр. Междунар. конф. “СИЭТ - 2002”. - Одесса. - 2002. - С. 128.

...