????????? ?? http://www.allbest.ru/

Національний університет “Львівська політехніка”

УДК 621.382

Методи та алгоритми ієрархічного проектування

площинної та просторової топології НВІС

05.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 рр.).

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

1. Проаналізувати відомі конструктивно-технологічні проектні рішення сучасних НВІС та методи проектування їх просторової та площинної топології, здійснити аналіз складності та розмірності задач, сформувати та уніфікувати математичні моделі схем і конструктивних просторів.

2. Розробити і дослідити методи розбиття та пакування на основі згортання схем з нечіткими характеристиками вершин, ієрархічні методи розміщення з накладанням макромоделей. Розробити та класифікувати за точністю і обчислювальною складністю методи розміщення одно і різногабаритних елементів в одно-, дво- і тривимірних просторах. Здійснити практичну розробку методів.

3. Розробити методологію, стратегії та алгоритми локальної оптимізації результатів розміщення, отриманих методами конструктивного характеру, на основі базової процедури, що використовує принцип накладання моделей в мікропросторі і уточнення позицій в макропросторі.

4. Класифікувати за обчислювальними затратами та розробити критерії розбиття схем і розміщення елементів для їх застосування у відповідних алгоритмах з метою: зменшення технічних ресурсів відтворення; покращання показників якості схем, таких як ширина каналу трасування чи максимальний час затримки сигналу.

5. Розробити методи ієрархічного макро- та мікротрасування з використанням дерева оптимального згортання контактів ланцюгів, розмитих (багатозначних) з'єднань між блоками та плаваючих контактів.

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

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

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

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

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

3. Розроблено методи та алгоритми побудови мінімальних зв'язувальних дерев на основі методу оптимального згортання контактів, які є керуванням для здійснення етапу макротрасування в просторі розмитих з'єднань. Застосування методів з використанням принципів невизначеності розширює простір пошуку оптимальних розв'язків, використання дерева та лісу згортання зменшує необхідні конструктивні ресурси , збільшуючи цим працездатність схем.

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

5. Розроблена архітектура та принципи взаємодії пакетів програм і модулів у підсистемі ієрархічного проектування площинної та просторової топології НВІС на основі розроблених методів, моделей та алгоритмів. Їх тестування підтвердило перспективність запропонованих підходів, показало, що кількісні результати, отримані в роботі з допомогою розроблених методів, перевищують в середньому на 10-20 відсотків відомі.

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

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

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

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

Практичне значення отриманих результатів. Автором розроблена підсистема проектування топології НВІС, яка складається з пакетів програм та модулів, які дозволяють розв'язувати задачі розбиття, пакування, компонування, розміщення одно- та різногабаритних елементів на площині та у просторі з врахуванням існуючих технологічних обмежень, трасування у просторових моделях з'єднань. Загальний обсяг програм, які реалізують запропонований методологічний та алгоритмічний апарат, становить понад 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 таблиць.ОСНОВНИЙ Зміст роботи

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

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

У другому розділі сформульовано мету і завдання декомпозиції схеми і розроблені методи та алгоритми для її розв'язування. Під час розбиття графа схеми необхідно отримати таке розбиття S_i*={A_i1*,...,A_in*}, для якого показник якості розбиття набуває оптимального значення

F(S_i*) = opt F(S_к ) (1)

S_к S(X).

Тут S_к - допустиме розбиття з класу S(X). Кожний елемент A_im=(X_im,V_im,R) складається з множини вершин X_im Х і множини ребер V_im V . Під час розбиття графa H = (X,V,R) на частини елементи розбиттів

S_і ={A_i1,..., A_in} повинні задовольняти умови:

(A_im S_i ) [Х(A_im ) X],

(A_im S_i ) [Х(A_im ) ],

(A_imS_i , A_ilS_i ) [A_im A_il , A_im A_il = ],

X(A_im )= X , V(A_im)=V, ( m=1,…, n ),

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

У роботі розглянуто формування специфічних задач розбиття (1), пов'язане з виконанням додаткових обмежень, які накладаються на параметри окремих підграфів та їх складових елементів, наприклад:

перебування розмірності підграфів у допустимих межах

