Разработка и исследование интегрированных алгоритмов разбиения СБИС на фрагменты

• Автор: Болоцкова, Ирина Андреевна
• Шифр специальности: 05.13.12, 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Таганрог
• Количество страниц: 156 с. : ил.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ

1. АНАЛИЗ АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧИ РАЗБИЕНИЯ

СХЕМ ЭВА

1.1. Постановка задачи разбиения схем

1.2. Классификация методов и алгоритмов решения задачи разбиения

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

2. АНАЛИЗ И ВЫБОР МОДЕЛЕЙ И АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧИ.

2.1. Анализ и выбор математической модели.

2.1.1. Виды математических моделей.

2.1.2. Графовые модели.

2.1.3. Модели на основе специальных графов.
2.1.4. Гиперграфовые и ультраграфовые модели.
2.2. Внутренняя и внешняя устойчивость.
2.3. Анализ алгоритмов определения независимых и доминирующих подмножеств.
2.3.1. Алгоритм полного перебора.
2.3.2. Алгоритм систематического перебора
2.3.3 Последовательный алгоритм
2.3.4. Методы, основанные на логических произведениях
2.3.5. Векторный способ нахождения вершинного и реберного покрытий.
2.4. Выводы и рекомендации.
3. РАЗРАБОТКА ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ ВЫДЕЛЕНИЯ ЯДЕР ГРАФА.
3.1.Анализ существующих алгоритмов решения оптимизационных задач
3.1.1. Методы решения оптимизационных задач.
3.1.2. Основные парадигмы генетических алгоритмов.
3.1.3. Структура генетического алгоритма
3.2. Разработка итерационного алгоритма выделения
экстремальных подмножеств.
3.2.1. Алгоритм Поиск в глубину.
3.2.2. Алгоритм Поиск в глубину с отсечением
3.3. Разработка простого генетического алгоритма выделения экстремальных подмножеств.
3.3.1. Разработка методики кодирования
3.3.2. Подбор генетических операторов.
3.3.3. Разработка структуры простого генетического алгоритма построения экстремальных подмножеств
3.4. Разработка модифицированного генетического алгоритма выделения независимых подмножеств в графе.
3.4.1. Разработка структуры хромосом
3.4.2. Стратегия формирования начальной популяции.
3.4.3. Разработка генетических операторов.
3.4.4. Разработка схемы генетического поиска
3.5. Разработка эволюционного алгоритма выделения экстремальных подмножеств в графе.
3.5.1. Алгоритм выделения доминирующих подмножеств
3.5.2. Алгоритм выделения независимых подмножеств
3.6. Теоретические оценки алгоритмов
3.7. Выводы и рекомендации
4. ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ
4.1. Итерационный алгоритм нахождения экстремальных
подмножеств
4.1.1. Анализ временной сложности алгоритма.
4.1.2. Описание программы.
4.1.3. Экспериментальные исследования.
4.2. Простой генетический алгоритм нахождения экстремальных подмножеств
4.2.1. Описание интерфейса
4.2.2. Результаты экспериментальных исследований
4.2.3. Анализ временной сложности.
4.3. Модифицированный генетический алгоритм выделения экстремальных подмножеств
4.3.1. Описание интерфейса
4.3.2. Экспериментальные исследования.
4.4. Эволюционный алгоритм нахождения экстремальных подмножеств в графе
4.4.1. Описание интерфейса программы
4.4.2. Результаты экспериментальных исследований
4.5. Выводы и рекомендации
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА


