Разработка и исследование генетических алгоритмов определения планарности схем ЭВА

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

1. АНАЛИЗ АЛГОРИТМОВ ОПРЕДЕЛЕНИЯ ПЛАНАРНОСТИ СХЕМ ЭВА
1.1. Постановка и анализ задачи
1.2. Анализ и выбор математической модели
1.3. Анализ задачи определения планарности
1.4. Матричные алгоритмы определения планарности. Алгоритм Данна - Чена
1.5. Циклические алгоритмы определения планарности
1.5.1. Алгоритм Винга - Фишера
1.5.2. Алгоритм Хопкрофта - Тарьяна
1.6. Выбор алгоритма определения планарности
1.7. Выводы и рекомендации
2. ИСПОЛЬЗОВАНИЕ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ ПРИ
РЕШЕНИИ ЗАДАЧИ ПЛАНАРИЗАЦИИ
2.1.Анализ методов оптимизации
2.2. Элементы генетических алгоритмов
2.3. Структура генетического алгоритма
2.4. Методика кодирования информации
2.5. Основные генетические операторы
2.5.1. Оператор селекции
2.5.2. Оператор кроссинговера
2.5.3. Оператор мутации
2.5.4. Оператор отбора
2.6. Общая схема генетического алгоритма
2.7. Выводы и рекомендации
3. РАЗРАБОТКА ГЕНЕТИЧЕСКОГО АЛГОРИТМА ПЛАНАРИЗАЦИИ78
3.1. Общая схема алгоритма планаризации

3.2. Исходные данные
3.3. Генерация циклов
3.4. Анализ промежуточных данных
3.5. Генетический алгоритм
3.5.1. Концепция ГА
3.5.2. Кодирование информации
3.5.3. Создание начального базового решения(Этап № 1)
3.5.4. Улучшение базиса (Этап № 2)
3.5.5. Точечная достройка базового решения (Этап № 3)
3.5.6. Изменение базового решения (Этап № 4)
3.6. Построение плоской укладки
3.7. Минимизация пересечений
3.8. Теоретические оценки алгоритма
3.9. Выводы и рекомендации
4. ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ АЛГОРИТМА
ПЛАНАРИЗАЦИИ
4.1. Цель экспериментального исследования
4.2. Определение пространственной и временной сложности алгоритма
4.3. Планирование эксперимента
4.4. Статистическая обработка экспериментальных данных
4.5. Результаты экспериментальных исследований
4.6.Сравнение результатов алгоритмов определения планарности
4.7. Описание интерфейса
4.8. Выводы и рекомендации
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА
ПРИЛОЖЕНИЯ
ПРИЛОЖЕНИЕ №

В настоящее время во многих отраслях таких, например, как электронная промышленность, приборо- и машиностроение широко применяются интегральные микросхемы (ИС) большой (БИС) и сверхбольшой (СБИС) степени интеграции. Это повышает надежность электронно-вычислительной аппаратуры (ЭВА), снижает ее габариты, потребляемую мощность, улучшая, таким образом, технико-экономические характеристики выпускаемых изделий.
Следует заметить, что под термином «интегральная микросхема (ИС)» понимается микроэлектронное изделие окончательной или промежуточной формы, предназначенное для выполнения функций электронной схемы, элементы и связи которого нераздельно сформированы в объеме и(или) на поверхности материала, на основе которого изготовлено изделие [1]. Согласно [2, 3] большой интегральной микросхемой (БИС) называется интегральная микросхема содержащая 500 и более элементов, изготовленных по биполярной технологии, либо 1 ООО и более элементов, изготовленных по МДП-технологии, причем под элементом интегральной микросхемы понимается часть ИС, не выделенная в самостоятельное изделие, но реализующая функцию какого-либо элемента схемы, например, транзистора.
Однако выпускаемые промышленностью стандартные ИС зачастую не удовлетворяют специальным требованиям заказчиков. Это обстоятельство привело к появлению мелкосерийных, «заказных» БИС и СБИС. Необходимость разработки небольших серий ИС, в свою очередь, привела к увеличению их стоимости, что влечет за собой увеличение затрат на этапах проектирования и разработки. [4-6].
Наряду с совершенствованием методов проектирования наблюдается тенденция стандартизации конструкций кристаллов ИС, как одного из способов снижения стоимости производства. Для этого используются так называемые базовые кристаллы представляющие собой совокупность расположенных на кристалле транзисторов между которыми расположены

2. ИСПОЛЬЗОВАНИЕ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ ПРИ РЕШЕНИИ
ЗАДАЧИ ПЛАНАРИЗАЦИИ
2.1.Анализ методов оптимизации
Существует несколько подходов к решению ]51Р-полных задач. К первой категории относятся методы, пытающиеся сузить границы перебора за счет построения частичных решений, представленных деревом поиска, и применения методов построения оценок, позволяющих опознать бесперспективные частичные решения, в результате чего от дерева поиска отсекаются бесперспективные ветви. К таким методам относятся широко известный метод ветвей и границ или метод неявного перебора.
Другую категорию составляют метод динамического программирования, метод отсечений и метод Лагранжа. Здесь снижение размерности перебора достигается через «снижение требований», которое заключается в отказе от поиска оптимального решения и нахождении квазиоптимального решения за приемлемое время. Такие алгоритмы получили название эвристических, поскольку для поиска решения они используют различные правила (эвристики) не имеющие строгого научного обоснования и определяемые опытным (эмпирическим) путем. Поэтому такие методы сильно зависят от специфики задачи.
Одним из наиболее распространенных методов оптимизации является метод «локального поиска», когда заранее выбранное множество локальных операций используется для последовательного улучшения начального решения до тех пор, пока такое улучшение возможно, в противном случае оказывается достигнутым локальный оптимум [103].
Однако все описанные методы имеют один серьезный недостаток - они неспособны находить выход из локальных оптимумов. Это вызвано применением жестких правил поиска в алгоритме оптимизации.
Существует еще одна категория поисковых методов - случайные методы, которые, в свою очередь делятся на три класса: случайный поиск,