Канальні алгоритми трасування

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

Реалізація канального алгоритму передбачає виконання двох процедур:

1. Розподіл з'єднань каналами з урахуванням їх оптимального завантаження;

2. Оптимізація розташування з'єднань на магістралях каналів.

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

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

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

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

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

Перший алгоритм канального трасування (так звана «класична» постановка задачі, яка не допускає зламу або переходу горизонтального сегмента з'єднання з магістралі на магістраль) було запропоновано Хашимото і Стівенсом в 1971 (A. Hashimoto, J. Stivens). Алгоритм отримав назву «алгоритм лівого кінця».

Нехай задано кілька відрізків, розподілених в одному каналіS=M1, M2, …, Mn>. Два відрізки вважаються такими, що перетинаються, якщоMiÇMj¹ Æ. Графом інтервалівG(S) множиниSназивається граф, вершинами якого є відрізкиMi, а ребра відповідають перетинуMiіMj.Тепер завдання розподілу з'єднань магістралями зводиться до мінімальної розмальовки графа інтервалівG(S). При цьому пофарбовані одним кольором відрізки розміщуються на одній магістралі, а хроматичне число графа інтервалів – необхідне проведення з'єднань число магістралей.

Алгоритм «лівого кінця» є простим алгоритмом розмальовки графа.

Алгоритм полягає в наступному:

1. Упорядкувати відрізки покоординатам лівого кінця;

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

приклад. Дано відрізки, координати яких отримані на першому етапі. Будуємо граф інтервалів (рис. 7.40).

М1
М2
М3
М4
М5
М6
М1
М2
М6
М4
М3
М5

Малюнок 7.40. Відрізки з'єднань та граф інтервалівG(S)

Фарбуємо вершинуM4у перший колір (поміщаємо на першу магістраль). ВершинаM1суміжна вершиніM4, фарбуємо її у другий колір (поміщаємо на другу магістраль). ВершинаM2суміжна вершинамM4таM1, фарбуємо її в третій колір (поміщаємо на третю магістраль). ВершинаM3не суміжна вершиніM4, фарбуємо її в перший колір (поміщаємо на першу магістраль). ВершинаM6суміжна вершиніM4і не суміжна вершиніM1, фарбуємо її у другий колір (поміщаємо на другу магістраль). ВершинаM5суміжна вершинамM3таM6, і не суміжна вершиніM2, фарбуємо її в третій колір (поміщаємо на третю магістраль). Результати розподілу відрізків магістралями наведено на рис. 7.41 (а).

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

М1
М2
М3
М4
М5
М6
а
а
b
b
c
c
b
c
a

а
б
в
Малюнок 7.41. Розподіл провідників у каналі (а); горизонтальний канал (б); граф вертикальних обмежень (в)

Розподіл провідників магістралями з урахуванням графа вертикальних обмежень показано на рис. 7.42 (а). Розподіл не є оптимальним. Оптимальний розподіл, отриманий за допомогою «алгоритму правого кінця», показано на рис. 7.42 (б).

б
а
а
а
b
b
c
c
а
а
b
b
c
c

Малюнок 7.42. Розподіл з'єднань за «алгоритмом лівого кінця» (а) та оптимальним розподілом по «алгоритму правого кінця» (б)

Д.М. Дойч (D.N. Deutsch) запропонував алгоритм «Dogleg» (дослівно –собача лапа, різке викривлення), що дозволяє будувати ламану лінію. Алгоритм складається із двох частин:

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

2. Починаючи з правого з'єднання, вони спрямовуються для зменшення числа міжшарових переходів.

На рис. 7.43 (а) показано контакти, які необхідно з'єднати. На рис. 7.43 (б) наведено граф вертикальних обмежень. На рис. 7.43.(в) показаний результат першого етапу алгоритму, але в рис. 7.43 (г) – остаточний результат. Вдалося спрямувати лише з'єднанняd – d.

г
в
а
а
b
b
b
c
c
c
d
d
c
a
b
d
а
а
b
b
b
c
c
c
d
d
а
а
b
b
b
c
c
c
d
d
а
б

Малюнок 7.43. Розподіл з'єднань магістралями алгоритмом «Dogleg»

Хороший результат дає модифікація алгоритму «Dogleg», що полягає у поперемінному використанні «алгоритмів лівого (для верхніх магістралей) та правого (для нижніх) кінців».

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

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

а
а
b
b
а
b
а''””’
а'
а
а
b
b
а''””’
а'
а
а
b
b
б
в

Малюнок 7.44. Обробка тупикової ситуації алгоритмом Dogleg

Низькатимчасова та просторова складність алгоритмів канального трасування робить їх найбільш прийнятними в САПР електронних систем, де вирішуються завдання величезної розмірності (кілька мільйонів транзисторів).

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

Перевагами канальних алгоритмів є:

1. Швидкодія (на один - два порядки вище, ніж у хвильових алгоритмів);

2. Менша витрата оперативної пам'яті ЕОМ (зберігається в повному обсязі ДРП, лише дискрети одного каналу);

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

Недоліком канальних алгоритмів і те, що вони менш універсальні, використовуються лише регулярних конструкцій.