Введение к работе
Актуальность темы. В последнее время в связи с ростом числа элементов и увеличением степени интеграции все большее значение приобретают вопросы, связанные с разработкой эффективных методов и алгоритмов решения основных задач автоматизированного проектирования СБИС. Одной из важнейших задач конструкторского этапа автоматизированного проектирования СБИС является задача разбиения схем на фрагменты.
В настоящее время требуются системы с несколькими миллионами транзисторов, которые невозможно разработать с помощью существующих утилит проектирования логического и физического уровня. Разбиение разделяет систему на более мелкие управляемые компоненты. В виду большой сложности и размерности задачи, существующие алгоритмы разбиения не всегда обеспечивают нужное качество разбиения.
Для повышения эффективности и качества решения данной задачи предлагаются новые методы и алгоритмы, основанные на использовании случайных и случайно-направленных методов поиска. К таким методам относятся генетические и эволюционные алгоритмы. Разработанные алгоритмы позволят повысить качество получаемых решений. Для этого используются новые методы поиска решений, учитывающие знания о решаемой задаче. Качество решения задачи разбиения оказывает непосредственное влияние на результаты работы остальных задач конструкторского этапа проектирования, т.к. данная задача является начальной на конструкторском этапе.
В этой связи, тема работы, связанная с разработкой новых методов решения задачи разбиения схем на фрагменты является важной для науки и практики.
Цель диссертационной работы. Целью данной работы является разработка новых и модифицированных алгоритмов решения задачи разбиения схем с учетом временных задержек.
Методы исследования. Выполненная работа характеризуется комплексным подходом. Основу для проведения исследований составляют: теория САПР, графов, алгоритмов, эволюционного моделирования. Исследование эффективности разработанных алгоритмов осуществлялось с помощью вычислительных экспериментов.
Достоверность результатов. Достоверность результатов подтверждается корректным использованием методов математической статистики, положительными результатами применения разработанных алгоритмов, а также анализом результатов проведенных экспериментальных исследований.
Основные положения, выносимые на защиту.
1. Новая архитектура процесса разбиения схем, основанная на методах эволюционного моделирования и многоуровневой парадигме.
2. Новые и усовершенствованные механизмы генетического поиска: учет «времени жизни» хромосом в популяции, применение принципов Парето оптимизации и распараллеливание процесса поиска.
3. Новые и усовершенствованные методы свертки гиперграфа на основе алгоритмов сжатия гиперребер, агрегации фракталов, применяемые с целью уменьшения размерности задачи разбиения и получения начального решения.
4. Новый параллельный генетический алгоритм разбиения схем с учетом временных задержек для этапа начального разбиения многоуровневой архитектуры поиска.
5. Новый гибридный генетический алгоритм нахождения разбиения схем для этапа развертки схемы, использующий разработанную «жадную» эвристику улучшения разбиения с целью предупреждения преждевременной сходимости.
6. Новый проблемно-ориентированный генератор начальной популяции на основе получения оптимальных строительных блоков.
7. Усовершенствованные операторы генетического поиска на основе фигурных чисел, обеспечивающие уменьшение времени поиска.
Научная новизна работы.
1. Предложена новая многоуровневая архитектура процесса разбиения схем с учетом временных задержек на основе методов эволюционного моделирования.
2. Разработан модифицированный генетический алгоритм разбиения схем с учетом «времени жизни» хромосом в популяции. Введение нового параметра в генетический поиск позволяет варьировать размер популяции на каждой итерации.
3. Предложен модифицированный генетический алгоритм на основе модели эволюции Ч. Дарвина, использующий принципы Парето оптимизации.
4. Представлены новые и усовершенствованные алгоритмы свертки гиперграфа на основе нахождения сжатия гиперребер, агрегации фракталов.
5. Разработан новый параллельный генетический алгоритм разбиения схем с учетом временных задержек. Предложен новый гибридный генетический алгоритм разбиения схем, включающий в себя «жадную» эвристику улучшения разбиения.
6. Разработан новый проблемно-ориентированный генератор популяции на основе анализа матрицы инцидентности гиперграфа и получения строительных блоков, повышающих целевую функцию хромосомы. Представлены модифицированные генетические операторы на основе фигурных чисел, позволяющие уменьшить время поиска оптимального решения за счет сокращения пространства поиска.
Практическая ценность. Практическую ценность представляют:
1. Архитектура эволюционного поиска для решения задач разбиения схем на фрагменты с учетом временных задержек.
2. Усовершенствованные операторы генетического поиска для решения задачи разбиения схем.
3. Программный комплекс «PGAComplex» решения задачи разбиения схем с учетом временных задержек.
Реализация результатов работы. Результаты работы внедрены в научно-исследовательских работах, выполняемых на кафедре САПР ТТИ ЮФУ.
Апробация работы. Основные результаты диссертационной работы обсуждались и были одобрены на Всероссийских научно-технических конференциях «Проблемы разработки перспективных микроэлектронных систем» (2005-2006 гг.), Международных научно-технических конференциях «Интеллектуальные САПР» (п. Дивноморское, 2005 - 2007 гг.), международной конференции «Интеллектуальные системы (IEEE AIS’06)» (п. Дивноморское, 2005г.), международной молодежной научно-технической конференции "Интеллектуальные системы в науке, технике, образовании, бизнесе" (п. Дивноморское, 2007 г.), IV-й Международной научно-практической конференции «Интегрированные модели и мягкие вычисления в искусственном интеллекте»(г. Коломна, 2007 г.), .
Публикации. Результаты диссертации отражены в 9 печатных работах.
Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы. Работа содержит 155 страниц, включая 55 рисунков, 15 таблиц, список литературы из 106 наименований, 5 страниц приложений с актами об использовании работы.
