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

Введение.

1. Разработка алгоритма формирования сети трасс.

1.1. Краткий обзор методов трассировки соединений.

1.2. Алгоритм формирования сети трасс.

1.3. Оценки сложности и сравнительные характеристики алгоритма ФСТ.

1.4. Выводы.

2. Применение алгоритма ФСТ для решения задачи трассировки элементов БИС.

2.1. Алгоритм построения кратчайших связывающих деревьев цепей.

2.2. Оценки трудоемкости и основные свойства алгоритма.

2.3. Оптимальное размещение кратчайших связывающих деревьев на КП на основе эволюционной оптимизации клики графа пересечений

• \ •». цепей.

2.4. Минимизация числа внутрисхемных пересечений цепей внутри канала.

2.5. Выводы.

3. Разработка параллельных алгоритмов трассировки на основе алгоритма ФСТ.

3.1. Параллельный алгоритм ФСТ и описание его реализации на МВС

3.2. Организация вычислительного процесса при использовании МВС

3.3. Оценка трудоемкости параллельного алгоритма ФСТ.

3.4. Описание применения параллельного алгоритма ФСТ для реализации процесса трассировки.

3.5. Алгоритмы представления поверхностей слоев БИС в памяти МВС.

3.6. Выводы.

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

4.1. Краткое описание основных функциональных характеристик программы трассировки и структуры пакета прикладных программ

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

4.3. Выводы.

В настоящее время основным фактором ускорения научно-технического прогресса, повышения качества общественного производства, является полная автоматизация производственных процессов, одним из главных направлений которой является широкое и повсеместное использование средств вычислительной техники /1/. В то же время появление новых разработок в области вычислительной техники, создание компьютерных современных моделей, обладающих высокой степенью быстродействия, являются основными предпосылками для разработок новых технологий производства основных узлов электронно-вычислительной аппаратуры (ЭВА), основными элементами которых являются БИС и СБИС. В настоящее время вследствие постоянного роста степени интеграции элементной базы ЭВА и повышения требований к параметрам узлов ЭВА актуальной становится проблема создания методов проектирования БИС, выполняемых без участия человека /2/. Одним из решений этой проблемы в наши дни является использование систем автоматизированного проектирования (САПР). Как отмечено в /164/, теоретические исследования математических методов и разработка на их основе эффективных алгоритмов, методик и средств позволяют обоснованно решать сложные задачи сокращения сроков проектирования оптимальных дискретных систем, что резко повысит их экономическую эффективность. Поэтому основной проблемой развития вычислительной техники яв^ ляется создание высокопроизводительных вычислительных средств, способных решать поставленные задачи. В области создания эффективных САПР в настоящее время на первый план выходит задача разработки новейших САПР, учитывающих специфику различных методов проектирования /9-12/, т.е. главная цель - разработка САПР, осуществляющих оптимальное проектирование элементной базы ЭВА, в т. ч. при минимуме временных затрат /160/.

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

Под проблемой автоматизированного проектирования топологии БИС будем в соответствие с /2,153,154/ понимать решение ряда задач, включающих представление исходной электрической схемы в виде математических или матричных моделей, размещение типовых фрагментов топологии на поле кристалла, проектирование коммутационных связей между отдельными элементами, распределение фрагментов трасс в проводящих слоях, контроль топологии. В качестве предварительного шага, предшествующего этапу размещения элементов /152/, решается задача компоновки /5/. Среди работ, представляющих описание методов и алгоритмов, разработанных к настоящему времени для реализации основных этапов проектирования, отметим работы /147,153,154/. Заметим также, что использование в качестве элементной базы БИС и СБИС высокой степени интеграции требует создания эффективных САПР, имеющих полный набор проектных процедур для организации цикла проектирования, но, в ряде случаев, обладающих быстродействием, недоступным для классических однопроцессорных ЭВМ. В частности, применение высокопроизводительных суперЭВМ с параллельной архитектурой создает возможности для реализации таких алгоритмов проектирования, которые не могут быть эффективно реализованы на классических однопроцессорных ЭВМ, например, алгоритмы, связанные с комбинаторным перебором, необходимым для определения вариантов расположения соединений. В работе /146/, посвященной проблемам создания эффективных САПР БИС на базе МВС, отмечается, что "проектирование БИС высокой степени интеграции требует создания эффективных САПР для организации сквозного цикла проектирования БИС за приемлемое сточки зрения пользователя время. К вычислительным системам, которые могут в полной мере удовлетворить этим требованиям, относятся многопроцессорные вычислительные системы (МВС). Положительный эффект при решении задач автоматизации проектирования на МВС может быть достигнут, в основном, за счет их распараллеливания, что в общем случае может привести к значительному сокращению временных затрат".

Существенный вклад в решение проблемы разработки теоретических и прикладных вопросов построения высокопроизводительных вычислительных систем и эффективных САПР внесли работы таких ученых, как Каляев A.B., Курейчик В.М., Мелихов А.Н., Селютин В.И., Корячко В.П., Норенков И.П., Батищев Д.И., Лошаков В.Н., Бершадский A.M., Зайцева Ж.Н., Баталов Б.В., ГлушковВ.М., Закревский А.Д., Коган Б.М., Карцев М.А., Марчук Г.И., Поспелов Д.А., Прангишвили И.В., Пухов Г.Е., Шилейко A.B., Абрайтис Л.Б.

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

