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

Означення 3. Назвемо внутрішню змінну, яка приймає одне і те ж значення в наборах і протилежне -- в наборах , розв'язуючою щодо згаданих зв'язаних переходів < a_i , a_j > і <a_k , a_l >.

В дисертації доводиться необхідність і достатність наступної теореми:

Теорема 2. Для виконання умови теореми (1) необхідно і достатньо, щоб в наборах і існувала, принаймні, одна розв'язуюча змінна щодо цих наборів.

Означення 4. Процедурою розв'язування пари переходів (<a_i , a_j >, < a_{k ,} a_l >), зв'язаної (означення 2) стосовно умови U, назвемо введення змінної, що розв'язує, в набори і станів a_i, a_j, a_k, a_l довільного асинхронного автомата.

Ця процедура покладена в основу алгоритму і методу, що сформульовані в реферуємій роботі, а також для зменшення кількості змінних в результуючій таблиці кодування. Метод дозволяє отримати задовільні результати, якщо число внутрішніх змінних, отриманих внаслідок його “роботи” такі, що m_об s - 1 + u, де u -- число вхідних каналів автомата. Якщо ця нерівність не задовольняється, то доцільно знаходження кодування із явно збитковим числом внутрішніх змінних, що визначає таке спрощення системи функцій збудження і виходів (ф.з.в.), коли дана нерівність задовольняється, як і враховуються всі вищезазначені обмеження. Відомі методи В.Г. Лазарєва - О.І. Пійль, А.Е. Янковської, В.А. Склярова, Лю, Тресі, Хартманіса не придатні для цієї мети.

Для побудови методу протиризикового кодування, що визначає в системі ф.з.в. отримання апріорно заданих значень m_об , l_об , n_разв , автор запропонував підхід і на основі його методи, які істотно використовують поняття розбиття на множині P переходів автомата на відміну від підходів вищезазначених авторів, що використали розбиття на множині станів автомата. Відомо, що кожному варіанту кодування станів автомата може бути однозначно зіставлена система двоблокових розбиттів на множині станів цього автомата. Будь-яке розбиття на множині переходів може природно розглядатися як розбиття на множині станів, якщо множина P доповнена переходами (a_i, a_i), ..., (a_l, a_l) i для будь-яких двох переходів <a_i, a_i> та <a_l, a_l> повинно існувати, принаймні, одне часткове розбиття, таке, що ці переходи належать різним блокам означеного розбиття. Для того, щоб побудувати систему S часткових розбиттів на множині P переходів асинхронного автомата, що задовольняють вищезгаданим умовам, визначається операція розкладу множини P переходів за множиною ортогональних умов, що полягає в побудові k підмножин, кожна з яких (i=1,..., k) відзначається відповідною умовою Ui. Крім того, для здійснення переходу від системи S часткових розбиттів до системи двоблокових розбиттів на множині P переходів і для можливості виконання оптимізуючих перетворень цих систем визначаються операції об'єднання сукупностей переходів (результатом виконання операції об'єднання на сукупностях s₁,..., s_k є сукупність s, що відмічена умовою U і “розщеплення” станів автомата, для яких функції переходів і виходів визначаються так, як і для стану, що розщеплюється). Після цього формулюються обмеження на систему , такі, що їй може бути зіставлена система на множині станів (і відповідне протиризикове кодування), за якого у виразах системи булевих ф.з.в. задовольняються обмеження m_об , l_об , n_разв і при цьому досягається мінімальне _сум. Часто виявляється, що вигляд д.н.ф. ф.з.в., вибраної з (4), (6) як стандартної, відрізняється від того, що безпосередньо реалізується в базисах наявного набору бібліотечних примітивів (наприклад, дужковий запис булевих виразів неекономічно реалізується в базисах примітивів бібліотек ПЛІС типу ХС2000 і ХС3000). Так, умову U_ij будь-якого переходу < a_i , a_j > можна записати у вигляді U_ij =  U_i , де U_i -- диз'юнктивний член (кон'юнкція) довжини u. Тоді будь-який диз'юнктивний член D_ij (10), що зіставляється у виразах ф.з.в. переходу < a_i , a_j >, можна уявити у вигляді

(7)

