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

• Автор: Бушин, Сергей Алексеевич
• Шифр специальности: 05.13.12, 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Таганрог
• Количество страниц: 142 с. : ил.

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

ВВЕДЕНИЕ
Развитие современной науки и техники тесно связано с развитием информационно-коммуникационных технологий (ИКТ), чья роль во всех областях проектирования и производства неуклонно растет. Проектирование все более сложных, требующих больших временных и трудовых ресурсов, новых объектов ЭВА и РЭА, невозможно без интегрированного компьютерного сопровождения. В современных ЭВА и РЭА, элементной базой являются системы на кристалле, сверхбольшие и сверхскоростные интегральные схемы (СБИС и ССБИС).
Быстрый прогресс в технологии сверхбольших интегральных схем обуславливает потребность в новых средствах автоматизированного проектирования. Разработчикам СБИС необходимы интеллектуальные программные системы, позволяющие реализовывать схемы с миллионами транзисторов на одном кристалле. Такие высокие характеристики достигаются за счет совместной оптимизации топологии проектов и мега библиотек. Это позволяет перевести на новый уровень такие ключевые характеристики объектов проектирования, как мощность, быстродействие, занимаемая площадь. Количественный рост сложности объекта проектирования привел к качественным изменениям в методологии проектирования, к повышению роли всех обеспечений САПР. Это позволяет в области синтеза топологии СБИС выйти на следующий уровень проектирования систем на кристалле в нанометровом диапазоне (2009-32нм, 2011-22нм и прогноз на 2013- 15нм и 2015-11 нм) [1]. Причем при создании СБИС возможен переход от 8, 9 слоев металлизации к одному слою. Процесс проектирования современных СБИС состоит из трех основных относительно независимых частей: логическое проектирование, тестирование и
верификация, синтез топологии. Системная интеграция данных этапов позволяет реализовывать платформы на «чипах» и переходить к созданию атомных процессоров. Межсоединения на кристаллах все более сложными поэтому возрастает проблема синтеза топологий. В этой связи разработка

новых интегрированных алгоритмов проектирования топологии является актуальной и важной для современных поколений радиоэлектронной и электронно-вычислительной аппаратуры. В работе рассмотрена одна из важных задач конструкторского проектирования СБИС - задача размещения. Она относится к классу МР- сложных[2]. В этой связи разработка комплекса эффективных полиномиальных алгоритмов с использованием современных критериев, является актуальной и важной задачей.
Цель диссертационной работы состоит в разработке и исследовании интегрированных биоинспирированных алгоритмов размещении компонентов СБИС.
Достижение указанной цели предполагает решение следующих основных задач:
построение графовых и гиперграфовых моделей коммутационных схем топологий и размещаемого пространства;
разработка эвристических поисковых методов размещения моделей коммутационных схем в заданной области ЧИПа;
построение архитектур бионического поиска, ориентированных на задачи размещения графовых моделей компонентов СБИС;
Для решения поставленных задач в диссертационной работе используются следующие методы: теория графов, множеств, алгоритмов и методология эволюционного моделирования.
Научная новизна работы заключается в решении задачи размещения компонентов СБИС, имеющей существенное значение в для синтеза топологии систем на кристалле (СнК).
1. Приведены новые основные принципы и приведена классификация математических моделей схем и критериев задачи размещения. Выбран комплексный критерий на основе оценки электромагнитотепловой совместимости элементов.

параметров, в результате чего увеличивается погрешность в расчетах временных моментов переключений схемы.
В таблице 1.1 приведён известный сравнительный анализ временных характеристик транзисторов и межсоединений для различных технологий изготовления СБИС.
Табл. 1.1. Величина задержек для разных технологий, согласно [1,24]
Технология Задержка в транзисторе Задержка в линии, Lintel mm
1.0 urn (А1, Si02) ~ 20 ps ~ 1 ps
100 піп (Си) ~ 5 ps ~ 30 ps
35 nir. Т':;" I ~ 2.5 ps (Си) і 1 250 ps
Как видно из таблицы 1.1 при изготовлении СБИС по технологии 35пт временные параметры межсоединений доминируют над аналогичными параметрами транзисторов. Поэтому разработка алгоритмов, позволяющих найти приемлемое по качеству и по трудоемкости решение задачи размещения компонентов СБИС с учётом временных задержек межсоединений, является весьма актуальной проблемой, стоящей перед разработчиками САПР.
Одним из путей решения отмеченной проблемы является разработка алгоритмов размещения, минимизирующих длину межсоединений с учетом заранее заданных ограничений на временные характеристики схемы [49,50]. Одновременно с длиной необходимо учитывать и сопротивления межсоединений. В данном подходе необходим учет реальных топологических параметров схемы.
Другим путем решения проблемы минимизации задержки является учет размеров логических элементов. Если известна емкостная нагрузка