Следует заметить, что задачи оптимальной организации вычислительных устройств на различных этапах проектирования в общем случае имеют комбинаторный тип и формулируются в виде задач о покрытии, раскраске, устойчивых множествах и др. Поскольку большинство из этих задач 1ЧР полные, то это в ряде случаев создает определенные трудности, связанные с большими временными затратами при получении оптимального варианта и увеличении размерности задачи. Как отмечено в /164,165/, для повышения размерности существует ряд путей, основными из которых являются: отмеченная выше возможная замена "ручного" проектирования машинным, т.е. использование систем автоматизации проектирования; замена точных алгоритмов проектирования приближенными, что может позволить получить решения, достаточно близкие к оптимальным за допустимое время. Таким образом, когда точные эффективные алгоритмы для трудных дискретных задач неизвестны, особое значение приобретают для них приближенные эффективные методы, в которых трудоемкость снижается за счет ослабления требований к точности решения /168/.

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

Автор считает своим долгом выразить глубокую признательность засл. деятелю науки и техники РФ, д.т.н., проф. Курейчику В.М., д.ф.-м. наук, проф. Сухинову А.И. без помощи которых невозможно было бы проведение исследований и написание данной работы.

ЦЕЛЬЮ ДАННОЙ РАБОТЫ ЯВЛЯЕТСЯ разработка и исследование методов решения задачи трассировки, позволяющих устранить основные недостатки локально-оптимальных методов, ориентированных на реализацию на различных типах ЭВМ и супер-ЭВМ, а также использующих эволюционную оптимизацию для получения оптимальных и квазиоптимальных вариантов разводки при реализации на коммутационном поле (КП). Для достижения цели решены следующие задачи: разработан алгоритм формирования сети трасс (ФСТ) и алгоритм подсчета числа трасс в сети, произведено сравнение трудоемкости алгоритмов ФСТ и Дейкстры; разработан эвристический алгоритм построения множества кратчайших вариантов деревьев цепей на основе алгоритма ФСТ; разработана методика получения множества оптимальных и квазиоптимальных вариантов размещения деревьев на поле кристалла, в т. ч. с использованием эволюционной оптимизации, разработаны модификации основных генетических операторов для решения задачи формирования оптимальной клики графа пересечений; разработан алгоритм формирования сети соединений произвольной длины, ориентированный для реализации на многопроцессорной системе; разработан метод оптимального отображения монтажной поверхности в распределенной памяти МВС; разработан пакет прикладных программ, проведены экспериментальные исследования, получены результаты решения тестовых примеров, не уступающие по качеству известным результатам.

МЕТОДЫ ИССЛЕДОВАНИЙ. При решении поставленных задач в работе использовались, в основном, теоретико-графовые методы и алгоритмы, элементы теории параллельных алгоритмов и параллельных вычислительных систем, методы аналитической геометрии. Для экспериментальной реализации представленных в работе параллельных алгоритмов была использована сопроцессорная многопользовательская станция проектирования НР9000 серии 700.

НАУЧНАЯ НОВИЗНА РАБОТЫ заключается в разработке алгоритмов, позволяющих получить решение задачи трассировки соединений, ликвидирующих основные недостатки локально-оптимальных методов, осуществляющих формирование множества оптимальных и квазиоптимальных вариантов прокладки с помощью генетической оптимизации, ориентированных для реализации на многопроцессорных и однопроцессорных ЭВМ; разработке методики построения и размещения кратчайших связывающих деревьев цепей на основе выделения клик графа пересечений, в т.ч. с использованием эволюционной оптимизации, разработке модификаций основных генетических операторов для решения задачи определения оптимальной клики; разработке алгоритма формирования сети трасс кратчайшей длины и подсчета их числа, а также параллельного алгоритма ФСТ, методики параллельной реализации основных операций на МВС; разработке метода отображения дискретной монтажной поверхности в распределенной памяти МВС для различных конфигураций дискретов.

ПРАКТИЧЕСКАЯ ЦЕННОСТЬ работы определяется решением ряда задач, использующих разработанные алгоритмы, программы для сокращения сроков проектирования, повышения размерности и числа получаемых оптимальных и квазиоптимальных вариантов. ^

Исследования автора проводились в рамках госбюджетной НИР "Создать систему конструкторского проектирования заказных БИС и исследовать эффективность ее реализации на МВС", выполняемой в НИИ МВС при ТРТУ/166,167/. Научные и практические результаты данной работы использованы при разработке БИС и СБИС в ТРТУ, а также при проектировании двухслойных гидроакустических печатных плат в НИИ "Бриз" г. Таганрога.

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

В научно-производственном объединении "Интеграл" г. Минска при разработке специальной телевизионной и видеотехники использованы методы построения деревьев цепей и их оптимального размещения на основе алгоритма формирования сети трасс.

Экспериментальная реализация параллельных алгоритмов, представленных в работе, производилась на сопроцессорной многопользовательской станции проектирования НР9000 серии 700 модель 712/60 Минского завода "Транзистор". Разработанные в работе параллельные методы включены в состав библиотеки матобеспечения многопользовательской системы НР9000.

