Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
32
Національний університет “Львівська політехніка”
Мельник Роман Андрійович
УДК 621.382
Методи та алгоритми ієрархічного проектування
площинної та просторової топології НВІС
.13.12 –системи автоматизації
проектувальних робіт
Автореферат
дисертації на здобуття наукового ступеня
доктора технічних наук
Львів-2001
Дисертацією є рукопис.
Робота виконана на кафедрі програмного забезпечення Національного університету “Львівська політехніка”.
Науковий консультант:
доктор технічних наук, професор
Базилевич Роман Петрович,
Національний університет “Львівська політехніка”,
завідувач кафедри програмного забезпечення
Офіційні опоненти:
член-кореспондент НАН України, доктор технічних наук, професор
Стоян Юрій Григорович, Інститут проблем машинобудування
ім. А. М. Підгорного, завідувач відділу математичного моделювання і
оптимального проектування, м. Харків;
доктор технічних наук, професор Вінцюк Тарас Климович,
Міжнародний науково-навчальний центр інформаційних технологій
та систем НАН України та Міністерства освіти і науки України,
завідувач відділу, м. Київ;
доктор технічних наук, професор кафедри автоматизації та
комп’ютерних технологій Овсяк Володимир Казимирович,
Українська академія друкарства, м. Львів.
Провідна установа: Харківський державний технічний університет
радіоелектроніки, кафедра автоматизації проектування
обчислювальної техніки, Міністерство освіти і науки
України, м. Харків.
Захист відбудеться “26“червня 2001 р. о 12 годині на засіданні спеціалізованої вченої ради Д 35.052.05 у Національному університеті “Львівська політехніка”за адресою: 79013, Львів-13, вул. С. Бандери, 12 ).
З дисертацією можна ознайомитися у бібліотеці Національного університету “Львівська політехніка”(м. Львів, вул. Професорська, 1).
Автореферат розісланий “25“травня 2001 р.
Вчений секретар
спеціалізованої вченої ради Ткаченко С.П.
Актуальність проблеми. Проектування надвеликих інтегральних схем є актуальним з огляду на декілька причин. НВІС є елементною основою сучасних комп’ютерних систем і мікропроцесорних пристроїв загального і спеціального призначення. Теоретичні і технологічні знання в цій галузі впливають на інформативне забезпечення практично всіх галузей економіки, зокрема, на соціальну сферу, освіту, медицину тощо.
Результати технічного проектування НВІС суттєво впливають на працездатність схем, відсоток випуску придатних пристроїв та надійність їх подальшої експлуатації. Тому покращання параметрів методів проектування топології НВІС в напрямку зменшення кількості фрагментів розбиття, довжини провідників на чіпі, часу максимальної затримки сигналу в межах декількох відсотків порівняно до наявних методів суттєво зменшує вартість виробництва в абсолютних цінах і покращує характеристики надійності схем.
Задачі проектування топології НВІС є трудно вирішуваними з огляду на те, що всі основні формулювання задач розбиття, компонування, розміщення та трасування належать до класів задач неполіноміальної складності; розмірність задач є значною і це не дозволяє використовувати методологій переборів у повному просторі параметрів; перш ніж бути запрограмованими в промисловій системі автоматизованого проектування, методи та алгоритми підлягають грунтовному аналізу їх складності та порівняльному аналізу ефективності.
Українські вчені від часу створення в Україні комп’ютерів знаходяться серед світових лідерів розроблення теорій, методологій, методів проектування обчислювальних систем. В Інституті кібернетики НАН України під керівництвом академіка В. М. Глушкова були закладені теоретичні основи методології проектування схемного та програмного забезпечення комп’ютерів, зокрема, програмування за “безпаперовою”технологією. В основі методології лежать методи блочного, абстрактного та структурного синтезу для проектування обчислювальних машин. Потім в Україні під керівництвом українських вчених Бублика Б.М., Вінцюка Т.К., Михалевича В.С., Павлова О.А., Пшеничного Б.Н., Рвачова І.В., Сергієнка І.В., Стояна Ю.Г. утворились наукові школи, в яких розробляються фундаментальні теоретичні та прикладні методології розв’язування оптимізаційних комбінаторних задач, синтезу оптимальних систем. Ці методології використовуються для розв’язування практичних задач оптимального розміщення, розкрою матеріалів, пакування, призначення ресурсів, проектування технічного і програмного забезпечення обчислювальної техніки. Організаторами шкіл для вирішення проблем проектування НВІС і, зокрема, їх топології є українські вчені Базилевич Р.П., Петренко А.І. Ними розроблені ефективні обчислювальні та евристичні методи схемотехнічного та технічного проектування радіоелектронної апаратури, в тому числі компоненти інтегральних схем.
НВІС належать до категорії об’єктів проектування, складність і розмірність яких постійно зростає. Це означає, що до методів проектування топології НВІС, а саме методів розбиття, розміщення і трасування постійно зростають вимоги щодо їх ефективності (швидкодії, якості результатів тощо). Вказані задачі проектування належать до класу NP-повних задач і переважна більшість методик розв’язання означених класів задач є евристичними. Розвиток обчислювальної техніки створює можливості продовження досліджень в цій предметній галузі для пошуку глобально–оптимальних розв’язків задач розбиття, розміщення та трасування НВІС практичної вимірності.
Отже, розроблення методів, моделей та алгоритмів ієрархічного проектування топології НВІС має теоретичне і практичне значення, потребує подальшого розвитку, що і визначило тему цієї дисертаційної роботи.
Зв’язок з науковими програмами, планами, темами. Дисертаційна робота виконана у руслі наукових досліджень кафедри програмного забезпечення Національного університету “Львівська політехніка”, які проводилися дисертантом як відповідальним виконавцем за період 1985-2000 рр. під час держбюджетних та госпдоговірних науково-дослідних робіт. Бюджетні теми виконувались в межах пріоритетних наукових напрямків Міністерства освіти і науки України: “Теоретичне обгрунтування і розроблення систем автоматизованого проектування ВІС, НВІС та ДП”та “Методи проектування комп’ютерних систем і технологій”, а саме: “Математичне та програмне забезпечення інтелектуальних систем автоматизованого проектування топології великих інтегральних схем”(1991-1993 рр., ДР № 0910044924); “Математичне та програмне забезпечення інтелектуальних систем синтезу топології великих інтегральних схем” (1991-1995 рр., ДР № 0194U029614); “Методи та алгоритми розв'язування оптимізаційних комбінаторних задач великої розмірності (на прикладі задач електроніки)”(1991-1995 рр., ДР № 0193U040390); “Високопродуктивні програмні та алгоритмічні засоби для проектування великих та надвеликих інтегральних схем”(1998-1999 рр., ДР № 0100U000503); “Методи та алгоритми розв’язування трудно вирішуваних оптимізаційних комбінаторних задач великої розмірності”(2000 р., ДР № 0198U002383).
У межах державної цільової програми “Створення і розвиток навчально-дослідницьких САПР та їх підсистем у ВНЗ”виконувались договірні теми: “Розробка алгоритмічного та програмного забезпечення для проектування топології мікрозборок з одношаровою комутацією”(1986, ДР № 01840079623); “Розробка алгоритмічного та програмного забезпечення підсистеми розбиття схеми на підсхеми, що реалізуються ТЕЗами”(1986, ДР № 01840022456); “Розробка на основі декомпозиційних методів математичного та програмного забезпечення для проектування матричних ВІС”(1987, ДР № 01870052807); “Декомпозиційні методи автоматизації проектування”(1988, ДР № 01880033345); “Розробка математичного забезпечення для ієрархічного проектування НВІС”( 1990, ДР № 01880079668); “Декомпозиційне проектування ВІС”(1991, ДР № 01890062609); “Розроблення та дослідження математичних методів та алгоритмів для автоматизованого проектування топології великих інтегральних схем і конструкцій радіоелектронної апаратури”(1991-1996 рр.).
Мета і завдання дослідження. Метою роботи є теоретичне обгрунтування і практичне розроблення методів, моделей, алгоритмів та підсистеми ієрархічного проектування площинної та просторової топології НВІС, що основані на ієрархічній методології оптимального згортання схемних елементів та їх компонентів, а також на ієрархічній методології розв’язування складних оптимізаційних задач великих розмірностей, що виникають на етапах проектування топології НВІС. Для досягнення цієї мети сформульовані такі основні наукові завдання:
Методи дослідження. У дисертаційній роботі використані евристичні методи розв’язання задач дискретної оптимізації, прямі й рекурсивні методи побудови конфігурацій стратегій пошуку екстремумів функцій від координат позицій елементів, метод оптимального згортання схем, ітераційні та конструктивні методи, методи оцінки складності алгоритмів, методи побудови складних програмних систем, методи формування і оптимального опрацювання складних структур даних. Як засоби дослідження складних систем у роботі використані декомпозиція, агрегація та макромоделювання для реалізації принципів ієрархічного багаторівневого проектування.
Новизна наукових результатів. Виконання теоретичних та експериментальних досліджень методів, алгоритмів та моделей дозволило розв’язати науково-прикладну проблему: розроблено ієрархічну методологію проектування топології НВІС, яка базується на оптимальному згортанні схем і містить методи розбиття та пакування, розміщення та трасування. Отримано такі наукові результати:
Обгрунтованість та вірогідність наукових результатів визначається використанням загальновизнаних підходів декомпозиції, агрегації та макромоделювання до проектування багатовимірних об’єктів зі складною ієрархічною структурою та великою кількістю параметрів. Достовірність наукових положень і результатів забезпечується строгістю, коректністю постановок задач та використання математичного апарату, доведення теоретичних міркувань до програмної реалізації.
Ефективність запропонованої методології, її алгоритмічної та програмної реалізації підтверджується аналізом обчислювальної складності алгоритмів та моделей в межах однотипних задач і порівнянням отриманих результатів з аналогічними результатами вітчизняних та зарубіжних дослідників.
Наукове значення результатів роботи полягає в тому, що на єдиній методологічній основі –методі оптимального згортання схем - розроблено вперше і узагальнюються відомі методи компонування з використанням нечіткого згортання, пакування і розміщення з використанням накладання макромоделей. Для збільшення швидкодії методів та вірогідності знаходження оптимальних розв’язків розроблені неперервні лінійчаті та просторові моделі для пошуку екстремумів дискретних функцій від координат позицій елементів, моделі розмитих з’єднань та ієрархічна структура їх реалізації, графові моделі для відображення топології каналу і пакування відрізків у каналі обходом дерева можливих розв’язків.
Практичне значення отриманих результатів. Автором розроблена підсистема проектування топології НВІС, яка складається з пакетів програм та модулів, які дозволяють розв’язувати задачі розбиття, пакування, компонування, розміщення одно- та різногабаритних елементів на площині та у просторі з врахуванням існуючих технологічних обмежень, трасування у просторових моделях з’єднань. Загальний обсяг програм, які реалізують запропонований методологічний та алгоритмічний апарат, становить понад 50000 операторів мови програмування високого рівня. Вони дозволяють зменшити кількість типорозмірів, загальну довжину з’єднань, завантаженість комутаційного простору НВІС і, як наслідок, підвищити їх швидкодію та надійність, зменшити кошти виробництва.
Реалізація та впровадження. Програмні засоби, розроблені під час наукових досліджень були впроваджені на підприємствах Мінська, Москви та Санкт-Петербурга. Нові версії підсистеми проектування проходять експериментальне випробовування для виробничих потреб на львівських підприємствах електронного спрямування (ВАТ “Мікроприлад”, ВО “Електрон”, ВО “Полярон”). Вони рекомендуються для впровадження в проектні організації, які розробляють інтегральні схеми.
Результати роботи впроваджені в навчальний процес при підготовці бакалаврів, спеціалістів та магістрів спеціальності “Програмне забезпечення автоматизованих систем”. Наукові положення і висновки дисертації лягли в основу лекційних курсів “Комбінаторні моделі в обчислювальних процесах”, “Системне програмне забезпечення”, “Структури та організація даних”, які читають у Національному університеті “Львівська політехніка”. Розроблено цикли лабораторних робіт і опубліковано методичні вказівки.
Апробація результатів дисертації. Основні результати дисертаційної роботи доповідались на понад 30 міжнародних та національних конференціях, а саме: Всесоюз. конф. "Розробка і впровадження в народне господарство ЄС ЕОМ", Москва, 1986, 1987; Всесоюз. конф. “Інтегровані системи автоматизованого проектування в гнучких виробничих системах”, Воронеж, 1988; Міжнародній конф. “САПР СОТ-89: Автоматизація технічного проектування обчислювальної техніки”, Москва, 1989; Всесоюз. конф. “Теорія і практика побудови інтелектуальних інтегрованих САПР РЕА і ВІС", Москва, 1986, 1987, 1988, 1989; Всесоюз. конф. “Автоматизація проектування РЕА та ЕОА", Пенза, 1987, 1988, 1989, 1990; Всесоюз. конф. “Автоматизація проектування РЕА”, Каунас, Литва, 1987, 1988, 1989, 1990, 1991, 1992; Міжнародній конф. “Комп’ютери -89”, Чехословаччина, Братислава, 1989; Міжнародному колоквіумі, НДР, ФРН, Ільменау, 1987, 1997, 1999; Міжнародній конф. “Укрсофт”, м. Львів, 1994, 1995; Міжнародній конф. “Сучасні проблеми засобів телекомунікацій, комп’ютерної інженерії та підготовки спеціалістів”, Львів-Славсько, 1998; сесіях Наукового товариства ім. Шевченка, Львів, 1998, 1999, 2000; Міжнародній конф. ”Досвід розробки та застосування САПР в мікроелектроніці”, Львів-Славсько, 1999; Міжнародній конф. “Сучасні проблеми засобів телекомунікацій, комп’ютерної інженерії та підготовки спеціалістів”, Львів-Славсько, 2000; Міжнародній конф. “Проблеми комп’ютерних наук в Україні”, Львів-Славсько, 2000.
Публікації. За темою дисертації опубліковано 65 наукових праць (монографія, 23 статті у фахових виданнях, 7 депонованих статей, 32 тези і доповіді з праць конференцій, 2 методичні вказівки) та зареєстровано 10 науково-технічних звітів, що виконані за темою дисертації за участю автора.
Особистий внесок здобувача. В авторефераті представлено 38 публікацій (14 самостійних). У працях, що написані у співавторстві, дисертанту належать: [2] - метод розміщення з врахування обмежень; [3] - метод розміщення різногабаритних елементів компонуванням; [4] - розміщення з накладанням макромоделей та розміщення їх на лінійках; [5,23,24,35] - методи макротрасування та призначення, моделі топологічного поля, алгоритми, архітектура підсистеми; [13,15,36.37] - метод і стратегії розміщення, структура пакетів, програмне забезпечення; [22] - алгоритми компонування; [19] - метод побудови мінімальних зв’язувальних дерев, програмний пакет; [25-28] - архітектура підсистеми розбиття та розміщення; [29-33] –метод макротрасування з декомпозицією, архітектура, моделі підсистеми трасування ВІС.
Структура дисертації. Дисертація містить вступ, шість розділів, висновки з роботи, список літератури, додатки. Повний обсяг дисертації 306 сторінок, з яких 266 сторінок машинописного тексту, список використаних джерел з 194 назв на 17 сторінках. У тексті є 237 рисунків та 12 таблиць.
ОСНОВНИЙ Зміст роботи
У вступі обгрунтовано актуальність тематики дисертаційних досліджень, коротко описано структуру і зміст роботи, висвітлено зміст положень, які становлять наукову новизну та її практичну цінність.
Перший розділ присвячено огляду літературних джерел з галузі наукових досліджень методів розбиття, пакування, розміщення та трасування інтегральних схем та принципам ієрархічної методології проектування топології НВІС.
У другому розділі сформульовано мету і завдання декомпозиції схеми і розроблені методи та алгоритми для її розв’язування. Під час розбиття графа схеми необхідно отримати таке розбиття Si*={Ai1*,...,Ain*}, для якого показник якості розбиття набуває оптимального значення
F(Si*) = opt F(Sк ) (1)
Sк S(X).
Тут Sк - допустиме розбиття з класу S(X). Кожний елемент Aim=(Xim,Vim,R) складається з множини вершин Xim Х і множини ребер Vim V . Під час розбиття графa H = (X,V,R) на частини елементи розбиттів
Sі ={Ai1,..., Ain} повинні задовольняти умови:
(Aim Si ) [Х(Aim ) X],
(Aim Si ) [Х(Aim ) ],
(AimSi , AilSi ) [Aim Ail , Aim Ail = ],
X(Aim )= X , V(Aim)=V,(m=1,…, n ),
де - квантор загальності, , - знаки об’єднання та перетину множин. Кількість підграфів, кількість зв'язків між ними виступають як функції критерію чи обмежень у дискретних оптимізаційних задачах розбиття.
У роботі розглянуто формування специфічних задач розбиття (1), пов’язане з виконанням додаткових обмежень, які накладаються на параметри окремих підграфів та їх складових елементів, наприклад:
Ni- card Xi Ni+ , (i=1..n),
xi xj Zd [(xiAк ) (xj Aр )], кр,
xixj Zt [(xi Aк ) (xj Aк )] ,
де Zd - множина елементів, які повинні бути рознесені в різні фрагменти; Zt - множина елементів, які повинні бути об’єднані в одному фрагменті, Ni- , Ni+ - нижня і верхня допустимі границі розмірів фрагментів.
Основою методу розв’язування задачі розбиття є побудова дерева згортання (редукції) графа, де центральною є процедура оцінювання претендентів на об’єднання. Вибір типу критеріальної функції F при побудові дерева згортання суттєво впливає на вид дерева і, як наслідок, на якість розбиття. У роботі класифіковані критерії об'єднання, на основі яких побудовано узагальнений як зважену суму функцій різних порядків
f (s,t) = w f (s,t,0)+ w f (s,t,1)+ w f (s,t,2)+ w f (s,t,3)+...,
де s,t - вершини-кандидати на об’єднання, wі –вагові коефіцієнти, порядок вказує на глибину пошуку. Аргументами функції виступають параметри точкової чи розподіленої моделей фрагмента графа для відображення ребер, які виходять назовні фрагмента; ребер, що є інцидентними тільки двом вершинам фрагмента хк,( хj X і ); кількість внутрішніх ребер фрагмента тощо.
Обчислювальні затрати алгоритму Д1 для загального випадку визначаються кількістю об'єднань, яка відповідає кількості вершин дерева без листків (N-1) і кількості підрахунків функції критерію, що дорівнює
N-1
Q(Д1) =(N-1) Qk + {N(N-1) / 2 + [ (N-i)] }QF = ~ О(N ),
i=1
де Qk - складність композиції, QF - складність обчислення функції критерію, а другий доданок у фігурних дужках визначає кількість підрахунків для новостворених елементів з утвореними раніше. Квадратна обчислювальна складність О(N) цього алгоритму робить проблематичним його використання для схем великої розмірності. Оскільки в практичних задачах схеми відображаються графами, далекими від повних, в роботі запропоновані вдосконалення методу, які полягають
F(Aij ) F (1- kv),
де F - найкраще значення функції критерію серед всіх пар вершин на цьому кроці об'єднання, kv (kv< 1) - коефіцієнт кількості об’єднань (коефіцієнт точності і швидкості згортання) на кроці;
а) для суміжних пар базової множини Х, що призведе до заміни
N (N-1) (N / 2) ксер,
де ксер - середній степінь вершини;
б) використанні мінімаксного принципу, в якому пошук пар здійснюється в екстремальному середовищі без зберігання всіх суміжних пар, а тільки найкращих суміжних пар. Після модифікацій алгоритму його обчислювальна складність, залишаючись залежною від kiлькості об'єднань та кількості підрахунків функції F, вже більшою мірою визначається стратегією врахування наповненості графа, способу зберігання тощо і для практичних задач знаходиться в межах
Q(Д2) = ~{ О(N) О(NlogN )} .
Розроблені методи розв’язування ряду задач декомпозиції для схем великих розмірностей оперують відповідним деревом згортання чи його побудовою. Перша група методів призначена для отримання певної кількості підсхем з заданою кількістю вершин у них і базується на алгоритмах опрацювання дерева згортання. Алгоритмічна складність послідовного методу визначається алгоритмами сортування частини вершин дерева, побудови дерева згортання за мінімаксною стратегією чи суміжних кандидатів і знаходиться в межах Q(В1) = ~{О(N) О(NlogN )}. Алгоритмічна складність паралельно-послідовного методу визначається алгоритмом побудови дерева згортання з додатковими затратами на пошук кандидатів для добору та корекції зменшених вершин дерева, тобто
Q(В2) = Q(Д( N)) + О(m)= ~{ О(NlogN ).
У дихотомічному алгоритмі згортання повторюється у просторі вершин, який поступово зменшується на кількість (m) виділених вершин і його обчислювальна складність визначається як
Q(В3) = log (N/m) Q(Д(N)).
Для розв’язання задач компонування, тобто декомпозиції з обмеженнями, накладеними на сумарні фізичні характеристики елементів схеми використовується принцип побудови неповного дерева згортання та переформування вершин дерева під час його побудови. Обчислювальні затрати алгоритму пов'язані з одним неповним згортанням всього графа, добором елементів до частин, що формуються, і згортанням елементів розформованих вершин
Q(К1) =(1 + lсер) Q(Д(N)),
де lсер - коефіцієнт для врахування кількості розформувань.
Методи цієї групи базуються на процедурі логічного розформування меншої з двох вершин дерева і процедури пошуку у глибину найкращих кандидатів для об’єднання серед раніше утворених вершин з розформованої вершини. На рис. 1 проілюстровано відмінності двох
Рис. 1. Стратегії алгоритмів компонування з розформуванням
методів компонування з розформуванням: а - дві вершини кандидати на об'єднання. б - одна вершина розформована і дві елементарні були почергово об'єднані з іншою вершиною; в - вершина розформована до певного рівня.
Модифікацією неповного згортання є вимушене згортання, в якому характеристики вершин дерева –це частини фізичних характеристик шуканих компонент, а структура дерева відповідає коефіцієнтам ділення схеми на компоненти та їх частини. Для випадку некратних характеристик елементів дерево має нерегулярний вигляд. Оптимальність компонування досягається вибором найкращих пар з можливих в межах обмежень. Складність методу повністю залежить від алгоритму побудови дерева згортання та розкиду характеристик елементів. Ознаками вимушеного згортання є розформування або блокування. На рис. 2 зображено фрагмент дерева згортання. Деякі вершини верхнього рівня відповідають фрагментам-кандидатам на виділення як підграфів Gn, а інші - фрагментам-кандидатам на розформування Gs.. Отриманий граф фрагментів опрацьовується процедурою логічного розформування і доповнення після розв’язання оптимізаційної задачі - пошуку фрагментів-кандидатів для виділення як кінцевих підграфів і фрагментів-кандидатів на розформування. У задачі обчислюються якісні параметри фрагментів, зокрема, і компонування, в цілому.
Рис.2. Фрагменти дерева неповного згортання
Розроблено підхід для розширення області пошуку оптимальної декомпозиції, який базується на побудові дерева згортання з нечіткими характеристиками вершин дерева. Перевагою нечітких характеристик є незакріпленість частини складу груп елементів на вершинах дерева, що створює додатковий частково призначений простір пошуку найкращих розв’язків задачі (рис.3). Маніпуляція спільними вершинами і усунення
Рис. 3. Переведення нечітких фрагментів у фіксовані
нечіткості дозволяє сформулювати оптимізаційний процес закріплення вершин для формування розбиття чи компонування в середовищі спільних елементів схеми –вершин графа. Використано поняття нечіткості двох типів: нечіткість вершин, що утворені під час однієї побудови дерева згортання та нечіткість, що утворюється внаслідок накладання фрагментів, утворених, як мінімум, на основі двох розбиттів, тобто дворазової побудови і опрацювання дерева згортання. Друга декомпозиція здійснюється частково примусово за певною стратегією включення елементів до компонент або вільно після зміни критеріїв, але з врахуванням обмежень на фрагменти в двох випадках. Мета багатократного згортання –виявити постійну складову шуканих фрагментів та простір, що відповідає змінній складовій фрагментів. Для декомпозиції з накладанням є справедливими рівняння
( Мі ) ( Мj) = Е, (Мі Мj) = Е, і=1,...,к; j=1,...,t, (2)
i j i , j
які показують, що поділ множини Е здійснено двома способами на різну кількість частин, М=(М,…,Мк) - фрагменти, отримані за одними правилами поділу, М= ( М,…,Мt ) - за іншими правилами. Фрагменти з різних множин мають в перетині спільні елементи, тобто
ij Мі Мj = Мij, Мij Е, s =|Мij|, s =1,2,... , (3)
де Мij - підмножини елементів, спільних для фрагментів, отриманих за різними стратегіями. Обмеження полягають у недопущенні повторного об’єднання в одному фрагменті Мі, наприклад, l/2, (l/2)-1,...,2 елементів, які належать одному фрагменту Мjз l елементів попереднього згортання. Графічно це зображається розрізом площини двома способами: 1-й - горизонтальними лініями, 2-й - вертикальними і накладання розбиттів одне на друге. На рис. 4,а для другого поділу обмеженнями виступає кількість 1/4 від всього складу елементів або половина фрагменту. Рис. 4,б є ілюстрацією, коли друге розбиття здійснено, наприклад, після зміни критеріїв згортання без накладання обмежень. Після двох декомпозицій
Рис. 4. Накладання розбиттів площини
утворились чотири частини, з яких наступними алгоритмами вибираються кандидати на добирання, розформування і покращання.
Для формування фрагментів Мі, Мj, розроблено методи компонування та пакування, які враховують результати попередніх декомпозицій. В основі методів є побудова дерева згортання, а врахування обмежень становить суттєву надбудову у зв’язку з використанням елементів примусу та врахування характеристик фрагментів. Ілюстрацією роботи методу для побудови компонентів, що перетинаються за певними правилами, є рис. 5 (вверх - вільне згортання, вниз –з обмеженнями). Для отримання розбиттів з довільним перетином компонентів найпростішим способом є зміна критерію повторного згортання або самого алгоритму згортання.
Рис. 5. Згортання фрагментів, що перетинаються
Задачі локальної оптимізації результатів компонування чи пакування, отриманих на основі побудови дерев згортання, класифіковані як такі:
Прийнято, що початкова кількість груп завжди перевищує кінцеву. Перенесення класифіковані з погляду способу і кількості груп. Виділено такі стратегії: перенесення та обмін (рис. 6,а), перенесення ланцюгом, циклічне (рис. 6,б) тощо.
e1
Рис. 6. Стратегії обміну і перенесення елементів
Розроблені методи реалізовані програмно, а їх тестування на багатьох прикладах показало, що кількість фрагментів при компонуванні та розбитті є меншою на 10-20 відсотків, ніж відомі з літератури для аналогічних задач. Швидкодія та мінімальні ресурси пам’яті дають змогу багатократно повторювати експерименти у просторі керуючих параметрів.
Третій розділ присвячено методу ієрархічного розміщення на площині і в просторі, що базується на накладанні та перетині макромоделей, отриманих як фрагменти розбиття методом компонування схем. Цей підхід названо розміщення макромоделюванням з накладанням, для якого є справедливим рівняння і умови (2,3). Для більшого, ніж два, числа макромоделей графічно цей поділ зображається розрізом площини або її частин двома способами: вертикальними та горизонтальними лініями і накладання розбиттів одне на друге (рис. 7, заштрихована частина - перетин Мij).
Рис.7. Розбиття площини двома правилами
Для формування макромоделей Мі, Мj, що перетинаються, застосовано розроблені методи компонування на основі парного згортання з врахуванням обмежень на якісний та кількісний склад елементів у компонентах повторного згортання. Зокрема, ілюстрацією роботи компонування схеми за правилами розрізу площини на рис. 7 є подвійне дерево на рис. 8 (друге зображене частково).
Рис. 8. Дерева формування макромоделей з обмеженнями
Включення спільних елементів у дві макромоделі дозволяє двічі знаходити найкращі зв’язки в межах цих макромоделей і досліджувати вплив їх переміщень по двох осях координат на загальну функцію довжини з’єднань при розв’язуванні задачі розміщення. При накладанні макромоделей для визначення позиції кожного елемента множини E на площині розв’язуються дві подібні задачі призначення макромоделей на позиції лінійок
Mо Lо , Mо Lо , (4)
щоб мінімізувати функції Fо і Fо сумарної довжини з’єднань між макромоделями. У позначеннях тип індексу задає спосіб. Задачі відрізняються між собою потужностями множин Mо, Mо. Отримані внаслідок розв’язування задачі лінійного розміщення (4) номери позицій лінійок Li і Lj, які закріплені за макромоделями Mi та Mj, вказують на номер стовпця і рядка, до яких належать елементи цих макромоделей.
Розроблено метод розміщення елементів схеми в тривимірному просторі, що базується на формуванні макромоделей алгоритмами компонування при їх триразовому перетині. У тривимірному випадку компоненти - макромоделі задовольняють рівняння
( Мі ) ( Мj ) ( Мs ) = Е, (5)
де макромоделі отримані за різними правилами поділу площин куба: М = (М,…,Мn ) - xz, М = ( М,…,Мm ) - yz, М0=(М1,…,Мp) - xy . У перетині макромоделей з різних площин є різна кількість елементів
ijs Мі Мj Мl = Мij, Мij Е, s =|Мij|, s =1,2,... (6)
Графічно (5,6) зображається поступовим розрізом трьох площин і, відповідно, об’єму куба горизонтальними, вертикальними та поперечними площинами і накладання розбиттів (рис. 9).
Рис. 9. Розбиття куба за трьома правилами
У тривимірному випадку при накладанні макромоделей для визначення позиції кожного елемента множини Е в об’ємі куба розв’язуються три задачі призначення макромоделей на лінійках Lо, Lо і Lо позицій
Mо Lо, Mо Lо і Mо Lо , (7)
щоб мінімізувати функції Fо, Fо і Fо сумарної довжини з’єднань між макромоделями (включаючи відстані до стінок куба). Ознакою глобального характеру методу накладання макромоделей є кількість елементів кc в перетині макромоделей Мі , Мj та Мl , сформованих за різними правилами. Ця кількість може бути довільною, але з погляду кількості обчислень число кc обмежується, оскільки воно визначає розмірність груп елементів, в межах яких остаточне призначення позицій не реалізоване. Якщо в перетині макромоделей є один елемент, то після закріплення макромоделей Мі, Мj та Мl на відповідних позиціях лінійок L , L та Lо координати призначення елемента є визначеними. Крім кількості елементів у перетині, використовується характеристика, яка вказує на спосіб розміщення цих елементів у макромоделях, наприклад, 12, 21, 22 тощо, приклади яких зображені на рис. 10. Збільшення кількості елементів в усіх перетинах макромоделей зменшує кількість макромоделей в межах типів Мі, Мі , Мl.
Рис. 10. Варіанти перетинів макромоделей
Після розв’язування задач розміщення (7) на лінійках місця спільних елементів є визначеними з точністю до координат позицій, призначених макромоделям. Наприклад, для випадку 22 чотирьом спільним елементам призначені координати xk, yk, а для уточненняположеннякожногоелемента на осі ординат здійснюються перестановки з додатковими обчисленнями значень функції критерію (рис. 10). Реалізовані дві стратегії уточнення координат елементів з перетинів: 1) до них окремо застосовуються точні або наближені методи для знаходження оптимальних координат, 2) уточнюють координати в межах методів локального характеру для всього простору. Кількість невизначених груп (двійок, трійок, четвірок тощо)
kn= | М | | М | | М0 |,
тобто початкове розміщення накладанням макромоделей зводиться до формування двійок, трійок, четвірок, тощо і знаходження для них оптимального місця як компонентам неявно. На рис. 11 явно об’єктами задачі розміщення є 2 горизонтальні і 3 вертикальні компоненти –макромоделі, а неявними - 6 компонент по 4 елементи.
Рис. 11. Макромоделювання з накладанням
Сформульовано критерії, які у вигляді бібліотеки використовують програми. Зокрема, запропоновані критерії для формування простору проведення міжелементних з’єднань, а саме: рівномірного розподілу зайнятої площі, рівномірного розподілу зайнятих контактів, рівномірного розподілу контактів у каналі даної макромоделі, рівномірного розподілу зовнішніх зв'язків між макромоделями, оцінка кількості транзитних ланцюгів тощо.
Розроблені методи розміщення графів на лінійці, як важливої складової розміщення через накладання макромоделей на площині та у просторі. Алгоритми класифіковані за складністю обчислень. Виділені п’ять груп методів: 1) точне укладання, 2) укладання графа на основі його дерева –складність визначається алгоритмами побудови дерева в графі, 3) розміщення на основі дерева згортання графа –обчислювальна складність знаходиться в межах складності алгоритму згортання; 4) поєднання стратегій ієрархічного розміщення з локальними процедурами на рівнях дерева згортання - складність визначається компонуванням та процедурами локального пошуку; 5) розміщення на лінійці застосуванням накладання макромоделей на коловій моделі розміщення і розрізом кола - складність визначається згортанням та процедурами уточнення.
Розроблені стратегії оптимізації результатів, отриманих на площині та у просторі методами накладання макромоделей. Наряду з процедурами повних перестановок елементів в обмеженому просторі, які застосовують на кінцевих етапах оптимізації, для просторих моделей (куб містить 8 елементів) розроблено методи ефективних перестановок, що реалізують мінімаксний принцип у виборі кандидатів та напрямів для перестановок, зменшуючи кількість обрахунків цільової функції. Складовою частиною цих методів є накладання макромоделей у мікропросторі (рис.12,а). Цю групу методів застосовують на проміжному етапі при переході від методів конструктивних до ітераційних. Запропоновані неперервні колові та сферичні моделі простору пошуку екстремальних значень функції, які полягають у згортанні лінії чи площини навколо осей Ox , Oy, Oz чи по двох осях одночасно (рис. 12,б). Неперервні моделі простору надають методам
Рис.12. Моделі просторів пошуку
локального характеру ознак глобальності за рахунок можливих перенесень елементів між фізично далеко розташованими позиціями. Побудова неперервних моделей здійснюється в просторі структур даних.
Як приклад застосування методів розміщення на основі накладання макромоделей на коловій моделі та укладання графа на лінійці розглянуто підхід до розв’язання задачі пакування (компонування за максимальною кількістю елементів та обмеженнями на кількість зовнішніх ланцюгів), яка в попередньому розділі розглянута як просторова задача. Задача пакування розв’язується пошуком екстремумів одновимірної дискретної функції густини січень залежно від координати лінійки (рис. 13,а) при умові попереднього знаходження оптимального розміщення графа на лінійці чи колі. Застосувавши метод накладання макромоделей до розміщення графа на коловому представленні лінійки (рис. 13,б) знаходимо оптимальне пакування рухом областей пошуку на колі (рис. 13 в), або іншими стратегіями.
Рис. 13. Макромоделювання для пакування на колі
Розроблені методи реалізовані програмно, а їх тестування на багатьох прикладах показало, що показники якості розміщення (довжина провідників за інтегральними чи мінімаксними критеріями) кращі, ніж відомі для аналогічних задач і має алгоритмічну складність, що не перевищує квадратної.
У четвертому розділі сформульована задача реалізації міжелементних з’єднань на площині та у просторі як оптимізаційна екстремальна задача на графах: знайти в графі (на моделі ДТРП тощо) мінімальне зв’язувальне дерево Tei*(W*(ei),V(ei)) (МЗД) для з’єднання вершин W*={W(e),W(e),..,W(es)} при виконанні умов мінімізації ряду функцій Fi (T*) = min Fi(T), що визначають якість дерева та обмежень. Запропоновані та проаналізовані моделі комутаційного простору (дискретного топологічного робочого поля - ДТРП) для побудови макроз’єднань. При переході до графової моделі простору з'єднання E представляються множиною вершин, які необхідно з'єднати. Критеріями якості побудованих дерев є функції сумарної чи максимальної довжин з’єднань, кількість кутів тощо. Розроблено методи побудови МЗД на основі принципу оптимального згортання контактів ланцюгів, який виступає керуванням для здійснення етапу макротрасування, незалежно від способу проведення фрагментів: лініями, променями чи хвильовим алгоритмом. В ієрархічному методі макротрасування використані поняття нечітких (розмитих) з’єднань на різних рівнях ієрархічного дерева згортання, які утворюються при об’єднанні контактів у кластери (блоки) і базується на факті, що для двох-трьох контактів ланцюга точний розв’язок завжди отримується. Критерієм для вибору найкращих пар вершин дерева Тз для згортання є мінімальна відстань між ними у ортогональній чи евклідовій метриці, тобто
Fij*= min L (i,j), i,jІ,
де відстань L (i,j) для кожного окремого випадку визначається за різними формулами. Розроблено паралельно-послідовну стратегію керування побудовою МЗД для почергової реалізації фрагментів груп ланцюгів із змінною кількістю ланцюгів у групі. Послідовна стратегія є частинним випадком, коли група містить один ланцюг. Керування паралельно-послідовним проведенням міжз’єднань здійснюється на основі побудови оптимального лісу згортання контактів і фрагментів міжз’єднань (рис. 14,а) та відповідних їм блоків (рис. 14,б).
Рис. 14. Фрагмент лісу дерев згортання контактів ланцюгів
Для згортання вершин використано принцип побудови вільного дерева згортання, в якому насамперед об’єднуються найближчі елементи. Розроблені різні стратегії побудови фрагментів МЗД: проведення бінарних з’єднань, коли на кожному рівні блок розглядається як сукупність двох блоків нижчого рівня, пошук 3-арних з’єднань для розбиття на три блоки тощо. Збільшення арності задачі ускладнює її, але призводить до кращих значень цільової функції сумарної довжини. Розроблені стратегії ранжування ланцюгів та їх фрагментів з погляду їх розташування та відстаней між контактами для мінімізації завантаженості комутаційного простору. Обчислювальна складність методу визначається алгоритмом побудови дерева згортання (повний граф - O(n) ) і складністю алгоритму побудови смуг невизначеності між блоками, який реалізований за допомогою алгебраїчних перетворень і хвильового алгоритму. Обчислювальна складність паралельно-послідовного макротрасування є більшою від послідовної стратегії за рахунок необхідності перерахунків відстаней між контактами і фрагментами в межах одного ланцюга, але не перевищує O(n). Метод вимагає значного об'єму оперативної пам’яті, який зростає при зберіганні з'єднань багатьох ланцюгів одночасно.
Важливим фактором, який впливає на якість і швидкодію макротрасування є вибір кількості вертикальних каналів в ДТРП. Якщо прийняти ширини всіх вертикальних каналів ДТРП рівними, то можна вважати, що структура ДТРП регулярна і рівномірна (рис. 15,а). Більш точною є модель ДТРП з регулярною нерівномірною структурою (рис.15,б), побудова якої здійснюється з метою виключення наявності двох і більше еквіпотенціальних контактів в одній грані. Ширина вертикального каналу в цій моделі ДТРП приймається мінімальною серед всіх відстаней бінарних з'єднань в усіх горизонтальних каналах. У моделі ДТРП з регулярною нерівномірною структурою топологічна ситуація в грані частково контролюється за допомогою кількості і списку номерів ланцюгів, траси яких перетинають чотири ребра, інцидентних даній грані. Якщо розбиття на грані здійснювати для кожного горизонтального каналу окремо при виконанні умови не потрапляння двох і більше еквіпотенціальних контактів в одну грань, то модель ДТРП має нерегулярну структуру (рис. 15,в). Загальна кількість граней моделі ДТРП нерегулярної структури менша від кількості граней моделі ДТРП регулярної нерівномірної структури, оскільки у другій моделі ширини вертикальних каналів представляють найгірші випадки серед всіх горизонтальних каналів, тобто менших ширин граней вже бути не може. Зменшення розмірності задачі при використанні нерегулярної моделі є позитивним фактором. У той же час перевагами регулярності є простота структур даних для опису моделей ДТРП. Найскладнішим типом моделі ДТРП є різногабаритна структура (рис. 15,г), яка формується для замовних НВІС.
Рис.15. Моделі ДТРП
Різні моделі ДТРП і керування кількістю граней у них спричиняють задачу побудови компромісної за точністю та часом побудови моделі. При побудові регулярних моделей ДТРП додатково до функції густини січень окремих каналів будується узагальнена функція густини як сума функцій густин окремих каналів F(j)= fi(j) , де j - номер дискретного кроку поверхні. Оптимізаційна задача полягає у знаходженні такого розбиття на KB рівних частин сумарної функції густини, щоб максимізувати кількість розрізаних бінарних відрізків. Для знаходження компромісного (з погляду значень KB і кількості перетинів) розрізу каналів на рівні частини розроблені методи пошуку оптимального K*.
Розроблено універсальний метод призначення, що застосовується для знаходження фрагментів макро- і мікроз’єднань. Зміст задачі оптимального призначення полягає в знаходженні відображення ER, де E - множина елементів, R - множина ресурсів, за якого функції якості набувають екстремальних значень, наприклад, мінімізації довжини використаних горизонтальних магістралей, кількості міжшарових переходів тощо. Метод базується на сукупності моделей та алгоритмів їх опрацювання.
Модель однорівневого призначення. Призначення здійснюється після знаходження МЗД кожного ланцюга або після знаходження МЗД всіх ланцюгів. У першому випадку алгоритм є простий, але отримані результати не є оптимальними. У другому - за рахунок вибору з множини результати є кращими. Вертикальні фрагменти дерев і області, до яких вони підходять, відрізняються між собою довжиною, кількістю лівих і правих горизонтальних складових, розташуванням контактів на горизонтальних границях. Перераховані характеристики впливають на координати призначення вертикальних фрагментів. При розгляді еквіпотенціальних контактів для одного типу у каналі виділено три основних (а,б,в) і два похідних (г,д) випадки (рис. 16), де заштриховані смуги визначаються координатами еквіпотенціальних контактів, у межах яких бажано реалізувати одноіменні вертикальні фрагменти. Вихід за межі смуг супроводжується
Рис. 16. Смуги розташування контактів
збільшенням довжини використаних горизонтальних ресурсів. На основі смуг оптимальності формулюються обмеження для керування координатою призначення
xil xi xir,
де xil, xir- відповідно, ліва і права координати границь областей, оптимальних для проведення в них вертикальних фрагментів, xi - дискретна змінна координати і-го вертикального фрагмента. Для формування цільової функції, що вказує на міру оптимальності координат призначення, приймається
| xi - xir | , xi > xir,
gi(xi) = | xi - xil |, xi < xil ,
0 xil xi xir .
Сформульована задача: на множині дискретних значень координат переходів між каналами Q = (q, q,..., qN) знайти координати, які мінімізують функцію
F =w g(х)+ wg(х)+...+ wngn(xn) (8)
при виконанні обмежень
x i x j , і j; i ,j є 1...,,n. (8a)
Цільова функція формулює вимогу перебування фрагментів в смугах оптимальності. Обмеження пов’язані з неможливістю призначити різним фрагментам однакові координати; wі - вагові функції кожного фрагмента, як правило, обернено пропорційні значенню ширини смуги .
Моделі багаторівневого призначення. Для двох суміжних каналів, зображених на рис. 17,а, тільки в позначених смугах координата призначення не впливає на загальну довжину горизонтальних відрізків. Поза смугами вона зростає лінійно з віддаленням від смуги. У дворівневому випадку розв’язування задачі (8) здійснюється для спільної границі каналів. Для багатоканального об’єднання залежно від кількості і розташування смуг оптимальності в каналах (рис. 17,б) будується узагальнений канал і функція S(xі) залежності сумарної довжини горизонтальних відрізків від координати призначення вертикального фрагмента. Функція набуває мінімального значення на певному проміжку, який приймається як смуга оптимальності в багаторівневій моделі для визначення границь в задачі (8). Реально переходи представляються окремими відрізками, як це проілюстровано на рис. 18,а. Позначивши їх множиною R = ( R, R,..., Rm ), де Rі= (rii+1, rii+2,...,rik) - підмножина відрізків з і-го каналу до і+1, і+2,..., k-го каналів; m - кількість каналів та ввівши подібну множину вертикальних фрагментів E =(Е, Е,..., Еm), де Еі= (еii+1, еii+2,...,еik) (приклад зображено на рис. 18,б з посортованими за довжиною і початковим рівнем елементами), необхідно розв’язати задачу оптимального призначення фрагментів трас E на множину ресурсів R. Елементи множини E розташовані на осі Ох згідно з координатами, отриманими після розв’язування задачі (6) для узагальненого каналу або для двох каналів як однієї моделі на основі смуг окремих каналів.
Рис. 17. Формування смуг оптимальності
У роботі розв’язана оптимізаційна задача за допомогою моделі у вигляді зважених орграфів G (звичайна та надлишкова - рис.18,в), які відображають ресурси так: множині каналів відповідає множина вершин X, множині ресурсів R - множина дуг, координаті ресурсу - вага дуги в
Рис. 18. Множини ресурсів і фрагментів та їх модель
орієнтованому графі. Сумарне алгоритмічне забезпечення багаторівневої моделі складається з методів побудови еквівалентних однорівневих моделей для всіх фрагментів у багатоканальному об’єднанні, знаходження координат призначення на множині умовних переходів узагальненого каналу в задачі (8), перетворення координат умовних переходів у послідовність відрізків реальних переходів множини R. Для розв'язування задачі призначення вертикальному фрагмента eij в графі G знаходиться шлях між і-ю та j-ю вершинами, оптимальний з погляду співвідношення умовних і реальних координат, кількості переходів між магістралями, довжини горизонтальних з'єднань тощо. Оптимізація здійснюється методом поступок: пошук оптимального розв’язку згідно з найважливішим критерієм, далі в межах певної поступки в головному критерії знаходиться оптимальний розв’язок за другим критерієм і т.д.
Методи макротрасування та призначення були застосовані до архітектури ПЛМ, які складаються з прямокутного масиву логічних блоків та множини програмованих ресурсів з’єднань. Використання розроблених стратегій керування трасуванням, як і декомпозиція простору, дозволили отримати кращі результати за шириною каналів та довжинами провідників, ніж відомі.
У п’ятому розділі розглянуті етапні задачі мікротрасування в каналі як пакування відрізків на ресурсах каналу без обмежень та з обмеженнями, які виникають при врахуванні бічних контактів. Сформульовано задачу : знайти відображення ВR , за якого відрізки В не перетинаються в межах однієї магістралі, а кількість використаних магістралей є мінімальною. Додатковими критеріями оптимальності є функції, які вказують на довжину вертикaльних складових з`єднань, кількість поворотів тощо. Для розв`язування поставленої задачі розроблено метод пакування на основі пошуку максимально можливих шляхів у графі вертикальних конфліктів GV, тобто перетворення його до вигляду GVS, в якому задано порядок укладання, як мінімум, в межах максимального шляху. Посортовані відрізки згідно з початковою координатою і послідовність вершин у шляхах є керуючою інформацією для роботи основної частини алгоритму, а саме: реалізації стратегії управління або визначення порядку укладання відрізків на магістралі. Знайдені максимальні шляхи не дають повної інформації для цього. Додатковою керуючою інформацією для укладання відрізків є ребра графа горизонтальної безконфліктності GG, наведені між вершинами різних максимальних шляхів (в межах шляхів головними керуючими є дуги підпорядкованості контактів) та дуги графа GV , що не ввійшли у максимальні шляхи. Розроблено стратегії призначення відрізків: послідовна, повних підграфів та режим повернень. Кількість шляхів в ієрархічному дереві пошуку - це можливі варіанти укладання відрізків. Пошук оптимального варіанта відбувається обходом дерева можливих розв’язків. У зв’язку з побудовою дерева перпендикулярно до магістралей і накладеними обмеженнями вертикальних та горизонтальних конфліктів ширина та глибина дерева пошуку не набувають великих значень, що робить можливим перебір всіх варіантів пакування для знаходження оптимального.
Для збільшення процента реалізованих з’єднань застосовується принцип “плавання” контактів. Розроблено спосіб управління топологічною ситуацією в каналі і попереднього призначення незакріплених контактів на горизонтальних сторонах каналу. Використання моделі плаваючих контактів дозволяє одночасно розв’язувати задачі які, звичайно, розв’язуються окремо: призначення вертикальних фрагментів дерев на вертикальні магістралі пластини; побудова з’єднань у каналі; призначення периферійних комірок і ланцюгів на їх контакти. Формулювання задачі призначення контактів на позиції у моделі каналу з “плаваючими” контактами таке: множину Кн незакріплених контактів призначити на множину Z вільних позицій
Кн Z так, щоб мінімізувати сумарну довжину з’єднань у каналі, кількість конфліктів в графі вертикальних конфліктів та довжину максимального шляху у графі GV. Задача доповнюється обмеженнями, пов’язаними з утворенням циклів в графі GV, рівномірним розподілом вільних позицій для контактів, а також іншими похідними обмеженнями. Врахування всіх критеріїв і обмежень ускладнює задачу, збільшує час для її розв’язання. Розроблено методи розв’язування задачі з оптимізацією основних показників, а саме: довжини з’єднань і кількості конфліктів на моделі каналу. Результатом роботи методів призначення є координати кортежів верхніх і нижніх контактів грані, які відповідають оптимальним значенням цільових функцій. Вони не є оптимальними в глобальному сенсі і покращуються процедурами локальної оптимізації. Реалізовано комбінаторний метод, в якому генеруються перестановки верхніх чи нижніх контактів, підраховується функція мети для кожного випадку і найкраще значення запам’ятовується. Факторіальна складність зменшена почастинним розв’язуванням задачі. Розроблено метод цілеспрямованого зменшення конфліктів, циклів і довжини шляхів в графі конфліктів грані чи каналу, який на етапі призначення знімає задачу знаходження конфігурації з’єднань. Завдання розробленого методу полягає в знаходженні контактів на верхній та нижній границі грані, які треба пересунути на інші позиції, щоб зменшити довжину максимального шляху в графі GV; розбити цикли, якщо вони можливі; зменшити кількість конфліктів, тобто кількість дуг в графі GV.
Розроблено метод мікротрасування в чотиристоронньому каналі (перемикачі) як задачу пакування відрізків з обмеженнями. Розроблено дві стратегії пакування: 1) послідовна стратегія : призначення кінцевих координат на всі бокові контакти; оптимізація призначення; розміщення відрізків на магістралях згідно з шляхами графа вертикальних конфліктів і горизонтальних обмежень; 2) послідовно-паралельна стратегія: призначення кінцевих координат відрізків тих бокових контактів, аналіз конфліктності яких не призводить до багатозначності; оптимізація призначення; розміщення відрізків на крайніх вільних магістралях, формування вільних пар позицій, призначення кінцевих координат на відрізки невикористаних раніше бічних контактів.
Стратегії послідовного вибору бічних контактів є керованими вибором бічних контактів не згідно з номерами магістралі їх розміщення чи стратегії, а на основі вагових коефіцієнтів пріоритетів контактів, що входять в шляхи графа вертикальних конфліктів. Описані принципи покладені в основу алгоритмів пакування. Розроблено декілька динамічних варіантів методів: односторонній з призначенням, односторонній з уточненням, мікротрасування перемикача, універсальний двосторонній з уточненням. Обчислювальна складність алгоритмів не перевищує О (n2), де n - кількість бічних контактів. На практиці, завдяки підготовці інформації про пари контактів до початку роботи основного алгоритму, його складність прямує до О(n)÷ О(Nlog2N ). Порівняння результатів роботи розроблених методів на відомих прикладах підтверджує те, що в NP-складних задачах незакріпленість проміжних розв’язків і гнучкість процесу їх отримання дозволяють отримати більш якісні результати трасування каналів та перемикачів, які в цьому випадку визначаються двома основними факторами: якістю призначення кінцевих координат відрізків бічних контактів і стратегією призначення основних з’єднувальних відрізків.
У шостому розділі розглянуті архітектура та принципи взаємодії пакетів та модулів програм в підсистемі ієрархічного проектування площинної та просторової топології НВІС (рис. 19) на основі розроблених методів, моделей та алгоритмів. Пакети працюють автономно або послідовно так, що кожний наступний використовує інформацію від попереднього. Всі види вхідної, проміжної та вихідної інформації зберігаються у базах, які представляють собою набори
структур даних моделей. Зв’язок з різними типами задач здійснюється через вхідний та вихідний інтерфейси. Спільною вхідною інформацією
Рис. 19. Склад підсистеми проектування топології НВІС
є гіперграф пристрою, характеристики площини, обмеження на розміри частин та позиції елементів, характеристики простору проведення міжз’єднань. Кінцева вихідна інформація призначена для закріплення елементів за відповідними позиціями та фіксації координат і типів міжз’єднань. Описані структури програмних пакетів та основні структури даних, що впливають на необхідні ресурси для розв’язання задач. Враховуючи багатоваріантність алгоритмічного забезпечення (кожний пакет має множину алгоритмів розв’язування етапної задачі), процес можливих шляхів його виконання представляється у вигляді ієрархічного дерева з кожним програмним пакетом на рівні (рис. 20). Повний процес проектування можна представити у вигляді шляху ітераційних процедур з можливим поверненням на будь-який попередній крок (рис. 21). Кожний комплекс має ядро, що характеризує його виконавчий метод. Ядрами є модулі, які працюють з ієрархічними моделями даних, а саме: побудови і опрацювання дерева
Рис. 20. Дерево можливих шляхів
згортання графа, багатократного згортання графа, згортання позицій площини з контактами ланцюгів, опрацювання лісу дерев чи опрацювання дерева пошуку оптимальних розв'язків окремих задач. Програмні пакети складаються з керуючих програм та модулів, які в сукупності розв’язують чергові задачі. Приклад структури пакета розміщення та пакування зображено на рис. 22. Підпорядкованість
Рис. 21. Послідовність виконання пакетів
модулів зображена на рис. 23. Спільними частинами алгоритмів розміщення та пакування є процедури побудови дерева згортання з залученням бібліотек критеріїв та обмежень. Модуль оптимізації призначений для виклику і керування
Рис. 22. Структурна схема пакета розбиття і пакування
стратегіями локального покращання результатів, отриманих зазначеними раніше алгоритмами глобального характеру або випадково. Стратегії С1 - СN реалізують різні стратегії локальної оптимізації, а саме: оптимізації накладанням макромоделей, перестановками тощо. На рівні локальної оптимізації використовуються алгоритми глобального характеру, які на вищих рівнях ієрархії використовуються для отримання розв’язків глобального характеру. Спільні блоки на рис. 23 обведені штриховою лінією для зменшення позначень на рисунку.
Для створення програмного забезпечення використано сучасну технологію об’єктно-орієнтованого програмування, що включає в себе попередній глибокий аналіз класів об’єктів та їх взаємодії. Середовище має традиційні та конкретно-особливі переваги над процедурним підходом: система легко доповнюється новими стратегіями та алгоритмами; програміст не здійснює облік та контроль пам’яті.
Рис. 23. Структура пакета пакування та розміщення
задачі; зручне керування динамічними процесами в програмній системі. Для зберігання опису схеми при згортанні використано віртуальний спосіб виділення памяті залежно від наявних ресурсів. Загальний об’єм підсистеми – понад 50 тисяч операторів мови високого рівня.
У додатках наведені приклади алгоритмів, що реалізовані в програмних комплексах, приклади програмних інтерфейсів, зразки текстів програм, що відображають окремі класи для опису об'єктів моделей, а також акти впровадження.
ОCНОВНІ РЕЗУЛЬТАТИ РОБОТИ
В дисертаційній роботі розв’язана науково-прикладна проблема: на єдиній методологічній основі – методі оптимального згортання схем - розроблено вперше і узагальнені відомі методи ієрархічного проектування площинної та просторової топології НВІС, зокрема, методи розв’язання задач розбиття, розміщення і трасування, що належать до класів комбінаторних задач неполіноміальної складності. Досягнуто покращання в середньому на 10-20 відсотків порівняно з відомими підходами таких показників: кількість фрагментів розбиття, сумарна довжина провідників, ширини каналів. Отримані такі наукові результати:
СПИСОК ОПУБЛІКОВАНИХ РОБІТ ЗА ТЕМОЮ ДИСЕРТАЦІЇ
АНОТАЦІЯ
Мельник Р.А. Методи та алгоритми ієрархічного проектування площинної та просторової топології НВІС. – Рукопис.
Дисертація на здобуття вченого ступеня доктора технічних наук за спеціальністю 05.13.12 – системи автоматизації проектувальних робіт. - Національний університет “Львівська політехніка”, Львів, 2001.
Дисертація присвячена побудові методів, моделей та алгоритмів розв`язання трудно вирішуваних комбінаторних задач, які формулюються при проектуванні площинної та просторової топології інтегральних схем надвеликої розмірності. Розроблені теоретично та досліджені експериментально методи для розв'язування задач розбиття, компонування, пакування, розміщення, міжелементних з'єднань на площинних та просторових моделях на єдиній методологічній основі – побудові дерева оптимального згортання схем. Розроблена архітектура, принципи взаємодії програмних пакетів підсистеми ієрархічного проектування топології НВІС. Реалізоване програмне забезпечення підсистеми.
Ключові слова: САПР, топологія НВІС, дискретна оптимізація, комбінаторні задачі, пакування, розбиття, компонування, нечітка декомпозиція, накладання макромоделей, розміщення елементів, макротрасування, мікротрасування, нечіткі з'єднання, обчислювальна складність, архітектура підсистеми програм.
АННОТАЦИЯ
Мельник Р.А. Методы и алгоритмы иерархического проектирования пространственной и плоскостной топологии СБИС. – Рукопись.
Диссертация на соискание ученой степени доктора технических наук по специальности 05.13.12 – системы автоматизации проектных работ.- Национальный университет “Львовская политехника”, Львов, 2001.
Диссертация посвящена построению методов, моделей и алгоритмов решения трудных комбинаторных задач, которые формулируются при проектировании плоскостной и пространственной топологии интегральных схем сверхбольшой размерности. Разработанные теоретически и исследованы экспериментально методы на единой методологической основе - оптимальном свертывании схем - для решения задач разбиения, компоновки, упаковки, размещения, реализации межэлементных соединений на плоскостных и пространственных моделях. Разработана архитектура и принципы взаимодействия пакетов программ в подсистеме иерархического проектирования топологии СБИС. Разработано программое обеспечение.
Ключевые слова: САПР, топология СБИС, дискретная оптимизация, комбинаторные задачи, упаковка, разбиение, нечеткая декомпозиция, компоновка, наложение макромоделей, размещение элементов, макротрассировка, микротрассировка, нечеткие соединения, вычислительная сложность, архитектура подсистемы.
ABSTRACT
Melnyk R.A. Methods and algorithms for hierarchical plate and space design of VLSI topology.- Manuscript.
Thesis on searching for doctorate degree of technical sciences by specialty 05.13.12 – automation design systems. - National University “Lviv Polytechnic”, Lviv, 2001.
More than 65 scientific papers (one book) are defended, which include theoretical and experimental researches for multilevel modeling, partitioning, packaging, placement and rooting methods. The new effective approaches, models and strategies for the large dimension problems using in common the hierarchical decomposition method are elaborated. The methods of the optimal reduction circuit tree building are elaborated and classified from the points of view for step velocity and merging accuracy. It is defined that the algorithms complexity depends from the problem formulation, circuit and strategy used: universal, of connected pairs or minimal-maximal. The algorithm complexity is within a range from logarithmic to square. Some methods based on working out the reduction tree are being analyzed, concretely parallel, consequent-parallel and binary.
New methods to form the components including multilevel are elaborated. They are based on the reduction tree partially built. The reforming and transforming principles for some tree vertices are used for these purposes. New methods of partitioning and packaging based on fuzzy clusters are developed. To find stable by size clusters and some with fuzzy characteristics allow to narrow a search space for the optimization algorithms with local possibilities. Fuzzy properties of different kinds are introduced. Local optimization procedures of two classes are elaborated: first ones could change the structure of final cluster groups and others change only content of the individual clusters. The procedures are used in constructive methods as well as at final stages of the decomposition processes.
The hierarchy method for space and plate placement is elaborated. It is based on crossing models and uses properties of evident and implicit cluster placement. New methods for linear placement as important part for crossing model placement are elaborated. The packaging and partitioning methods are elaborated based on one dimension discrete function posed on continuous circle model. The crossing models method is used for these purposes. The local optimisation procedures are elaborated. They use principle of crossing models in micro space and accuracy solution in macro space. Some continuous space models are proposed to accept the local algorithm properties of global ones. For these purposes some new strategies are also proposed.
The two and three dimension space models are elaborated and classified from the point of view to guarantee clearance of topology situation in routing space. The space models are as a result the combinatorial problem with many solutions the best from which are found by the series of space partitioning procedures. The decomposition methods to find the minimal connecting tree in the space models are elaborated. The reduction tree for net contacts is accepted as a control for rooting processes. The fuzzy connections between the tree vertices are used to increase the space to find the best possible solutions. The wave processes are classified and some strategies to decrease the computer resource losses as well as decomposition approach for wave processes are developed. The problem to assign with minimal resources the planned fragments of routing to concrete plate or space tracks are formulated and one-, two-, and many layers models are considered. Some methods for assignment based on extreme graph problem as well as minimal-maximal problem are elaborated.
The micro (canal, switchbox) routing problem is considered as segment packaging with constraints or without them. The solution tree is considered. It could be elaborated by all existing ways due to the character of canal dimension. The principle of “swimming” contacts is used for the assignment problem, which must be solved until the packaging process is in action. Some strategies for swimming net contacts assignment are proposed. The goal of the problems are to minimize canal conflicts, the length of the maximal possible way in the conflict graph. The methods and strategies for side contact segment assignment are proposed.
The architecture, flowcharts and software for CAD system for VLSI topology design are developed. Many examples of partitioning, packaging, placement and routing with different control environment for very large-scale circuits were run. Excellent and good compatible results were achieved.
Key words: САD, VLSI topology, fuzzy partitioning, packaging, hierarchy, crossing models, space and plate placement, macro- and micro-routing, fuzzy routing, algorithm complexity, architecture, software.