.

Розвиток теорії і розробка методології логічного синтезу НВІС на основі багаторівневих автоматних моделей: Автореф. дис… д-ра техн. наук / Є.Л. Дени

Язык: украинский
Формат: реферат
Тип документа: Word Doc
0 4713
Скачать документ

НАЦІОНАЛЬНА АКАДЕМІЯ НАУК УКРАЇНИ
ІНСТИТУТ КІБЕРНЕТИКИ ІМЕНІ В.М.ГЛУШКОВА

ДЕНИСЕНКО ЄВГЕНІЙ ЛЕОНІДОВИЧ

УДК 681.326.3

РОЗВИТОК ТЕОРІЇ І РОЗРОБКА МЕТОДОЛОГІЇ
ЛОГІЧНОГО СИНТЕЗУ НВІС НА ОСНОВІ
БАГАТОРІВНЕВИХ АВТОМАТНИХ МОДЕЛЕЙ

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

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

Київ – 1999

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

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

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

Офіційні опоненти: доктор технічних наук, професор,
член-кореспондент НАН Республіки Бєларусь
Закревський Аркадій Дмитрович,
Інститут технічної кібернетики
НАН Республіки Бєларусь,
головний науковий співробітник,
доктор технічних наук, професор,
Рабінович Зіновій Львович,
Інститут кібернетики НАН України,
головний науковий співробітник
доктор технічних наук
Баркалов Олександр Олександрович,
професор кафедри електронних обчислювальних машин Донецького державного технічного університету.

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

Захист відбудеться ” 15 ” квітня 1999 г. о 14-00 час. на засіданні спеціалізованої вченої ради
Д 26.194.03 при Інституті кібернетики НАН України за адресою: 252022, Київ, проспект Академіка Глушкова, 40.

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