Акты об использовании результатов работы в промышленности приведены в приложении.

НА ЗАЩИТУ ВЫНОСЯТСЯ: алгоритм формирования сети кратчайших трасс на КП, алгоритм подсчета их числа; применение алгоритма ФСТ для построения кратчайших связывающих деревьев цепей, методика оптимального размещения цепей на основе формирования оптимальной клики графа пересечений; разработка основных генетических операций, реализующих процесс эволюционного поиска оптимальной клики; параллельный алгоритм ФСТ и методика его реализации на МВС; методика отображения дискретного КП в распределенной памяти МВС; результаты экспериментальной реализации генетического алгоритма и сравнительные характеристики тестовых примеров.

АПРОБАЦИЯ. Результаты данных исследований докладывались на 33, 34 студ. НТК в 1986, 1987 г., на межреспубликанской СНТК в г. Омске в 1987 г., на 1 межреспубликанской СНТК "Разработка АСУ", в г. Киеве в 1987 г., на научно-технической школе молодых ученых и специалистов "Организационно-экономические вопросы создания вычислительных комплексов и систем" в 1988 г. в Москве, на 35 и 36 НТК Таганрогского радиотехнического института в 1989 и 1990 г., на Международной НТК молодых ученых и специалистов "Молодые ученые в решении комплексной программы НТП стран - членов СЭВ" в 1989 г. в г. Киеве, на НТК молодых ученых и специалистов Таганрогского радиотехнического института "Архитектура ЭВМ и машинное моделирование" в 1989 г., на межреспубликанской НТК молодых ученых и аспирантов "Микропроцессорные системы и средства автоматики" в г. Новосибирске в 1990 г., на Всесоюзном семинаре "САПР в машиностроении и приборостроении" в г. Ульяновске в 1990 г., на 4 Международной конференции молодых ученых "Актуальные проблемы разработки АСУ" в г. Паланге в 1990 г., на 7 НТС "Математическое обеспечение систем с машинной графикой" в 1990 г. в Тюмени, на 37 и 38 НТК ТРТИ в 1991 и 1992 г., на школе-семинаре "Методы автоматизированного проектирования РЭА и СБИС" в г. Киеве в 1991г., на 16 НТК НИИ приборостроения в г. Жуковском в 1991 г., на НТК "Автоматизация проектирования РЭА и ЭВА" в г. Пензе в 1991 и 1992 г., на НТК "Информационные технологии и системы. Технологические задачи механики сплошных сред" в 1992 г. в Воронеже, на 2 Международной НТК "Актуальные проблемы фундаментальных наук" в Москве в 1994 г, на 4 Всероссийской научной конференции молодых ученых "Техническая кибернетика, радиоэлектроника и системы управления" в Таганроге в 1998 г, на 4 Всероссийской НТК "Новые информационные технологии в научных исследованиях и образовании" в Рязани в 1999 г., на Международной НТК "Проблемы совершенство

10 вания зерноуборочной техники: конструирование, организация производства, эксплуатация и ремонт" в Ростове-на-Дону в 1999 г.

ПУБЛИКАЦИИ. По теме диссертации опубликованы 22 работы (статьи и тезисы докладов на конференциях, отмеченных выше). В ВНТИЦ зарегистрировано 2 отчета по госбюджетной НИР, выполненных при участии автора.

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

4.3. ВЫВОДЫ.

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

1. Разработан пакет прикладных программ, осуществляющий реализацию на ЭВМ представленных в работе методов и алгоритмов.

2. Проведено экспериментальное исследование разработанного генетического алгоритма с использованием тестовых схем Burstein difficult channel, Burstein difficult switchbox, показавшее возможность получения результатов разводки, не уступающих по качеству известным, а для схемы Burstein difficult channel число пересечений цепей минимизировано на 1, длина параллельных прокладок в слоях уменьшена на 3 единицы.

3. Представлены графические и табличные зависимости ЦФ от числа генераций при использовании элитной и "рулеточной" селекции. Экспериментальные результаты показали целесообразность применения элитной селекции, при которой достигается более высокая частота сходимости к оптимальному значению. Показано также изменение отношения частоты сходимости в зависимости от размера популяции. При минимальном размере п = 50 частота для элитной и "рулеточной" селекции составляет 1 и 0,6, а при максимальном размере п = 200 1 и 1 для схемы Burstein difficult channel, для схемы Burstein difficult switchbox данные значения при п = 50 составляют 0 и 0 (т. е. сходимость не дает ни один тип селекции), при п = 250 0,90 и 0,75 (т.е. частота сходимости достаточно высока).

5. ЗАКЛЮЧЕНИЕ.

В заключение сформулируем и обобщим основные научные и практические результаты данной работы.

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

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

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

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

5. Разработана методика оптимального отображения КП в распределенной памяти МВС при различных степенях загруженности КП, при которой каждый МП содержит в памяти хотя бы один доступный дискрет и участвует в работе.

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

