автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.13, диссертация на тему:Проектирование цифровых систем с использованием логического программирования

НАЦИОНАЛЬНА АКАДЕМ1Я НАУК УКРАШИ 1НСТИТУТ ПРОБЛЕМ МОДЕЛЮВАННЯ В ЕНЕРГЕТИЦ1

к.т.н. Януш Шайна (Польща)

' о

i

а,, УДК 681.33

ПРОЕКТУВАННЯ ЦИФРОВИХ СИСТЕМ 3 ВИКОРИСТАННЯМ ЛОГ1ЧНОГО ПРОГРАМУВАННЯ

Спсцтльшсть 05.13.13 - Обчислювальш машини, системи та мереж1

АВТОРЕФЕРАТ дисертаци на здобуття наукового ступеня доктора техшчних наук

Ки'Гв - 1999р.

LjA

Дисерташею е монограф1я.

Робота виконана у ф1рм! ADB (Advanced Digital Broadcast - Польща)

Офщшш опоненти:

д. т. н., проф. I.A. Жуков, заст. ректора КиУвського м1жнародного ушверситету цившьноУ авшщУ,

д. т. н., проф. В.Н. Коваль, зав. вщдмом 1нституту мбернетики ¡м. В.М. Глушкова HAH УкраУни,

д. т. н., проф. Ю.М. Короспль, зав. вщдшом 1нституту проблем моделювання венергетиш HAH УкраУни.

Провщна оргашзашя - Нацюнальний техшчний ушверситет "КиУвський Полггехшчний 1нститут" МЫстерства осв1ти УкраУни, КиУв, кафедра ЕОМ

сГО

Захист в'|дбудеться ¥ " 2000 р. о ^^ год. на засщанш

спешал1зованоУ ради Д 26.185.01 в 1нститут1 проблем моделювання в енергетищ НАН УкраУни

(252680, ГСП, КиУв-164, вул. Генерала Наумова, 15)

3 дисертацкю можна ознайомитись у б1блютещ 1нституту проблем моделювання в енергетищ HAH УкраУни.

Автореферат розюлано " ' " 1999 р.

Вчений секретар спещалЬованоУ ради Д 26.185.01

канд. техьпчних наук Е. П. Семапна

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

Актуальность робота

В останнш час спостер1гаеться штенсивне зростання юлькосгп po6iT, що потребують нових ¡нформацшних технологш автоматизованого проектування цифрових систем. Обумовлюеться цей зрют, насамперед, великою конкуренщею на електронному ринку, а також розповсюдженням пристроТв, вироблених малими сер!ями i призначених до конкретного застосування (пристроУ ASIC - Application Specific Integrated Circuit). Вимоги ринку, як i виробництво малих cepifi, вимагають пщвищення ефективносп проектування, тобто скорочення часу, необхщного для ш'дготовки проекту, та виконання ретельно'1 перевфки пристрою ще до початку його виробництва. Внаслщок цього виникла необхщшсть автоматизацп Bcix етап!в проектування, в тому числ! тих, для яких градицшш методи проектування мало ефективш.

У зв'язку 3i сказаним вище, все бшьшого значения набирають методи, як! принципово вщр1зняються вщ традищйних тим, що мають не числовий i не алгоршшчний характер. Вони базуються, головним чином, на використанш евристичного i символ!чного перетворень, як! широко використовуються у штучному ¡нтелекть

На думку автора, значш можливосл в цш сфер! створюе застосування лопчного програмування.

Лопчне програмування HHHi використовусться в багатьох р!зноман5тних галузях, таких, наприклад, як перетворення мови, керування, анаш фшансового ринку, в apxiTeKTypi, телекомушкацп, для перетворення эбраз!в i ¡нше. Проте, KpiM ¡снування природних зв'язюв з проектуванням цифрових систем, BWOMi з л1тератури приклади використання лопчного програмування в цш галуз! обмежуються елементарними зразками.

Метою монографп е усунення перел1чених прогалин.

Представлен! вище м!ркування стосуються, насамперед, двох головних задач, яким безпосередньо присвячена ця монограф1я, тобто :имвол!чному синтезу цифрових систем i динам!чному моделюванню, що враховуе 4acoei залежност!.

BiflOMi з лЬератури пращ, як! присвячеш безпосередньо символ!чному синтезу, мають елементарний, або фрагментарний характер.

В другому випадку, тобто при динам1чному моделюванш, вщом! iBTopoei npaui, пов'язан! з лопчним програмуванням, не виршують "фоблем реальних часових залежностей, а тшьки зв'язаш лопчно з :еквенщею нуль-одиниця, або одиничними змшами сигналу, а не з

вщображенням складних, взаемозалежних вектор1в багатьох сигнал1в. Е деяких ¡нших вщомих авторов! працях запропоноваш ршення, як1 маюи алгоритм1чний характер i стосуються анашзу одиничних часовю залежностей, а не складних д1аграм, або зв'язаш тшьки 3i специфшащею, i не з моделюванням даних залежностей.

Мета роботи

Метою дисертацн, зпдно з викладеним вище, е створення методолог! проектування i моделювання електронних цифрових систем : використанням лопчного програмування, зокрема, у визначенш можливост доповнення застосованих традицшних алгоритм1чних i числових методн методами евристичними i символшними.

Метою дисертацн з практично'/ точки зору е, передуам, створенш ефективних метод!в:

а) моделювання поведшки цифрових систем i процеав 3i складним{ часовими д1аграмами i розшзнавання таких д1аграм,

б) символ1чного синтезу цифрових систем.

