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

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

СОДЕРЖАНИЕ
ВВЕДЕНИЕ.

1. ОБЗОР И АНАЛИЗ АЛГОРИТМОВ СЖАТИЯ ТОПОЛОГИИ СБИС

1.1 Постановка задачи сжатия.

1.2 Классификация алгоритмов сжатия топологии СБИС.

1.3 Одномерное сжатие

1.4 1.5мерное сжатие

1.5 Двухмерное сжатие

1.6 Иерархическое сжатие.

1.7 Выводы.

2. РАЗРАБОТКА ПОДХОДА К ЗАДАЧЕ СЖАТИЯ ТОПОЛОГИИ СБИС

2.1 Постановка задачи
2.2 Подход к решению задачи
2.3 Пример процесса сжатия ячейки мультиплексора.
2.4 Выводы.
3. РАЗРАБОТКА МЕТОДОВ ОПИСАНИЯ ТОПОЛОГИИ СБИС НА БАЗЕ НАБОРА ПРИМИТИВОВ
3.1 Общие сведения.
3.2 Разработка методов создания и описания примитивных
геометрических объектов
3.3 Разработка метода описания слоев и конструкторских правил
3.4 Построение абстрактных объектов для компонентов СБИС.
3.5 Разработка методики описания технологических правил для
изготовления СБИС
3.6 Методика расчета основных параметров ячеек.
3.7 Выводы.
4. РАЗРАБОТКА МЕТОДОВ И АЛГОРИТМОВ МОДИФИКАЦИИ ТОПОЛОГИИ СБИС.
4.1 Разработка алгоритма перемещения узла
4.1.1 Разработка алгоритма определения возможности перемещения узла
4.1.2 Разработка алгоритма построения очереди примитивов для
модификации топологии
4.2 Определение временной сложности алгоритмов модификации
топологии .
4.3 Выводы
5. РАЗРАБОТКА АЛГОРИТМА ДВУХМЕРНОГО СЖАТИЯ ТОПОЛОГИИ СБИС НА ОСНОВЕ МЕТОДА ИМИТАЦИИ ОТЖИГА
5.1 Общие сведения
5.2 Разработка алгоритма сжатия топологии СБИС на основе метода
имитации отжига
5.3 Выбор целевой функции.
5.4 Выводы
6. ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ РАЗРАБОТАННОГО
АЛГОРИТМА СЖАТИЯ ТОПОЛОГИИ СБИС
6.1 Выбор параметров целевой функции
6.2 Выбор значений управляющих параметров процесса имитации
отжига
6.3 Определение временной сложности алгоритма сжатия топологии
6.4 Сравнение предложенного алгоритма с аналогами.
6.5 Выводы
ЗАКЛЮЧЕНИЕ.
ЛИТЕРАТУРА


Таким образом, высота топологии может быть уменьшена только за счет уменьшения высоты канала. Для этого используется частный случай сжатия, называемый канальным сжатием. Однако некоторые канальные трассировщики производят компактную топологию, не требующую дополнительного сжатия. Массив ключей (Gate Array): Т. В данной работе разрабатывается алгоритм сжатия, который может быть использован для сжатия топологии полностью заказных СБИС. СБИС. Алгоритмы сжатия могут быть классифицированы двумя разными способами. Первый способ - это классификация по направлению перемещения элементов во время сжатия: одномерное сжатие и двухмерное сжатие [4]. При одномерном сжатии элементы перемещаются только по оси х или по оси у. В результате изменяются либо х- либо у- координаты элементов. Если сжатие выполняется вдоль оси х, то оно называется х-сжатисм. Соответственно, если сжатие выполняется вдоль оси у, то оно называется у-сжатием. На рис. В случае двухмерного сжатия элементы могут перемещаться одновременно вдоль обеих осей. В результате, во время двухмерного сжатия, изменяются и х- и у- координаты элементов для минимизации площади топологии. На рис. Второй способ классификации основывается на методе вычисления минимальных расстояний между элементами [1]. Существует два метода: сжатие с помощью графа ограничений и сжатие с помощью виртуальной сетки. При использовании графа ограничений соединения и минимальные расстояния описываются с помощью линейных неравенств, которые могут быть смоделированы, используя взвешенный ориентированный граф (граф ограничений) как показано на рис. Затем граф ограничений используется для вычисления новых позиций элементов. Рисунок 1. Рисунок 1. Другой метол, метол виртуальной сетки, предполагает, что топология располагается на сетке. Каждый элемент рассматривается прикрепленным к линии сетки. Во время сжатия алгоритм сдвигает лини сетки ближе друг к другу вместе с элементами расположенными на них. Минимальное расстояние между двумя смежными линиями сетки зависит от элементов расположенных на этих линиях. Преимущество этого метода состоит в том, что для выполнения такой процедуры требуются простые и легко применяемые алгоритмы. Однако метод виртуальной сетки не дает хорошего результата в сравнении с методом графа ограничений. Алгоритмы сжатия также можно классифицировать по уровню иерархии сжимаемой схемы. Если сжатие применяется к разным уровням иерархии топологии, то оно называется иерархическим сжатием. Любой из выше упомянутых методов может быть расширен до иерархического сжатия. Некоторые алгоритмы сжатия перед своей работой убирают все уровни иерархии. В таком случае не всегда возможно реконструировать иерархию после сжатия. Алгоритмы одномерного сжатия применяются последовательно но X и У осям до тех пор, пока сжатие возможно. Рассмотрим сжатие с помощью графа ограничений [8]. Граф ограничений С = (V, Е) является взвешенным графом. Каждая вершина у<=У представляет собой элемент. Каждое ребро представляет собой ограничение. Оба типа ограничений могут быть представлены графом ограничений. Bx>Ax + d, (1. Ах - х-координата элемента А. Такое неравенство представляется в графе ограничений как ребро из А в В с весом d (см. На рис. Физическое соединение может быть представлено циклом из двух ребер, т. Лх - Вх| < d может быть записано двумя следующими ограничениями: Ах > Вх - d и Ах > Вх - d. Эти два ограничения представляются в графе как пара ограничений между Ах и Вх, каждое с весом равным —d. Граф ограничений также содержит две дополнительных вершины, L (Left) и R (Right), которые представляют две физических границы левую и правую. Вершину L можно представить как источник графа ограничений, т. L, другими словами ребра смежные с L только выходят из нее. Соответственно, R можно рассматривать как приемник графа. На рис. L и R. В процессе сжатия во время перемещения элементов необходимо сохранить исходные электрические соединения. Большинство программ сжатия получают информацию об электрических соединениях из перекрытий элементов в исходной топологии. Рисунок 1. Рисунок 1.