7. Получены оценки трудоемкости: для алгоритма ФСТ от числа вершин N сети 0(N), для алгоритма построения ДШ от числа вершин ДШ N 0(N ). Представлены соотношения и графические зависимости, определяющие возможность получения качественного выигрыша по трудоемкости и числу операций. Для алгоритма ФСТ данное соотношение имеет вид N>3+6C(ST), где C(ST) - число маршрутов в сети; для алгоритма построения ДШ величина качественного выигрыша возрастает с увеличением N вследствие различия в степени оценок трудоемкости (кубическая у алгоритма Ханана и квадратичная).

8. Разработан пакет прикладных программ, включающий программу трассировки дискретного КП. Проведено экспериментальное исследование генетического алгоритма, что позволило для тестовых схем получить результаты, не уступающие по качеству известным и превосходящие их. Представлены также графические и табличные зависимости ЦФ от числа генераций при использовании селекции типа "колесо рулетки" и элитной, при которой была достигнута более высокая частота сходимости к оптимальному значению. Получены результаты, показывающие изменение частоты сходимости в зависимости от размера популяции. В частности, при максимальном размере 250 для схемы Burstein difficult switchbox частота сходимости достаточно высока и составляет для элитной и рулеточной селекции соответственно 0,90 и 0,75.

1. Справочник по САПР / А.П.Будя, А.Е.Кононюк, Г.П.Куценко и др.; Под ред. В.И.Скурихина. - К.: Техника, 1988.

2. А.В.Каляев и др. Автоматизация проектирования вычислительных структур.- Изд. РГУ, 1988.

3. И.В.Прангишвили и др. Параллельные вычислительные системы с общим управлением. М.: Энергоатомиздат, 1983.

4. А.В.Каляев. Многопроцессорные системы с программируемой архитектурой.- М.: Радио и связь, 1984.

5. А.И.Петренко и др. Автоматизированное проектирование СБИС на базовых кристаллах. М.: Радио и связь, 1988.

6. Л.Б.Абрайтис. Автоматизация проектирования ЭВМ.-М.: Сов. радио, 1978.

7. М.А.Карцев. Принципы организации параллельных вычислений, структуры вычислительных систем и их реализация. Кибернетика, 1981, N2.

8. Г.Г.Казеннов, Е.В.Сердобинцев. Проектирование топологии матричных БИС. М.: Высш. шк., 1990.

9. Thomas F. Wheeler. Changing directions in VLSI CAD. IEEE Сотр., 1993.

10. D. Barle. VLSI: Fundamentional and Applications. springerverlag, New York,1980.

11. H.W. Carter. Computer Aided Design of IS. Computer, April, 1986.

12. D.L. Rijan. Computer Aided Graphics and Design. Marcel Dekker Inc, New York, 1985.

13. Б.Н.Файзулаев, И.И.Шагурин, А.Н.Кармазинский и др. Быстродействующие матричные БИС и СБИС. М.: Радио и связь, 1989.

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

15. C.Y. Lee. An algorithm of path connections and it applications. IRE trans, 1961,1. N 3.

16. F.Rubin. The Lee path connection algorithm. IEEE Trans., 1974.

17. Р.В.Ногис, Д.Ю.Юркунас. Алгоритм трассировки печатных соединений с малым числом поворотов. В кн.: Вычислительная техника. Т. 1. Каунас, политехи, ин-т, 1970.

18. J.Soukup. Fast maze router. In: Proc. 15th Design Automation Conference,1978.

19. F.Rubin. An iteractive technique for printed wire routing. In. Proc. 11th Design Automation workshop, 1974.

20. B.D.Heller, R.S.Fisher. An organizational approach to routing printed circuit boards. -In: Proc. 15thDesign Autom. Conf., 1978.

21. K.Mikami, F.Tabushi. A Computer Program for Optimal Routing of Printed Circuit Connectors. IEEE Proc., 1968.

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

23. Т.С.Лазарева. Алгоритм трассировки печатных соединений на основе представления о каналах. Автоматика и вычислительная техника, 1969, N5.

24. Е.И.Гурвич, А.И.Крапчин. Быстродействующий алгоритм трассировки двухслойных печатных плат. В кн.: Выч. техника. Т. 4. Каунас, политехи, ин-т, 1973.

25. S.F.Lass. Automated printed circuit routing with a stepping aperture. Comm. ACM, 1969.

26. В.Я.Подымов. Принципы последовательного распределения ресурсов платы в задаче трассировки. В кн.: Выч. техника. Т. 4. Каунас, политехи, ин-т, 1973.

27. О.Н.Юрин. Единая система автоматизации проектирования ЭВМ. М.: Сов. радио, 1976.

28. B.W.Kernigan, D.G.Sweikert, G.Persky. An optimum channelrouting algorithm. In: Proc. 10th Design autom. workshop, 1973.

29. D.N.Deutsch. A "Dogleg" channel router. In: Proc. 11th Design Automation Conf., 1976.

30. D.W.Hightower. Generalized Channel Router. Proc. CAD 80 Conf., 1980.

31. Н.Кристофидес. Теория графов. М.:Мир, 1978.

32. Г.П.Мозговой, В.И.Чуйков. Алгоритм сокращения затрат памяти ЭВМ при волновой трассировке биполярных матричных БИС. Изв.вузов СССР. - 1988. - Т. 31.N9.

