Введение к работе
Актуальность темы. Современный этап развития человеческой цивилизации, характеризующийся высокими темпами роста развития науки и техники, нелегко представить без использования изделий микроэлектронной промышленности в повседневной жизни Использование различных достижений микроэлектроники при производстве интегральных схем (ИС), больших ИС (БИС), сверхбольших ИС (СБИС), суперкристаллов, обуславливает повышение основных характеристик электронных вычислительных средств (ЭВС) проектируемых на их основе, например, снижаются массогабаритные показатели, уменьшаются потребляемая и рассеиваемая мощности, повышаются быстродействие и надежность Современные ЭВС, такие как, персональные компьютеры, оборудование вычислительных и специальных пользовательских сетей, контроллеры и другие управляющие устройства и системы содержат в своем составе десятки, а иногда и сотни СБИС Однако к характеристикам ЭВС предъявляются неоднозначные требования в зависимости от класса и назначения аппаратуры, использующей СБИС и суперкристаллы Какая-то из характеристик или их совокупность могут быть определяющими, тогда как требования к остальным снижаются
Применение на этапе проектирования САПР способствует повышению степени интеграции СБИС на уровне узлов, блоков и всей системы в целом Сегодня СБИС способны выполнять сложнейшие наборы функции, а геометрические размеры транзисторов сократились до 0 18 мкм и меньше Неуклонное повышение степени интеграции СБИС привело к тому, что в них более 60% общей временной задержки сигнала приходится на задержки в межсоединениях Рост размера области, отводимой для межсоединений, опережает рост размера области, предназначенной для активных элементов В чипе, содержащем 10 миллионов транзисторов и использующем 4 слоя металлизации, около 40% площади отводится под межсоединения
Сейчас, на всех стадиях проектирования топологии СБИС интенсивно используют средства автоматизации проектирования (САПР) и многие фазы могут быть полностью или частично автоматизированы Важнейшим этапом в цикле проектирования СБИС, является этап конструкторского проектирования, на котором решаются задачи разбиения, планирования, размещения, трассировки, упаковки, верификации
Поскольку схема может содержать несколько миллионов транзисторов, то невозможно спроектировать топологию всей схемы целиком в связи с ограниченными возможностями вычислительных средств, поэтому схема разбивается группировкой компонентов в блоки В результате разбиения формируется множество блоков и множество соединений между блоками
В связи с большой сложностью и размерностью задач конструкторского проектирования, а также с возникновением новых тенденций в технологии изготовления СБИС, появляется необходимость в разработке новых направлений, методик, алгоритмов для решения данного класса задач
В этой связи диссертационная работа посвящена решению актуальной и важной научно-технической проблемы разработке и исследованию новых и развитию существующих алгоритмов решения задачи разбиения схемы, обеспечивающих не только достижение требуемых результатов, но и поднимающих процесс исследования на высокий уровень, не требующий от ученых-исследователей навыков в области программирования
Данная работа является развитием результатов исследований, проводимых на кафедре САПР Таганрогского технологического института Южного федерального университета в рамках приоритетного национального проекта «Образование», а также аналитической ведомственной целевой программы «Развитие научного потенциала высшей школы» (2006 - 2008 гг) на тему «Разработка бионических методов и принципов поиска оптимальных решений при проектировании»
Цель диссертационной работы состоит в разработке и исследовании комплекного гибридного генетического алгоритма разбиения схем с учетом числа межузловых связей и общей временной задержки Для достижения поставленной цели в работе были решены следующие основные задачи
Модифицирован аддитивный критерий для опенки качества решения задачи разбиения с учетом числа внешних связей и временной задержке сигнала
Построена архитектура генетического поиска для решения задачи разбиения схем
Разработаны способы представления разбиения схем, учитывающие специфику задачи Предложенные структуры, кодирующие альтернативные решения, реализованы с использованием гомологичных хромосом и отличаются тем, что кодирование и декодирование имеет линейную сложность, а использование генетических операторов не приводит к образованию недопустимых решений
Разработаны гибридные генетические процедуры, процедура локального улучшения, алгоритм адаптации множества виртуальных популяций и отдельных решений
Построены модифицированные генетические операторы
В качестве методов решения поставленных задач в диссертационной работе использовались элементы теорий множеств, алгоритмов, ірафов, а также методы и средства эволюционного моделирования, генетического поиска, теории вычислительных систем, параллельного и объектно-ориентированного программирования
Научная новизна работы заключается в решении задачи разбиения схем с использованием гибридных генетических процедур В работе
Построена архитектура генетического поиска для решения задачи разбиения схем
Разработаны и теоретически обоснованы новые технологии и механизмы генетического поиска, повышающие его эффективность - распараллеливание
процесса поиска на базе виртуального набора популяций, адаптация виртуального набора популяций, чередование генетических операторов и типов хромосом в процессе поиска.
Разработаны и исследованы с учетом специфики решаемых задач, с ориентацией на большие размерности принципы кодирования решений в виде структурированных и многохромосомных представлений, отличающихся гомологичностью, простотой, линейной оценкой трудоемкости для задачи разбиения схем
Разработаны механизмы преодоления алгоритмом «локальных ям», и увеличения скорости поиска на основе эвристических методов и метода моделирования отжига
К числу наиболее важных научных результатов диссертации относятся
новая архитектура комплексного гибридного генетического алгоритма для решения задачи разбиения схем,
принципы кодирования решений и структуры хромосом, учитывающие специфику решаемых задач с ориентацией на задачи большей размерности, отличающиеся гомологичностью, линейными оценками пространственной и временной сложное! и и имеющих широкую сферу применения,
новые технологии и механизмы генетического поиска на базе адаптируемого виртуального набора популяций с альтернативными структурами хромосом и генетических операторов,
новые технологии и средства повышения эффективности выхода из "локальных ям" и снижения общего времени поиска квазионтимальных решений,
новые и усовершенствованные операторы генетического поиска обеспечивающие снижение времени поиска
Практическая ценность работы заключается в реализации программного комплекса «Partitioning», использование которого позволяет на 15-20% ускорить процесс решения задачи разбиения схем, при этом получать решения, не уступающие по качеству по сравнению с существующими аналогами, благодаря использованию новых способов представления решений в задаче разбиения, а так же модифицированной архитектуре генетического поиска Данная среда позволяет автоматизировать процесс разбиения, сделать его доступным для специалистов различных областей науки, не обладающих навыками программирования
Реализация и внедрение результатов работы. Основные теоретические и практические результаты диссертационной работы использованы в госбюджетных научно-исследовательских работах Технологического института Южного федерального университета «Разработка теории и принципов построения интеллектуальных систем принятия решений при проектировании на
основе квантовых вычислений и бионических методов поиска» и «Разработка бионических методов и принципов поиска оптимальных решений при проектировании», а так же в рамках приоритетного национального проекта «Образование»
Материалы диссертации использованы в учебном процессе на кафедре САПР ТТИ ЮФУ при преподавании следующих дисциплин «Методы оптимизации», «Эволюционное моделирование и генетические алгоритмы», «Автоматизация конструкторского и технологического проектирования»
Апробация основных теоретических и практических результатов работы. Результаты диссертации докладывались и обсуждались на Всероссийских и Международных научно-технических конференциях «Интеллектуальные САПР», (г. Таганрог, 2003 - 2005 гг), VII Всероссийская научная конференция студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления», (г Таганрог, 2004г), II Всероссийская научная конференции молодых ученых, аспирантов и студентов «Информационные технологии, системный анализ и управление», (г. Таганрог, 2004 г), III Всероссийская научная конференции молодых ученых, аспирантов и студентов «Информационные технологии, системный анализ и управление», (г Таганрої, 2005 г), Международная научно-техническая конференция «Интеллектуальные САПР», (г Таганрог, 2006 г )
Получено свидетельство об официальной регистрации программы для ЭВМ
Публикации. По теме диссертационной работы опубликовано 7 печатных работ, сделано 2 доклада на Всероссийских и Международных научно-технических конференциях
Структура и объем работы. Диссертационная работа состоит из введения, четырех глав и заключения, изложенных па 139 страницах, содержит 38 рисунок, 17 таблицы, 103 наименований библиографии и приложения
Похожие диссертации на Разработка и исследование комплексного гибридного генетического алгоритма разбиения схем
