Алгоритм канального трасування

Алгоритм канального трасування (англ. Channel router) — різновид алгоритмів трасування для інтегральних схем. Використовується, як правило, для плат з двома шарами провідників, забезпечує з'єднання контактів на верхній і нижній частині каналу. При числі шарів понад два в окремі шари виділяються доріжки живлення та «землі».

«Проблеми маршрутизації»: з'єднання контактів 1-1, 2-2 та 3-3 не можуть бути здійснені в одному шарі

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

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

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

В порівнянні з популярним алгоритмом Лі алгоритм канального трасування характеризується значно меншим часом обчислень (у 70 — 100 разів).

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

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

Примітки

1. Генетический алгоритм для трассировки двухслойных каналов^{[недоступне посилання з червня 2019]} (рос.)

Посилання

• (англ.)