33. Г.Э.Широ, Л.И.Лапидус. Метод трассировки печатных соединений. В кн.: Применение вычислительных машин для проектирования цифровых устройств. - М.: Сов. радио, 1968.

34. Р.П.Базилевич и др. Особенности использования аналогового рабочего поля для машинной трассировки соединений. В кн.: Вычисл. техника. Т. 4. Каунас, политехи, ин-т, 1974.

35. Л.Б.Абрайтис, В.А.Жилевичюс. Алгоритм параллельной трассировки печатных плат. В кн.: Вычисл. техника. Т. 3. Каунас, политехи, ин-т, 1972.

36. А.А.Горбачев. Модификация алгоритма Дейкстры для решения задач трассировки печатных плат. Калининградский ин-т рыбной пром. и хоз-ва, деп. в ВИНИТИ, N 7160-В89, 1989.

37. J.P.Cohoon, D.Richards. A linear-time steiner tree routing algorithm for terminals on the boundary of a rectangle. IEEE Int. Conf. Comput., 1988.

38. C.Jingsheng. A new algorithm for standard cell global routing. IEEE Int. Conf. Comput., 1988.

39. J.Joseph, A.Wu. On routing two-terminal nets in the presence of obstacles.-IEEEtranc. comput., 1989.

40. S.Majid, D.T.Lee. A new approach to topological via minimization. IEEE trans, comput, 1989, N 8.

41. S.Yitender, B.Bhargab. Via minimization in VLSI Routing with Movable Terminals. IEEE Trans. Comput. Aid, 1989, N 8.

42. J.F.Naveda, K.C.Chang. A new approach to multi-layer PCB routing with short VIAS. 1986.

43. R.Anastasi. Survey of PWS Trace routing technologies, Part 1. 1987.

44. Г.Г.Казеннов, В.М.Щемелинин. Топологическое проектирование нерегулярных БИС. М.: Высш. шк., 1990.

45. В.В.Курейчик. Исследование и разработка генетических алгоритмов для конструкторского синтеза элементов СБИС. Дисс. на соискание ученой степени к.т.н., Таганрог, ТРТУ, 1995.

46. В.Н.Сачков. Введение в комбинаторные методы дискретной математики. -М.: Наука, 1982.

47. Л.Б.Абрайтис. Автоматизация проектирования топологии цифровых ИС. -М.: Радио и связь, 1985.

48. Б.А.Сорокопуд, С.В.Дымов. Применение алгоритма Дейкстры для решения задачи трассировки. Тезисы докладов НТК "Автоматизация проектирования РЭА и ЭВА", Пенза, 1991.

49. А.А.Зыков. Теория графов. Новосибирск, Наука, 1969.

50. В.С.Линский. Построение кратчайших деревьев с ограничениями на степени вершин. Электр, техника. Сер.6. Микроэлектроника, 1971.

51. И.Л.Матицкас. Алгоритм определения дерева оптимальной длины с ограничениями степени его вершин. В кн.: Выч. техн. Т. 2. Каунас, пол. ин-т, 1971.

52. Л.Б.Абрайтис, И.Л.Матицкас, Р.Р.Хомскис. Исследование эффективности алгоритмов определения соединений комплексов монтажных схем. В кн.: Выч.техн. Т. 2, Каунас, пол. ин-т, 1971.

53. Р.В.Тверицкий. Алгоритм поиска кратчайшего пути и его применение для формирования цепей. Вопросы радиоэлектроники, сер. 7, ЭВТ, 1970.

54. Р.К.Прим. Кратчайшие связывающие сети и некоторые обобщения. В кн.: Кибернет. сб., N 2, М., ИЛ, 1961.

55. М. Ватанабэ и др. Проектирование СБИС. М.: Мир, 1988.

56. Б.А.Бабаян, В.С.Попов. Нахождение связывающей сети абсолютно минимальной длины.- Труды семинара отдела структурных и логических схем, М., ИТМ и ВТ АН СССР, 1969.

57. Y.Y.Yung, О.Wing. Optimal and suboptimal solution algorithms for the wiring problem. IEEE Proc. Int. Symp., 1972.

58. M.Chein. An algorithm pour relier N points. Calcolo, 1968, V.5.

59. H.Freitag. Design automation for LSI. In Wesion Technical Papers, L. Angeles,

60. В.А.Литвиненко. Методы определения клик графа. В кн.: Методы и программы решения оптимизационных задач на графах и сетях. Часть 2. - Новосибирск. -1982.

61. И.А.Николаев и др. Некоторые вопросы решения задачи стационарного обтекания на многопроцессорной системе. Таганрог, 1987, Деп. в ВИНИТИ, N 6573-В87.

62. L. Mah, L. Steinberg. Topological Class routing for printed circuit boards. In: Proc. ACM-IEEE Design autom. workshop, 1972.

63. В.Н.Лошаков. Параллельная трассировка соединений проводниками второго порядка. Электр, техника, 1975, в. 4.

64. В.Н.Лошаков. Методы сокращения операций в алгоритме параллельной трассировки соединений и некоторые оценки. Электр, техника, 1976, вып. 1/5/.

65. Э. Майника. Алгоритмы оптимизации на сетях и графах. М.: Мир, 1981.

