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

АЛГОРИТМИ Трасування

 

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

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

 

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

 

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

1) Хвильові алгоритми, засновані на ідеях Лі та розроблені Ю.Л.

Зіманом і Г.Г. Рябовим. Дані алгоритми одержали широке поширення в існуючих САПР, оскільки вони дозволяють легко враховувати технологічну специфіку друкованого монтажу зі своєю сукупністю конструктивних обмежень, Ці алгоритми завжди гарантують побудова траси, якщо шлях для неї існує;

 

2) ортогональні алгоритми, що володіють більшу швидкодію, ніж алгоритми першої групи. Реалізація їх на ЕОМ вимагає в 75-100 разів менше обчислень у порівнянні з хвильовими алгоритмами. Такі алгоритми застосовують при проектуванні друкованих плат з наскрізними металізованими отворами. Недоліки цієї групи алгоритмів пов'язані з отриманням великої кількості переходів з шару на шар, відсутністю 100%-ої гарантії проведення трас, великим числом що йдуть паралельно провідників;

 

3) Алгоритми евристичного типу. Ці алгоритми частково засновані на евристичному прийомі пошуку шляху в лабіринті. При цьому кожне підключення проводиться за найкоротшим шляхом, обходячи що зустрічаються на шляху перешкоди.

 

Хвильовий алгоритм Лі

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

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

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

,де Pk і Pk-1 - ваги осередків k-го і (k-1)-го фронтів; - ваговафункція, що є показником якості проведення шляху, кожен параметрякої характеризує шлях з точки зору одного з критеріївякості (довжини шляху, числа перетинів і т.п.). На Pk накладають однеобмеження - ваги осередків попередніх фронтів не повинні бути більше вагосередків наступних фронтів. Фронт поширюється тільки на сусідніосередки, які мають з осередками попереднього фронту або загальну сторону,або хоча б одну спільну точку. Процес поширення хвилі триваєдо тих пір, поки її розширюється фронт не досягне приймача або на?-мукроці не знайдеться жодної вільної комірки, яка могла б бути включенав черговий фронт, що відповідає випадку неможливості проведення трасипри заданих обмеженнях.

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

Щоб виключити невизначеність при проведенні шляху для випадку,коли кілька осередків мають однаковий мінімальну вагу, вводять поняттяподорожніх координат, які задають пріоритет проведення траси. Кожненапрям кодують двійковим числом за mod q, де q - числопереглядаються сусідніх осередків. При цьому чим більш переважно те чиінший напрямок, тим менший числовий код воно має. Наприклад, якщозадатися пріоритетним порядком проведення шляху зверху, праворуч, знизу ізліва, то коди відповідних дорожніх координат будуть 00, 01, 10, і 11.
Приписаних колійних координат виробляють на етапі розповсюдження хвилі. Припроведенні шляху рух від осередку до осередку здійснюють за дорожнімикоординатах.

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

Модифікації алгоритму Лі

 

Метод зустрічної хвилі

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

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

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

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

 

Променевий алгоритм трасування

В даному алгоритмі, запропонованим Л.Б. Абрайтісом, вибір комірок длявизначення шляху сполучаються між точками A і B виробляють за заздалегідьзаданих напрямках, подібним променів. Це дозволяє скоротити числопереглядаються алгоритмом осередків, а отже, і час на аналіз ікодування їхнього стану, однак приводить до зниження ймовірності знаходженняшляху складної конфігурації, і ускладнює облік конструктивних вимог дотехнології друкованої плати.

Робота алгоритму полягає в наступному. Здається число променів,розповсюджуваних з точок A і B, а також порядок присвоєння подорожніхкоординат (звичайно число променів для кожної комірки-джерела приймаєтьсяоднаковим). Промені A (1), A (2),..., A (n) і B (1), B (2),..., B (n) вважаютьоднойменними, якщо вони розповсюджуються з однойменних джерел A або B.
Промені A (i) і B (i) є різнойменними по відношенню один до одного.
Поширення променів виробляють одночасно з обох джерел дозустрічі двох різнойменних променів в деякій комірці C. Шлях проводиться зосередку C і проходить через осередки, за якими поширювалися промені.

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

Промені:
A (1): вгору, вліво
A (2): вліво, вгору
B (1): вниз, праворуч
B (2): вправо, вниз
На другому кроці промінь B (1) виявляється заблокованим, а на четвертому кроціблокується і промінь A (2). Промені A (1) і B (2) зустрічаються в комірці C на восьмомукроці.

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

використаної літератури