Введение к работе
. Актуальность работы. Элементной базой ЭВМ новых поколений являются сверхбольшие сверхскоростные интегральные схемы (СБИС и ССБИС), содержащие миллионы транзисторов на кристалле. Создание высококачественных СБИС в короткие сроки и при сравнительно низких затратах требует постоянного совершенствования методов автоматизированного проектирования. Этап конструкторского проектирования СБИС включает следующие стадии: компоновка, размещение, трассировка. Ввиду огромной сложности трассировка решается в два этапа: сначала глобальная, а потом детальная. Очень важное значение для решения задачи детальной трассировки имеет порядок закрепления выводов за контактами. В пределах каждой подсхемы целью задач размещения, глобальной трассировки и перераспределения выводов является создание благоприятных условий для детальной трассировки.
Разработка методов и алгоритмов для этих задач актуальна. Это связано в первую очередь с тем, что эти задачи относятся к классу NP. Появление новых более современных средств вычислительной техники, а так же повышенные требования предъявляемые к проектируемым устройствам являются побудительной причиной разработки новых алгоритмов и методов решения этих задач. Одним из актуальных подходов к созданию новых эффективных средств проектирования является использование методов эволюционного моделирования и генетического поиска.
Целью диссертационной работы является разработка методов и алгоритмов размещения, глобальной трассировки, перераспределения выводов, позволяющих повысить плотность проектируемых СБИС.
Для достижения поставленной цели были выполнены следующие задачи:
1. Разработка структурной схемы процесса генетического поиска для задач размещения, глобальной трассировки и перераспределения выводов.
-
Разработка процедуры формирования популяции и селективного отбора.
-
Разработка процедур оценки качества (фитнесса).
-
Разработка структуры и методов кодирования и декодирования хромосом.
-
Разработка и модификация генетических операторов.
-
Исследование генетических алгоритмов размещения, глобальной трассировки и перераспределения выводов.
Методы исследования в диссертации основаны на использовании элементов теории множеств, элементов теории алгоритмов, элементов теории исследования операций, элементов генетики и генетического поиска.
Научная новизна диссертационной работы заключается в следующем:
а) Разработаны структуры генетического поиска для решения
задач размещения, глобальной трассировки, перераспределения
выводов, которые позволяет повысить качество решения за счет
случайно направленного поиска.
б) Разработаны новые структуры и принципы кодирования и
декодирования решений в виде хромосом для задач размещения,
глобальной трассировки, перераспределения выводов, исполь
зующие специфичные значения об этих задачах и позволяющие
использовать все механизмы природной генетики, исключающие
возникновение нарушений.
в) Разработаны новые и модифицированные проблемно - ори
ентированные генетические операторы и принципы формирова
ния и смены популяций, позволяющие осуществлять выход из
локальных оптимумов.
Практическую ценность работы представляют:
-
Генетический алгоритм и программа размещения.
-
Генетический алгоритм и программа глобальной трассировки.
-
Генетический алгоритм и программа перераспределения выводов.
Реализация результатов работы. Основные теоретические и практические результаты диссертационной работы использованы в госбюджетных работах «Разработка теории и методов построе-
ния интегрированных САПР БИС с элементами искусственного интеллекта» (№ ГР01.9.50004188 ), «Разработка методов и моделей генетического поиска в интеллектуальных САПР» выполненной в рамках государственной научно- технической программы «Университеты России» (1995- 1996 г.г.), хоздоговорной работе «Учебно- методический комплекс. Применение экспертных систем в инженерной практике» выполненной в рамках научно-технической программы «Компьютеризация образования» (1995 г.), «Исследование генетических методов оптимизации» (№ ГР 02970001838).
Результаты работы внедрены в НИИ МВС в качестве ПО САПР проектирования топологии СБИС.
Кроме того материалы диссертации использованы в учебном процессе на кафедре САПР ТРТУ при чтении лекции и в цикле лабораторных работ по курсу «Методы генетического поиска».
Апробация основных теоретических и практических результатов работы проводилась на научных семинарах: «Генетические алгоритмы» (осень 1994- весна 1997 г.г. ТРТУ), Всероссийской научно- технической конференции студентов и аспирантов «Новые информационные технологии. Информационное, программное и аппаратное обеспечение» (г. Таганрог 1995- 97 г.), Всероссийской научно- технической конференции с участием зарубежных представителей «Интеллектуальные САПР» (г. Геленджик 1994-97 г.).
Публикации. Результаты диссертации отображены в 10 печатных работах.
Структура и объем диссертационной работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложения. Работа содержит 168 страниц, включая 96 рисунков, 19 таблиц, список литературы из 103 наименований, приложения и акты об использовании.
