Розвиток теорії і розробка методології логічного синтезу НВІС на основі багаторівневих автоматних моделей

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

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

Національна академія наук України

Інститут кібернетики імені В.М. Глушкова

05.13.05 -- Елементи та пристрої обчислювальної техніки та систем керування

Автореферат

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

Розвиток теорії і розробка методології логічного синтезу НВІС на основі багаторівневих автоматних моделей

Денисенко Євгеній Леонідович

Київ - 1999



Дисертація є рукописом

Роботу виконано в Інституті кібернетики імені В.М.Глушкова НАН України.

Науковий консультант:

доктор технічних наук, професор, член-кореспондент НАН України Палагін Олександр Васильович, Інститут кібернетики НАН України, заступник директора

Офіційні опоненти:

доктор технічних наук, професор, член-кореспондент НАН Республіки Бєларусь Закревський Аркадій Дмитрович, Інститут технічної кібернетики НАН Республіки Бєларусь, головний науковий співробітник

доктор технічних наук, професор, Рабінович Зіновій Львович, Інститут кібернетики НАН України, головний науковий співробітник доктор технічних наук

Баркалов Олександр Олександрович, професор кафедри електронних обчислювальних машин Донецького державного технічного університету.

Провідна установа: Національний технічний університет України "Київський політехнічний інститут", кафедра обчислювальної техніки.

З дисертацією можна ознайомитись в науково-технічному архіві Інституту.

Учений секретар спеціалізованої вченої ради Романов В.О.

Загальна характеристика роботи

Актуальність теми. За останні роки проблема логічного синтезу стає однією з основних серед проблем проектування в усіх провідних наукових центрах та фірмах-виробниках надвеликих інтегральних схем (НВІС). Обсяг фінансування на фундаментальні дослідження, НДР і НДДКР лише у США на цю проблему за останні 5 років збільшився в 10 разів, вдвічі перевищивши обсяг коштів, що виділяються на розв'язання проблеми тестування.

Досягти необхідної бездефектності проектних рішень НВІС за необхідних показників швидкодії та обсягів устаткування традиційними евристичними методами за допомогою засобів аналізу НВІС стає тим важче, чим вище складність і вимірність задач, навіть за їхнього неухильного вдосконалення. Ситуація загострюється тим, що подолання засобами технології порогу 100 Мгц спричиняє наростаюче погіршення працездатності синхронної схемотехніки. Погано вирішують проблему як спеціальні рекомендації та узгоджуючі мікросхеми фірм США (Intel, DEC), так і недостатні результати в галузі асинхронної схемотехніки, дослідження якої активізуються в Японії.

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

Великий вклад у розв'язання проблеми логічного синтезу в основному в галузі абстрактної та прикладної теорії автоматів внесли представники шкіл В.М. Глушкова, М.О. Гаврилова, А.Д. Закревського, Є.Н. Вавілова, З.Л. Рабіновича, С.О. Майорова, В.Г. Лазарєва, Ю.В. Капітонової, Хафмена, Колдуела, Хартманіса, Джераче, Ангера та ін. До цього кола робіт слід віднести і результати по дискретному аналізу О.Б. Лупанова, Ю.І. Журавльова, С.В. Яблонського.

Ґрунтуючись на цих фундаментальних результатах, практичну спрямованість у межах гіпотетичних або окремих реальних логічних обмежень дістали наступні цикли прикладних праць: синтез операційних автоматів (С.О. Майоров, Г.І. Новіков, З.Л. Рабінович, Б.Г. Лисіков, О.С. Нікітін, А.Д. Коршунов, В.П. Корячко); синтез мікропрограмних автоматів в базисах МІС, ПЗП та ПЛМ (С.І. Баранов, О.В. Палагін, О.Л. Бандман, О.О. Баркалов, В.А. Скляров, С.М. Ачасова); синтез послідовнісних схем на МІС та СІС (А.Д. Закревський, В.Г. Лазарєв, Ю.В. Капітонова, О.І. Пійль, А.Т. Міщенко); мінімізація станів автомата (І.В. Потосін, Ф.І. Андон, Й.І. Брона); окремі задачі логічного проектування в середовищі обмежень матричних ВІС (В.А. Міщенко); окремі засоби і алгоритми проектування структур ЕОМ (С.А. Майоров, З.Л. Рабінович, Г.І. Новіков, Б.А. Бабаян, О.В. Палагін) та ін.

Ці роботи як потенціальні складові не об'єднані якимось основоположним стрижнем, наприклад, багаторівневою моделлю НВІС, контури однієї з яких намічені в монографії Майєрса. Одним з імовірних наслідків цього є недостатній (математичний) взаємозв'язок моделей і даних задач системного і логічного етапів. Тому вхідні дані задач логічного етапу, як правило, визначаються евристично, що завжди збільшує імовірність помилки. Також недостатні моделі і методи, що об'єднують цілі логічного і топологічного етапів. Тому оптимальна за критеріями логіки схема може перетворитися в надто збиткову внаслідок проектування топології або взагалі “не дотрасуватися” до кінця.

Навіть самі “найбагатші” роботи, сукупність яких лише умовно можна назвати методологією логічного проектування дискретних приладів (але не НВІС), містять в собі або методи синтезу асинхронних схем, або методи синтезу мікропрограмних(на основі синхронних) автоматів. Жодна з них не містить в собі обидва підходи в межах усіх логічних обмежень, водночас як зростаюча складність багаторівневого управління вимагає або обгрунтованого вибору одного з них, або суміщення обох в одній НВІС.

Сьогодні більшість мов опису специфікацій НВІС розроблені одними авторами, а методики проектування -- іншими. Тому часто існує неузгодженість методик і мов, більшість з яких містить в собі засоби описів не більше, ніж для одного рівня проектних рішень. Це породжує труднощі в перепідготовці і “стиковці” даних навіть на логічному етапі. Наявні винятки -- потужні мови CONLAN і VHDL, до точних описів трансляторів яких поки що немає доступу, -- лише підтвердження цього. Все наведене являє собою сукупність не визначених сьогодні знань, відсутність яких не дозволяє досі сучасно сформулювати і тим більш розв'язати проблему логічного проектування НВІС.