Перша з тих проблем (моделювання i розшзнавання часових д1аграм становить спробу нового розв'язання одшеУ з дуже трудомютких задач пов'язаних з моделюванням систем високого р!вня ¡нтеграцп (VLSI) i < темою праць автора, яю були виконаш в останнш час.

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

Зв'язок роботи з науковими програмами i дослщними планами

1деУ, як1 представлен! в монографп, виникли в межах наступим: науково-дослцших програм.

СРВР 02.20: Впровадження програмованих лог'тних структур у цифрови: системах та вишрювальних приладах. 1985-1990. Полггехшк; Зеленогурська. В рамках Центрального Плану Головних Дослщжен] М1н1стерства Науки i ВищоУ Освгги Полыщ. Роль автора: безпосереднш учасник i заступник кер!вника теми. COHERENCE S-JEP по 07648 i S-JEP по 0449 (Structural Joint Europeai Project). 1990-1996. Проект фшансований ввропейською Ушею Робота над проектом проводилася спшьно з: (а) Ушверситетом i

BpicTcmi, Анпшя; (б) Ушверситетом в Манчестер!, Анпшя; (в) Полггехшкою Зеленогурською, Польща. Роль автора: кер1вник науковоТ теми з польськоУ сторони. Artificial Intelligence Based Stock Exchange Analyzer. 1991-1992. За умовою Kinetic Capital Corporation, Сиетл, США. Роль автора: безпосереднш учасник i кер1вник теми. Audio and Video Compression. 1992. Центр Проектування 1нтегральних Юл INMOS. Image Processing Unit, Анпня.

Роль автора: член колективу, вщповщальний за частину проекту, яка стосуеться моделювання складних часових залежностей. Виконаш теми автором: (a) Behavioral model of Generic Video RAM Device, (6) Timing model of MPEG Decoder. Behavioral Model of STi 3240 Video Decoder. 1993-1994. Полггехшка Зеленогурська. За умовою SGS-Thomson Microelectronics. Image Processing Business Centre, Гренобль, Франщя. Роль автора: безпосереднш учасник i кертник теми. Transputer Based Intelligent Management System for Interactive TV Digital Satellite Receiver. 1995-1996. Гкштехшка Зеленогурська. За умовою SGS-Thomson Microelectronics, Asia-Pacific Branch, CiHranyp. Роль автора: безпосередшй учасник i кер1вник теми. IRD: Integrated Receiver-Decoder for Satellite TV. 1997-1999. Advanced Digital Broadcast, Польща. За умовою ф1рми Broadcast Software Systems International, Тайвань.

Роль автора: науковий кер1вник i координатор теми.

Наукова новизна здобутих результате

До найважливших наукових досягнень автора, вщбитих у монографп необхщно вщнести:

1. Розробка методологи проектування i моделювання цифрових систем з використанням лопчного програмування, зокрема, демонстращю иожливосп доповнення традицШних алгоритм1чних i числових методш гвристичними i символ!чними методами.

2. Створення нового, орипнального методу розшзнавання часових Гаграм, який мае декларативний характер i базуеться на використанж застосованих в штучному ¡нтелек™ метсиив пор!вняння з еталоном i метапрограмування.

3. Створення мови моделювання, яка дозволяе ефективно проектувати «одел! цифрових систем i процеав 3Í складними часовими дтграмами.

4. Застосування лопчного програмування до автоматизащ символьного синтезу цифрових систем, описаних за допомогою лопчни: секвенцш (cnoci6 pe&imaui'i под1бний до автоматичного доведения теорем використанням правил лопчних висновюв i евристичних правил).

5. Створення на ocucmi розроблених теоретичних метод1В V: практичноУ реал1зашУ, яка свщчить про придаттсть запропонованих методп до розв'язування реальних, складних задач в сфер! проектування моделювання цифрових пристроУв.

Практичне значения отриманих результате

Результати робгг, зв'язаних з автоматизащею символ1чни: перетворень лопчних виразт (роздш 3 монограф1У), а також символ1чнш синтез (розд1п 4) були використаш при розробщ системи CAD LOGIC, як: призначена для комп'ютерного забезпечення проектування цифрови: систем з програмованими лопчними структурами PAL i була створена ; 1989-1990 р.

Результати po6iT, зв'язаних з розшзнаванням часових д1аграм i мовон Pro Waves (роздш 6), були використаш на практищ для побудови моделе! динам1чноУ пам'ят!, пристрою декодера зображення i протокол!] комушкащУ, як1 були створен i у межах робгг, проведених колективом очолюваним автором в 1992-1997 роках, для SGS-Thomson Microelectronic Asia-Pacific Branch, а також Broadcast Software Systems International.

В останшй час роботи автора, зв'язаш з розшзнанням i мoдeлювaння^ складних часових д1аграм, були використаш для проектування штегральни; пристроУв високого р1вня ¡нтегращУ ASIC, призначених до використання i ¡нтерактивному цифровому телебаченш i при проектуванш супутникови: телев1зшних приймач1в-декодер!в за вимогою ф!рми Asia Digital Broadcas для ринкт Австрал1У, ГПвденно-АфриканськоУ республ1ки, 1спани, ТаУланду 1зраУлю.

ОсобливоУ уваги заслуговуе проект виконаного на високому piBH ¡нтегращУ пристрою ADB Phase II Signal Processor (PSP), а також пристрон Bili-I Fast Descrambler.

Пристрш PSP - спешал1зований процесор цифрових телев!зшни; сигнатв, що реалЬуе, мш ¡ншими, функцп: 6iTOBOi' i байтовоУ корекщ помилок, розкладання потужност! цифрових сигналш на компоненти, , також декодування i транскодування сигналш. ПристрЫ PSP забезпечу роботу приймача ¡нтерактивного цифрового телебачення у двох найбшьи популярних нин1 системах передач! сигналу: DVB (Digital Videi Broadcasting) в Сврош i Orbit (Scientific Atlanta Compression System Phase II

у США. Система працюе з максимальною частотою 120 мгГц i складаеться з 40 тисяч ком1рок. Проект системи виконано сшльно з проектними бюро ф1рми SGS Thomson Microelectronics (США, 1тал1я). Автор був вщповщальним за виконання модел! системи PSP, а також брав участь в анал1з1 часових залежностей системи.

Система Bili-1 е декодером для цифровоУ супутниково'У системи передач! сигнал1в, кодованих у формат! ф!рми IRDETO. ПристрШ працюе з частотою 60 мгГц i складаеться з 35 тисяч KOMipoK. Автор виконав анал1з часових залежностей роботи пристрою на окремих етапах його проектування. До кшця 1999 року ф^рма SGS Thomson Microelectronics випустить 130 тисяч пристроТв Bili-I. Вже кшька мюящв пристрш використовуеться у новш генеращУ супутникових приймачш-декодер!в.

Особистий внесок автора

В области розшзнавання часових fliarpaM високоУ складносп автор вапропонував новий, орипнальний метод, який дозволяе принципово :простити створення моделей цифрових систем високого р1вня ¡нтеграцп VLSI, а також р1зномаштних npoueciB, описаних за допомогою складних часових fliarpaM. За рахунок використання можливост1 лопчного програмування в межах метапрограмування i пор1вняння з еталоном, а гакож використання символьного перетворення була отримана можлив!сть простого перетворення опису часових д1аграм на прологов! описово-моделююч! правила.

3 метою nepeeipKH результатт теоретичноУ роботи автор розробив :истему розшзнавання часових fliarpaM i мову моделювання цифрових дристроУв i npouecie. Цю мову автор використав шзшше на практищ для дроектування складних цифрових систем, що призначеш, головним чином, до застосування у цифровому супутниковому телебаченн!.

В сфер! символ!чного синтезу цифрових систем автор запропонував зикористання лопчного програмування для автоматизащУ синтезу дристроУв, описаних за допомогою лопчних секвент!в. Такий шдхщ дозволив створити комплексний апарат синтезу, що охоплюе проблему - вщ зпису npaui системи до декомпозищУ к!нцевого опису пщгруп, яю можна шроваджувати у ф1зичних елементах.

У частиш, присвячежй трансляци специфжащУ пристроУв, автор «водить методи штучного штелекту, що застосовуються в ¡нших галузях, ю галузей, зв'язаних з проектуванням i моделюванням цифрових пристроТв.

KpiM того, автор представив в po6oTi BiflOMi з л^ератури класичш ¿етоди специф!кащУ i моделювання цифрових систем за допомогою

лопчного програмування в узагальненш 1 розширешй автором форм] завдяки чому отримано стисле 1 комплексне подання цшоТ тематики.

Апробащя результате