N _i^- card X_i N _i⁺ , (i=1..n),

примусове перебування елементів у різних або спільному підграфах

x_i x_j Z_d [(x_iA_к ) (x_j A_р )], кр,

x_ix_j Z_t [(x_i A_к ) (x_j A_к )] ,

де Z_d - множина елементів, які повинні бути рознесені в різні фрагменти; Z_t - множина елементів, які повинні бути об'єднані в одному фрагменті, N _i^- , N _i⁺ - нижня і верхня допустимі границі розмірів фрагментів.

Основою методу розв'язування задачі розбиття є побудова дерева згортання (редукції) графа, де центральною є процедура оцінювання претендентів на об'єднання. Вибір типу критеріальної функції 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) Q_k + {N(N-1) / 2 + [ (N-i)] }Q_F = ~ О(N² ),

ⁱ⁼¹

де Q_k - складність композиції, Q_F - складність обчислення функції критерію, а другий доданок у фігурних дужках визначає кількість підрахунків для новостворених елементів з утвореними раніше. Квадратна обчислювальна складність О(N²) цього алгоритму робить проблематичним його використання для схем великої розмірності. Оскільки в практичних задачах схеми відображаються графами, далекими від повних, в роботі запропоновані вдосконалення методу, які полягають

· в керуванні кількістю об'єднань пар вершин на кроці контролем критерію пар вершин

F(A_ij ) F ₀ (1- k_v),

де F₀ - найкраще значення функції критерію серед всіх пар вершин на цьому кроці об'єднання, k_v (k_v< 1) - коефіцієнт кількості об'єднань (коефіцієнт точності і швидкості згортання) на кроці;

· в застосуванні різних стратегій обчислення критеріальної функції F :

а) для суміжних пар базової множини Х₁, що призведе до заміни

N (N-1) (N / 2) к_сер,

де к_сер - середній степінь вершини;

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

Q₂(Д2) = ~{ О(N) О(Nlog₂N )} .

Розроблені методи розв'язування ряду задач декомпозиції для схем великих розмірностей оперують відповідним деревом згортання чи його побудовою. Перша група методів призначена для отримання певної кількості підсхем з заданою кількістю вершин у них і базується на алгоритмах опрацювання дерева згортання. Алгоритмічна складність послідовного методу визначається алгоритмами сортування частини вершин дерева, побудови дерева згортання за мінімаксною стратегією чи суміжних кандидатів і знаходиться в межах Q(В1) = ~{О(N) О(Nlog₂N )}. Алгоритмічна складність паралельно-послідовного методу визначається алгоритмом побудови дерева згортання з додатковими затратами на пошук кандидатів для добору та корекції зменшених вершин дерева, тобто