Мета і задачі досліджень. Мета проведених досліджень -- розвинути прикладну теорію логічного проектування в напрямку урахування всіх логічних обмежень НВІС і створити на цій основі ефективну методологію і систему апробованих методів і методик логічного синтезу НВІС для розв'язання проблеми отримання логічних схем, що забезпечують позитивне розв'язання задач топології, гарантовану вірогідність функціонування, максимальну швидкодію при мінімальних витратах обладнання.

Основні задачі дисертаційної роботи, що визначаються поставленою метою:

-- на основі використання загальної теорії, сучасних стилів і методів логічного проектування розробити методологічні основи ієрархічного логічного синтезу НВІС, отримати вірогідні, близькі до оптимальних схемотехнічні рішення в рамках логічних обмежень, що задаються;

-- розробити методику багаторівневого ієрархічного синтезу послідовнісних (асинхронних) пристроїв у межах відомих сьогодні логічних обмежень НВІС різноманітних типів: БМК, ПЛІС, ПЛМ та ін., що містить в собі математичні механізми оптимізації і адаптації до різноманітних значень логічних обмежень і що дозволить одержувати схеми максимально досяжної швидкодії з кількістю “обладнання”, що задається, у межах цих обмежень;

-- розробити методику ієрархічного проектування системи багаторівневого мікропрограмного керування НВІС і обчислювальних систем в базисах ПЛМ і ПЗП, що дозволить одержувати близькі до оптимальних схеми і вирішувати оптимізуючі задачі покриття;

-- розробити систему методів логічного синтезу як складову методології і методик, що включає в себе: методи протигоночного кодування асинхронних автоматів, засновані на “розв'язуванні” переходів, і/або які передвизначають оптимальну реалізацію автомата мережею з логічних бібліотечних примітивів НВІС; метод ієрархічного синтезу структурного автомата, що дозволить отримати без перебирання оптимальні за кількістю примітивів регулярні схеми з максимальною швидкодією; метод покриття, що дозволить отримати оптимальні рішення; метод проектування систем адресації мікропрограмного управління; метод оцінки ефективності проектних специфікацій, які синтезуються; метод поліпшення якості трасування НВІС і багатошарових друкованих плат;

-- розробити мову для багаторівневого опису НВІС і обчислювальних систем;

-- для точного обґрунтування ключових “механізмів” методології і методик, що її складають, методів, алгоритмів і рекомендацій розробити наступні теоретичні положення: сформулювати багаторівневу автоматну модель НВІС і модель “ліс” (сукупність багаторівневих моделей) обчислювальних систем з різнорідних або однотипових НВІС; мережні автоматні моделі фрагментів архітектури і структури НВІС -- мережу магазиних перетворювачів, мережі секвенціальних і паралельних автоматів; визначити і довести необхідні і достатні умови відсутності логічного ризику в довільному асинхронному автоматі, а також достатні умови, за яких в процесі багаторівневого синтезу булевих функцій збудження і виходів точно задовольняються логічні обмеження на кількість входів примітивів типу AND і OR і коефіцієнт розгалуження виходу.

Методи досліджень. Виконане дослідження розвиває результати, отримані В.М. Глушковим, А.Д. Закревським, Е.Д. Хафменом та ін. в прикладній теорії скінченних автоматів та їхній розвиток в працях С.І. Баранова, Ю.В. Капітонової, О.В. Палагіна, А.Т. Міщенко стосовно до врахування логічних обмежень НВІС, побудови багаторівневої автоматної моделі, моделі “ліс”, мережних моделей автоматів і організації процесу ієрархічного синтезу. Методики ієрархічного синтезу, методи і процедури кодування станів і покрить використовують методи Лю, Тресі, А.Д. Закревського і алгебру розбиттів Хартманіса-Стірнза стосовно до множини переходів асинхронного автомата. Проведені дослідження грунтуються також на використанні апаратів теорії множин, графів, чисел і елементів булевої алгебри.

Наукова новизна. Сукупність проведених у роботі досліджень і на їх основі розробок являє собою теоретичне узагальнення, обґрунтування і розв'язання значної прикладної проблеми -- розробки методології ієрархічного логічного синтезу послідовнісних схем НВІС, що задовольняють усім логічним обмеженням як формалізованої стратегії і тактики прийняття проектних рішень, і нового її “наповнення” принципами системного підходу та ієрархічності, методиками синтезу асинхронних і мікропрограмних автоматів, методами і алгоритмами синтезу цих автоматів з урахуванням обмежень, що дозволять отримати адекватні вхідним даним проектні рішення, близькі до оптимальних, що забезпечують максимальну швидкодію.

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

-- новий підхід до логічного синтезу та побудови НВІС і обчислювальних систем з різнорідних НВІС, заснований на запропонованих багаторівневій автоматній моделі та сукупності таких моделей -- “ліс”, який дозволить створювати нові методи і алгоритми синтезу;

-- ефективна прикладна теорія асинхронних автоматів і на її основі методика ієрархічного синтезу асинхронних схем як мереж з логічних примітивів за умов усіх відомих сьогодні логічних обмежень НВІС: ПЛІС, БМК, ПЛМ та ін.;

-- методика ієрархічного проектування систем багаторівневого мікропрограмного управління НВІС і обчислювальних середовищ для різноманітних логічних базисів, що містить у собі підсистему методів, у тому числі розвиток методу покриття А.Д. Закревського і метод “упаковки”, що дозволяють отримати проектні рішення, порівняні з кращими інженерними;

-- система методів логічного синтезу, що складається з методу протиризикового кодування в кордонах обмежень, методу структурного синтезу, методу покриття в задачах кодування мікрокоманд, методу оптимального проектування систем адресації мікрокоманд, методу оцінки ефективності проектних специфікацій, які синтезуються, і методу поліпшення якості трасування НВІС і багатошарових друкованих плат, що модифікує хвильовий алгоритм Лі;

-- дві версії алголо- і PL-подібної мов для багаторівневого логічного опису НВІС і систем, що дозволяють одноманітно деталізувати багато мовних конструкцій в низхідному процесі логічного синтезу;

