Автореферат (Исследование и разработка методов автоматического вывода геометрических ограничений с использованием декларативного программирования и формальных методов)

На правах рукописиБыков Сергей АнатольевичИССЛЕДОВАНИЕ И РАЗРАБОТКА МЕТОДОВ АВТОМАТИЧЕСКОГОВЫВОДА ГЕОМЕТРИЧЕСКИХ ОГРАНИЧЕНИЙ С ИСПОЛЬЗОВАНИЕМ ДЕКЛАРАТИВНОГО ПРОГРАММИРОВАНИЯ И ФОРМАЛЬНЫХ МЕТОДОВСпециальность 05.13.11 ––«Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей»Авторефератдиссертации на соискание учёной степеникандидата технических наукМосква – 20172Работа выполнена в Московской лаборатории перспективных проблем САПРАО «Интел А/О»Научный руководитель:Рыженко Николай Владимирович, кандидаттехнических наук, ведущий научный сотрудникМосковской лаборатории перспективных проблем САПР АО «Интел А/О»Официальные оппоненты:Бычков Игнат Николаевич, доктор технических наук, заместитель Генерального директораПАО «ИНЭУМ им.

И.С. Брука»Путря Фёдор Михайлович, кандидат технических наук, начальник лаборатории «Верификации СнК и IP-блоков» ОАО НПЦ «ЭЛВИС»Ведущая организация:Федеральное государственное учреждение«Федеральный научный центр Научноисследовательский институт системных исследований Российской академии наук»Защита состоится «07» декабря 2017 г. в 13-00 часов на заседаниидиссертационногосоветаД 212.131.05набазефедеральногогосударственного бюджетного образовательного учреждения высшегообразования «Московский технологический университет» по адресу: 119454,г. Москва, пр.

Вернадского, д. 78, ауд. Д217С диссертацией можно ознакомиться в библиотеке Московскоготехнологического университета и на сайте https://mirea.ru/.Автореферат разослан «05» ноября. 2017 г.Ученый секретарьдиссертационного советак.т.н, доцентАндрианова Елена Гельевна3Общая характеристика работыАктуальность работы. Научно-технический прогресс второй половины ХХ века привел к разрыву между практическими возможностями разработанных технологий изготовления и существующими методами и методологиями решения традиционных задач проектирования. Опережающими темпами растет сложность проблем, которые требуется решать промышленности.

Методы и средства снижения этой сложности являются предметом активных исследований.Сегодня природа традиционных задач оптимизации в процессе разработки кардинально изменилась с увеличением числа параметров, значениякоторых необходимо соблюдать. Такие проекты зачастую представляют собой сложнейшие проблемы большой размерности. Сами параметры нередкосвязаны между собой множеством противоречивых требований, которые необходимо выполнить.

Высокая размерность таких задач приводит к тому, чтопрактический интерес представляет поиск не оптимального решения, а любого, которое соответствует всем заданным требованиям, и в кратчайшие сроки.Одним из перспективных подходов к решению подобных задач является применение формальных методов и декларативного программирования. Врамках данного подхода разработка заключается в описании задачи в терминах предметной области и в формулировании желаемых свойств решения, ане в написании алгоритма решения. Полученная спецификация проблемы затем используется в качестве входных данных некоего универсального алгоритма. Такой подход позволяет использовать одно и то же математическое ипрограммное обеспечение для решения широкого круга задач — детали описания конкретной проблемы становятся частью входных данных. Результатом работы данного подхода является решение, гарантированно удовлетворяющее всем заданным ограничениям; иначе может быть сгенерировано доказательство, почему такое решение невозможно построить.

Прогресс в развитии формальных методов позволяет решать актуальные задачи индустрии,содержащие десятки тысяч параметров и сотни тысяч ограничений.Проблема роста сложности задач разработки наблюдается и в областипроектирования микро- и наноэлектроники. Переход к актуальным и перспективным технологическим процессам сопровождается увеличением стоимости изготовления интегральных схем (ИС), что вынуждает использоватьразличные агрессивные оптимизации для контроля стоимости конечногопродукта. Вместе с тем, жесткая конкурентная среда рынка требует сокращения цикла проектирования и ускорения выпуска новых продуктов.Одним из способов снижения сложности процесса проектированиясверхбольших интегральных схем (СБИС) является методология проектирования на основе библиотек электронных компонентов (т.н.

библиотек стандартных ячеек). В основе этой методологии проектирования лежит использование в качестве базовых элементов стандартных ячеек — компонентов ИС,4детали физической реализации которых скрыты за абстрактным интерфейсом. Стандартные ячейки используются при построении функциональныхблоков. Разработка библиотек стандартных ячеек является трудоемким процессом и требует существенных временных затрат.