Q(В2) = Q(Д( N)) + О(m²)= ~{ О(Nlog₂N ).

У дихотомічному алгоритмі згортання повторюється у просторі вершин, який поступово зменшується на кількість (m) виділених вершин і його обчислювальна складність визначається як

Q(В3) = log₂ (N/m) Q(Д(N)).

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

Q(К1) =(1 + l_сер) Q(Д(N)),

де l_сер - коефіцієнт для врахування кількості розформувань.

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

методів компонування з розформуванням: а - дві вершини кандидати на об'єднання. б - одна вершина розформована і дві елементарні були почергово об'єднані з іншою вершиною; в - вершина розформована до певного рівня.

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

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

( М_і ) ( М^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 від всього складу елементів або половина фрагменту. Коли друге розбиття здійснено, наприклад, після зміни критеріїв згортання без накладання обмежень. Після двох декомпозицій

утворились чотири частини, з яких наступними алгоритмами вибираються кандидати на добирання, розформування і покращання.

Для формування фрагментів М_і, М^j, розроблено методи компонування та пакування, які враховують результати попередніх декомпозицій. В основі методів є побудова дерева згортання, а врахування обмежень становить суттєву надбудову у зв'язку з використанням елементів примусу та врахування характеристик фрагментів. Для отримання розбиттів з довільним перетином компонентів найпростішим способом є зміна критерію повторного згортання або самого алгоритму згортання.

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

· Перенесення вершин між фрагментами, характеристики яких задовольняють обмеження. Кількість груп при цьому не змінюється.

· Перенесення вершин між фрагментами, характеристики яких не задовольняють обмеження. Кількість груп при цьому змінюється.

Прийнято, що початкова кількість груп завжди перевищує кінцеву. Перенесення класифіковані з погляду способу і кількості груп. Виділено такі стратегії: перенесення та обмін, перенесення ланцюгом, циклічне (рис. 6,б) тощо.

Розроблені методи реалізовані програмно, а їх тестування на багатьох прикладах показало, що кількість фрагментів при компонуванні та розбитті є меншою на 10-20 відсотків, ніж відомі з літератури для аналогічних задач. Швидкодія та мінімальні ресурси пам'яті дають змогу багатократно повторювати експерименти у просторі керуючих параметрів.

Третій розділ присвячено методу ієрархічного розміщення на площині і в просторі, що базується на накладанні та перетині макромоделей, отриманих як фрагменти розбиття методом компонування схем. Цей підхід названо розміщення макромоделюванням з накладанням, для якого є справедливим рівняння і умови (2,3). Для більшого, ніж два, числа макромоделей графічно цей поділ зображається розрізом площини або її частин двома способами: вертикальними та горизонтальними лініями і накладання розбиттів одне на друге.

Для формування макромоделей М_і, М^j, що перетинаються, застосовано розроблені методи компонування на основі парного згортання з врахуванням обмежень на якісний та кількісний склад елементів у компонентах повторного згортання. Зокрема, ілюстрацією роботи компонування схеми за правилами розрізу площини є подвійне дерево.

Включення спільних елементів у дві макромоделі дозволяє двічі знаходити найкращі зв'язки в межах цих макромоделей і досліджувати вплив їх переміщень по двох осях координат на загальну функцію довжини з'єднань при розв'язуванні задачі розміщення. При накладанні макромоделей для визначення позиції кожного елемента множини E на площині розв'язуються дві подібні задачі призначення макромоделей на позиції лінійок

M_о L_о , M^о L^о , (4)

щоб мінімізувати функції F_о і F^о сумарної довжини з'єднань між макромоделями. У позначеннях тип індексу задає спосіб. Задачі відрізняються між собою потужностями множин M_о, M^о. Отримані внаслідок розв'язування задачі лінійного розміщення (4) номери позицій лінійок L_i і L^j, які закріплені за макромоделями M_i та M^j, вказують на номер стовпця і рядка, до яких належать елементи цих макромоделей.

Розроблено метод розміщення елементів схеми в тривимірному просторі, що базується на формуванні макромоделей алгоритмами компонування при їх триразовому перетині. У тривимірному випадку компоненти - макромоделі задовольняють рівняння

( М_і ) ( М^j ) ( Мs ) = Е, (5)

де макромоделі отримані за різними правилами поділу площин куба: М₀ = (М₁,…,М_n ) - xz, М⁰ = ( М¹,…,М^m ) - yz, М0=(М1,…,Мp) - xy . У перетині макромоделей з різних площин є різна кількість елементів

ijs М_і М^j Мl = М_ij, М_ij Е, s =|Мij|, s =1,2,... (6)

Графічно (5,6) зображається поступовим розрізом трьох площин і, відповідно, об'єму куба горизонтальними, вертикальними та поперечними площинами і накладання розбиттів.

У тривимірному випадку при накладанні макромоделей для визначення позиції кожного елемента множини Е в об'ємі куба розв'язуються три задачі призначення макромоделей на лінійках 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 тощо. Збільшення кількості елементів в усіх перетинах макромоделей зменшує кількість макромоделей в межах типів М_і, М^і , Мl.

Після розв'язування задач розміщення (7) на лінійках місця спільних елементів є визначеними з точністю до координат позицій, призначених макромоделям. Наприклад, для випадку 22 чотирьом спільним елементам призначені координати x_k, y_k , а для уточнення положення кожного елемента на осі ординат здійснюються перестановки з додатковими обчисленнями значень функції критерію (рис. 10). Реалізовані дві стратегії уточнення координат елементів з перетинів: 1) до них окремо застосовуються точні або наближені методи для знаходження оптимальних координат, 2) уточнюють координати в межах методів локального характеру для всього простору. Кількість невизначених груп (двійок, трійок, четвірок тощо)

k_n= | М₀ | | М⁰ | | М0 |,

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

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

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

Розроблені стратегії оптимізації результатів, отриманих на площині та у просторі методами накладання макромоделей. Наряду з процедурами повних перестановок елементів в обмеженому просторі, які застосовують на кінцевих етапах оптимізації, для просторих моделей (куб містить 8 елементів) розроблено методи ефективних перестановок, що реалізують мінімаксний принцип у виборі кандидатів та напрямів для перестановок, зменшуючи кількість обрахунків цільової функції. Складовою частиною цих методів є накладання макромоделей у мікропросторі. Цю групу методів застосовують на проміжному етапі при переході від методів конструктивних до ітераційних. Запропоновані неперервні колові та сферичні моделі простору пошуку екстремальних значень функції, які полягають у згортанні лінії чи площини навколо осей Ox , Oy, Oz чи по двох осях одночасно. Неперервні моделі простору надають методам локального характеру ознак глобальності за рахунок можливих перенесень елементів між фізично далеко розташованими позиціями. Побудова неперервних моделей здійснюється в просторі структур даних.

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

Розроблені методи реалізовані програмно, а їх тестування на багатьох прикладах показало, що показники якості розміщення (довжина провідників за інтегральними чи мінімаксними критеріями) кращі, ніж відомі для аналогічних задач і має алгоритмічну складність, що не перевищує квадратної.

У четвертому розділі сформульована задача реалізації міжелементних з'єднань на площині та у просторі як оптимізаційна екстремальна задача на графах: знайти в графі (на моделі ДТРП тощо) мінімальне зв'язувальне дерево T_ei*(W*(e_i),V(e_i)) (МЗД) для з'єднання вершин W*={W(e₁),W(e₂),..,W(e_s)} при виконанні умов мінімізації ряду функцій F_i (T*) = min F_i(T), що визначають якість дерева та обмежень. Запропоновані та проаналізовані моделі комутаційного простору (дискретного топологічного робочого поля - ДТРП) для побудови макроз'єднань. При переході до графової моделі простору з'єднання E представляються множиною вершин, які необхідно з'єднати. Критеріями якості побудованих дерев є функції сумарної чи максимальної довжин з'єднань, кількість кутів тощо. Розроблено методи побудови МЗД на основі принципу оптимального згортання контактів ланцюгів, який виступає керуванням для здійснення етапу макротрасування, незалежно від способу проведення фрагментів: лініями, променями чи хвильовим алгоритмом. В ієрархічному методі макротрасування використані поняття нечітких (розмитих) з'єднань на різних рівнях ієрархічного дерева згортання, які утворюються при об'єднанні контактів у кластери (блоки) і базується на факті, що для двох-трьох контактів ланцюга точний розв'язок завжди отримується. Критерієм для вибору найкращих пар вершин дерева Т_з для згортання є мінімальна відстань між ними у ортогональній чи евклідовій метриці, тобто

F_ij ^*= min L (i,j), i,jІ,

де відстань L (i,j) для кожного окремого випадку визначається за різними формулами. Розроблено паралельно-послідовну стратегію керування побудовою МЗД для почергової реалізації фрагментів груп ланцюгів із змінною кількістю ланцюгів у групі. Послідовна стратегія є частинним випадком, коли група містить один ланцюг. Керування паралельно-послідовним проведенням міжз'єднань здійснюється на основі побудови оптимального лісу згортання контактів і фрагментів міжз'єднань та відповідних їм блоків.

Для згортання вершин використано принцип побудови вільного дерева згортання, в якому насамперед об'єднуються найближчі елементи. Розроблені різні стратегії побудови фрагментів МЗД: проведення бінарних з'єднань, коли на кожному рівні блок розглядається як сукупність двох блоків нижчого рівня, пошук 3-арних з'єднань для розбиття на три блоки тощо. Збільшення арності задачі ускладнює її, але призводить до кращих значень цільової функції сумарної довжини. Розроблені стратегії ранжування ланцюгів та їх фрагментів з погляду їх розташування та відстаней між контактами для мінімізації завантаженості комутаційного простору. Обчислювальна складність методу визначається алгоритмом побудови дерева згортання (повний граф - O(n²) ) і складністю алгоритму побудови смуг невизначеності між блоками, який реалізований за допомогою алгебраїчних перетворень і хвильового алгоритму. Обчислювальна складність паралельно-послідовного макротрасування є більшою від послідовної стратегії за рахунок необхідності перерахунків відстаней між контактами і фрагментами в межах одного ланцюга, але не перевищує O(n²). Метод вимагає значного об'єму оперативної пам'яті, який зростає при зберіганні з'єднань багатьох ланцюгів одночасно.

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

Різні моделі ДТРП і керування кількістю граней у них спричиняють задачу побудови компромісної за точністю та часом побудови моделі. При побудові регулярних моделей ДТРП додатково до функції густини січень окремих каналів будується узагальнена функція густини як сума функцій густин окремих каналів F₀(j)= f_i(j) , де j - номер дискретного кроку поверхні. Оптимізаційна задача полягає у знаходженні такого розбиття на K_B рівних частин сумарної функції густини, щоб максимізувати кількість розрізаних бінарних відрізків. Для знаходження компромісного (з погляду значень K_B і кількості перетинів) розрізу каналів на рівні частини розроблені методи пошуку оптимального K*.

Розроблено універсальний метод призначення, що застосовується для знаходження фрагментів макро- і мікроз'єднань. Зміст задачі оптимального призначення полягає в знаходженні відображення ER, де E - множина елементів, R - множина ресурсів, за якого функції якості набувають екстремальних значень, наприклад, мінімізації довжини використаних горизонтальних магістралей, кількості міжшарових переходів тощо. Метод базується на сукупності моделей та алгоритмів їх опрацювання.

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

x_il x_i x_ir,

де x_il, x_ir - відповідно, ліва і права координати границь областей, оптимальних для проведення в них вертикальних фрагментів, x_i - дискретна змінна координати і-го вертикального фрагмента. Для формування цільової функції, що вказує на міру оптимальності координат призначення, приймається

| x_i - x_ir | , x_i > x_ir,

g_i(x_i) = | x_i - x_il | _, x_i < x_{il ,}

0 x_il x_i x_{ir .}

Сформульована задача: на множині дискретних значень координат переходів між каналами Q = (q₁, q₂,..., q_N) знайти координати, які мінімізують функцію

F =w₁ g₁(х₁)+ w₂g₂(х₂)+...+ w_ng_n(x_n) (8)

при виконанні обмежень

x _i x _j , і j; i ,j є 1...,,n. (8a)

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

Моделі багаторівневого призначення. Для двох суміжних каналів, тільки в позначених смугах координата призначення не впливає на загальну довжину горизонтальних відрізків. Поза смугами вона зростає лінійно з віддаленням від смуги. У дворівневому випадку розв'язування задачі (8) здійснюється для спільної границі каналів. Для багатоканального об'єднання залежно від кількості і розташування смуг оптимальності в каналах будується узагальнений канал і функція S(x_і) залежності сумарної довжини горизонтальних відрізків від координати призначення вертикального фрагмента. Функція набуває мінімального значення на певному проміжку, який приймається як смуга оптимальності в багаторівневій моделі для визначення границь в задачі (8). Реально переходи представляються окремими відрізками. Позначивши їх множиною R = ( R₁, R₂,..., R_m ), де R_і= (r_ii+1, r_ii+2,...,r_ik) - підмножина відрізків з і-го каналу до і+1, і+2,..., k-го каналів; m - кількість каналів та ввівши подібну множину вертикальних фрагментів E =(Е₁, Е₂,..., Е_m), де Е_і= (е_ii+1, е_ii+2,...,е_ik) (приклад зображено на рис. 18,б з посортованими за довжиною і початковим рівнем елементами), необхідно розв'язати задачу оптимального призначення фрагментів трас E на множину ресурсів R. Елементи множини E розташовані на осі Ох згідно з координатами, отриманими після розв'язування задачі (6) для узагальненого каналу або для двох каналів як однієї моделі на основі смуг окремих каналів.