автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.12, диссертация на тему:Разработка и исследование моделей и алгоритмов решения Евклидовой задачи Штейнера для трассировки электрических соединений

Оглавление.

Введение.

1. Анализ методов и алгоритмов решения задачи трассировки.

1.1. Постановка задачи трассировки электрических соединений.

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

1.1.2. Детальная трассировка.

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

1.3. Анализ алгоритмов построения деревьев Штейнера в ортогональной метрике.

1.4. Топологическая трассировка и гибкая прокладка соединений.

1.5. Анализ топологических методов трассировки.

1.6. Выводы.

2. Разработка математического обеспечения для решения задач трассировки.

2.1. Разработка архитектуры процесса трассировки.

2.2. Геометрия гибкой трассировки.

2.3. Постановка Евклидовой задачи Штейнера.

2.4. Построение кратчайшего соединения трёх точек в Евклидовом пространстве.

2.5. Вычисление координат точки Штейнера.

2.6. Определение координат точки Штейнера при построении обходов.

2.7. Кратчайшее соединение четырёх точек в Евклидовом пространстве.

2.8. Кратчайшее соединение произвольного количества точек в Евклидовом пространстве.

2.9. Примеры решения Евклидовой задачи Штейнера для произвольного количества точек.

2.10. Выводы.

3. Решение Евклидовой задачи Штейнера для неоднородных соединений.

3.1. Постановка Евклидовой задачи Штейнера для неоднородных соединений.

3.2. Оптимальное соединение 3-х точек в Евклидовом пространстве при условии неоднородности соединений.

3.3. Решение задачи соединения источника электрических сигналов с приёмниками

3.4. Алгоритм решения Евклидовой задачи Штейнера для неоднородных соединений

3.5. Выводы.

4. Экспериментальные исследования и анализ разработанных алгоритмов и программ „

4.1. Цель экспериментальных исследований.

4.2. Этапы экспериментальных исследований.

4.3. Результаты вычислительных экспериментов и сравнение результатов работы алгоритма.

4.4. Краткое описание программной и аппаратной среды.

4.5. Выводы.

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

Под «интегральной микросхемой (ИС)» понимается микроэлектронное изделие окончательной или промежуточной формы, предназначенное для выполнения функций электронной схемы, элементы и связи которого нераздельно сформированы в объеме и(или) на поверхности материала, на основе которого изготовлено изделие [1]. Согласно [2, 3] большой интегральной микросхемой (БИС) называется интегральная микросхема содержащая 500 и более элементов, изготовленных по биполярной технологии, либо 1000 и более элементов, изготовленных по МДП-технологии, причем под элементом интегральной микросхемы понимается часть ИС, не выделенная в самостоятельное изделие, но реализующая функцию какого-либо элемента схемы, например, транзистора.

Степень интеграции постоянно возрастает с момента изобретения ИС. В 1965 году сопрезидент фирмы Intel Гордон Мур, предсказал, что число элементов на кристалле ИС должно удваиваться каждый год на протяжении последующих 10 лет. Это предсказание впоследствии было названо законом Мура [4]. Последующие 25 лет позволили уточнить закон Мура: число элементов на кристалле удваивается в среднем каждые 1,5 года. Применение на этапе проектирования САПР разного уровня способствует повышению степени интеграции СБИС на уровне узлов, блоков и всей системы в целом [5-21].

Неуклонное повышение степени интеграции СБИС привело к тому, что в них более 60% общей временной задержки сигнала приходится на задержки в межсоединениях. Рост размера области, отводимой для межсоединений, опережает рост размера области, предназначенной для активных элементов. В чипе, содержащем 10 миллионов транзисторов и использующем 4 слоя металлизации, около 40% площади отводится под межсоединения. Кроме того, рост числа транзисторов на кристалле, увеличивает также и средние размеры кристаллов. Подсчитано, что площади кристаллов самых больших ИС возрастают примерно на 13% в год и эта тенденция, согласно прогнозу, сохранится, по крайней мере, на ближайших полтора - два десятилетия.