66. Л.Р.форд, Д.Р.Фалкерсон. Потоки в сетях. М.: Мир, 1966.

67. Л.К.Бабенко и др. Параллельные алгоритмы метода циклической редукции для решения сеточных эллиптических уравнений. Таганрог, 1989, деп. в ВИНИТИ N 2802-В89.

68. А.В.Петросян и др. Некоторые оптимальные алгоритмы линейной трассировки. -В кн.: Вычисл. техника. Т. 6. Каунас.пол. ин-т, 1974.

69. Н.Н.Яковлев. Канальный трассировщик с гарантированным результатом. -Тезисы докладов НТК "Автоматизация проектирования РЭА и ЭВА", Пенза, ПДЭНТЗ, 1991.

70. В.В.Семенец и др. Оптимизационные алгоритмы канальной трассировки. Тезисы докладов НТК "Автоматизация проектирования РЭА и ЭВА", Пенза, ПДЭНТЗ, 1991.

71. С.Е.Маркосян. О раскраске вершин графа интервалов. Вопросы радиоэлектроники. Сер. 7. ЭВТ, 1972, Вып. 4.

72. Алгоритмы, мат. обеспечение и архитектура МВС. М.: Наука, 1982.

73. В.В.Воеводин. Математические модели и методы в параллельных процессах. М.: Наука, 1986.

74. А.В.Каляев. Принципы организации многопроцессорных систем сверхвысокой производительности. Микропроцессорные средства и системы, 1984, N 2.

75. Р.Хокни, К. Джескоуп. Параллельные ЭВМ. Архитектура, программирование, алгоритмы. М.: Радио и связь, 1986.

76. M. Feilmeier, G.Joubert. Parallel computers: architect, and perfom. Par. Сотр. proc., Berlin, 1985.

77. Л.К.Бабенко и др. Принципы организации вычислений в МВС реального времени, Львов, 1988.

78. О.Б.Макаревич и др. МВС с динамическим резервированием. Электронизация народного хозяйства, 1989, N 1.

79. В.В.Воеводин. Математическая модель конвейерных вычислений. М., 1982. /Препринт/ ОВМ АН СССР, N 42//.

80. К.Г.Самофалов, Г.М.Луцкий. Основы теории многоуровневых конвейерных вычислительных систем. М.: Радио и связь, 1989.

81. R.-D. Fubrich. The connection machine a general purpose accelerator for VLSI CAD. - IEEE Comput, 1987.

82. Y.Yag, W.Weibelle. Extensionson perfomanse Evaluation Techniques for concurrent Systems. 12th Int. Comput. Software and Appl. Conf., Chicago, 1988.

83. Б.А.Головкин. Параллельная обработка информации. Изв. АН СССР, Техн. кибернетика, 1979, N 2.

84. А.В.Каляев. Супер-ЭВМ на основе процессора ЕС 2703. Перспективы развития. Конструирование алгор. и решение задач мат. физики, М., 1987.

85. Б.А.Бабаян и др. Многопроцессорные ЭВМ и методы их проектирования. -М.: Высш. шк., 1990.

86. J.H.Barnes, R.M.Brown, M.Kato. The ILLIAC-4 Computer. IEEE Trans. Comput., 1968, N8.

87. S.F.Reddaway. DAP a distributed array processor. - IEEE/ACM, Florida,1973.

88. C.D.Polychronopoulos. Processor allocation for horizontal and vertical parallelizm. IEEE Trans. Comput, 1987.

89. Э.А.Трахтенгерц. Введение в теорию анализа и распараллеливания программ ЭВМ в процессе трансляции. М.: Наука, 1981.

90. Н.Н.Миренков. Параллельное программирование для многомодульных вычислительных систем. М.: Радио и связь, 1989.

91. Б.А.Головкин. Расчет характеристик и планирование параллельных вычислительных процессов. М.: Радио и связь, 1983.

92. В.В.Воеводин. Некоторые машинные аспекты распараллеливания вычислений. М, 1981. /Препринт/ ОВМ АН СССР: N 22/.

93. А.Б.Барский. Планирование параллельных вычислительных процессов. М.: Машиностроение, 1980.

94. В.Г.Лебедев, Ю.М.Шурайц. Распараллеливание циклов с произвольным шагом. Автомат, и телемех., 1979, N 9.

95. Программирование на параллельных вычислительных системах /под ред. Бэбба.-М.: Мир, 1991.

96. С.Б.Погребинский, В.П.Стрельников. Проектирование и надежность многопроцессорных ЭВМ. М.: Радио и связь, 1988.

97. В.Ф.Евдокимов, Л.И.Стасюк. Параллельные вычислительные структуры на основе разрядных методов вычислений. Киев.: Наукова думка, 1987.

98. Е.Валях. Последовательно-параллельные вычисления. М.:Мир, 1985.

99. Б.В.Анисимов и др. Машинный расчет элементов ЭВМ. М.: Высшая школа, 1976.

100. Л.К.Бабенко и др. Способы реализации базовых операций вычислительной алгебры в МВС. Управляющие системы и машины, 1989, N 5.

101. D.J.Evans. Design of parallel numerical algorithms. Parallel Process, 1986.

