Диссертация (1090534), страница 7
Текст из файла (страница 7)
Использование SMT позволяет избежвть этапапредставления электрических цепей в виде булевых выражений и обратногодекодирования полученного результата к описанию трассировки. Данныйметод также позволяет работать с трассировкой каналов различной ширины.Использование модели SMT позволяет решать задачу детальной трассировки29в процессе исследования различных архитектур FPGA с различающимисятрассировочными ресурсами. Поставновка задачи при этом не требует измененийв поставленных ограничениях. Возможность SMT находить минимум илимаксимум поставленной целевой функции используется для поиска оптимальнойширины канала трассировки. Экспериментальные результаты показывают, чтоSMT, как язык постановки задач, обладает большей выразительностью и являетсяболее гибким инструментом решения подобных задач, в сравнении с методамирешения задач выполнимости булевых функций.В работе [50] рассматривается метод автоматического синтезатопологий стандартных ячеек с использовантием алгоритмов решениязадачи SAT.
На первом этапе формулируется логическая формула,соответствующая задаче размещения комплиментарных пар транзисторов.При этом занимаемая ими площадь должна быть минимальной. Учитываетсявозможность использования общей диффузии и объединения затворов междусоответствующими транзисторами. Для полученного размещения формулируетсяSAT задача, соответствующая проблеме детальной трассировки.
Для обеихзадач используется псевдобулевая формулировка для построения задачиоптимизации. Экспериментальные результаты были сравнены с результамитрассировки с использованием коммерческого программного комплексаProGenesis и с имплементацией алгоритма на основе метода целочисленногопрограммирования. Задача размещения транзисторов была решена значительнобыстрее подходом на основе решения SAT в сравнении с методом целочисленногопрограммирования. 32 стандартных ячейки были отрассированы на 46% быстрее,чем при использовании коммерческого решения.
Площадь полученных ячеек приэтом увеличилась на 3%.Необходимость учета все большего числа правил проектированияпозволяет описывать элементы топологии стандартных ячеек в терминахдискретных объектов — кусочков металлов фиксированных размеров,переходных отверстий и др. В работе [51] это свойство используется вкачестве основы для разработки алгоритма автоматической трассировкистандартных ячеек. На первом этапе генерируется список соединений междупарами терминалов указанных цепей. Затем выполняется поиск электрическихи геометрический нарушений, возникающих между найденными вариантамисоединений.
Полученная информация используется затем для формирования30задачи SAT. Набор значений входных параметров, выполняющий полученнуюлогическую формулу, соответствует полной трассировке стандартной ячейки,соответствующей всем заданным технологическим требованиям. Данныйподход может быть использован при разработке библиотек стандартных ячеекс использованием современных технологических процессов. Также в работепредлагается ряд оптимизаций рассмотреного алгоритма. Рассматривается методоптимизации полученной топологии ИС через решение последовательности задачSAT при условии, что каждая следующая учитывает все больше дополнительныхограничений. Описанный подход был реализован и применяется для трассировкикоммерческой библиотеки стандартных ячеек. 89% элементов были успешнооттрассированы, включая такие сложные компоненты, как сканирующиетриггеры, сумматоры и мультиплексоры.По мере развития технологий и скоращения технологических норм припроектировании ИС возникает необходимость во введении дополнительныхограничений, накладываемых на топологию компонентов ИС.
В частности,возник целый класс правил, которые описывают разрешенные топологии,появление которых, тем не менее, нежелательно. В работе [52] описываетсяподход, позволяющий минимизировать число таких топологий приавтоматической трассировке стандартных ячеек. В основе предложенногоалгоритма лежит алгоритм решения задачи SAT и применение псевдобулевыхсчетчиков для описания нежелательных топологий.Сходный подход используется и для выполнения глобальной трассировкиблоков памяти, предложенный в работе [53].
Псевдобулевы счетчикииспользуются здесь для минимизации числа используемых вертикальныхтреков при выполнении трассировки нескольких стандартных ячеек в рамкахблока памяти.В работе [54] предлагается метод трассировки, который можетбыть применен к любому технологическому процессу, использующемуограничивающие правила проектирования. Программная система можетбыть настроена для использования любых фабрик и технологий, включаяметод двойного нанесения рисунка. В работе описывает алгоритм детальнойтрассировки, основанный на использовании булевой математики. Алгоритмиспользует новый подход к формулированию задачи трассировки, теориюграфов для работы с “плавающими” контактами, эффективные эвристики31для сокращения необходимых вычислительных ресурсов. В случае, еслистандартная ячейка не может быть оттрассирована, число несоединенныхконтактов минимизируется.
Гибкость предложенного подхода демонстрируетсяна примере трассировки как ячеек одинарной высоты, так и двойной. Врамках экспериментов, 127 стандартных ячеек были страссированы за1,5 часа. Полученные топологии были сравнены с результатами работыкоммерческого трассировщика. Таким образом, была продемонстрированаконкурентноспособность предложенного алгоритма и подхода с использованиемтрассировочных сеток в целом.В работе [55] предлагается метод трассировки программируемыхлогических интегральных схем типа FPGA (field-programmable gate array)с использованием алгоритма SAT.
Формулируется задача канальной трассировкив формате логического выражения в виде КНФ, при этом максимизируетсячисло дизъюнктов с двумя переменными. Если логическое выражение содержиттолько такие дизъюнкты, то оно может быть решено за полиномиальное время.Если же в SAT задаче есть дизъюнкты с большим числом переменных, задачастановится NP–полной. Считается, что большее число дизъюнктов размерности2 упрощает решение SAT–задачи. Экспериментальные результаты показывают,что увеличение доли таких дизъюнктов до 90% и более обеспечивает ускорениерешения задачи трассировки до 20 раз, по сравнению с известными техникамитрассировки на базе SAT.С точки зрения трассировки ИС, SAT предоставляет уникальнуювозможность полностью исследовать все возможные варианты трассировкии найти подходящее решение или “доказать” его отсутствие, в противовестрадиционным методам, которые могут не найти допустимого решения.
Несмотря на это преимущество, коммерчиские программные системы трассировкиFPGA редко используют SAT, в силу возможных проблем с масштабируемостью.В работе [56] рассматривается два подхода к трассировке FPGA на основеалгоритма SAT. На примере трассировке цепей синхронизации для устройствсерии Xilinx UltraScale. Экспериментальные результаты показывают, чтоодин из предложенных методов обладает лучшей производительностью иустойчивостью, в сравнее с традиционными метода. Описанная формулировкаSAT задачи содержит в 20 раз меньше переменных и ограничений, чем другие32варианты и позволяет найти решение в 18 раз быстрее. Алгоритм реализован ввиде модуля коммерческой программной системы трассировки Vivaldo.1.4 Потенциальные области применения декларативногопрограммирования в системах автоматического проектированияинтегральных схемОдним из способов снижения сложности процесса проектированиясверхбольших интегральных схем (СБИС) является методология проектированияна основе библиотек электронных компонентов (т.н.
библиотек стандартныхячеек). В основе этой методологии проектирования лежит использование вкачестве базовых элементов стандартных ячеек — компонентов ИС, деталифизической реализации которых скрыты за абстрактным интерфейсом.Стандартные ячейки используются при построении функциональныхблоков, где образуют ряды фиксированой высоты. На этапе проектированиястандартной ячейки невозможно предугадать, какие именно компоненты будутразмещены вокруг нее. При проектировании библиотек стандартных ячеекобеспечивается отсутствие нарушений технологических ограничений при любомдопустимом размещении.
Ошибки разработки топологий стандартных элементовмогут приводить к возникновений нарушений правил проектирования приформировании рядов ячеек. Пример такого нарушения показан на Рисунке 1.2:два элемента ИЛИ–НЕ2 установлены встык. Данный элемент спроектированс учетом ограничения на минимальное расстояние между углами переходныхотверстий. На границе между двумя элементами (белая пунктирная линия)образовалась запрещенная топология, выделенная красным.Этап разработки топологий элементов составляет значительную частьобщего бюджета проектирования библиотек. Актуальным способом физическогопроектирования элементов является метод синтеза — автоматическаягенерация физического представления ячейки (топологии) с учетом заданныхтехнологических ограничений.
Применение подобных программных системпозволило сократить цикл разработки. Однако, при работе с актуальными иперспективными технологическими процессами, разработчики сталкиваются33Рис. 1.2. Запрещенное размещение элементов ИЛИ–НЕ2, спроектированных безучета информации о топологиях других элементов библиотекис необходимостью учета технологических ограничений при размещенииэлементов библиотеки встык на этапе проектирования функциональныхблоков. При разработке библиотеки необходимо учитывать не только нормыиспользуемой технологии, определяемые процессом изготовления ИС, но идополнительные ограничения, предотвращающие потенциальные нарушениипри составлении рядов ячеек. При составлении рядов ячеек нарушаютсяограничения на минимальные расстояния между проводниками, расстояниямежду переходными отверстиями, образуются запрещенные конфигурациипереходных отверстий.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