Звідси д.н.ф. функцій збудження кожному переходу < a_j, a_j >, умові U_i , функції збудження s_k (або r_k) ставиться у відповідність терм D_ij внутрішніх змінних. Внутрішній змінній d_k відповідає двоблокове розбиття  = C; D, причому блок C зазначений “0” (“1)”, а блок D -- “1” (“0)”. Позначимо R (U_i , a_i , a_j ) множину переходів, зв'язаних (5) з a_i , a_j щодо U_i . В системі двоблокових розбиттів нехай існує розбиття  = E; F, таке, що a_i , a_j E. Позначимо символом L множину всіх переходів з R (U_i , a_i , a_j ), таких, що їх перші проекції (пр₁) містяться в E. Тоді можна довести що:

Твердження 1. Терм U_ij складається з літер d₁,..., d_t , якщо містить розбиття _?,...,_t, такі, що a_i , a_j належать одному з блоків добутку розбиттів _?  ,..., _t, наприклад E, а друга проекція від L належить F. Такі твердження сформульовані для різних значень t. Стосовно величини t_н -- нижньої оцінки t в дисертації доведене твердження:

Теорема 3. Існує протиризикове кодування станів довільного асинхронного автомата, таке, що будь-який терм T_ij д.н.ф. ф.з.в. складається з однієї внутрішньої змінної. Нарешті, можна довести, що

Твердження 2. f термів D_ij відповідає множині G, що належить P переходів в д.н.ф. ф.з.в. s_k або r_k , якщо в системі розбиттів _?,...,_f , такі, що E є блоком добутку _? ,..., _f, такого, що g належить E, перша проекція від L належить E, а друга проекція від L належить D, де L належить R(u_i,<a_i , a_j>).

Сформульовані твердження для різних значень f.

На підставі цих результатів сформульований метод протиризикового кодування станів нормального асинхронного автомата, який наперед визначає в системах булевих функцій збудження і виходи величини m_об, l_об , і внаслідок цього -- n_разв. Однак вимірність задач, що вирішуються цим засобом інколи залишається великою. Для зменшення вимірності цих задач доцільно або використати авторський засіб декомпозиції початкового автомата, або у вхідному структурному алфавіті автомата використати синхронізуючі (тактуючі) сигнали. В останньому випадку автомат залишається асинхронним (без перетворення в синхронний), але істотно спрощується задача перетину множини P по множині ортогональних умов. В таких автоматах умова будь-якого переходу істотно залежить від змінної, відповідної тактуючому сигналу. Тоді при побудові системи двоблокових розбиттів на множині P переходів з заданими обмеженнями застосування операції розкладу (перетину) множини P по множині ортогональних умов зводиться до розкладу по множині ортогональних змінних, відповідних сигналам різних тактуючих серій.

Дана побудова проміжної специфікації -- системи , що задовольнить побудові часткових розбиттів множини P відповідно синхронізуючим змінним. Формульні вирази систем двоблокових розбиттів множини P тактуємих автоматів при значеннях параметрів t = 1 такі:

Для t = 2, 3 вирази для систем S аналогічні. Всі вони містять в собі оціночну інформацію.

Обмеження на систему двоблокових розбиттів (на множині P переходів автомата), за яких число термів д.н.ф. s_k і r_k може бути зменшено за рахунок склеювання по внутрішніх змінних, якщо умова f  l_об не досяжна, зведені до таких:

Твердження 3. Терми T_ij і T_kl функції s_k (чи r_k) відрізняються значенням тільки однієї змінної, якщо відповідне їй розбиття  = E; F, таке, що a_i, a_j  E і a_k, a_l F -- єдине.

Твердження 4. D_ij і D_kl (U_ij=U_kl) д.н.ф. s_k (r_k) склеюються, якщо серед розбиттів _?,...,_p в системі є єдине розбиття  = V; W, таке, що a_i, a_j  V і a_k, a_l W, а будь-яке інше  = H; Z, таке, що або a_i, a_j , a_k, a_l H, або Z.

Вищенаведені результати є теоретичною основою методу і алгоритмів кодування станів асинхронних тактуємих автоматів з урахуванням числа входів бібліотечних примітивів НВІС типу AND (NAND) (в дисертації -- метод 4.3) і метод алгоритмів збиткового кодування, що враховують число входів примітивів типу OR (NOR, XOR) (у дисертації -- метод 4.4).