Быстрая эволюция в производстве ИС стала бы невозможной без использования автоматизации выполнения различных этапов проектирования [5-9]. Сейчас, на всех стадиях проектирования топологии СБИС интенсивно используют средства автоматизации проектирования (САПР) и многие фазы могут быть полностью или частично автоматизированы.

Проектирование и изготовление современных СБИС невозможно без использования ЭВМ, являющихся незаменимым инструментом для расчета, изготовления, испытания, внедрения СБИС и устройств, созданных на их основе. Однако использование ЭВМ для этих целей малоэффективно без наличия мощного специального математического обеспечения, являющегося основой для создания автоматизированных систем проектирования (САПР). САПР, в общем случае, должны решать три категории задач: функциональное, техническое и технологическое проектирование.

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

Современная САПР СБИС должна учитывать ряд критериев: увеличение производительности при возрастающих ограничениях при разработке и производства СБИС, время разработки СБИС, стоимость разработки. Такая система обеспечивает разработку мелкосерийных, «заказных» СБИС. Полученная интегральная схема может использовать биполярную технологию (более 500 элементов) или МДП-технологию (более 1000 элементов).

Большой вклад в развитие моделей, методов, стратегий, алгоритмов автоматизированного проектирования СБИС внесли российские и зарубежные учёные такие, как: Бершадский A.M., Казеннов Г.Г., Курейчик В.М., Тетельбаум А .Я., Норенков И.П., Селютин В.А., Базилевич Р.П., Берштейн J1.C., Карелин В.П., Шервани Н. и др [5-21]. В основном известные алгоритмы, программы и пакеты в САПР предназначены для оптимальной компоновки, размещения разногабаритных объектов (формирования базового плана кристалла) и трассировки электрических соединений по критерию минимизации занимаемой площади и длины связей. В связи с увеличением сложности и размерности задач конструкторского проектирования, а также с возникновением новых тенденций в технологии изготовления СБИС, появляется необходимость в разработке новых направлений, методик, алгоритмов для решения данного класса задач.

С точки зрения повышения эффективности САПР, представляет интерес разработка нового математического обеспечения, алгоритмов и методов проектирования, для так решения называемых NP-полных задач, т.е. задач, в которых нахождение оптимального решения возможно только полным перебором. К числу таких методов можно отнести методы поисковые методы, методы динамического программирования, метод моделирования отжига, методы эволюционного моделирования [22-31]. В настоящее время широкое распространение получили метод моделирования отжига и эволюционные методы, поскольку такие алгоритмы позволяют обрабатывать множество решений при учёте множества критериев [32-39]. К ним относятся и генетические алгоритмы (ГА) - поисковые алгоритмы, основанные на механизмах натуральной селекции и генетики, работающие с популяциями решений методом эволюционного поиска. Уже имеются примеры успешного применения ГА для решения самых различных задач, в том числе и задач автоматизированного проектирования СБИС.

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

Значительный интерес, проявляемый к проблеме машинного проектирования эскиза топологии соединений, во многом объясняется большой трудоемкостью этого этапа и невозможностью создания универсальных алгоритмов трассировки, одинаково эффективных для различных конструкций СБИС. Известно большое число алгоритмов трассировки, основанных на различных методах построения, как отдельных трасс, так и цепей в целом [40-44]. Важным вопросом при трассировке является построение кратчайших связывающих деревьев цепей электрических схем. Решение задачи построения минимальных связывающих деревьев используется на начальном этапе трассировки для определения возможной конфигурации соединений [45 - 50].

Различают два принципа построения минимальных связывающих деревьев. Первый состоит в том, что не допускается вводить дополнительные вершины. Такая задача называется построением минимального связывающего дерева (МСД). Существуют эффективные алгоритмы Крускала, Прима и другие, предназначенные для построения МСД. Второй случай состоит в том, что разрешается вводить произвольное количество дополнительных вершин и соединяющих их ребер. Такая задача называется задачей Штейнера [51-62]. Ее решение приводит к построению дерева Штейнера (ДТП), а дополнительные вершины называются точками Штейнера (ТШ).

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