-- нове, ефективне теоретичне обґрунтування ключових “механізмів” методології, її методик, методів, алгоритмів і рекомендацій складається з моделей (багаторівнева деревоподібна автоматна модель НВІС і модель “ліс” як сукупність багаторівневих моделей -- модель обчислювальних систем з різнорідних НВІС, мережі магазинних перетворювачів, секвенціальних і паралельних автоматів як моделі фрагментів архітектури і структури НВІС), визначених і доведених необхідних і достатніх умов відсутності логічного ризику в довільному асинхронному автоматі (з пріоритетом до аналогічних результатів Дж. Тресі), а також достатніх умов для системи двоблокових розбиттів на множині переходів, за яких в системах булевих функцій збудження і виходів точно задовольняються логічні обмеження на кількість входів примітивів типу AND і OR і коефіцієнт розгалуження виходу.

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

Практичне значення і реалізація результатів роботи. Розроблена в даному дослідженні методологія перевизначена для використання в логічному проектуванні обчислювальних приладів і систем в НВІС-реалізації та їх багаторівневих пристроїв управління, що з'єднують як мікропрограмні, так і асинхронні послідовнісні блоки та їхні композиції. Робота виконувалася на основі переліку найважливіших НДР у відповідності з основними Програмами Радміна, ДКНТ СРСР, ДКНТ України, зокрема "Рапира", "Крона" та ін., за відповідною госпдоговірною тематикою в області розвитку методів та інструментальних засобів обчислювальної техніки та автоматизації 1976-1993 рр., що дозволило довести основні алгоритми і рекомендації, що складають методологію, методики, методи, до стадії, на якій вони використовуються як формальний інструмент інженерами-розробниками. Використання їх на практиці дозволяє значно (більше ніж вдвічі) скоротити терміни розробок і практично уникнути помилок при порівняних витратах обладнання з евристичними розробками високого класу. Такі розробки простіші у налагоджені і не вимагають макетування.

Запропоновані методики, методи, алгоритми і рекомендації, “що наповнюють” методологію, використовувались у багатьох розробках, у тому числі:

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

-- проект мікроЕОМ “Електроніка С5-21” (спільно з ЛКТБ ЛОЕП “Світлана”);

-- НДДКР по створенню макетних зразків міні-ЕОМ СОУ і ПЕОМ ряду “Нейрон” (спільно з ВО ім. С.П. Корольова);

-- макетний зразок системи налагодження для МП1810 (спільно з НВО “Мікропроцесор”);

-- проект багаторівневого пристрою управління в рамках НДР створення редукційно-потокової ПЕОМ (спільно з відділом №255 Інституту кібернетики ім. В.М. Глушкова НАН України і НВО “Вимпел”).

Висока ефективність і відносна простота, відсутність перебору в методиках, методах і алгоритмах методології стали підставою для їхньої реалізації в багатьох експериментальних CAD-пакетах і CAD-системах країн СНД, у тому числі:

-- в експериментальних версіях систем “ПРОЕКТ-БЭСМ” і “ПРОЕКТ ЕС”;

-- в експериментальному пакеті “УАССМА ЕС”;

-- в CAD-системі “АВТОМАТ ”.

Отримані в дисертації результати являють собою сукупність нових знань, що дозволять вирішувати нові задачі на логічному, а також на системному і топологічних етапах проектування НВІС і систем.

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

Від ряду підприємств отримані документи, які підтверджують впровадження результатів роботи.

Апробація роботи. Результати досліджень і розробок, що складають зміст дисертації, доповідалися і обговорювалися на Міжнародному симпозіумі “Діагностика, надійність і менеджмент несправностей” (Будапешт, 1990), VII Симпозіумі “Застосування мікропроцесорів і мікроЕОМ (Будапешт, 1992), Республіканській науково-технічній конференції “Обчислювальна техніка” (Тбілісі, 1974, 1976), 1-й і 2-й Всесоюзних нарадах “Мікропроцесор” (Рига, 1975, 1977), VII Всесоюзній нараді з проблем управління (Мінськ, 1977), I Всесоюзній конференції по застосуванню мікропроцесорів (Абовян, 1977), VI Всесоюзному семінарі по розробці і впровадженню систем контролю і діагностування РЕО (Москва, 1984), Республіканській конференції “Впровадження САПР -- шлях вдосконалення інженерної праці і якості розробок” (Вінниця, 1987), Республіканській конференції “Проблеми проектування замовлених та напівзамовлених НВІС” (Ялта, 1989), обговорювалися на багатьох республіканських семінарах Наукової ради з проблеми “Кібернетика” НАН України.

Публікації по роботі. За темою дисертації опубліковано 60 друкованих робіт, у тому числі 1 монографія, 3 довідники, 3 авторських свідоцтва СРСР на винаходи.

Структура та обсяг роботи. Дисертація складається з вступу, шести розділів, висновку, списку літератури, додатків і містить сторінок основного тексту -- 319, рисунків -- 60, таблиць -- 27, сторінок додатків -- 30. У дисертації та авторефераті всі означення, формули, теореми, твердження, пропозиції нумеруються одним, крізним рядом цифр.

До захисту виносяться:

1. Теоретичні результати як розвиток прикладної теорії автоматів.

2. Методологія логічного синтезу НВІС та її складові.

3. Методика ієрархічного синтезу асинхронних автоматів та схем НВІС.

4. Методика ієрархічного проектування мікропрограмних пристроїв управління НВІС на засаді синхронних автоматів.

5. Система методів логічного синтезу схем НВІС.

6. Розробка мов багаторівневого опису проектних логічних специфікацій НВІС.

Декларація про особистий внесок здобувача у роботах, що виконувались у співавторстві. Всі наукові результати дисертації здобувач отримав самостійно: у монографії [1] -- с. 1-32, 54-128, 208-260; в [1,16,18,23,26] -- теорія та методологія логічного синтезу НВІС; в [1,4-6,19] -- методика ієрархічного проектування систем багаторівневого мікропрограмного управління НВІС; в [1,14,15,17] -- головні ідеї та математичне обгрунтування системи методів логічного синтезу; в [7,8,24] -- семантика і синтаксис мов багаторівневого опису НВІС; у [20] -- с. 20-45, 192-306; у [22] -- с. 86-106. Розробка та впровадження методологічних, технічних та програмних засобів виконана особисто здобувачем або під його керівництвом і за його участю співробітниками Інституту кібернетики ім. В.М. Глушкова НАН України, фахівцями галузевих підприємств та організацій [9, 19-22 та документи впровадження].