Головш науков1 досягнення \ практичш результати пращ бул! представлен! на конференщях 1 семшарах в Полыщ1 за кордоном. В Польш в мютах: Зелена Гура, Шклярська Поремба, Люблш, Торунь, Вроцлав Гданськ, Варшава. За кордоном на м1жнародних конференщях на Украш (Ки1'в), в Словаки (Братислава), в Ншеччиш (1лменау 1 Дрезден), Франщ (Гренобль) 1 у Сшгапурь

Публшаци

По тем1 дисертащУ були опублковаш 41 наукова робота, серед яких ! монографи (без сшвавтора), 2 книги, опублковаш в найбшьш престижних ; Полыщ наукових видавництвах, тобто Рашг'^уо'л'е Wyda'wnictwo Каиков1' (без сшвавтор1в) 1 Wydawnictwa Naukowo-Techniczne (автор 1 науковш редактор), а також 33 статп, серед яких 11 без сшвавтор1в.

Структура I обсяг роботи

Робота складаеться ¡з вступу, шести роздшв, заверешення, висновюв списку використованоТ л!тератури. В щлому монограф1я мютить 24( сторшок, 26 рисунюв, а також 11 таблиць 1 д1аграм.

ЗМ1СТРОБОТИ

Розд1л 1. Вступ

В роздш подано вступ до галуз1 лопчного програмування, виконан< огляд л1тератури, сформульована основна мета роботи та визначена галуз наукових дослщжень, визначено практичне значения 1 показано зв'язо виконаноТ роботи з науково-дослщними програмами.

Роздш 2. Основш методи спецнф1кацп \ моделювання цифрових систем

В роздш подаш в'щош з л1тератури класичш методи специфшащТ моделювання цифрових систем за допомогою лопчного програмування узагальненш 1 розширенш автором форми У розглянутих випадках лопчн програмування використовуеться як мова специфжацн так 1 моделюванш

Опис пристро'ш подано безпосередньо в форм1 клаузул або прологових гер\пв, a ïx властивост! виводяться за допомогою безпосередньо'1 лопчноУ цедукцп. Метою роздшу е, з одного боку, представления вище викладених метод1в, а з другого - подання основного мехашзму, на якому грунтуеться попчне програмування.

Розд1л 3. Символ!чн1 операцн

В роздш представлена проблема автоматичного перетворення попчних вираз!в, що використовуються в проектуванш цифрових пристроТв. Показано, що, завдяки декларативному характеру лопчного програмування, 1втоматизащя символ1чних перетворень може бути простою i натуральною. Сам опис проблеми, поданий в конвенцп лопчного програмування, е майже э!внозначним з його ¡мплементащею, а окрем1 предикати е трупами клаузул, южна з яких вщповщае визначеному правилу евристичного перетворення зираз1в i не залежить вщ р1вня складност1 цього виразу.

Оскшьки бшышсть проблем, зв'язаних з проектуванням цифрових систем, можуть бути виршеними за допомогою евристичних метод1в та перетворень символ1чного характеру вщпов'шно, даш методи автоматизацп леретворень можуть мати широке i р1зноб1чне застосування. Однак, перед y'ciM, методи, що подаш в цьому роздш, е вихщними для piuieHb, зикладених в наступних роздшах.

Роздш 4. Автоматизация символ1чного синтезу цифрових систем

В роздш розглянуто cnociô використання лопчного програмування 1ля реал!зацп' символ!чного синтезу цифрових систем, описаних за lonoMororo лопчних секветчв.

Представлене ршення проблем автоматизацп npoueciB: а) нормал1защ'1 секвешчв способом под!бним до автоматичного доведения георем з використанням правил лопчних висновюв, (б) м1шм1зацп опису з зикористанням евристичних правил, (в) синтезу до вигляду, що вщповщае структур! використовуваних елементт - символьные перетворення, (г) хекомпозицп' опису системи на тдгрупи, як1 можна використовувати в жремих ф^зичних елементах - вживання мехашзму пошуку апарату

îhchobkîb.

Метод символ1чного синтезу цифрових систем, поданий у цьому юздш, було використано в систем! CAD LOGIC, призначенш для 1роектування цифрових елеменлв з використанням програмованих юпчних структур.

Як вже було зазначено, у синтез! був застосований гпдрахуно] лопчних елемешчв секвенлв. Вщносно до цифрових систем можн; припустити, що секвент е умовним поняттям, в якому "умова" визначен; комбшащею вибраних вхщних сигналт. Поява тих сигнал ¡в обумовлю реалвашю операцИГ, яка записана з правого боку знаку включения (" ) - я: "наслщок". Наприклад, опис за допомогою секвешчв 4-б1тового репстру що виконуе операцн: установления на виходах одиниць, паралельний запи* даних, зсув вл!во 1 зсув вправо, можна представити в виглядк

/е.1*/в0 |- @д3*@д2*@д1*@д0,

/в1*б0 |- (х3->@д3)*(х2->@д2)*(х1->@д1)*(хО->@дО) , з1*/з0 I- (д2->@дЗ)*(>@сз2)*(д0->@д1)*(вхЛ->@дО), з1*э0 |- (вхПр->@дЗ)*(дЗ->@д2)*(д2->@д1)*(д1->@д0).

Головною частиною процесу проектування е перетворенн: початкового опису функцюнування системи, поданого за допомогон секвенлв, до вигляду, вщповщного структур! елемент1в, передбачених дл. використання. Оскшьки було прийнято, що будуть застосовуватис елементи PAL, завдання полягае у видшенш з секвент!в знаюв !мпл!кацн р!внозначност!, а також здШсненш таких перетворень, при яких кожнш секвент вщтворював би залежност! вихщних сигн&шв вщ вхщних у вигляд1 в!дпов!дному елементам PAL.

Цей процес можна реал!зувати в три етапи. На першому етап виконуеться так звана нормал!защя секвент!в шляхом вилучення з них bcí: лопчних поеднань. На другому - виконуеться м!шм!защя вихщних функщ£ На третьому - проводиться синтез секветтв до вигляду, вщповщног структур! систем PAL. Наприклад, для групи секвент!в:

/si * /so |- (al->yl)*(аО->уО), /si * sO |- (Ы->yl)*(Ь0->у0),

де:

хЗ, х2, xl, хО

-паралельш входи,

- П0СЛ1Д0ВНИЙ BXÍfl при 3CyB¡ ВЛ1В0,

- послщовний вх1д при зсув! вправо, -виходи,

- знак, передуючий виходам в наступному стан!.

вхЛ

вхПр

д3, q2, gl, д О

®

81 * /во |- (с1->у1)*(СО->уО), 81 * бО |- у1 * уО.

иормшшащя приводить до наступного виду:

аО |- уО,з1,э0

а1 1 - у1, 81, 80

ЬО, э0 1 - уО, 81

Ы, БО 1- У1,з1

СО, 81 |- уО,эО

с1, в1 |- у1,80

81,80 1- У1

Б1 , э0 1- уо

По™, з метою виконання мЫм1зацп залежност1 вихщних сигнашв зщ вхщних, необхщно, насамперед, перетворити секвенти таким чином, цоб вони явно виражали Т1 залежносп. Для цього необх'щно, щоб в другому ■шеш виразу секвента залишилися тшьки т1 сигнали, ям представляють эезультати операци:

аО,/80,/з1 1- уо

а1,/50,/э1 1- у1

ЬО, 80,/Б1 1- уо

Ы, 80,/81 1- у1

СО,/эО, 81 1- уо

с1,/з0, Э1 1- у!

ЭО, э1 1- у1

ЭО , 81 1- уо

На цШ шдстав! шсля \пшм1зацп утворюються наступи! секвенти, що дредставляють можлив1 елементарш залежност1 вихщних сигнагив вщ зхщних:

ьо, бо 1- уо

Ы, 80 I" У1

СО, 81 1- уо

С1, 81 1- У1

аО,/аО,/э1 1- уо

а1,/эО,/б1 1- У1

эО, э1 1- У1

80,31 1- уо

На черговому етат синтезу виконуеться вщповщне об'еднанн. секвештв таким чином, щоб отриманий запис вщповщав безпосередны структур! елемент1в PAL:

sO*sl + al*/sO*/sl + el* si + bl*sO |- yl sO*sl + aO*/sO*/sl + cO*sl + bO*sO |- yO

Останшм кроком (декомпозищя опису) е подш секвенпв на пщгрупи кожна з яких може бути використана в одному елемент1 PAL. Цей поди повинен бути виконаний так, щоб забезпечити оптимальне використанн: елеметтв.

Найбшьш важливими роздшами синтезу е нормал1защя секветтв мшш1защя опису. Нормал1защю секвекпв можна виконати способом под1бним до автоматичного доведения теорем, якщо використати при цьом; формальний математичний апарат у вигляд1 правил bhchobkíb Гентцена МЫмшшю слщ проводити евристичним способом, застосовуючи правил поглинання i вщакання. Нижче подаш приклади обох зазначених rpyi правил, представлених у формальному запису (окрем1 грецьк1 лггер] означають пропоноваш формули). Правило вилучення знака заперечення в першому члеш:

/Ф,Г |- 0 Г |- 0, Ф

Правило вилучення знака поеднання кон'юнкщУ в першому члеш:

Ф1 *Ф2, Г |-б>

Ф1, Ф2, Г 1-0 Правило вилучення знака поеднання кон'юнкщУ у другому члеш:

Г |- 0, ¥1*¥2

Г |- 0, 91 Г |- 0, Т2 Правило вилучення знака поеднання ¡мшикашУ у другому члеш:

Г |- 0, Т1-> ¥2

Т1, Г I- 0, Ч>2

Правило поглинання:

Ф,Г,0 I- «Р. Л Ф.Г |- У

Ф,Г I- f

Правило вшакання:

Ф1.Л.Ф2 |-0 Г\-Ч'1,А,Ч>2

Ф1.Ф2.Г |- 0, ¥7, ¥>2

В даному роздш монограф!1 подано cnoci6 автоматизаци ecix описаних етап1в синтезу. При цьому був використаний декларативний характер лопчного програмування, проведена автоматизашя виконання символ1чних операцш 3i збереженням посльцовност! дШ, як у випадку синтезу, проведеного мануально, тобто безпосередньо людиною, без використання комп'ютерних засоб1в. Найважлив!шою проблемою проведено!' таким чином автоматизаци е вщповщна специфжащя правил виконання перетворень. Завдяки використанню декларативного пщходу сама специфкащя цих правил е одночасно i Тх реал!зашею. Це вимагае, м1ж шшим, такого визначення терм1в, щоб вони якомога точшше вщображували cnoci6 запису секветтв, який був використаний при Тх безпосередньому (мануальному) перетворенш. Маеться на уваз1, що секвент, представлено у вигляд1 списку формул i знак1в лопчного включения. Це ¡люструе рис. 1.

negated variable clause variables

/si * sO |- ( al -> yl ) * ( aO -> yO ) ^_(_/ ^-,_^ -__-formula clause clause

formula

Рис. 1. Складов! елементи секвента

Вщповщш терми можуть мати у цьому випадку наступний вигляд:

sequent = sequent_element*

sequent_element = formula ( formula_elements ); sequence_sign

Беручи до уваги прийнят! визначення формули, а також застосовуючи рекуренщю, терми, що описують складов! формули, можна представити у иаступному вигляд!:

formula_elements = formula_element* formula_element = variable ( variableName );

negated_variable ( variableName ); conjunction ( conjunction_sign ); clause ( formula_elements ); negated_clause ( formula_elements ) variableName = symbol conjunction_sign = symbol

При такому визначеш терм1в запис секветчв, поданих на рис. 1, буде:

[ formula ( [ negated_variable ( "si" ), conjunction ( "*" ), variable ( "sO" ) ] ), sequence_sign,

formula ( [ clause ( [ variable ( "al" ),

conjunction ( "->" ), variable ( "yl" ) ] ), conjunction ( "*" ) , clause ( [ variable ( "aO" ),

conjunction ( "->" ), variable ( "yO" )])])]

Cnoci6 автоматизацн процесу синтезу подано на приклад1 правил; вилучення знака заперечення у першому члеш виразу:

а,/Ф,Г |- <9 а,Г |- в, Ф

Це правило повинно бути використане, якщо першон неелементарною формулою у секвента е формула, яка мае тшьки змшну з знаком заперечення, або вираз 3i знаком заперечення.

Нижче подано словесний опис способу застосування розглянутоп правила, який використовуеться при мануальнш реал1зацн. 1. Необхщно видшити в перетворюваному секвент1 три наступш частини:

I - послщовн1сть елементарних формул, ¡снуючих перед розгляданою

формулою, що мае оператор заперечення (а),

II - формулу, що мае елемент заперечення (/Ф),

III - решта частини секвента, що мае знак лопчного включения (Г |- 0).

14

2. Частину I необхщно поеднати з частиною III.

3. У кшщ послщовност!, створено"! в пункт! 2, необхщно дописати формулу з частини II, позбавлену, проте, знака заперечення.

Клаузули, як! в!дпов!дають поданому вище словесному опису, маготь наступний вид:

a) для змшнок