В этой связи, тема работы, связанная с разработкой нового математического обеспечения для построения кратчайших связывающих деревьев и построения обходов элементов, а также методов и алгоритмов доразводки электрических соединений в процессе трассировки СБИС является АКТУАЛЬНОЙ.

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

Для достижения поставленной цели были поставлены и решены следующие задачи:

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

Выполнен анализ существующих методов и алгоритмов решения задачи построения минимальных связывающих деревьев и задачи Штейнера.

Предложен математический аппарат, позволяющий выполнять построение минимальных связывающих деревьев Штейнера.

Разработана математическая модель и алгоритм построения минимального связывающего дерева (дерева Штейнера) на основе решения Евклидовой задачи Штейнера.

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

Разработана математическая модель и методика сопряжения построений Евклидовых деревьев Штейнера с построением обходов для гибкой прокладки соединений.

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

Для решения поставленных задач использовались следующие МЕТОДЫ ИССЛЕДОВАНИЙ: элементы теории множеств, элементы теории графов и гиперграфов, элементы теории алгоритмов, элементы теории генетического поиска.

НАУЧНАЯ НОВИЗНА диссертационной работы заключается в:

1. Разработке математического аппарата и моделей для построения дерева Штейнера на основе решения Евклидовой задачи.

2. Разработке алгоритма построения минимального связывающего дерева (дерева Штейнера), позволяющего сократить длину соединений.

3. Разработке алгоритма построения минимального связывающего дерева (дерева Штейнера) с учетом различной толщины соединений и наличия направленности соединений.

4. Разработке метода сопряжения построений Евклидовых деревьев Штейнера с построением обходов для гибкой прокладки соединений.

ПРАКТИЧЕСКУЮ ЦЕННОСТЬ работы представляют:

Математическая модель построения минимального связывающего дерева на основе решения Евклидовой задачи Штейнера.

Алгоритм и программное обеспечение для решения задачи построения дерева Штейнера на этапе глобальной трассировки СБИС, позволяющие уменьшить длину соединений при проектировании СБИС.

Алгоритм и программное обеспечение построения минимального связывающего дерева с учетом различной толщины соединений и наличия направленности соединений.

Метод сопряжения построений Евклидовых деревьев Штейнера с построением обходов для гибкой прокладки соединений. РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ.

Основные теоретические и практические результаты диссертационной работы использованы в госбюджетной НИР «Разработка теории и принципов построения интеллектуальных систем автоматизированного проектирования на основе эволюционной адаптации, нейросетевых моделей и методов принятия решений», а также х/д НИР по теме «Исследование алгоритмов решения Евклидовой задачи Штейнера для трассировки электрических соединений».

Материалы диссертации были использованы в учебном процессе на кафедре САПР ТРТУ при чтении лекций по курсам «Методы оптимизации», «Эволюционное моделирование и генетические алгоритмы», «Автоматизация конструкторского и технологического проектирования».

АПРОБАЦИЯ основных теоретических и практических результатов работы проходила на Международных научно-технических конференциях «Интеллектуальные САПР» и «Искусственные интеллектуальные системы» (г. Геленджик, 2004 - 2005 гг.), на Всероссийской научной конференции «Управление и информационные технологии» (г. Пятигорск, 2004 г.), на Всероссийской научной конференции аспирантов и студентов (г. Таганрог , 2004 - 2005 гг.) и Всероссийской конференции молодых ученых и аспирантов «Новые информационные технологии» (г. Таганрог, 2004 - 2005 гг.).

ПУБЛИКАЦИИ. По теме диссертации опубликовано 9 печатных работ.

СТРУКТУРА И ОБЪЁМ ДИССЕРТАЦИОННОЙ РАБОТЫ

Диссертационная работа состоит из введения, четырёх глав, заключения, и списка использованных источников. Работа содержит 140 стр., включая 59 рис., 3 табл., список использованных источников из 120 наименований, 3 стр. приложений и актов об использовании и регистра .

4.5. Выводы

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

Результаты экспериментов показали эффективность разработанного алгоритма по сравнению с существующими. Основными критериями эффективности являются качество получаемого решения (целевая функция) и временная сложность алгоритма.