Российского фонда фундаментальных исследований «Разработка теории и принципов эволюционного проектирования на основе многоагентных подходов» (№ 5), «Эволюционное проектирование с адаптацией» (№ 4), «Генетические алгоритмы в интеллектуальных САПР» (№ 0), х/д между ТРТУ и Российским научно-исследовательским институтом информационных технологий и систем автоматизированного проектирования (ГУ Рос НИИ ИТ и АП) № 1 «Разработка эволюционных алгоритмов на фафах с динамическими параметрами» и научно-исследовательской работе «Разработка интеллектуальных систем проектирования и технологической подготовки производства на основе эволюционной адаптации» (№ ГР 7), выполняемой в рамках научно-технической программы Министерства образования РФ «Научные исследования высшей школы по приоритетным направлениям науки и техники». Кроме того, материалы диссертации использованы в учебном процессе на кафедре САПР ТРТУ при чтении лекций, а также лабораторных и практических занятиях по курсам «Эволюционное моделирование и генетические алгоритмы», «Методы оптимизации и генетические алгоритмы» и «Математические основы дискретной техники». АПРОБАЦИЯ основных теоретических и практических результатов работы проводилась на научных семинарах кафедры САПР "Генетические алгоритмы" (с по гг. Таганрог, , гг. Всероссийской научной конференции молодых ученых и аспирантов (г. Таганрог, , , г. Всероссийской научной конференции молодых учёных и аспирантов «Новые информационные технологии. Разработка и аспекты применения» (г. Таганрог, , гг. Интеллектуальные САПР» (г. Геленджик, - гг. Международной научной конференции «Искусственные интеллекиуальные системы» (г. Геленджик, - гг. ПУБЛИКАЦИИ. Результаты диссертации отражены в печатных работах. СТРУКТУРА И ОБЪЕМ ДИССЕРТАЦИОННОЙ РАБОТЫ. Диссертационная работа состоит из введения, четырех глав, заключения, и списка использованных источников. Работа содержит 7 стр. СОДЕРЖАНИЕ РАБОТЫ. ВО ВВЕДЕНИИ обоснована актуальность темы диссертационной работы, дано общее описание выполненной работы. В ПЕРВОЙ ГЛАВЕ приведена постановка задачи разбиения схем при проектировании СБИС по критерию максимизации (минимизации) суммарного количества межблочных связей. Рассмотрены существующие алгоритмы и методы решения задачи разбиения схем при проектировании СБИС, выявлены их достоинства и недостатки. ВО ВТОРОЙ ГЛАВЕ проведен сравнительный анализ существующих математических моделей схем ЭВА и выбрана математическая модель, позволяющая интерпретировать задачу разбиения как задачу построения независимых и доминирующих подмножеств. Сформулирована постановка задачи определения независимых и доминирующих подмножеств для логических схем, представленных графовыми и гиперграфовыми математическими моделями и приведены основные теоретические положения и критерии, позволяющие оценить сложность рассматриваемой проблемы. Проведен анализ существующих методов и алгоритмов выделения независимых и доминирующих подмножеств в графовых и гиперграфовых математических моделях и определено место рассматриваемой задачи в процессе автоматизированного проектирования ЭВЛ. Выделены основные группы алгоритмов, а также их достоинства, недостатки и перспективы развития. Приведены оценки пространственной и временной сложности алгоритмов. В ТРЕТЬЕЙ ГЛАВЕ приведена краткая классификация методов оптимизации, показаны преимущества методов эволюционного моделирования и генетического поиска по сравнению с традиционными методами решения № - полных задач. Кратко проанализированы основные положения теории генетического поиска. На основе-анализа механизма эволюции предложен ряд подходов к использованию методов эволюционного моделирования и генетических алгоритмов для решения задачи построения независимых и доминирующих подмножеств в специальных графовых и гиперграфовых математических моделях. Предложена модифицированная форма представления исходных данных, позволяющая сократить объем требуемой памяти и ряд процедур построения начальной популяции и определения длины хромосом. Определена методика кодирования, учитывающая специфику решаемой задачи и позволяющая улучшить качество получаемых решений. Разработаны модификации генетических операторов, позволяющие учитывать особенности решаемой задачи. Предложены архитектура и принципы работы генетических алгоритмов выделения, независимых и доминирующих подмножеств, а также правила формирования популяции и отбора индивидов, сводящие к минимуму вероятность преждевременной сходимости. Определены теоретические оценки пространственной и временной сложности разработанных алгоритмов. На основе выполненного анализа ранее разработанных ГА даны рекомендации по настройке ГА и основных генетических операторов. В ЧЕТВЕРТОЙ ГЛАВЕ приведено описание экспериментальных исследований разработанных алгоритмов и программ.