Разработка алгоритмов оценки и построения минимальных связывающих деревьев в САПР электронной аппаратуры тема диссертации и автореферата по ВАК РФ 05.13.12, кандидат технических наук Рыженко, Николай Владимирович

• Рыженко, Николай Владимирович
• кандидат технических наук
• 2004

Оглавление диссертации кандидат технических наук Рыженко, Николай Владимирович

Введение.

Глава 1. Определения и понятия.~.

1.1 Элементы теории графов, используемые в работе.

1.2 Место минимальных связывающих деревьев в задачах САПР электронной аппаратуры.

1.3 Задача Краскала-Прима.

1.4 Выводы.

Глава 2. Задача Штейнера.

2.1 Свойства деревьев Штейнера в прямоугольной метрике.

2.2 Точные алгоритмы построения деревьев Штейнера в прямоугольной метрике для задач ограниченной размерности.

2.3 Точные алгоритмы построения деревьев Штейнера в прямоугольной метрике для общего случая.

2.4 Приближенные алгоритмы построения деревьев Штейнера в прямоугольной метрике.;.'.

2.5 Алгоритм выборки перспективных дополнительных точек.

2.6 Оптимизация конфигурации дерева Штейнера.

2.7 Выводы.

Глава 3. Глобальная трассировка.

3.1 Постановка задачи и стандартная методика глобальной трассировки.i.

3.2 Первый этап Pathfinder. Построение леса деревьев с учетом текущего распределения цепей по ребрам глобального графа.".

3.3 Второй этап Pathfinder. Оптимизация распределения цепей по ребрам глобального графа.

3.4 Третий этап Pathfinder. Волновая трассировка.

3.5 Сравнение результатов Pathfinder с результатами других программ глобальной трассировки.

3.6 Выводы.

Введение диссертации (часть автореферата) на тему «Разработка алгоритмов оценки и построения минимальных связывающих деревьев в САПР электронной аппаратуры»

Актуальность работы.

Серьезной проблемой при проектировании электронных устройств на современных КМОП-технологиях становится дефицит трассировочного ресурса. К нему приводит несколько факторов. Увеличение плотности транзисторов при тех же технологических размерах проектируемого устройства обуславливает рост числа электрических соединений на характерную относительную единицу площади (площадь одного транзистора). С увеличением слоев металлизации трассировочный ресурс каждого слоя уменьшается, поскольку увеличивается суммарная площадь сквозных переходов между слоями. С увеличением электронного оборудования возникает проблема падения напряжения питания - для ее решения увеличивают число переходов с верхних слоев земли/питания до уровня логических элементов, что значительно снижает трассировочный ресурс промежуточных (сигнальных) слоев металлизации. Хотя уменьшение минимальной ширины электрических проводников соответствует аналогичному уменьшению размеров транзисторов, однако на практике проблема прогнозирования и учета электромиграции приводит к тому, что растет число проводников с шириной, большей минимально возможной. Аналогичное утверждение справедливо для минимального расстояния между проводниками - для уменьшения взаимной емкости и обеспечения помехоустойчивости расстояние между проводниками критических цепей делают большим, чем минимально возможное.

Негативный эффект дефицита трассировочного ресурса связан с тем, что в процессе трассировки проводники назначаются «в обход» загруженных областей, а не «напрямую». Это обстоятельство приводит к увеличению величин задержек в цепях связи и уменьшению быстродействия электронного устройства в целом. Более того, высокая плотность логических элементов и, следовательно, трасс в определенных областях СБИС может привести к тому, что детальная трассировка при недостаточно качественной глобальной трассировке вообще не сможет бьггь осуществлена. Возможно, придется увеличить общую площадь кристалла или использовать дополнительные слои металлизации. И первый, и второй вариант снижают эффективность смены технологии и уменьшают надежность производства СБИС.

Немаловажным фактором также является время работы используемых алгоритмов. Проблемы, возникающие при проектировании СБИС на современных технологиях, приводят к тому, что изменяется сам процесс проектирования: из однопроходного он становится итерационным. Различные этапы, и в том числе процедура глобальной трассиращси, повторяются неоднократно для достижения требуемых характеристик проектируемого устройства. Кроме того, высокая плотность трасс и общее увеличение числа электрических цепей приводят к тому, что итерационный процесс трассировки становится плохо сходящимся — значительно увеличивается общее число требуемых итераций.