Основний зміст роботи

Якість обчислювальної системи (пристрою), яка реалізується у НВІС, багато в чому визначається тим, наскільки точно враховуються на всіх етапах проектування для об'єктів даного класу вимоги і обмеження. Чим вище в ієрархії процесу проектування допускаються помилки або неточності, тим складніше їх усунути або скомпенсувати засобами більш низького рівня і тим менша ймовірність отримання вірогідного рішення.

Тому початковим кроком у розв'язанні проблеми логічного синтезу було проведене аналітичне дослідження НВІС як об'єкту проектування (розділ I). В зв'язку з тим, що процеси крізного проектування НВІС як висхідний, так і низхідний є ієрархічними, багаторівневими, то й особливості НВІС доцільно аналізувати відповідно цим рівням. Основні з них по висхідній ієрархії такі:

конструкторсько-технологічні:

-- найбільш розповсюджені кристали, що реалізуються по КМОП-технології, площею, як правило, не більше 1010 мм². Рекордні кристали мають розміри: Celeron 300A/333 - 9.814.6 мм², кристали комплекту Америка -- 12.712.7 мм²;

-- кристали упаковуються в стандартні корпуси таких типів: DIP-корпус, що є до 48 двурядових виводів; PLCC-корпус, що має від 68 до 84 виводів, розташованих по периметру корпусу; PGA-матричний корпус, що має від 208 до 591 виводів; корпуси комплекту Америка мають від 256 до 300 штирьових виводів з матричним розташуванням.

Топологічні: найбільше розповсюдження набули НВІС з проектними нормами 0.25 мкм. В Європі досягнута цифра 0.3 мкм, а в США і Японії -- 0.18 мкм. Мінімальна площа транзистора коливається в межах 0.50.8 мкм². Звичайні 2-3 шари металізації. В Україні робітничі норми -- 3 мкм, граничні -- 2 мкм і один шар металізації.

Схемотехнічні: переважна більшість НВІС-реалізацій залишається на синхронній схемотехніці. В усіх фірмах-виробниках НВІС практично встановилися такі значення логічних обмежень: в бібліотечних логічних примітивах типу AND, OR і XOR кількість входів від 2 до 6, інколи до 10, навантажувальна “спроможність” -- від 3 до 10, затримка в одному каскаді -- від 0.5 до 1.0 нс. Типи тригерів -- D, SR, JK і їхні різновиди. Зберігається тенденція розширення номенклатури макросів у бібліотеках. Традиційні прагнення до досягнення максимальної швидкодії при мінімумі логічних елементів за рахунок зменшення кількості каскадів і мінімізації довжини трас, а також збільшення величин синхронізуючих частот. Перехід на частоти понад 100 Мгц створює нові проблеми, в зв'язку з чим збільшується інтерес до теорії і практики асинхронних схем.

Архітектурно-структурні: поряд із триваючим вдосконаленням архітектури фон Неймана в НВІС шляхом її ускладнення (Pentium Pro, Power PC 601,603 і ін.) або спрощення -- RISC-архітектура, трансп'ютери, успішно розвиваються паралельні архітектури (N-куб і її різновиди, data flow, систоличні типу IWARP, суперскалярні VLIW та ін.). Триває НВІС-реалізація не тільки ядер ОС, але також інтерпретаторів, систем багаторівневої внутрішньої пам'яті та інших архітектурних модулей за допомогою багаторівневого мікропрограмного управління і паралельного мікропрограмування для розпаралелювання міжрегістрових пересилок.

Характерні особливості НВІС проаналізовані не тільки для їхнього врахування в задачах логічного синтезу, але головним чином для того, щоб при розв'язанні цих задач не погіршити показників, що закладаються при проектуванні архітектури і структури об'єкта.

Окрім цього, для якомога точнішого формулювання проблеми було необхідне аналітичне дослідження етапів, рівнів, основних задач і стилів крізного проектування НВІС (продовження розділу I). Сукупно сформульовано сім етапів, що історично склалися в теорії і практиці проектування, кожний з яких складається з одного або декількох рівнів.

Функціональний. Мета -- проектування функціонального опису, формально відповідаючого на питання, що (а не як) повинен виконувати об'єкт в НВІС-реалізації. Окремі рівні цього етапу ще не сформувалися.

Системний. Мета -- розробка архітектури об'єкта. На цьому етапі розрізняють такі рівні: системний, мовний (вхідної мови об'єкта), операційної системи, асемблерний, системи команд.

Логічний. Мета -- проектування структури апаратної частини об'єкта, який реалізується, мікропрограм і функціональних схем. Тут розрізняють структурний, мікропрограмний (міжрегістрових пересилок) і функціонально-схемний (логічних схем) рівні.

Схемотехнічний. Мета -- проектування електричної принципової схеми (ПС). Традиційні рівні: розрахунок параметрів схемотехнічних елементів, синтез електричної ПС, моделювання і корекція ПС.

