Ликвидация вертикальных конфликтов межсоединений в канале перед трассировкой
    А.В. Мухлаев, С.Н. Щеглов, М.Д. Сеченов Введение
    Низкая временная и пространственная сложность алгоритмов канальной трассировки делает их наиболее приемлемыми в САПР электронных систем, где решаются задачи огромной размерности (несколько миллионов транзисторов). Указанное обстоятельство обусловило повышенный интерес разработчиков САПР к группе канальных алгоритмов и, как следствие, большое число различных типов канальных трассировщиков.
    Наибольшее внимание исследователей традиционно привлекала группа канальных алгоритмов, относящихся к безизломным канальным трассировщикам. Подробнее остановимся на указанной группе алгоритмов и введем некоторые основные понятия, так как безизломные канальные трассировщики наиболее приемлемы в последующим причинам:
    - позволяют получать решения наиболее быстро ;
    - хорошо апробированы и применяются на практике ;
    - достаточно качественно и эффективно решают задачу трассировки в двустороннем канале. 1. Классификация, критерии и постановка задачи канальной трассировки
    Ввиду того, что задача канальной трассировки в сводится к задаче трассировки горизонтального канала, сверху и снизу ограниченного подлежащими соединению контактами, запишем формальную постановку задачи и дадим традиционные определения плотности и графа вертикальных ограничений (ГВО) (рис. 1).
    Пусть задана декартова система координат и на оси Х с ша-гом n отложены точки Pl1, Pl2, ...,Pln , образующие кортеж B и соответствующие нижнему ряду контактов горизонтального канала, а на некоторой линии mi (линии mj откладываются с шагом b ), параллельной оси Х отложены точки Pt1, Pt2, ...,Ptn образующие кортеж Т и соответствующие верхним контактам горизонтaльного канала.
    
    Выделим подмножества Plij,Ptij,j=1,f,i=1,f,Plj,Pti?0}, каждое из которых составлено из Plj и Pti равных между собой, т.е. соответствующих одной цепи (f- число цепей). На их основе сформируем множество отрезков Q={q1,q2,...,qn}левые координаты которых равны минимальной координате Plj?Pti из соответствующего подмножеcтва Pi-Xq1i=min Хрi, а правые координаты-максимальной координате P1j?Ptj-Xq2i=maxXpi
    Необходимо распределить qf отрезков по магистралям таким образом, чтобы требуемое для трассировки число магистралей было минимально: mk?min и выполнялось ограничение (1)
    ?(i,j)=1,f:q1*nqj=? ( 1)
    а также ограничения, задаваемые с помощью графа вертикальных ограничений (ГВО), множество вершин которого соответствует Pi,j=1,f ,т.е. соответствует множеству цепей, а две его вершины Pi и Pj соединяются ориентированным ребром, что означает принудительное расположение отрезка qi выше, чем qj в том случае, если
    
    ?Ptij?T==> Ptij? Plij?B
    
    Следует отметить, что условие (1) несомненно приоритетно по сравнению с другими критериями трассировки (см. рис. 1), однако, может носить и аддитивный и мультипликативный характер. Отметим, что плотность Ui колонки i канала будем называть число горизонтальных сегментов ?qi , пересекающих i ко-лонку. Максимальной плотностью Umax назовем Ui :
    j=1,n
    Широко известны и применяются на практике алгоритмы "Левого края" и раскраски графа ограничений комбинаторные, дающие решения очень быстро. ............