ЗАКЛЮЧЕНИЕ

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

1. Сформулирована поставка задачи и определено ее место в общей проблеме проектирования ЭВА. Проведен комплексный анализ существующих этапов трассировки, выявлены их особенности и недостатки. Обоснована необходимость разработки нового математического и программного обеспечения решения Евклидовой задачи Штейнера для трассировки электрических соединений.

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

3. Разработано математическое обеспечение для построения кратчайших обходов с перестроением Евклидовых деревьев Штейнера при прокладке соединений в произвольной метрике, позволяющие вычислять точное взаимное расположение точек обхода и смежных точек Штейнера.

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

5. Разработано математическое обеспечение и алгоритм построения оптимального Евклидового дерева Штейнера с разнородными фрагментами соединений позволяющие минимизировать суммарную площадь.

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

1. Закон РФ № 3526 - 1 от 23.09.92г. «О правовой охране топологий интегральных микросхем»

2. ГОСТ 17021 75 «Микросхемы интегральные. Термины и определения».

3. Морозов К.К., Одиноков В.Г., Курейчик В.М. Автоматизированное проектирование конструкций радиоэлектронной аппаратуры: Учеб. пособие для вузов. М.: Радио и связь, 1983.-280 е.: ил.

4. Schaller Robert R. MOORE IS LAW: past, present, and future. IEEE SPECTRUM JUNE, 1997, pp. 53-59.

5. Селютин В.А. Машинное конструирование электронных устройств. -М.: Советское радио, 1977. 384 с.

6. Деньдобренко Б.Н., Малика А.С. Автоматизация конструирования РЭА. М.: Высшая школа, 1980. - 384 с.

7. Курейчик В.М. Математическое обеспечение конструкторского и технологического проектирования с применением САПР. М.: Радио и связь, 1990.-352 е.: ил.

8. Селютин В.А. Автоматизированное проектирование топологии БИС. -М.: Радио и связь, 1983. 112с.

9. Sherwani N.A. Algoritms for VLSI Physical Design Automation. Norwell, Kluwer Academic Publishers, 1995, 538 p.

10. Петренко А.И., Лошаков B.H., Тетельбаум А.Я., Шрамченко Б.Л. Автоматизированное проектирование СБИС на базовых кристаллах. М.: Радио и связь, 1988. 160 е., ил.

11. Системы автоматизированного проектирования: В 9-ти кн. Кн. 6. Автоматизация конструкторского и технологического проектирования: Учеб. пособие для втузов/ Под ред. Норенкова И.П.-М.: Высшая школа, 1986.-160 с.:ил.

12. Корячко В.П., Курейчик В.М., Норенков И.П. Теоретические основы САПР: Учебник для вузов. М.: Энергоатомиздат, 1987.-400 е.: ил.

13. Савельев А.Я., Овчинников В.А. Конструирование ЭВМ и систем. Москва, Высшая школа, 1989.

14. Базилевич Р.П. Декомпозиционные и топологические методы автоматизированного конструирования электронных устройств. Львов: Вища школа, 1981. - 168 е., ил.

15. Петренко А.И., Сыпчук П.П., Тетельбаум А.Я., Иванников А.Д., Саватьев В.А. Автоматизация конструирования больших интегральных схем. Киев, Вища школа, 1983. - 312 с.

16. Автоматизация проектирования радиоэлектронных средств. Учебное пособие для ВУЗов. Под ред. О.В. Алексеева. М.: Высшая школа, 2000. -479 с.

17. Методы разбиения схем РЭА на конструктивно законченные части. Под редакцией Морозова К.К. М.:, Советское радио, 1978.

18. Петренко А.И., Тетельбаум А.Я., Шрамченко Б.Л. Автоматизация конструирования электронной аппаратуры (топологический подход). -Киев: Вища школа, 1980. 176 с.

19. Автоматизация проектирования топологии БИС на базовых матричных кристаллах / А.И. Петренко, А.Я. Тетельбаум, Б.Л. Шрамченко, Н.В. Луганский // Зарубежная радиоэлектроника, 1985, № 8, с. 26 - 40.