rule ( Parti,

[ formula ( [ negated_variable ( Name ) ] ) | Partlll ],

NegationSign_in_predecesor, [ NewSequent ] ) append ( Parti, Partlll, NewBeginning ),

append ( NewBeginning, [ formula ( [ variable ( Name ) ] ) ], NewSequent ).

b) для виразу:

rule ( Parti,

[ formula ( [ negated_clause ( Content ) ] ) | Partlll ],

Negationsign_in_predecesor, [ NewSequent ] )

append ( Parti, Partlll, NewBeginning ),

append ( NewBeginning, [ formula ( [ clause ( Content ) ] ) ], NewSequent ),

де предикат

rule ( sequent, sequent, sequentSide, sequents ), мае наступи! параметри:

частина I перетворюваного секвента, частина II i III,

б!к секвента, з якого знаходиться знак заперечення, результат використання правила.

Перший параметр, тобто послщовшсть елементарних формул hí початку секвента, видшяеться при використаш допом1жно'1 клаузул! предикату

rule ( Parti, [ formula ( [ variable ( N ) ] ) | Rest ], SequentSide, Resuit )

append ( Parti, [ formula ( [ variable ( N ) ] ) ], NewPartI ), rule ( NewPartI, Rest, SequentSide, Resuit ).

Як видно, запис правила докладно вщповщае словесному опису, : единим додатковим предикатом, що застосовуеться в операцшних частина) клаузул, е стандартний предикат append.

Аналопчно виконуеться решта правил синтезу, що по суп < автоматизацию усього описаного процесу.

Роздш 5. Перетворення опису цифрових систем

Цей роздш мае допом!жний характер. Bíh присвячений проблем перетворення (трансляцп") опиав цифрових систем.

В npoueci проектування транслящя часто мае велике практичж значения, тому що дозволяе використовувати pÍ3H¡, не зв'язан безпосередньо пом1Ж собою, засоби комп'ютерного забезпечення.

В роздш показано, що застосування лопчного програмуванш дозволяе провести звичайну замшу одше'Г форми опису пристрою - шшою нав-1ть тод'1, коли обидв'] форми дуже складн'1 i р1зномаштш.

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

Характерною рисою методу е натуральшсть i простота використання а також те, що окрем1 предикати i клаузули е простим вщбиттял вщповщних словесних опис1В, або формальних специфшацш, наприклад синтактичних д1аграм. Завдяки цьому, слушшсть ¡мплементацп' < очевидною, а можлив1сть помилитися - дуже мала. Kp¡m того, транслято[ також може просто модифжуватися i розбудовуватися через змшу абс доповнення одиничних клаузул, наприклад, в випадку розширенн) початкового опису.

В роздал! використано приклад перетворення опису, поданого з; допомогою списку поеднань у формам Intergraph, до опису на mobí VHDL.

Метод був використаний для конструювання описово-моделюючих правил мови моделювання Pro Waves, представлених в шостому роздш.

Роздш 6. Розшзнавання часових Д1аграм

Одшею з основних проблем, ¡снуючих при проектуванш i моделюванн'1 ¡нтегральних систем високого р1вня штегращУ VLSI, е проблема дотримування часових вимог м1ж Д1аграмами окремих вхщних i вихщних сигнашв. Hi вимоги можуть бути дуже складними з урахуванням того, що одиничний елемент VLSI може виконувати багато р1зних функцш, а також беручи до уваги складшсть окремих еталонних д1аграм. Через те модел1 роботи бшьшост! елеменлв VLSI або протоюшв комушкащУ, що написаш традищйним способом, наприклад, за допомогою мови VHDL, можуть мати багато тисяч лшШ, а Ух шдготування може бути надто трудомютким.

В цьому роздш представлено новий, орипнальний метод моделювання роботи (behavioral simulation) цифрових пристроУв високого р1вня штегращУ VLSI, а також процесш, що вщбуваються в цих цифрових системах, як1 характеризуються складними часовими залежностями. Приклад таких залежностей подано на рис. 2.

Запропонований метод дозволяе значно скоротити час приготування моделей i, тим самим, скоротити процес проектування пристрою.

В цьому метод1 розшзнавання часових д1аграм виконано методом пор1вняння з еталоном i застосуванням метапрограмування.

Завдяки цьому задача зводиться до типово декларативного виду. Це дозволяе принципово зменшити р1вень труднощ'ж i час, необхщний для створення модели а завдання проектувальника обмежуеться виключно формальним записом еталошв часових д!аграм, без необхщносп використання будь-якого алгоритму.

Метод використовуеться до побудування мови опису i моделювання fliarpaM Pro Waves (Prolog based system for Waves recognition), що працюе спшьно з мовою VHDL. Мова мае велике практичне значения i була використана, м1ж ¡ншими, для побудови модел1 динам!чноУ пам'ят! VRAM, ¡нтерфейсноУ системи декодера зображення (MPEG Video Decoder), моделювання протокол1в комушкащУ з трансп'ютерними системами, а також для проектування спещал1зованих ¡нтегральних пристроУв, як1 використовуються в цифровому телебаченш. Зпдно з ¡нформашею, вщомою з лггератури, а також власних праць автора, процес створення таких моделей традищйним способом, за допомогою мови VHDL, тривае часто майже м!сяць. В випадку використання розгляданого методу час створення можна скоротити до кшькох дшв.

Рис. 2. Приклад складних часових залежностей в ¡нтегральному пристро VLSI: одна з кшькох часових д1аграм динам1чноУ пам'ят1 DRAM page early write cycle.

В розгляданому метод1 опис часових залежностей, ¡снуючих у еталон циклу, подшений на групи i зв'язаний з головними под!ями циклу, як називаються подыми вщнесення. Для кожноУ такоУ nofli'i, в залежносп ви необхщносп, може бути подана трупа значень час1В, зв'язаних з нек лшоб1чним (leftSideGroup), правоб1чним (rightSideGroup), а такой двоб1чним способом (bothSideGroup). Загальний, формальний запис кожноУ з труп е наступний:

leftSideGroup( ReferenceEvent ) ->>

t ( TimeName, BoundaryEvent ) { , t ( TimeName, BoundaryEvent ) }; 18

rightSideGroup( ReferenceEvent ) ->>

t ( TimeName, BoundaryEvent ) { , t ( TimeName, BoundaryEvent ) },-

bothSideGroup{ ReferenceEvent ) ->> t ( TimeName,

LeftBoundaryEvent, RightBoundaryEvent ) { , t ( TimeName,

LeftBoundaryEvent, RightBoundaryEvent ) };

де:

- псотя гранична - e другою з подш, яка обмежуе даний час вщповцшо з л1вого або з правого боку вщносно до nofli'i вщнесення,

- тва под!я гранична i права под1я гранична е под1ями, ям обмежують даний час; цей час належить до двоб1чноТ групи, вишовшно з л!-вого i правого боку в ¡д нос но до поди вынесения,

- дужки ("{}") означають можливють появи в даному фрагмент! нуля, один або багато разш.

Поди записуються зпдно з наступною схемою:

event( SignalName,

PriorToChange_SignalValue, AfterChange_SignalValue )

Граничш под1У можуть мати також невизначений характер, наприклад,

event (Add,_). Це можливе в наступних випадках:

- 1стотним е сам факт змши сигналу, а не його виду.

- 1стотним е те, що змша сигналу не вшбуваеться у визначений ¡нтервал часу, поза яким цей сигнал може змшюватися, або бути незмшним. В цьому випадку визначення "под1я гранична" мае характер умовний, i мае значения меж1 ¡нтервалу. Под!я, як така, що приймаеться як змша сигналу, може в шлому не вщбутися. Така ситуашя мае Micue, наприклад, при адресних сигналах.

На рис. 3 поданий приклад еталона циклу, а також вщповиний

формальний запис.

а)

