Разработка и исследование методов планирования кристалла СБИС на основе эволюционной адаптации

• Автор: Лебедев, Владимир Борисович
• Шифр специальности: 05.13.12
• Научная степень: Кандидатская
• Год защиты: 2003
• Место защиты: Таганрог
• Количество страниц: 145 с. : ил

СОДЕРЖАНИЕ
Введение

1.Проблемы, методы, состояние и практика решения задачи планирования кристалла СБИС

1.1 .Введение в проблему.

1.2. Анализ существующих методов и подходов к задаче планирования

1.2.1. Планирование, основанное на целочисленном программировании.

1.2.2 Прямоугольная дуализация.

1.2.3. Методы планирования, основанные на иерархическом дереве

1.2.4. Планирование, основанное на ограничениях

1.3. Методы оптимизации при решении задач проектирования СБИС

1.4. Выводы
2.Разработка алгоритмов и моделей поисковой адаптации для решения задачи планирования кристалла СБИС
2.1. Проблемная формулировка, термины и определения
2.2. Формирование пространства решений.
2.3. Формирование плана методом свертки
2.4. Организация поисковой процедуры на основе коллективной адаптации при планировании кристалла СБИС с изменяющейся ориентацией блоков.
2.5. Организация поисковой процедуры на основе коллективной адаптации при планировании кристалла СБИС с изменяющимися размерами блоков
2.6. Выводы
3. Планирование СБИС на основе многоуровневой эволюции.
3.1. Основные задачи раздела.
3.2. Разработка принципов кодирования и декодирования хромосом при планировании на основе гильотинного разреза
3.3. Разработка представления и принципов кодирования дерева при планировании методом не гильотинного разреза.
3.4. Разработка представления и принципов кодирования парного дерева
разрезов
3.5. Стохастическое планирование СБИС
3.6. Генетические операторы при планировании.
3.7. Организация процедуры генетического поиска при планировании
3.8. Выводы.
4.Экспериментальные исследования разработанных алгоритмов.
4.1. Цель экспериментальных исследований
4.2. Исследование механизмов генетического поиска.
4.3. Исследование механизмов коллективной альтернативной адаптации
4.4. Исследование эффективности и сравнение результатов, получаемых представленными алгоритмами планирования кристалла СБИС.
4.5. Выводы.
Заключение.
Литература


В связи с этим становится актуальным вопрос поиска и разработки эффективных представлений, методов и алгоритмов для решения задачи планирования кристалла СБИС. Для достижения поставленной цели решались следующие задачи. Разработка программных средств на основе проведенных исследований для решения задачи планирования кристалла СБИС. ЭВА, РЭА и СБИС. Практическая проверка предлагаемых моделей и методов осуществлялась путем их программной реализации, апробацией на реальных задачах и тестированием на стандартных тестах (бенчмарках). Научная новизна работы заключается в теоретическом обобщении и решении проблемы, имеющей важное значение для решения задачи планирования кристалла СБИС. Разработаны и исследованы с учетом специфики задачи планирования кристалла СБИС, с ориентацией на большие размерности новые принципы кодирования решений в виде структурированных и многохромосомных представлений, отличающихся гомологичностью, простотой, линейной оценкой трудоемкости. Разработаны и экспериментально исследованы новые адаптивные поисковые алгоритмы для решения задачи детерминированного и стохастического планирования кристалла СБИС на основе самообучения и генетического поиска и предложены технологии как их совместного, так и автономного использования. Достоверность результатов диссертационной работы. Основные положения, выносимые на защиту. Архитектура алгоритма планирования кристалла СБИС методами эволюционной адаптации на основе самообучения и генетического поиска. Модели, методы и алгоритмы альтернативной коллективной адаптации для решения задачи планирования кристалла СБИС. Новые технологии и средства повышения эффективности процесса альтернативной адаптации для усиления способности выхода из “локальных ям”. Модели, методы и алгоритмы решения задачи детерминированного и стохастического планирования кристалла СБИС на основе генетической адаптации. Новые технологии и механизмы генетического поиска на базе адаптируемого виртуального набора популяций с альтернативными структурами хромосом и генетических операторов. Принципы кодирования решений и структуры хромосом, учитывающие специфику решаемых задач с ориентацией на задачи большей размерности, отличающиеся гомологичностью, линейными оценками пространственной и временной сложности и имеющих широкую сферу применения. Практическая ценность работы состоит в том, что основные теоретические положения доведены до конкретных методик и алгоритмов. Разработанные методы эволюционной адаптации на основе самообучения и генетического поиска, являются мощным средством выхода из “локальных ям”, приводящим к синтезу решений, близких к оптимальным. Алгоритм планирования кристалла СБИС методами эволюционной адаптации реализован в виде программы на языке Вог1апс1 С++ для Vindows. Предложенные методы позволяют достигнуть улучшенных показателей объектов проектирования. Кроме того, предложенные алгоритмы и программы носят достаточно универсальный характер и могут быть использованы для решения задач в области генетического программирования, в частности задачи символического регресса, заключающейся в построении математического выражения, задаваемого примерами. Реализация результатов работы. Основные теоретические и практические результаты, полученные в диссертационной работе, использованы в ряде научно-исследовательских работ, проводимых в Таганрогском государственном радиотехническом университете руководителем или исполнителем которых являлся автор. В работах, выполняемых по грантам РФФИ: “Генетические алгоритмы в интеллектуальных САПР” (шифр 0); “Символьные информационные технологии проектирования на основе эволюционной адаптации” (шифр 5); “Эволюционное проектирование с адаптацией” (шифр 4). По гранту Минобразования РФ на проведение фундаментальных исследований в области технических наук - “Исследование и разработка методов трассировки СБИС на основе эволюционной адаптации”. По гранту РФФИ Конкурс молодых ученых и специалистов “Разработка эволюционных алгоритмов и программ для решения основных задач автоматизированного проектирования” (шифр 0, Руководитель Лебедев В.