Таким образом, актуальной становится разработка эффективных как с точки зрения качества получаемых решений, так и времени работы, методов глобальной трассировки компонентов СБИС в условиях дефицита трассировочного ресурса (высокой плотности трасс).

Цель исследования.

Целью диссертационной работы являлось создание компонента САПР для глобальной трассировки СБИС в условиях высокой плотности трасс.

В соответствии с целью диссертационной работы были определены следующие задачи:

1. Исследование существующих алгоритмов построения минимальных связывающих деревьев, методов глобальной трассировки СБИС и анализ эффективности их применения для современных и перспективных КМОП технологий.

2. Разработка алгоритмического обеспечения для глобальной трассировки СБИС в условиях высокой плотности трасс.

3. Разработка методов ускорения алгоритма последовательного введения дополнительных точек в дерево Краскала-Прима при сохранении качества получаемых решений исходного алгоритма.

4. Разработка компонента САПР для глобальной трассировки СБИС.

Научная новизна работы.

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

1. Разработка способов ускорения алгоритма последовательного введения дополнительных точек в дерево Краскала-Прима путем предварительной выборки перспективных точек Штейнера.

2. Разработка эффективных способов трансформации дерева Штейнера путем перестроения ограниченного множества ребер определенного типа. 3

3. Решение задачи построения начального леса деревьев Штейнера с учетом возможного распределения цепей по ребрам глобального графа.

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

Результаты, выносимые на защиту.

В процессе проведения исследований автором получены следующие результаты:

1. Конструктивный алгоритм предварительной выборки перспективных точек Штейнера для алгоритма последовательного введения дополнительных точек в дерево Краскала-Прима.

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

3. Вычислительная эффективность и качество получаемых решений предложенного комплекса алгоритмов доказана экспериментальными результатами, в том числе на тестовых примерах ESTEIN из стандартной библиотеки для задач исследования операций OR-Library.

4. Методика оценки и учета возможного распределения цепей по ребрам глобального графа при построении леса деревьев Штейнера.

5. Комплексный итерационный алгоритм оптимизации укладки цепей по ребрам глобального графа.

6. На основе предложенных алгоритмов создан компонент САПР Pathfinder для глобальной трассировки СБИС. Эффективность предложенных подходов подтверждена экспериментами на наборе тестовых примеров глобальной трассировки IBM, а также при сравнении с результатами работы программы глобальной трассировки Labyrinth.

Практическая ценность."

Основным практическим результатом проведенных исследований стало создание программы глобальной трассировки Pathfinder. Разработанное программное обеспечение входит в состав экспериментальной версии САПР научно-исследовательского проекта Ariadna.

Результаты исследований, выполненных по теме диссертации, нашли применение также в программном комплексе схемного редактора Endeavor компании Avanti в подсистеме автоматической визуализации электрических схем Make Schematic для создания схемы электрических соединений. Данное программное обеспечение используется на этапе логического проектирования и позволяет строить графическое изображение схемы по списку соединений элементов.

Личный вклад автора.

Предложенные в диссертации алгоритм выборки перспективных дополнительных точек, алгоритм трансформации дерева Штейнера с использованием ограниченного множества ребер определенного типа, а также метод использования алгоритмов построения леса деревьев с учетом возможного распределения цепей и метод использования алгоритмов оптимизации укладки цепей разработаны лично-автором. Программное обеспечение в течение ряда лет создавалось коллективом разработчиков (в ЗАО «МЦСТ») при личном участии автора. Компонент САПР Pathfinder для глобальной трассировки СБИС создан лично автором в рамках научно-исследовательского проекта Ariadna в течение 2003 года в Институте микропроцессорных вычислительных систем РАН.

Апробация.

Результаты диссертационной работы докладывались на всероссийских и вузовских научных конференциях:

1. ИрбенекВ. С., Рыженко Н. В. Применение алгоритмов построения и оценки длин минимальных связывающих деревьев в САПР электронной аппаратуры. Российская научная конференция «Экономические информационные системы на пороге 21 века», Москва, октябрь 1999.

2. Рыженко Н. В. Алгоритмы построения минимальных связывающих деревьев и га применение в САПР электронной аппаратуры. V Всероссийская научная конференция студентов и аспирантов, Таганрог, октябрь 2000.

