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

ВВЕДЕНИЕ

1. СРАВНИТЕЛЬНЫЙ АНАЛИЗ АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧИ • КАНАЛЬНОЙ ТРАССИРОВКИ ЦЕПЕЙ РАЗЛИЧНОЙ ШИРИНЫ В СБИС

1.1. Постановка задачи канальной трассировки цепей в СБИС.

1.2. Исследование бессеточного алгоритма канальной трассировки СБИС.

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

1.4. Применение алгоритмов адаптации в методах генетического поиска.

1.5. Выводы.

2. РАЗРАБОТКА ГЕНЕТИЧЕСКОГО АЛГОРИТМА КАНАЛЬНОЙ ТРАССИРОВКИ ЦЕПЕЙ РАЗЛИЧНОЙ ШИРИНЫ В СБИС

2.1. Постановка задачи.

2.2. Целевая функция.

2.3. Принципы кодирования и декодирования хромосом.

2.4. Принцип создания массивов горизонтальных и вертикальных максимумов .57 2.5 Создание начальной популяции.

2.6. Структурная схема генетического алгоритма.

2.7. Модифицированные генетические операторы.

2.8. Теоретические оценки алгоритма.

2.9. Выводы.

3. РАЗРАБОТКА ГЕНЕТИЧЕСКОГО ОПЕРАТОРА НА ОСНОВЕ ПРОЦЕДУР АДАПТАЦИИ.

3.1. Генетический оператор адаптации.

3.2. Структурная схема алгоритма адаптации.

3.3. Формирование объекта адаптации.

3.4. Целевая функция.

3.5. Модель объекта адаптации.

3.6. Методика выработки управляющих сигналов.

3.7. Пример работы оператора адаптации.

3.8. Теоретические оценки оператора адаптации.

3.9. Выводы.

4. РАЗРАБОТКА ПРОГРАММНОЙ РЕАЛИЗАЦИИ И ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ РАЗРАБОТАННЫХ АЛГОРИТМОВ.

4.1. Цель экспериментального исследования.

4.2. Описание работы с программой.

4.3. Формат входного и выходного файла канала СБИС.

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

4.5. Результаты экспериментальных исследований.

4.6. Сравнение результатов исследования разработанных алгоритмов с результатами аналогов.

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

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

СБИС делятся на область коммутационных блоков (от англ. бшНсЫзох) и область каналов.

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

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

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

• шумы и задержки как следствие перекрёстных искажений;

• падение напряжения на внутреннем активном сопротивлении; ^ • электромиграция и плотность тока; индуктивность.

Перекрёстные искажения возникают из-за взаимной емкостной связи между проводниками микросхемы, в результате чего при изменении уровня сигнала в проводнике форма сигнала в соседних проводниках также изменяется. Эти эффекты почти не проявлялись при использовании технологии с шириной проводников 0,5 мкм и больше. По мере повышения плотности схем и перехода к 0,25-мкм и меньше технологии, емкостная связь начинает расти вследствие сближения проводников и роста их относительной толщины.

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

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

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

Проблема канальной трассировки является NP-полной [1] и в настоящее время не существует радикального метода, гарантирующего нахождение глобально оптимального решения. Существующие детерминированные алгоритмы хоть и обеспечивают высокую точность получаемых решений, однако для получения этого результата необходимо очень много времени. Такие алгоритмы используются при небольшой размерности задачи.

Одним из новых направлений поисковых методов являются методы генетического поиска. Они базируются на моделировании естественного процесса эволюции для поиска оптимального решения [2]. Существуют четыре основных модели эволюционных алгоритмов: генетические алгоритмы (Holland, 1975), генетическое программирование, эволюционное программирование (Fogel, 1966) и эволюционные стратегии (Rechenberg, 1973). В генетическом алгоритме (ГА) решению соответствует хромосома. Она оценивается целевой функцией (fitness). Важное значение придается кодированию решения в хромосому и разработке целевой функции. Основными механизмами трансформации решения являются операторы кроссинговера и мутации. Существует множество различных операторов как стандартных (побитовое скрещивание, изменение одного гена), так и специальных, созданных только для конкретного алгоритма, и только для конкретной структуры хромосомы. В кроссинговере новое решение образуется из нескольких старых. В мутации существующее решение может случайно преобразовано. Таким образом, из полученной новой популяции решений на основе селекции могут быть отобраны лучшие решения в следующее поколение. Весь метод моделирует естественный процесс эволюции в достижения оптимума.

