Введение к работе
Актуальность работы. В настоящее время в связи с развитием технологии изготовления СБИС возник ряд новых тенденций при их проектировании. Уменьшение размеров элементов и временных задержек сигналов в них привело к тому, что более 60% общей временной задержки приходится на задержки в межсоединениях. Рост размера области, отводимой для межсоединений, опережает рост размера области, предназначенной для активных элементов. Эти тенденции ведут к возрастанию значения трассировки при конструкторском проектировании, требуют разработки новых методов для получения более качественных решений на этом этапе.
В связи с большой сложностью и размерностью задачи трассировки при проектировании используется иерархический подход к трассировке. Задача трассировки разбивается на глобальную и детальную трассировки. Глобальная трассировка заключается в разбиении области трассировки на подобласти и распределении соединений по подобластям. Детальная трассировка заключается в реализации соединений в каждой подобласти.
Разработка методов и алгоритмов решения задач глобальной трассировки является актуальной. Это связано в первую очередь с тем, что эти задачи относятся к классу NP. Появление новых, более современных средств вычислительной техники, а также возникающие возможности технологии создания интегральных схем являются побудительной причиной разработки новых алгоритмов и методов решения задач трассировки. Одним из актуальных подходов к созданию новых эффективных средств проектирования является использование методов эволюционного моделирования и генетического поиска.
Целью диссертационной работы является разработка и исследование генетических методов и алгоритмов распределения трассируемых соединений СБИС по слоям.
Для достижения поставленной цели были решены следующие
задачи:
-
Разработка структурной схемы процесса генетического поиска для задач расслоения топологии СБИС.
-
Разработка процедуры формирования популяции и селективного отбора.
-
Разработка процедур оценки качества .
-
Разработка методов кодирования и декодирования хромосом.
-
Исследование генетических алгоритмов распределения топологии трассировки.
Для решения поставленных задач использовались следующие методы исследований: элементы теории множеств, элементы теории алгоритмов, элементы теории генетического поиска.
Научная новизна диссертационной работы заключается в разработке:
архитектуры генетического поиска, ориентированной на решение задач распределения трассируемых соединений по слоям;
методики решения задачи расслоения топологии; модифицированных генетических операторов, ориентированных на решение задач трассировки. Практическую ценность работы представляют:
Генетический алгоритм и комплекс программ распределения соединений топологии СБИС.
Реализация результатов работы. Основные теоретические и практические результаты диссертационной работы: использование в госбюджетных работах "Разработка теории и методов построения интегрированных САПР БИС с элементами искусственного интеллекта" (№ ГР 01.9.50004188) /'Разработка методов и моделей генетического поиска в интеллектуальных САПР" выполненной в рамках государственной научно-технической программы "Университеты России" (1995-1996 г.г.), хоздоговорной работе "Учебно-методический комплекс. Применение экспертных систем в инженерной практике" выполненной в рамках научно-технической программы
"Компьютеризация образования" (1995 г.), "Исследование генетических методов оптимизации" (№ ГР 02.9.70001838).
Результаты работы используются в МГТИ (г. Майкоп). Кроме того материалы диссертации использованы в учебном процессе на кафедре САПР ТРТУ при чтении лекций и в цикле лабораторных работ по курсу "Методы генетического поиска".
Апробация основных теоретических и практических результатов работы проводилась на научных семинарах "Генетические алгоритмы" (осень 1994 - весна 1995 г. г. ТРТУ), Всероссийской научно-технической конференции студентов и аспирантов "Новые информационные технологии. Информационное, программное и аппаратное обеспечение" (г. Таганрог 1995 - 97 г.), Всероссийской научно-технической конференции с участием зарубежных представителей "Интеллектуальные САПР" (г. Геленджик 1994-98 г.).
Публикации. Результаты диссертации отражены в 9 печатных работах.
Структура и объем диссертационной работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложений. Работа содержит 133 страниц , включая 33 рисунка, 10 таблиц, список литературы из 102 наименований, 8 стр. приложений и актов об использовании.
