Целевая функция, минимизирующая изменения, предлагаемая нами.
, данная функция была выведена исходя из графого метода решения, если рассмотреть модель этой функции в графе, то она будет выглядеть так:
Для того, чтобы сохранить расстояние между двумя ребрами Xi и Xj величиной distance, необходимо построить дополнительные вершины и ребра. Т.е. Необходимо внести структуру из двух вершин и пяти ребер, для каждой пары вершин между которыми необходимо сохранить заданное расстояние. r и l – это дополнительные вершины, коэффициенты у вершин должны быть такими, чтобы графовый решатель старался притягивать их к друг другу. Коэффициенты же при Xi и Xj должны быть такие, чтобы графовый метод старался их притягивать к li и rj соответственно. Вся картина должна выглядеть так (Рис22). Где стрелками показаны ожидаемые движения вершин графа, при наличии слека.
Так как между Xi и Xj может существовать другой путь (показан пунктиром) Рис.21, суммарная длинна которого больше, чем величина distance, то решение никогда не будет найдено, удовлетворяющее условию ребра с величиной distance. Всю систему графа для каждой пары можно переписать в виде неравенств, которые будут иметь две переменных с той же целевой функцией, следовательно, решать можно данную задачу обычным симплекс методом.
Минимальный набор дистанций, который необходимо сохранять
Нету еще
Формальное описание работы алгоритма сжатия и миграции
В качестве входной информации требуются формальные описания технологических правил, шаблона (архитектуры) ячейки, и исходная топология. Выходной информацией является топология, удовлетворяющая требованиям технологических правил. Основные потоки данных представлены на Рис.23. Хотя задачи сжатия и миграции топологии несколько отличаются форматами входных/выходных данных и предварительной обработкой топологии, обе используют общий базовый алгоритм, представленный на Рис.24. В основе системы лежит алгоритм 1.5-мерного сжатия топологии [2]. Так как при 1,5-мерном сжатии минимизируется размер топологии только в основном направлении, то необходимо последовательно применять данный алгоритм для вертикального и горизонтального направлений. Данная последовательность определяется тем, что топология стандартной ячейки должна иметь фиксированную высоту, поэтому вертикальное сжатие должно выполняться первым. Если при этом не удалось достичь заданной высоты, то дальнейшее сжатие не выполняется. После проведения сжатия топологии по обоим направлениям выполняется оптимизация топологии по какой либо целевой функции либо минимизации длин проводника, либо минимизация изменений при миграции.
Рис. 18 Входные и выходные данные системы сжатия и миграции топологии
Рис. 19 Блок-схема процесса сжатия топологии
1.5-мерное сжатие [2] - итеративный процесс, где на каждой итерации выполняется одномерное сжатие. После одномерного сжатия выделяется минимальное подмножество объектов, которые препятствуют уменьшению размера топологии в направлении сжатия. Затем выбранные объекты сдвигаются в сторону. Итерации повторяются пока размер топологии уменьшается или не достигнут целевой размер, т.е. высота стандартной ячейки или ее оценка.
Алгоритм одномерного сжатия основан на поиске длиннейших путей в графе ограничений. Граф ограничений для задачи сжатия - это направленный взвешенный граф, описанный выше. Каждая вершина представляет одну сторону контура и характеризуется координатой, которая равна координате стороны. Граф содержит две дополнительные вершины Source и Sink. Source - это вершина, которая не имеет входящих ребер, а Sink - выходящих. Вершины Source и Sink представляют воображаемые границы топологии, для них не существует сторон контура. Ребро графа описывает множество ограничений между соответствующими сторонами контуров. Вес ребра равен длине максимального ограничения.[1]
Кроме ограничений, определяемых технологией, топология должна удовлетворять ограничениям, которые являются внешними. Данные ограничения необходимы для обеспечения стыковки ячеек на кристалле или обеспечения корректной работы схемы (например, ограничения на задержку сигнала).
Множество вершин и ребер основного графа, принадлежащих длиннейшему пути между вершинами Source и Sink, называется критическим подграфом, а его ребра и вершины – критическими. Длина критического пути определяет размер топологии в соответствующем направлении и может быть уменьшена с помощью следующих операций:
-
разбиение критической вершины на несколько новых вершин;
-
удаление критического ребра из графа ограничений.
При поиске длиннейших путей в графе ограничений вычисляются минимально возможные координаты вершин, которые определяют координаты объектов топологии. Однако, в топологии стандартной ячейки существуют объекты (внешние порты и граница ячейки) координаты которых должны быть кратны размеру некоторой сетки. Для решения данной проблемы разработан алгоритм поиска длиннейших путей, позволяющий вычислять координаты таких объектов с учетом сетки [2].
Нахождение критического пути заключается в проходе по графу от вершины Source к Sink и обратно с целью установить минимально и максимально возможное координаты вершин в графе. Вершины, для которых максимальная и минимальная координаты совпадают, будут составлять критический путь. Все другие вершины имеют некоторый диапазон координат, который может принимать вершина, не нарушив при этом ни одного правила. Наличие данного диапазона у большинства вершин будем называть slack. Именно наличие слеков позволяет нам проводить некоторые оптимизации. Выбор оптимизационный функции завилит от текущей задачи, которую решает тополог.
Обзорный пример
Как было выше сказано, большинство САПР работает с различными алгоритмами сжатия. Здесь я постараюсь обзорно показать каждый этап работы с топологией во время миграции одной из стандартных ячеек библиотеки smos10 с использование сжатия по Y-направлению для переноса топологии на другую архитектуру, с большим количеством треков.
Рассмотрим входную топологию в формате GDSII, высота ячейки составляет 8 треков или 11.2 микрона:
Рис. 20 Входная топология ячейки and2_8
Далее запустим миграционный движок на эту ячейку. И первое этап, который мы можему видим – это построение ограничений. Нарушенные ограничений выделены темным цветом, именно они входят в критический путь и заставляют ячейку увеличиться на один трек (Рис 26) до высоты в 12.6 микрон:
Рис. 21 Построение ограничений, выделение нарушенных ограничений.
Следующий этап – это использование 1.5D- сжатия. Все объекты топологии встают на минимально возможные координаты, которые позволяют им технологические правила. Происходит вставка дополнительных контактов.
Рис. 22 Установка в минимум всех объектов топологии и вставка дополнительных контактов.
Далее происходит оптимизация топологии. Все объекты, которые имеют слек участвуют в в работе минимицационной функции. На выходе можно получить топологический шаблон с минимальными длинами проводников (Рис 28):
Рис. 23 Минимизация длин проводников.
Или попытка привести топологию к первоначальному виду (минимизация изменений) Рис 29.
Рис. 24 Минимизация изменений при миграции.
Конечная топология после минимизации изменений похожа на исходную топологию. Что и требовалось от САПР.
В данной работе рассматривалась программная система автоматического сжатия и миграции топологии стандартных ячеек КМОП СБИС, разработанная в компании Freescale Semiconductor. Система поддерживает технологические процессы с минимальными размерами до 32 нм и используется для миграции топологии библиотек стандартных ячеек, а также сжатия топологии в системе CELLERITY [Error: Reference source not found].
Метрики тестирования
Пока черновой вариант таблиц (См черновой файл: tests.xls)
Литература
-
Sherwani N. Algorithm for the VLSI Physical Design Automation. Second Edition. - Kluwer Academic Publishers, 1995. – 538 p.
-
Сотников М.А., Алгоритм сжатия топологии стандартных ячеек субмикронных СБИС // Тр. НИИР. - 2002.- C. 108-112.
-
Juanwen Zhu, Frang Fang, Qianying Tang Calligrapher: A new Layout-Migration Engine for Hard Intellectual Property Libraries. IEEE Transactions on Computer-aided design of integrated circuits and system (September 2005 Volume 24 Number 9) ISSN 0278-0070
-
http://ru.wikipedia.org/wiki/Симплекс-метод материал из Википедии - свободной энциклопедии.
-
К.т.н. Плеханов А.С. Метод минимизации задержек сигналов при сжатии топологии с учетом технологической сетки
-
Sching L.Lin Jonathan Allen. Minplex – A compactor that minimizes the boundary rectangle and individual rectangles in a layout. //Proceeding of the 23rd Design Automation Conference 1986, pp123-130
-
Virtuoso Compactor Reference Manual, Product Version 5.0 http://www.ece.uci.edu/eceware/cadence/compactref/compactrefTOC.html
-
Jeff Wilson, Walter Ng, Via Doubling to Improve Yield // Mentor White Paper, August 2005
-
M.A.Сотников, Э.А.Улуханов, К.С.Муханов, //Улучшение топологии стандартных ячеек субмикронных СБИС для повышения выхода годных
-
F.-L. Heng, Z. Chen, and G.E. Tellez. “A VSLI artwork legalization technique based on a new criterion of minimum layout perturbation.” in Proc. Int Symp. Physical Design (ISPD), Napa Valley, CA. 1997 (pp 116-121)
|
