ОДЕССКИЙ НАЦИОНАЛЬНЫЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
ОДЕСЬКИЙ НАЦІОНАЛЬНИЙ ПОЛІТЕХНІЧНИЙ УНІВЕРСИТЕТ
ЗАЩОЛКІН Костянтин Вячеславович
УДК 004.312.4:519.713.1
МОДЕЛІ, МЕТОДИ ТА ІНСТРУМЕНТАЛЬНІ ЗАСОБИ
ДЛЯ АВТОМАТИЗОВАНОГО ПРОЕКТУВАННЯ ЦИФРОВИХ
КЕРУЮЧИХ ПРИСТРОЇВ З ЖОРСТКОЮ ЛОГІКОЮ
05.13.12 – Системи автоматизації проектувальних робіт
Автореферат
дисертації на здобуття наукового ступеня
кандидата технічних наук
Одеса – 2007
Дисертацією є рукопис.
Робота виконана в Одеському національному політехнічному університеті Міністерства освіти і науки України.
Науковий керівник: | кандидат технічних наук, доцент
Полін Євген Леонідович,
Одеський національний політехнічний університет,
доцент кафедри комп’ютерних інтелектуальних систем
та мереж.
Офіційні опоненти: | доктор технічних наук, професор
Становський Олександр Леонідович,
Одеський національний політехнічний університет,
завідувач кафедри нафтогазового та хімічного
машинобудування;
кандидат технічних наук, доцент
Красічков Олексій Олександрович,
ДВНЗ “Донецький національний технічний університет”,
доцент кафедри електронних обчислювальних машин.
Захист відбудеться 29 листопада 2007 р. о 1330 на засіданні спеціалізованої вченої ради К .052.08 в Одеському національному політехнічному університеті за адресою: 65044, м. Одеса, проспект Шевченка, 1, ауд. 400-А.
З дисертацією можна ознайомитись у бібліотеці Одеського національного політехнічного університету за адресою: 65044, м. Одеса, проспект Шевченка, 1
Автореферат розісланий 26 жовтня 2007 р.
Вчений секретар
спеціалізованої вченої ради К .052.08,
кандидат технічних наук, доцент О.С. Савєльєва
ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ
Актуальність теми. Зростання складності цифрових обчислювальних систем (ЦОС) і підвищення вимог до процесу та результатів їх проектування обумовлюють необхідність розвитку вже існуючих та розробки нових ефективних методів синтезу цифрових елементів і пристроїв.
ЦОС у загальному випадку являє собою сукупність трьох компонентів: множини обчислювачів, множини елементів пам'яті, пристрою керування обчислювальним процесом. Пристрій керування в значній мірі визначає основні характеристики ЦОС: продуктивність, витрати обладнання, надійність. Проектування цифрових керуючих пристроїв (ЦКП) ускладнюється тим, що якщо функціональні вузли, які реалізують елементи пам'яті та оператори, звичайно досить стандартні й можуть повторюватися в різних ЦОС, то ЦКП, як правило, унікальні та вимагають повної процедури проектування для кожної конкретної ЦОС. Розробка ефективних ЦКП сучасних ЦОС через їх велику розмірність і складність можлива тільки за умови автоматизації процесу проектування.
В більшості випадків існуючі інструментальні засоби автоматизованого проектування ЦКП у якості математичного апарату використовують моделі низького рівня – автомати Мілі, Мура, С-автомати, та моделі високого рівня – описи ЦКП основані на граф-схемах алгоритмів (ГСА). Зазначені моделі низького рівня не можуть описувати такий важливий режим поведінки ЦКП як динамічне введення та усунення затримки його реакції. Для опису такого функціонування ЦКП застосовують штучні прийоми, в результаті чого ускладнюється апаратна реалізація ЦКП та погіршуються його часові характеристики. Традиційні графові моделі високого рівня характеризуються структурною надмірністю та необхідністю виконання додаткових заходів для забезпечення еквівалентності з моделями низького рівня, які застосовуються спільно з ними в проектному процесі. Це призводить до підвищення часової складності процесу синтезу та збільшення розмірів вихідного опису ЦКП.
На підставі викладеного, а також з урахуванням того, що адекватні моделі та методи синтезу, засновані на використанні цих моделей, можуть значно поліпшити техніко-економічні показники автоматизованого проектування ЦКП, справедливо твердження, що нове рішення науково-практичного завдання розробки засобів автоматизованого проектування ЦКП на основі ефективних моделей і методів є дуже актуальним.
Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконувалась відповідно до завдань держбюджетної науково-дослідної роботи Одеського національного політехнічного університету № 326-62 “Апаратно-програмні засоби автоматизованих систем”.
Мета і задачі дослідження. Мета роботи полягає в зменшенні часу синтезу і підвищенні якості проектних рішень САПР ЦКП за рахунок розробки ефективних моделей ЦКП та методів проектування.
Відповідно до поставленої мети в дисертації були вирішені наступні задачі:
– виконано аналіз структурної організації САПР ЦКП, а також моделей і методів, що використовуються у процесі автоматизованого проектування ЦКП;
– досліджені моделі керування ЦОС і системами автоматики, а також методи проектування, засновані на їх використанні;
– запропоновано класифікацію моделей керування ЦОС за ознакою міри покриття простору рішень, та визначено місце відомих моделей у цій класифікації;
– розроблені моделі низького рівня для ЦКП, які дозволяють адекватно описувати поведінку ЦКП з урахуванням динаміки його реакції;
– розроблені моделі високого рівня для ЦКП, орієнтовані на використання в САПР і позбавлені основних недоліків традиційних графових моделей;
– розроблені методи синтезу ЦКП, засновані на використанні запропонованих моделей, результати застосування яких дозволяють зменшити час синтезу і дають кращі показники продуктивності та складності апаратної реалізації, ніж традиційні методи;
– досліджена можливість мінімізації апаратної реалізації ЦКП за рахунок використання оптимального кодування внутрішніх станів, на підставі чого була виконана модифікація метода кодування;
– розроблено інформаційну технологію автоматизованого проектування ЦКП та САПР що її реалізує; у середовищі розробленої САПР проведена експериментальна перевірка запропонованих рішень.
Об'єкт дослідження. Процес автоматизованого проектування ЦКП.
Предмет дослідження. Моделі ЦКП, що застосовуються в САПР, та засновані на цих моделях методи проектування апаратного забезпечення.
Методи дослідження базуються на теорії цифрових автоматів, теорії графів, схемотехніці цифрових систем, теорії проектування ЕОМ і систем, елементах теорії алгоритмів і математичної логіки.
Наукова новизна отриманих результатів полягає в наступному:
– вперше розроблені моделі низького рівня для ЦКП – абстрактні композиційні автомати, які сполучають властивості автоматів Мілі та Мура в часі (СT-автомат) та в часі й просторі виходів (СST-автомат);
– дістав подальшого розвитку канонічний метод структурного синтезу цифрових автоматів шляхом його поширення на клас CST-автоматів з довільною кількістю виходів;
– дістали подальшого розвитку графові моделі високого рівня для ЦКП, а саме, запропоновані моделі ПГСА (паралельна граф-схема алгоритму) та модифікована ПГСА (яка в роботі отримала назву “ГВ-ГСА”), які відрізняються від традиційних моделей видом відношення суміжності вершин, правилами визначення позицій змінної стану, способами формування значень змінної стану та вихідних сигналів ЦКП;
– вперше розроблено методи синтезу ЦКП за його описом у вигляді ПГСА та модифікованої ПГСА, які засновані на переході до векторного композиційного СST-автомата з подальшим застосуванням до нього метода структурного синтезу;
– дістали подальшого розвитку методи оптимального кодування внутрішніх станів цифрового автомата, а саме, запропоновано модифікації методу квадратичного кодування, засновані на використанні методів Монте-Карло, обмеженого пошуку в ширину та на введенні штучної надмірності в розмірність кодових комбінацій.
Практичне значення отриманих результатів полягає у створенні інформаційної технології автоматизованого проектування (ІТАП) ЦКП, що представляє собою єдиний формалізований процес застосування у режимі автоматизованого проектування запропонованих і традиційних моделей, методів і методик. Розроблена ІТАП втілена в САПР ЦКП, що дозволило: зменшити час синтезу та виходячи із вхідних даних меншої розмірності, ніж в існуючих системах, одержати проектні рішення, що мають більшу продуктивність та менші апаратні витрати.
Використання модифікованої ПГСА як моделі високого рівня, мікропрограмного CST-автомата як моделі низького рівня та методу синтезу на їх основі в САПР ЦКП, дозволило в середньому: на 14% зменшити час синтезу; на 40% зменшити розмірність опису ЦКП; на 8% зменшити апаратну складність ЦКП та на 5,5% підвищити продуктивність системи ЦКП – об’єкт керування (ОК) в порівнянні з результатами використання традиційних моделей та методів. Застосування запропонованих модифікацій методу квадратичного кодування, дозволило зменшити складність апаратної реалізації функції переходів ЦКП на 9%.
Розроблені інформаційна технологія та САПР, впроваджені на виробничо-комерційному підприємстві “Телекарт – прилад” (м. Одеса) і використовуються там при проектуванні керуючих пристроїв для цифрових телекомунікаційних систем.
Теоретичні положення та програмне забезпечення, отримані в рамках дисертаційних досліджень, впроваджені в навчальний процес кафедри “Комп'ютерні інтелектуальні системи та мережі” Одеського національного політехнічного університету.
Особистий внесок здобувача полягає в дослідженні існуючих й розробці та розвитку нових моделей, методів і засобів автоматизованого проектування цифрових керуючих пристроїв з жорсткою логікою. Дисертант розробив нові математичні моделі ЦКП та на їх основі запропонував методи, призначені для використання в САПР, довів їх до рівня програмної реалізації і впровадження у виробництво, а також в навчальний процес. Автором запропоновано: класифікацію моделей керування ЦОС за критерієм якості покриття простору рішень [2, ]; моделі низького рівня для ЦКП – композиційні CT і CST автомати [4, 11]; графові моделі високого рівня для ЦКП і методи їх синтезу [3, ]; підходи до побудови САПР ЦКП на основі графових моделей [1, , ]; модифікацію методу квадратичного кодування станів цифрового автомата [9].
Апробація роботи. Основні результати дисертаційного дослідження доповідалися на Міжнародних конференціях з автоматичного управління “Автоматика–2004” (Київ, 2004), “Автоматика–2006” (Вінниця, 2006), Міжнародних науково-практичних конференціях “Сучасні інформаційні та електронні технології 2002, 2006, 2007” (Одеса, 2002, 2006, 2007), науковому семінарі “Математичне моделювання та інформаційні технології” (Одеса, 2007), науковому семінарі “Інформаційні системи та технології” (Одеса, 2005), Всеукраїнській конференції молодих вчених “Комп'ютерне моделювання та інформаційні технології в науці, економіці та освіті” (Кривий Ріг, 2001), Міжнародній науково-технічній конференції “Фізичні та комп'ютерні технології в народному господарстві” (Харків, 2000).
Публікації. За матеріалами дисертації опубліковано 15 наукових праць, у тому числі 6 статей (5 з яких у фахових виданнях згідно з переліком ВАК України) та 9 тез доповідей на науково-технічних конференціях і семінарах.
Структура і обсяг дисертації. Дисертаційна робота складається зі вступу, п'яти розділів, висновків, списку використаних джерел та трьох додатків. Загальний обсяг дисертації становить 189 сторінок, в тому числі 154 сторінки основного тексту, і містить 50 рисунків та 31 таблицю. Список використаних джерел складається з 104 найменувань.
ОСНОВНИЙ ЗМІСТ РОБОТИ
У вступі обґрунтована актуальність теми дисертації, сформульовані основна мета і задачі дослідження, зазначено зв'язок з науковими програмами, планами і темами, охарактеризовані наукова новизна і практичне значення одержаних результатів, приведена інформація про впровадження результатів роботи, їхню апробацію і публікації.
У першому розділі проведено аналіз структурної організації САПР ЦКП, а також моделей і методів, які використовуються в процесі автоматизованого проектування ЦКП (рис. ). Відзначено, що методи синтезу ЦКП використовують у якості вхідних даних два типи моделей: моделі високого рівня, які є вихідним описом ЦКП, і моделі низького рівня, що безпосередньо втілюються в апаратну реалізацію.
Рис. 1. Структурна організація САПР ЦКП.
Методи синтезу виконують переклад опису ЦКП з моделей високого рівня у низькорівневі моделі й далі в системи булевих рівнянь, які визначають логічну схему пристрою, що проектується. Фізична реалізація пристрою виконується за рахунок використання опису систем булевих рівнянь у термінах мов опису апаратних засобів (Hardware Description Language – HDL).
Показано, що традиційні моделі та методи синтезу, які застосовуються в процесі автоматизованого проектування ЦКП, мають недоліки. Зокрема, використання в якості моделей низького рівня для ЦКП абстрактних автоматів (АА) Мілі або Мура пов’язане із проблемою некоректного функціонування системи ЦКП – об’єкт керування, що виникає при певних (властивих кожному із цих АА окремо) функціональних залежностях між станами входу ЦКП і станами його виходу. Для ОК з поведінкою, що змінюється в часі (у частині затримки функціонування), традиційно описують поведінку ЦКП автоматом Мілі, а на етапах, коли реакція ЦКП на зміну його входу повинна супроводжуватися затримкою, вводять в автомат додатковий внутрішній стан. Це призводить до ускладнення ЦКП. При описі ЦКП що керує ОК з векторним виходом і поведінкою, яка змінюється у часі по кожному з його компонентів, виникають описані проблеми, але розповсюджені на простір виходів ОК.
Використання в САПР ЦКП, графових моделей високого рівня, заснованих на моделі ГСА, пов’язано з рядом проблем.
1. Методи синтезу, засновані на переході від цих моделей до АА Мілі або Мура, пов'язані із взаємними перетвореннями між нееквівалентними моделями, що призводить до необхідності застосування штучних прийомів (що дозволяють враховувати динаміку реакцію ЦКП), які погіршують характеристики ЦКП.
2. Традиційні графові моделі мають недолік, що виражається в надлишковому числі вершин і необхідності усунення наслідків цієї надмірності при мінімізації булевих функцій у процесі синтезу. Цей недолік є наслідком опису функції переходів і функції виходів ЦКП одним графом з послідовною структурою. Усунення зазначеного недоліку призводить до збільшення часу синтезу.
3. У традиційних графових моделях ЦКП не передбачена можливість безпосереднього звертання до змінної стану, однак така можливість може бути корисною у зв'язку з тим, що вона дозволила б інтерпретувати змінну стану як звичайну змінну операційного автомата (ОА). Це в свою чергу дало б можливість перекласти процес зміни значень змінної стану на ОА.
Розроблено класифікацію моделей обчислювальних процесів за ознакою міри покриття простору рішень. Визначено місце традиційних моделей ЦКП у цій класифікації. Показано, що традиційні графові моделі ЦКП накладають обмеження на можливість керування багатьма класами обчислювальних процесів у зв'язку з низьким значенням класифікаційної ознаки. Виходячи з результатів аналізу сучасного стану автоматизованого проектування ЦКП, ставиться мета і задачі подальших досліджень.
У другому розділі запропоновані моделі низького рівня для ЦКП з затримкою реакції, яка змінюється в часі – абстрактні композиційні автомати. Вони дозволяють сполучати властивості автоматів Мілі та Мура в часі (СT-автомат) та в часі й просторі виходів (СST-автомат). Показано, що композиційні автомати є самостійним класом абстрактних автоматів, а автомати Мілі, Мура та С-автомати являють собою їхні окремі випадки.
Композиційний CT-автомат визначається як кортеж з п’яти компонентів:
SCT A, , ,
де A= A1A2 – множина (алфавіт) внутрішніх станів автомата (A1A2=);
A1, A2 – непусті множини станів типу 1 та 2, відповідно. В станах aA1 та aA2 автомат SCT веде себе як автомат Мілі та Мура відповідно;
X = {x1,2,…,f} та Y = {y1,y2,…,yg} – множини станів входу та виходу, відповідно (вхідний та вихідний алфавіти);
– функція переходів, що реалізує відображення деякої множини D AX в A;
– функція виходів;
1 – функція виходу, що реалізує відображення деякої множини в Y;
2 – функція виходу, що реалізує відображення деякої множини в Y.
Оскільки СT-автомат у стані aA1 веде себе як автомат Мілі, а в стані aA2 – як автомат Мура, то A1 і A2 будуть називатися, множеною станів автоматів Мілі та Мура, відповідно.
Доведено наступні теореми.
Теорема 1. Для композиційного CT-автомата не існує рівносильного автомата Мілі.
Теорема 2. Для композиційного CT-автомата не існує рівносильного автомата Мура.
Визначено композиційний CST-автомат із двома виходами. Ця модель поширена на випадок довільної кількості виходів. Векторний CST-автомат з n виходами визначається як кортеж з шести компонентів:
= A, C, X, Y, , ?,
де A= – множина внутрішніх станів, Aj Ak= для будь-яких Aj и Ak при jk;
С – двійкова утворююча матриця (УМ) розмірністю n2n виду С=, C1 – матриця розмірністю n2 у якій перший стовпець містить нульові, а другий одиничні значення, C2 – матриця розмірністю n(2n-2), стовпці якої містять всі можливі різні двійкові комбінації відмінні від стовпців матриці C1. УМ – це матриця, яка описує поведінку композиційного автомата на різних етапах його функціонування. Число рядків УМ дорівнює кількості виходів автомата. Число стовпців дорівнює кількості підмножин Ai, на які розбитий внутрішній алфавіт автомата. Кожний стовпець УМ значеннями своїх компонентів визначає тип виходу (“0” – вихід типу Мілі, “1” – вихід типу Мура) при приналежності поточного стану автомата тій або іншій підмножині Ai;
X = {X1,2,…,m} та Y = {Y1,2,…,n} – множини, елементами яких є множини станів входів та виходів, відповідно;
– функція переходів, що реалізує відображення деякої множини D в A, де D ADX, DX T, де T={t tP(X1X2…Xm) та t{xi,}{xi,}, i=1..m }, P – операція отримання булеану. Множина T містить елементи булеану множини X1X2…Xm, за винятком тих елементів, які одночасно містять елемент вхідного алфавіту та його інверсію. Таким чином, компоненти DX – це можливі комбінації елементів вхідних алфавітів, від яких може залежати перехід автомата в черговий стан.
? = {?1, ?2,…, ?n} – множина функцій виходів, таких що
та операції над матрицею C та множиною A:
= =
та – функції виходу, що реалізують, відповідно, відображення деякої множини DX чи деякої множини в Yi.
Якщо значення i-того виходу CST-автомата визначається в даний момент часу функцією виходу , то цей вихід є виходом типу Мілі, якщо функцією , то цей вихід у даний момент часу є вихід типу Мура.
Кількість підмножин Ai, на які розбивається внутрішній алфавіт CST-автомата з n виходами, дорівнює M=2n. Число різних моделей автоматів з n-компонентним векторним виходом, які можливо одержати на основі такої розбивки (шляхом виродження деяких підмножин Ai), дорівнює K=–1 (рис. 2). З них KCST = K – 2n –1 моделей належать до класу композиційних CST-автоматів (у тому числі, модель у якій всі множини Ai непусті – повний CST-автомат, та інші KCST –1 моделей, що є його окремими випадками – часткові CST-автомати).
Рис. 2. Можливі реалізації CST-автомата з n виходами.
“Мі” – вихід типу Мілі, “Му” – вихід типу Мура,
“0” – підмножина Ai пуста, “1” підмножина Ai не пуста
Вводяться наступні позначення. та – непересічні множини вихідних сигналів CST-автомата, що мають місце у момент часу t на виходах, типу Мура й Мілі відповідно. та – непересічні множини вихідних сигналів на виходах типу Мура та Мілі, відповідно, у даний момент часу рівних логічній одиниці.
Дістав подальшого розвитку канонічний метод структурного синтезу (КМСС) АА, шляхом його адаптації до задач синтезу CST-автомата з двома виходами та CST-автомата з довільною кількістю виходів. Для представлення первісних даних запропонованого методу, використовується структурна таблиця, що відрізняється від аналогічної таблиці традиційного КМСС одночасною наявністю стовпців описуючих значення на виходах типу Мура () та типу Мілі ().
Перші два етапи метода структурного синтезу (кодування абстрактних алфавітів і вибір елементів пам'яті) векторного CST-автомата збігаються з аналогічними етапами КМСС. На третьому етапі, з урахуванням формату структурної таблиці, виконується побудова системи булевих функцій збудження елементів пам’яті CST-автомата. На четвертому етапі виконується побудова системи функцій вихідних сигналів. Вираження для кожної функції вихідного сигналу має вигляд:
yh = A1 A2 … Ag N1 N2 … Ns,
де Aq – поточний стан, якому відповідає (входить в один рядок структурної таблиці) вихідний сигнал ; Nq кон’юнкція виду aiXj, у якій ai – поточний стан та Xj – множина умов переходу із цього стану, що відповідають сигналу .
У третьому розділі запропоновані графові моделі високого рівня для ЦКП, які призначені для використання в процесі автоматизованого проектування, а також методи синтезу засновані на цих моделях.
Запропонована модель – ПГСА та заснований на ній метод синтезу ЦКП. Модель ПГСА має кращі характеристики за ознакою міри покриття простору рішень ніж традиційні моделі і дозволяє відмовитися від введення порожніх вершин при певних функціональних залежностях між логічними умовами та мікроопераціями.
Модель ПГСА дістала подальший розвиток у вигляді модифікованої ПГСА, яка дозволяє: роздільно описувати функції переходів і виходів, що дає можливість зменшити час синтезу та розмірність опису пристрою; використовувати механізми прямої та непрямої зміни стану пам’яті ЦКП, що дає можливість балансувати обсяг апаратного забезпечення між ЦКП та ОА? а також залучати обчислювальні ресурсі ОА для задач організації керування.
Модифікована ПГСА – визначається як 11-ти компонентний кортеж
G (V, Г,,,, R, P,X,Y,R,P),
де V =VX VY VR VP{vB, vE} – множина вершин модифікованої ПГСА; VX, VY, vB, vE – множини логічних та операторних вершин, початкова та кінцева вершини, відповідно, аналогічні однойменним вершинам ГСА; VR – множина операторних вершин керування; VP – множина вершин позицій;
Г – відношення суміжності на множині V;
X та Y – множина логічних умов та мікрооперацій, відповідно;
FP – змінна стану (фішка), визначена на множині констант P та доступна ОА;
R – множина мікрооперацій, що мають на змістовному рівні вигляд: Ft+1 := f(Ft, W), де Ft та Ft+1 – значення фішки у поточний та наступний момент часу, відповідно; f – деяка функція, що залежить від поточного значення фішки і змінних W ОА;
P N0 – непуста множина цілих констант, що відмічають вершини VP, vB, vE;
LX : X VX, LY : Y VY , LR: R VR, LP: P VP {vB, vE} – відображення задані на відповідних компонентів кортежу G.
Опис ЦКП на основі модифікованої ПГСА являє собою орієнтований (не обов'язково зв'язаний) граф, що має одну початкову (vB) та можливо одну кінцеву вершину (vE).
Вершина позиції vPVP це вершина в якій може перебувати фішка. У будь-який момент дискретного часу, фішка може перебувати тільки в одній вершині позиції. Кожна вершина vVP {vB, vE} повинна бути відмічена підмножиною множини констант P. Кожна константа відмічає тільки одну вершину vPVP чи пару вершин {vB, vE}.
Активний шлях фішки (АШФ) – це такий спрямований шлях між вершиною позиції viVPvB, у якій перебуває фішка в поточний момент часу t і вершиною позиції vjVPvE, у якій фішка повинна перебувати в момент часу t+1. АШФ може бути заданий явно або за умовчуванням. Допускаються два способи явного завдання АШФ – прямий та непрямий. При прямому способі завдання, вершини vi та vj зв'язані за допомогою послідовності дуг, що виходять з вершини vi, проходить через вершини логічних умов і входять у вершину vj. При непрямому завданні, перехід фішки з вершини vi у вершину vj визначений єдиною операторною вершиною vVR, яка містить мікрооперацію rR та лежить наприкінці шляху, що виходить з вершини vi. Активні шляхи задані коректно, якщо при будь-якому припустимому наборі значень логічних умов X(t) модифікована ПГСА має один явно заданий АШФ, або не має такого. В останньому випадку АШФ заданий за умовчуванням, при цьому F(t+1) = F(t).
Активні шляхи ініціалізації (АШІ) – це множина спрямованих, не циклічних шляхів, що виходять з вершини позиції vVPvB, у якій перебуває фішка в даний момент часу, не проходять через інші вершини позицій і завершуються вершинами з множини VY. АШІ, які містять та не містять умовні вершини, називаються умовними та безумовними АШІ, відповідно. Безумовною частиною умовного АШІ називається та його частина, що перебуває між вихідною вершиною позицією АШІ і найближчої до неї умовною вершиною (включаючи умовну вершину). Умовна частина АШІ являє собою його доповнення до безумовної частини.
Виконання модифікованої ПГСА – це процес дискретного переміщення фішки F з вершини початкової позиції vB у вершину кінцевої позиції vE (чи в vB) по деякому шляху, який складається з фрагментів, що є АШФ для кожної вершини позиції, та супроводжується ініціалізацією умовних і операторних вершин, що перебувають на АШІ.
Таким чином, АШФ визначають переходи фішки по графу, а АШІ – функцію виходу в кожній позиції розміщення фішки. Підграф переходів фішки GП – це підграф модифікованої ПГСА, що включає всі можливі АШФ. Підграф виходів GВ – ациклічний підграф, що включає всі можливі АШІ.
Припустиму топологію графа модифікованої ПГСА визначає відношення суміжності Г. Його основні властивості полягають у наступному: образ кожного елемента з множин VY, VX, VP та {vB} в цьому відношенні може містити будь-яке, відмінне від нуля, число елементів; вершини VX, VP, vB не можуть бути кінцевими вершинами графа; множина образів вершин VR і vE у відношенні Г, порожня; операторній або умовній вершині повинні передувати вершини; вершині позиції чи кінцевій вершині може не передувати жодна вершина.
Довільний граф модифікованої ПГСА G має еквівалентний за результатом виконання граф G', кількість операторних вершин в якому не перевищує |Y |+|R|. Подання модифікованої ПГСА у вигляді графа G’ буде називатися структурованим поданням (СП). У роботі запропонована методика перетворення довільного графа G до СП. У СП множина умовних вершин складається із трьох попарно непересічних підмножин VX=VX1VX2VX3, причому VX1VX2 GВ, VX1VX3 GП (рис. 3).
Рис. 3. Вигляд графа модифікованої ПГСА у структурованому представленні.
У графі СП G’ переходи фішки до вершин позицій, позначених множинами констант P1…Pi, задані у непрямий спосіб за допомогою операторних вершин VR. Переходи до вершин позицій Pi+1…Pk та кінцевої/початкової вершини задані у прямий спосіб за допомогою дуг, що входять у ці вершини. У граничних випадках переходи в усі вершини позиції та у кінцеву вершину можуть бути задані тільки у непрямий спосіб або навпроти винятково прямо.
Позначення вершини viVP vE множиною констант Pi P, що має потужність |Pi|>1, дозволяє за допомогою однієї мікрооперації rR виконати переходи: з різних вершин множини VP vB у вершину vi; з вершини vi в різні вершини множини VP vE.
В роботі запропоновано методи структурного синтезу ЦКП за його описом у вигляді ПГСА та модифікованої ПГСА. Методи засновані на переході від високорівневого графового опису ЦКП до мікропрограмного CST-автомата (перший етап) та виконанні структурного синтезу отриманого автомата (другий етап).
Перший етап методу синтезу ЦКП за його описом у вигляді модифікованої ПГСА містить тринадцять дій. Перша дія етапу виконує зіставлення множини вершин позицій ПГСА та множини вершин графа CST-автомата. Друга дія виконує зіставлення множини констант, що позначають вершини позицій ПГСА та множини станів CST-автомата. У межах третьої дії виконується зіставлення множини станів CST-автомата та множини вершин його графа. Четверта та п’ята дії ставлять у відповідність АШФ ПГСА, які задані явно, прямим способом та за умовчуванням, дуги графа CST-автомата. Шоста та сьома дії ставлять у відповідність логічним умовам ПГСА вхідні алфавіти, а мікроопераціям ПГСА – вихідні алфавіти CST-автомата. Восьма дія мікроопераціям rkR ПГСА ставить у відповідність вихідні алфавіти відповідних виходів 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 = T = f(D). Свободою кодування буде називатися відношення кількості можливих КК до кількості станів автомата, які потрібно закодувати: F(D) t/D = T/D = f(D)/D. Лівою околицею точки x0 буде називатися інтервал (x0-?, x0], при ? > 0 (?, x0N).
В дисертації був проведений аналіз функції F(D) та її зіставлення з поведінкою функції kЭФ(D). У результаті цього, другим фактором, що знижує ефективність квадратичного кодування, була визначена низька свобода кодування при D, що приймає значення з лівої околиці цілого ступеня двійки.
З метою зменшення негативного впливу першого фактора, в роботі запропоновано чотири модифікації ЕМ (ЕМ1 – ЕМ4). Нехай K={K1, … Kt} – множина усіляких КК розмірності T; A={a1, …, aD} – множина станів автомата, які потрібно закодувати; t = 2T, D ? t. Задача ЕМ полягає у однозначному зіставленні LK: AKA, множині A, множини кодів станів КА={kai | kaiK}. На нульовому кроці традиційного ЕМ кодуються одразу два стани, обрані за визначеними правилами. На i-му кроці ЕМ кодується черговий незакодований раніше стан aН. Для цього за правилами ЕМ з множини ще незакодованих КК KНЗK вибирається ПБКК KЖKНЗ. Для всіх КК, що входять до KЖ={, , … } за правилами ЕМ, підраховуються значення оцінних функцій ={?1, ?2, … ?p}. Після цього, за наступним правилом, виконується кодування стану aН:
якщо ?j = min(), то LK(aН).
ЕМ передбачає, що у випадку, якщо мінімальне значення мають оцінні функції для декількох КК із KЖ (надалі цей випадок буде називатися “спеціальною ситуацією”), то для кодування на поточному кроці необхідно вибрати першу з цих КК. Тобто, правило кодування для “спеціальної ситуації” має такий вигляд:
якщо = min(), то LK(aН) | (1)
Модифікація 1 (ЕМ1). Пропонується вирішення задачі розвитку ЕМ шляхом використанням методу Монте-Карло, аналогічно тому, як це робиться для рішення задачі комівояжера. Виконується традиційний ЕМ, для якого правило розв’язання “спеціальної ситуації” (1) формулюється в наступному вигляді:
якщо = min(),
то LK(aН)random(,,…,) | (2)
Це означає, що якщо на i-му кроці ЕМ, виникає “спеціальна ситуація”, тобто мінімум на множині міститься в декількох її елементах, то випадковим образом вибирається одна із КК, що відповідає цим мінімумам. Після завершення кодування, підраховується значення kЭФ. Результати кодування запам'ятовуються у вигляді двох елементів: значення kЭФ та множина кодів КА. Процедура кодування повторюється задане число раз N. Якщо знову отримані, на черговому кроці, результати кодування КА мають менший kЭФ, то вони запам'ятовуються замість попередніх результатів.
Модифікація 2 (ЕМ2). Пропонується вирішення задачі розвитку ЕМ шляхом використанням методу обмеженого пошуку в ширину. Задається параметр пошуку – ціле число R = …(D-2). Виконується традиційний ЕМ, для якого правило розв’язання “спеціальної ситуації” формулюється в наступному вигляді:
якщо 0 < i ? R, то виконати правило (4), інакше виконати правило (1) | (3)
де i – номер кроку кодування – ціле число від 1 до D-2; R – глибина обмеження пошуку, ціле число від 0 до D-2. Правило (4) має наступний вигляд:
якщо = min(),
то (aН), (aН), … (aН) | (4)
Правило (4) означає, що якщо на i-му кроці ЕМ виникає “спеціальна ситуація” =min(), то формується стільки варіантів процедури кодування стану aН, скільки є мінімальних значень у множині . Подальші кроки виконуються з урахуванням всіх отриманих на даному кроці варіантів кодування. Правило (3) означає, що правило (4) застосовується для розв’язання “спеціальної ситуації” тільки на обмеженій кількості початкових кроків.
Така процедура призводить до одержання дерева рішень. Гілкам цього дерева на кожному кроці присвоюються КК з множини {, ,…, }. Альтернативні множини результатів кодування КА1, КА2, … КАh отримуються як послідовності КК, що зустрічаються на шляху від кореня до кожної з кінцевих вершин дерева. Для кожної з множин КА1, КА2, …, КАh підраховується kЭФ. У якості остаточного результату кодування, обирається будь-яка множина КАi, що має найменший kЭФ.
Модифікація 3 (ЕМ3). Запропоновано подальший розвиток ЕМ на основі спільного застосування ЕМ1 та ЕМ2. До ЦА застосовується ЕМ2, результатом цього є множина кодів КАmin, яка складається з двох непересічних підмножин КАmin=КА4КА1, де КА4 і КА1 – підмножини КК отриманих за правилами (4) та (1), що входить до ЕМ2, відповідно. Задається параметр N і до станів, що кодуються на лінійному ланцюжку вершин дерева рішень, підмножиною кодів КА1 застосовується ЕМ1.
Модифікація 4 (ЕМ4). Запропоновано подальший розвиток ЕМ за рахунок модифікації ЕМ3. При виконанні ЕМ3 обирається будь-яка підмножина KA, що має найменше значення kЭФ. Якщо таких підмножин декілька, то до кожної з них можна застосувати етапи ЕМ3 і вибрати кращий результат. Для керування процесом кодування пропонується параметр 1 ? H ? u, що визначає кількість підмножин КА, до яких застосовується ЕМ4.
З метою зменшення негативного впливу другого фактора, запропонована п'ята модифікація ЕМ (ЕМ5). Завдання усунення впливу другого фактора може бути вирішена шляхом штучного збільшення розмірності КК. Таке збільшення розмірності КК на одиницю призводить до: збільшення простору рішень задачі кодування (множини можливих КК) у два рази; збільшення пам'яті автомата на один елемент та можливо додатковим витратам апаратури. Перший із зазначених наслідків, збільшення розмірності КК, може послужити поліпшенню результатів кодування, а отже зменшенню апаратних витрат на реалізацію ЦА. Другий наслідок призводить до безумовного збільшення апаратних витрат. Рішення задачі кодування при цьому полягає в знаходженні компромісу між результатами даних двох наслідків введення штучної надмірності в розмірності КК.
Модифікація 5 (ЭМ5) полягає в наступному. Виконується кодування одним з ЕМ – (ЕМ…ЕМ4). Результатом кодування є три компоненти: KA – множина кодів станів; kЭФ; ціна за Квайном C для системи булевих рівнянь, що реалізують функції збудження елементів пам'яті ЦА. Задається CП – ціна за Квайном елемента пам'яті та E[0, ] – дійсний параметр, що визначає поріг кількості станів, починаючи з якого свобода кодування вважається “недостатньою” для ефективного кодування. Зазначений поріг обчислюється за формулою:
П = ОК(D) – {[ОК(D)]•E + 1}
де, ОК(D) та ОК(D) – операції округлення, результат яких дорівнює найближчому більшому та меншому числу, відповідно, що є цілим ступенем двійки (операнд кратний числу, яке є цілим ступенем двійки, не округляється); {} – операція традиційного арифметичного округлення.
Якщо D < П, то кодування припиняється і як остаточний результат приймається отримана множина кодів, тому що, для даного D, при заданому порозі вважається, що, свобода кодування має “достатню” величину і її збільшення не приведе до підвищення ефективності кодування. Інакше у КК вноситься надмірність, шляхом збільшення їх розмірності на один розряд і процедура кодування повторюється. Якщо сума знов отриманої ціни C та ціни CП менша за ціну отриману до внесення надмірності, то збільшення свободи кодування дало позитивний результат і робиться спроба подальшого її збільшення.
У роботі проведено експерименти над програмними реалізаціями запропонованих модифікацій ЕМ і виконані зіставлення отриманих результатів з результатами традиційного ЕМ. Експерименти полягали в кодуванні автоматів, що розрізняються: числом станів, видами графів, призначенням. Експерименти показали доцільність застосування запропонованих модифікацій в процесі синтезу ЦКП. Узагальнені результати експериментів представлені в таблиці.
У п'ятому розділі запропонована ІТАП ЦКП та виконано опис САПР, що втілює цю технологію. Розроблена ІТАП являє собою єдиний формалізований процес застосування запропонованих і традиційних моделей, методів та методик, спрямований на підвищення ефективності проектування ЦКП. ІТАП складається з дев'яти етапів, що дозволяють по технічному завданню на проектування ЦКП одержати технологічні дані для його апаратної реалізації. Основною моделлю ЦКП, для представлення вхідних даних, у розробленій інформаційній технології виступає модифікована ПГСА. При накладенні на цю модель певних обмежень, ЦКП може бути представлений у вигляді ПГСА або ГСА.
Запропонована технологія втілена