Основное отличие ГА от других оптимизационных методов состоит в том, что они оперируют целым множеством решений. Используется целевая функция, а не детерминированная оценка решения. Для модификаций решений и последующей селекции используются вероятностные модели.

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

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

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

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

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

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

3. Построение алгоритма формирования начальной популяции.

4. Разработка и исследование нового генетического оператора на основе процедур адаптации.

5. Создание структуры и принципов кодирования и декодирования хромосомы.

6. Разработка процедуры оценки и качества (целевой функции).

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

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

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

2. Создании новых структур и принципов кодирования и декодирования решений для задачи канальной трассировки.

3. Создании модифицированного алгоритма формирования начальной популяции.

4. Разработке нового генетического оператора на основе процедур адаптации.

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

1. Структура и принцип представления информации для генетического алгоритма канальной трассировки СБИС.

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

РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ.

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

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

Результаты работы внедрены в НИИ ТКБ ТРТУ по научно-исследовательской работе №710/98-16002-7 «Участие в разработке технических предложений по созданию РИС и алгоритмов ее функционирования».

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

ПУБЛИКАЦИИ. Результаты диссертации отражены в 7 печатных работах. Запатентовано 1 авторское свидетельство для программ ЭВМ «Программа генетической трассировки цепей в канальной области СБИС (ПГТК)»

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

Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложения. Работа содержит 147 стр., включая 60 рис., 13 таб., список литературы из 105 наименований, 5 стр. приложений и актов об использовании.

4.7. Выводы и рекомендации

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

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

3. Экспериментальное исследование стандартных каналов показывает, что результаты данного алгоритма в некоторых случаях равны или лучше опубликованных результатов других популярных алгоритмов.

ЗАКЛЮЧЕНИЕ

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

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

V трассировки СБИС.

2. Разработан комплекс алгоритмов канальной трассировки, на основе применения методов генетического поиска и алгоритмов адаптации. Генетический алгоритм основан на проблемно-специфическом представлении схемы и проблемно-ориентированных генетических операторах. Создан генетический оператор на основе процедур адаптации. Он использует несколько видов автоматов адаптаций, такие как автомат с линейной тактикой, «осторожный» и «доверчивый» автоматы. Оператор создает решения по отличной от других генетических операторов схеме, тем самым, увеличивая разнообразие генотипа в генетическом алгоритме.

3. Создана новая методика кодирования решений. Она учитывает специфику решаемой задачи, и позволяет отбросить большое количество "нереальных" решений. Применение новых принципов кодирования позволяет улучшить качество получаемых решений и уменьшить время работы алгоритма. Определены генетические операторы, схема генетического алгоритма.

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

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

Yr- оценки пригодности решения. Она учитывает длину проводников цепей, количество межслойных переходов, габаритные размеры канала СБИС. Созданы модифицированные генетические операторы, позволяющие улучшить решения на 10-30% по сравнению с начальными решениями, формируемыми волновым алгоритмом. Определены ВСА каждого генетического оператора, они пропорциональны 0(N2).

5. Использование параллельных стратегий выполнения генетического алгоритма с применением оператора миграции позволило: усовершенствовать качество решения, уменьшить вероятность попадания в локальный оптимум, сократить время решения задачи.

6. Для реализации предложенного комплекса алгоритмов было разработано программное обеспечение. При разработке программы канальной трассировки СБИС были учтены критерии создания пользовательского интерфейса (интуитивность, непротиворечивость, неизбыточность, гибкость). Программа выводит информацию о проделанной работе в виде графиков (эффективность алгоритма, время работы) и значений f* показателей (ЦФ, число магистралей, длина цепей и т.п.). Программа написана на языке программирования Borland С++ 5.02 для ОС Windows 95/98. Для ее запуска потребуется IBM™ — совместимый компьютер класса Pentium™, с частотой 120МГц, объемом оперативной памяти - 32МБ.