Необходимость в применении агрессивных оптимизаций при проектировании ИС вынуждает использовать библиотеки ячеек, содержащие большое число элементов. Также растет и количество самих библиотек — для разных проектов могут потребоваться специфичные наборы компонентов.Традиционно СБИС разрабатываются по методологии «сверху-вниз»,начиная с высокоуровневого поведенческого описания в терминах функций иалгоритмов и заканчивая детальным физическим описанием СБИС.

Недостатком такого подхода является резкое увеличение стоимости ошибок приувеличении сложности проекта. Более того, понять, насколько параметрыСБИС соответствуют заданным требованиям, можно только в самом концецикла разработки. Ошибки, обнаруженные в конце любого из промежуточных этапов приводят к повторному выполнению всего этапа.Также стоит отметить, что большинство современных компанийразработчиков СБИС не обладают своими собственными производственнымилиниями – изготовление выполняется на специализированных фабриках, которые предоставляют описание используемых технологических процессов иограничений.

Данные ограничения должны быть соблюдены при разработкеСБИС. Такое разделение создает барьер между разработчиками, предоставляющими высокоуровневое описание СБИС, и разработчиками физическогопредставления. Устранение этого барьера может сократить цикл разработки вцелом.Этап разработки топологий элементов составляет значительную частьобщего бюджета проектирования библиотек. Актуальным способом физического проектирования элементов является метод синтеза — автоматическаягенерация физического представления ячейки (топологии) с учетом заданныхтехнологических ограничений.

Применение подобных программных системпозволило сократить цикл разработки. Однако, при работе с актуальными иперспективными технологическими процессами, разработчики сталкиваютсяс необходимостью учета технологических ограничений при размещении элементов библиотеки встык на этапе проектирования функциональных блоков.При разработке библиотеки необходимо учитывать не только нормы используемой технологии, определяемые процессом изготовления ИС, но и дополнительные ограничения, предотвращающие потенциальные нарушении присоставлении рядов компонентов.

При составлении рядов компонентов нарушаются ограничения на минимальные расстояния между проводниками, расстояния между переходными отверстиями, образуются запрещенные конфигурации переходных отверстий.Важно отметить, что по мере ужесточения технологических норм, область взаимного влияния компонентов топологии увеличивается. Корректировать возникающие на границах компонентов коллизии внесением локаль-5ных изменений на уровне функционального блока становится все сложнее.До настоящего времени вспомогательные правила на границах стандартныхячеек создаются вручную.

Процесс их разработки является итеративным.Таким образом, разработка вычислительного комплекса автоматического вывода геометрических ограничений на границах структурных компонентов, предотвращающих нарушения при размещении структурных компонентов встык сократит цикл проектирования библиотек. Использование подобного вычислительного комплекса позволяет обеспечить дополнительнуюсвязь между уровнями логического и физического проектирования СБИС. Посвоей природе задача формирования набора дополнительных правил является задачей оптимизации большой размерности. Вычислительный комплексавтоматического вывода правил с использованием формальных методов идекларативного программирования является эффективной технологией длярешения поставленной задачи.Объектом диссертационного исследования являются вычислительные комплексы, используемые при разработке структурных компонентов ограниченной площади.Предметом диссертационного исследования являются методы, алгоритмы и программные средства разработки структурных компонентов ограниченной площади, основанные на использовании декларативного программирования и формальных методов.Область исследования определена предметной областью паспортаспециальности 05.13.11: 3) “Модели, методы, алгоритмы, языки и программные инструменты для организации взаимодействия программ и программныхсистем”.Цель работыЦелью данной работы является разработка вычислительного комплекса, выполняющего процедуру автоматического построения геометрическихограничений на базе декларативного программирования и позволяющего отделить алгоритм решения задачи от деталей исследуемых технологий.

Примером подобных структурных компонентов могут являться стандартныеячейки, используемые при разработке полупроводниковых устройств.Для достижения поставленной цели необходимо было решить следующие задачи:1. Исследование методов решения задач многопараметрической оптимизации.2. Исследование методов постановки и решения задач в декларативном стиле.3.

Разработка алгоритма построения вспомогательных геометрических ограничений на границах структурных компонентов ограниченнойплощади.4. Разработка алгоритма анализа вспомогательных геометрическихограничений и их влияния на параметры структурных компонентов ограниченной площади.65. Разработка вычислительного комплекса для автоматического вывода субоптимального набора геометрических ограничений на границахструктурных компонентов ограниченной площади.Методика проведения исследования разработанных моделей, методов и алгоритмов включает в себя использование теории выполнимости булевых функций, дискретной математики, теории графов, методов минимизации логических функций.Основные положения, выносимые на защиту:1.