Топологічний. Мета -- розробка геометрії масок фотошаблонів всього кристалу НВІС (в ПЛІС -- розробка розміщення логічної схеми в середовищі макрочарунок CLB і IOB і трас міжз'єднання). Рівні: ескізно-топологічний, матричний, фотошаблонний (в ПЛІС -- компоновки, розміщення, трасування і корекції при підрахунку затримок в трасах). В деяких методиках існує рівень палочкових діаграм.

Конструкторсько-технологічний. Мета -- розробка конструкторської і технологічної документації на конструювання і виготовлення окремих вузлів і всього кристалу НВІС. Традиційні рівні: розробка конструктивів, розробка технологічних маршрутів, “збірка” всього кристалу в корпусі.

Етап налагоджувальних робіт. Мета -- створення дієздатного макету НВІС або зразка системи на НВІС.

Виконаний аналіз засобів формування ядра функціонального опису обчислювальної системи і шляхи його коректного розширення. Намічений шлях формалізації переходу від задач функціонального до задач системного проектування: вибір (розробка) зовнішніх і внутрішніх мов, склад інтерпретаторів, ядра операційної системи і системи команд як “верхнього поверху” багаторівневого управління в НВІС з точки зору їх можливої мікропрограмної і апаратної реалізації і логічного синтезу. Показано, що результати розв'язування цих задач, особливо заключні, у визначенні точної архітектури є вхідними для логічного етапу і істотно впливають на ефективність розв'язування його задач. Зокрема, зазначено математичні і методичні труднощі переходу від імітаційних моделей системного етапу до автоматних логічного через неузгодженості цих моделей.

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

Стислий аналіз традиційних задач проектування принципових схем, топології і конструкторсько-технологічних наведено лише для того, щоб показати необхідність врахування окремих особливостей їхнього розв'язання на логічному етапі: необхідна регулярність для спрощення електричних розрахунків, врахування величин затримок в трасах міжз'єднань, тепловіддача і кількість виводів та ін.

У висновку аналізу особливостей НВІС і задач крізного проектування, заснованих на ідеології ієрархічного синтезу, наведено існуючі альтернативи: одна з них -- ідеологія синтезу каналу передачі даних НВІС, як основа проектування, інша -- ґрунтується на застосуваннях теорії складних систем, запропонованих в роботах М.П. Бусленко, Месаровича, Такахари та ін. Третя -- трансляторні засоби на основі описів МВР, наприклад мовою VHDL, і методологія кремнієвої компіляції, запропонована Мід-Конвей. На основі цього аналізу зроблений висновок про можливість математичної автоматної основи всього крізного процесу проектування, сформульована проблема логічного синтезу НВІС і основні задачі, що її складають.

Наступним найважливішим кроком (на основі аналізу об'єкта проектування), що є ключовим у розв'язанні проблеми, є формування багаторівневої автоматної моделі НВІС (розділ II). Для досягнення цієї мети концептуально окреслена умовна оболонка такої деревоподібної моделі. Вершиною моделі прийнятий інтерпретуючий автомат IA, що може бути отриманий з функціонального опису об'єкта, а “листям” моделі можуть бути елементарні автомати в дев'ятизначному структурному алфавіті, запропоновані Кобилинським і Зеленевською для опису фрагментів схем, еквівалентних фрагментам топології НВІС за умов дефектів. Виконане аналітичне дослідження відомих автоматних моделей як можливих “кандидатів” у фрагменти, що містяться в умовній оболонці багаторівневої моделі НВІС. Аналіз показує, що інтерпретуючий автомат IA і магазинний перетворювач Mt, запропоновані Віденською групою фірми IBM, а також дискретний перетворювач D_T , запропонований В.М. Глушковим і О.А. Летичевським, можуть бути використані як фрагменти вершинної частини багаторівневої моделі -- моделі фрагментів архітектури НВІС. На основі аналізу секвенціального і паралельного автоматів, запропонованих А.Д. Закревським, і послідовної і паралельної мереж абстрактних автоматів, запропонованих С.І. Барановим і А.Е. Кіеваліком, зроблений висновок про їх придатність у “кандидати” як моделей структурних рішень в зазначеній умовній оболонці. Показана аналогічна придатність для цієї мети автоматів усіх інших відомих різновидів як моделей мікропрограм, функціональних схем (послідовнісних і комбінаційних). Окрім цього, на основі праць Мід, Конвей і А.В. Кобилинського, О.О. Зеленевської зазначена можливість подання фрагментів топології, в тому числі і з дефектами типу обривів, замикання та ін., і еквівалентних їм фрагментів електричних схем елементарними автоматами у дев'ятизначному структурному алфавіті.

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



} , (1)

де -- вхідний алфавіт мережі;

} -- базис мережі, множина компонентних автоматів (КА);

t -- вихідний алфавіт мережі;

} -- структура мережі, множина функцій сполучення КА мережі;

} -- множина вхідних функцій}, 1  i  N мережі

-- вихідна функція мережі.

Для довільної мережі магазинних перетворювачів визначений вислідний магазинний перетворювач . Показано, що одним із шляхів низхідного переходу від моделі IA до мережі може бути проста заміна кожного стану IA відповідним йому магазинним перетворювачем. Також показано, що кожний з магазинних перетворювачів складає набір об'єктів, які задовольняють всім восьми аксіомам структур даних (по Олонгрену).

Подальша низхідна деталізація мережі шляхом структурування її компонент може бути виконана різноманітними шляхами і засобами. Часто для практичної мети визначення моделей фрагментів структури НВІС доцільно таке структурування мережі , що призводить до двох взаємопов'язаних мереж: мережі управляючих і мережі операційних автоматів. Аналіз відомих суворо послідовних або паралельних мереж управляючих абстрактних автоматів, запропонованих С.І. Барановим і А.Е. Кіеваліком, показав їхню громіздкість і недостатність атрибутів. Для заповнення цього недоліку як “наповнення” умовної оболонки мережі управляючих автоматів розроблені дві альтернативні мережі: мережа секвенціальних і мережа паралельних автоматів (побудовані на засаді моделей А.Д. Закревського).

Мережа простих (по Закревському) секвенціальних автоматів (СА) представляється шісткою таким чином:

, (2)

де -- вхідний алфавіт мережі простих СА; }, 1 i n -- базис мережі, множина КА мережі , причому вхідний алфавіт i-го простого СА

де і -- відповідно внутрішній і зовнішній вхідні алфавіти;

-- вихідний алфавіт мережі простих СА;

-- множина функцій сполучення КА, структура мережі ;

-- множина вихідних функцій;

-- вихідна функція.

Для мережі визначений вислідний простий СА, позначений символом .

Аналогічно визначена мережа паралельних автоматів (ПА) як модель фрагментів структури паралельного управління НВІС:

, (3)

де } і } -- базис і структура мережі відповідно. На основі мережі визначений вислідний паралельний автомат .