20. Автоматизация проектирования больших и сверхбольших интегральных бхем. / А.И. Петренко, В.М. Курейчик, А.Я. Тетельбаум и др. // Зарубежная радиоэлектроника, 1981, № 6, с. 47 - 66.

21. Крегер Д., Тозун О. Автоматизированное проектирование обостряет конкуренцию приборов со стандартами. //Электроника, 1980, т.ЗЗ, № 15, с.28 - 34.

22. Holland, John Н., Adaptation in Natural and Artificial Systems: An Introductory Analysis with Application to Biology, Control, and Artificial Intelligence. University of Michigan, 1975.

23. Goldberg David E., Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Publishing Company, Inc. 1989.

24. Davis L.D. Handbook of Genetic Algorithms. Van Nostrand Reinold, New York, 1991, -385p.

25. Курейчик В.М. Генетические алгоритмы и их применение. Монография. Таганрог: Изд во ТРТУ, 2003 - 212 с.

26. Емельянов В.В., Курейчик В.В., Курейчик В.М. Теория и практика эволюционного моделирования. Монография. М: Физматлит, 2003. -432 с.

27. Гладков JI.A., Курейчик В.В., Курейчик В.М. Генетические алгоритмы. Учебное пособие. Под ред. В.М. Курейчика. Ростов-на-Дону, Ростиздат, 2004. - 400 с.

28. Foundation of Genetic Algorithms, edited by Rawlins Gregory. Morgan Kaufman Publishers, San Mateo, California, 1991, -473p.

29. Practical Handbook of Genetic Algorithms Complex Coding Systems. Volume 3. / Edited by Lance D. Chambers. CRC Press, Boca Raton, London, New York, Washington D.C., 1999. - 572 p.

30. Michalewicz Z. Genetic Algorithms + Data Structures = Evolution Programs. Springer-Verlag, 1992.

31. Курейчик В.В. Эволюционные методы решения оптимизационных задач: Монография. Таганрог: Изд-во ТРТУ, 1999,95 с.

32. Ren-Hung Hwang, Wei-Yuan Do, Shyi-Chang Yang. Multicast Routing Based on Genetic Algorithms. Journal of Information Science and Engineering 16, 885-901,2000.

33. Xianwei Zhou. Genetic algorithm for stochastic optimal control traffic assignment problem, proceedings of neural networks and brain on international conference in 1998, 305-3

34. Zhou Xianwei, Chen Changjia, Zhu Gang. A Genetic Algorithm for Multicasting Routing Problem. School of Electronic and Information Engineering, Northern Jiaotong University , Beijing , 100044

35. Burstein M. Channel routing, Layout Design and Verification. Elsevier Science, 1986. pp. 133-167.

36. Yoshimura Т., Kuh E.S. Efficient algorithms for channel routing. IEEE Trans. Computer Aided Design Integrated Circuits & Syst., vol.1, no.l, 1982. pp. 2535.

37. Alexander M. J., Robins G. New I performance-driven FPGA Routing Algorithms. IEEE Transactions on CAD of Integrated Circuits and Systems, Vol. 15, No. 12, pp. 1505-1517, December 1996.

38. Cox L.A., Davis L., Qiu Y. Dynamic Anticipatory Routing In Circuit-Switched Telecommunications Networks. Handbook of Genetic Algorithms, Lawrence Davis, ed., VanNostrand Reinhold, 1991, pp 124 143.

39. Zhou X. Genetic algorithm for stochastic optimal control traffic assignment problem, proceedings of neural networks and brain on international conference in 1998. p. 305 - 309.

40. Christensen H.L., Wainwright R.L., Schoenefeld D.A. A Hybrid Algorithm for The Point to Multipoint Routing Problem. Proceedings of the 1997 ACM Symposium on Applied Computing, ACM Press, 1997, pp 263 268.

41. Bharath-Kumar K., Jaffe J.M. Routing to multiple destinations in computer networks. IEEE Trans. Commun., Vol. COMM-31, No.3.,1983, p. 343-351.

42. Rouskas G. N. Multicast routing withi end-to-end delay and delay variation constraints. IEEE Journal on selected areas in communications, No.3., 1997, p. 346- 156.

