Автореферат (1090533), страница 4
Текст из файла (страница 4)
Вершина соответствует -ой топологии. Ребросоединяет две вершинытогда и только тогда, когдасоответствующие топологии вместе не содержат нарушений правил проектирования. Пример графа, соответствующего формуле (6), приведен на Рисунке7. Нумерация вершин графа соответствует обозначению топологий, изображенных на рисунке 4, например, вершина соответствует Рисунку 4б. Построение такого графа требуетчисла операций, где – число вершин.Рис. 7. Пример графа, описывающего отношения разрешенных топологийКаждому классу топологий соответствует клика — подграф, все вершины которого попарно соединены ребрами — на заданном графе . Интерес представляют максимальные клики — подграфы, которые нельзя расширить включением дополнительных вершин.
Такие клики соответствуютгруппам топологий, включающим наибольшее число разрешенных комбинаций объектов, и, таким образом, обеспечивающими наибольшую свободу притрассировке стандартной ячейки. Задача поиска клик является сложной иплохо поддается аппроксимации. В литературе рассматривается множествоалгоритмов для поиска клик, работающих как за экспоненциальное время вобщем случае, так и за полиномиальное время в случае отдельных семействграфов.
В диссертационной работе используется алгоритм, который для поиска каждой следующей максимальной клики требуетвремени ипамяти, где— время, необходимое для умножения двух матрици — число вершин графа.Выходными данными реализованного алгоритма является множествомаксимальных клик, соответствующие подмножеству конъюнкций формулы(6). Каждое такое подмножество описывает группу топологий, которые несоздают нарушений при установке встык друг с другом. На Рисунке 8 представ лены две максимальные клики графа, изображенного на Рисунке 7.Рис. 8. Примеры двух максимальных клик. Вершины клик закрашенытемным цветом17Полученные множества топологий, соответствующие максимальнымкликам, уже могут быть использованы в качестве дополнительных правилпроектирования. На практике, однако, число разрешенных топологий можетбыть крайне велико. Для их обработки и хранения могут потребоваться значительные объемы вычислительных ресурсов.
В диссертационной работебыл реализован алгоритм вывода компактного представления дополнительных правил проектирования на границах ячеек для каждой максимальнойклики. Задача сводится к минимизации логических функций.Каждая полученная клика соответствует подмножеству конъюнктов вформе, описывающей все разрешенные топологии. На базе этого подмножества выполняется поиск отрицания заданного логического выражения, которое можно интерпретировать следующим образом: “любая топология, невходящая в заданное множество, является запрещенной”.
Для этого каждыйконъюнкт кодируется следующим образом: символсоответствует представленному элементу топологии, — отсутствующему, “ ” — значению“не важно”. Для полученной таблицы истинности вычисляется компактноепредставление методами минимизации логических функций. Затем вычисляется отрицание полученной компактной формы. Итоговое логическое выражение является искомым правилом на границах.
Пример подобного преобразования показан в Таблице 2.Для двух полученных ранее клик данная процедура вычисляет два правила, описывающих запрещенные топологии на границах стандартных ячеек,в которых переменнаясоответствует присутствующим в топологии границам ячейки:Таблица 2Построение правила проектирования на границах ячеекГрафическое представление данных правил приведено на Рисунке 9.В диссертационной работе был реализован вычислительный комплексвыбора наиболее подходящих ограничений на границах структурных компонентов из множества полученных вариантов. Оптимальность определяетсяпараметрами структурных компонентов, полученных с учетом рассматриваемых ограничений.18Рис. 9. Первый вариант правила проектирования на границе ячейки (а)и второй (б). Темным окрашены запрещенные элементы топологии,светлым отмечены разрешенныеИсследуемые геометрические ограничения разделяются на группы, например, по отдельным слоям.
Каждая группа правил затем служит входнымиданными для разработанной процедуры построения вариантов правил проектирования на границах. Результатом работы этой процедуры является технологический файл с дополнительными ограничениями, который используетсядля синтеза тестовой библиотеки ячеек.В случае, если не удалось оттрассировать ни один структурный компонент, текущее множество правил помечается как некорректное.
Иначе, в качестве входных данных для поиска дополнительных правил используетсяследующая группа ограничений. Схематически этот процесс показан на Рисунке 10.Рис. 10. Схематическое изображение процесса анализа правил на границах ячеек“Правила 1” — первая группа исследуемых геометрических ограничений, “Правила на границах 2” — построенные ограничения на границах компонентов и вторая группа исследуемых геометрических ограничений вместе.Темным отмечен вариант технологии, исключенный из рассмотрения — ниодин из предложенных структурных компонентов не был успешно построен.По результатам работы оптимальным может считаться множество ограничений “Правила на границах 2, вариант 0” — все компоненты были успешносинтезированы при учете заданных ограничений.Разработанный алгоритм вычисляет оценки качества каждого вариантаограничений на границах компонентов, выраженные в числе успешно сгенерированных структурных компонентов.
В данной работе критерием качества19выступает площадь структурных компонентов. Исследование того, как дополнительные геометрические ограничения влияют на другие параметрыструктурных компонентов, выходит за рамки диссертационной работы. Вместе с тем, предложенная процедура анализа правил позволяет учитывать различные дополнительные характеристики при исследовании влияния дополнительных правил.
Субоптимальный вариант полученных ограничений может быть выбран автоматически или же экспертом.Четвертая глава посвящена апробации предложенного вычислительного комплекса автоматического вывода геометрических ограничений награницах структурных компонентов. Общая блок–схема предложенной процедуры вывода геометрических ограничений представлена на Рисунке 11.Этапы, обведенные пунктирным контуром, были разработаны в рамках данной диссертационной работы.Для проведения экспериментов был выбран открытый технологическийпроцесс FreePDK15 с проектной нормой 15 нм. Структурные компонентыбыли взяты из открытой библиотеки ячеек NanGate.
На базе описания технологического процесса была построенная трассировочная сетка, правила проектирования были сформулированы в виде логических выражений. Для проведения экспериментов были выбраны 10 стандартных ячеек библиотекиNanGate. Для вывода дополнительных правил на границах ячеек были выбраны правила проектирования, представленные на Рисунке 12.На первом этапе все ячейки были оттрассированы без каких-либо дополнительных ограничений, помимо правил проектирования.
Для всех парячеек были сгенерированы все разрешенные размещения встык, для каждогоиз которых была выполнена проверка нарушений правил проектирования. Врезультате проверки были выявлены 183 нарушения выбранных геометрических ограничений, возникших на границах ячеек.Рис. 11. Блок–схема предлагаемого маршрута проектирования библиотек стандартных ячеек для КМОП технологии с учетом вспомогательныхправил проектирования20Для предотвращения полученных нарушений площадь ячеек была увеличена на 1 шаг затвора с каждой стороны в горизонтальном направлении,после чего были повторно сгенерированы все попарные размещения и выполнена проверка правил. Этот подход позволил разрешить все 183 нарушения за счет увеличенной площади компонентов.На заключительном этапе были построены дополнительные правилапроектирования на границах стандартных ячеек, полученные для выбранныхвходных геометрических ограничений.
Для них было построено 88 вариантовправил на границах ячеек. Из них 76 были удалены из рассмотрения, т.к. ниодна из ячеек не была успешно страссирована в рамках заданных ограничений, полностью были проанализированы оставшиеся 12 вариантов правил. Вкачестве критерия качества стандартных ячеек была выбрана площадь. Только один из построенных наборов правил позволил сгенерировать все ячейки взаданной площади. Этот вариант правил и был признан оптимальным в рамках эксперимента.На Рисунке 13 приведен пример топологии, составленной из двух элементов ИЛИ–НЕ2, учитывающих дополнительные ограничения на границахячеек. Белым пунктиром обозначена граница двух элементов. При установкевстык элементы образуют топологию, не содержащую нарушений заданныхправил проектирования.а)б)г)в)д)Рис.
12. Минимальная длина проводника (а), минимальное расстояниемежду двумя проводниками (б), минимальное расстояние для двух проводников в двунаправленном слое (в), три переходных отверстия в ряд (г), двапереходных отверстия по диагонали (д)21Рис. 13. Разрешенное размещение ячеек, спроектированных с учетомограничений на границахПроведено сравнение результатов предложеного подхода с подходомна основе увеличения площади стандартных элементов.
В Таблице 3 приведены результаты сравнения. Получен выигрыш по площади топологий стандартных ячеек (от 16 до 50%). Выигрыш по площади в среднем составляет28.2%. Стоит отметить, что данное значение получено при использованииоптимистичного технологического процесса FreePDK15. При работе с промышленными процессами, описывающими на порядки больше технологических ограничений, выигрыш по площади может быть иным.В заключении приведены основные результаты, полученные в результате диссертационной работы.Таблица 3ЯчейкаAND2AOI21BUFINVMUX2NAND2NOR2OAI2OR2XOR2ОбщаяплощадьЭкспериментальные результатыМаршрут с увели- Предложенный марчением площадишрут с доп. Прави(шагов сетки)лами (шагов сетки)75756442121064647575977151Выигрыш поплощади (%)28.628.633.350.016.633.333.328.628.622.228.222Основные выводы и результаты1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