7. Проведенные исследования показали эффективность предложенного комплекса алгоритмов. Результаты генетического алгоритма не хуже чем у tfi аналогов, таких как: Griddles, Mighty, YACR2 и др. Применение разработанных алгоритмов и методик позволяет уменьшить сроки проектирования СБИС на 5-10%.

1. J. P. Cohoon, J. Karro, J. Lienig "Evolutionary Algorithms for the Physical Design of VLS1.Circuits," Advances in Evolutionary Computing: Theory and Applications, Ghosh, A., Tsutsui, S. (eds.) Springer Verlag, London, 2003. pp. 683-712.

2. Goldberg D.E. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley Publishing Company Inc., Massachusetts, 1989. 412p.

3. Shervani N. Algorithms for VLSI physical design automation. USA, Kluwer Academy Publisher, 1995.-538 p.

4. Бородулин A.B., Курейчик B.M., Эволюционный алгоритм канальной ^ трассировки топологии СБИС, Журнал «Известия вузов. Электроника»,1. Москва, №5/2002. 57-63с.

5. Tseng Н.Р., Sechen С. A gridless multi-layer channel router based on a combined constraint graph and tile expansion approach. Department of Electrical Engineering, Box 352500, University of Washington, Seattle, WA 98195, ISPD, 1996.-P. 210-217.

6. Yoshimura Т., Kuh E.S. Efficient algorithms for channel routing // IEEE Trans. Computer Aided Design Integrated Circuits & Syst. 1982. -Vol. 1, № 1. - P. 25-35.

7. Howard H. Chen and Ernest S. Kuh. Glitter: A Gridless Variable Width Channel Router., IEEE Transaction on Computer-Aided Design, Vol. CAD-5, No. 4, October 1986. pp. 459-465.

8. H. H. Chen. Trigger: A three layer gridless channel router. Proceedings of IEEE International Conference on CAD, 1986. pp. 196-199.

9. Лебедев Б.К., Полупанов A.A. Генетический алгоритм компоновки с элементами самоорганизации. Известия ТРТУ №3(26), Интеллектуальные САПР. Таганрог, 2002. с. 62.

10. Курейчик В.М. Генетические алгоритмы. Монография. Таганрог: ТРТУ, 1998.-242 с.

11. И.Бородулин А.В., Хайрова Е.Е., Экспертная подсистема управления генетическим поиском в канальной трассировке. Известия ТРТУ №3., Таганрог, 1999.145-151с.

12. Davidenko V.N., Kureichik V.M., and Miagkikh V.V. Genetic Algorithm for Restrictive Channel Routing Problem. Proc. of the 7th International Conf. on Genetic Algorithms, M. Kaufmann Publisher, San Mateo, California, 1997. pp. 636-642.

13. Давиденко B.H. Алгоритм задачи канальной трассировки, основанный на методе генетического поиска. Известия ТРТУ, № 3, Таганрог, 1996. стр.1. X 46-49.

14. Давиденко В.Н. Генетический алгоритм канальной трассировки. Межведомственный тематический научный сборник «Интеллектуальные САПР», выпуск 5, Таганрог, 1995. с. 155-156.

15. Полупанов А А. Адаптивная архитектура генетического поиска // Перспективные информационные технологии и интеллектуальные системы №3(11), Таганрог, 2002. с. 49-55

16. Давиденко В.Н. Надъячеечная трассировка на основе генетических процедур. Известия ТРТУ № 2, Таганрог, 1998.

17. 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.

18. Курейчик B.M., Лебедев Б.К., Лях A.B., Проблемы эволюционной адаптации в САПР. Новинтех, № 3,1991.

19. Курейчик В.В. Автореферат кандидатской диссертации "Исследование и разработка генетических алгоритмов для конструкторского синтеза элементов СБИС".- Таганрог.: ТРТУ, 1995. 16 с.