3. Рыженко Н. В. Алгоритм щ> строения минимальных связывающих деревьев с дополнительными вершинами (деревьев Штейнера) для случая прямоугольной метрики. XLIV Научная конференция МФТИ, Москва, ноябрь 2001.

4. Рыженко Н. В. Алгоритм построения минимальных связывающих деревьев с дополнительными вершинами (деревьев Штейнера) для случая прямоугольной метрики. Юбилейная VIII Санкт-Петербургская международная конференция «Региональная информатика - 2002», Санкт-Петербург, ноябрь 2002.

5. Рыженко Н. В. Pathfinder. Конкурс исследовательских проектов в области проектирования интегральных схем, проходивший при поддержке МФТИ и представительства корпорации Intel в странах СНГ. Проект-победитель. 2003.

6. Рыженко Н. В. О подходах к решению задачи глобальной трассировки СБИС для случая большой плотности трасс. XLVI Научная конференция МФТИ, Москва, ноябрь 2003.

7. Рыженко Н. В. Программа глобальной трассировки Pathfinder. XXI Научно-техническая конференция в/ч 03425, Москва, декабрь 2003.

Кроме того, результаты диссертационной работы неоднократно докладывались . »и обсуждались на научно-технических семинарах ИМВС РАН и ЗАО «МЦСТ».

Публикации.

По теме диссертации опубликовано 5 работ:

1. ИрбенекВ. С., Рыженко Н. В. Применение алгоритмов построения и оценки длин минимальных связывающих деревьев в САПР электронной аппаратуры. В сборнике докладов российской научной конференции «Экономические информационные системы на пороге 21 века», Москва, 1999, стр. 361-366.

2. Рыженко Н. В. Алгоритм построения минимальных связывающих деревьев с дополнительными вершинами (деревьев Штейнера) для случая прямоугольной метрики. «Высокопроизводительные вычислительные системы и микропроцессоры», Выпуск 3, Труды ИМВС РАН, Москва, 2002, стр. 48-61.

3. Ирбенек В. С., Рыженко Н. В. Алгоритмы проектирования топологии электрических соединений в САПР электронной аппаратуры. «Зарубежная радиоэлектроника. Успехи современной радиоэлектроники», №7,2002, с. 71-79.

4. Рыжещсо Н. В. Задача построения дерева Штейнера для этапа глобальной трассировки. «Высокопроизводительные вычислительные системы и микропроцессоры», Выпуск 4, Труды ИМВС РАН, Москва, 2003, стр. 96-105.

5. Рыженко Н. В. Программа глобальной трассировки Pathfinder. В сборнике тезисов докладов XXI Научно-технической конференции в/ч 03425, Москва, декабрь 2003.

Структура и объем работы.

Диссертация состоит из введения, трех глав и заключения. Диссертация содержит 129 страниц текста, 63 иллюстрации, 29 таблиц (включая 7 таблиц приложения) и приложение на 8 листах. Список литературы и ссылок на ресурсы Internet насчитывает 61 наименование.

Заключение диссертации по теме «Системы автоматизации проектирования (по отраслям)», Рыженко, Николай Владимирович

3.6 Выводы.

Результаты, представленные в данной главе, можно сформулировать следующим образом:

1. Проанализированы основные проблемы глобальной трассировки для современных и перспективных технологий производства СБИС. Систематизированы основные факторы, приводящие к дефициту трассировочного ресурса. Проанализированы стандартная методика глобальной трассировки, ее актуальность и недостатки в условиях дефицита трассировочного ресурса и высокой плотности трасс.

2. Разработан комплекс алгоритмов и методов для глобальной трассировки СБИС в условиях повышенной плотности трасс.

3. Предложена методика оценки и учета возможного распределения цепей по ребрам глобального графа при построении леса деревьев Штейнера.

4. Предложен способ использования эластичности прямоугольных деревьев Штейнера для более качественного распределения цепей по ребрам глобального графа перед этапом перетрассировки.

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

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

7. На основе предложенных алгоритмов создан компонент САПР Pathfinder для глобальной трассировки СБИС. Разработанное программное обеспечение входит в состав экспериментальной версии САПР научно-исследовательского проекта Ariadna.