Вищезгадувана мережа операційних автоматів, “яка взаємодіє” з мережею управляючих, може бути визначена як спеціалізований варіант мережі, запропонований С.І. Барановим і А.Е. Кіеваліком. Спеціалізація її полягає в тому, що кожний КА мережі -- це операційний автомат, запропонований, наприклад, О.Д. Коршуновим, В.П. Корячко, А.С. Нікітіним та ін.

Подальша низхідна деталізація може бути виконана традиційно: в обох мережах управляючих і операційних автоматів виділяються взаємопов'язані пари (композиції) управляючого (УА) і операційного (ОА) автоматів. Для деталізації, в свою чергу, цієї відомої композиції УА-ОА, запропонованої В.М. Глушковим, використовуються різноманітні моделі мікропрограм, системи булевих функцій і моделі схем як мереж з логічних елементів (в термінології НВІС -- мереж з логічних примітивів та макросів). У цих моделях, більшість з яких відомі (запропоновані O.B. Палагіним, А.Т. Міщенко, В.А. Міщенко, В.A. Скляровим, О.О. Баркаловим та ін.) специфіка НВІС повинна враховуватися шляхом відповідних перетворень моделей з урахуванням усіх логічних обмежень НВІС. Зокрема, задача виключення логічного ризику специфічно різноманітна в моделях синхронної і асинхронної схемотехніки НВІС. Окрім цього, в моделях логічного етапу бажано максимальне врахування особливостей задач топології, зокрема максимізації регулярності схеми, мінімізації довжини міжз'єднань та ін. Далі показано, що низхідний перехід від автоматних моделей логічного етапу до моделей топології теж може бути “автоматним”, наприклад, з використанням елементарних автоматів у дев'ятизначному структурному алфавіті, запропонованих А.В. Кобилинським і О.О. Зеленевською як моделей електричних схем, еквівалентних фрагментам топології в умовах дефектів. Іншим підходом такого переходу може бути перехід від логічних моделей до моделі layout-ов, запропонований Мід та Конвей.

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

Заключна думка даного розділу -- ідея моделі “ліс” як сукупності різноманітних за “висотою” (різноманітні вершини і основи) деревоподібних моделей -- багаторівневої багатокомпонентної автоматної моделі обчислювальної системи довільної складності, що реалізується декількома НВІС з різною архітектурою. Позитивна особливість моделі “ліс” -- повна сумісність одноіменних порівневих модельних специфікацій усіх її компонент.

Наступним важливим кроком у розв'язанні поставленої проблеми є відображення специфіки і ефективності запропонованої багаторівневої моделі в структурах даних, головним чином, в засобах багаторівневого опису НВІС та її фрагментів (розділ III). Для цієї мети виконаний аналіз мов поведінкового опису: булевих виразів (мови систем PALASM, MAX+PLUS, мова ADF та ін.), рівня міжрегістрових пересилок (DDL, FDL, ISPS, HSL, CDL, SDL, HHDL); мов процедурного типу (АЛГОРИТМ, FLAMEL, MIMOLA, ASMILE та ін.), у тому числі, мов програмування ALGOL, C, PASCAL; мов багаторівневого опису (CONLAN, PINLAN, VHDL). Аналіз проведений з точки зору визначення ефективних мовних конструкцій для багаторівневого подання даних і розв'язування задач логічного синтезу. Аналіз мов показав наступне. По-перше, як правило, це абсолютна несхожість будь-яких двох мов, розроблених різними авторами (наприклад, мови систем MAX+PLUS і DASH LCA для однієї мети). По-друге, це відсутність в більшості мов засобів “підтримки” ієрархічного принципу проектування. По-третє, це різні формати даних і, що ще гірше, відмінність в управлінні даними, а також, як правило, відсутність в атрибутах мови засобів для організації бази даних.

Тому, для ефективного розв'язання задач логічного етапу (як, зрештою, й інших) необхідна розробка мовних засобів, максимально вільних від цих недоліків. Першим результатом у цьому напрямку з'явилася розробка засобів опису ВІС та їхніх фрагментів як елементів проектованих систем. Запропонована деревоподібна структура описів комплектів (серій) ВІС покликана забезпечити швидкий пошук у базі даних описи ВІС з заданими функціями, видавання повної інформації про функціональні можливості на вимогу, можливість отримання основних характеристик ВІС для логічного (у тому числі часового) проектування/моделювання.

Загальна структура опису елемента: <описание>:: ОПИСАНИЕ <имя элемента>; <функциональная часть> <описание спецификаций> КОНЕЦ Ф; <описание временных характеристик> КОНЕЦ ВР; <описание конструктивных особенностей> КІНЕЦЬ ОП <имя элемента>#. Мнемоніка стандартних і спецфункцій запозичена з мови PINLAN.

Список елементів включає в себе множини логічних примітивів та макросів, що для багатьох видів ВІС, наприклад, МАВІС і ПЛІС стали стандартними (AND, OR, XOR та їх інверсії), а також мнемоніку внутрішніх регістрів і зовнішніх шин мікропроцесорних та слайсових ВІС. Мнемоніка опису шин наведена в узагальненому вигляді з єдиною системою позначок, за якої розрізняються вхідні, вихідні, керуючі шини, шини даних і умов. В описі шин об'єктами, що адресуються, можуть бути як стандартні (наприклад, макроси, що розрізняються іменами і функціями), так і внутрішні регістри, що розрізняються іменами будь-якого типу: акумулятори, збірка регістрів загального призначення (РОН), спецрегістри адреси, маски, розширення, стани, числа зрушень та ін.

Показана можливість організації бази даних, структура якої істотно враховує особливості конструкцій мови. У такій БД можливий швидкий пошук як повної, так і часткової інформації елемента (фрагмента) ВІС.

