Задача минимизации длин проводников
Данная задача сводиться к тому, что на выходе нужно получить топологический шаблон с минимальными длинами проводников, т.е. результатом оптимизации на сжатой топологии является уже топология, у которой все контакты соединены проводниками, а сумма длин всех проводников является минимально возможной при данном расположении контактных окон.
Целевая функция минимизации представлена в таком виде:
, если раскрыть скобки, то можно привести к виду
, где l пробегает все значения i и j, а значения коэффициента k являются отрицательными при всех значениях j. На рисунке это выглядит так:
Здесь xi и xj – это края проводника в направлении x, а ki и kj - это соответствующие коэффициенты. Эти коэффициенты можно представить как сопротивление проводника в данном месте. Сопротивление можно вычислить, как ортогональный размер, обозначенный стрелочками, умножить на сопротивление удельной длины материала данного слоя. Для того чтобы минимизировать длину проводника, нам нужно найти его минимально возможную разность его краев.
В САПР от Cadence Virtuoso Compactor [7] коэффициенты ki берутся из специального технологического файла. Данные коэффициенты называются весами. Этот метод минимизации проводной длины определяется, как “взвешенная минимизация". Чем выше вес для объектов слоя, тем больше приоритет компактор дает для уменьшения длины проводов на том слое. Если никакие веса на заданы, то компактор использует веса по умолчанию. В CMOS библиотеке по умолчанию веса для диффузионного слоя больше чем веса для слоя поликремния, который в свою очередь больше чем веса для металлических слоев. Объяснить это можно только тем, что сопротивление слоя диффузии больше, чем поликремния, который в свою очередь больше, чем сопротивление металлических слоев. Компактор выполняет минимизацию длинные проводов уже после сжатия топологии, используя эвристический алгоритм. Данный алгоритм не гарантирует никакого абсолютного минимума и не пытается уменьшить размер ячейки.
Вообще задачу такого типа решается на направленном графе. Необходимо только расширить модель графа ограничений. Помимо весов ребер, которые представляю собой величины правил, необходимо добавить веса вершин, которые будут обозначать соответствующие коэффициенты при соответствующем из целевой функции.
Данную задачу можно решить двумя способами: Симплекс или специальным графовым методами. Основные преимущества графового метода перед симплекс-методом:
-
В симплекс методе присутствует деление [4], а это значит, что мы имеем дело с дробными величинами, что приводит в итерационном процессе к накоплению ошибок в решении.
-
Очень часто требуется внести дополнительные ограничения, в частности, в последних технологических процессах все объекты топологии должны находиться в технологической сетке. Математически это требование может быть представлено:
, (5)
где X – это координата вершины графа , соответствующего объекта, размещаемого в сетке, T – это число объектов координаты которых должны быть кратны шагу сетки, Р – период , B-смещение технологической сетки относительно начала координат и n – целое число.
Важно подчеркнуть, что задача оптимизации (4) с такими дополнительными ограничениями (5) уже не является линейной, поэтому симплекс методом уже не может быть решена.
Графовый метод решения задач оптимизации
Задача минимизации функции с ограничениями (4) решается известным методом линейного программирования – симплекс-методом. Поскольку этот метод требует обработки большого объема информации в виде таблиц, был предложен подход, использующий граф ограничений. В этом случае каждой вершине графа приписывается вес, равный сумме весов ki проводников, подходящих к данной вершине, взятой со знаком плюс., если направление проводника от вершины совпадает с направлением сжатия, и знаком минус в противоположном случае Рис (11). Вычисленный таким образом вес вершины показывает направление перемещения объекта топологии, связанного с этой вершиной, при котором суммарная задержка будет уменьшаться. Если вес вершины больше нуля, это направление совпадает с направлением сжатия, в случае же веса меньше нуля – это противоположное направление. Как известно, симплекс - метод минимизирует функцию путем перехода, от одного допустимого решения к другому, при этом требуя, чтобы менялась только одна базовая переменная. Это требование приводит к тому, что в графе ограничений в каждый момент времени существует множество подграфов, каждый из которых является деревом. В вершине этих деревьев находятся неподвижные вершины, то есть вершины, координаты которых нельзя изменять. Каждое ребро, принадлежащее такому подграфу, имеет минимально возможную длину и называется критическим. Такие ребра соответствуют базовым переменным симплекс метода. Минимизация может начинаться только с допустимого решения. Доказано [6], что граф, соответствующий топологии, полученный в результате сжатия, удовлетворяет такому требованию, поскольку на нем всегда можно найти множество соответствующих подграфов, являющихся деревьями.
Поскольку в [6] излагаются только общие идеи, то в [5] к.т.н. Плеханов А.С. указал метод, который позволяет решить задачу минимизации с дополнительными ограничениями, указанными в (5). Для начала опишем алгоритм, который позволяет находить минимум без учета (5) Рис 12.
Исходные данные: граф ограничений, координаты вершин поле сжатия топологии, веса вершин.
Результат: Координаты вершин графа, минимальная суммарная задержка сигналов.
Рис. 11 Алгоритм решения без учета ограничений на сетку
Поясним создание групп вершин графа. Пусть имеется критическое ребро графа. Находим вершину, их которой выходит данное ребро (FromNode) и вершину, в которую оно входит (ТоNode). Находим подграф, в который входит данное ребро. Делим данный подграф таким образом, чтобы получить два подграфа, в один из которых входит FromNode, а в другой входит ToNode. Поскольку исходный подграф является деревом, очевидно, что полученные подграфы также являются деревьями. Из полученных двух подграфов выбираем тот, который не содержит неподвижной вершины (т.е. у вершины нет слека), являющейся вершиной исходного подграфа. Из вершины этого графа образуем группу, которая будет использоваться для дальнейшей обработки.
Проиллюстрируем это на примере. На Рис .13 показан граф, соответствующий некоторой топологии после сжатия. Все вершины графа имеют минимально возможные координаты и определенный вес. Возьмем ребро между вершинами N8(FromNode) и N9(ToNode). Это ребро принадлежит подграфу, в который входит вершина Source, NN3,4,5,7,8,9,10 и Sink, а принадлежащие ему ребра показаны сплошными стрелками. Делим этот подграф на два подграфа таким образом, чтобы вершина N8 входила в один, а N9 – в другой. Первый подграф состоит из вершин Source, NN3,4,7 и 8, а второй – из вершин NN9,5,6,10 и Sink. Теперь вершина Source, являющаяся вершиной исходного подграфа, содержится в первом из полученых подграфов. Следовательно, группу формируем из вершин NN 9,5,6,10 и Sink.
Рис. 12 Определение групп вершин графа по ребру между вершинами N8 и N9
Вычисляем вес полученной группы, как сумму весов всех входящих в нее узлов. Аналогично весу отдельного узла, вес группы показывает направление ее перемещения для уменьшения суммарной задержки.
Выполняется данное перемещение групп до тех пор, пока можно осуществить хотя бы одно изменение координат вершин графа, приводящее к уменьшению целевой функции.
Следует отметить важное обстоятельство: в результате этих действий, несмотря на изменение состава и конфигурации подграфов, общая структура графа в виде множества деревьев остается неизменной.
При учете дополнительных ограничений вида(5) задача перестает быть линейной. Дополнительные ограничения приводят к тому, что координата объекта топологии, может быть только дискретные значения на допустимом интервале (слеке). В соответствии с этим координаты вершин, входящих в группу, содержащие данную вершину, также будут принимать только дискретные значения. Это приводит к тому, что решение, полученное приведенным выше алгоритмом, будет не оптимальным.
На Рис 14a объекты, которые находились не в критическом пути, получили неоптимальное решение согласно алгоритму, описанному выше. Алгоритм, описанный в [5], позволяет получать решения в сетке Рис 14b.
Рис. 13 Варианты неоптимального и оптимального решения для объекто, не в критическом пути, с учетом сетки.
Метод решения состоит из двух этапов. На первом этапе ограничения, накладываемые сеткой, не учитываются, и решение получают изложенным выше способом. На втором этапе заданные топологические объекты размещаются в координатах, кратных технологической сетки. При этом используется решение, полученное напевом этапе. Поскольку решение, полученное на первом этапе, является оптимальным, без учета (5), то любое изменение координат топологических объектов либо ухудшает значение целевой функции, либо оставляет его неизменным.
Для решения любой задачи минимизации заданной в (4) с учетом (5) необходимо найти такие новые координаты объектов, при которых заданные топологические объекты находились бы в технологической сетке, а ухудшение целевой функции было бы минимальным. Предположим, что имеется один объект, который необходимо разместить в технологической сетке. Для этого необходимо выбрать координату сетки, в которую будет устанавливаться заданный объект топологии. Пусть координатой объекта является X, а ближайшие координаты технологической сетки есть X0 и X1 (X0X)(Рис. 15).
Рис. 14 Выбор координаты технологической сетки для размещения проводника.
Для выбора из этих двух возможных координат ту, в которой будет установлен объект, используем следующий алгоритм:
Исходные данные: граф ограничений, объект топологии, который необходимо установить в координату X0 или X1.
Результат: Координата X0 или X1.
-
Проверяем условие (4) при установки объекта в координату X0. Если условия выполняются, ставим Flag0=1, иначе Flag0=0.
Проверяем условие (4) при установки объекта в координату X1. Если условия выполняются, ставим Flag1=1, иначе Flag1=0.
-
If ((Flag0 == 1) и (Flag1 == 0)) {
Выбираем X0
} else {
If ((Flag1 == 1) и (Flag0 == 0)) {
Выбираем X1
} else {
If ((Flag1 == 1) и (Flag0 == 1)){
If (X- X0 < X1-X) {
Выбираем X0
} else {
Выбираем X1
}
} else {
Ошибка
}
}
}
Таким образом, задача установки объекта в сетку сводится к задаче оптимального перемещения объекта из одной координаты в другую.
|
