Диссертация (1090534), страница 15
Текст из файла (страница 15)
Данная формула может быть интерпретированаследующим образом: если отсутствует кусочек металла A И присутствует элементметалла B, И при этом отсутствует хотя бы один элемент металла C ИЛИD, то обнаружено нарушение правила проектирования “минимальная длинапроводника”.а)б)Рис. 3.4. Пример представления правил проектирования в виде логическихвыражений. Конфигурация элементов топологии на сетке (а) и соответствующеелогическое выражение(б)На Рисунке 3.5 представленно другое правило, описывающее переходноеотверстие.
Представленная формула описывает следующее правилопроектирования: если есть переходное отверстие A И нет соответствующихучастков металлов B ИЛИ C, то нарушено правило проектирования “переходноеотверстие между слоями металлизации B–C”.69а)б)Рис. 3.5. Пример представления правил проектирования в виде логическихвыражений. Конфигурация элементов топологии на сетке(а) и соответствующеелогическое выражение(б)Таким образом, правила проектирования могут быть представленны в видедеревьев логических выражений.
Они могут содержать произвольное числопеременных и операторов, глубина дерева при этом не ограничена. Операторывключают в себя следующие отношения: И, ИЛИ, НЕТ, ИСКЛЮЧАЮЩЕЕ-ИЛИ,БОЛЬШЕ–РАВНО, МЕНЬШЕ–РАВНО. Объект, соответствующей переменнойправила, должен либо присутствовать в заданной координате, либо его появлениезапрещено. Любые иные объекты топологии, которые не влияют на текущееправило проектирования игнорируются и не представлены в логическом дереве.При использовании данной модели, правила проектирования могут бытьописаны в виде перечисления всех вариантов топологий.
В таком случаекаждое правило будет представлять собой оператор И, включающий в себядва и более элемента топологии. Обе формы представления технологическихправил логически эквиваленты друг другу, однако, использование компактногопредставления с учетом различных операторов позволяет снизить потреблениевычислительных ресурсов и памяти. Один подход к формулированию правилможет быть сведен к другому методами минимизации логических функций илиметодами преобразования КНФ формул к ДНФ виду. Подобная процедура будетобсуждена подробнее в разделе 3.5.703.3 Алгоритм получения разрешенных топологийНа первом этап необходимо составить модель, описывающую топологий,возникающие на границах стандартных ячеек.
В качестве метода представленияэлементов топологии и правил проектирования использована модель данных,подробно описанная в разделе 3.2. Входным данными на данном этапеявляется технологический файл, описывающий слои, трассировочную сетку,геометрические ограничения и параметры элементов топологии — тип (кусочекметалла или переходное отверстие), принадлежность слою, форму, точкипривязки к узлам трассировочной сетки.
Также данный файл содержитописание специальных виртуальных элементов топологии — границ стандартныхячеек, как горизонтальных, так и вертикальных. Дополнительно может бытьпредоставлена информация об архитектуре стандартных ячеек — о высоте рядаячеек и о расположении линий питания и земли.На данном этапе необходимо построить окно конечного размера, вкотором далее будет выполнятся моделирования различных вариантов топологий.Внутри окна создается трассировочная сетка, описанная в технологическомфайле.
Рассмотрим правило проектирования, запрещающее размещении двухпереходных отверстии в на соседних узлах трассировочной сетки в диагональномнаправлении, представленное на Рисунке 3.6. Пусть высота стандартнойячейки позволяет разместить пять таких переходных отверстий в вертикальномнаправлении. Ширина окна зависит от ширины самого большого правилапроектирования. На Рисунке 3.7 показан пример топологии, нарушающейправило проектирования; черными жирными линиями показаны границыстандартных ячеек, сплошные тонкии линии соответствуют позициям, в которыхмогут быть размещены заданные переходные отверстия.
Крайние позиции сверхуи снизу отстоят от границ стандартных ячеек так, что при совмещении двухячеек в вертикальном направлении нарушения не возникают. Каждый узел наиллюстрации пронумерован – от 0 в верхем левом углу до 9 в правом нижнем.Соответствующую нумерацию имеют и переходные отверстия.Заданные правила проектирование создаются во всех возможных узлахтрассировочной сетки, с учетом возможных отражений и поворотов (Рисунок 3.8).В рамках поставленной задачи интерес представляют только те правила71а)б)Рис.
3.6. Пример представления правил проектирования в виде логическихвыражений. Формула(а) запрещает топологию(б)проектирования, которые пересекают границы стандартных ячеек (как вгоризонтальном, так и вертикальном направлении), и, иными словами, могут бытьнарушены при составлении топологии из нескольких элементов.
В дальнейшембудут рассматриваться только те элементы топологии на трассировочной сетке,которые входят в эти правила проектирования на границах ячеек. Остальныеобъекты не оказывают влияния на исследуемые правила проектирования и могутбыть опущены. Для моделирования топологий с учетом правил проектирования,пересекающих вертикальную границу, снизу от построенного окна добавляетсяеще одно, такого же размера. В нем там же создаются все заданные правилапроектирования.При таком построении правила проектирования могут покрывать объектыза пределами построеного окна, часть из которых необходимо учитывать впроцессе моделирования, часть должны быть опущены. В диссертационнойработе используется следующая процедура анализа правил проектирования.Рассмотрим ограничение на минимальную длину проводника, представленноена Рисунке 3.4, два варианта которого вписаны в окно.
На Рисунке 3.9представленно схематическое изображение обоих вариантов. Жирная чернаялиния обозначает границу стандартной ячейки, тонкая пунктирная соответствуетгранице построенного окна. В обоих случаях элемент топологии D выходит запределы окна и о его влиянии на топологию внутри ничего неизвестно.72Рис. 3.7. Пример запрещенной топологии с показанными границамистандартных ячеекРис.
3.8. Все варианты правила проектирования с учетом отражений и поворотовВ случае, показаном на Рисунке 3.9(а), правило может быть нарушенопри отсутствии элемента C и, таким образом, данное ограничение необходимоучитывать на дальнейших этапах. Вместе с тем, правило, показанное наРисунке 3.9(б), не может быть нарушено без учета элемента D. Для поискаподобных избыточных правил в рамках диссертационной работы используетсяследующая процедура.
Заданное правило проектирования помечается как“невыполненное”. Каждый элемент топологии, входящий в правило и которыйнаходится внутри построенного окна, помечается как найденный: запрещенныеэлементы помечаются как отсутствующие, обязательные — как присутствующие.С учетом полученных данных вычисляется результат выполнения логических73а)б)Рис. 3.9.
Два варианта ограничения минимальной длины в окне: исходный(а) иотраженный (б)операций над элементами топологии, которые входят в правило проектирования.Если элементы топологии внутри окна могут образовывать запрещеннуюправилом комбинацию, то все правило будет помечено как “выполнимое”. Врезультате процедуры также будут выделены все узлы логического дерева,которые могут образовывать нарушение. Все узлы, которые не имеютсоответствующей отметки, могут быть удалены из дальнейшего рассмотрения,включая корневой узел всего логического дерева — тогда все правилопроектирования может быть исключено. Пример показан на Рисунке 3.10.Серым отмечены узлы логического дерева, которые могут быть исключеныиз рассмотрения.
Правило, представленное на Рисунке 3.10(б), может бытьудалено — значение его корневого узла невозможно определить, зная только обэлементах топологии внутри окна. Данная процедра обепечивает корректностьпостроения топологий на дальнейших этапах и, дополнительно, сокращаеттребуемые объемы памяти для хранения правил проектирования за счет удаленияизбыточных ограничений и элементов топологии.а)б)Рис. 3.10. Логические деревья с отмеченными избытычными вершинами74На данном этапе построено окно фиксированного размера. Оно включаетв себя множество дискретных точек, определяемых трассировочной сеткой.К каждой точке привязаны объекты топологии, которые в ней могут бытьразмещены.
Также определен список правил проектирования в виде логическихфункций поверх объектов топологий. Важно отметить, что при такой постановкезадачи, границы стандартных ячеек могут быть рассмотрены как оси симметрии.Любое дополнительное правило будет действовать с обеих сторон от границыячейки, как это показано на Рисунке 3.11. Такие отношения действуют какв горизонтальном, так и в вертикальном направлении. Они могут бытьинтерпретированы следующим образом: если объект топологии xi можетбыть размещен в конкретной фиксированной позиции, то также должныбыть разрешены соответствующие ему объекты справа от границы ячейки,снизу и справа–снизу.
Пример такого отношения показан на Рисунке 3.12.Зелеными линиями обозначены элементы топологии, соответствующиеграницам ячеек. Пунктирные стрелки указывают на отношения симметриимежду объектами. Например, так как объект x1 разрешен, то разрешены исоответствующие ему объекты x8 , x11 , x18 . Подобные отношения симметриимогут быть выражены при помощи ограничений на равенство значений булевыхпеременных, соответствующих заданным элементам топологии, пример которогоприведен на Рисунке 3.13.а)б)Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