20. Курейчик В.М., Зинченко Л.А. Эволюционное моделирование с динамическим изменением параметров. Труды VII национальной конференции по искусственному интеллекту, М., Физматлит, 2000. с. 516—t* 523.

21. Бородулин А.В., Алгоритм и программа трассировки цепей различной ширины, V Всероссийская научная конференция студентов и аспирантов. Техническая кибернетика, радиоэлектроника и системы управления. КРЭС-2000, Таганрог, 2000. с.97.

22. Свидетельство «Программа генетической трассировки цепей в канальной области СБИС (ПГТК)». Авторы Курейчик В.М., Бородулин А.В., №2004610401, 9.02.2004г.

23. Т. G. Szymanski. Dogleg channel routing is NP-complete. IEEE Transactionson Computer-Aided Design, CAD 4:31-41, January 1985.

24. Бородулин A.B. Алгоритм трассировки цепей различной ширины, Перспективные информационные технологии и интеллектуальные системы № 1/2001, Таганрог. 114-121с.

25. Гладков JI.A., Зинченко JI.A., Курейчик В.В., Курейчик В.М., Лебедев Б.К., Нужнов Е.В., Сорокин С.Н. Методы генетического поиска: Научное издание / Под редакцией В.М. Курейчика. Таганрог: Изд-во ТРТУ, 2002.122 с.

26. Burstein М. Channel routing, Layout Design and Verification // Elsevier Science. 1986.-P. 133-167.

27. Sangiovarni-Vincenteli et al. A new gridless channel router: Yet Another Channel Router the second YACR2. Proceeding of International Conference on Computer-Aided Design (ICCAD). 1984. - P. 72-75.

28. Kureichik V., Davidenko V., Miagkikh V. Genetic algorithms for restrictive channel routing // Proc. of the 7-th International conference on Genetic Algorithms. USA, MSU, East Lansing, 1997. - P. 636-542.

29. Давиденко В.Н. Алгоритм волновой трассировки цепей произвольной ширины. Известия ТРТУ, №3, Таганрог, 1997. стр. 148-151.

30. Potts J.C., Giddens Т., Yadav S. The Development and Evaluation of a t^- improved Genetic Algorithm Based on Migration and Artificial Selection //

31. EE Transactions on systems, man, and cybernetics. 1994. -Vol. 24, № 1, January. - P. 73-86.

32. Лебедев Б.К. Методы поисковой адаптации в задачах автоматизированного проектирования СБИС: Монография. Таганрог: изд-во ТРТУ, 2000.192 с.

33. Курейчик В.М. Математическое обеспечение КТП с применение САПР. М., Радио и связь, 1990. с.352.

34. Лебедев Б.К. Разнесение соединений по слоям на основе коллективной адаптации. Известия ТРТУ №3., Таганрог, 1999. с. 176-186.

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

36. Автоматизированное конструирование монтажных плат РЭА: Справочник специалиста. Под редакцией Л.П. Рябова., М., Радио и связь, 1986. 192с.

37. В.Н. Варшавский, Д.А. Поспелов. Оркестр играет без дирижера. М., Главная редакция физико-математической литературы., 1984. 208 с.

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

39. Курейчик В.М., Калашников В.А., Лебедев Б.К. Автоматизация проектирования печатных плат., Ростов, РГУ, 1984. 80с.

40. Эволюционная эпистемология и логика социальных наук: Карл Поппер и ^ его критики. Под. ред. В.Н. Садовского, М. Эдиториал УРСС, 2000г. 464с.

41. Schnecke V., Vornberger О. A Genetic Algorithms for VLSI Design Automation. Proc. of the Second Intl. Conf. Adaptive Computing in Engineering, Design and Control, Plymouth, UK, March 1996. pp. 53-58.

42. James Reed, Alberto Sangiovarni-Vincenteli, Mauro Santomauro. A New Symbolic Channel Router: YACR2., IEEE Transactions on Computer-Aided Design, Vol. CAD-4, No. 3, JULY, 1985.

43. Rostam Joobbani, D.P. Siewiorek. WEAVER: A Knowledge-Based Routing Expert., IEEE Design & Test, February, 1986.