Ці результати стали також основою для розробки спрощеного (порівняно з канонічним методом В.М. Глушкова) методу ієрархічного структурного синтезу асинхронних тактуємих автоматів, що враховує (практично) всі наявні нині логічні обмеження НВІС. Цей метод (у дисертації -- метод 4.5) полягає в формульному визначенні д.н.ф. ф.з.в., вільних від логічного ризику за всіма аргументами безпосередньо по вхідному завданню (коректному алгоритму функціонування) автомата і отриманій системі двоблокових розбиттів на множині P переходів з наступним тривіальним переходом до системи на множині станів, що задовольнять заданим обмеженням. Метод зводиться до визначення за формулою диз'юнктивного члена U_ij T_ij відповідного переходу <a_i, a_j> автомата A в д.н.ф. вигляду (8), (11) (власне, до визначення за формулою елементарного терму T_ij , тому що U_ij звичайно задається в алгоритмі), якщо U_ij задається елементарним термом вхідних змінних. Наведені формули, що дозволять визначити такі елементарні терми за будь-якого значення t від 1 до 3, що обмежують їхню довжину. Кількість таких елементарних термів зменшується за рахунок зумовлених склеювань. У рамках методу запропонований спосіб виключення ризику вихідного сигналу, якщо його тривалість перевищує тривалість тактованого шляхом додання до результуючої системи двоблокових розбиттів на множині станів автомата одного додаткового (у випадку необхідності, коли ризик не виключений випадково внаслідок побудови системі ) розбиття

де Zi -- множина станів, на яких y_i =1 (0), а \Z_i -- множина всіх інших станів множини , на яких y_i = 0 (1) або його значення невизначено і може бути довизначено довільно. Якщо обмеження на m_об, l_об і n_разв задовольняються, то сумарне значення _сум сумарної затримки сигналу в схемі буде мінімальним, а швидкодія схеми -- максимальною.

У багаторівневих системах управління сучасних НВІС і обчислювальних систем існують і продовжують розроблятися блоки, для яких вимоги досягнення максимальної швидкодії істотно послаблені, а вхідні алгоритми надто великі (понад ста міток). Такими є блоки мікропрограмного управління, основані на моделі синхронного (по Хартманісу, Мілеру, Ангеру) автомата.

Виконане дослідження (розділ V) сучасного стану питання і аналізу управляючих систем в НВІС-реалізації від популярних моделей ПЕОМ фірм Intel і Motorola до останніх розробок конвейєрник архітектур НВІС Power 603 і Pentium 100 показують, що при досягненні частот понад 100 Мгц, незважаючи на тенденцію збільшення частки асинхронних приладів і схем, частка мікропрограмних приладів (блоків) управління (МПУ) залишається значною. Удосконалення структур МПУ від структури Уілкса - Стрінжера до сучасних, незважаючи на успішне розв'язання багатьох задач, дві з них як центральні не були розв'язані. По-перше, це задача кодування полів звичайно в межах двох критеріїв: ефективної взаємодії і простоти реалізації в вибраному логічному базисі з відповідними обмеженнями. По-друге, це задача формування адресації мікрокоманд або задача проектування систем адресації. Для теоретичного обгрунтування розв'язання першої задачі сформульовані такі поняття: системи W = = {w₁,..., w_t} мікрокоманд МПУ; системи мікрооперацій (МО); маски N, набору масок П, вектора масок . Використані означення Граселі - Монтанарі сумісності мікрооперацій, класу С сумісності, максимального класу сумісності.

Означення 5. Результатом маскування МК w_i (і =1,..., t) вектором класів сумісності при заданому наборі класів сумісності називається МК , що задовольняє рівності

(8)

Введемо також множину всіх підмножин МК w_i (i =1,..., t). На основі цього сформульовані наступні дві задачі маскування:

перша -- знайти мінімальний набір класів сумісності , у якого для будь-яких w і w_i w існує вектор класів сумісності , що задовольняє виразу

; (9)

друга -- знайти мінімальний набір класів сумісності , що задовольнить такій вимозі: для будь-якого w існує МК w_i і вектор класів сумісності , для яких

(10)

У процесі розв'язання задач в дисертації першим проміжним результатом сформульований алгоритм, що зводить задачу побудови мінімального набору класів сумісності до частинного вигляду задачі цілочисельного лінійного програмування -- до задачі покриття. Виконаний аналіз визнаних методів розв'язання задач покриття і вибраний метод А.Д. Закревського, що використовує поняття дерева пошуку. Цей метод спрощений шляхом перетворення даних вхідної задачі, де множину МО уявлено графом :

