Алгоритм удаления циклов в графе вертикальных ограничений задачи трассировки многослойного канала

А.М. Марченко, А.П. Плис

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

Одним из важных этапов автоматизированного проектирования топологии СБИС является трассировка каналов. Каналом называется односвязная прямоугольная область на поверхности кристалла, предназначенная для соединения контактов, принадлежащих одной и той же цепи. В первой постановке задачи контакты располагались на двух противоположных сторонах канала, а трассировка была разрешена в двух коммутационных слоях. При этом в одном слое размещались горизонтальные сегменты соединений, а в другом - вертикальные. Такой канал называется 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.

Если в канале существуют контакты, расположенные на боковых сторонах, то порядок их расположения также отражается в графе дополнительными ребрами. На рисунке 2 приведен пример канала, содержащего четыре цепи a, b, c, d с контактами на боковых сторонах, и соответствующий граф вертикальных ограничений.

Рис. 2.

Задача приведения VCG к ациклическому виду (задача 2) может быть сформулирована следующим образом: используя информацию о цепях в канале и о графе вертикальных ограничений, так изменить конфигурацию  цепей, чтобы соответствующий VCG не имел циклов.

Основная идея, положенная в основу алгоритмов решения этой задачи, состоит в расщеплении вершины графа, которая участвует в создании цикла, на две или более части. Это соответствует разделению горизонтального сегмента на два или более новых сегмента. Такие механизмы были предложены Дойчем [2] (терминальный доглег) и Прессом [5] (нетерминальный доглег).

Эти варианты доглега отличаются друг от друга способами перераспределения контактов горизонтального сегмента между новыми сегментами. Местоположение контактов определяет существование и ориентацию ребер между соответствующими вершинами VCG, поэтому метод разделения контактов на группы в наибольшей степени влияет на успех процедуры удаления циклов. При терминальном доглеге контакты делятся по признаку левый - правый относительно контакта, по которому происходит разбиение. При этом в цепи может появиться несколько горизонтальных сегментов, но нет гарантии удаления циклов.

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

Наличие в канале более двух коммутационных слоев и контактов на боковых сторонах приводит к тому, что контакт может порождать в VCG входящие и выходящие ребра одновременно. В этом случае разделения контактов на верхние и нижние недостаточно и для успешного разбиения вершины требуется дополнительный анализ графа и, возможно, многократный (мульти-) доглег. В данной статье предлагается алгоритм мульти-доглега, который способен эффективно расщеплять вершины в такой ситуации. Он состоит из следующих шагов:

1. Если в VCG нет циклов либо уже рассмотрены все его вершины,  то завершить работу алгоритма.

2. Найти критическую вершину в VCG, выбирая среди еще не рассмотренных вершин.

3. Построить расширенный граф вертикальных ограничений.

4. Построить локальный граф контактов. Если в локальном графе  контактов нет петель, то раскрасить его в минимальное число  цветов, иначе вернуться на шаг 1.

Поделитесь этой записью или добавьте в закладки