102. O.A.Mcbryan. Matrix and vector operation on hypercube parallel processor. -Par. com., 1987, v.5.

103. Параллельные вычисления / под ред. Г. Родрига. М.: Наука, 1986.

104. M.Cosnard. Complexity of the parallel QR decomposition. Parallel Comput. proc., 1986.

105. M.Cosnard, Y.Robert. Complexity of parallel QR factorization. J. Assoc. Comput. Mach., 1986, N 4.

106. А.С.Сергеев. О двух параллельных алгоритмах для определения полного спектра квадратных невырожденных матриц. Таганрог, ТРТИ, 1987, Деп. в ВИНИТИ, N 7182-В87.

107. А.С.Сергеев. Реализация QR метода на МВС. В сб.: Материалы 1 межреспубликанской НТК "Разработка АСУ", Киев, КПИ, 1989, Деп. в УкрНИИНТИ, N 998-Укр89.

108. А.И.Сухинов, А.С.Сергеев. Параллельный алгоритм метода Якоби для определения спектра симметрической эрмитовой матрицы. В сб.: Тезисы докладов НТК "Архитектура ЭВМ и машинное моделирование", Таганрог, ТРТИ, 1989.

109. S.Rose Jonathan. Parallel standard cell placement algorithms with quality equivalent to simulated annealing. IEEE Trans. Comput., 1988, V.7, N 3.

110. P.Banerjee, M.Jones. A parallel simulated annealing algorithm for standard cell placement on a hypercube computer. IEEE Int. Conf., 1986.

111. F.Darema. Parallel algorithms for chip placement by simulated annealing. IBM J.Res. and Den., 1987, v.31, N 3.

112. C.Kumar, S.Sarma. Parallel placement on a Reduced Array Architecture. 25 th ACM/IEEE Dec. Autom., Conf., 1988.

113. W.Youngju. Maze router on a hypercube multiprocessor computer. Proc. Int. Conf. Par. Proc., 1987.

114. Chang Shing Chong. Parallel algorithms for channel routing in the knock-knee model. - Proc. Int. Conf. Par. Process., 1988.

115. Mehdi R. Zargham. Parallel channel routing. 25th ACM/IEEE Des. Autom. Conf., 1988.

116. В.А.Литвиненко, С.А.Ховансков. Алгоритм трассировки на МВС. Таганрог, 1991, Деп. в ВИНИТИ. N 1684-В91.

117. Sazuki Key. A hardware maze router with application to interactive rip-up and reroute. IEEE Trans-Comput., 1986.

118. Naor Joseph. A fast parallel coloring of planar graphs with five colors. Inf. Proc. Lett, 1987, N 1.

119. P.Kleyn. An efficient parallel algorithm for planarity. 27th Ann. Symp. Found. Сотр., Toronto, 1986.

120. R.Anderson. Parallelism and the maximal path problem. Inf. Process. Lett., 1987, v.24, N 2.

121. A.C.David. A fast area-optimal VLSI algorithm for the connected components problem. IEEE Int. Conf. Comput. Design, 1987.

122. K.Doshi. Optimal graph algorithms on a fixed-size linear array. IEEE Trans. Compute, 1987, N 4.

123. В.И.Хохлюк. Параллельные алгоритмы целочисленной оптимизации. М.: Радио и связь, 1987.

124. А.С.Сергеев. Вопросы разработки программного обеспечения САПР ЭВА, ориентированного для реализации на МВС. В сб.: Тезисы докладов Всесоюзного семинара "САПР в машиностроении", Ульяновск, НПК "Ульяновский центр микроэлектроники", 1990.

125. А.С.Сергеев. Использование метода получения сети трасс между парой дискретов КП для реализации этапа трассировки проводящих покрытий матричных БИС. В сб.: Тезисы докладов 16 НТК НИИ приборостроения, г. Жуковский, 1991.

126. В.А.Калашников, А.С.Сергеев. Использование параллельных супер-ЭВМ для реализации этапа трассировки проводящих покрытий БИС. В сб.: Тезисы 38 НТК ТРТИ, Таганрог, ТРТИ, 1992.

127. Л.А.Боли, В.А.Калашников, А.С.Сергеев. Разработка технологической схемы процесса трассировки в САПР БИС, использующей независимую прокладку соединений. Тезисы докл. НТК "Информационные технологии и системы", Воронеж, 1992.

128. В.А.Литвиненко, С.А.Ховансков. Оценка эффективности определения клики графа на МВС. Таганрог, ТРТИ, 1990.

129. А.Н.Мелихов и др. Применение графов для проектирования дискретных устройств. М.: Наука, 1974.

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

131. А.Т.Абрамов и др. Автоматизированное конструирование монтажных плат РЭА. М.: Радио и связь, 1986.

132. J.Holland. Adaptation in natural and artificial systems, Ann Arbor, University of Michigan Press USA, 1975.

133. Б.К.Лебедев. Разработка точных алгоритмических методов для организации оптимальных вычислительных процессов технологического проектирования микроэлектронных устройств. -Диссерт. на соискание ученой степени к.т.н., Таганрог, 1979.

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