43. Ammar M. H., Cheung S.Y., Scoglio C.M. Routing Multipoint Connections Using Virtual Paths in an ATM Network. IEEE INFOCOM '93, The Conference on Computer Communications Proceedings Vol.1 (1993) 95-105.

44. Kadirire J., Knight G. Comparison of Dynamic Multicast Routing Algorithms for Wide-Area Packet-Switched ATM Networks. IEEE Conference on Computer Commu-nications 1 (1995)-p. 212-219.

45. Gondran M., Minoux M. Graphs and Algorithms. John Wiley, New York, NY, 1984.

46. Dionne R., Florian M. Exact and Approximate Algorithms for Optimal Network Design. Networks 9 (1979) 37-59.

47. Ни Т. C. Optimum communication spanning trees. SIAM Journal on Computing, 3(3):188-195,1974.

48. Kershenbaum A. Telecommunications Network Design Algorithms. McGraw-Hill, New York, NY, 1992.

49. Moon J. W. Various proofs of cayley's formula for counting trees. In F. Harary, editor, A Seminar on Graph Theory, pages 70{78. Holt, Rinehart,and Winston, New York, NY, 1967.

50. Palmer С. C., Kershenbaum A. Two algorithms for finding optimal communications spanning trees. Technical Report (report number unassigned), IBM T. J. Watson Research Center,P.O. Box 704, Yorktown Heights, NY, 1993.

51. Hanan M., "On Steiner's problem with rectilinear distance," SIAM J. Appl. Math., vol 14,1966. pp. 255-265.

52. Steger A. The Steiner Tree Problem. 1 March 2004. On-line. http://www.ti.inf.ethz.ch. 12 Apr 2004.

53. Chopra S. Comparison of Formulations and a Heuristic for Packing Steiner Trees in a Graph. Annual of Operations Research, vol. 50, Sept. 1994. pp. 143-171.

54. Mandoiu I.I., Vazirani V.V., Ganley J.L. A New Heuristic for Rectilinear Steiner Trees, IEEE Transactions on CAD 19 (2000). pp. 1129-1139.

55. Esbensen H. Finding (Near-) Optimal Steiner Trees in Large Graphs, Proceedings of the Sixth International Conference on Genetic Algorithms, Morgan Kaufmann Publishers, Inc., 1995. pp 485 - 492.

56. Winter P., Hwang F.K., Richards D.S. The Steiner tree problem. Elsevier Science Publishers В. V., 1992.

57. Winter P. Steiner problems in networks: a survey. Networks, 17, 1987.

58. Chang C., Sarrafzadeh M. Wong C.K. A powerful global router: Based on steiner min-max trees. Proceedings of IEEE International Conference on Computer-Aided Design, pages 2-5, November 7-10 1989.

59. Plesnik J. A bound for the Steiner tree problem in graphs. Math. Slovaca, 31, 1981.

60. Rayward-Smith VJ. The computation of nearly minimal Steiner trees in graphs. Int. J. Educ. Sci. Techmol., 14, 1983.

61. Rao S. K., Sadayappan P., Hwang F. K., Shor P.W. The rectilinear Steiner arborescence problem, Algorithmica, vol 7., 1992. pp. 277-288.

62. Ivanov A., Tuzhilin A. Minimal Networks: The Steiner Problem and its Generalizations. CRC Press, 1994.

63. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980. 476 с.

64. Кофман А. Введение в прикладную комбинаторику. М.: Наука, 1975. -480 с.

65. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978.-432 с.

66. Курейчик В.М. Оптимизация в САПР: Учебное пособие. Таганрог, ТРТУ, 1998.

67. Овчинников В.А. Алгоритмизация комбинаторно-оптимизационных задач при проектировании ЭВМ и систем. М.: изд-во МГТУ им. Н.Э.Баумана, 2001. - 288 с.

68. Кормен Т., Лейзерсон И., Ривест Р. Алгоритмы: построения и анализ. М.: МЦМО,2000.

69. Фридман А., Менон П. Теория и проектирование переключательных схем. М.: Мир, 1978.