Важливим результатом цього розділу є розробка основ мови багаторівневого низхідного опису систем на ВІС як сукупності компонент, взаємодіючих за певною системою алгоритмів і зв'язків між ними на всіх рівнях деталізації. Кожна компонента -- це “чорна шухляда” з наборами вхідних і вихідних параметрів з певною відповідністю між ними. При цьому перетворення параметрів всередині компоненти не беруться до уваги на кожному рівні абстрагування. На верхніх рівнях це може бути архітектурна компонента, що реалізується окремою ВІС, а на нижньому -- логічний примітив або навіть вентиль. Наочність, максимізація спільності описових засобів, ієрархічність і внаслідок цього можливість автономного проектування компонент та простота внесення змін в описи і, головне, врахування найбільш повної специфікації ВІС при описі структур і алгоритмів функціонування об'єкта на всіх рівнях -- основні вимоги до експериментальної версії мови. Ці вимоги відображені в лексиці, семантиці та синтаксисі мови. У ньому як основна конструктивна одиниця використане поняття ЭЛЕМЕНТ, відповідне вищезазначеному поняттю “компонента”. За функціональною ознакою елементи поділяються на чотири типи: інформаційний, запам'ятовуючий, обчислювальний і управляючий. Поняття ИНФОРМАЦИОННЫЙ ЭЛЕМЕНТ введене для ієрархічного опису структур даних і їх складових (наприклад, змінних і констант), а ЗАПОМИНАЮЩИЙ -- для опису структур і елементів пам'яті. Сенс понять ВЫЧИСЛИТЕЛЬНЫЙ і УПРАВЛЯЮЩИЙ елементи -- узвичаєні. Вхідними і вихідними параметрами можуть бути цифрові дані довільної структури.

Якщо як елемент використовується серійна (не та, що розробляється) ВІС з відомим набором функцій, то з усіх формальних параметрів на даному рівні опису може використовуватися частина з них або замінюватися фактичними параметрами. Введений опис підпрограм як послідовностей операцій тільки над змінними даного рівня опису. ПОДПРОГРАММА не може мати внутрішніх змінних або констант. Цим поняття підпрограми відрізняється від прийнятого в PL/1. Підпрограма використовується для виділення ділянок, що повторюються в алгоритмі функціонування і описується як елемент, але без зазначення типу. Лексичний і семантичний механізми динамічного опису системи у ВІС-реалізації в основному запозичені у Дійкстри - Дала як послідовності синхронних і асинхронних подій. Для синхронізації послідовних процесів введені спеціальні типи керуючих змінних -- СЕМАФОР і БУФЕР, зміст яких аналогічний прийнятому у Дійкстри.

Семантика мови характерно виражена засобами опису алгоритмів функціонування елементів і підпрограм. При визначенні послідовності зміни станів системи (подій) використовується інформація про відповідність вхідних і вихідних параметрів, а також алгоритми перетворення параметрів і обробки керуючої інформації. Для запису цих алгоритмів використовуються оператори мови PL/1, а також спеціальні, введені Дійкстрою для опису синхронізації “роботи” елементів. Ці ж засоби використовуються для підпрограм. Але на відміну від засобів мови PL/1 тут введене поняття описаної операції, що притаманна тільки даній ВІС і яку без цього поняття необхідно громіздко виражати традиційними засобами: <описание операции>::=<имя операции>. <разрядность> (<список параметров>). Для зменшення довжини опису при багаторазовому використанні одного елемента вводиться індексація елемента та його параметрів.

Повний синтаксис експериментальної версії мови містить у собі всі необхідні конструкції та засоби для багаторівневого низхідного опису довільної обчислювальної системи з ВІС-реалізацією. Основні поняття і конструкції наступні:

<лексическая часть>, БЛОК, <спецификации переменных>, <описание переменной>, СПИСОК, ДЕРЕВО, СЕТЬ, <семантическая часть>, ПОДПРОГРАММА, <описание операторов>, <выражение>.

<синтаксическая часть>::=<конфигурация> <статическое описание> <динамическое описание>

Поняття КОНФИГУРАЦИЯ введене для визначення інформаційних зв'язків між елементами і підпрограмами. Це перелік елементів із зазначенням фактичних параметрів. При описі конфігурації елементи можуть об'єднуватися в структури, а вони описуються аналогічно прийнятому в PL/1 опису структур, але замість імен змінних підставляються імена елементів із списками фактичних параметрів. Окрім традиційних структур, відповідних структурам даних, введені поняття КОНВЕЙЕР, СТЕК, МАГАЗИН, а сенс конструкції <динамическое описание> пояснений в абзаці лексики.

Заключним блоком результатів розділу III є розробка експериментальної версії синтаксису мови багаторівневого алгоритмічного опису логічних специфікацій НВІС. Ця розробка виконана на основі базової мови АЛГОРИТМ як відомої, випробуваної і доступної. З конструкцій цієї мови вибрана підмножина засобів, істотно необхідних для опису проектних специфікацій логічного етапу, для яких припускається апаратна реалізація. У зв'язку з цим в цю підмножину не включені інші засоби мови, призначені головним чином для опису програмних підсистем проектованого об'єкта. Виконане розширення цієї підмножини за рахунок додання засобів опису функцій, в особливості булевих, а також дерева поняття <микропрограмма>. На відміну від мови PINLAN сюди свідомо не додані засоби опису функціональних і електричних схем НВІС, що визначені нині як стандартні (наприклад, в схемних редакторах Future Net, P CAD і багатьох інших), і можуть бути включені в мову окремим блоком при необхідності. Основні поняття і конструкції в синтаксисі мови такі:

ієрархічний логічний надвеликий інтегральний

АЛГОРИТМ, ОПИСАНИЕ, <описание массивов>, <описание переменных>, <описание констант>, <описание функций>, <описание подпрограмм>, <микропрограмма>. Істотно поширені поняття <кодовое выражение> і <оператор>. Наведений повний синтаксис мови, названої МИКРОАЛГОРИТМ.

Центральним блоком результатів дисертації є розробка основ теорії, математичних механізмів, алгоритмів, засобів і методик, “наповнючих” умовну оболонку методології логічного синтезу (розділи IV і V).

Нині асинхронні автоматні моделі і схемотехніка отримали “нове дихання” у середовищі НВІС. У вищерозглянутій багаторівневій моделі виділяється її фрагмент -- низхідна гілка з дерева моделей: асинхронна мережа автоматів асинхронний автомат асинхронна схема -- як модель послідовнісного пристрою в НВІС-реалізації. Тоді задача отримання коректної асинхронної схеми зводиться до задачі ієрархічного синтезу асинхронного автомату, що задається відомою шісткою A<, X, Y, (a, x), (a, x), a₀>. Коректність асинхронної схеми, нечутливої до величин затримок у ланцюжках логічних елементів по Ейхельбергеру, досягається виключенням явища логічного ризику.

