Реферат: Алгоритм удаления циклов в графе вертикальных ограничений задачи трассировки многослойного канала
a> 0, b³ 0, g³ 0 - коэффициенты важности перечисленных параметров, которые выбираются пользователем в зависимости от конкретной задачи.
Определенная таким образом функция выбора позволяет расщеплять большее количество циклов за одну итерацию, выбирать для доглега цепи меньшей ширины, а также не усложнять конфигурацию приоритетных цепей, например цепей земли/питания.
На шаге 3 для найденной критической вершины a строится расширенный граф вертикальных ограничений (Expanded Vertical Constraints Graph) следующего вида: EVCGa = ((X \ a)?Ka, Ua), где X - множество вершин исходного VCG, a - критическая вершина VCG, Ka - множество новых вершин, образованных контактами сегмента, соответствующего вершине a, Ua - множество ориентированных ребер, соединяющих новые вершины с другими вершинами VCG. Такой граф содержит более детальную информации о циклах, проходящих через критическую вершину. На рисунке 3 приведен пример EVCGa для канала, показанного на рисунке 2.
На шаге 4 строится локальный граф контактов для критической вершины a (Local Pin Graph): LPGa = (Ka, Va), где Va - множество неориентированных ребер. Ребро vi?Va соединяет вершины km, kn? Ka, если в графе EVCGa существует путь между вершинами km и kn. Локальный граф для вершины a изображен на рисунке 3.
Каждое ребро локального графа контактов соответствует как минимум одному циклу, проходящему через критическую вершину VCG, и указывает на контакты, образующие этот цикл. Таким образом, если ребро существует между парой вершин локального графа, то соответствующие им контакты должны быть назначены в различные группы при расщеплении вершины VCG. В этом случае соответствующие ребру циклы будут удалены.
Возможен случай, когда в локальном графе появляется петля. Петля не может быть удалена путем разбиения контактов на группы, так как контакт не может быть расщеплен на части. В этом случае проходящий через вершину цикл не может быть удален путем расщепления только данной вершины.
Использование локального графа контактов позволяет свести задачу разбиения контактов на группы к задаче раскраски неориентированного графа. Необходимо раскрасить локальный граф контактов в минимальное число цветов так, чтобы вершины, соединенные ребром, оказались раскрашены в разные цвета. Раскраска графа в минимальное число цветов будет соответствовать разбиению сегмента на минимальное число частей, достаточное для удаления циклов в VCG. Необходимо отметить, что, несмотря на сложность задачи раскраски произвольного графа в минимальное число цветов, для данного случая задача всегда может быть решена методом полного перебора, так как размерность локального графа контактов определяется числом контактов в цепи и для сигнальных цепей обычно не превышает 5.
Если локальный граф контактов не содержит нечетных циклов, то, по теореме Кенига [6], он может быть раскрашен в два цвета. В этом случае достаточно бинарного доглега. В остальных случаях требуется мульти-доглег. Пример раскраски локального графа контактов для вершины а показан на рисунке 3.
Граф вертикальных ограничений после одной процедуры мульти-доглега изображен на рисунке 3. Критическая вершина a расщеплена на три новые вершины (a’, a’’, a’’’) в соответствии с раскраской графа LPGa , а ребра, относящиеся к a, построены заново для трех новых вершин.
Рис.3.
Чтобы завершить процедуру мульти-доглега, необходимо найти место для вертикального соединения между новыми сегментами. Эта задача решается на шаге 7 в соответствии с [5].
В общем случае итерации повторяются до тех пор, пока не будут удалены все циклы. Граф, рассмотренный в нашем примере, был приведен к ациклическому виду за один шаг. После этого была решена задача укладки горизонтальных сегментов в канале. Результат канальной трассировки показан на рисунке 4. Необходимо отметить, что это решение не удается получить ранее известными методами.
Рис.4.
Алгоритм мульти-доглега был реализован на языке С++. На рис. 5 представлен пример канала, который является сложным для задачи удаления циклов. Контакты фиксированы на верхней и нижней и упорядочены на левой и правой сторонах, VCG содержит 33 цикла. Алгоритм мульти-доглега удаляет циклы в этом примере за 9 итераций.
Рис.5.Трассировка сложного примера
Разработанный алгоритм приведения VCG к ациклическому виду обеспечивает, в отличие от известных алгоритмов, трассировку многослойных каналов с контактами, расположенными на любой стороне и в любом коммутационном слое, что является в настоящее время необходимым технологическим условием применения САПР СБИС.
Список литературы
A.Hashimoto and J.Stivens. “Wire routing by optimization channel assignment within large apertures.” Proc. Of the 8th Design automation workshop, pp. 155-163, 1971.
Deutsch D.N. “A Dogleg Channel Router” in Proc. 13th Design Automat. Conf. June 1976, pp. 425-433.
T.Yoshimura, E. S. Kuh “Efficient algorithm for channel routing”, IEEE Transactions on Computer-Aided Design, CAD-1(1):25-30, January 1982.
H.H.Chen, E. Kuh “Glitter: A gridless variable-width channel routing”, IEEE Transactions on Computer-Aided Design, CAD-5(4):459-465, 1986.
Bryan Preas “Channel Routing With Non-Terminal Doglegs”, Proc. European Design Automation Conference (EDAC), March 1990, pp. 451-458.
Берж К. “Теория графов и ее применения”, Иностранная Литература, Москва, 1962.