Разработка и исследование интегрированных алгоритмов размещения элементов на основе методов эволюционного моделирования

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

ВВЕДЕНИЕ.

1. АНАЛИЗ ПРОБЛЕМ И ПЕРСПЕКТИВ МЕТОДОВ РАЗМЕЩЕНИЯ

1.1. Анализ проблемы размещения фрагментов БИС

1.2. Постановка задачи размещения фрагментов БИС

1.3. Классификация и анализ методов размещения фрагментов БИС

1.4. Выводы

2. РАЗРАБОТКА ИНТЕГРИРОВАННЫХ МЕТОДОВ РЕШЕНИЯ ЗАДАЧ РАЗМЕЩЕНИЯ

2.1. Стратегия и принципы решения задачи размещения

2.2. Архитектура интегрированного поиска

2.3. Разработка генетических и эволюционных стратегий размещения фрагментов БИС

2.4. Построение усовершенствованных генетических операторов, ориентированных на решение задачи размещения
2.5. Выводы
3. ПОСТРОЕНИЕ ИНТЕГРИРОВАННОГО АЛГОРИТМА РАЗМЕЩЕНИЯ ФРАГМЕНТОВ БИС
3.1. Интегрированный алгоритм на основе методов эволюционного моделирования
3.2. Разработка модифицированного алгоритма
3.3. Разработка модифицированных генетического и эволюционного алгоритмов размещения фрагментов БИС
3.4. Разработка параллельного алгоритма размещения фрагментов БИС
3.5. Выводы
4. ВЫЧИСЛИТЕЛЬНЫЙ ЭКСПЕРИМЕНТ И АНАЛИЗ РАЗРАБОТАННЫХ АЛГОРИТМОВ РАЗМЕЩЕНИЯ
4.1. Цель и основные задачи построения программного комплекса решения задач размещения фрагментов БИС
4.2. Описание программной реализации интегрированного алгоритма размещения фрагментов БИС
4.3. Результата проведения вычислительног о эксперимента на тестовых примерах
4.4. Выводы
ЗАКЛЮЧЕНИЕ
Список используемых источников


Поэтому при решении задач конструкторского синтеза ЭВС для снижения размерности выполняются различные способы декомпозиции задачи па более простые подзадачи . Функциональные характеристики каждого фрагмента БИС можно условно описать кортежем систем коммутационных, электрических, конструктивных и внешних параметров . Система Л коммутационных параметров определяет число элементов и соединений фрагментов БИС. Система В электрических параметров в основном не зависит от коммутационных параметров. Здесь необходимо решать проблемы задержки, электрической совместимости, емкостного баланса и т. Система С конструктивных параметров определяет размеры фрагментов, внутренних элементов, толщину и длину соединений. Система Р определяется ЛИР лицом, принимающим решение, т. В процессе синтеза топологий все фрагменты БИС требуется разместить в заданном каркасе, т. ЧИПс интег ральной схемы, а также определить предварительное расположение всех электрических соединений. Реализация выражения 1. А I в заданных пределах. Задача размещения фрагментов КИС относится к классу ИРтрудных проблем. Известна гипотеза, что для таких задач невозможно строить алгоритмы получения точного решения, обладающие полиномиальной вычислительной сложностью . Однако для различного класса реальных задач проектирования БИС возможно строить экспоненциальные алгоритмы, у которых для некоторых п временная сложность имеет значения аналогичные линейным алгоритмам. В таких методах вместо полного перебора реализуется направленный перебор альтернативных решений, обеспечивающий отбрасывание неперспективных вариантов, где достижение глобального оптимума не является глобальной первостепенной задачей. Достаточно получать локальные оптимумы, находящиеся в близком соседстве к глобальному. Ориентация поисковых алгоритмов на получение приближенных решений с заданной точностью повышает эффективность и качество синтеза топологий БИС. Известно, что переход на эвристические и локальные алгоритмы позволяет ряд задач размещения класса ЫР перевести в класс Р, обладающий полиномиальной вычислительной сложностью . Как отмечено в работах Базилевича , один из основных путей уменьшения сложности задачи размещения это редукция их размерности. В основном, уменьшение редукцию размерности задачи выполняют путем декомпозиции сложной оптимизационной задачи размещения на ряд подзадач, которые можно решать путем распараллеливания процесса поиска. Эффективным методом уменьшения размерности задачи размещения является выбор нечетких подсистем топологических параметров. Это целесообразно для получения первоначального решения, которое может стать прообразом будущих популяций альтернативных решений. Использование топологических параметров позволяет анализировать взаимное расположение элементов в топологическом пространстве. В рассматриваемых задачах размещения, содержащих тысячи фрагментов БИС групп транзисторов, эффективным является многоуровневое макромолслированис. При этом исходная задача большой размерности проблема размещения БИС разбивается на множество иерархически вложенных друг в друга идентичных задач размещение фрагментов БИС значительно меньшей размерности, решаемых одним базовым оптимизационным методом . Итак, проблема размещешш фрагментов БИС формально сводится к определению оптимальною пространственного расположения связанных элементов модулей, фрагментов с расположенными на них терминалами выводами на коммутационном иоле КП в соответствии с заданными критериями. Проблема размещения во многом определяется типом проектируемой БИС. Основным комплексным критерием качества размещения является мера оценки электромагнито тепловой совместимости при размещении фрагментов БИС . Данный критерий определяет область допустимых размещений элементов на плоскости, на которой могу т быть заданы другие критерии. При заданных размерах кристалла БИС важной задачей является размещение на нем всех элементов без наложений. В общем случае для оценки качества размещения вводят функцию качества, описывающую критерии оптимальности размещения.