Для визначення необхідних математичних механізмів і створення методики ієрархічного синтезу коректних асинхронних схем сформовані такі поняття і визначення: довільний перехід <a_i, a_j> автомата, умови U_ij переходу <a_i, a_j>, асинхронного (по Мілеру) автомата, вхідні та вихідні структурні сигнали структурного автомата , ризик, кодування станів з безпосередніми переходами.

Означення 1. Логічний ризик стійкого стану a_j назвемо некритичним, якщо для будь-яких двох станів a_k , a_l (a_i , a_j ) і будь-якого сигналу x Uij (a_k , x) = (a_l , x). У протилежному випадку -- ризик критичний.

Нехай U_ij і U_kl -- умови переходів <a_i, a_j> і <a_k, a_l> відповідно.

Означення 2. Назвемо зв'язаними переходи <a_i, a_j> і <a_k, a_l> часткового асинхронного автомата щодо умови U тоді і тільки тоді, коли a_i a_j a_k a_l , ( U_ij ?U_kl ) U 0, і не зв'язаними в противному випадку.

На підставі цього в дисертації доведено необхідність і достатність наступної теореми.

Теорема 1. Кодування станів асинхронного автомата буде протиризиковим, коли будь-яким станам, що утворюють пару (<a_i, a_j>, <a_k, a_l>) зв'язаних переходів, зіставлені набори , такі, що кожний набір з підмножини не перетинається з кожним набором підмножини .

У дисертації показано, що від вигляду функцій збудження елементів пам'яті структурного автомата і його структурної функції виходу істотно залежить їх економічна реалізація логічними примітивами з бібліотеки вибраного типу НВІС. У свою чергу, вигляд цих функцій визначається вибраним варіантом (протиризикового) кодування. У реферуємій роботі показано, яким чином одержаний варіант кодування передбачає кількість літер у термі та кількість термів у диз'юнктивній нормальній формі вищезазначених функцій. Елементом пам'яті структурного автомата вибраний тригер SR_k з роздільними входами s_k -- одиничним і r_k -- нульовим як найбільш економічний серед примітивів бібліотек НВІС.

Функція s_k подана диз'юнктивною нормальною формою (д.н.ф.) у вигляді:

, (4)

де U_ij -- умова переходу <a_i , a_j>, T_ij -- терм, що задає множину проміжних наборів. Звідси

Переходу < a_i , a_j > автомата, функції збудження s_k (або r_k) ставиться у відповідність добуток T_ij внутрішніх змінних, або кожному переходу < a_i , a_j > в д.н.ф. функції збудження відповідає диз'юнктивний член

D_ij = U_ij T_ij (5)

Функція збудження нульового входу елемента пам'яті SR_k

, (6)

де -- підмножина множини P всіх переходів <ai, aj>, таких, що при переході () змінна b_k змінює своє значення з одиниці на нуль.

Позначимо t довжину терму T_ij , u_ijmax -- максимальне число літер в будь-якому термі д.н.ф. U_ij =, а -- число термів вигляду (4), (6) в д.н.ф. функції s_k (r_k).

У сучасній проблемі логічного проектування схемотехніки НВІС одне з ключових питань -- якого вигляду повинна бути д.н.ф. функцій збудження і виходів, щоб ця д.н.ф. максимально враховувала всі логічні обмеження більшості існуючих НВІС. Іншими словами, яка кількість літер в кон'юнкції і яку кількість самих кон'юнкцій допустимо для реалізації примітивами даної бібліотеки НВІС.

Дослідження автором доступних бібліотек примітивів фірм Xillinx, ALTERA, Motorola, Cypres, Intel та інших існуючих і тих, що розробляються нині матричних НВІС і ПЛІС показали, що логічні обмеження бібліотечних примітивів такі: m_об -- число вхідних каналів примітивів типу AND, що звичайно не перевищує значень m_об = 2  4; l_об -- число вхідних каналів примітивів типу OR (l_об = 24, 6); n_разв -- коефіцієнт розгалуження (допустиме навантаження) вихідного каналу будь-якого логічного примітива (звичайно n_разв = 3  5 або 7  10, а для потужних n_разв = 15 або 20 або 30). Кожний примітив або логічна макрочарунка ПЛІС характеризується ще обмеженням -- це час, на величину якого сигнал затримується, що задається звичайно граничними значеннями (_{min    max}). Якщо при реалізації виразів s_k, r_k, yi бібліотечними примітивами виявляється, що m_об < t_ij + u_ij , l_об <  і число входжень одного і того ж символу (внутрішньої змінної) в системі булевих функцій (s₁,...,s_k, r₁,...,r_k, y₁,...,y_k) перевищує величину n_разв й іншого вибору немає, то реалізація таких д.н.ф. потребує, з одного боку, збиткову кількість примітивів і найчастіше, макрочарунок, а з іншого -- збільшення глибини комбінаційної схеми з цих елементів, внаслідок чого може бути перевищена величина сумарне і виникнути ситуація, подібна логічному ризику в схемі. Отже, доцільно проводити синтез асинхронного автомата взагалі, і кодування його внутрішніх станів, зокрема таким чином, щоб у результуючих д.н.ф. максимальні величини m_об, l_об, n_разв і _сум не перевищували відповідних максимальних значень логічних примітивів з наявного бібліотечного набору. Природно, що ці задачі повинні вирішуватися спільно з задачами виключення ризику тривкого стану і ризику вихідних сигналів за всіма аргументами. Покажемо, як це зробити, наприклад, на етапі знаходження економічного (в сенсі врахування вищезазначених обмежень) протиризикового кодування внутрішніх станів довільного асинхронного автомата, а також, як подолати скруту перебору великої кількості варіантів кодування і отримати єдине, що задовольнить обмеження. Нехай -- набори внутрішніх змінних внутрішніх станів a_i, a_j, a_k, a_l зв'язаних переходів < a_i , a_j > і < a_k , a_l >.

...