Разработка и исследование алгоритмов решения задачи размещения компонентов СБИС с учетом временных задержек

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

Содержание
Содержание
ВВЕДЕНИЕ

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

I

1.1. Анализ проблемы размещения.

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

1.3. Классификация критериев задачи размещения

1.4. Постановка задачи размещения с учетом временных задержек.

1.5. Классификация и анализ методов размещения

1.6. Выводы.

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


Обоснован выбор математической модели на основе дерева Штейнера для использования в качестве целевой функции генетического алгоритма. В третьей главе Разработаны модификации традиционных алгоритмов решения задачи размещения: последовательного алгоритма и алгоритма слепого поиска. Разработан проблемно-ориентированный генетический алгоритм. Разработан многопопуляционный параллельный генетический алгоритм па основе модели островов. Предложен новый поход к кодированию решения генетического алгоритма, учитывающий статусы генов. Разработаны модифицированные проблемно-ориентированные генетические операторы. В четвертой главе представлены результаты проведения серии экспериментов для разработанных в третьей главе алгоритмов. Приведено описание разработанного программно-алгоритмического комплекса. По результатам экспериментов определены оценки временной сложности алгоритмов. Определены оптимальные значения управляющих параметров для разработанных генетических алгоритмов. Определена эффективность разработанных алгоритмов размещения с учетом временных задержек. В заключении изложены основные выводы и результаты диссертационной работы. В приложении даны копии актов об использовании результатов работы и приведен листинг программно-алгоритмического комплекса. Вследствие развития полупроводниковой технологии и роста затрат на проектирование интегральных схем экономически обоснованным становится полузаказное проектирование, в котором реализована идея предварительного изготовления реконфигурируемой архитектуры с последующей конкретизацией пользователем её функционального назначения. Мировыми лидерами в изготовлении схем такого класса являются такие фирмы-производители, как Altera, Actel, AT&T, Xilinx, и др. Реконфигурируемые СБИС сочетают в себе достоинства специализированных СБИС, быстро изготавливаются и имеют большой объём выпуска, характерный для стандартных СБИС [-]. Полузаказные СБИС обладают большим разнообразием конструктивно-технологических решений. FPGA). Самыми распространёнными типами полузаказных СБИС являются схемы на основе матричных кристаллов. Базовый матричный кристалл (БМК) представляет собой монокристаллическую полупроводниковую пластину, на которой размещена матрица нескоммутированных базовых ячеек (БЯ), в которых находится определённое количество транзисторов и резисторов. Базовая ячейка представляет собой логический модуль с внутренней структурой. В периферийной части БМК располагаются интерфейсные элементы ввода-вывода (буферные ячейки). При электрическом и физическом проектировании сложную электронно-вычислительную аппаратуру (ЭВА), содержащую несколько сотен полупроводниковых приборов, очевидно, нельзя рассматривать в качестве одноуровневой структуры, так как при этом постановка и решение задачи структурной оптимизации сталкивается с двумя трудностями: во-первых, слишком большое количество переменных исключает возможность применения ЭВМ с конечной памятью; во-вторых, переменные на разных уровнях имеют неравноценное влияние на обобщённый критерий качества, что заведомо приводит к большому количеству малоэффективных шагов поиска. И с функциональной, и с эксплуатационной точки зрения структура ЭВА может быть разделена на несколько уровней []. Иерархическая структура проектирования, заданная делением всей конструкции на блоки разного ранга, обеспечивает удобство проектирования, изготовления, эксплуатации и является необходимым условием для автоматизации проектирования ЭВА и применения алгоритмических методов проектирования. В проектно-конструкторских задачах применяют двухуровневое или трехуровневое рассмотрение устройства. При двухуровневом представлении элемент (Н-1)-го уровня рассматривают как некоторое устройство с соответствующим делением на составные элементы (компоненты) Его уровня. При трёхуровневом представлении элемент (1+2)-го уровня рассматривают как некоторое устройство (кристалл, чип), состоящее из макроэлементов (1+1)-го уровня (слои, линейки, блоки), которые в свою очередь состоят из базовых элементов Его уровня.