70. Dreyer D., Overton М. Two Heuristics for the Euclidean Steiner Tree Problem. NSF 2002.

71. Winter P., Zachariasen M. Large Euclidean Steiner Minimum Trees in an Hour. ISMP 1997.

72. Kahng А. В., Robins G. A New Class of Iterative Steiner Tree Heuristics with Good Performance, IEEE Transactions on Computer-Aided Design, 11 (7), 1992. pp. 893-902.

73. Salowe J.S., Warme D.M. An Exact Rectilinear Steiner Tree Algorithm, in Proc. IEEE Intl. Conf. on Computer Design, Cambridge, MA, October 1993. -pp. 472-475.

74. Harris F Jr. Parallel Computation of Steiner Minimal Trees. PhD Dissertation, Department of Computer Science, Clemson University, Clemson, South Carolina, 1994.

75. Kalpakis K., Sherman A.T. Probabilistic Analysis of an Enhanced Partitioning Algorithm for the Steiner Tree Problem in Rd. Networks, vol. 24, No. 3, May 1994. pp. 147 - 156.

76. Dahlhaus E. A Parallel Algorithm for Computing Steiner Trees in Strongly Chordal Graphs. Discrete Applied Mathematics, vol. 51, no. 1-2, June 22, 1994.-pp. 47-61.

77. Grith J., Robins G., Salowe J. S., Zhang T.T. Closing the Gap: Near-Optimal Steiner Trees in Polynomial Time. IEEE Transactions on Computer Aided Design and Describing Integrated Circuits Systems, vol. 13, no. 11, Nov. 1994.-pp. 1351-1365.

78. Zachariasen M., Warme D., Winter P. Exact algorithms for plane Steiner tree problems: a computational study. Technical Report DIKUTR-98/11, University of Copenhagen, 1998.

79. Hochbaum, D. Approximation Algorithms for NP-Hard Problems. PWS Publishing, 1997.

80. Vazirani V. Approximation Algorithms. Springer, 2001. http://www.ti.inf.ethz.ch/ew/courses/ApproxAlgs0304/problem sets/approx-steiner.pdf.

81. Warme D.M., Winter P., Zachariasen M. Exact Algorithms for Plane Steiner Tree Problems: A Computational Study. University of Copenhagen, 1998.

82. Zachariasen, M. Algorithms for Plane Steiner Tree Problems. Ph.D. Thesis, Department of Computer Science, University of Copenhagen, 1998.

83. Zhou, H. Efficient Steiner tree construction based on spanning graphs. ISPD 2003.

84. Kou L., Markowvksi G., Berman L. A fast algorithm for Steiner trees. Acta Informatica,15,1982.

85. Beasley J. E. A heuristic for euclidean and rectilinear Steiner problems. European journal of Operational Research, 58,1992. pp. 284-292.

86. Zelikovsky A.Z. A 11/6- approximation algorithm for the network Steiner problem. Algorithmica, 9:463-470,1993.

87. Beasley J.E. Algorithm for the Steiner Problem in graphs. Networks 14 (1984) 147-169

88. Beasley J.E. An SST-based Algorithm for the Steiner Problem in Graphs. Networks 19(1989) 1-16.

89. Dowsland K.A., Hill-Climbing, Simulated Annealing and the Steiner Problem in Graphs. Engineering Optimization 17 (1991) 91-107.

90. Larochelle J.-F., A Tabu Search Heuristic for the Steiner Tree Problem in Graphs.Master Thesis Ecole Polytechnique de Montreal (1995) 105 p.

91. Ho J.M., Vijayan G., Wong C.K. A new approach to the rectilinear Steiner tree problem. IEEE Transactions on Computer Aided Design, 9(2): 185-193, February 1985.

92. Jones J., Harris F. A Genetic Algorithm for the Steiner Minimal Tree Problem. University of Nevada. http://www.cs.unr.edu/~fredh/papers/conf/agaftsmtp/paper/doc 1 .ps.gz

