Трасування в комутаційному блоці на основі генетичних
процедур
Б. К. Лебедєв
Вступ
Зважаючи грандіозної складності трасування НВІС розбивається на
два етапи: глобальна і детальна. При глобальної трасуванні вирішується два
задачі: розбивка комутаційного поля на області та розподіл сполук за
областям. Детальна трасування полягає в проектуванні топології з'єднань
всередині областей. Традиційно комутаційне поле розбивається на два типи
областей: канал і комутаційний блок (switch box).
У класичній постановці комутаційний блок - це
прямокутна ділянка на всіх чотирьох сторонах якої розміщені в
фіксованих позиціях термінали (висновки). Термінали позначені цифрами --
номерами підключених до них ланцюгів. Завдання полягає в тому щоб зробити термінали
кожній ланцюга електрично зв'язними так, щоб ланцюга і перехідні отвори,
реалізують зв'язку, вписувалися в область трасування й задовольняли
конструктивним обмеженням.
Зазвичай проблема вирішується за додатково накладеними
обмеженнями, одним з яких є число шарів. У роботі розглядається двошарова
трасування.
Завдання трасування в обмеженій прямокутної області
є NP-повною. Тому
незважаючи на велику кількість розробок, проблема побудови ефективного трассіровщіка
є актуальною.
Більшість алгоритмів трасування в комутаційному блоці
грунтуються на евристики, що реалізують в тій чи іншій мірі ідею
послідовної трасування [1,2,3,4]. У процесі прокладки на кожному кроці
використовуються правила спрямовані на мінімізацію впливу прокладаються
ланцюги на невбитій. Проте повною мірою проекстраполіровать всі ситуації не
представляється можливим. Це призводить до необхідності додаткової
трасування. Основу цих алгоритмів складають два принципи: локальна
деформація, розрив частини з'єднань і перетрассіровка їх різними методами
[2]. Але на жаль, і тут виникає проблема черговості перетрассіруемих
з'єднань. У зв'язку з цим інтерес представляють комбінаторні алгоритми,
оперують з усіма сполуками. Серед математичних методів забезпечують
Комбінаторний підхід до розв'язуваної задачі останнім часом найбільше
поширення набули методи моделювання відпалу та еволюційного
програмування. Особливий інтерес викликають генетичні алгоритми,
засновані на механізмах природної селекції та генетики [5,6].
У роботі запропоновані нові генетичні процедури для вирішення
завдання трасування в комутаційному блоці, що враховують знання про проблемної
області. Розроблено нові структури та
принципи кодування хромосом, модифіковані генетичні оператори, і структура
генетичного пошуку. Проведено експериментальні дослідження.
1. Формулювання завдання,
основні терміни і позначення
Дамо формальний опис завдання трасування комутаційного
блоку (ЗТКБ). Дано: верхній ряд контактів К1 = (к1i) і нижній ряд контактів К2 = (к2i), пронумеровані зліва направо, лівий ряд контактів К3 = (к3i) і правий ряд
контактів К4 = (к4i), пронумеровані
зверху вниз, і розташовані на сторонах прямокутника. До них відповідно
підходять безлічі ланцюгів N1 = (n1i), N2 = (n2i), N3 = (n3i), N4 = (n4i), N = N1