RAS

CAS

^ tASR

ADD

zx

^ tRAH

6)

V

>czzx

Column

Г

X

leftSideGroup (event (RAS, 1, 0) ) -» titCRP, event (CAS, 0,1)),

t (tASR, event (Add, _,_)) ;

rightSideGroup(event(RAS,1,0)) ->> t(tRAS, event(RAS,0,1)),

t(tRAH, event(Add,_,_));

leftSideGroup (event(CAS,1,0)) ->> t(tACS, event(Add,_,_));

bothSideGroup (event (CAS, 1, 0)) -» t(tAR, event (RAS, 1, 0), event (Add,

Рис. 3. Фрагмент еталона циклу, а також вщповщний формальний запис: (а) часова д1аграма; (б) формальний запис циклу

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

Задачею створення правил е розшзнавання виду циклу шляхом пор1вняння зм1н вхцщих сигнал1в з еталонами р1зних цикл1в, а також ¡шшювання передач! даних, зв'язаних з роботою пристрою, що моделюеться.

Метапрограмування - це мехашзм, який дозволяе програм1 конструювати ¡ншу програму \ виконувати и, або може в процеа своа роботи виконувати самомодифшащю, тобто змшювати фрагмента свого власного коду. Цей процес описано у встуш до розгляданого роздшу.

На другому eTani вщбуваеться необхщна щентифжащя, яка виконуеться за допомогою правил, що були створеш на першому еташ. У випадку змши будь-якого з вхщних сигнал1в вщбуваеться модифжащя поточного часу моделювання, вщновлення бази даних, яка мштить атрибути сигнал1в, а також вщновлення клаузул, що описують лшо-, право-, i двоб1чш групи 4aciB. Дал1 проводиться перев1рка на вмют в баз! даних опис!в, яю вщповщають Л1Воб1чшм часам. Уа вщтинки часу, необхщш для щентифжацп якогось циклу, перев1-ряються одночасно на вмют в баз1 даних подш, пов'язаних, з виконанням право - i двоб1чних час1в, а також перев1ряеться ¡нформащя про невиконання на якомусь з bwthhkib часу подп, пов'язаноУ з цим циклом.

Нижче подано приклад правила-клаузули, створено!' для лтоб1чно1 групи фронту, еталону циклу, поданого на рис. 3.

Формальний запис л1воб1чно1 групи, що метить два часи (tCRP i tASR):

leftSideGroup ( event ( RAS,1,0 )) ->> t ( tCRP, event (CAS,0,1)),

t ( tASR, event (Add,_,_));

ae: timeRange ( tCRP, min (10), max(_) ).

timeRange ( tASR, min ( 0), max(_) ).

Генероване описово-моделююче правило:

LeftSideGroup % tCRP, :- currentTime ( TO ), event ( last, "RAS", event ( last, "CAS", A is T0-10, T1<=A,

event ( last, "Add",

B is T0-0,

T2<=B.

tASR

change ( 1,0 ), TO ),

change ( 0,1 ), T1 ),

change (_,_), T2 ),

» tCRP

% <----->

% tASR

% <----------->

» RAS -----------------

* CAS ---------

% Add XXXX==============

% T2 T1 TO

Розгляданий метод ¡дентЦнкаци був використаний до побудови мови эпису i моделювання д1аграм Pro Waves (Prolog based system for Waves •ecognition). Ця система призначена для сумюноУ роботи на мов1 VHDL i служить для моделювання роботи (behavioral simulation) цифрових систем 3i жладними часовими д1аграмами.

Модельований елемент описуеться в щй систем! за допомогою групи еталонних цшшв (CYCLE), аналопчно тому, як то мае Micue в випадку техшчноУ документащУ пристрою, наприклад, опис елементу DRAM м1стить, мЬк ¡ншим, наступи цикли: read, early write, late write, read-write, page early write, та iHiui.

Опис кожного з еталонних циюйв починаеться вщ подання необхщних кшцевих умов початку циклу, тобто визначення першоТ поди вынесения, юнуючо'У у цьому цикл!, а також стану шших сигнал!в у момент надходження uie'i под!У. Наприклад:

start_conditions ( event ( RAS,1,0 ), WE=0, CAS=l )

Опис еталона даного циклу може бути подшений на частини (PART). Вони в!дпов!дають тим фрагментам еталона, ям виявляються секвентно. Черговють запису частин в еталош циклу вимагае необхщну черговють виникнення фрагмент!в поточного циклу.

Подш на частини дозволяе дуже просто описувати фрагменти циклу, що повторюються. Одиничш частини супроводжуються декларащею part_type (single). Частини, що повторюються - декларащею part_type(repetitive).

Найважлившими фрагментами опису даного еталона е тша опиав окремих частин. Це т!ло створено ¡з запис!в вщповщних груп л!во-, право- i двоб!чних час1в, у вщповщност! з !нструкц!ею пщ назвою action. Задачею ¡нструкцп е швдювання передач! даних. Сама передача виконуеться модулем опису системи, написаному мовою VHDL (рис. 5). Модуль, написаний мовою Pro Waves, ¡шщюе цю передачу шсля розшзнавання фрагмента вщповщного циклу. 1нструкщя action мае наступний загальний вигляд:

action ( ActionName, ConnectedWithAction_ReferenceEvent )

Ьпшювання передач! даних вщбуваеться тод!, коли виконан! yci niBo6i4Hi часи, що зв'язан! з под!ею в!днесення названою paнiшe в ¡нструкцп action, а також yci л!воб1чш часи, що зв'язан! з под!ями вщнесення, що виникали рашше в опису еталона даного циклу. Зважаючи на це, ¡стотним е необх^шсть того, щоб чергов!сть запису л!воб!чних груп в1дповщала черговост1 появи Ух подш вщнесення в еталош циклу.

Нижче подано приклад формального запису еталона циклу в систем! Pro Waves. Це е опис поданого на рис. 4 спрощеного еталона циклу Two-Byte Register Read системи декодера зображення MPEG2 STi3500.

Two - Byte Register Read Cycle

АЙУ

F.ven АНЛрм

OHH AHde«

CDS TR mist be hi gh

Рис. 4. Спрощений еталон циклу Two-Byte Register Read системи декодера зображення MPEG2 STi3500 ф!рми SGS-Thomson

WAVE_DESCRIPTION MPEG_DekoderVideo_modulProWaves; signal ( DATA, ADD, nWAIT, nCS, RnW, nCDSTR );

tSHRX:min( 5 ns tSHSL:min(20 ns tSHWZ:min( _ tSLWD:min{ tSLWH:min( tSLWL:min( _ tWHAX:min( 0 ns tWHDV:min(10 ns tWHSH:min( 0 ns

rime(tAVDV:min( _ ),max(20 ns tAVSH:min< 5 ns),max( _ CAVSL:min( 5 ns),max( _ tDVSH:min( 5 ns),max( _ tDVWH:min( 5 ns),max( _ tRVSL:min( 5 ns),max( _ tSHAX:min( 5 ns),max( _ tSHDI:min(10 ns),max( _ tSHDX:min( 5 ns),max( _ action) Read_HigherByte_Address, Read_LowerByte_Address, SendToBus_HigherByte, SendToBus_LowerByte,

Generate_nWAlT_l_0_l_Read2_Signal,

Generate_nWAIT_Z_Read2_Signal );

^YCLE Two_Byte_Register_Read;

start_conditions { event ( nCS,l,0 ), nCDSTR=l, DATA=Z );

3EGIN

,max( _ ) ,max( _ ) ,max(10 ns) ,max(10 ns) ,max(50 ns) ,max(25 ns) ) )

, max ( , max ( , max (

) ) ;

RnW=1, nWAIT=Z,

PART OnePartCycle;

part_type ( single )

tAVSL,event(ADD,_,_)), tRVSL,event(RnW,0,1)); tSLWH,event(nCS,0,1)), tDVWH,event(ADD,_,_)); tAVSH,event(ADD,_,_)), tDVSH,event(DATA,_,_)); tSLWL,event(nWAIT,1,0)), tSLWD,event(nWAIT,Z,1)); tWHAX,event(ADD,_,_)), tWHDV,event(DATA,_,_)); tSHAX,event(ADD,_,_)), tSHRX,event(RnW,1,0)), tSHSL,event(nCS,1,0)), tSHWZ,event(nWAIT,l,Z)), tSHDI,event(DATA,_,_)), tSHDZ,event(DATA,_,Z));

action ( Generate_nWAIT_l_0_l_Read2_Signal, event (nCS,1, , 0 ) )

action ( Read_HigherByte_Address, event (nCS , , 1, .0)

action ( SendToBus_HigherByte, event (nCS , -1, .0)

action ( Read_LowerByte_Address, event (nWAIT, .0, .1)

action ( SendToBus_LowerByte, event (nWAIT, . 0, ,1)

action ( Generate_nWAIT_Z_Read2_Signal, event (nCS , .0,1)

end;

END; --of_CYCLE; END. --Of DESCRIPTION.

Як вже зазначалося, р1вень складносп часових залежностей, щ< можуть виникати мгж сигналами елемент!в високого р1вня штеграцн спричиняе те, що створення вщповщно! модел! на MOBi VHDL е процесои дуже кроштким i довготривалим. Створення тако'У модел1 на MOBi Pro Wave; вщносно просте. В зв'язку з цим дуже ефективним, з точки зору часу необхщного для шдготовки модели е поеднання модуля розгпзнаванн: AiarpaM, описаного мовою Pro Waves з операщйним модулем, написант мовою VHDL. Cnoci6 виконання такого поеднання подано на рис. 5, якш вщноситься до розглянутого вище прикладу декодера зображення.

Модуль, виконаний мовою Pro Waves, а точшше, генероваш на Т основ! описово-моделююч1 правила, виконуе дв! основш функц1'1. Перша : них - розшзнавання д1аграм через пор1вняння Yx з еталонами цикл1в, а такол

leftSideGroup (event (nCS,l,0)) ->> t

t

leftSideGroup (event (nWAIT,0,l)) ->> t

t

leftSideGroup (event(nCS,0,1)) ->> t

t

rightsideGroup(event(nCS,1,0)) ->> t

t

rightSideGroup(event(nWAIT,0,1)) ->> t

t

rightSideGroup(event(nCS,0,1)) ->> t

t t t t t

Ш1щювання виконання операщй системи, що моделюеться, шляхом створення вщповщних значень сигналу мовою VHDL action.

DATA WAIT R/W

A A -

ADD CS CDSTR

У-м.

L^L

Розтзнавання часових д!аграм декодера

Результат розп1знавання (out)

\ А А А А А

интерфейс_С

1нтерфейс

CDSTR (in)

\ /\ /\ /\ /

R/W (in)

ViDb С

(in)

Ol

HAIT (in)

од

\ /

ADD (in)

DATA (in)

Onepauiï декодера результат

CDSTR (in) розп1знавання

R/W (in) (in> V

H

CS (in) D

WAIT (out) L

ADD (in)

DATA ( inout )

MPEG

Влдео Декодер -модуля ProWaves

MPEG

В1део Декодер -модуля VHDL

р

Рис. 5. Поеднання модулю, написаного мовою Pro Waves, з модулем VHDL

Модуль, написаний мовою VHDL, виконуе yci операцГ модельованого пристрою, що шщшоваш сигналом action. Цей модуш складаеться з двох компоненте - головного компоненту, який виконуе ус згадаш вище операцп, а також компоненту ¡нтерфейс _VHDL_C_Prolog, щс мае допом1жний характер i забезпечуе комушкащю пом1ж головнил компонентом i прологовим модулем.

У таблицях 1, 2 i 3 подано пор!вняння ефективносп моделювання, < також ефективност1 процесу створення модел1 елемента VRAMp. PD42264, i випадку використання мови Pro Waves, а також у випадку використанш виключно мови VHDL. Модуль Pro Waves був установлений за допомогок комшлятора SICStus Prolog, модуль VHDL - за допомогою модулятор; Synopsys-VHDL, Bepcin 3.1. Для моделювання використано комп'ютер Sui SPARCstation 2, який мае 64 М байти пам'ят1 RAM.

В залежноеп вщ кшькост1 модельованих подш, витраченш процесором CPU час для модел1 Pro Waves в пор1внянш з моделлю написаною виключно за допомогою мови VHDL, е бшьш вщ 2 до 7 рази (Табл.1). Проте принципово зменшуеться час, який повинен витратип проектувальник на створення само'1 модель У випадку використанн) виключно мови VHDL цей час складае кшька мюящв, а у випадю використання мови Pro Waves - тшьки деюлька дшв (Табл.3). Скороченш часу е результатом значного зменшення po3Mipy опису (Табл.2), а передуам змши типу цього опису з алгортъпчного виду на декларативний, при яком} основна задача проектувальника зводиться до вщповщноп формал1зованого запису еталошв часових д1аграм елемента, щ( моделюеться.

Табл. 1. Час моделювання елемента VRAM

Кшькють Кшькють Час CPU [s]

моде- pi3HHX тшьки ProWaves

Тип циклу льованих часових VHDL & VHDL

подШ параметрш

Read 25 26 1.6 3.8

Early write 25 29 1.6 3.8

Page early write 128 35 1.7 4.5

(5 cells)

Page early write 6152 35 5.7 39.1

(256 cells)

Табл.2. Po3Mip опису елемента VRAM, вим1рюваний за допомогою кшькосп л!Н1й, що створюють код, а також кшькосп використаних ключових сл1в мови VHDL

Кшьшсть Кшьюсть ключових сл1в

Тип модел! лшш if, elsif last_event, event, etc. wait

Титьки VHDL - вся модель 5500 + 400* 455 218 56

Pro Waves & VHDL - частина VHDL 220 + 400* 28 64 12

Pro Waves & VHDL - частина ProWaves 1600 - - -

[*) лнш коду, що зв'язаш з штерфейсом (port i generic), а також повщомленнями про порушення часових вимог.

Габл.З. OpieHTOBHiffl час, необхщний для створення модел! VRAM

Тип модел1 Час створення модел1 одним

проектувальником

лльки VHDL декшька мюящв (*)

ProWaves & VHDL декшька дшв

'*) на основ! л1тератури, поданоУ в монограф1У i власних праць автора.

Мова Pro Waves була використана для побудови модел1 кшькох тристроУв i процеав, що мають дуже складш nacoBi характеристики. До ийважливших з них належать модели пам'яи VRAM (Video RAMp, Ю42264), ¡нтерфейсноУ частини системи декодера зображення (MPEG/2 s^ideo Decoder STi 3500), протокол1в комушкацп з трансп'ютерними ;истемами, а також, в осташпй час, модел^ що використовуються шд час троектування ¡нтегральних пристроУв для потреб цифрового телебачення \DB Phase II Signal Processor (PSP) i Bili-I Fast Descrambler.

Розд1Л 7. Завершения

В роздш подано стисл1 висновки монограф1У, а також й найважлив1ип юсягнення.

ПРИКЛАДИ ВПРОВАДЖЕНЬ

1нтегральний пристрш ASIC: Bili-I Fast Descrambler

Рис. 6. Bili-I Fast Descrambler - спроектована схема

• Декодер цифровий для супутниковоУ передач! сигналу DVB, кодованоп в систем! ф!рми IRDETO.

• Реал1зуе функцп: бгатоТ та байтово'1 корекцй' похибок, розкла, потужносп та декодування сигнагив.

• Частота тактових ¡мпульав 60 мгГц.

• 35 тисяч ком1рок.

» Проект виконано в сшвпращ з проектними бюро ф1рми SGS Thomson

Microelectronics в США, та у 1талп. » Виробництво в США та на Мальтк

► До кшця 1999 року ф1рма SGS Thomson Microelectronics виконае 130 тисяч пристроУв VLSI Bili-I.

► Декшька MicnuiB пристрой вже монтуеться для новоУ генеращ'У супутникових приймач1'в-декодер!в.

>ис. 7. Bili-I Fast Descrambler - приклад використання

Дифровий супутниковий приймач - декодер для ШвденноТ Африки

» Приймач спроектовано за запитом компанп MULTICHOICE.

• 300 канатв TV, автоматичний пошук програм, пов'язаний з банковими системами, bhôip мови, реагпзащя kbhtkîb, функщя down load.

» Процесор типу rise EMMA ^PD61030 (core: Silicon Graphics). Модулящя типу QPSK.

• Система кодування IRDETO. Операцшна система Open TV EN2.

• Забезпечення виевгглення швидкоУ шзнавально'У графжи.

1 Шина нетелев1зШних даних 115 kbaud (Internet, комп'ютерш програми).

• CyMicHicTb з системами MPEG-2, DVB, DiSEqC.

Сертифшоваш у США.

Рис. 8. Приймач-декодер з пристроем BILI-I, зроблено за замовленняг* компани MULTICHOICE для ринку ГНвденноТ Африки

Цифровий супутниковий приймач-декодер для Австрали

• Приймач зроблено за замовленням компани AUSTAR.

• Паралельний процесор OMEGA Sti5500 + ADB Bili-I fast descrambler.

• Система кодування IRDETO, система операцшна Open TV 3500.

• Вщео-декодування Video: ISO/IEC 13818-2, Audio: ISO/IEC 13818-3.

• Демультиплексування пакете ISO/IEC 13818-1.

• Сумюний з системами MPEG-2, DVB, DiSEqC.

• Сертиф1коваш у США.

Рис. 9. Приймач-декодер зроблено за замовленням компани AUSTAR дл ринку Австрали

Висновки

1. В робот1 представлена методология автоматизацп фоектування i моделювання електронних цифрових систем, що опираеться ia евристичш i символ1ЧШ операцн. Це ¡стотно доповнюе використовуваш у цй галуз1 традицшш алгоритм1чш i числов1 методи.

2. Ця задача е актуальною i важливою науково-дослщною фоблемою, осюльки з ростом конкуренцп на електронному ринку, а також : розповсюдженням спещашзованих систем, що виробляються малими :ер1ями, зросла необхщшсть створення нових метсуцв проектування, яю ;абезпечують шдвищення ефективност1 проектування, а також, мЬк ¡ншими, юзволяють скоротити час, необхщний для шдготовки проекту i виконання >етельноТ верифкацп системи ще до початку и виробництва.

3. Ршення охоплюють широке коло проблем, пов'язаних з (икористанням лопчного програмування в проектуванш цифрових систем. 1ри цьому забезпечено комплексне вщображення yciei тематики.

4. До найбшьш значних наукових i практичних досягнень, на (умку автора, належать:

> Створення нового, оригшального методу розтзнавання часових д1аграм. 1 Побудова, на баз1 запропонованого, нового методу розшзнавання, мови Pro Waves, призначено'1 для опису i моделювання електронних цифрових систем, що характеризуються складними часовими залежностями. 1 Опрацювання методу автоматизацп символ!Чного синтезу цифрових

систем, описаних за допомогою лопчних секвенпв. 1 Практичш реал1защУ розроблених метод1В при створенш сучасних пристроУв обчислювальноУ технки.

5. В межах моделювання часових залежностей у попередшх [рацях були запропоноваш pi3Hi piiuemw, що спрощують створення юделей. Проте, вони мали принаймш одну з приведених нижче рис:

■ мали алгоритмпший, а не декларативний характер; це означав, що завдання проектувальника часто було надто складним,

- стосувалися анал1зу одиничних змш сигналу, а не складних взаемозалежних д!аграм для багатьох сигнатв,

- були зв'язаш тшьки 3i специфжащею, а не з моделюванням часових залежностей.

f монограф!'/ використано новий, систематичний шдхщ до опису складних заемозв'язаних Д1'аграм для багатьох сигнал1в, який опираеться на подш ;асових залежностей на групи, пов'язаш з под1ями вщнесення циклу. Цей юдш, а також под ¡л циклу на частини, можуть мати характер повторювань.

Це дозволяе створювати формальну мову опису i моделювання часови моделей пщ назвою Pro Waves, в якому цифровий пристрш, процес аб система, що моделюються, описуеться щлком декларативним способом, з допомогою групи еталошв циюив, як то мае мкце у випадку техн'1чнс документацГк

Для розшзнавання описаних таким чином циюив пщ час процес моделювання використовувалися методи, що застосовуються у штучном штелект1 - пор1вняння з еталоном i метапрограмування. Особливо ефективним виявилося поеднання часового модуля, написаног мовою Pro Waves, з операцшним модулем, написаним мовою VHDL. Використання новоУ мови Pro Waves дозволяе:

• багаторазово скоротити час пщготовки модели цифрових пристро'п npouecie i систем, як1 характеризуються складними часовим залежностями,

• звести завдання проектувальника до формального запису еталош часових д1аграм без необх!дност1 осмислення i використання будь-яког алгоритму,

• шдвищити точшсть моделювання, тому що, завдяки декларативном характеру проектування , мае мюце незначна можлив1сть помилок.

6. В сфер1 синтезу цифрових систем, в перюд, передуючи

роботам автора, в Польцц не ¡снували доступш допомгжш nporpaMHi засоб для процесу автоматизаци символ1чного синтезу. Автору, так само, не бул в ¡дома жодна попередня робота, зв'язана з використанням лопчног програмування для автоматизаци синтезу з застосуванням лопчни секвенлв. 1снуюч1 в той час теоретичш роботи були присвячен насамперед, застосуванню у проектуванш цифрових систем переважн алгебраУчних i символ1чних метод!в, як1 могли використовуватися тшьк при мануальному проектуванн1, цебто безпосередньо людинок Застосування цих метод!в не було пов'язано з автоматизацию процес проектування. В зв'язку з приведении вище, можливо забезпечит розв'язання реальних, складних завдань проектування. 3 метою виконанн автоматизащУ символ1чного синтезу автор nepeHic апарат, використовувани в галуз1 штучного ¡нтелекту i автоматичного доведения теорем, у галуз проектування цифрових систем. Внаслщок виконана автоматизащя:

• нормал1защУ секвент1в (способом, под1бним до автоматичного доведенн теорем, з використанням лопчних висновк1в),

• мш1м1защУ опису (застосування евристичних правил),

' синтезу до вигляду, вщповщному структур! застосованих елемешчв

(символ!чне перетворення), ' декомпозицп опису на шдгрупи, яку можна використовувати в окремих

ф1зичних елементах, з застосуванням мехашзму пошуку. 1а основ! запропонованого методу синтезу була створена система CAD -ogic, яка призначена для автоматизацн проектування цифрових систем з (икористанням програмованих лопчних структур PAL.

7. Результати роботи описаш в монографп i знайшли широке астосування у народному господарствь Це свщчить про слушшсть i ¡ктуальшсть теоретичних розв'язань, а також про ïx велике практичне начення.

8. Особливо'1 уваги в цьому обсяз1 заслуговуе мова Pro Waves. Зона знайшла широке застосування при проектуванш спещатзованих щфрових систем високого р1вня штеграци ASIC, що призначеш для упутникового цифрового телебачення i при проектуванш цифрових елевкзшних штерактивних приймач!в-декодер1в, виконаних на замовлення ;еликих, вщомих у цшому cbítí, ф1рм таких як: SGS Thomson /licroelectronics, Sun Moon Star, Broadcast Software Systems International i ^sia Digital Broadcast. Наприклад, спещатзований пристрш Bili-I fast lescrambler, спроектований за допомогою мови Pro Waves, було випущено ершно в кшькосп понад сто тисяч штук.

Таким чином, можна стверджувати, що поставлена в робот! проблема ¡у л а досягнута, а опрацювання методу автоматизаци проектування, що рунтуеться на евристичних методах i символ^чних операциях, ¡стотно ;оповнюе ¡снуюч1 алгоритм1чш i числов1 методи.

)chobhí публикацн

. Szajna J.: Projektowanie ukladów cyfrowych z wykorzystaniem programowania logicznego. MONOGRAFIA nr 82. Politechnika Zielonogórska, 1996 (240 с).

. Szajna J.: Programowanie strukturalne. Wybrane algorytmy i struktury grafowe. MONOGRAFIA nr 41, Wyzsza Szkola Inzynierska. Zielona Góra, 1989 (440 с).

. Szajna J.: Technika programowania. Elementy programowania sprzçtu i wspólpracy z systemem operacyjnym. PAÑSTWOWE WYDAWNICTWO NAUKOWE. Warszawa 1990 (237 c).

4. Szajna J., Adamski M., Kozlowski T.: Programowanie w jqzyku logik WYDAWNICTWA NAUKOWO-TECHNICZNE. Warszawa 1991 (166 c).

5. Szajna J., Mirkowski J.: Zaawansowane techniki programowania. Polski Towarzystwo Ekonomiczne. 1989 (177 c).

6. Szajna J.: Turbo Pascal 4.0. Polskie Towarzystwo Ekonomiczne. 198 (173 c).

7. Wagner F., Szajna J., Michta E.: Laboratorium mikroprocesorów. Wyzsz Szkola Inzynierska. Zielona Góra, 1985 (132 c).

8. Szajna J.: Wykorzystanie zmiennych dynamicznych jqzyka Pascal 1 minimalizacji funkcji logicznych. Zeszyty Naukowe WSInz. Nr 78, str. 12' 132. Zielona Góra, 1986.

9. Adamski M., Szajna J., Kapela A.: PAL Design Software PALMAI Mikroprocesory- Dydaktyka i Zastosowania. WSI Zielona Góra, Politechnik Wroclawska, TH Ilmenau, str. 158-168. Zielona Góra 1987.

10. Adamski M., Szajna J., Kapela A.: Programmable Array Logic Softwari Control Systems and Computer Science. Bucharest, Vol.3, pp. 86-9Í Romania 1987.

11. Adamski M., Szajna J., Wysocki A.: Automated State Machine Design an PAL Implementation. Wissenschaftliche Beitrage zur Informatik 1988 No ( pp. 13-18. Dresden, Germany.

12. Adamski M., Szajna J.: Turbo Prolog jako deklaracyjny jqzy programowania. Nowoczesne Jqzyki Programowania. Str. 135-168. Polski Towarzystwo Informatyczne. Lódz 1989.

13. Szajna J., Kozlowski T.: Wykorzystanie jqzyka Prolog w projektowani ukladów cyfrowych. Zeszyty Naukowe WSInz. nr 95, str. 5-15. Z. Góra 1991

14. Szajna J., Biliñski K.: Przyklad zastosowania Turbo Prologu do realizac prostego translatora. Zeszyty Naukowe WSInz. nr 95, str. 17-27. Zielon Góra 1991.

15. Szajna J: Translacja specyfikacji ukladu cyfrowego opisanego za pomoc listy pol^czeñ na jqzyk VHDL. Metrología i systemy pomiarowe nr 13, st 31-38. Polska Akademia Nauk. Komitet Metrologii i Aparatury Naukowe Warszawa 1992.

16. Szajna J: Wykorzystanie programowania logicznego do automatyzac przeksztalcania wyrazeri logicznych. Metrología i systemy pomiarowe nr 1! str. 39-44. Polska Akademia Nauk. Komitet Metrologii i Aparatui Naukowej. Warszawa 1992.

17. Szajna J: Automated realization of boolean algebra theorems in tt simplification of logical expressions. Applied Mathematics and Computs Science. 1993. Vol.3, no. 2, pp. 383-392.

8. Szajna J., Wqgrzyn M., Walkowiak M., Wolanski P.: Programowanie w projektowaniu ukladow cyfrowych. Informatyka na wyzszych uczelniach dla gospodarki narodowej, str. 57-61. Gdansk, 1994.

9. Szajna J.: Transputer Based Intelligent Management System for Interactive TV Digital Satellite Receiver. SGS-Thomson Microelectronics, pp. 25-38. Singapore, 1995.

,0. Kozlowski Т., Dagless E., Saul J., Adamski M., Szajna J.: Parallel controller synthesis using Petri nets. IEE Proceedings - Computers and Digital Techniques, Vol. 142. No. 4, pp. 263 -271, 1995. 1. Szajna J: Prolog-based Timing Waveform Recognition System for Behavioural VHDL Simulation. Synthesis and System Integration of Mixed Technologies, pp. 155-161. Fukuoka, Japan, 1996.

Особистий внесок автора у робота, що написаш з сшвавторами, е аступним.

В poöoTi 4 внесок автора охоплюе 1, 3, 4, 5, 6 роздши i додаток (у cyMi 50 сторшок); що охоплюе yci основш ¡деУ i подаю методи. Внесок шших вох cnißaBTopiß стосуеться роздшу 2, який мае характер доповнення ¡дносно до головноУ частини npaui, а також подання приклад1в.

В роботах 5, 13, 14 i 18 автору належить бшьша частина редставлених результат, зокрема, yci запропоноваш головш ¡деУ i одання методш.

В poöoTi 12 внесок автора складае 8 з 10 роздшв. Результати робот 7, 9, 10 i 11 належать сшвавторам в piBHnx частках. В poöoTi 20 - автором був запропонований формат специфжащУ 1ереж1, що базуеться на лопчному програмуванж.

кНОТАЦП

Я. Шайна: Проектування цифровых систем з використанням ozihhozo програмування. Монограф|'я

Дисертац1я на здобуття вченого ступеню доктора техшчних наук за пещальн1стю 05.13.13 - обчислювальш машини, мереж! i системи. -ютитут проблем моделювання в енергетиц1 HAH УкраУни, КиУв, 1999.

Представлена методолопя автоматизащУ проектування i моделювання ифрових систем, що базуеться на лопчному програмуванш. Найб!льш уттевими досягненнями монографй" е слщуюч1. Запропоновано новий ригшальний декларативний метод розшзнавання часових д1аграм i метод втоматизащУ символ!чного синтезу цифрових систем, як! описуються за

допомогою лопчних секвештв. Представлена можливють використаш лопчного програмування для динам1чного моделювання з застосування баз даних, трансляцн опису i автоматизащУ перетворення лопчних вираз1 Особливо!' уваги заслуговуе запропонована мова моделювання цифрови систем i процеав ProWave, а також застосування запропонованого монографи методу для розшзнання складних часових д1аграм. Ця moi знайшла широке застосування для проектування цифрових систем високог р1вня штегращУ. До цього часу були випущеш в кшькост1 бшыи шж 100 ОС штук спещал1зован1 системи, спроектоваш для супутникового телебачення використанням означеноУ вище мови.

Ключов1 слова: лопчне програмування, цифров1 систем] символ1чний синтез, моделювання, САД цифрових пристроУв.

J. Szajna: Design of Digital Systems with the Usage of Log Programming. Monograph.

Thesis for the doctor 's degree by the specialty 05. 13.13 - computer systems and networks. - The Institute of Simulation Problems in Energetic National Academy of Science of Ukraine, Kiev, 1999.

The dissertation presents methodology of automatization of digital circui design and simulation by means of logic programming. Here are some of the mo important achievements of this monograph. The new, original, declaratn method for timing waveform recognition. Methods for the automatization of tl symbolic synthesis of digital circuits that are described by using logic sequent The application of logic programming to dynamic simulation uses databas< description translation, and automatic manipulation of logic expressions. Tl ProWave simulation language for digital circuits and processes, implemented с the bases of the suggested in this monograph method for a complex timir waveform recognition, deserves special attention. This language has found a wic application in the design of large-scale integration digital circuits. Up to tl present moment, more than 100 000 items of specifically designed for digital T circuits based on the above-mentioned language have been sold.

Key words: logic programming, digital circuits, symbolic synthesi simulation, CAD of digital systems.

Я. Шайна: Проектирование цифровых систем с использование логического программирования. Монография.

Диссертация на соискание ученой степени доктктора технически наук по специальности 05.13.13 - вычислительные машины сети и системы Институт проблем моделирования в энергетике НАН Украины, Киев, 1999.

В диссертации представлена методология автоматизирован t

36

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

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

Представлена возможность использования логического рограммирования для динамического моделирования с применением баз анных, трансляции описания и автоматического преобразования огических выражений.

Представлен новый, оригинальный метод распознавания временных иаграмм, имеющих декларативный характер и основанный на методах, рименяемых в искусственном интеллекте - сравнение с эталоном и етапрограммирование.

[а основе предложенного метода распознавания временных диаграмм эздан новый формальный язык описания и моделирования временных оделей, названный Pro Waves, в котором моделируемое устройство, роцесс или система описывается полностью декларативным способом с омощью группы эталонных циклов, как это имеет место в случае редставления технической документации, [рименение языка позволяет:

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

) свести задачу проектанта к формальной записи эталонов временных иаграмм без необходимости осмысливания и применения каких - либо пгоритмов;

) повысить точность моделирования, так как, благодаря декларативному арактеру проектирования, возможность допустить ошибку незначительна.

В области синтеза цифровых устройств были разработаны методы втоматизации символического синтеза цифровых систем, описываемых с омощью логических секвентов.

С этой целью был использован аппарат, применяемый в области скусственного интеллекта и автоматического доказательства теорем, к

проектированию цифровых устройств. В части процесса автоматизащ была выполнена:

а) нормализация секвентов способом, подобным автомата ческоь< доказательству теорем, с использованием правил логических выводов;

б) минимизация описания за счёт применение эвристических правил;

в) синтез системы к виду, соответствующему структуре применяемь элементов с помощью символических преобразований;

г) декомпозиция описания на подгруппы, которые можно применять отдельных физических элементах, за счёт использования механизма поискг

На основе предложенного метода синтеза была создана систе\ CAD Logic, предназначенная для автоматизации проектирования цифровь систем с использованием программируемых логических структур PAL.

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

Особого внимания в этом смысле заслуживает язык описания моделирования цифровых систем Pro Waves. Этот язык нашёл широкс применение при проектировании специализированных цифровых устройст высокого уровня интеграции ASIC, предназначенных для спутнико1 цифрового телевидения, а также при проектировании цифровь телевизионных интерактивных приёмников-декодеров, выполненных г заказу больших, известных во всём мире фирм, таких как: SGS Thomsc Microelectronics, Sun Moon Star, Broadcast Software Systems International Asia Digital Broadcast. Спроектированные специализированные систем! предназначенные для использования в цифровом спутниковом телевидени были произведены в количестве более ста тысяч штук.

Ключевие слова: логическое программирование, цифровые систем! символический синтез, моделирование, САД цифровых устройств.