|
НАЦІОНАЛЬНА АКАДЕМІЯ НАУК УКРАЇНИ
ІНСТИТУТ ПРОБЛЕМ МОДЕЛЮВАННЯ В ЕНЕРГЕТИЦІ
ім. Г.Є. Пухова
к.т.н. Януш Шайна (Польща)
УДК 681.33
ПРОЕКТУВАННЯ ЦИФРОВИХ СИСТЕМ З
ВИКОРИСТАННЯМ ЛОГІЧНОГО ПРОГРАМУВАННЯ
Спеціальність 05.13.13 - Обчислювальні машини, системи та мережі
Автореферат
дисертації на здобуття наукового ступеня
доктора технічних наук
Київ – 2001 р.
Дисертацією є монографія.
Робота виконана у фірмі ADB (Advanced Digital Broadcast - Польща)
Офіційні опоненти:
д. т. н., проф. І.А. Жуков, зав. кафедри обчислювальної техніки Національного авіаційного університету МОН України, м. Київ
д. т. н., проф. В.Н. Коваль, зав. відділом Інституту кібернетики ім. В.М. Глушкова НАН України, м. Київ
д. т. н., проф. Ю.М. Коростіль, зав. відділом Інституту проблем моделювання в енергетиці НАН України, м. Київ.
Провідна організація - Національний технічний університет “Київський Політехнічний Інститут” Міністерства освіти і науки України, Київ, кафедра ЕОМ.
Захист відбудеться “27“ вересня 2001 р. о 14 год. на засіданні спеціалізованої ради
Д 26.185.01 Інституту проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
(03680, ГСП, Київ-164, вул. Генерала Наумова, 15)
З дисертацією можна ознайомитись у бібліотеці Інституту проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України.
Автореферат розіслано “23“ серпня 2001 р.
Вчений секретар спеціалізованої
ради Д 26.185.01
канд. технічних наук Е. П. Семагіна
ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ
Актуальність роботи
В останній час спостерігається інтенсивне зростання кількості робіт, що потребують нових інформаційних технологій автоматизованого проектування цифрових систем. Обумовлюється цей зріст, насамперед, великою конкуренцією на електронному ринку, а також розповсюдженням пристроїв, вироблених малими серіями і призначених до конкретного застосування (пристрої ASIC - Application Specific Integrated Circuit). Вимоги ринку, як і виробництво малих серій, вимагають підвищення ефективності проектування, тобто скорочення часу, необхідного для підготовки проекту, та виконання ретельної перевірки пристрою ще до початку його виробництва. Внаслідок цього виникла необхідність автоматизації всіх етапів проектування, в тому числі тих, для яких традиційні методи проектування мало ефективні.
У зв’язку зі сказаним вище, все більшого значення набирають методи, які принципово відрізняються від традиційних тим, що мають не числовий і не алгоритмічний характер. Вони базуються, головним чином, на використанні евристичного і символічного перетворень, які широко використовуються у штучному інтелекті.
На думку автора, значні можливості в цій сфері створює застосування логічного програмування.
Логічне програмування нині використовується в багатьох різноманітних галузях, таких, наприклад, як перетворення мови, керування, аналіз фінансового ринку, в архітектурі, телекомунікації, для перетворення образів і інше. Проте, крім існування природних зв’язків з проектуванням цифрових систем, відомі з літератури приклади використання логічного програмування в цій галузі обмежуються елементарними зразками.
Метою монографії є усунення перелічених прогалин.
Представлені вище міркування стосуються, насамперед, двох головних задач, яким безпосередньо присвячена ця монографія, тобто символічному синтезу цифрових систем і динамічному моделюванню, що враховує часові залежності.
Відомі з літератури праці, які присвячені безпосередньо символічному синтезу, мають елементарний, або фрагментарний характер.
В другому випадку, тобто при динамічному моделюванні, відомі авторові праці, пов’язані з логічним програмуванням, не вирішують проблем реальних часових залежностей, а тільки зв’язані логічно з секвенцією нуль-одиниця, або одиничними змінами сигналу, а не з відображенням складних, взаємозалежних векторів багатьох сигналів. В деяких інших відомих авторові працях запропоновані рішення, які мають алгоритмічний характер і стосуються аналізу одиничних часових залежностей, а не складних діаграм, або зв'язані тільки зі специфікацією, а не з моделюванням даних залежностей.
Мета роботи
Метою дисертації, згідно з викладеним вище, є створення методології проектування і моделювання електронних цифрових систем з використанням логічного програмування, зокрема, у визначенні можливості доповнення застосованих традиційних алгоритмічних і числових методів методами евристичними і символічними.
Метою дисертації з практичної точки зору є, передусім, створення ефективних методів:
а) моделювання поведінки цифрових систем і процесів зі складними часовими діаграмами і розпізнавання таких діаграм,
б) символічного синтезу цифрових систем.
Перша з тих проблем (моделювання і розпізнавання часових діаграм) становить спробу нового розв’язання однієї з дуже трудомістких задач, пов’язаних з моделюванням систем високого рівня інтеграції (VLSI) і є темою праць автора, які були виконані в останній час.
Друга проблема, символічний синтез, є альтернативною у відношенні до числових методів, а також до комплексного методу проектування цифрових систем. Розв'язанню цієї проблеми присвячені деякі праці автора в 1985-1993 роках.
Зв’язок роботи з науковими програмами і дослідними планами
Ідеї, які представлені в монографії, виникли в межах наступних науково-дослідних програм.
CPBP 02.20: Впровадження програмованих логічних структур у цифрових системах та вимірювальних приладах. 1985-1990. Політехніка Зеленогурська. В рамках Центрального Плану Головних Досліджень Міністерства Науки і Вищої Освіти Польщі.
Роль автора: безпосередній учасник і заступник керівника теми.
COHERENCE S-JEP no 07648 i S-JEP no 0449 (Structural Joint European Project). 1990-1996. Проект фінансований Європейською Унією. Робота над проектом проводилася спільно з: (а) Університетом в Брістолі, Англія; (б) Університетом в Манчестері, Англія; (в) Політехнікою Зеленогурською, Польща.
Роль автора: керівник наукової теми з польської сторони.
Artificial Intelligence Based Stock Exchange Analyzer. 1991-1992. За умовою Kinetic Capital Corporation, Сиетл, США.
Роль автора: безпосередній учасник і керівник теми.
Audio and Video Compression. 1992. Центр Проектування Інтегральних Кіл INMOS. Image Processing Unit, Англія.
Роль автора: член колективу, відповідальний за частину проекту, яка стосується моделювання складних часових залежностей. Виконані теми автором: (а) Behavioral model of Generic Video RAM Device, (б) Timing model of MPEG Decoder.
Behavioral Model of STi 3240 Video Decoder. 1993-1994. Політехніка Зеленогурська. За умовою SGS-Thomson Microelectronics. Image Processing Business Centre, Гренобль, Франція.
Роль автора: безпосередній учасник і керівник теми.
Transputer Based Intelligent Management System for Interactive TV Digital Satellite Receiver. 1995-1996. Політехніка Зеленогурська. За умовою SGS-Thomson Microelectronics, Asia-Pacific Branch, Сінгапур.
Роль автора: безпосередній учасник і керівник теми.
IRD: Integrated Receiver-Decoder for Satellite TV. 1997-1999. Advanced Digital Broadcast, Польща. За умовою фірми Broadcast Software Systems International, Тайвань.
Роль автора: науковий керівник і координатор теми.
Наукова новизна здобутих результатів
До найважливіших наукових досягнень автора, відбитих у монографії необхідно віднести:
1. Розробка методології проектування і моделювання цифрових систем з використанням логічного програмування, зокрема, демонстрацію можливості доповнення традиційних алгоритмічних і числових методів евристичними і символічними методами.
2. Створення нового, оригінального методу розпізнавання часових діаграм, який має декларативний характер і базується на використанні застосованих в штучному інтелекті методів порівняння з еталоном і метапрограмування.
3. Створення мови моделювання, яка дозволяє ефективно проектувати моделі цифрових систем і процесів зі складними часовими діаграмами.
4. Застосування логічного програмування до автоматизації символічного синтезу цифрових систем, описаних за допомогою логічних секвенцій (спосіб реалізації подібний до автоматичного доведення теорем з використанням правил логічних висновків і евристичних правил).
5. Створення на основі розроблених теоретичних методів їх практичної реалізації, яка свідчить про придатність запропонованих методів до розв’язування реальних, складних задач в сфері проектування і моделювання цифрових пристроїв.
Практичне значення отриманих результатів
Результати робіт, зв’язаних з автоматизацією символічних перетворень логічних виразів (розділ 3 монографії), а також символічний синтез (розділ 4) були використані при розробці системи CAD LOGIC, яка призначена для комп’ютерного забезпечення проектування цифрових систем з програмованими логічними структурами PAL і була створена у 1989-1990 р.
Результати робіт, зв’язаних з розпізнаванням часових діаграм і мовою Pro Waves (розділ 6), були використані на практиці для побудови моделей динамічної пам’яті, пристрою декодера зображення і протоколів комунікації, які були створені у межах робіт, проведених колективом, очолюваним автором в 1992-1997 роках, для SGS-Thomson Microelectronics Asia-Pacific Branch, а також Broadcast Software Systems International.
В останній час роботи автора, зв’язані з розпізнанням і моделюванням складних часових діаграм, були використані для проектування інтегральних пристроїв високого рівня інтеграції ASIC, призначених до використання в інтерактивному цифровому телебаченні і при проектуванні супутникових телевізійних приймачів-декодерів за вимогою фірми Asia Digital Broadcast для ринків Австралії, Південно-Африканської республіки, Іспанії, Таїланду і Ізраїлю.
Особливої уваги заслуговує проект виконаного на високому рівні інтеграції пристрою ADB Phase II Signal Processor (PSP), а також пристрою Bili-I Fast Descrambler.
Пристрій PSP - спеціалізований процесор цифрових телевізійних сигналів, що реалізує, між іншими, функції: бітової і байтової корекції помилок, розкладання потужності цифрових сигналів на компоненти, а також декодування і транскодування сигналів. Пристрій PSP забезпечує роботу приймача інтерактивного цифрового телебачення у двох найбільш популярних нині системах передачі сигналу: DVB (Digital Video Broadcasting) в Європі і Orbit (Scientific Atlanta Compression System Phase II) у США. Система працює з максимальною частотою 120 мгГц і складається з 40 тисяч комірок. Проект системи виконано спільно з проектними бюро фірми SGS Thomson Microelectronics (США, Італія). Автор був відповідальним за виконання моделі системи PSP, а також брав участь в аналізі часових залежностей системи.
Система Bili-I є декодером для цифрової супутникової системи передачі сигналів, кодованих у форматі фірми IRDETO. Пристрій працює з частотою 60 мгГц і складається з 35 тисяч комірок. Автор виконав аналіз часових залежностей роботи пристрою на окремих етапах його проектування. До кінця 1999 року фірма SGS Thomson Microelectronics випустить 130 тисяч пристроїв Bili-I. Вже кілька місяців пристрій використовується у новій генерації супутникових приймачів-декодерів.
Особистий внесок автора
В області розпізнавання часових діаграм високої складності автор запропонував новий, оригінальний метод, який дозволяє принципово спростити створення моделей цифрових систем високого рівня інтеграції VLSI, а також різноманітних процесів, описаних за допомогою складних часових діаграм. За рахунок використання можливості логічного програмування в межах метапрограмування і порівняння з еталоном, а також використання символічного перетворення була отримана можливість простого перетворення опису часових діаграм на прологові описово-моделюючі правила.
З метою перевірки результатів теоретичної роботи автор розробив систему розпізнавання часових діаграм і мову моделювання цифрових пристроїв і процесів. Цю мову автор використав пізніше на практиці для проектування складних цифрових систем, що призначені, головним чином, до застосування у цифровому супутниковому телебаченні.
В сфері символічного синтезу цифрових систем автор запропонував використання логічного програмування для автоматизації синтезу пристроїв, описаних за допомогою логічних секвентів. Такий підхід дозволив створити комплексний апарат синтезу, що охоплює проблему - від опису праці системи до декомпозиції кінцевого опису підгруп, які можна впроваджувати у фізичних елементах.
У частині, присвяченій трансляції специфікації пристроїв, автор наводить методи штучного інтелекту, що застосовуються в інших галузях, до галузей, зв‘язаних з проектуванням і моделюванням цифрових пристроїв.
Крім того, автор представив в роботі відомі з літератури класичні методи специфікації і моделювання цифрових систем за допомогою логічного програмування в узагальненій і розширеній автором формі, завдяки чому отримано стисле і комплексне подання цілої тематики.
Апробація результатів
Головні наукові досягнення і практичні результати праці були представлені на конференціях і семінарах в Польщі і за кордоном. В Польщі в містах: Зелена Гура, Шклярська Поремба, Люблін, Торунь, Вроцлав, Гданськ, Варшава. За кордоном на міжнародних конференціях на Україні (Київ), в Словакії (Братислава), в Німеччині (Ілменау і Дрезден), Франції (Гренобль) і у Сінгапурі.
Публікації
По темі дисертації були опубліковані 41 наукова робота, серед яких 2 монографії (без співавтора), 2 книги, опубліковані в найбільш престижних у Польщі наукових видавництвах, тобто Panstwowe Wydawnictwo Naukowe (без співавторів) і Wydawnictwa Naukowo-Techniczne (автор і науковий редактор), а також 33 статті, серед яких 11 без співавторів.
Структура і обсяг роботи
Робота складається із вступу, шести розділів, заверешення, висновків і списку використованої літератури. В цілому монографія містить 240 сторінок, 26 рисунків, а також 11 таблиць і діаграм.
ЗмІст роботи
Розділ 1. Вступ
В розділі подано вступ до галузі логічного програмування, виконано огляд літератури, сформульована основна мета роботи та визначена галузь наукових досліджень, визначено практичне значення і показано зв’язок виконаної роботи з науково-дослідними програмами.
Розділ 2. Основні методи специфікації і моделювання цифрових систем
В розділі подані відомі з літератури класичні методи специфікації і моделювання цифрових систем за допомогою логічного програмування в узагальненій і розширеній автором формі. У розглянутих випадках логічне програмування використовується як мова специфікації так і моделювання. Опис пристроїв подано безпосередньо в формі клаузул або прологових термів, а їх властивості виводяться за допомогою безпосередньої логічної дедукції. Метою розділу є, з одного боку, представлення вище викладених методів, а з другого - подання основного механізму, на якому грунтується логічне програмування.
Розділ 3. Символічні операції
В розділі представлена проблема автоматичного перетворення логічних виразів, що використовуються в проектуванні цифрових пристроїв. Показано, що, завдяки декларативному характеру логічного програмування, автоматизація символічних перетворень може бути простою і натуральною. Сам опис проблеми, поданий в конвенції логічного програмування, є майже рівнозначним з його імплементацією, а окремі предикати є групами клаузул, кожна з яких відповідає визначеному правилу евристичного перетворення виразів і не залежить від рівня складності цього виразу.
Оскільки більшість проблем, зв’язаних з проектуванням цифрових систем, можуть бути вирішеними за допомогою евристичних методів та перетворень символічного характеру відповідно, дані методи автоматизації перетворень можуть мати широке і різнобічне застосування. Однак, перед усім, методи, що подані в цьому розділі, є вихідними для рішень, викладених в наступних розділах.
Розділ 4. Автоматизація символічного синтезу цифрових систем
В розділі розглянуто спосіб використання логічного програмування для реалізації символічного синтезу цифрових систем, описаних за допомогою логічних секвентів.
Представлене рішення проблем автоматизації процесів: (а) нормалізації секвентів способом подібним до автоматичного доведення теорем з використанням правил логічних висновків, (б) мінімізації опису з використанням евристичних правил, (в) синтезу до вигляду, що відповідає структурі використовуваних елементів - символічне перетворення, (г) декомпозиції опису системи на підгрупи, які можна використовувати в окремих фізичних елементах - вживання механізму пошуку апарату висновків.
Метод символічного синтезу цифрових систем, поданий у цьому розділі, було використано в системі CAD LOGIC, призначеній для проектування цифрових елементів з використанням програмованих логічних структур.
Як вже було зазначено, у синтезі був застосований підрахунок логічних елементів секвентів. Відносно до цифрових систем можна припустити, що секвент є умовним поняттям, в якому “умова” визначена комбінацією вибраних вхідних сигналів. Поява тих сигналів обумовлює реалізацію операції, яка записана з правого боку знаку включення (" |-" ) - як “наслідок”. Наприклад, опис за допомогою секвентів 4-бітового регістру, що виконує операції: установлення на виходах одиниць, паралельний запис даних, зсув вліво і зсув вправо, можна представити в вигляді:
/s1*/s0 |- @q3*@q2*@q1*@q0,
/s1*s0 |- (x3->@q3)*(x2->@q2)*(x1->@q1)*(x0->@q0),
s1*/s0 |- (q2->@q3)*(q1->@q2)*(q0->@q1)*(вхЛ->@q0),
s1*s0 |- (вхПp->@q3)*(q3->@q2)*(q2->@q1)*(q1->@q0).
де:
x3, x2, x1, x0 - паралельні входи,
вхЛ - послідовний вхід при зсуві вліво,
вхПp - послідовний вхід при зсуві вправо,
q3, q2, q1, q0 - виходи,
@ - знак, передуючий виходам в наступному стані.
Головною частиною процесу проектування є перетворення початкового опису функціонування системи, поданого за допомогою секвентів, до вигляду, відповідного структурі елементів, передбачених для використання. Оскільки було прийнято, що будуть застосовуватись елементи PAL, завдання полягає у виділенні з секвентів знаків імплікації і рівнозначності, а також здійсненні таких перетворень, при яких кожний секвент відтворював би залежності вихідних сигналів від вхідних у вигляді, відповідному елементам PAL.
Цей процес можна реалізувати в три етапи. На першому етапі виконується так звана нормалізація секвентів шляхом вилучення з них всіх логічних поєднань. На другому – виконується мінімізація вихідних функцій. На третьому – проводиться синтез секвентів до вигляду, відповідного структурі систем PAL.
Наприклад, для групи секвентів:
/s1 * /s0 |- (a1->y1)*(a0->y0),
/s1 * s0 |- (b1->y1)*(b0->y0),
s1 * /s0 |- (c1->y1)*(c0->y0),
s1 * s0 |- y1 * y0.
нормалізація приводить до наступного виду:
a0 |- y0,s1,s0
a1 |- y1,s1,s0
b0,s0 |- y0,s1
b1,s0 |- y1,s1
c0,s1 |- y0,s0
c1,s1 |- y1,s0
s1,s0 |- y1
s1,s0 |- y0
Потім, з метою виконання мінімізації залежності вихідних сигналів від вхідних, необхідно, насамперед, перетворити секвенти таким чином, щоб вони явно виражали ті залежності. Для цього необхідно, щоб в другому члені виразу секвента залишилися тільки ті сигнали, які представляють результати операції:
a0,/s0,/s1 |- y0
a1,/s0,/s1 |- y1
b0, s0,/s1 |- y0
b1, s0,/s1 |- y1
c0,/s0, s1 |- y0
c1,/s0, s1 |- y1
s0,s1 |- y1
s0,s1 |- y0
На цій підставі після мінімізації утворюються наступні секвенти, що представляють можливі елементарні залежності вихідних сигналів від вхідних:
b0,s0 |- y0
b1,s0 |- y1
c0,s1 |- y0
c1,s1 |- y1
a0,/s0,/s1 |- y0
a1,/s0,/s1 |- y1
s0,s1 |- y1
s0,s1 |- y0
На черговому етапі синтезу виконується відповідне об’єднання секвентів таким чином, щоб отриманий запис відповідав безпосередньо структурі елементів PAL:
s0*s1 + a1*/s0*/s1 + c1*s1 + b1*s0 |- y1
s0*s1 + a0*/s0*/s1 + c0*s1 + b0*s0 |- y0
Останнім кроком (декомпозиція опису) є поділ секвентів на підгрупи, кожна з яких може бути використана в одному елементі PAL. Цей поділ повинен бути виконаний так, щоб забезпечити оптимальне використання елементів.
Найбільш важливими розділами синтезу є нормалізація секвентів і мінімізація опису. Нормалізацію секвентів можна виконати способом, подібним до автоматичного доведення теорем, якщо використати при цьому формальний математичний апарат у вигляді правил висновків Гентцена. Мінімізацію слід проводити евристичним способом, застосовуючи правила поглинання і відсікання. Нижче подані приклади обох зазначених груп правил, представлених у формальному запису (окремі грецькі літери означають пропоновані формули).
Правило вилучення знака заперечення в першому члені:
/ΦF,ΓG |- ΘQ
———————————
ΓG |- ΘQ, ΦF
Правило вилучення знака поєднання кон’юнкції в першому члені:
ΦF1*ΦF2, ΓG |- ΘQ
—————————————
ΦF1, ΦF2, ΓG |- ΘQ
Правило вилучення знака поєднання кон’юнкції у другому члені:
ΓG |- ΘQ,ΨY1*ΨY2
—————————————————————
ΓG |- ΘQ,ΨY1 ΓG |- ΘQ,ΨY2
Правило вилучення знака поєднання імплікації у другому члені:
ΓG |- ΘQ, ΨY1->ΨY2
—————————————
ΨY1, ΓG |- ΘQ, ΨY2
Правило поглинання:
ΦF,ΓG,ΘQ |- ΨY,ΛL ΦF,ΓG |- ΨY
————————————————————————
ΦF,ΓG |- ΨY
Правило відсікання:
ΦF1,ΛL,ΦF2 |- ΘQ ΓG |- ΨY1,ΛL,ΨY2
————————————————————————
ΦF1,ΦF2,ΓG |- ΘQ,ΨY1,ΨY2
В даному розділі монографії подано спосіб автоматизації всіх описаних етапів синтезу. При цьому був використаний декларативний характер логічного програмування, проведена автоматизація виконання символічних операцій зі збереженням послідовності дій, як у випадку синтезу, проведеного мануально, тобто безпосередньо людиною, без використання комп’ютерних засобів. Найважливішою проблемою проведеної таким чином автоматизації є відповідна специфікація правил виконання перетворень. Завдяки використанню декларативного підходу сама специфікація цих правил є одночасно і їх реалізацією. Це вимагає, між іншим, такого визначення термів, щоб вони якомога точніше відображували спосіб запису секвентів, який був використаний при їх безпосередньому (мануальному) перетворенні. Мається на увазі, що секвент, представлено у вигляді списку формул і знаків логічного включення. Це ілюструє рис. 1.
| 
