Алгоритм удаления циклов в графе вертикальных ограничений задачи трассировки многослойного канала
    А.М. Марченко, А.П. Плис
    Рассмотрена проблема устранения циклических конфликтов при трассировке многослойного канала с любым расслоением при размещении контактов на любой стороне. Предложен алгоритм преобразования графа вертикальных ограничений к ациклическому виду путем расщепления его вершины на минимальное число новых вершин, который, в отличие от известных, использует информацию о контактах цепи, соответствующей выбранной вершине.
    Одним из важных этапов автоматизированного проектирования топологии СБИС является трассировка каналов. Каналом называется односвязная прямоугольная область на поверхности кристалла, предназначенная для соединения контактов, принадлежащих одной и той же цепи. В первой постановке задачи контакты располагались на двух противоположных сторонах канала, а трассировка была разрешена в двух коммутационных слоях. При этом в одном слое размещались горизонтальные сегменты соединений, а в другом - вертикальные. Такой канал называется HV - каналом [1].
    Качество решения задачи трассировки во многом определяет окончательный результат проектирования таких широко распространенных типов кристаллов, как тракты передачи данных, в которых каналы занимают около 20% общей площади. В канальной трассировке можно выделить три основные задачи:
    1. Построение графа вертикальных ограничений.
    2. Удаление циклов из графа вертикальных ограничений.
    3. Укладка горизонтальных сегментов в канале.
    Известно много эвристических алгоритмов канальной трассировки, которые эффективно решают задачу укладки горизонтальных сегментов при условии, что граф вертикальных ограничений не содержит циклов [2-4]. В то же время проблема построения графа вертикальных ограничений и удаления из него циклов изучена недостаточно полно. По мере совершенствования технологии изготовления СБИС проблема канальной трассировки постоянно усложняется. Например, увеличивается число коммутационных слоев, разрешается нарушать принятую модель расслоения соединений, контакты могут находиться на любой стороне канала и в любом слое. Перечисленные новые технологические требования приводят к усложнению графа вертикальных ограничений и превращают проблему его преобразования к ациклическому виду в крайне актуальную.
    Граф вертикальных ограничений (Vertical Constraints Graph) - это граф следующего вида: VCG=(X, U), где X - множество вершин, соответствующих горизонтальным сегментам цепей, U - множество ориентированных ребер. В случае двуслойного канала с принятым расслоением HV ребро ui(U соединяет вершины xm, xn( X, если существует пара противолежащих контактов, принадлежащих соответственно горизонтальным сегментам m, n, первый из которых расположен на верхней, а второй - на нижней сторонах канала.
    В многослойном канале возможны более сложные вертикальные ограничения. Если контакты расположены один над другим в соседних вертикальных слоях, что может иметь место в VVH канале, то порядок соответствующих им горизонтальных сегментов представляется в графе дополнительными ребрами так, как это показано на рисунке 1.
    
    Рис.1.
    Если в канале существуют контакты, расположенные на боковых сторонах, то порядок их расположения также отражается в графе дополнительными ребрами. ............