1. Якщо деяка вершина i з'єднана з множиною I вершин, а вершина j -- з множиною J вершин, причому (i I) & (i I) & ((I \ j) (J \ i)), то вершина j може бути усунена з графа з наступною корекцією розв'язання цієї задачі.

2. Якщо граф не є зв'язним, то задача може бути розбита на декілька незалежних підзадач.

3. Розв'язання задачі може бути знайдено серед максимальних класів сумісності (по Закревському). Зауваження 1, 2 використовуються для спрощення графа вхідної задачі, зауваження 3 -- для спрощення системи нерівностей для власне задачі покриття. На підставі викладеного сформульований алгоритм розв'язання вхідної задачі, а пошук мінімального покриття виробляється у відповідності з блок-схемою алгоритму, наведеного в реферуємій роботі (в дисертації рис. 5.5).

У рамках методики проектування мікропрограмних ПУ розв'язана також задача проектування системи адресації мікрокоманд (САМ), яка формулюється так.

Нехай задані мікропрограма M, множина її вхідних наборів x = {x₁,..., x_t}, вибраний сторінковий засіб адресації і необхідно визначити множину C = {C₁,..., C_l} класів вхідних наборів, розмір сторінки мікропрограмної пам'яті (розрядність n₁ поля адреси МК), мінімізуючий обсяг цієї пам'яті

, (11)

де N₁ -- кількість сторінок в мікропрограмній пам'яті.

Нехай максимальна потужність вхідного набору x_i серед елементів множини X

(12)

Тоді справедливі наступні обмеження:

; (13)

. (14)

Друга задача проектування САМ -- визначення оптимальних розмірів сторінки.

Нехай задана мікропрограма M={w₁,..., w_N } і евристично вибраний розмір сторінки . Вибравши підмножину , що міститься на одній сторінці, однозначно визначається множина МК переадресацій на інші сторінки така, що потужність об'єднання. Тут істотно наступне обмеження, визначальна вимога до максимальних класів сумісності: . Будується матриця елементів B_ij , рядки якої позначені w_i (i = 1,..., N), де N -- число мікрокоманд в M з урахуванням МК переадресації, стовпці C_j ( j = 1,..., n) всіх можливих варіантів розміщення мікропрограми M в сторінках заданого розміру. Сформулювавши систему обмежень і функцію мети аналогічно попередній задачі, зводимо задачу розбиття мікропрограми за критерієм мінімуму числа сторінок до задачі покриття.

Використання методу “упаковки” для розв'язання даної задачі вимагає визначення максимальних класів сумісності на множині вершин графа G (M). Визначається верхня межа для цих класів шляхом розрізування графа G (M) з урахуванням подальшої властивості розбиття (декомпозиції) мікропрограми. Якщо мікрокоманда w_i (i = 1,..., N), де N -- число міток у мікропрограмі M, належить фрагменту M_j ( j = 1,..., k) від M, то цьому ж фрагменту належать усі мікрокоманди -- її приймальники і в відображенні на G (M) є околом вершини v_i фрагменту G (m_j) графа G (M). Тоді задача, що розв'язується, полягає в розрізуванні графа G (M) на фрагменти G (M_j) при обмеженнях і мінімізації k. Як в задачах розбиття множини мікрооперацій або множини вхідних наборів (сигналів) на класи, дана задача зводиться до побудови максимальних класів сумісності (алгоритми якого в дисертації наведені в розділі 5.4), вилучення не максимальних шляхом попарного порівняння і розв'язанню відповідної задачі покриття.

Всі перераховані вище теоретичні результати, алгоритми і методи складають методику логічного проектування мікропрограмних пристроїв управління в логічних базисах ПЗП або ПЛМ.