135. В.М.Курейчик. Вопросы моделирования эволюции в САПР. В сб.: Интеллектуальные САПР, Таганрог, 1994.

136. K.Shahokar, P.Mazumder. VLSI cell placement techniques. ACM Computing Surveys, Vol.23, 1991.

137. G.A.Vignaux, Z.Michalevicz. A genetic algorithm for the linear transportation problem. IEEE trans, on system, 1991.

138. L.Davis. Genetic algorithms and simulated annealing, London, Pitman, 1987.

139. D.N.Ackley. A connectionist machine for genetic hillclimbing. Kluwer Academic Publishers, Boston, 1994.

140. В.А.Калашников, А.С.Сергеев. Применение генетического подхода для параллельной реализации построения минимальных связывающих деревьев цепей схемы. В сб.: Интеллектуальные САПР, Таганрог, 1994.

141. В.А.Калашников, А.С.Сергеев. Применение эволюционного подхода для реализации основных этапов проектирования топологии БИС. Тезисы докладов НТК "Диагностика, информатика и метрология - 94", С. - Петербург, 1994.

142. D.E.Goldberg. Genetic algorithms in search optimization and machine lerning. Addision-wessley Publishing Company, Inc, USA, 1989.

143. И.Л.Трунов. Создание высокопроизводительных САПР на базе МВС. -Диссертация на соиск. уч. степени к.т.н., Таганрог, 1996.

144. Shervani N. Algorithms for VLSI physical design automation. Kluver Academic Publishers, 1995.

145. Мобильная объектно-ориентированная параллельная среда САПР СБИС //IEEE Trans. Comput. Aid. Des. Integr. Circuits and Syst.- 1996, p. 829-842.

146. Интегрированная САПР высокоуровневого синтеза БИС, адаптирующаяся к библиотеке модулей // Proc. Nat. Sei. Counc., Rep. China, 1995, p. 220-234.

147. Методология выбора средств автоматизации электронного проектирования // Electron Des. 1995, N 17, p. 81-94.

148. Мелихов А.Н., Карелин В.П. Методы распознавания изоморфизма и изоморфного вложения четких и нечетких графов. Таганрог, ТРТУ, 1995.

149. Ведерникова О.Г., Чернышев Ю.О. Исследование алгоритма имитации отжига числа для решения задач размещения при проектировании БИС. Известия ТРТУ, 1995.

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

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

152. Мухлаева И.В. Разработка и исследование генетических методов одномерной упаковки. Диссерт. на соискание ученой степени к.т.н., Таганрог, 1997.

153. Лебедев О.Б. Исследование и разработка генетических алгоритмов формирования топологии СБИС повышенной плотности. Диссерт. на соискание ученой степени к.т.н., Таганрог, 1997.

154. Файзуллин А.З. Разработка и исследование генетических методов размещения двумерных геометрических объектов. Диссертация на соискание ученой степени к.т.н., Таганрог, 1996.

155. Сергеев A.C. Применение эволюционной методики "направленного" кроссовера для определения оптимального размещения вариантов соединений. Интеллектуальные САПР, вып. 5, 1995 г., с. 128-131.

156. Сергеев A.C. О возможном применении направленной эволюционной оптимизации для решения задачи определения оптимумов функции. Известия ТРТУ, N 3, 1996, с. 101-102.

157. Боли JI.A. Оптимальное автоматизированное проектирование БИС. Изд-воРГУ, 1987.

158. Liening J., Thulasiraman К. A genetic algorithm for channel routing in VLSI circuits. The Massachusetts Institute of Technology, 1995.

159. Joobani R., Siewiorek D. Weaver: A Knowledge-Based Routing Expert. -IEEE Design & Test, 1986.

160. Чернышев Ю.О. Методы, алгоритмы и параллельные вычислительные структуры для решения комбинаторных задач проектирования дискретных устройств.- Диссертация на соиск. уч. степ, д.т.н., Ростов-на-Дону, 1983.

161. Гаврилов М.А. и др. Логическое проектирование дискретных устройств. -М.: Наука, 1977.

162. Об одном методе оценки эффективности алгоритмов / E.JI.Белый, О.Р.Терно и др. В кн: Проблемы совершенствования методов и процессов управления в условиях АСУ. - М.: 1980, с. 84-92.

163. Сергеев A.C. Разработка программы проектирования топологии цепей БИС на основе алгоритма формирования сети соединений. Известия ТРТУ, сер. "Интеллектуальные САПР", 1998, с. 127-129.

164. Malgorzata Marek-Sadowska. Switchbox routing a retrospective. - Integration, the VLSI journal 13, p. 39-65.

165. Давиденко B.H. Надьячеечная трассировка на основе генетических процедур. Известия ТРТУ, 1998, N 2, с. 22-27.

166. Сергеев A.C. Разработка метода проектирования топологии проводящих покрытий БИС на основе эволюционной оптимизации. Тезисы докладов НТК "Новые информационные технологии в научных исследованиях и образовании", Рязань, 1999, с.67-68.

167. Сергеев A.C. Разработка алгоритма трассировки соединений на основе генетической оптимизации клики графа пересечений цепей. Известия ТРТУ, сер. "Интеллектуальные САПР", Таганрог, 1999, с. 129-133.157