8. Проведено сравнение результатов работы Pathfinder и других программ глобальной трассировки Labyrinth и Chi на тестовых примерах IBM. Суммарная длина^рсех цепей у Pathfinder меньше аналогичного показателя у Labyrinth на 14-20 процентов, у Chi на 1-3 процента. Однако главный критерий - это суммарное переполнение глобального графа. Pathfinder устраняет его практически полностью, в то время как у Chi и Labyrinth этот показатель составляет несколько десятков и сотен единиц для каждого тестового примера.

Заключение. - —

Основной результат диссертационной работы заключается в разработке алгоритмической основы и создания компонента САПР для глобальной трассировки СБИС в условиях высокой плотности трасс.

В процессе исследования автором были получены следующие результаты:

1. Разработан алгоритм оценки перспективных дополнительных точек. Использование данного алгоритма позволяет в несколько раз сократить время работы алгоритма последовательного введения дополнительных точек в дерево Краскала-Прима.

2. Временные и качественные характеристики предложенного модифицированного алгоритма позволяют успешно использовать его в программе глобальной трассировки Pathfinder, входящей в состав экспериментальной версии САПР научно-исследовательского проекта Ariadna. Предложенный алгоритм нашел применение также в программном комплексе редактора Endeavor компании Avanti в подсистеме автоматической визуализации электрических схем Маке Schematic.

3. Разработан и практически реализован алгоритм динамического перестроения дерева Штейнера. Использование ограниченного множества ребер определенного типа позволяет за приемлемое время значительно улучшить качественные показатели модифицированного алгоритма. Экспериментально доказано, что процедура перестроения дерева использует лишь незначительную часть времени, сэкономленного за счет «отбраковки» неперспективных точек. Высокое качество получаемых решений подтверждено экспериментально на тестовых примерах ESTEIN из стандартной библиотеки OR-Library. Данный тестовый набор представляет собой совокупность задач с размерностью 10, 20, 30, 40, 50, 60, 70, 90, 100,250 и 500 точек - по 15 задач на каждую размерность. Отличие от оптимального значения в среднем для всех задач составляет 0.11 процента.

4. Разработан комплекс алгоритмов и методов для глобальной трассировки СБИС в условиях повышенной плотности трасс.

5. Предложенный комплекс алгоритмов реализован автором в программе глобальной трассировки Pathfinder, входящей в состав экспериментальной версии САПР научно-исследовательского проекта Ariadna.

116

6. Проведено сравнение результатов работы Pathfinder и других программами глобальной трассировки Labyrinth и Chi на тестовых примерах IBM. Суммарная длина всех цепей у Pathfinder меньше аналогичного показателя у Labyrinth на 14—20 процентов, у Chi на 1-3 процента. Однако главный критерий - это суммарное переполнение глобального графа. Pathfinder устраняет его практически полностью, в то время как у Chi и Labyrinth этот показатель составляет несколько десятков и сотен единиц для каждого тестового примера.

Благодарности.

Автор выражает искреннюю признательность научному руководителю Андрею Валентиновичу Жмурину за необходимое руководство и всемерную поддержку в подготовке и написании диссертационной работы. Большое спасибо Валентину Евсеевичу Вулихману, Александру Сергеевичу Калачеву и Валерию Владимировичу Шилову за ценные замечания и рекомендации, учтенные в работе. Автор благодарен Валентину Сергеевичу Ирбенеку - без помощи, участия и поддержки этого человека, столь неожиданно ушедшего из жизни, данная работа не состоялась бы.

Список литературы диссертационного исследования кандидат технических наук Рыженко, Николай Владимирович, 2004 год

1. J. Vuillemin. A data structure for manipulating priority queues. Commun. ACM 21,4 (April 1978), pp. 309-315.

2. H. Кристофидес. Теория графов. Алгоритмический подход. Москва, мир, 1978.

3. R. С. Prim. Shortest connection networks and some generalizations. Bell System Tech. J., 36,1957, pp. 1389-1401.

4. M. Kruskal. On the shortest spanning subtree of the the graph, and the traveling salesman problem. Proc. Amer. Math. Soc., 7, 1956, pp. 48-50.

5. C. Berge, A. Choilla-Houri. Programming, games and transportation networks. N.Y., John Wiley & Sons, 1965.

6. A. C.-C. Yao. An О (E log log V) algorithm for finding minimum spanning trees. Inf. Proc. Lett. 4,1975, pp. 21-25.

7. M. L. Fredman, R. E. Taijan. Fibonacci heaps and their uses in improved network optimization algorithms. Proceedings of 25th IEEE Symposium on the Foundations of Computer Science, Singer Island, 1984.

