Содержание к диссертации
Введение
Глава 1. Обзор методов сжатия топологии 8
1.1. Постановка задачи сжатия 9
1.2. Классификация алгоритмов сжатия 13
1.3. Одномерное сжатие 14
1.4. Алгоритмы, использующие два графа ограничений 25
1.5. Двумерное сжатие 31
1.6. Иерархическое сжатие 33
1.7. Оптимизация топологии 34
Выводы 36
Глава 2. Представление топологии и построение графа ограничений ... 37
2.1. Контурное представление топологии 37
2.2. Представление технологических правил 41
2.3. Построение графа ограничений 41
2.4. Способы минимизации длины критического пути в графе ограничений 47
2.5. Выводы 53
Глава 3. Методы сжатия топологии стандартных ячеек 55
3.1. Алгоритм 1.5 мерного сжатия 56
3.2. Анализ графа ограничений 60
3.3. Критерий остановки и анализ дальнейшей сжимаемости топологии .. 71
3.4. Выход из локальных минимумов 73
3.5. Заключительная оптимизация топологии 76
3.6. Сложность алгоритма сжатия 82
3.7. Выводы 83
Глава 4. Снижение размерности задачи сжатия 85
4.1. Метод линейной декомпозиции 85
4.2. Способы применения линейной декомпозиции 88
4.3. Выводы 89
Глава 5. Исследование эффективности методов сжатия 91
5.1. Выбор характеристики размера топологии стандартной ячейки 91
5.2. Зависимость времени сжатия от размеров топологии 93
5.3. Сравнение качества сжатия топологии 96
5.4. Минимизация задачи сжатия 100
5.5. Выводы 103
Заключение 104
Список литературы: 107
- Классификация алгоритмов сжатия
- Способы минимизации длины критического пути в графе ограничений
- Критерий остановки и анализ дальнейшей сжимаемости топологии
- Способы применения линейной декомпозиции
Введение к работе
Актуальность работы.
В настоящее время современные субмикронные технологии достигли такой степени интеграции, что минимальный размер топологического объекта меньше длины волны, используемой при фотолитографии. Например, длина затвора транзистора равна 45 нм, а длина волны - 193 нм. (Для сравнения размер вируса гриппа равен 60 нм.) Как следствие этого, к известным технологическим ограничениям на минимальное расстояние и размер объектов топологии добавились новые, более сложные правила. Данные правила зависят от конфигурации, геометрических размеров и взаимного расположения объектов топологии. Кроме того, для создания объектов меньше чем длина волны применяются специальные приемы, позволяющие улучшить разрешающую способность технологического оборудования. Одним из таких приемов является засветка противоположными фазами с разных сторон проводника. Это порождает ряд правил, гарантирующих отсутствие конфликтов противоположных фаз. Например, необходимо выдерживать специальное минимальное расстояние между проводами, если:
они перпендикулярны и их ширина меньше длины волны;
между ними расположен третий провод и их ширина меньше длины волны. Технологические ограничения такого вида делают процесс разработки современных топологий более трудоемким, чем раньше.
Уменьшение размеров привело к тому, что проводники вносят существенный вклад в задержку распространения сигнала даже в топологии стандартной ячейки. Следовательно, необходимо учитывать данные схемотехнические проблемы при разработке топологии ячеек. Особенно сильно на задержку распространения сигнала в стандартной ячейке влияет расстояние между затворами транзисторов, так как диффузионная область имеет значительное сопротивление и емкость по сравнению с металлами.
Наряду с перечисленными ограничениями происходит быстрая смена технологий. Каждый год появляется новый технологический процесс, который в первую очередь требует разработки новой библиотеки стандартных ячеек. Это приводит к тому, что разработка библиотеки производится в сжатые сроки и часто параллельно с доводкой технологии.
Таким образом, сложные технологические ограничения и сжатые сроки проектирования делают невозможным разработку топологии стандартных ячеек без использования Систем Автоматизированного Проектирования (САПР). Одним из важных этапов автоматического синтеза топологии является сжатие. На этом этапе производится уменьшение площади топологии одновременно с контролем и выполнением всех ограничений, накладываемых технологическим процессом производства.
Параллельная разработка библиотеки и технологий требует коррекции уже разработанных ячеек после каждого изменения технологических норм. Задача коррекции технологических правил является родственной задаче сжатия и называется миграцией топологии. Однако, при миграции размер топологии может увеличиться для выполнения требований новых ограничений.
Известные методы сжатия не учитывают перечисленные выше технологические и схемотехнические ограничения. Следовательно, разработка новых эффективных методов сжатия и миграции топологии является актуальной.
Цель диссертационной работы состоит в разработке эффективных методов и алгоритмов сжатия топологии стандартных ячеек СБИС с учетом требований современных субмикронных технологий. Для достижения данной цели в диссертационной работе решаются следующие задачи:
разработка эффективного алгоритма сжатия топологии стандартных ячеек субмикронных СБИС;
разработка алгоритмов для улучшения быстродействия, трассируемости и выхода годных на этапе сжатия;
разработка модели топологии, позволяющей проводить эффективное сжатие и учитывать современные технологические ограничения;
разработка иерархических методов сжатия больших ячеек;
исследование эффективности предложенного алгоритма, сравнение качества сжатия с существующими методами и выбор оптимальных параметров настройки алгоритмов.
Научная новизна результатов, представленных в данной диссертационной работе, заключается в следующем:
- предложена новая модель топологии и методы ее реорганизации для
проведения полуторамерного сжатия, основной особенностью которой
является использование непересекающихся многосвязных контуров;
предложен алгоритм полуторамерного сжатия топологии стандартных ячеек субмикронных СБИС, который, в отличие от известных, учитывает современные технологические ограничения, позволяющие создавать объекты меньше длины волны, используемой при фотолитографии;
предложен алгоритм автоматического удаления положительных циклов в графе ограничений, который, в отличие от известных, использует полуторамерные реорганизации топологии. Это позволяет сжимать некорректную топологию с одновременным устранением технологических нарушений. Данный алгоритм используется как при сжатии, так и в различных методах оптимизации топологии;
разработан оригинальный метод поиска оптимального сечения критического подграфа, который отличается от известных одновременным применением различных способов минимизации длины критического пути (разбиение вершины и удаление ребра). Данный подход позволяет получать более компактную топологию;
предложен алгоритм минимизации диффузионных областей с помощью полуторамерных реорганизаций топологии, который позволяет минимизировать задержки сигнала.
Реализация.
На базе предложенных алгоритмов разработан комплекс программ сжатия и миграции топологии. Программа сжатия топологии стандартных ячеек используется в системе автоматического синтеза топологии стандартных ячеек. Программа миграции топологии успешно используется для коррекции топологии при незначительном изменении технологических ограничений и при переводе топологии на новые технологические процессы. Разработанные программы внедрены в ЗАО "Моторола ЗАО".
Практическая значимость работы.
Алгоритмы и подходы, предложенные в данной работе, реализованы в виде программы сжатия топологии, которая используются при автоматическом синтезе топологии стандартных ячеек СБИС. Данные алгоритмы также используются при миграции существующих топологий на новые технологические процессы. Модель топологии, используемая для сжатия, позволяет выдерживать основные современные технологические ограничения. С использованием данных программ были проведены синтез и миграция нескольких библиотек стандартных ячеек для
современных технологических процессов. Предложенный метод линейной
- декомпозиции задачи сжатия, позволяет применять данные алгоритмы для
топологии больших размеров.
Апробация основных теоретических и практических результатов работы проводилась на конференциях:
Международная научно-техническая конференция "Интеллектуальные
САПР" (г. Геленджик, 1999-2003 г., 5 докладов)
Всероссийская межвузовская научно-техническая конференция студентов
* и аспирантов "Микроэлектроника и информатика-2003", (МИЭТ, 2003 г., 1
доклад)
Публикации. Результаты диссертации отражены в пяти статьях [2,3,6,7,12], шести тезисах научных докладов на конференциях [1,4,8-11] и одном патенте [5].
Структура и объем диссертационной работы. Диссертационная работа состоит из введения, пяти глав, заключения и списка литературы. Работа содержит 119 страницы и 2 акта о внедрении.
%
*
Классификация алгоритмов сжатия
Известны ID алгоритмы, решающие задачу сжатия за полиномиальное время [15], но они не обеспечивают необходимого качества, а 2D сжатие является NP-полной задачей [51], что накладывает ограничения на размерность. Таким образом, с увеличением степени интеграции и появлением сложных технологических правил широкое распространение получили различные эвристические методы. Данные методы не находят оптимального решения, но все таки используют два направления для решения задачи.
Они получили название полуторамерных (1.5D). Здесь сжатие происходит в одном (основном) направлении. Главная цель - уменьшить размер т пологии в этом направлении. Однако в процессе сжатия возможно изменение координат объектов в другом (ортогональном) направлении. Второй критерий классификации основан на способе вычисления минимального расстояния между объектами топологии. Здесь существует два класса методов: сжатие основанное на графе ограничений и на виртуальной сетке. При использовании графа ограничений связность объектов топологии и технологические правила между ними описываются с помощью линейных неравенств, которые могут быть смоделированы с помощью взвешенного направленного графа (графа ограничений). Этот граф используется для вычисления минимально возможных координат элементов топологии. С другой стороны, использование виртуальной сетки предполагает, что топология нарисована на сетке. Каждый элемент рассматривается вместе с его линией сетки. При сжатии линия сетки перемещается вместе со всеми элементами, связанными с ней. Минимальная позиция каждой сетки зависит от ее элементов. Преимущество этого метода в том, что он прост и может быть легко реализован.
Однако, он не позволяет получить такой плотности топологии, как графовый подход. Последний критерий - использование иерархии при сжатии. Если сжатие происходит на различных уровнях иерархии, то такой подход называется иерархическим. Алгоритмы, которые раскрывают все уровни иерархии, называются неиерархическими.
При иерархическом сжатии размерность решаемой задачи существенно снижается, но решение получается неоптимальным. При полном раскрытии иерархии сильно возрастает размерность задачи и трудно восстановить иерархию после сжатия, что может быть нежелательно. Как уже говорилось ранее, одномерное сжатие не может обеспечить нахождение минимального решения за одну итерацию. Поэтому одномерное сжатие многократно повторяется по А и Y направлениям до тех пор, пока размер топологии уменьшается. Рассмотренные в данном разделе алгоритмы описываются на примере сжатия по X направлению. В простейшем методе сжатия с использованием виртуальной сетки каждый компонент топологии прикрепляется к линии сетки, как показано на Рис. 1.7. Элементы А и В прикреплены к первой линии, С, F - ко второй, a D и Е - к третьей. На следующем шаге вычисляется минимально возможное расстояние между каждой парой соседних линий сетки. При этом учитывается минимальное технологическое расстояние между объектами топологии (Spacing=l) и расстояние от линии сетки до края объекта. В данном примере минимальное расстояние между линиями 1 и 2 равно 6, а между 2 и 3 равно 4. Далее линии сетки, а с ними и объекты топологии, ставятся на минимальные расстояния (Рис. 1.8). Затем аналогичным образом выполняется У-сжатие. Основное преимущество данного метода в том, что он быстр, а недостаток -элементы закреплены за линии сетки и это приводит к существенным потерям площади. В статье [42], Воуег предложил модификацию данного алгоритма, который позволяет производить расщепление линий сетки, если это необходимо. В данном методе элементы, назначенные на одну линию сетки, разбиваются на независимые группы, например по связности. Алгоритм имеет два этапа: на первом выполняются X и Y сжатия описанным выше методом. Затем среди объектов, принадлежащих Hi каждой линии сетки, вьщеляются сильно связанные группы и каждая группа рассматриваются независимо. Таким образом, если одной линии сетки соответствовали две или более групп, то эта линия расщепляется на две и снова выполняется одномерное сжатие. Рассмотрим пример на Рис. 1.8. Объекты, назначенные на вторую линию, разобьем на две группы: первая С, вторая F. На Рис. 1.9 показана топология после сжатия. Ее ширина меньше, чем после предыдущего алгоритма.
Способы минимизации длины критического пути в графе ограничений
Множество вершин и ребер основного графа, принадлежащих длиннейшему пути между вершинами Source и Sink, называется критическим подграфом, а его ребра и вершины - критическими. Длина критического пути определяет размер топологии в соответствующем направлении. В работах [4], [6] были предложены способы преобразования объектов топологии, позволяющие уменьшить длину критического пути с помощью следующих операций: разбиения критической вершины на несколько новых вершин; удаления критического ребра из графа ограничений. Разбиение критической вершины. Разбиение критической вершины на несколько новых - это эффективный способ минимизации длины критического пути. Разбиение критической вершины приводит к разрыву критических путей, проходящих через данную вершину. Преобразования топологии, которые приводят к разбиению вершины графа ограничений, следующие: разрыв связи между объектами топологии (удаление пары связности); оптимизация формы контура ("Jog Insertion "). Разрыв связи между объектами топологии. В разделе 2.1 были описаны пары связности, которые используются для сохранения конструкции и минимизации размерности задачи. Эти пары могут образовывать положительные циклы в графе ограничений или увеличивать длину критического пути. В этом случае такую пару необходимо удалить. После удаления пары вершина графа ограничений разделяется на две новых вершины и строятся ребра, описывающие правила к объектам данных вершин. Пример удаления пары для уменьшения длины критического пути приведен на Рис. 2.16. Оптимизация формы контура ("JogInsertion"). Добавление изломов в топологические объекты также приводит к разбиению критической вершины.
Данное преобразование объектов топологии было впервые предложено в [32] и известно под названием "Jog Insertion". На Рис. 2.17а) показан "Jog Insertion" для произвольного участка контура, который можно определить как разбиение двух противоположных сторон контура. При этом точки излома сторон должны быть разнесены в перпендикулярном направлении на величину правила минимальной ширины для данного слоя. Таким образом, "Jog- Insertion" можно обобщить и представить разделением некоторой стороны контура на две или более частей. Такие преобразования необходимы, когда в критическом пути находится "широкая" фигура (ширина больше, чем минимально возможная). Для уменьшения длины критического пути такую фигуру можно привести к минимальной ширине путем добавления в нее дополнительных сторон. Примеры приведения контура к минимально возможной ширине путем "вдавливания" в него других фигур приведены на Рис. 2.17 б) и в). Удаление ребер критического подграфа. Удаление критического ребра приводит к разрыву критических путей, проходящих через данное ребро.
Если ребро невозможно удалить, то уменьшение его длины также позволяет сократить длину критического пути. Алгоритм удаления (уменьшения длины) критического ребра состоит из трех шагов: 1. удаления критического ребра из основного графа ограничений; 2. добавления новых ребер в основной или ортогональный граф ограничений; 3. удаления сторон контура (если это необходимо). Удаление некоторого ребра в графе является следствием преобразования (реорганизации) контуров, между сторонами которых построено ребро. Для удаления критических ребер предлагаются следующие способы реорганизации контуров: сдвиг стороны контура; удаление стороны контура; изменение типа стороны; слияние двух контуров одной и той же цепи; изменение формы контура при сохранении его площади. Сдвиг стороны контура. Сдвиг стороны приводит к удалению ребра, образованного правилами минимального расстояния, включения или ширины. Для этого стороны контуров необходимо разнести в ортогональном направлении на столько, чтобы их проекции не пересекались и находились на расстоянии величины правила. Сдвиг сторон без нарушения других правил обеспечивается путем добавления дополнительного ребра в ортогональный граф ограничений. Примеры сдвига сторон и добавления новых ребер приведены на Рис. 2.18. Удаление стороны контура Для удаления ребра, соответствующего правилу минимального расстояния или ширины, также может быть использовано удаление стороны контура, к которой применяется данное правило. Удаление стороны производится в два этапа. Сначала в ортогональный граф добавляется пара новых ребер, уменьшающих сторону контура до нулевой длины, затем данная сторона удаляется. Такой прием позволяет удалять ребро, образованное правилом минимального расстояния, как между разными контурами (Рис. 2.19 а)), так и в пределах одного контура (Рис. 2.19 б)). Изменения типа стороны контура на противоположный приводит к удалению критического ребра, отвечающего за сохранение конструкции контура. Вместо него создается новое ребро, противоположное данному, которое необходимо для представления конструкции и может не принадлежать критическому пути. Пример изменения типа стороны приведен на Рис. 2.20.
Критерий остановки и анализ дальнейшей сжимаемости топологии
При использовании итерационных алгоритмов хороший критерий остановки позволяет существенно ускорить сходимость и избежать зацикливания. В [12] предложены несколько критериев остановки для алгоритма сжатия топологии стандартных ячеек СБИС: целевой размер, плотность и память объектов топологии. Целевой размер является нижней оценкой возможного размера топологии в направлении сжатия. Например, все стандартные ячейки одной библиотеки должны иметь одинаковую высоту, заданную пользователем. При сжатии по X направлению размер не ограничен, поэтому для данного направления используется нижняя оценка, которая вычисляется, исходя из следующих факторов: Количество входных и выходных портов. Так как каждый порт должен стоять в сетке трассировщика и занимать уникальную колонку, то минимальная ширина топологии не может быть меньше количества портов, умноженного на размер сетки. PerimeterfSh) -периметр фигуры. Если плотность топологии больше некоторой предельной величины, то сжатие завершается. Предельная плотность определяется экспериментальным путем и зависит от технологических ограничений и шаблона (ограничений пользователя) ячейки. По умолчанию, в качестве предела используется 1.0. Память объекта топологи - это максимальное количество итераций без улучшения целевой функции, в которых объект может участвовать. Каждый объект топологии имеет память, представленную некоторым целым числом. Если в процессе минимизации критического пути объект участвует в трансформациях топологии, то его память уменьшается на единицу после каждой трансформации. Объект исключается из рассмотрения, если его память равна нулю. При каждом уменьшении размера топологии память объектов восстанавливается. Такой подход позволяет избежать зацикливания.
Предложенный алгоритм сжатия является итерационным и выполняет итерации до тех пор, пока размер топологии уменьшается. Одним из недостатков такого подхода является попадание в локальные минимумы. Пример локального и глобального минимума при сжатии по X направлению приведен на Рис. 3.20. Для решения данной проблемы предлагается алгоритм [9], который позволяет выходить из локальных минимумов с временным увеличением размера топологии или нарушением некоторых технологических правил. Данный алгоритм выполняется после достижения локального минимума и состоит из следующих шагов: 1. Выбрать способ трансформации топологии. 2. Выполнить трансформацию топологии для выхода из локального минимума 3. Выполнить сжатие для коррекции технологических правил и достижения исходного размера топологии. 4. Если сжатие прошло успешно, то продолжать итерационное сжатие, иначе восстановить исходную топологию, выбрать следующий тип трансформации топологии и перейти на шаг 2. Алгоритм последовательно выполняется несколько раз для различных методов трансформации топологии.
При этом изменяется форма фигур, выполняется удаление и добавление фигур, а также создаются дополнительные ограничения, влияющие на форму и размер фигур. Предлагаются следующие методы трансформаций топологии: Выпрямление меандров: Меандр, принадлежащий критическому пути, значительно увеличивают его длину. Для его удаления из критического пути в топологию добавляются ограничения, которые при сжатии в направлении Y будут выпрямлять меандр и выталкивать посторонние объекты за его пределы, как показано на Рис. 3.21.
Способы применения линейной декомпозиции
Предложенный метод делает возможным применение 1.5-мерного сжатия [13] для больших фрагментов топологии (свыше 500 транзисторов). Предлагается два способа применения данного подхода: сжимать отдельные рыхлые фрагменты топологии; сжимать очень большие ячейки, используя сканирующее окно. Для снижения размерности задачи сжатия можно рассматривать не всю топологию, а только некоторые ее рыхлые фрагменты, как показано на Рис. 4.6, и проводить сжатие только данных фрагментов. Обычно рыхлая топология возникает на месте стыковки отдельно синтезированных фрагментов и может быть выделена автоматически. Такой подход позволяет не применять сжатие к плотным фрагментам топологии, что существенно экономит время. В случае если топология собрана из нескольких одинаковых фрагментов (например, топология сдвигового регистра), данный подход позволяет сохранить ее регулярность. Для сжатия всей топологии большого блока предлагается применять сканирующее окно. При данном подходе окно постепенно сдвигается в направлении сжатия от одного края топологии до другого. Размер окна определяет компромисс между качеством и временем сжатия. Чем шире окно и больше область перекрытия соседних окон, тем лучше качество сжатия, но больше время. В данной главе описан метод линейной декомпозиции топологии, который является модификацией [76].
Предложенный способ обработки объектов топологии в области сечения позволяет уменьшать размерность задачи сжатия, избегая потерь площади, обусловленных запрещенными регионами и краевыми ситуациями, возникающими в [76]. Учет объектов окружения дает возможность применить 1.5-мерные методы сжатия, что существенно увеличивает плотность топологии. В отличие от ранее предложенного подхода, всегда гарантируется построение допустимого сечения. Применение данного метода позволяет применять рассмотренные алгоритмы сжатия не только для топологии стандартных ячеек, но и для больших фрагментов топологии. В данной главе проведено исследование предложенных алгоритмов сжатия, которые были реализованы в виде программы на языке C++. Для проведения экспериментов по оценке сложности алгоритмов необходимо выделить параметр, который характеризует размерность задачи сжатия. Как было показано в предыдущих главах, сложность различных алгоритмов, используемых при сжатии, зависит от числа фигур топологии либо от размера графа ограничений: количества его вершин или ребер. Таким образом, необходимо выделить характеристику размера топологии стандартных ячеек, которая имеет линейную зависимость от данных параметров. Для поиска такой характеристики были исследованы различные параметры, характеризующие размер топологии. Исследование проводилось на библиотеке, содержащей 420 стандартных ячеек.
Проведенные эксперименты показали, что таким параметром можно считать количество транзисторов. Количество транзисторов однозначно определяет сложность топологии стандартной ячейки и ее размер. Как видно из Рис. 5.1 число фигур примерно в 10 раз больше, чем транзисторов. Каждая вершина графа ограничений представляет одну или несколько сторон объектов топологии, т.е. можно предположить, что число вершин имеет линейную зависимость от числа сторон объектов топологии. Проведенные эксперименты также показали, что число сторон имеет линейную зависимость от числа фигур топологии, а, следовательно, и от числа транзисторов тоже. Из Рис. 5.2 видно, что количество вершин графа ограничений примерно в 8-10 раз больше числа затворов. Сложность некоторых алгоритмов, описанных в предыдущих главах, зависит от числа ребер графа ограничений. Как показано в [49], и проведенные эксперименты это подтвердили, число ребер в графе ограничений имеет линейную зависимость от числа вершин с коэффициентом 4-10. Рис. 5.3 показывает данные зависимости для X и У направлений. Для Y направления четко просматриваются две линии, которые определяются одно и двух высотными ячейками. Кроме того, ширина топологии стандартной ячейки так же имеет линейную зависимость от числа транзисторов (Рис. 5.4). На рисунке явно прослеживаются три линии, которые соответствуют: одно-высотным, двух высотным и нескольким специализированным ячейкам. Таким образом, для топологии стандартных ячеек число затворов можно считать параметром, характеризующим размер задачи сжатия. Все основные параметры, определяющие сложность алгоритмов сжатия, имеют линейную зависимость от числа транзисторов.
Оценка времени сжатия была проведена на наборе стандартных ячеек, которые имеют размер от 2 до 50 затворов. Среди данных топологий присутствуют как простые комбинаторные ячейки (простейшие логические функции: и, или, не, и т.д.), так и последовательностные (содержащие обратные связи), которые имеют более сложную топологию. В большинстве случаев реальная сложность алгоритмов отличается от наихудшего случая, оценки которого были проведены в теоретической части диссертации. Таким образом, необходимо выявить зависимость времени сжатия на реальных примерах. Как было показано в Главе 2, сжатие топологии стандартной ячейки можно разделить на 2 независимых этапа