44. Бородулин A.B., Курейчик B.M., Новая архитектура генетического алгоритма канальной трассировки, Перспективные информационные технологии. №2/2002, Таганрог, 71-79с.

45. Hyuchul Shin and Alberto Sangiovarni-Vincenteli. MIGHTY: a rip-up and reroute detailed router., Proceeding of International Conference on Computer-Aided Design (ICCAD), 1986. pp. 2-5.

46. Ronald I. Greenberg, Alexander T. Ishii and Alberto L. Sangiovarni-Vincenteli. Mulch: A multi-layer channel router using one, two and three layer partitions., Proceeding of International Conference on Computer-Aided Design (ICCAD) 1988. pp. 88-91.

47. D. Richards. Complexity of single-layer routing. IEEE Transactions on Computers, c-33(3), March 1984. pp. 286-288.

48. W. Cao. "Cross point assignment," IEEE CAD vol. 14, pp. 69-78, Mar., 1995.

49. C. Chiang "global routing based on Steiner minimax trees," IEEE Trans CAD, vol. 9, Dec. 1990.

50. R. C. Carden, IV and C.K. Cheng, "A global router using an efficientiLapproximate multicommodity multiterminal flow algorithm," 28 CAD Conf., 1991.

51. Быстродействующие матричные БИС и СБИС. Теория и проектирование. Под общей редакцией Б. Н. Файзулаева и И.П. Шагурина. М., Радио и связь, 1989.

52. Сквозное автоматизированное проектирование микроэлектронной аппаратуры / З.Ю. Готра, В.В. Григорьев, Л.М. Смеркло, В.М. Эйдельнант. М, Радио и связь, 1989. с.280.

53. Автоматизация проектирования БИС. Под ред. Г.Г. Казенова, М., Высшая школа, 1990.

54. Douglas Braun et al. Chameleon: a new multi-layer channel router., Proceeding of 23rd Design ACM/IEEE Automation Conference 1986, pp. 495-502.

55. Tai-Tsung Ho et al. A general greedy channel routing algorithm., IEEE Transaction on Computer-Aided Design, Vol. 10, No. 2, pp. 204-211, February, 1991.

56. Margarine, A. Romane, A. De Gloria, F. Curatelli and P. Antognetti. A tile-expansion router., IEEE Transaction on Computer-Aided Design, Vol. CAD-6, No. 4, pp. 507-517, July 1987.

57. N J. Nilsson, Principles of artificial intelligence, Englewood Cliffs, NJ, 1980. pp. 53-94.

58. Holland J. H., Adaptation in Natural and Artificial Systems: An Introductory Analysis with Application to Biology, Control, and Artificial Intelligence. University of Michigan, 1975.

59. Бородулин A.B., Структура хромосомы в генетическом алгоритме канальной трассировки. Новые информационные технологии. Разработка и аспекты применения. Таганрог, 2001. с.96.

60. A. Hashimoto and J. Stevens. Wire routing by optimization channel assignment within large apertures. Proceedings of the 8th Design Automation Workshop, 1971. pp. 155-163.

61. M. Tompa. An optimal solution to a wire-routing problem. Journal of Computer and System Sciences, 23(2), October 1981. pp. 127-150.

62. A. Siegel and D. Dolev. The separation for general singe-layer wiring barriers. Proceedings of Carnegie-Melon Conference on VLSI systems and computations, October 1981. pp. 143-152.

63. F. M. Maley, Single-layer wire routing and compaction. The MIT press, 1990.

64. С. E. Leiserson and R. Y. Pinter. Optimal placement for river routing. SIAM Journal of Computing, 12, No 3, August 1983. pp. 447-462.

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

66. Разработка САПР. Под ред. А.В. Петрова. М., Высшая школа, 1990.

67. Абрайтис JI.A. Автоматизация проектирования топологии цифровых интегральных микросхем. М., Радио и связь, 1985. 200 с.

68. М. Burstein and R. Pelavin. Hierarchical channel router. Proceedings of 20-th ACM/IEEE Design Automation Conference, 1983. pp. 519-597.

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

