Диссертация (1090534), страница 17
Текст из файла (страница 17)
При компилированиивысокооптимизированной библиотеки из исходного кода, компилятор gccвыполняет оптимизации, при которых объем занимаемой памяти квадратичнозависит от длины логического выражения. Для компенсации этого эффекта КНФформула может быть разделена на отдельные выражения:bool check_layout (const Layout& l) {assert (l.size() == maxidx);const bool a0=((l[0] && l[1]));5const bool a1=((l[3] && l[2]));83...return a0 || a1 ... ;};Предложенная оптимизация позволила добиться снижения временныхзадержек на выполнение каждой итерации проверки нарушений правилпроектирования на четыре порядка: с 10−2 сек. до 10−6 сек., по сравнениюс вариантом, основанным на коммерческом программном комплексе.Рис. 3.17.
Пример графа, описывающего отношения разрешенных топологийПопарные отношения между разрешенные топологиями могут бытьописаны кликами графа. Практический интерес представляют максимальныеклики — полные подграфы, которые не могут быть расширены добавлениемновых вершин. Для перечисления максимальных клик графа в диссертационнойработе используется алгоритм, представленный в работе [93].Выходными данными реализованного алгоритма является множествомаксимальных клик, соответствующие подмножеству конъюнкций формулы(3.5).
Каждое такое подмножество описывает группу топологий, которые несоздают нарушений при установке встык друг с другом. На Рисунке 3.18представлены две максимальные клики графа, изображенного на Рисунке 3.17.Формулы (3.7) и (3.8) описывают топологии, входящие в каждую из построенныхмаксимальных клик.C1(x0 , x1 , x2 , x3 , x4 ) = ¬x0 ¬x1 ¬x2 ¬x3 ¬x4 ∨ ¬x0 x1 ¬x2 ¬x3 ¬x4 ∨∨ ¬x0 ¬x1 ¬x2 x3 ¬x4 ∨ ¬x0 x1 ¬x2 x3 ¬x4(3.7)C2(x0 , x1 , x2 , x3 , x4 ) = ¬x0 ¬x1 ¬x2 ¬x3 ¬x4 ∨ ¬x0 ¬x1 x2 ¬x3 ¬x4(3.8)84а)б)Рис. 3.18. Примеры двух максимальных клик. Вершины клик закрашены темнымцветом3.5 Построение компактного описания правил на границахГруппы топологий, представленные в виде ДНФ, могут быть использованыв качестве дополнительных ограничений вида “если текущая топология не входитв множестве разрешенных, то она запрещена”.
Однако, ДНФ представлениеявляется избыточным и трудоемкими при анализе пользователем, они такжемогут потребовать больших объемов памяти для хранения. Компактноепредставление правил проектирования на границах может быть полученаметодами минимизации логических функций.В диссертационной работе был реализован алгоритм выводавспомогательных правил проектирования на границах ячеек для каждоймаксимальной клики. Задача сводится к минимизации логических функций.Каждая полученная на предыдущем этапе клика соответствует подмножествуконъюнтов в формуле, описывающей все разрешенные топологии. Дляпостроения компактного описания дополнительных правил проектированиямогут быть использованы техники минимизации логических функций.
Вдиссертационной работе правила проектирования описывают запрещенныекомбинации объектов. Полученная компактная формула описывает разрешенныетопологии. Таким образом, для каждой компактной формулы C1min и C2minнеобходимо найти отрицание. Резльтат выполнения этой операции может бытьинтерпретирован следующим образом: “любая топология, не входящая в заданноемножество, является запрещенной”.
Примеры подобных преобразованийпоказаны в Таблицах 2 и 3. Каждый полученный конъюнкт кодируется85следующим образом: символ 1 соответствует представленному элементутопологии, 0 — отсутствующему, “−” — значению “не важно”.Таблица 2 — Построение правила проектирования на границах ячеекдля клики C1C1(x0 , . . . , x4 ) C1min (x0 , . . . , x4 ) ¬C1(x0 , .
. . , x4 )v1 ) 000001−−−−v2 ) 010000−0−0−−1−−v4 ) 00010−−−−1v5 ) 01010Таблица 3 — Построение правила проектирования на границах ячеекдля клики C2C2(x0 , . . . , x4 ) C2min (x0 , . . . , x4 ) ¬C2(x0 , . . . , x4 )v0 ) 00000−−1−−00 − 00v3 ) 00100Таким образом, результатом работы процедуры для двух полученных ранееклик является две формулы:¬C1min (x0 , . . . , x4 ) = x0 ∨ x2 ∨ x4¬C2min (x0 , . .
. , x4 ) = x2Полученные выражения описывают определенные варианты запрещенныхтопологии. Однако, данные топологии являются запрещенными только привозникновении рядом с границами стандартных ячеек. Для построениякорректных правил проектирования, к полученным формулам необходимодобавить переменные, соответствующие границам стандартных ячеек:¬C1min (x0 , . . . , x4 ) = CB ∧ (x0 ∨ x2 ∨ x4 )¬C2min (x0 , . . . , x4 ) = CB ∧ x2Полученные выражения интерпретируются следующим образом: “если естькакой-либо объект из входящих в формулу И и есть заданная граница стандартныхячеек, то данная топология запрещена”. Графическое представление данныхправил приведено на Рисунке 3.19.86а)б)Рис.
3.19. Первый вариант правила проектирования на границе ячейки (а)и второй (б). Темным окрашены запрещенные элементы топологии, светлымотмечены разрешенныеВ диссертационной работе для выполнения описанных пребразованийлогических формул используется алгоритм логической минимизацииEspresso [104]. Полученные логические выражения используются для построениялогических деревьев, для которых затем генерируются все возможные смещения,отражения и повороты. Полученные таким образов правила проектированиязатем добавляются к данным, полученным из входного технологического файла.Результатом работы этой процедуры является технологический файл, идентичныйисходному, но расширеный вспомогательными правилами на границах ячеек.Этот файл может быть использован для автоматической трассировки ячеек.Этот этап является заключительным в процедуре автоматического выводадополнительных ограничений на границах стандартных ячеек.3.6Анализ и сравнение различных вариантов ограничений на границахПолученные наборы правил проектирования по разному влияют нахарактеристики стандартных ячеек и, таким образом, оказывают влияние напараметры всей СБИС в целом.
В диссертационной работе предлагаетсяоценивать качество вспомогательных правил проектирования методом синтезастандартных ячеек с учетом дополнительных геометрических ограничений.87В диссертационной работе был реализован метод выбора наболееподходящего правила на границах стандартных ячеек из множества полученныхвариантов. В диссертационной работе критерием оптимальности являетсяплощадь стандартных ячеек, оттрассированных с учетом дополнительныхограничений.Исследуемые геометрические ограничения разделяются на группы.В диссертационной работе правила разделяются по слоям: ограничения,включающие в себя элементы топологии в одном и том же слое попадают водну и ту же группу. Каждая группа правил затем служит входными даннымидля разработанной процедуры построения вариантов правил проектирования награницах.
Результатом работы этой процедуры является технологический файл сдополнительными ограничениями, который используется для синтеза тестовойбиблиотеки ячеек. Выходными данными данной процедуры является списокстандартных ячеек, которые были успешно оттрассированы в рамках заданнойплощади.В случае, если с учетом заданных ограничений не удалось оттрассироватьни одну ячейку, текущее множество правил помечается как некорректное иудаляется из рассмотрения. Иначе, в качестве входных данных для поискавспомогательных правил используется следующая группа ограничений.Схематически этот процесс показан на рис. 3.20. “Правила 1” — первая группаРис. 3.20. Схематическое изображения процесса анализа правил на границахячеекисследуемых правил проектирования, “Правила на границах 2” — построенныеправила на границах ячеек и вторая группа исследуемых правил проектированиявместе.
Темным отмечен вариант технологии, исключенный из рассмотрения —ни одна из предложенных стандартных ячеек не была успешно страссирована. Порезультатам работы оптимальным может считаться множество правил “Правила88на границах 2, вариант 0” — все ячейки были успешно синтезированы при учетезаданных ограничений.Разработанный алгоритм вычисляет оценки качества каждого вариантаправил на границах структурных компонентов, выраженные в числе успешнооттрассированных элементов библиотеки.
Наилучший вариант может бытьвыбран автоматически или же экспертом.3.7 ВыводыВ третьей главе был разработан вычислительный комплексавтоматичического вывода и анализа различных вариантов геометрическихограничений на границах структурных компонентов, предотвращающихнарушения при установке элементов встык. В рамках диссертационной работыпроблема вывода геометрических ограничений представляется в виде задачиоптимизации.
В основе предложенного метода лежит использование формальныхметодов для решения поставленной проблемы. В качестве примера решаемойзадачи рассматривается автоматический синтез стандартных ячеек на этапефизического проектирования СБИС.В качестве модели данных для описания правил проектирования итопологий предлагается использовать трассировочные сетки, в узлах которыхразмещаются дискретные элементы топологии. Геометрические ограниченияпредставляются в виде выражений логики высказываний, которые описываютотношения между различными элементами.
Для моделирования различныхтопологий на границах ячеек выполняется построение окна, внутри которогостроиться трассировочная сетка. Высота окна определяется высотой стандартныхячеек, ширина — размером исследуемых правил.На следующем этапе геометрические ограничения, записанные в видевыражений логики высказываний, транслируется в конъюнктивную нормальнуюформу. Подобное преобразование может быть выполнено различными методами.В диссертационной работе используется преобразование Цейтина. К полученнойКНФ добавляются специальные ограничения симметрии, разрешающие или89запрещающие использование элементов топологии по разные стороны от границячеек.Полученная формула используется в качестве входных данных дляалгоритма перечисления всех возможных решений логического выражения.Результатом работы алгоритма является логическое выражение в дизъюнктивнойнормальной форме.
Каждый конъюнкт в полученном выражении соответствуеттопологии, не содержащей нарушений заданных правил проектирования. Наданном этапе о каждой такой топологии известно только следующее: приустановке такой топологии встык к самой себе образуется также разрешеннаятопология.На следующем этапе выполняется процедура поиска групп топологий.Любая пара топологий в пределах одной группы образует разрешеннуютопологию при установке встык друг к другу. Данная задача разбиения сводится крешению задачи на графах. Каждой топологии ставится в соответствие вершинаграфа. Две вершины соединены ребром тогда и только тогда, когда вместе ониобразуют разрешенную топологию.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
