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

В общем случае итерации повторяются до тех пор, пока не будут удалены все циклы. Граф, рассмотренный в нашем примере, был приведен к ациклическому виду за один шаг. После этого была решена задача укладки горизонтальных сегментов в канале. Результат канальной трассировки показан на рисунке 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.