У шостому підсумковому розділі завершується досягнення поставленої мети -- побудова методології багаторівневого логічного синтезу НВІС. Показана побудова багаторівневої автоматної моделі НВІС як основоположного стрижня методології (розділи 6.1, 6.2), її верхніх частин -- мережі дискретних (магазинних) перетворювачів, що деталізується на стику системного і логічного етапів в мережу мереж операційних (запропонованих), мереж секвенціальних, паралельних і звичайних управляючих автоматів. Паралельно моделі в процесі логічного проектування вишикується багаторівнева ієрархія алгоритмічних і структурних описів до рівня міжрегістрових пересилок або мікропрограм. Проведений аналіз і запропоновані рекомендації по вибору того чи іншого методу синтезу, який іде вниз від рівня мікропрограм. Далі описана (в дисертації -- розділ 6.3) конкретна версія методології як логічної надбудови синтезу логічних схем в середовищі матричних НВІС з архітектурою LCA типу XC2000. Визначені всі логічні обмеження цього середовища: логічний ризик (при асинхронній реалізації), число входів і коефіцієнт розгалуження, тип елемента пам'яті, значення величини затримок у різних макрочарунках і обмеження на кількість бітових трас міжз'єднань. На основі цього розроблені стратегія експертного вибору кодування станів (з використанням авторських результатів -- глава 4) і власне сама тактика кодування в рамках обмежень. У рамках методології адаптований до заданих обмежень запропонований раніше спрощений метод структурного синтезу, що дозволить отримати оптимальну реалізацію внутрішніх змінних і систем булевих функцій збудження і виходів примітивами бібліотеки Future Net. Запропонований простий (порівняно із асимптотичними) метод оцінки ефективності проектних специфікацій, які одержані внаслідок синтезу, що дозволить визначити число умовних еквівалентних вентилів, які витрачаються на реалізацію послідовнісної схеми. Для макрочарунок вводу-виводу

, (15)

де , -- потужності вхідного і вихідного алфавітів, k_вв -- постійний коефіцієнт.

Суттєвість оцінки грунтується на суті авторського методу структурного синтезу: кожному переходу <a_i, a_j> автомата відповідає диз'юнктивний член (кон'юнкція) D_ij. Звідси

, (16)

де , -- кількість елементів в часткових розбиттях на множині переходів, K_CLB -- коефіцієнт, визначальна кількість еквівалентних вентилів в логічній макрочарунці (CLB), N -- число станів автомата. Наведені аналогічні вирази для елементів пам'яті різноманітних типів і вираження , що дозволить визначити кількість еквівалентних вентилів на реалізацію функції виходу. Остаточний вираз для трьох різноманітних засобів кодування станів, коли p=1, p=2 і p=] log₂N [ такий:

, (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, кількість U_ij 128.

Основні результати та висновки

Головний підсумковий результат даної роботи -- розв'язання значної прикладної проблеми -- створення ефективної прикладної теорії, обгрунтованої методології і комплексу апробованих методик і методів ієрархічного логічного синтезу послідовнісних схем НВІС, що задовольняють усі логічні обмеження [1,11,12].

Суть методології полягає в п'яти її складових здійснених розробок:

1. Теоретичною базою розробленої методології логічного синтезу НВІС є такі результати, отримані як розвиток прикладної теорії автоматів:

1.1 Побудовані багаторівнева деревоподібна автоматна модель НВІС і модель “ліс” (як сукупність багаторівневых моделей) обчислювальних систем з різнорідних НВІС для системного аналізу і синтезу в задачах логічного проектування НВІС високої складності [1,12].

1.2 Запропоновані автоматні моделі деяких фрагментів архітектури і структури НВІС: мережа магазинних перетворювачів, мережі секвенціальних та паралельних автоматів, що дозволяють формалізувати задачі системного етапу і здійснити формальний перехід від системних моделей до логічних [1,10].

1.3 Вперше сформульована і доведена сукупність теорем та пропозицій, на засаді яких вилучається логічний ризик у довільних асинхронних автоматах і логічних схемах, які засновані на механізмі ортогонального кодування з урахуванням “достатніх” умов тривалості вихідних сигналів [1,2,16].

1.4 Запропоновано операції розкладання та розрізу множини переходів асинхронного автомата по множині ортогональних умов. На цьому вперше сформульовані пропозиції і доведена їх достатність, на яких в процесі ієрархічного синтезу булевих функцій збудження і виходів точно задовольняються логічні обмеження на кількість входів примітивів типу AND і OR і коефіцієнт розгалуження виходу [1,2,13,16,25].

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

Методика містить в собі математичні “механізми” адаптації до різноманітних значень логічних обмежень і дозволяє одержувати послідовнісні схеми максимально досяжної швидкодії, що задаються кількістю “обладнання” за цих обмежень.

3. Методика ієрархічного проектування систем багаторівневого мікропрограмного управління НВІС і обчислювальних систем в базисах ПЛМ і ПЗП [1,4-6,18,19].

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

4. Система методів логічного синтезу, що є складовою методології, утворена з таких:

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].

5. Дві версії алголо - і 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).

АНОТАЦІЇ

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

Дисертація на здобуття наукового ступеня доктора технічних наук за спеціальністю 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.

Размещено на Allbest.ru