Автореферат разісланий ” 10 ” березня 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). В зв’язку з тим, що процеси крізного проектування НВІС як висхідний, так і низхідний є ієрархічними, багаторівневими, то й особливості НВІС доцільно аналізувати відповідно цим рівням. Основні з них по висхідній ієрархії такі:
конструкторсько-технологічні:
— найбільш розповсюджені кристали, що реалізуються по КМОП-технології, площею, як правило, не більше 1010 мм2. Рекордні кристали мають розміри: Celeron 300A/333 – 9.814.6 мм2, кристали комплекту Америка — 12.712.7 мм2;
— кристали упаковуються в стандартні корпуси таких типів: DIP-корпус, що є до 48 двурядових виводів; PLCC-корпус, що має від 68 до 84 виводів, розташованих по периметру корпусу; PGA-матричний корпус, що має від 208 до 591 виводів; корпуси комплекту Америка мають від 256 до 300 штирьових виводів з матричним розташуванням.
Топологічні: найбільше розповсюдження набули НВІС з проектними нормами 0.25 мкм. В Європі досягнута цифра 0.3 мкм, а в США і Японії — 0.18 мкм. Мінімальна площа транзистора коли¬вається в межах 0.50.8 мкм2. Звичайні 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, а також дискретний перетворювач DT , запропонований В.М. Глушко¬вим і О.А. Летичевським, можуть бути використані як фрагменти вершинної частини багаторівневої моделі — моделі фрагментів архітектури НВІС. На основі аналізу секвенціаль¬ного і паралельного автоматів, запропонова¬них А.Д.Закревським, і послідовної і пара¬лель¬ної мереж абстрактних автоматів, запропонованих С.І.Барановим і А.Е.Кіеваліком, зроблений висновок про їх придатність у “кандидати” як моделей структурних рішень в зазначеній умовній оболонці. Показана аналогічна придатність для цієї мети автоматів усіх інших відомих різновидів як моделей мікропрограм, функціональних схем (послідовнісних і комбінаційних). Окрім цього, на основі праць Мід, Конвей і А.В.Ко¬би¬линсько-го, О.О.Зеле¬нев¬ської зазначена можливість подання фрагментів топології, в тому числі і з дефектами типу обривів, замикання та ін., і еквівалентних їм фрагментів електричних схем елементарними автоматами у дев’яти¬значному структурному алфавіті.
Виконаний аналіз свідчить про те, що всі вищезазначені відомі автоматні моделі та їхні композиції (мережі) можуть бути ієрархічними взаємозв’язаними “елементами” багаторівне¬вої моделі НВІС. Разом з цим підкреслено, що при переході від розв’язання задач системного етапу до розв’язання задач логічного етапу, наприклад від автомата, що інтерпретує, до мереж абстрактних або структурних автоматів, можливості перерахованих моделей недо¬стат¬ні. Для заповнення цієї “прогалини” були сформульовані наступні нові моделі. Так, моделлю фрагмента архітектури НВІС, більш деталізованою ніж інтерпретуючий автомат, може бути мережа магазинних перетворювачів :
} , (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. Коректність асинхронної схеми, нечутливої до величин затримок у ланцюжках логічних елементів по Ейхельбергеру, досягається виключенням явища логічного ризику.
Для визначення необхідних математичних механізмів і створення методики ієрархічного синтезу коректних асинхронних схем сформовані такі поняття і визначення: довільний перехід автомата, умови Uij переходу , асинхронного (по Мілеру) автомата, вхідні та вихідні структурні сигнали структурного автомата , ризик, кодування станів з безпосередніми переходами.
Означення 1. Логічний ризик стійкого стану aj назвемо некритичним, якщо для будь-яких двох станів ak , al  (ai , aj ) і будь-якого сигналу x  Uij (ak , x) = (al , x). У протилежному випадку — ризик критичний.
Нехай Uij і Ukl — умови переходів і відповідно.
Означення 2. Назвемо зв’язаними переходи і часткового асинхронного автомата щодо умови U тоді і тільки тоді, коли ai  aj  ak  al , ( Uij Ukl )  U  0, і не зв’язаними в противному випадку.
На підставі цього в дисертації доведено необхідність і достатність наступної теореми.
Теорема 1. Кодування станів асинхронного автомата буде протиризиковим, коли будь-яким станам, що утворюють пару (, ) зв’язаних переходів, зіставлені набори , такі, що кожний набір з підмножини не перетинається з кожним набором підмножини .
У дисертації показано, що від вигляду функцій збудження елементів пам’яті структурного автомата і його структурної функції виходу істотно залежить їх економічна реалізація логічними примітивами з бібліотеки вибраного типу НВІС. У свою чергу, вигляд цих функцій визначається вибраним варіантом (протиризикового) кодування. У реферуємій роботі показано, яким чином одержаний варіант кодування передбачає кількість літер у термі та кількість термів у диз’юнктив-ній нормальній формі вищезазначених функцій. Елементом пам’яті структурного автомата вибраний тригер SRk з роздільними входами sk — одиничним і rk — нульовим як найбільш економічний серед примітивів бібліотек НВІС.
Функція sk подана диз’юнктивною нормальною формою (д.н.ф.) у вигляді:
, (4)
де Uij — умова переходу , Tij — терм, що задає множину  проміжних наборів. Звідси
Переходу автомата, функції збудження sk (або rk) ставиться у відповідність добуток Tij внутрішніх змінних, або кожному переходу в д.н.ф. функції збудження відповідає диз’юнктивний член
Dij = Uij  Tij . (5)
Функція збудження нульового входу елемента пам’яті SRk
, (6)
де — підмножина множини P всіх переходів , таких, що при переході ( ) змінна bk змінює своє значення з одиниці на нуль.
Позначимо t довжину терму Tij , uijmax — максимальне число літер в будь-якому термі д.н.ф. Uij = , а — число термів вигляду (4), (6) в д.н.ф. функції sk (rk).
У сучасній проблемі логічного проектування схемотехніки НВІС одне з ключових питань — якого вигляду повинна бути д.н.ф. функцій збудження і виходів, щоб ця д.н.ф. максимально враховувала всі логічні обмеження більшості існуючих НВІС. Іншими словами, яка кількість літер в кон’юнкції і яку кількість самих кон’юнкцій допустимо для реалізації примітивами даної бібліотеки НВІС.
Дослідження автором доступних бібліотек примітивів фірм Xillinx, ALTERA, Motorola, Cypres, Intel та інших існуючих і тих, що розробляються нині матричних НВІС і ПЛІС показали, що логічні обмеження бібліотечних примітивів такі: mоб — число вхідних каналів примітивів типу AND, що зви¬чайно не перевищує значень mоб = 2  4; lоб — число вхідних каналів примітивів типу OR (lоб = 24, 6); nразв — коефіцієнт розгалуження (допустиме навантаження) вихідного каналу будь-якого логічного примітива (звичайно nразв = 3  5 або 7  10, а для потужних nразв = 15 або 20 або 30). Кожний примітив або логічна макрочарунка ПЛІС характеризується ще обмеженням  — це час, на величину якого сигнал затримується, що задається звичайно граничними значеннями (min    max). Якщо при реалізації виразів sk, rk, yi бібліотечними примітивами виявляється, що mоб і .
Означення 3. Назвемо внутрішню змінну, яка приймає одне і те ж значення в наборах і протилежне — в наборах , розв’язуючою щодо згаданих зв’язаних переходів і .
В дисертації доводиться необхідність і достатність наступної теореми:
Теорема 2. Для виконання умови теореми (1) необхідно і достатньо, щоб в наборах і існувала, принаймні, одна розв’язуюча змінна щодо цих наборів.
Означення 4. Процедурою розв’язування пари переходів (, ), зв’язаної (означення 2) стосовно умови U, назвемо введення змінної, що розв’язує, в набори і станів ai, aj, ak, al довільного асинхронного автомата.
Ця процедура покладена в основу алгоритму і методу, що сформульовані в реферуємій роботі, а також для зменшення кількості змінних в результуючій таблиці кодування. Метод дозволяє отримати задовільні результати, якщо число внутрішніх змінних, отриманих внаслідок його “роботи” такі, що mоб  s – 1 + u, де u — число вхідних каналів автомата. Якщо ця нерівність не задовольняється, то доцільно знаходження кодування із явно збитковим числом внутрішніх змінних, що визначає таке спрощення системи функцій збудження і виходів (ф.з.в.), коли дана нерівність задовольняється, як і враховуються всі вищезазначені обмеження. Відомі методи В.Г.Ла¬зарєва – О.І.Пійль, А.Е.Янковської, В.А.Склярова, Лю, Тресі, Хартманіса не придатні для цієї мети.
Для побудови методу протиризикового кодування, що визначає в системі ф.з.в. отримання апріорно заданих значень mоб , lоб , nразв , автор запропонував підхід і на основі його методи, які істотно використовують поняття розбиття на множині P переходів автомата на відміну від підходів вищезазначених авторів, що використали розбиття на множині  станів автомата. Відомо, що кожному варіанту кодування станів автомата може бути однозначно зіставлена система двоблокових розбиттів на множині станів цього автомата. Будь-яке розбиття на множині переходів може природно розглядатися як розбиття на множині станів, якщо множина P доповнена переходами (ai, ai), …, (al, al) i для будь-яких двох переходів та повинно існувати, принаймні, одне часткове розбиття, таке, що ці переходи належать різним блокам означеного розбиття. Для того, щоб побудувати систему S часткових розбиттів  на множині P переходів асинхронного автомата, що задовольняють вищезгаданим умовам, визначається операція розкладу множини P переходів за множиною ортогональних умов, що полягає в побудові k підмножин , кожна з яких (i=1,…, k) відзначається відповідною умовою Ui. Крім того, для здійснення переходу від системи S часткових розбиттів до системи двоблокових розбиттів на множині P переходів і для можливості виконання оптимізуючих перетворень цих систем визначаються операції об’єднання сукупностей переходів (результатом виконання операції об’єднання на сукупностях s1,…, sk є сукупність s, що відмічена умовою U і “розщеплення” станів автомата, для яких функції переходів і виходів визначаються так, як і для стану, що розщеплюється). Після цього формулюються обмеження на систему , такі, що їй може бути зіставлена система на множині станів (і відповідне протиризикове кодування), за якого у виразах системи булевих ф.з.в. задовольняються обмеження mоб , lоб , nразв і при цьому досягається мінімальне сум. Часто виявляється, що вигляд д.н.ф. ф.з.в., вибраної з (4), (6) як стандартної, відрізняється від того, що безпосередньо реалізується в базисах наявного набору бібліотечних примітивів (наприклад, дужковий запис булевих виразів неекономічно реалізується в базисах примітивів бібліотек ПЛІС типу ХС2000 і ХС3000). Так, умову Uij будь-якого переходу можна записати у вигляді Uij =  Ui , де Ui — диз’юнктивний член (кон’юнкція) довжини u. Тоді будь-який диз’юнктивний член Dij (10), що зіставляється у виразах ф.з.в. переходу , можна уявити у вигляді
. (7)
Звідси д.н.ф. функцій збудження кожному переходу , умові Ui , функції збудження sk (або rk) ставиться у відповідність терм Dij внутрішніх змінних. Внутрішній змінній dk відповідає двоблокове розбиття  = C; D, причому блок C зазначений “0” (“1)”, а блок D — “1” (“0)”. Позначимо R (Ui ,) множину переходів, зв’язаних (5) з щодо Ui . В системі двоблокових розбиттів нехай існує розбиття  = E; F, таке, що ai , aj  E. Позначимо символом L множину всіх переходів з R (Ui , ), таких, що їх перші проекції (пр1) містяться в E. Тоді можна довести що:
Твердження 1. Терм Uij складається з літер d1,…, dt , якщо містить розбиття ,…,t, такі, що ai , aj належать одному з блоків добутку розбиттів   ,…, t, наприклад E, а друга проекція від L належить F. Такі твердження сформульовані для різних значень t. Стосовно величини tн — нижньої оцінки t в дисертації доведене твердження:
Теорема 3. Існує протиризикове кодування станів довільного асинхронного автомата, таке, що будь-який терм Tij д.н.ф. ф.з.в. складається з однієї внутрішньої змінної. Нарешті, можна довести, що
Твердження 2 . f термів Dij відповідає множині G, що належить P переходів в д.н.ф. ф.з.в. sk або rk , якщо в системі розбиттів ,…,f , такі, що E є блоком добутку  ,…, f, такого, що g належить E, перша проекція від L належить E, а друга проекція від L належить D, де L належить R(ui,).
Сформульовані твердження для різних значень f.
На підставі цих результатів сформульований метод протиризикового кодування станів нор-маль¬ного асинхронного автомата, який наперед визначає в системах булевих функцій збудження і виходи величини mоб, lоб , і внаслідок цього — nразв. Однак вимірність задач, що вирішуються цим засобом інколи залишається великою. Для зменшення вимірності цих задач доцільно або використати авторський засіб декомпозиції початкового автомата, або у вхідному структурному алфавіті автомата використати синхронізуючі (тактуючі) сигнали. В останньому випадку автомат залишається асинхронним (без перетворення в синхронний), але істотно спрощується задача перетину множини P по множині ортогональних умов. В таких автоматах умова будь-якого переходу істотно залежить від змінної, відповідної тактуючому сигналу. Тоді при побудові системи двоблокових розбиттів на множині P переходів з заданими обмеженнями застосування операції розкладу (перетину) множини P по множині ортогональних умов зводиться до розкладу по множині ортогональних змінних, відповідних сигналам різних тактуючих серій.
Дана побудова проміжної специфікації — системи , що задовольнить побудові часткових розбиттів множини P відповідно синхронізуючим змінним. Формульні вирази систем двоблокових розбиттів множини P тактуємих автоматів при значеннях параметрів t = 1 такі:

Для t = 2, 3 вирази для систем S аналогічні. Всі вони містять в собі оціночну інформацію.
Обмеження на систему двоблокових розбиттів (на множині P переходів автомата), за яких число термів д.н.ф. sk і rk може бути зменшено за рахунок склеювання по внутрішніх змінних, якщо умова f  lоб не досяжна, зведені до таких:
Твердження 3. Терми Tij і Tkl функції sk (чи rk) відрізняються значенням тільки однієї змінної, якщо відповідне їй розбиття  = E; F, таке, що ai, aj  E і ak, al F — єдине.
Твердження 4. Dij і Dkl (Uij=Ukl) д.н.ф. sk (rk) склеюються, якщо серед розбиттів ,…,p в системі є єдине розбиття  = V; W, таке, що ai, aj  V і ak, al W, а будь-яке інше  = H; Z, таке, що або ai, aj , ak, al  H, або  Z.
Вищенаведені результати є теоретичною основою методу і алгоритмів кодування станів асинхронних тактуємих автоматів з урахуванням числа входів бібліотечних примітивів НВІС типу AND (NAND) (в дисертації — метод 4.3) і метод алгоритмів збиткового кодування, що враховують число входів примітивів типу OR (NOR, XOR) (у дисертації — метод 4.4).
Ці результати стали також основою для розробки спрощеного (порівняно з канонічним методом В.М. Глушкова) методу ієрархічного структурного синтезу асинхронних тактуємих автоматів, що враховує (практично) всі наявні нині логічні обмеження НВІС. Цей метод (у дисертації — метод 4.5) полягає в формульному визначенні д.н.ф. ф.з.в., вільних від логічного ризику за всіма аргументами безпосередньо по вхідному завданню (коректному алгоритму функціонуван¬ня) автомата і отриманій системі двоблокових розбиттів на множині P переходів з наступним тривіальним переходом до системи на множині станів, що задовольнять заданим обмеженням. Метод зводиться до визначення за формулою диз’юнктивного члена Uij  Tij відповідного переходу автомата A в д.н.ф. вигляду (8), (11) (власне, до визначення за формулою елементарного терму Tij , тому що Uij звичайно задається в алгоритмі), якщо Uij задається елементарним термом вхідних змінних. Наведені формули, що дозволять визначити такі елементарні терми за будь-якого значення t від 1 до 3, що обмежують їхню довжину. Кількість таких елементарних термів зменшується за рахунок зумовлених склеювань. У рамках методу запропонований спосіб виключення ризику вихідного сигналу, якщо його тривалість перевищує тривалість тактованого шляхом додання до результуючої системи двоблокових розбиттів на множині станів автомата одного додаткового (у випадку необхідності, коли ризик не виключений випадково внаслідок побудови систем і ) розбиття де Zi — множина станів, на яких yi =1 (0), а \Zi — множина всіх інших станів множини , на яких yi = 0 (1) або його значення невизначено і може бути довизначено довільно. Якщо обмеження на mоб, lоб і nразв задовольняються, то сумарне значення сум сумарної затримки сигналу в схемі буде мінімальним, а швидкодія схеми — максимальною.
У багаторівневих системах управління сучасних НВІС і обчислювальних систем існують і продовжують розроблятися блоки, для яких вимоги досягнення максимальної швидкодії істотно послаблені, а вхідні алгоритми надто великі (понад ста міток). Такими є блоки мікро¬програмного управління, основані на моделі синхронного (по Хартманісу, Мілеру, Ангеру) автомата.
Виконане дослідження (розділ V) сучасного стану питання і аналізу управляючих систем в НВІС-реалізації від популярних моделей ПЕОМ фірм Intel і Motorola до останніх розробок конвейєрник архітектур НВІС Power 603 і Pentium 100 показують, що при досягненні частот понад 100 Мгц, незважаючи на тенденцію збільшення частки асинхронних приладів і схем, частка мікропрограмних приладів (блоків) управління (МПУ) залишається значною. Удосконалення структур МПУ від структури Уілкса – Стрінжера до сучасних, незважаючи на успішне розв’язан¬ня багатьох задач, дві з них як центральні не були розв’язані. По-перше, це задача кодування полів звичайно в межах двох критеріїв: ефективної взаємодії і простоти реалізації в вибраному логічному базисі з відповідними обмеженнями. По-друге, це задача формування адресації мікро-команд або задача проектування систем адресації. Для теоретичного обгрунтування розв’язання першої задачі сформульовані такі поняття: системи W = = {w1,…, wt} мікрокоманд МПУ; системи мікрооперацій (МО); маски N, набору масок П, вектора масок . Використані означення Граселі – Монтанарі сумісності мікроопера¬цій, класу С сумісності, максимального класу сумісності.
Означення 5. Результатом маскування МК wi (і =1,…, t) вектором класів сумісності при заданому наборі класів сумісності називається МК , що задовольняє рівності
. (8)
Введемо також множину  всіх підмножин МК wi (i =1,…, t). На основі цього сформульовані наступні дві задачі маскування:
перша — знайти мінімальний набір класів сумісності , у якого для будь-яких w   і wi  w існує вектор класів сумісності , що задовольняє виразу
; (9)
друга — знайти мінімальний набір класів сумісності , що задовольнить такій вимозі: для будь-якого w   існує МК wi і вектор класів сумісності , для яких
. (10)
У процесі розв’язання задач в дисертації першим проміжним результатом сформульований алгоритм, що зводить задачу побудови мінімального набору класів сумісності до частинного вигляду задачі цілочисельного лінійного програмування — до задачі покриття. Виконаний аналіз визнаних методів розв’язання задач покриття і вибраний метод А.Д. Закревського, що використовує поняття дерева пошуку. Цей метод спрощений шляхом перетворення даних вхідної задачі, де множину МО уявлено графом :
1. Якщо деяка вершина i з’єднана з множиною I вершин, а вершина j — з множиною J вершин, причому (i I) & (i I) & ((I \ j)  (J \ i)), то вершина j може бути усунена з графа  з наступною корекцією розв’язання цієї задачі.
2. Якщо граф  не є зв’язним, то задача може бути розбита на декілька незалежних підзадач.
3. Розв’язання задачі може бути знайдено серед максимальних класів сумісності (по Закрев-ському). Зауваження 1, 2 використовуються для спрощення графа вхідної задачі, зауваження 3 — для спрощення системи нерівностей для власне задачі покриття. На підставі викладеного сформу-льо¬ваний алгоритм розв’язання вхідної задачі, а пошук мінімального покриття виробляється у відповідності з блок-схемою алгоритму, наведеного в реферуємій роботі (в дисертації рис. 5.5).
У рамках методики проектування мікропрограмних ПУ розв’язана також задача проектування системи адресації мікрокоманд (САМ), яка формулюється так.
Нехай задані мікропрограма M, множина її вхідних наборів x = {x1,…, xt}, вибраний сторін-ковий засіб адресації і необхідно визначити множину C = {C1,…, Cl} класів вхідних наборів, розмір сторінки мікропрограмної пам’яті (розрядність n1 поля адреси МК), мінімізуючий обсяг цієї пам’яті
, (11)
де N1 — кількість сторінок в мікропрограмній пам’яті.
Нехай максимальна потужність  вхідного набору xi серед елементів множини X
(12)
Тоді справедливі наступні обмеження:
; (13)
. (14)
Друга задача проектування САМ — визначення оптимальних розмірів сторінки.
Нехай задана мікропрограма M={w1,…, wN } і евристично вибраний розмір сторінки . Вибравши підмножину , що міститься на одній сторінці, однозначно визначається множина МК переадресацій на інші сторінки така, що потужність об’єднан-ня . Тут істотно наступне обмеження, визначальна вимога до максимальних класів суміс¬но¬сті: . Будується матриця елементів Bij , рядки якої позначені wi (i = 1,…, N), де N — число мікрокоманд в M з урахуванням МК переадресації, стовпці Cj ( j = 1,…, n) всіх можливих варіантів розміщення мікропрограми M в сторінках заданого розміру. Сформулювавши систему обмежень і функцію мети аналогічно попередній задачі, зводимо задачу розбиття мікропрограми за критерієм мінімуму числа сторінок до задачі покриття.
Використання методу “упаковки” для розв’язання даної задачі вимагає визначення максимальних класів сумісності на множині вершин графа G (M). Визначається верхня межа для цих класів шляхом розрізування графа G (M) з урахуванням подальшої властивості розбиття (декомпозиції) мікропрограми. Якщо мікрокоманда wi (i = 1,…, N), де N — число міток у мікропрограмі M, належить фрагменту Mj ( j = 1,…, k) від M, то цьому ж фрагменту належать усі мікрокоманди — її приймальники і в відображенні на G (M) є околом вершини vi фрагменту G (mj) графа G (M). Тоді задача, що розв’язується, полягає в розрізуванні графа G (M) на фрагменти G (Mj) при обмеженнях і мінімізації k. Як в задачах розбиття множини мікрооперацій або множини вхідних наборів (сигналів) на класи, дана задача зводиться до побудови максимальних класів сумісності (алгоритми якого в дисертації наведені в розділі 5.4), вилучення не максимальних шляхом попарного порівняння і розв’язанню відповідної задачі покриття.
Всі перераховані вище теоретичні результати, алгоритми і методи складають методику логічного проектування мікропрограмних пристроїв управління в логічних базисах ПЗП або ПЛМ.
У шостому підсумковому розділі завершується досягнення поставленої мети — побудова методології багаторівневого логічного синтезу НВІС. Показана побудова багаторівневої автоматної моделі НВІС як основоположного стрижня методології (розділи 6.1, 6.2), її верхніх частин — мережі дискретних (магазинних) перетворювачів, що деталізується на стику системного і логічного етапів в мережу мереж операційних (запропонованих), мереж секвенціальних, паралельних і звичайних управляючих автоматів. Паралельно моделі в процесі логічного проектування вишикується багаторівнева ієрархія алгоритмічних і структурних описів до рівня міжрегістрових пересилок або мікропрограм. Проведений аналіз і запропоновані рекомендації по вибору того чи іншого методу синтезу, який іде вниз від рівня мікропрограм. Далі описана (в дисертації — розділ 6.3) конкретна версія методології як логічної надбудови синтезу логічних схем в середовищі матричних НВІС з архітектурою LCA типу XC2000. Визначені всі логічні обмеження цього середовища: логічний ризик (при асинхронній реалізації), число входів і коефіцієнт розгалуження, тип елемента пам’яті, значення величини затримок у різних макрочарунках і обмеження на кількість бітових трас міжз’єднань. На основі цього розроблені стратегія експертного вибору кодування станів (з використанням авторських результатів — глава 4) і власне сама тактика кодування в рамках обмежень. У рамках методології адаптований до заданих обмежень запропонований раніше спрощений метод структурного синтезу, що дозволить отримати оптимальну реалізацію внутрішніх змінних і систем булевих функцій збудження і виходів примітивами бібліотеки Future Net. Запропонований простий (порівняно із асимптотичними) метод оцінки ефективності проектних специфікацій, які одержані внаслідок синтезу, що дозволить визначити число умовних еквівалентних вентилів, які витрачаються на реалізацію послі¬дов¬ніс¬ної схеми. Для макрочарунок вводу-виводу
, (15)
де , — потужності вхідного і вихідного алфавітів, kвв — постійний коефіцієнт.
Суттєвість оцінки грунтується на суті авторського методу структурного синтезу: кожному переходу автомата відповідає диз’юнктивний член (кон’юнкція) Dij. Звідси
, (16)
де , — кількість елементів в часткових розбиттях на множині переходів, KCLB — коефіцієнт, визначальна кількість еквівалентних вентилів в логічній макрочарунці (CLB), N — число станів автомата. Наведені аналогічні вирази для елементів пам’яті різноманітних типів і вираження , що дозволить визначити кількість еквівалентних вентилів на реалізацію функції виходу. Остаточний вираз для трьох різноманітних засобів кодування станів, коли p=1, p=2 і p=] log2N [ такий:
, (17)
, (18)
. (19)
Сумарний вираз для всієї послідовнісної схеми, що реалізує автомат A:
. (20)
Розроблені рекомендації по оптимальній реалізації системи булевих функцій і елементів пам’яті автомата, використані при реалізації логічних схем примітивами з бібліотеки Future Net CAD-пакету XAСT. Також показано, що логічна схема, одержана внаслідок авторського методу синтезу є регулярною, за винятком місць “галуження”, і тому добре компонується, розміщується і трасується (див. додаток А дисертації) з мінімальною величиною сум сумарної затримки. Якщо стопроцентна розводка сполучень не досягається, що частіше має місце у евристично створюваній схемі, то пропонується метод поліпшення якості трасування НВІС і багатошарових друкованих плат. Суть методу полягає в створенні процедури побудови “недотрасованих” трас, що враховує деформацію раніше проведених, і являє собою модифікацію хвильового алгоритму Лі. На відміну від алгоритму Лі необхідно зберігати в пам’яті масив, що визначає S стани всіх дискрет, а також запам’ятати L–mun джерела фронту хвилі. Безпосередня деформація (незавершених) трас виробляється шляхом їх перепроведення, що забезпечує оптимальну форму траси в сенсі мінімізації її довжини (і відповідно мінімізації величини сум ) і числа перегинів. У рамках методології запропонований метод налагодження послідовнісних схем, що не вимагає притягнення додаткових логічних інструментальних засобів, але за допомогою наявних в CAD-пакеті XAСT моделюючих підсистем SILOS, SIMUL і FLEX, дозволяє одержати гарантовано вірогідні, дієздатні логічні проектні специфікації.
Завершують розділ обгрунтовані авторські рекомендації по використанню методології в інших інструментальних логічних середовищах, наприклад, в середовищі ПУЛЬС (розроб¬ки ІТМ і ОТ — Москва) і в середовищі OrCAD SDT. Показано, як не складно “настроюва¬ти” основні математичні механізми методології до логічних обмежень цих CAD-пакетів.
У додатку А наведений приклад використання авторської методології для чотирирівне¬вого логічного проектування модуля асоціативної регістрової пам’яті редукційно-потокової ПЕОМ. Даний приклад виконано автором самостійно, а весь проект ПЕОМ — спільно з відділом № 255 Інституту кібернетики ім. В.М.Глушкова НАН України і НВО “Вимпел”, Москва.
Показана багаторівнева коректна деталізація в проекті від 3 станів функціонального опису через два проміжні (деталізація і уточнення), до 32 станів в заключному варіанті. Наведені відпо-від¬ні граф-схеми, проміжні проектні специфікації (таблиця кодування, системи булевих функцій збудження і виходів), коректна “відлагоджена” регулярна логічна схема і топологічна схема модуля в кристалі XC 2018PC84-70, де задіяні 66-логічних макрочарунок, що відповідає оцінкам (57-60). Експериментальні проекти цього модуля синтезовані іншими засобами вимагають більше 100 макрочарунок, тобто навіть не містяться в такому обсязі і, природно, не трасуються.
У додатку Б стисло описаний експериментальний проект програмної реалізації фрагмента методології. Лінгвістичне забезпечення в ньому містить засоби опису мікропрограм, операційних автоматів, примітивів та макросів бібліотеки Future Net, таблиць кодування як розширен¬ня підмножин мов (див. розділ II). Програмне забезпечення (що реалізувалося частково) містить засоби синтезу МПА з обмеженнями: кількість станів  1000, кількість МК —  256, розрядність МК  128, кількість Uij  128.

ОСНОВНІ РЕЗУЛЬТАТИ ТА ВИСНОВКИ
Головний підсумковий результат даної роботи — розв’язання значної прикладної проблеми — створення ефективної прикладної теорії, обгрунтованої методології і комплексу апробованих методик і методів ієрархічного логічного синтезу послідовнісних схем НВІС, що задовольняють усі логічні обмеження [1,11,12].
Суть методології полягає в п’яти її складових здійснених розробок:
I. Теоретичною базою розробленої методології логічного синтезу НВІС є такі результати, отримані як розвиток прикладної теорії автоматів:
1.1. Побудовані багаторівнева деревоподібна автоматна модель НВІС і модель “ліс” (як сукупність багаторівневых моделей) обчислювальних систем з різнорідних НВІС для системного аналізу і синтезу в задачах логічного проектування НВІС високої складності [1,12].
1.2. Запропоновані автоматні моделі деяких фрагментів архітектури і структури НВІС: мережа магазинних перетворювачів, мережі секвенціальних та паралельних автоматів, що дозволяють формалізувати задачі системного етапу і здійснити формальний перехід від системних моделей до логічних [1,10].
1.3. Вперше сформульована і доведена сукупність теорем та пропозицій, на засаді яких вилучається логічний ризик у довільних асинхронних автоматах і логічних схемах, які засновані на механізмі ортогонального кодування з урахуванням “достатніх” умов тривалості вихідних сигналів [1,2,16].
1.4. Запропоновано операції розкладання та розрізу множини переходів асинхронного автомата по множині ортогональних умов. На цьому вперше сформульовані пропозиції і доведена їх достатність, на яких в процесі ієрархічного синтезу булевих функцій збудження і виходів точно задовольняються логічні обмеження на кількість входів примітивів типу AND і OR і коефіцієнт розгалуження виходу [1,2,13,16,25].
II. Методика багаторівневого ієрархічного синтезу асинхронних послідовнісних пристроїв у межах відомих нині логічних обмежень НВІС різноманітних типів: БМК, ПЛІС, ПЛМ та ін. [1,2,16].
Методика містить в собі математичні “механізми” адаптації до різноманітних значень логічних обмежень і дозволяє одержувати послідовнісні схеми максимально досяжної швидкодії, що задаються кількістю “обладнання” за цих обмежень.
III. Методика ієрархічного проектування систем багаторівневого мікропрограмного управ-лін¬ня НВІС і обчислювальних систем в базисах ПЛМ і ПЗП [1,4-6,18,19].
Методика побудована на умовах отримання диз’юнктивних нормальних форм, близьких до найкоротших, і містить “механізм” диз’юнктивного “вписування” на входах системи адресації. Це дозволяє формально одержувати рішення, порівняні з кращими інженерними.
IV. Система методів логічного синтезу, що є складовою методології, утворена з таких:
4.1. Метод протиризикового кодування станів асинхронних автоматів без обмежень [1]. Простота в реалізації і ефективність методу сприяли його включенню до багатьох CAD-пакетів.
4.2. Три методи протиризикового кодування станів автомату, передвизначаючі його оптимальну реалізацію мережею (схемою) з примітивів типу AND, OR і вибраного типу тригера з заданими обмеженнями [1,2,13,16].
4.3. Метод ієрархічного синтезу структурного автомата, що дозволить отримати оптималь¬ні за кількістю примітивів регулярні схеми з максимальною швидкодією. На відміну від ві¬до¬мих канонічних методів синтезу тут знижується вимірність задачі, що вирішується за раху¬нок виключення ресурсоємних процедур перебору і алгоритмів мінімізації булевих функцій [16].
4.4. Метод покриття в задачі кодування мікрокоманд. Він дозволяє отримати розв’язок, близький до оптимального як в цій задачі, так і в інших, які можуть бути зведені до задачі покриття [4].
4.5. Метод проектування систем адресації мікропрограмних пристроїв управління, що оптимально реалізуються в логічних базисах ПЛМ та ПЗП з економічним розміщенням мікро-програм (в пам’яті) [5,6].
4.6. Метод оцінки ефективності синтезованих проектних специфікацій [3]. На відміну від відомих громіздких методів оцінки інженерних рішень і асимптотичних оцінок складності даний метод дозволяє за алгоритмом функціонування досить точно оцінити, з точністю до булевої змінної, складність систем булевих функцій збудження та їхню реалізацію в примітивах і макросах вибраної бібліотеки НВІС [3].
4.7. Метод поліпшення якості трасування НВІС та багатошарових друкованих плат. Він дозволяє покращити деякі “повні” (близько 100%) трасування або дотрасувати “неповні”, що неможливо дотрасувати іншими методами та засобами [14,15].
V. Дві версії алголо – і PL-подібних мов для багаторівневого опису НВІС і обчислювальних систем. Розроблені лексика, семантика і повний синтаксис кожної мови [7,8,24]. У мовах втілена спроба реалізації ідеї “абстрактної конфігурації”, що дозволить однаково деталізувати багато які мовні конструкції всіх рівнів у низхідному процесі логічного проектування.
Методологія логічного синтезу фрагментарно впроваджена в автоматизованій системі проектування обчислювальних машин і систем (ПРОЕКТ), в системах УАССМА ЕС (Санкт-Петербург) і АВТОМАТ (Мінськ), а також в навчальних процесах ряду вузів.
Народногосподарське значення методології ілюструється її різноманітністю застосування і складових фрагментів при логічному багаторівневому проектуванні ряду спецпроцесорів і спец-пристроїв в Інституті кібернетики ім. В.М.Глушкова НАН України по госпдоговірній тематиці (з ЦКБ “Алмаз”, Москва; РКБ “Гло¬бус”, Рязань; ЛКТБ ЛОЭП “Світлана”, Санкт-Петербург та ін.), в НДДКР по створенню ма¬кет¬них зразків міні-ЕОМ СОУ і ПЕОМ ряду “Нейрон” на ВО ім. С.П.Ко¬-рольова (Київ), у НВО “Мікропроцесор”, в проекті редукційно-потокової ППЕОМ (з НВО “Вимпел”, Москва) та ін.

ОСНОВНІ ПОЛОЖЕННЯ ДИСЕРТАЦІЇ
ОПУБЛІКОВАНІ В ТАКИХ ПРАЦЯХ:

1. Микропроцессорные системы обработки информации: проектирование и отладка / А.В. Палагин, Е.Л. Денисенко, Р.И. Белицкий, В.И. Сигалов. — Киев: Наук. думка. — 1993. — 352 с.
2. Денисенко Е.Л. Иерархический синтез асинхронных автоматов на программируемых логических интегральных схемах (ПЛИС) с учетом ограничений // УСиМ. — 1997. — № 1/3. — С. 72 – 77.
3. Денисенко Е.Л. Метод оценки эффективности проектных спецификаций, получаемых в результате синтеза асинхронных автоматов на ПЛИС // Там же. — № 4/5. — С. 41 – 43.
4. Белицкий Р.И., Денисенко Е.Л., Палагин А.В. Метод покрытия в задаче кодирования микрокоманд // Там же. — 1977. — № 6. — С. 74-81.
5. Денисенко Е.Л., Палагин А.В., Рокитский А.Г. Проектирование систем адресации микропрограммных устройств управления // Там же. — 1983. — № 4. — С. 33-36.
6. Денисенко Е.Л., Палагин А.В., Цатрян К.Ж. К задаче проектирования систем адресации микропрограммных устройств управления и размещения микропрограмм в памяти // Там же. — 1985. — № 2. — С. 24-25.
7. Денисенко Е.Л., Палагин А.В., Полонская Н.С. Принципы организации базы данных и язы¬ка описания элементов микропроцессорных БИС // Там же. — 1985. — № 3. — С. 29-32.
8. Денисенко Е.Л., Палагин А.В., Полонская Н.С. Построение языка описания вычислительных систем на микропроцессорных БИС // Там же. — 1985. — № 4. — С. 28-30.
9. Денисенко Е.Л. О практическом использовании методологии логического синтеза устройств и систем // Там же. — 1998. — №2. — С. 94–95.
10. Денисенко Е.Л. Сеть параллельных автоматов// Там же. — 1998. — №3. — С.34–36.
11. Denisenko E.L., Slobodjanjuk T.F. Hierarchical Design of Custom VLSIs for Control Computers // Intern. collection of research reports: Diagnosis, reliability and alarm management. — Budapest, Computer and Automation Institute, Hungarien Academy of Sciences. — 1990. — P. 181-197.
12. Денисенко Е.Л. Методология проектирования СБИС // Проектирование и применение средств микропроцессорной техники. — Киев: Ин-т кибернетики им. В.М.Глушкова АН УССР, 1986. — С. 28-31.
13. Денисенко Е.Л. Достаточные условия кодирования состояний автомата, реализуемого ПЛМ минимальной площади // Средства микропроцессорной техники. — Киев: Ин-т кибернетики им. В.М. Глушкова АН УССР, 1987. — С. 54-50.
14. Денисенко Е.Л., Местман Б.Я. Принципы построения подсистемы проектирования топологии в системе иерархического сквозного проектирования СБИС // Проектирование элементов и узлов ЭВМ. — Киев: Ин-т кибернетики им. В.М. Глушкова АН Украины, 1988. — C. 35-38.
15. Местман Б.Я., Денисенко Е.Л. Алгоритмы улучшения качества трассировки многослойных печатных плат и кристаллов СБИС // Микропроцессорная техника. — Киев: Ин-т кибернетики им. В.М. Глушкова АН Украины, 1988. — С. 60-64.
16. Денисенко Е.Л., Горбунов С.К. Иерархический синтез последовательностных схем, реализуемых матричными ПЛИС // Микропроцессорная техника. — Киев: Ин-т кибернетики им. В.М.Глушкова АН Украины, 1992. — С. 21-30.
17. Метод отладки последовательностных схем (синтезированных по авторской методологии) с помощью моделирующей подсистемы SILOS пакета XAСT / С.К. Горбунов, Е.Л. Денисенко, А.И. Зайончковский, В.И. Сигалов // Микропроцессорные системы и персональные ЭВМ. — Киев: Ин-т кибернетики им. В.М. Глушкова АН Украины, 1993. — С. 47-50.
18. Денисенко Е.Л., Зайончковский А.И. Основные этапы и принципы построения вычислительных систем на основе микропроцессорных средств // Техн. средства мини- и микроЭВМ. — Киев: Ин-т кибернетики им. В.М. Глушкова АН УССР, 1979 . — С. 3-12.
19 . А. с. 943727 СССР. Микропрограммное устройство управления процессора / А.В.Палагин, Е.Л.Денисенко, А.Ф.Дряпак, А.Ф.Кургаев, А.А.Прядилова, В.Я.Кузнецов. — Опубл. 15.07.82, Бюл. № 26. — 7 с.

ОПУБЛІКОВАНІ ПРАЦІ, ЯКІ ДОДАТКОВО ВІДОБРАЖАЮТЬ
РЕЗУЛЬТАТИ ДИСЕРТАЦІЇ:
20. Справочник по цифровой вычислительной технике (Процессоры и память) / Б.Н. Малиновский, Е.Л. Денисенко, Е.И.Брюхович и др.— Киев: Тэхника, 1979.— 511 с.
21. Справочник по цифровой вычислительной технике (Электронные вычислительные машины и системы) / Б.Н. Малиновский, В.Я. Александров, Е.Л. Денисенко и др. — Киев: Тэхника, 1980. — 319 с.
22. Справочник по цифровой вычислительной технике (Программное обеспечение) / Б.Н. Малиновский, В.В. Липаев, Е.Л. Денисенко и др.. — Киев: Тэхника, 1981. — 206 с.
23. Денисенко Е.Л., Кекелия В.И. Кодирование состояний автоматов, описываемых линейными микропрограммами, и их реализация в вычислительной среде // Тр. республ. науч.-техн. конф. по вычисл. техн. — Тбилиси: ЭЛВА, 1974. — С. 185-188.
24. Денисенко Е.Л., Полонская Н.С. Об использовании языков описания аппаратных средств для многоуровневого проектирования мультипроцессоров // Конструирование специализированной электронно–вычислительной аппаратуры. — Рязань: Изд–во РРТИ, 1984. — С.26–29.
25. Денисенко Е.Л. О соседнем кодировании состояний автоматов кодами минимальной длины, описываемых линейной микропрограммой // Проектирование и применение мини-ЭВМ. — Киев, 1977. — С. 16-19. — (Препр. / Ин-т кибернетики АН УССР; 77-73).
26. Денисенко Е.Л., Палагин А.В.. Юсифов С.И. О формализации проектирования микропроцессоров с несколькими операционными блоками. — Киев, 1985. — 18 с. — (Препр. / Ин-т кибернетики им. В.М.Глушкова АН УССР; 85-32).

Денисенко Є.Л. Розвиток теорії і розробка методології логічного синтезу НВІС на основі багаторівневих автоматних моделей. — Рукопис.
Дисертація на здобуття наукового ступеня доктора технічних наук за спеціальністю 05.13.05 — елементи та пристрої обчислювальної техніки та систем керування. Інститут кібернетики ім. В.М.Глушкова НАН України, Київ, 1999.

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

Денисенко Е.Л. Развитие теории и разработка методологии логического синтеза СБИС на основе многоуровневых автоматных моделей. — Рукопись.
Диссертация на соискание ученой степени доктора технических наук по специальности 05.13.05 — элементы и устройства вычислительной техники и систем управления. — Институт кибернетики им. В.М.Глушкова НАН Украины, Киев, 1999.

В диссертационной работе представлена методология логического синтеза СБИС как открытая система взаимосвязанных принципов, методик, методов, алгоритмов, управляемых математическими “механизмами” или экспертными рекомендациями автора. Методология позволяет получать в рамках всех логических ограничений (на примере ПЛИС типа LCA) гарантированно достоверную логическую схему, адекватную исходным данным, обеспечивающую максимальное быстродействие (минимум каскадов) при близких к минимальным затратах логических примитивов и предопределяющую положительное решение задач топологии.
Ключевые слова: многоуровневая автоматная модель, асинхронный и синхронный автоматы, асинхронная схема, логическая схема, иерархический синтез.

Denisenko E.L. Development of theory and methodology of VLSI logical synthesis on the basis of multilevel automata models. — Manuscript.
Thesis for a doctor’s degree by speciality 05.13.05 — elements and devices of computer facilities and control systems. — The Institute of Cybernetics of National Academy of Science of Ukraine, Kyiv, 1999.
The thesis deals with the methodology of VLSI logic design as an open system of interrelated principles, methods and algorithms controlled by mathematical “mechanisms” or author’s recommendations. This methodology enables obtaining, within the framework of all logical constraints, (using the example of an LCA-type PLIC) a guaranteed reliable logical circuit adequate to initial data which provides the maximum speed with the minimum expenditure of logical primitives and a predetermining positive solution of topology problems.
Key words: multilevel automaton model, asynchronous and synchronous automata, asynchronous circuit, logical scheme, hirerarchical synthesis.

Нашли опечатку? Выделите и нажмите CTRL+Enter

Похожие документы
Обсуждение

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

avatar
  Подписаться  
Уведомление о
Заказать реферат!
UkrReferat.com. Всі права захищені. 2000-2019