Оглавление
Оглавление 1
Вступление 2
Введение в компакцию 3
Оптимизация. 4
Задача для WireMinimization 4
Метод WireMinimizer 5
Целевые функции 5
Расстояния в шаблоне, сохранение которых приводит к сохранению пропорциональности 7
Реализация в BearTM 8
Вступление
Сейчас на рынке очень много тулов для работы с топологией. Очень много их основанных на сжатии. Методы сжатия могут сильно изменить топологический шаблон, а, следовательно, нарушить работу схемы, которую представляла заданная топология. Рассмотрим пару примеров.
Необходимо подкорректировать топологию, так как вышла новая версия DRM (новая ревизия технологических правил), включающая в себе новые или чуть измененные старые правила технологии. Конечно же, можно заново перерисовать все шаблоны, сделанные по старой ревизии технологии, но это будет крайне не эффективная трата, как человеко-часов дизайнера, так и денег компании. Поэтому последнее время появились тулы, которые позволяют редактировать топологию под новые технологические правила. Если эти тулы основаны на сжатии топологии, то они, просто сожмут шаблоны топологий до минимальных размеров, предусмотренных в DRM, тем самым могут быть нарушены некоторые задумки дизайнера, которые были внесены в топологические шаблоны. Например, дизайнер мог увеличить ширину шин для того, чтобы уменьшить эффект электромиграции, но после работы тула данные шина может сжаться до минимальных размеров проводника, тем самым появиться уязвимое место в шаблоне чипа. Второй пример из данной области – это наличие «глупого» проводника, расположенного между двумя проводниками, цель которого это ликвидировать наводки одной цепи на другу. После работы тула, он сожмется и примет размер по площади минимально доступный и перестанет играть роль защитника одной цепи от другой. Пример можно посмотреть на рисунке.
Далее, это расположение контактных окон транзисторов, если их местоположение измениться координально, то скорость переключения транзистора может также измениться. Поэтому следует сохранять первоначальную структуру шаблона топологии. Еще одна область, где целесообразно сохранить первоначальную структуру шаблона. Помимо DR правил существуют DF правила. Эти правила являются необязательными и служат для того, чтобы повысить выход годных с данной технологии. Выполнять эти правила стоит с учетом сохранения первоначальной структуры шаблона. Также можно внести еще одну область применения алгоритмов сохранения топологии – это перенос шаблонов с одной технологии на другую. По новым правилам с применением тула, основанного на компакции, мы можем получать шаблоны, которые будут кардинально отличаться от первоначальных, в старой технологии.
В данной статья я опишу подход, с помощью которого можно сохранить структуру первоначального топологического шаблона после работы компактора.
Введение в компакцию
Компакция представляет собой сжатие топологии до минимальных размеров, предусмотренных в технологии, по которой сделан данный шаблон. Это значит все правила, которые имеются в технологии выглядят таким образом: минимальный промежуток для данного слоя должен быть в 5а, минимальна ширина шины должна быть 3а, размер затвора поликремния, а минимальная площадь активной диффузионной области 10а в квадрате ну и т.д.. Мы будем рассматривать компакцию на основе графа ограничений, где каждое правило накладываемое на каждое вхождение его в топологии, представлено в виде множества или одного неравенства. Т.е. в конечном счете, мы имеем целый набор неравенств вида , где x и y – это края топологических контуров, а v – это значение, которое допустимо быть между ними. Ввиду того, что мы имеем набор неравенств второго порядка, то мы можем представить данный набор в виде взвешенного направленного графа G(V,E).
В данном графе вершины – это координаты краев топологических контуров, между которыми, активно правило, выраженное в виде ребра, а величина ребра показывает минимально допустимое значение между ними. Также в графе обычно присутствуют две специальные вершины – это Source и Sink. Source – это вершина, которая ограничивает весь набор координат с низу, и Sink – это вершина, которая ограничивает сверху.
Различают компакцию, как 1 мерную, так и 2 мерную. 1 мерная компакция учитывает правила только по 1 направлению X или Y, а двумерная – это учет правил сразу по обоим направлениям, что значительно усложняет задачу.
Весь граф со всеми вершинами и ребрами представляет собой топологический шаблон сделанный по определенной технологии. Решить граф – это значит найти в нем критический путь – это самый длинный путь от вершины Source до Sink. Возможное проблемы при обходе графа – это наличие положительных циклов. Цикл – это комбинация ребер и вершин в графе, обход по которым с учетом направлений ребер приводит к зацикливанию. В графе изображенном выше присутствует один положительный цикл - это путь 2-3-2-3-.... Прежде чем решать граф необходимо избавиться от всех положительных циклов. Нахождение критического пути заключается в проходе по графу от вершины Source к Sink и обратно с целью установить минимально и максимально возможное координаты вершин в графе. Вершины, для которых максимальная и минимальная координаты совпадают, будут составлять критический путь. Все другие вершины имеют некоторый диапазон координат, который может принимать вершина, не нарушив ни одного правила. Наличие данного диапазона у большинства вершин будем называть slack. Именно наличие слеков позволяет нам проводить некоторые оптимизации, одна из них – это возможность расставить вершины максимально приближенном к первоначальному варианту топологии до компакции.
Оптимизация.
Оптимизация представляет собой решение всех неравенств с учетом некоторой целевой функции. Известно, что решая набор неравенств можно получить некоторую область в n-мерного пространства, где n – это количество переменных в системе неравенств. Если же задать целевую функцию на данной области решений, то можно получить единственно решение, бесконечно много решений или ни одного решения. Система неравенств с заданной целевой функцией представляет собой задачу линейного программирования. В общем виде она выглядит так:
Решать данную задачу можно симплекс методом. Но в нашем случае задача немного облегчена, все наши неравенства состоят из двух переменных, поэтому решать данную задачу можно специальным методом. Метод этот носит название WireMinimization, которые применяют для решения задачи, в которой необходимо уменьшить длину всех проводников.
Задача для WireMinimization
Данная задача сводиться к тому, что на выходе нужно получить топологический шаблон с минимальными длинами проводников Минимизация длин проводников – это один из видов оптимизации. Её результатом является топологический шаблон, у которого все контакты соединены проводниками, а сумма длин всех проводников является минимально возможной при данном расположении контактов.
Целевая функция минимизации представлена в таком виде:
, если раскрыть скобки, то можно привести к виду
, где l пробегает все значения i и j, а значения коэффициента k являются отрицательными при всех значениях j. На рисунке это выглядит так:
Здесь xi и xj – это края проводника в направлении x, а ki и kj - это соответствующие коэффициенты. Эти коэффициенты можно представить как сопротивление проводника в данном месте. Сопротивление можно вычислить, как ортогональный размер, обозначенный стрелочками, умножить на сопротивление удельной длины материала данного слоя. Для того чтобы минимизировать длину проводника, нам нужно найти его минимально возможную разность его краев.
Задачу такого типа решается на направленном графе. Необходимо только расширить модель графа ограничений. Помимо весов ребер, которые представляю собой величины правил, необходимо добавить веса вершин, которые будут обозначать соответствующие коэффициенты при соответствующем x из целевой функции.
Плюсы данного метода перед симплекс методом:
-
Это графовый метод решения, а как следствие из этого – выигрыш в скорости
-
В симплекс методе присутствует деление, а это значит, что мы имеем дело с дробными величинами, что приводит к накоплению ошибок в решении.
Метод WireMinimizer
Целевые функции
На данный момент существует три целевых функции, которые позволяют получить на выходе с различной степенью похожести, исходный шаблон.
-
, здесь - это вектор переменных, участвующих в вешении, а - это вектор их старых значений. Минусы данной функции описаны в статье [1].
-
, здесь и - это - координаты правого и левого ребра каждой пары ребер i-ого объекта топологии. Константы и - это - координаты правого и левого ребер соответственно в первоначальной топологии. Здесь вместо минимизации изменения абсолютных значений координат ребер, минимизируется изменение всех фигур топологии. Т.к. эта функция содержит модуль, то ее нельзя решить привычными методами. Необходимо линеаризировать функцию, избавившись от модуля. Чтобы это проделать воспользуемся материалом статьи [2]. Метод, описанный в статье, линиаризирует функцию, содержащую модуль, но при этом к набору неравенств добавляется дополнительные неравенства. Дополнительные неравенства выглядят так:В нашем случае на каждую пару ребер добавляются две дополнительные переменные и , а целевая функция замениться на . Недостатком данной функции – это содержание трех переменных в неравенствах, а это означает, что мы не можем использовать модель ортогонального взвешенного графа.
-
, данная функция была выведена исходя из графого метода решения, если рассмотреть модель этой функции в графе, то она будет выглядеть так:Для того, чтобы сохранить расстояние между двумя ребрами xi и xj величиной distance, необходимо построить дополнительные вершины и ребра. Т.е. Необходимо внести структуру из двух вершин и пяти ребер, для каждой пары вершин между которыми необходимо сохранить заданное расстояние. R и l – это дополнительные вершины, коэффициенты у вершин должны быть такими, чтобы графовый решатель старался притягивать их к друг другу. Коэффициенты же при xi и xj, должны быть такие, чтобы графовый метод старался их притягивать к li и rj соответственно. Вся картина должна выглядеть так: Т.к. между xi и xj может существовать другой путь (показан пунктиром), суммарная длинна которого больше, чем величина distance, то решение никогда не будет найдено, удовлетворяющее условию ребра с величиной distance. Всю систему графа для каждой пары можно переписать виде неравенств, которые будут иметь две переменных с той же целевой функцией, следовательно, решать можно данную задачу обычным симплекс методом.
Расстояния в шаблоне, сохранение которых приводит к сохранению пропорциональности
Структуру, которую мы добавляем к вершинам, между которыми хотим видеть определенно расстояние, мы обозначим, как пользовательское ограничение, т.к. простыми ограничениями называют технологические правила.
Для того чтобы сохранить топологию в первоначальном состоянии, нам необходимо выделить места, на которые нужно установить пользовательские ограничения. Помимо технологических правил в граф добавятся дополнительные ограничения, решение которых будет стремиться привести к первоначальному виду нашу топологию. Рассмотрим данные места (на рисунках отмечены стрелочками).
-
Это сохранение размеров объекта топологии. Это значит, что необходимо сохранить такие же значения всех ширин объекта топологии, что и в первоначальном.
-
Это сохранение формы объекта. Данная задача необходима для того, чтобы избежать плавания одной части объекта над другой. Здесь прерывистой линией на конечном объекте топологии показано неправильное решение, которое может возникнуть, если пренебречь сохранением формы объекта.
-
Сохранение положений объектов топологии относительно друг друга. Чтобы объекты не «плавали» в бибоксе относительно друг друга их необходимо как-нибудь закрепить. Инструментом крепления прекрасно подходят контактные окна. С помощью контактных окон соединены почти все топологические объекты, следовательно, если мы сохраним положение контактных окон внутри топологических объектов, то мы заставим сохранить свои позиции относительно друг друга все объекты топологии, которых контактное окно соединяет. Таким образом, у нас будут еще «плавать» группы объектов топологии внутри бибокса, а также те объекты топологии, которые не имеют контактных окон. Для того чтобы предотвратить данную проблему нам достаточно зацеплять данные группы или отдельные объекты топологии за какой-нибудь край боундарибокса. На рисунке линии красного цвета показывают край боурдари бокса.
-
Выравнивание контактов между параллельными затворами двух транзисторов. Это частная задача, которая может быть выполнена на данном этапе. Данная задача как раз не сохраняет, а наоборот, изменяет топологию.
Если стремиться выполнить все эти подзадачи (кроме последней), то выходной топологический шаблон будет максимально похож на шаблон до компакции.
Реализация в BearTM
В программном комплексе BearTM реализована возможность сохранять пропорциональность между входным и выходным шаблонами. Входными данными для этого маршрута служит граф, вершины которого установлены в минимум. Сам маршрут состоит из трех этапов. На первом этапе вершинам графа задаются веса для минимизации длин проводников. Это сделано для того, чтобы решатель учитывал задачу минимизации длин проводников для тех вершин, которым не нужно задавать веса для сохранения расстояний. Затем добавляются новые пары вершин L и R для каждой пары вершин, между которыми нужно сохранить расстояние, и задаются дополнительные веса для них. В последнем этапе граф с дополнительными вершинами попадает, как входные данные, решателю, который двигает вершины графа согласно заданным коэффициентам у вершин. Решателей сейчас два. Первый – это решатель, основанный на графовой модели, и второй – решатель, использующий библиотеку LP Solve для решения задач линейного программирования. Абстрактно весь маршрут выглядит следующим образом:
На выходе мы получаем граф, вершины которого расставлены согласно целевой функции, по которому можно восстановить топологию.
Литература
1.
2.
|