8. T. Barrera, J. Griffith, G. Robins, T. Zhang. Closing the gap: near-optimal Steiner trees in polynominal time. IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, Vol. 13, November 1993.

9. S. М. Sait, Н. Youssef. VLSI physical design automation. Theory and Practice. The Institute of Electrical and Electronics Engineers, New York, 1995.

10. M. R. Garey, R. L. Graham, D. S. Johnson. The complexity of computing Steiner minimal trees. SIAM J. of Appl. Math., 32,1977.

11. The International Technology Roadmap for semiconductors. Interconnect. 2003.

12. В. Ф. Уткин. Новые методы построения графического изображения схем, представленных списком соединений. Зарубежная радиоэлектроника. Успехи современной радиоэлектроники №7,2002, стр. 80-86.

13. В. Ф. Уткин. Исследование алгоритмических методов визуализации электрических схем. Диссертационная работа на соискание степени к.т.н., ИМВС РАН, 2002.

14. М. J. S. Smith. Application-Specific Integrated Circuits. Addison Wesley. 1997.

15. В. С^ Ирбенек. Временная верификация и оптимизация размещения компонентов предельных по быстродействию ЭВМ. Диссертационная работа на соискание степени д.т.н., ИМВС РАН, 2001.

16. J. Е. Bestley. OR-Library is a collection of test data sets for a variety of Operations Research (OR) problems, http://mscmga.ms.ic.ac.uk/info.html

17. M. Hanan. On Steiner's problem with rectilinear distance. SIAM J. Applied Math., 14,1966.

18. J. P. Cohoon, D. S. Richards, J. S. Salowe. An optimal Steiner tree algorithm for a net whose terminals lie on the perimeter of the rectangle. IEEE Transactions on Computer-Aided Design, Vol. 9, Apr. 1990.

19. Ore. Theory of graphs. Colloquium publications, 38, American Mathematical Society, Providence, 1962 (русский перевод: О. Ope. Теория графов. Москва, Наука, 1968).

20. Y. Y. Yang, О. Wing. Optimal and suboptimal solution algorithms for the wiring problem. Proceedings of IEEE International Symposium on Circuit Theory, 1972.

21. J. Ho, G. Vijayan, С. K. Wong. New algorithms for the rectilinear Steiner problem. Annals of Discrete Mathematics 53, Amsterdam, Netherlands, 1992.

22. J. S. Salowe, D. M. Warme. An exact rectilinear Steiner tree algorithm. Proceedings of International Conference on Computer Design, 1993.

