Главная » Просмотр файлов » Диссертация

Диссертация (1090534), страница 7

Файл №1090534 Диссертация (Исследование и разработка методов автоматического вывода геометрических ограничений с использованием декларативного программирования и формальных методов) 7 страницаДиссертация (1090534) страница 72018-01-18СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 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, спроектированных безучета информации о топологиях других элементов библиотекис необходимостью учета технологических ограничений при размещенииэлементов библиотеки встык на этапе проектирования функциональныхблоков. При разработке библиотеки необходимо учитывать не только нормыиспользуемой технологии, определяемые процессом изготовления ИС, но идополнительные ограничения, предотвращающие потенциальные нарушениипри составлении рядов ячеек. При составлении рядов ячеек нарушаютсяограничения на минимальные расстояния между проводниками, расстояниямежду переходными отверстиями, образуются запрещенные конфигурациипереходных отверстий.

Характеристики

Список файлов диссертации

Исследование и разработка методов автоматического вывода геометрических ограничений с использованием декларативного программирования и формальных методов
Документы
Свежие статьи
Популярно сейчас
Почему делать на заказ в разы дороже, чем купить готовую учебную работу на СтудИзбе? Наши учебные работы продаются каждый год, тогда как большинство заказов выполняются с нуля. Найдите подходящий учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6384
Авторов
на СтудИзбе
308
Средний доход
с одного платного файла
Обучение Подробнее