70. Taniguchi N., Liu. X., Sakamoto. A. and Shimamoto. Т. An approach to channel routing using genetic algorithms" Bulletin of Faculty of Engineering, Tokushima University, No. 38, 1993. pp.99-112.

71. Goldberg D.E., Kalyanmoy D. A comparative analysis of selection schemes used in genetic algorithms. In Rawlings G.(Ed.). Foundations of Genetic Algorithms. Indiana University. Mogan Kaufmann, San Mateo, С A, 1991.

72. Syswerda G. Uniform Crossover in Genetic Algorithms. Proc. of the 3-rd Conf. on Genetic Algorithms, M. Kaufmann Publisher, San Mateo, California, 1989. p. 2-9.

73. Батищев Д.И. Генетические алгоритмы решения экстремальных задач: Учебное пособие. Воронеж, 1995. 69 с.

74. Автоматизированное проектирование СБИС на базовых кристаллах / А.И. Петренко, В.М. Лошаков, А. Тительбаум и др. М., Радио и связь, 1988.

75. Gary W. Clow A global routing algorithm for general cells., Proceeding of ACM/IEEE 21st Design Automation Conference, pp. 54-51.

76. Chung-Kuan Cheng and David N. Deutsch. Improved channel routing by via minimization and shifting., Proceeding of ACM/IEEE 25th Design Automation Conference, 1988. pp. 677-680.

77. Вермишев Ю.Х. Основы автоматизации проектирования. М., Радио и связь, 1988.

78. Арнуш Крейг. Borland С++ 5: Освой самостоятельно: Пер с англ., М.: Восточная Книжная Компания, 1997. 720 с.

79. Н.В. Чичварин. Экспертные компоненты САПР., Москва, Машиностроение, 1991. 240с.

80. Lin Y., Hsu Y., Tsai F. A detailed router based on simulated evolution. IEEE Trans. Computer Aided Design, № 5, 1988. pp. 38-41.

81. Казенов Г.Г, Марченко A.M. Абстрактный эволюционный алгоритм синтеза СБИС. Известия ТРТУ, №3, Таганрог, 1996. стр. 112.

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

83. Деньдобренко Б.П., Малика A.C. Автоматизация проектирования радиоэлектронной аппаратуры. М., Высш. шк., 1980. 384 с.

84. Системы автоматизированного проектирования в радиоэлектронике. Под редакцией Норенкова И.П. Справочник. Москва, Радио и связь, 1986.

85. Харари Ф. Теория графов. М.: Мир, 1973. 300 е., ил.

86. Курейчик В.М. Генетические алгоритмы и их применение в САПР. Интеллектуальные САПР, меж. сб., Таганрог, 1995. стр. 7-11.

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

88. Ляпунова Н.А. О мутациях случайных и направленных. Наука и жизнь. 1989 г. №8 с. 60-61.

89. Лебедев Б.К. Канальная трассировка на основе генетических процедур. Известия ТРТУ, №3, Таганрог, 1997. с. 53-60.

90. Курейчик В.М., Глушань В.М., Щербаков Л.И. Комбинаторные аппаратные модели и алгоритмы в САПР. М.: Радио и связь, 1990.216 с.

91. Мину М. Математическое программирование. М., Наука, 1990.

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

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

94. Страуструп Б. Язык программирования Си++. М., Радио и связь, 1991. 352 с.

95. Подбельский В.В. Язык Си++: Учебное пособие. М., Финансы и статистика, 1995. 560 с.

96. Голуб А.И. С и С++. Правила программирования. М., БИНОМ, 1996. 272 с.

97. Бентли Д. Жемчужины творчества программистов / пер. с англ. М., Радио и связь, 1990. 244 с.

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

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

100. Митропольский А.К. Техника статистических вычислений. М., Наука., 1971.576 е.: ил.

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

102. Адлер Ю.П. Планирование эксперимента при поиске оптимальных условий. М.: Наука, 1971. 283 е.: ил.

103. Бронштейн И.Н., Семендяев К.А. Справочник по математике для инженеров и учащихся втузов. М.: Наука, 1986. 544 е.: ил.