Ліквідація вертикальних конфліктів межз'єднань
в каналі перед трасуванням
А.В. Мухлаев, С.Н.
Щеглов, М.Д. Сєченов
Вступ
Низька тимчасова і
просторова складність алгоритмів канального трасування робить їх найбільш
прийнятними в САПР електронних систем, де вирішуються завдання величезною розмірності
(кілька мільйонів транзисторів). Вказана обставина зумовило підвищений
інтерес розробників САПР до групи канальних алгоритмів і, як наслідок,
велика кількість різних типів канальних трассіровщіков.
Найбільшу увагу
дослідників традиційно привертала група канальних алгоритмів, що відносяться
до безізломним канальним трассіровщіка. Детальніше зупинимося на зазначеній
групі алгоритмів і введемо деякі основні поняття, тому що безізломние
канальні трассіровщіка найбільш прийнятні в
наступним причинах:
- дозволяють отримувати
вирішення найбільш швидко;
- добре апробовані і
застосовуються на практиці;
- досить якісно
і ефективно вирішують завдання трасування в двосторонньому каналі.
1.
Класифікація, критерії та постановка задачі канальної трасування
З огляду на те, що завдання
канальної трасування в зводиться до задачі
трасування горизонтального каналу, зверху і знизу обмеженого такими, що підлягають
з'єднанню контактами, запишемо формальну постановку завдання і дамо
традиційні визначення щільності і графа вертикальних обмежень (ГВО) (рис.
1).
Нехай задана декартова система
координат і на осі Х с ша-гом n відкладені точки Pl1, Pl2, ..., Pln, що утворюють кортеж B і
відповідні нижньому ряду контактів горизонтального каналу, а на деякій
лінії mi (лінії mj відкладаються з кроком b),
паралельної осі Х відкладені точки Pt1, Pt2, ..., Ptn утворюють кортеж Т і
відповідні верхнім контактам горізонтaльного каналу.
Виділимо підмножини Plij, Ptij, j = 1, f, i = 1, f, Plj, Pti
