Быстродействующий метод размещения элементов СБИС с учетом загрузки коммутационных слоев

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

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

Глава 1. Современные проблемы автоматизации проектирования топологии СБИС

1.1. Технологические тенденции и конструкторские требования

1.2. Основные этапы решения задачи размещения

1.3. Критерии качества и тестовые примеры

1.4. Аналитические методы

1.5. Дихотомические алгоритмы

1.6. Комбинированные алгоритмы

1.7. Результаты сравнения на РО

1.8. Методы легализации, детального размещения и ЕСО

1.9. Эффективность алгоритмов размещения в зависимости от схемы и библиотеки
Выводы
Глава 2. Методы оптимизации размещения
2.1. Модель графа перестановок
2.2. Алгоритм оптимизации размещения элементов
Глава 3. Оценка трассируемости с использованием вероятностного анализа
3.1. Постановка задачи
3.2. Оценка перегрузок
3.3. Запреты на трассировку
3.4. Оптимизация трассируемости
Выводы
Глава 4. Метод оценки деревьев Штейнера, адаптирующийся к критериям трассировки
4.1. Постановка задачи
4.2. Похожие деревья
4.3. Нахождение взаимнооднозначного соответствия между вершинами
4.4. Алгоритм построение дерева Штейнера.
Выводы
Глава 5. Программная реализация алгоритмов
5.1 Структура данных для алгоритмов оптимизации
5.2 Оценка трассируемости
5.3 Реализация общего оптимизационного алгоритма
5.4 Оптимизация трассируемости
5.5 Легализация элементов СБИС
5.6. ЕСО размещение
Выводы
Заключение
Акт о внедрении
Список литературы


Алгоритмы размещения должны учитывать относящуюся к трассировке информацию, такую как количество трассировочных ресурсов, распределение запретов и другие. Более того, необходим хороший алгоритм оценки и управления трассируемостью, иначе полученное размещение будет перегружено, что ухудшит трассируемость и производительность схемы. Алгоритмы размещения обычно состоят из 3-х основных частей: глобального размещения, легализации и детального размещения. Фаза глобального размещения делится на начальное глобальное размещение, физическую кластеризацию и финальное глобальное размещение. Целью начального глобального размещения является равномерное распределение элементов по области размещения для последующей физической кластеризации. Во время этой стадии рассматривается полный список цепей, включающий в себя стандартные элементы и макроблоки. Далее итеративно используется техника глобальной оптимизации и переброски элементов, описанная в [2]. Целью этапа физической кластеризация является устранение пересечений макроблоков и фиксация их взаимного расположения. На этом этапе стандартные элементы объединяются в кластеры на основе их размещения, полученного после этапа начального глобального размещения. Вся область размещения делится на корзины, и алгоритм физической кластеризации используется для объединения стандартных элементов в мягкие блоки (соотношение длины и высоты этих блоков может меняться при последующей работе алгоритма). Таким образом, получается начальная кластеризация для последующей работы алгоритма. Затем, с помощью некоторого оптимизационного алгоритма, устраняются пересечения между макроблоками и одновременно уменьшается общая длина соединений После этого все стандартные элементы декластеризуются и помещаются в центры соответствующих мягких блоков. Целью этапа финального глобального размещения является дальнейшее устранение пересечений между элементами и последующее уменьшение общей длины межсоединений. Макроблоки и стандартные ячейки перемещаются так, что сохраняется начальное взаимное расположение макроблоков и не возникает пересечений между ними. В конце этого этапа получается распределенное размещение с небольшим количеством пересечений и небольшой общей длиной межсоединений. На этапе легализации все макроблоки помещаются в ближайшие легальные позиции так, что пересечения между ними отсутствуют. Их размещение фиксируется на протяжении всех последующих шагов алгоритма, и они рассматриваются как запреты на области размещения. Область размещения разбивается на ряды, а ряды делятся запретами на сегменты размещения. После этого может быть использован эвристический алгоритм для размещения всех стандартных элементов по сегментам так, что емкости всех сегментов (отношение количества размещенных элементов к общему количеству посадочных мест) выравниваются. Внутри каждого сегмента стандартные элементы помещаются на легальные позиции. Последним этапом алгоритма является детальное размещение. После того, как вес стандартные элементы были легально размещены внутри сегментов размещения, применяется алгоритм детального размещения для уменьшения суммарной длины межсоединений. Он состоит из следующих шагов: глобальное перемещение, локальное перемещение и локальный сдвиг. Во время шага глобальных перемещений алгоритм пытается найти наилучшес место размещения для элемента на всей области размещения. Для каждого стандартного элемента определяется оптимальная область, которая определяется как область, в которой суммарная длина межсоединений минимальна, считая все остальные элементы фиксированными. Оптимальная область для элемента определяется, базируясь на идее медианы [3]. Рассмотрим элемент /. Пусть /V, = {и,,л2,. ШуМуЫуМ-) соответственно. После того как оптимальная область определена, алгоритм находит пересечение этой области с сегментами размещения и меняет местами текущий элемент с элементом из оптимальной области. Во время шага локальных перемещений рассматриваются только элементы внутри одного сегмента размещения. Алгоритм последовательно перебирает все смежные элементы и меняет их местами, если это приведет к уменьшению суммарной длины межсоединений.