23. C. D. Thomborson, L. L. Deneen, G. Shute. Computing a rectilinear Steiner minimaltree in 0{п0{Гп) time. Parallel Algorithms and Archtectures, Berlin, Germany, 1987.

24. Y. T. Wong, M. Pecht. A solution for Steiner problem. Placement and Routing of Electronic modules, New York, 1993.

25. S. E. Dreyfiis, R. A. Wagner. The Steiner problem in graphs. Networks, 1,1972.

26. J. L. Ganley, J. P. Cohoon. A faster dynamic programming algorithm for exact rectilinear Steiner minimal trees. Proceedings of 4th Great Lakes Symposium on VLSI, 1994.

27. F. K. Hwang. On Steiner minimal trees with rectilinear distance. SIAM J. Applied Mathematics, 30, 1976.

28. F. K. Hwang, D. S. Richards, P. Winter. The Steiner tree problem. North Holland, 1992.

29. J. L. Ganley, J. P. Cohoon. Optimal rectilinear Steiner trees in 0(n2 2.62") time. Proceedings of 6th Canadian Conference on Computation Geometry, 1994.

30. D. M. Warme. A new exact algorithm for rectilinear Steiner trees. INFORMS Conference, San-Diego, California, 1997.119

31. В. Ирбенек, Н. В. Рыженко. Алгоритмы проектирования топологии электрических соединений в САПР электронной аппаратуры. Зарубежная радиоэлектроника. Успехи современной радиоэлектроники №7,2002.

32. Т. Barrera, J. Griffith, S. А. McKee, G. Robins, Т. Zhang. Toward a Steiner engine: enhanced serial and parallel implementations of the iterated 1-Steiner MRST algorithm. Proceedings of Great Lakes Symposium on VLSI, Kalamazoo, MI, March 1993.

33. F. K. Hwang. The Rectilinear Steiner Problem. Journal of Design Automation and Fault-Tolerant Computing, Vol. 2,1978.

34. H. В. Рыженко. Алгоритм построения минимальных связывающих деревьев с дополнительными вершинами (деревьев Штейнера) для случая прямоугольной метрики. Труды ИМВС РАН №3,2002.

35. М. Hanan. Net Wiring for Large Scale Integrated Circuits. IBM Research Report RC 1375,1965.

36. A. Ayupov, I. Bychkov, V. Lyssyi, D. Rybin, N. Ryzhenko, A. Sorokin, A. Usenkov, V. Utkin, O. Venger. Ariadna. Technical Report, IMCS RAS, December 2003.

37. IBM benchmarks for global routing, http://beiiing.cs.ucla.edu/benchmarks/gr-input/

38. A standard-cell placer DRAGON. http://er.cs.ucla.edu/Dragon/

39. R. Nair. A Simple Yet Effective Technique for Global Wiring. In IEEE Transactions on Computer Aided Design. March 1987.41 .A global router Labyrinth, http://www.ece.ucsb.edu/~kastner/labvrinth/

40. J. Cong, P. H. Madden. Performance Driven Multi-Layer General Area Routing for PCB/MCM Designs. Proceedings of ACM/IEEE Design Automation Conference, 1998.

41. Tsung-Yi Ho, Yao-Wen Chang, Sao-Jie Chen, D. T. Lee. A Fast Crosstalk- and Performance-Driven Multilevel Routing System. ICCAD'03, November 2003.

42. S.-P. Lin, Y.-W. Chang. A novel framework for multilevel routing considering routability and performance. ICCAD'02, November 2002.

43. J. S. Rose. LocusRoute: A Parallel Global Router for Standard Cells. In Proceedings of the 25th Design Automation Conference, June 1988.

44. Coundert. Timing and Design Closure in Physical Designs Flows. Proceedings of the International Symposium on Quality Electronic Design, 2002.

45. M. Lai and D. F. Wong. Maze routing with buffer insertion and wire sizing. DAC, 2000.

46. J. Lillis, С. К. Cheng, T-.T.^Y. Lin. Optimal wire sizing and buffer insertion for low power and a generalized delay model ICCAD-95,1995.

47. T. Okamoto, J. Cong. Buffered Steiner tree construction with wire sizing for interconnect layout optimization. ICCAD-96,1996.

48. H. Zhou, D. F. Wong, I. M. Liu, A. Aziz. Simultaneous Routing and Buffer Insertion with Restrictions on Buffer Location. DAC, 1999.

49. A. H. Salek, J. Lou, M. Pedram. A simultaneous routing tree construction and fanout ' optimization algorithm. ICCAD, 1998.

50. A. H. Salek, J. Lou, M. Pedram. MERLIN: semi-order-independent hierarchical ■ buffered routing tree generation using local neighborhood search. DAC, 1999.

51. E. Bozorgzadeh, R. Kastner, M. Sarrafzadeh. Creating and Exploiting Flexibility in Rectilinear Steiner Trees. In IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems. May 2003.

52. R. Kastner, E. Bozorgzadeh, M. Sarrafzadeh, Predictable Routing. ACM/IEEE International Conference on Computer-Aided Design, 2000.

53. University of California, Santa Barbara, http://www.ucsb.edu/

54. Department of Electrical and Computer Engineering. University of California, Santa Barbara, http:// www.ece.ucsb. edu/

55. Конкурс исследовательских проектов в области автоматизации проектирования интегральных схем, проходивший при поддержке МФТИ и представительства корпорации Intel в странах СНГ. http://www.curricula.ru/CAD contest.esp

56. Row Но, Kenneth W. Mai, Mark A. Horowitz. The future of wires. Proceedings of IEEE, Vol. 89, No. 4, April 2001.

57. D. Sylvester, K. Keutzer. Getting to the Bottom of Deep Submicron II: A Global Wiring Paradigm. In proceedings of Intl. Symposium on Physical Design, 1999.

58. R. T. Hadsell, P. H. Madden. Improved Global Routing through Congestion Estimation. DAC, June 2003.

59. M. Borah, R. M. Owens, M. J. Irwin. An edge-based heuristic for Steiner routing. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 13(12), December 1994.