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

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

Содержание
Введение

1 Анализ и состояние проблемы планирования СБИС

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

1.2 Представление модулей при планировании СБИС

1.3 Классификация критериев задачи планирования СБИС

1.4 Классификация и анализ представлений плана СБИС

1.5 Анализ существующих методов и подходов к задаче планирования СБИС

1.6 Выводы

2 Планирование СБИС на основе композиционного подхода

2.1 Постановка задачи
2.2 Представление плана «обобщенная польская запись»
2.3 Поисковая адаптация в задачах САПР
2.4 Разработка архитектуры генетического поиска для решения задачи планирования СБИС
2.5 Организация поисковой процедуры на основе коллективной альтернативной адаптации для решения задачи планирования СБИС
2.6 Разработка архитектуры меметического алгоритма для решения задачи
планирования СБИС
2.7 Выводы
3 Планирование СБИС с учетом энергопотребления
3.1 Проблема энергопотребления СБИС
3.2 Основные подходы к решению проблемы энергопотребления при мультивольтажном проектировании СБИС
3.3 Постановка задачи
3.4 Генетический алгоритм назначения напряжений
3.5 Двухуровневое распараллеливание алгоритма планирования СБИС с учетом энергосбережения
3.6 Выводы

4 Программная реализация и экспериментальные исследования
разработанных алгоритмов планирования СБИС
4.1 Обзор библиотек метаэвристик для эволюционных вычислений
4.2 Архитектура библиотеки ИАНЬ
4.3 Многопоточная реализация алгоритма назначения напряжений
4.4 Описание программного продукта
4.5 Эксперименты
4.6 Выводы
Заключение
Библиографический список
ПРИЛОЖЕНИЯ

Введение
Общая характеристика диссертационного исследования
Актуальность работы. В настоящее время современные нанометровые технологии производства СБИС достигли такой степени интеграции, что минимальный размер топологического объекта значительно меньше длины волны, применяемой при фотолитографии. Размерности решаемых задач на всех этапах проектирования существенно увеличились. Такие схемы могут быть спроектированы только на основе иерархического подхода.
Совершенствование технологии производства и резкое повышение функциональной сложности СБИС часто опережают возможности проектирования, что вызывает необходимость в пересмотре разработанных ранее и существующих на сегодняшний день алгоритмов и методов конструкторского проектирования и стимулирует разработку новых эффективных методов и средств их проектирования.
В связи с этим особо актуальна разработка новых эффективных методов решения задач конструкторского проектирования.
При проектировании больших систем часто топологическая схема требуется уже на ранних стадиях проектирования, хотя еще не были спроектированы все модули, т.е. не вся информация обо всех модулях имеется в наличии, часть этой информации может оказаться неточной. Планирование -это ранняя фаза проектирования СБИС. Оно дает информацию о приблизительных значениях площади, задержки, мощности и других рабочих характеристиках. Необходимость снижения энергопотребления наряду с уменьшением площади кристалла и повышением производительности стала одной из важнейших проблем для разработчиков специализированных интегральных схем (ASIC) и систем на кристалле (СнК), которые используются в сетевом оборудовании, мобильных устройствах и других приложениях.
Таким образом, одной из важнейших задач синтеза и формирования топологии СБИС является задача планирования кристалла СБИС.

важно, когда подавляющее большинство модулей являются гибкими. План обычно удовлетворяет хотя бы одному ограничению (горизонтальному или вертикальному). Набор ограничений является сверхограниченным, если в нем имеется много избыточных ограничений. Желательно получить полный набор ограничений из входного относительного размещения, а затем удалить те избыточные ограничения, которые сказываются на уменьшении площади топологического плана [2].
Квантовые алгоритмы. Ключевая идея квантовых алгоритмов заключается в одновременной работе с множеством решений (вариантов планирования в контексте исследуемой задачи), что может существенно ускорить поиск. В работе [30] используется польская запись для кодирования бинарного дерева разрезов.
Введем алфавит А = {X, }. Структуру дерева разрезов можно задать используя на базе алфавита А польское выражение для бинарного дерева, где X соответствует листьям дерева разрезов (областям), а - соответствует внутренним вершинам дерева (разрезам). Польские выражения для деревьев, представленных на рис. 1.21(а) и рис. 1.21(6) имеют вид: ХХ*ХХ*Х** и ХХ*ХХ»Х*.

»3 сг ёе* )с;
к.
(а) (б)
Рис. 1.21. Польская запись и бинарное дерево разрезов