93. Rabkin M. Efficient use of Genetic Algorithms for the Minimal Steiner Tree and Arborescence Problems with applications to VLSI Physical Design. Design Technology Process Verification and Physical Design, Intel Corporation, Santa Clara, California 9505.

94. Ludwick J. A Parallel and Genetic Approach to the Steiner Tree Extraction Problem. Masters Paper, Department of Computer Science, Clemson University, Clemson, South Carolina, 1996.

95. Esbensen H. Computing near-optimal solutions to the Steiner problem in a graph using a genetic algorithm. Networks, Vol.26,1995. pp. 173-185.

96. Ho J.M., Vijayan G., Wong С. K. A new approach to the rectilinear Sterner tree problem. IEEE Transactions on Computer Aided Design, 9(2): 185-193, February 1985.

97. Chang C., Sarrafzadeh M., Wong C.K. A powerful global router: Based on sterner min-max trees. Proceedings of IEEE International Conference on Computer-Aided Design, pages 2-5, November 7-10 1989.

98. Базилевич Р.П. Обобщённый подход к формализации задачи машинной трассировки межсоединений на плоскости. // Изв. ВУЗов СССР. Радиоэлектроника, 1974, № 6. с. 98-103.

99. Базилевич Р.П. Некоторые задачи синтеза планарных топологий. В кн.: Вычислительная техника. Вильнюс, 1979, т. 12. - с. 16-23.

100. Базилевич Р.П. Декомпозиционные и топологические методы автоматизированного метода конструирования электронных устройств. Львов.: Вища школа, 1981. - 168с.

101. Лузин С.Ю., Полубасов О.Б. Проектирование печатных плат. Новые методы решения старых проблем. // САПР и графика, 1997, № 11. с. 58 -59.

102. Лузин С.Ю., Полубасов О.Б. Топологическая трассировка: реальность или миф? EDA Expert, 5(68), 2002. - с. 42-46.

103. Петренко А.П., Тетельбаум А.Я., Забалуев Н.Н. Топологические алгоритмы трассировки многослойных печатных плат. М.: Радио и связь, 1983.- 152с.

104. Система топологической трассировки печатных плат TopoR ver. 1.0. Руководство пользователя. Санкт-Петербург, 2003.

105. Сухарев А.В., Золотов А.И. Модели и процедуры оптимизации в автоматизации проектирования. (Программный комплекс FreeStyle Router): Учеб. пособие. СПб.: СЗТУ, 2001. - 165с.

106. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи.-М.: Мир, 1982.-416 с.

107. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность.-М.: Мир, 1985.-512 с.

108. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов.-М.: Мир,- 1979.-536 с.

109. Ш.Липский В. Комбинаторика для программистов/ Пер. с польского Евстигнеева В.А., Логиновой О.А.-М.: Мир, 1988.-213 с.:ил.

110. Митропольский А.К. Техника статистических исследований. М., "Наука"., 1971.-576 е.: ил.

111. Применение математических методов и ЭВМ. Планирование и обработка результатов эксперимента: Учеб. пособие./ Под общ. ред. Останина А.Н.- Минск.: Вышэйшая школа., 1989. 218 е.: ил.

112. Адлер Ю.П. Введение в планирование эксперимента. М.: Металлургия, 1969. 157 с.:ил.

113. Лэнгсам Й., Огенстайн М., Тетельбаум А. Структура данных для персональных ЭВМ. М., Мир, 1989. - 568 с.

114. Львовский Е.Н. Статистические методы построения эмпирических формул: Учеб.пособие для втузов. М., Высшая школа, 1988. 239 е.: ил.

115. Helvig С. S., Robins G., Zelikovsky A. Improved Approximation Bounds for the Group Steiner Problem, In Proc. Conference on Design Automation and Test in Europe, 1998. pp. 406 - 413.

116. Berman P., Raimayer V. Improved Approximations of the Steiner Tree Problem. Journal of Algorithms, vol. 17, no. 3, Nov. 1994. pp. 381-408.

117. Chow W. F., Soukup J. Set of test problems for the minimum length connecting networks.

118. Duin C. W., Volgenant A. Reduction Tests for the Steiner Problem in Graphs. Networks 19 (1989) 549-567.