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

У роботі розв'язана оптимізаційна задача за допомогою моделі у вигляді зважених орграфів G, які відображають ресурси так: множині каналів відповідає множина вершин X, множині ресурсів R - множина дуг, координаті ресурсу - вага дуги в орієнтованому графі. Сумарне алгоритмічне забезпечення багаторівневої моделі складається з методів побудови еквівалентних однорівневих моделей для всіх фрагментів у багатоканальному об'єднанні, знаходження координат призначення на множині умовних переходів узагальненого каналу в задачі (8), перетворення координат умовних переходів у послідовність відрізків реальних переходів множини R. Для розв'язування задачі призначення вертикальному фрагмента e_ij в графі G знаходиться шлях між і-ю та j-ю вершинами, оптимальний з погляду співвідношення умовних і реальних координат, кількості переходів між магістралями, довжини горизонтальних з'єднань тощо. Оптимізація здійснюється методом поступок: пошук оптимального розв'язку згідно з найважливішим критерієм, далі в межах певної поступки в головному критерії знаходиться оптимальний розв'язок за другим критерієм і т.д.

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

У п'ятому розділі розглянуті етапні задачі мікротрасування в каналі як пакування відрізків на ресурсах каналу без обмежень та з обмеженнями, які виникають при врахуванні бічних контактів. Сформульовано задачу : знайти відображення ВR , за якого відрізки В не перетинаються в межах однієї магістралі, а кількість використаних магістралей є мінімальною. Додатковими критеріями оптимальності є функції, які вказують на довжину вертикaльних складових з`єднань, кількість поворотів тощо. Для розв`язування поставленої задачі розроблено метод пакування на основі пошуку максимально можливих шляхів у графі вертикальних конфліктів G_V, тобто перетворення його до вигляду G_VS, в якому задано порядок укладання, як мінімум, в межах максимального шляху. Посортовані відрізки згідно з початковою координатою і послідовність вершин у шляхах є керуючою інформацією для роботи основної частини алгоритму, а саме: реалізації стратегії управління або визначення порядку укладання відрізків на магістралі. Знайдені максимальні шляхи не дають повної інформації для цього. Додатковою керуючою інформацією для укладання відрізків є ребра графа горизонтальної безконфліктності G_G, наведені між вершинами різних максимальних шляхів (в межах шляхів головними керуючими є дуги підпорядкованості контактів) та дуги графа G_V , що не ввійшли у максимальні шляхи. Розроблено стратегії призначення відрізків: послідовна, повних підграфів та режим повернень. Кількість шляхів в ієрархічному дереві пошуку - це можливі варіанти укладання відрізків. Пошук оптимального варіанта відбувається обходом дерева можливих розв'язків. У зв'язку з побудовою дерева перпендикулярно до магістралей і накладеними обмеженнями вертикальних та горизонтальних конфліктів ширина та глибина дерева пошуку не набувають великих значень, що робить можливим перебір всіх варіантів пакування для знаходження оптимального.

Для збільшення процента реалізованих з'єднань застосовується принцип “плавання” контактів. Розроблено спосіб управління топологічною ситуацією в каналі і попереднього призначення незакріплених контактів на горизонтальних сторонах каналу. Використання моделі плаваючих контактів дозволяє одночасно розв'язувати задачі які, звичайно, розв'язуються окремо: призначення вертикальних фрагментів дерев на вертикальні магістралі пластини; побудова з'єднань у каналі; призначення периферійних комірок і ланцюгів на їх контакти. Формулювання задачі призначення контактів на позиції у моделі каналу з “плаваючими” контактами таке: множину К_н незакріплених контактів призначити на множину Z вільних позицій

К_н Z так, щоб мінімізувати сумарну довжину з'єднань у каналі, кількість конфліктів в графі вертикальних конфліктів та довжину максимального шляху у графі G_V. Задача доповнюється обмеженнями, пов'язаними з утворенням циклів в графі G_V, рівномірним розподілом вільних позицій для контактів, а також іншими похідними обмеженнями. Врахування всіх критеріїв і обмежень ускладнює задачу, збільшує час для її розв'язання. Розроблено методи розв'язування задачі з оптимізацією основних показників, а саме: довжини з'єднань і кількості конфліктів на моделі каналу. Результатом роботи методів призначення є координати кортежів верхніх і нижніх контактів грані, які відповідають оптимальним значенням цільових функцій. Вони не є оптимальними в глобальному сенсі і покращуються процедурами локальної оптимізації. Реалізовано комбінаторний метод, в якому генеруються перестановки верхніх чи нижніх контактів, підраховується функція мети для кожного випадку і найкраще значення запам'ятовується. Факторіальна складність зменшена почастинним розв'язуванням задачі. Розроблено метод цілеспрямованого зменшення конфліктів, циклів і довжини шляхів в графі конфліктів грані чи каналу, який на етапі призначення знімає задачу знаходження конфігурації з'єднань. Завдання розробленого методу полягає в знаходженні контактів на верхній та нижній границі грані, які треба пересунути на інші позиції, щоб зменшити довжину максимального шляху в графі G_V; розбити цикли, якщо вони можливі; зменшити кількість конфліктів, тобто кількість дуг в графі G_V.

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

Стратегії послідовного вибору бічних контактів є керованими вибором бічних контактів не згідно з номерами магістралі їх розміщення чи стратегії, а на основі вагових коефіцієнтів пріоритетів контактів, що входять в шляхи графа вертикальних конфліктів. Описані принципи покладені в основу алгоритмів пакування. Розроблено декілька динамічних варіантів методів: односторонній з призначенням, односторонній з уточненням, мікротрасування перемикача, універсальний двосторонній з уточненням. Обчислювальна складність алгоритмів не перевищує О (n²), де n - кількість бічних контактів. На практиці, завдяки підготовці інформації про пари контактів до початку роботи основного алгоритму, його складність прямує до О(n)ч О(Nlog₂N ). Порівняння результатів роботи розроблених методів на відомих прикладах підтверджує те, що в NP-складних задачах незакріпленість проміжних розв'язків і гнучкість процесу їх отримання дозволяють отримати більш якісні результати трасування каналів та перемикачів, які в цьому випадку визначаються двома основними факторами: якістю призначення кінцевих координат відрізків бічних контактів і стратегією призначення основних з'єднувальних відрізків.

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

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

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

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

ОCНОВНІ РЕЗУЛЬТАТИ РОБОТИ

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

Розроблені та класифіковані алгоритми побудови дерева оптимального згортання схеми з врахуванням часових та якісних характеристик. Визначено, що складність алгоритмів залежить від формулювання задачі згортання, параметрів схеми та від прийнятої стратегії згортання: універсальної, суміжних пар чи мінімаксної і коливається від квадратної до O(nlog₂n).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

СПИСОК ОПУБЛІКОВАНИХ РОБІТ ЗА ТЕМОЮ ДИСЕРТАЦІЇ