Исследование и разработка методов автоматического вывода геометрических ограничений с использованием декларативного программирования и формальных методов тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат наук Быков Сергей Анатольевич

• Быков Сергей Анатольевич
• кандидат наук
• 2017

Оглавление диссертации кандидат наук Быков Сергей Анатольевич

Введение

Актуальность работы

Цель исследования

Методы исследования

Положения, выносимые на защиту

Научная новизна

Практическая значимость

Степень достоверности

Личный вклад

Апробация работы

Публикации

Глава 1. Анализ методов разработки геометрии структурных

компонентов

1.1 Тенденции развития математических и программных средств

1.2 Разработка программного обеспечения с использованием декларативного программирования и формальных методов

1.3 Декларативное программирование в актуальных системах автоматического проектирования топологий интегральных схем

1.4 Потенциальные области применения декларативного программирования в системах автоматического проектирования интегральных схем

1.5 Постановка цели и задач исследования

Глава 2. Математическое обеспечение вычислительного комплекса

автоматического вывода геометрических ограничений

2.1 Элементы логики высказываний и теории выполнимости булевых функций

2.1.1 DPLL алгоритм

2.1.2 CDCL алгоритм

2.1.3 Метод поиска стабильных моделей

2.1.4 Метод перечисления решений задачи SAT

2.2 Элементы теории графов, используемые в работе

2.3 Задача минимизации логических функций

2.4 Выводы

Глава 3. Разработка вычислительного комплекса вывода

геометрических ограничений

3.1 Алгоритм вывода геометрических ограничений

3.2 Модель данных

3.3 Алгоритм получения разрешенных топологий

3.3.1 Построение задачи SAT

3.3.2 Процедура перечисления всех разрешенных топологий

3.4 Поиск классов топологий

3.5 Построение компактного описания правил на границах

3.6 Анализ и сравнение различных вариантов ограничений на границах

3.7 Выводы

Глава 4. Применение метода автоматического вывода

дополнительных геометрических ограничений

4.1 Оборудование и ПО

4.1.1 Технологический процесс FreePDK15

4.1.2 Библиотека стандартных ячеек NanGate OCL15

4.2 Вывод правил

4.3 Валидация результатов

4.4 Выводы

Заключение

Литература

Приложение А. Актуальные проблемы разработки нанометровых

топологий компонентов интегральных схем

Список сокращений и условных обозначений

АНФ — алгебраическая нормальная форма

БИС — большая интегральная схема

ВЫП — теория выполнимости булевых формул в теориях

ДНФ — дизъюнктивная нормальная форма

ИС — интегральная схема

КНФ — конъюнктивная нормальная форма

СБИС — сверхбольшая интегральная схема

ASP — программирования стабильных моделей, Answer Set Programming BDD — бинарная диаграмма решений, Binary Decision Diagram ITRS — Международный план по развитию полупроводниковой технологии

OBDD — упорядоченная бинарная диаграмма решений, Ordered Binary Decision Diagram

POS — дизъюнктивная нормальная форма, Product-of-Sums SAT — теория выполнимости булевых формул SOP — конъюнктивная нормальная форма, Sum-of-Products SMT — теория выполнимости булевых формул в теориях QBF — квалифицированная булева формула

Введение

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

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

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

Проблема роста сложности задач разработки наблюдается и в области проектирования микро- и наноэлектроники. Переход к актуальным и перспективным технологическим процессам сопровождается увеличением

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

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

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

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

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

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

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

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

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

Область исследования определена предметной областью паспорта специальности 05.13.11: 3) "Модели, методы, алгоритмы, языки и программные инструменты для организации взаимодействия программ и программных систем".

Цель исследования

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

Для достижения поставленной цели необходимо было решить следующие задачи:

1. Исследование методов решения задач многопараметрической оптимизации.

2. Исследование методов постановки и решения задач в декларативном стиле.

3. Разработка алгоритма построения вспомогательных геометрических ограничений на границах структурных компонентов ограниченной площади.

4. Разработка алгоритма анализа вспомогательных геометрических ограничений и их влияния на параметры структурных компонентов ограниченной площади.

5. Разработка вычислительного комплекса для автоматического вывода субоптимального набора геометрических ограничений на границах структурных компонентов ограниченной площади.

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

Положения, выносимые на защиту

1. Доказана эффективность применения формальных методов и декларативного программирования для решения задач многопараметрической оптимизации большой размерности.

2. Алгоритм перечисления множеств геометрических ограничений, предотвращающих нарушения указанных геометричеких ограничений, возникающих при установке структурных компонентов ограниченной площади встык друг к другу.

3. Алгоритм оценки качества полученных вспомогательных правил проектирования на границах структурных компонентов ограниченной площади и алгоритм поиска множества правил, соответствующего заданным критериям качества.

4. Вычислительный комплекс "Вычислитель геометрических ограничений".

Научная новизна

1. Разработан алгоритм построения всех разрешенных геометрий в ограниченной площади путем представления геометрических ограничений в виде булевых выражений и последующего решения задачи А1^АТ.

2. Разработан алгоритм поиска классов геометрий, не приводящих к нарушениям заданных ограничений при любом разрешенном размещении, заключающийся в построении графа с описанием совместных и несовместных топологий геометрий и перечислении всех максимальных полных подграфов.

3. Разработан алгоритм выбора субоптимальных геометрических ограничений на границах структурных компонентов, построении ограниченного множества элементов, анализе параметров их качества

и сравнительном анализе качества компонентов с учетом разных вариантов ограничений на границах, позволивший сократить площадь тестового набора структурных компонентов на 28.2%.

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

Степень достоверности научных положений и выводов, полученных соискателем, подтверждается теоретическими выкладками и успешным промышленным внедрением.

Личный вклад

Все основные результаты получены автором лично. Постановка задачи выполнена совместно с научным руководителем. Автор принимал активное участие в разработке архитектуры, реализации, документации и тестировании программного обеспечения, внедрённого в АО "Интел А/О".

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

Апробация работы

Основные результаты работы докладывались и обсуждались на: конференции "Гагаринские чтения" (г. Москва, 2015); конференции "Проблемы разработки перспективных микро- и наноэлектронных систем" (г. Москва, 2014; г. Москва, 2016); 14th IEEE East-West Design & Test Symposium (Yerevan, Armenia, 2016).

Публикации

Основные результаты по теме диссертации изложены в 8 печатных изданиях, 6 из которых изданы в журналах, рекомендованных ВАК, 2 — в тезисах докладов.

Объем и структура работы

Диссертация состоит из введения, четырёх глав, заключения и одного приложения. Полный объём диссертации составляет 159 страниц с 27 рисунками и 5 таблицами. Список литературы содержит 199 наименований.

Глава 1. Анализ методов разработки геометрии структурных компонентов

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

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

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

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

очередь, увеличиватся стоимость различных ошибок. Одним из способов снижения рисков возникновения ошибок является использование различных вычислительных комплексов на всех этапах разработки. Основные этапы разработки микроэлетроники показаны на Рисунке 1.1.

Разработка RTL кода Логический синтез Физический синтез

изготовлению

Рис. 1.1. Основные этапы разработки интегральных схем

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

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

1.1 Тенденции развития математических и программных средств

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

В частности, в работе [1] рассматривается задача оптимального управления водными ресурсами на примере гидроэнергетического комплекса Оровиль-Термалито в Калифорнии, являющегося ключевым элементом водоснабжения штата. Особенностью данной задачи является необходимость оптимизации нескольких целевых функций одновременно [2]. Для моделирования нелинейных отношений между уровнями воды в резервуарах и выходной мощностью силовых установок была разработана математическая модель в виде полиномиальной функции. С целью уменьшения ошибок аппроксимации и более точного моделирования реальных процессов были рассмотрены различные методы приближения с помощью кривых. Также в рамках проведенного исследования был проведен сравнительный анализ различных методов многопараметрической оптимизации. Были рассмотрены такие многоцелевые подходы, как метод имитации отжига [3], метод на основе генетических алгоритмов [4], метод роя частиц [5]. Разработанный в данной работе подход глобальной оптимизации на основе эволюционных алгоритмов и с использованием метода главных компонент [6] продемонстрировал высокую точность и устойчивость.

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

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

Одним из способов упрощения сложности решения различных задач с позиции инфраструктуры является использование облачных вычислений — концепция, подразумевающая повсеместный сетевой доступ к общему множеству настраеваемых вычислительных ресурсов [8]. Однако разработка соответствующих систем управления ресурсами в условиях растущего спроса и распространения систем облачных вычислений [9] сама по себе является трудоемкой задачей. Одним из подходов к решению задачи назначения облачных ресурсов является использования локальной активности [10]. Принцип локальной активности был разработан в процессе исследований в области микроэлектроники, но может быть применен к решению задач моделировая люой однородной или неоднородной среды. В случае облачных технологий примером локально активного элемента является вычислительная машина, входящая в облако. Стоит отметить, что во многих работах при разработке планировщиков задач эти элементы рассматриваются как пассивные, что оказывает негативное влияние на результаты исследований. В работе [11] рассматриваются различные аспекты разработки облачных систем с использованием принципа локальной активности, обуславливающие сложность подобных проектов. Также предлагается планировщик задач, который может находиться в состоянии "порядка" или "хаоса" и приводятся параметры, описывающие каждое состояние. Для получения этих данных выполняется имитационное моделирование. В данной работе также рассматривается метод управления "хаосом" при распределении ресурсов в облачных системах, основанный на введении уровня локальной активности для вычислительных элементов, который используется для обеспечения требуемого качества обслуживания (англ. Quality of Service, QoS). Данный подход был реализован в качестве модуля для системы Apache

Spark [12]. Экспериментальные результаты показывают, что предложенный планировщик задач позволяет сократить расходы на сервера на 23%, увеличивает среднее время отклика на 15% - 20% и сокращается стандартное отклонение времени отклика на 20% - 30%, по сравнению со стандартным планировщиком Spark.

Начиная с 80-ых годов наблюдается "взрывной" рост объемов данных, которые необходимо хранить и обрабатывать [13-15]. Для обеспечения возможности обрабатывать такие данные и решать различные задачи аналитики и прогнозирования используется ряд подходов под общим названием "big data". Актуальные задачи big data могут включать сотни и тысячи параметров, что приводит к экспоненциальному росту пространства признаков. Практическое значение имеет решение задачи определения такого подмножества параметров, используемых в дальнейшем при построении моделей, которое бы обеспечивало требуемую точность прогнозов. В работе [16] предлагается метод выбора подмножества признаков, котоорый может быть использован для анализа потоков данных в реальном времени. Метод основан на алгоритме роя частиц , позволяющего получить требуемый уровень точности при заданных ограничениях на доступные вычислительные ресурсы.

Одним из источников больших объемов данных является распространение Интернета Вещей(англ. Internet-of-Things, IoT) — концепции вычислительной сети машин, обеспеченных встроенными технологиями взаимодействия друг с другом или с внешней средой [17-19]. Обеспечение инфраструктуры и вычислительных ресурсов для географически разразненной и гетерогенной среды , обеспечивающей функционирование IoT, является актуальной и трудоемкой задачей.

В работе [20] рассматривается метод распределния ресурсов облачной вычслительной системы для обеспечения работоспособности IoT системы. Показывается, что данная задача принадлежит классу NP-сложных и может быть решена методами комбинаторной оптимизации. Предметом исследования являются методы распределния ресурсов таким образом, что выполняются заданные ограничения на качество сервиса при обеспечении максимальной прибыли поставщика IoT услуг. Для увеличения прибыли необходимо сократить число нарушений заданного соглашения об уровне предоставления услуги (англ. Service Level Agreement, SLA). В работе рассматривается постановка задачи

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

Одним из вариантов построения IoT является разработка систем устойчивого (англ. resilent) IoT. Особенность таких систем является обеспечение прибыли поставщика услуг с учетом неопределенности в том, в каком контексте будут использованы элементы IoT сети. В работе [22] задача построения автономной устойчивой IoT сети сводится к решению двух задач — поиску таких m изменений в процессе предоставления услуг, которые удовлетворяют интересам клиентов, которые представляются как k — 1 возможных изменений в требованиях клиентов. В качестве решения предлагается жадный алгоритм, который последовательно применяет пять моделей для решение двух поставленных задач. В работе показано, что данная задача принадлежит классу NP-сложных и может быть решена методами комбинаторной оптимизации. В работе также демонстрируется, как исследуемая задача может быть представлена в виде проблемы вычисления оценок кредитного дефолтного свопа (англ. credit default swap, CDS). Для оценки предложенного метода решения был проведен анализ базы данных слухов, распространяемых в различных СМИ. Результаты показывают, чтл предложенная схема улучшает оценки CDS. В результате работы был разработан прототип системы, в которой поставщик услуг рекомендует различные персонализированые услуги пользователя веб-сервисов и мобильный устройств с ОС Android.

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

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

1.2 Разработка программного обеспечения с использованием декларативного программирования и формальных методов

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

Рост комплексности и сложности современных программных систем вынуждает разработчиков пользоваться различными средствами проектирования, такими как UML/OCL. Верификация и валидация таких моделей ПО и оборудования является актуальной проблемой современных средств разработки. Поведение таких моделей описывается операциями с ограничениями на начальное и конечное состояние системы. Одако, этой информации зачастую недостаточно для полного описания процесса перехода из начального состояния в конечное. Как правило, эта проблема решается описанием дополнительных ограничений. Предложены и различные методы верификации подобного описания UML/OCL моделей, основанных на символьных вычислениях. Каждому возможному состоянию системы ставится в соответствие переменненая, взаимоотношения между ними и возможные переходы задаются в виде ограничений. В работе [23] рассматривается процедру верификации UML/OCL

моделей с использованием алгоритма SAT, учитыващей дополнительные ограничения на переходы от одного состояния к другому.

Современное ПО все больше опирается на использование параллелизма и конкуррентности. Однако, данные технологии значительно усложняют программные системы и вносят новые классы ошибок, например, возможность возникновения состояния "гонки", в которм несколько потоков блокируют доступ к одному и тому же ресурсу и ждут завершения друг друга. В работе [24] рассматривается метод на основе SAT алгоритма для анализа специального класса сетей Петри — сетей Гадара. Этот формализм используется для моделирования поведения многопоточных систем. SAT используется для генерации оптимальной стратегии управления многопоточным выполнением с учетом теории дискретных систем управления. Экспериментальные результаты демонстрируют высокую степень масштабируемости предложенного подхода, в сравнении с классическими методами. Эксперименты показывают, что подход с использованием алгоритма SAT позволяет генерировать системы управления для моделей с более 100 небезопасных состоянии.

Прогресс в развитии методов решения задачи SAT позволяет работать над реальными проблемами промышленности, которые могут содержать тысячи и десятки тысяч переменных. В работе [25] рассматриваются проблемы планирования и назначения. Для решения этих задач приводятся методы сведения к проблеме SAT, которые затем решаются при помощи современных алгоритмов. Эеспериментальные результаты показывают, что данный подход отличается высокой степенью масштабируемости.

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

то подмножество предположения, которое не может быть выполнено в рамках заданных ограничений. Алгоритм обучения с конфликтами естественным образом поддерживает добавление утверждений. Однако, удаление утверждений сопровождается дополнительной работой — выученные утверждения, основанные на исключенных фактах, также должны быть сброшены. В работах [26; 27] при добавлении нового утверждения создается дополнительный контекст, в рамках которого продолжается решение исходной задачи. При удалении утверждения, этот контекст сбрасывается. В работе [28] используются дополнительные литералы, которые позволяют включать или выключать заданные утверждения.

Подход с использованием предположений, впрочем, обладает двумя недостатками, которые снижают производительность всего алгоритма. Во-первых, использование предположений не позволяет выполнять предварительное упрощение заданной формулы при помощи специального препроцессора SatElite, представленного в работе [29]. Данный препроцессор активно используется при решении практических задач. Во-вторых, предположения всегда остаются в формуле, а не удаляются в ходе решение процедурой распространения констант. В литературе обсуждаются методы решения как первой проблемы [30], так и второй [31], но не обеих вместе. В работе [32] рассматривается подход, адресующий обе проблемы одновременно, в котором сначала в задачу добавляются предположения, после чего применяется алгоритм SatElite. Предложенный алгоритм демонстрирует более высокую производитесльность по сравнению с существующими подходами. В качестве экспериментальных данных использовались общедоступные тестовые примеры, полученные в ходе решения промышленных задач верификации полупроводниковых устройств.

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

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

Расширением алгоритмов SAT являются методы решения задач выполнимости формул в теориях (англ. satisfiability modulo theories, SMT). Данный подход позволяет решать задачи выполнимости в терминах целых и вещественных чисел, теории списков и битовых векторов и др. SMT теория может включать в себя произвольные переменные, а не только булевы. Предикатами же в этой теории может быть любое булевое выражение от этих переменных. SMT теория предоставляет больше возможностей для моделирования, чем формулы SAT. Например, SMT-формула позволяет моделировать операции функции модулей микропроцессора на уровне слов, а не на уровне битов.

При разработке современного ПО большое внимание уделяется тестированию и обеспечению корректности и надежности. В работе [33] описывается программный комплекс KLEE, предоставляющий инструменты символьного выполнения программы и автоматической генерации тестов. Программная система KLEE была использована для анализа 89 программ из пакета GNU Coreutils, которые установлены на миллионах компьютеров по всему миру и тщательно протестированы. Покртыие тестами составило более 90% строчек кода, что существенно превышает покрытие тестами. написанными вручную. Также были проанализированы 75 программ пакета Busybox, для 31 из которых было достигнуто 100% покрытие кода. В общей сложности, при помощи KLEE были проанализированы 452 программы (более 430 тысяч строчек кода), в которых было обнаружено 56 критических ошибок. 3 из них не были найдены на протяжении последних 15 лет. KLEE использует SAT и SMT алгоритмы для анализа исходных кодов ПО и генерации тестов.

KLEE также используется в качестве инструмента для поиска ошибок и генерации тестов на базе документации (англ. Document-Assisted Symbolic Execution, DASE). Проект DASE. представленный в работе [34], использует методы анализа естественного языка и эвристики для обработки документации к программной системе. В результате DASE автоматически выводит ограничения на входные параметры ПО. Эта информация затем используетс для управления процессом символьного выполнения, обращая больше внимания на семантически важные участки кода. При помощи DASE были проанализированы такие пакеты

программ, как foreutils, findutils, grep, binutils, elftoolchain. Было обнаружено 12 критических, прежде неизвестных и не обнаруженных другими системами символьного выполнения, 6 из них подтверждены разработчиками. Степени покрытия кода, условия и вызовов были улучшены на 14.2-120.3%, 2.3-167.7% и 16.9-135.2%, соответственно. 97.8-100% полученных ограничений корректны.

В работе [35] рассматривается метод решения проблемы поиска пути в систмах с несколькими агентами. Предметом исследования являются методы поиска оптимальных решений, предотвращающих столкновения между агентами, в случае ненаправленных графов. Начальные и конечные позиции агентов могут различаться. Существуют варианты формулировки этой задачи в виде SAT проблемы, минимизирующие число шагов, необходимых для достижения цели. В данной работе рассматривается метод минимизации числа шагов для каждого агента, тем самым, выполняется поиск решения с наименьшей стоимостью. Экспериментальные результаты показывают, что данный подход обладает производительностью, сравнимой с лучшими известными реализациями.

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

Например, в работе [36] описаны различные прикладные задачи, возникающие при анализе данных, которые были успешно решены методом MaxSAT. Примерами таких задач являются минимизации весовой функции при корреляционной кластеризации, построение вероятностной графической модели минимального размера и анализ причинно-следственных связей. В результате, были предложены различные варианты трансляции этих прикладных задач к MaxSAT виду, поддержку вещественных коэффициентов при решении MaxSAT.

Список литературы диссертационного исследования кандидат наук Быков Сергей Анатольевич, 2017 год

Литература

1. Improving the multi-objective evolutionary optimization algorithm for hydropower reservoir operations in the California Oroville-Thermalito complex / Tiantian Yang, Xiaogang Gao, Scott Lee Sellars, Soroosh Sorooshian // Environmental Modelling & Software. — 2015. — Vol. 69. — Pp. 262-279.

2. Miettinen Kaisa. Nonlinear multiobjective optimization. — Springer Science & Business Media, 2012. — Vol. 12.

3. Brooks Stephen P, Morgan Byron JT. Optimization using simulated annealing // The Statistician. — 1995. — Pp. 241-257.

4. Akbari Reza, Ziarati Koorush. A multilevel evolutionary algorithm for optimizing numerical functions // International Journal of Industrial Engineering Computations. — 2011. — Vol. 2, no. 2. — Pp. 419-430.

5. Bonyadi Mohammad Reza, Michalewicz Zbigniew. Particle swarm optimization for single objective continuous space problems: a review // Evolutionary computation. — 2016.

6. Bengio Yoshua, Courville Aaron, Vincent Pascal. Representation learning: A review and new perspectives // IEEE transactions on pattern analysis and machine intelligence. — 2013. — Vol. 35, no. 8. — Pp. 1798-1828.

7. A review of simheuristics: Extending metaheuristics to deal with stochastic combinatorial optimization problems / Angel A Juan, Javier Faulin, Scott E Grasman et al. // Operations Research Perspectives. — 2015. — Vol. 2. — Pp. 62-72.

8. Neto Paulo. Demystifying cloud computing // Proceeding of Doctoral Symposium on Informatics Engineering. — 2011.

9. Columbus Louis. Roundup Of Cloud Computing Forecasts And Market Estimates, 2014 // Forbes Magazine. — 2015.

10. Mainzer Klaus. The cause of complexity in nature: An analytical and computational approach // How Nature Works. — Springer, 2014. — Pp. 19-49.

11. Complexity Reduction: Local Activity Ranking By Resource Entropy For QoS-aware Cloud Scheduling / Huankai Chen, Frank Wang, Matteo Migliavacca et al. // Services Computing (SCC), 2016 IEEE International Conference on / IEEE. — 2016. — Pp. 585-592.

12. Zaharia Matei. Spark: In-Memory Cluster Computing for Iterative and Interactive Applications // Invited Talk. NIPS Big Learning Workshop: Algorithms, Systems, and Tools for Learning at Scale (Granada, Spain. December 12-17, 2011). — 2011.

13. Hellerstein Joe. Parallel programming in the age of big data // Gigaom Blog. — 2008.

14. Segaran Toby, Hammerbacher Jeff. Beautiful data: the stories behind elegant data solutions. — "O'Reilly Media, Inc. 2009.

15. Data IBM Big. IBM-Bringing Big Data to the Enterprise. — 2015.

16. Fong S., Wong R., VasilakosA. V. Accelerated PSO Swarm Search Feature Selection for Data Stream Mining Big Data // IEEE Transactions on Services Computing. — 2016. — Jan. — Vol. 9, no. 1. — Pp. 33-45.

17. Internet of Things (IoT): A vision, architectural elements, and future directions / Jayavardhana Gubbi, Rajkumar Buyya, Slaven Marusic, Marimuthu Palaniswami // Future Generation Computer Systems. — 2013. — Vol. 29, no. 7. — Pp. 1645-1660.

18. On the integration of cloud computing and internet of things / Alessio Botta, Walter De Donato, Valerio Persico, Antonio Pescape // Future Internet of Things and Cloud (FiCloud), 2014 International Conference on / IEEE. — 2014. — Pp. 2330.

19. of Things Global Standards Initiative Internet et al. ITU. — 2015.

20. Choi Yeongho, Lim Yujin. Optimization Approach for Resource Allocation on Cloud Computing for IoT // International Journal of Distributed Sensor Networks. — 2016. — Vol. 2016.

21. Cramton Peter, Shoham Yoav, Steinberg Richard. Combinatorial auctions. — 2006.

22. Kamal Rossi, Hong Choong Seon, Choi Mi-Jung. Autonomic Resilient Internet-of-Things(IoT)Management//CoRR. — 2015. — Vol. abs/1508.03975. — URL: http://arxiv.org/abs/1508.03975.

23. Frame Conditions in Symbolic Representations of UML/OCL Models / Nils Przigoda, Jonas Gomes Filho, Philipp Niemann et al. // Int'l Conf. Formal Methods and Models for System Design. — 2016.

24. Stanley Jason, Liao Hongwei, Lafortune Stéphane. SAT-Based Control of Concurrent Software for Deadlock Avoidance // IEEE Transactions on Automatic Control. — 2015. — Vol. 60, no. 12. — Pp. 3269-3274.

25. Lin Hai. A Scalable Method for a Particular Scheduling Problem Based on Boolean Satisfiability. — 2015.

26. Chaff: Engineering an efficient SAT solver / Matthew W Moskewicz, Conor F Madigan, Ying Zhao et al. // Proceedings of the 38th annual Design Automation Conference / ACM. — 2001. — Pp. 530-535.

27. Whittemore Jesse, Kim Joonyoung, Sakallah Karem. SATIRE: A new incremental satisfiability engine // Design Automation Conference, 2001. Proceedings / IEEE. — 2001. — Pp. 542-545.

28. Biere Armin. PicoSAT essentials // Journal on Satisfiability, Boolean Modeling and Computation. — 2008. — Vol. 4. — Pp. 75-97.

29. Eén Niklas, Biere Armin. Effective preprocessing in SAT through variable and clause elimination // International conference on theory and applications of satisfiability testing / Springer. — 2005. — Pp. 61-75.

30. Nadel Alexander, Ryvchin Vadim, Strichman Ofer. Preprocessing in incremental SAT // International Conference on Theory and Applications of Satisfiability Testing / Springer. — 2012. — Pp. 256-269.

31. Nadel Alexander, Ryvchin Vadim. Efficient SAT solving under assumptions // International Conference on Theory and Applications of Satisfiability Testing / Springer. — 2012. — Pp. 242-255.

32. Nadel Alexander, Ryvchin Vadim, Strichman Ofer. Ultimately incremental SAT // International Conference on Theory and Applications of Satisfiability Testing / Springer. — 2014. — Pp. 206-218.

33. KLEE: Unassisted and Automatic Generation of High-Coverage Tests for Complex Systems Programs. / Cristian Cadar, Daniel Dunbar, Dawson R Engler et al. // OSDI. — Vol. 8. — 2008. — Pp. 209-224.

34. Dase: Document-assisted symbolic execution for improving automated software testing / Edmund Wong, Lei Zhang, Song Wang et al. // 2015 IEEE/ACM 37th IEEE International Conference on Software Engineering / IEEE. — Vol. 1. —

2015. — Pp. 620-631.

35. Boolean Satisfiability Approach to Optimal Multi-agent Path Finding Under the Sum of Costs Objective: (Extended Abstract) / Pavel Surynek, Ariel Felner, Roni Stern, Eli Boyarski // Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems. — AAMAS '16. — Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems,

2016.— Pp. 1435-1436.— URL: http://dl.acm.org/citation.cfm?id=2937029. 2937197.

36. Berg Jeremias, Hyttinen Antti, Järvisalo Matti. Applications of MaxSAT in Data Analysis // Easychair Proceedings in Computing. EasyChair. — 2015.

37. MaxSAT-Based Scheduling of B2B Meetings / Miquel Bofill, Marc Garcia, Josep Suy, Mateu Villaret // Integration of AI and OR Techniques in Constraint Programming: 12th International Conference, CPAIOR 2015, Barcelona, Spain, May 18-22, 2015, Proceedings / Ed. by Laurent Michel. — Cham: Springer International Publishing, 2015. — Pp. 65-73. — URL: http://dx.doi.org/10.1007/ 978-3-319-18008-3_5.

38. Sule Virendra. Implicant based parallel all solution solver for Boolean satisfiability // arXiv preprint arXiv:1611.09590. — 2016.

39. Gaudioso Ginevra, Leonetti Matteo, Stone Peter. State Aggregation through Reasoning in Answer Set Programming. — Leeds, 2016.

40. Gebser Martin, Ryabokon Anna, Schenner Gottfried. Combining Heuristics for Configuration Problems Using Answer Set Programming // Logic Programming and Nonmonotonic Reasoning: 13th International Conference, LPNMR 2015, Lexington, KY, USA, September 27-30, 2015. Proceedings / Ed. by Francesco Calimeri, Giovambattista Ianni, Miroslaw Truszczynski. — Cham: Springer International Publishing, 2015. — Pp. 384-397. — URL: http://dx. doi.org/10.1007/978-3-319-23264-5_32.

41. Automated Resource Allocation in Business Processes with Answer Set Programming / Giray Havur, Cristina Cabanillas, Jan Mendling, Axel Polleres // 11th International Workshop on Business Process Intelligence. — 2015.

42. Mansor Mohd Asyraf, Kasihmuddin Mohd Shareduwan M, Sathasivam Saratha. VLSI Circuit Configuration Using Satisfiability Logic in Hopfield Network // International Journal of Intelligent Systems and Applications (IJISA). — 2016. — Vol. 8, no. 9. — P. 22.

43. Hopfield John J. Neural networks and physical systems with emergent collective computational abilities // Proceedings of the national academy of sciences. — 1982. — Vol. 79, no. 8. — Pp. 2554-2558.

44. Chandrakar Khushbu, Mishra Shashank, Roy Suchismita. SAT based low power scheduling and module binding with clock gating // Computer, Communication, Control and Information Technology (C3IT), 2015 Third International Conference on / IEEE. — 2015. — Pp. 1-5.

45. Kaxiras S., Martonosi M. 4.2 Idle unit switching activity: clock gating // Architectural Techniques for Low Power. — 2008. — Vol. 4, no. 8. — P. 207.

46. Ganguly Pritha, Chandrakar Khushbu, Roy Suchismita. SAT based approach for power on inrush current minimization with power gating // Electronics, Computing and Communication Technologies (CONECCT), 2015 IEEE International Conference on / IEEE. — 2015. — Pp. 1-5.

47. Chandrakar Khushbu, Roy Suchismita. Effect of increasing voltage levels on power saving obtained by multiple voltages design // Advance Computing Conference (IACC), 2015 IEEE International / IEEE. — 2015. — Pp. 867-871.

48. SAT-ATPG for application-oriented FPGA testing / Robert Hülle, Petr Fiser, Jan Schmidt, Jaroslav Borecky // Electronics Conference (BEC), 2016 15th Biennial Baltic / IEEE. — 2016. — Pp. 83-86.

49. Safar Mona, Salem Ashraf. Solving constraints in FPGA detailed routing using SMT // 2015 IEEE International Conference on Electronics, Circuits, and Systems (ICECS) / IEEE. — 2015. — Pp. 613-616.

50. Iizuka Tetsuya, Ikeda Makoto, Asada Kunihiro. High speed layout synthesis for minimum-width CMOS logic cells via Boolean satisfiability // IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences. — 2004. — Vol. 87, no. 12. — Pp. 3293-3300.

51. Ryzhenko N., Burns S. Standard cell routing via boolean satisfiability // Proceedings of the 49th Annual Design Automation Conference / ACM. — 2012. — Pp. 603-612.

52. Минимизация числа нежелательных топологий при проектировании стандартных ячеек / Рыженко Н.В., Сорокин А.А., Быков С.А., Талалай М.С. // Проблемы разработки перспективных микро- и наноэлектронных систем - 2014. Сборник трудов. — 2014. — № 1. — С. 121-136.

53. Н.В. Рыженко, А.А. Сорокин, С.А. Быков. Синтез блоков памяти с использованием представления правил в виде булевых функций от топологических объектов // Проблемы разработки перспективных микро-и наноэлектронных систем - 2014. Сборник трудов. — 2014. — № 1. — С. 127-132.

54. A boolean rule-based approach for manufacturability-aware cell routing / Jordi Cortadella, Jonathan Petit, Sergio Gomez, Francesc Moll // Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on. — 2014. — Vol. 33, no. 3. — Pp. 409-422.

55. Mukherjee Shyamapada, Roy Suchismita. Nearly-2-SAT Solutions for Segmented-Channel Routing // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. — 2016. — Vol. 35, no. 1. — Pp. 128-140.

56. Boolean Satisfiability-Based Routing and Its Application to Xilinx UltraScale Clock Network / Henri Fraisse, Abhishek Joshi, Dinesh Gaitonde, Alireza Ka-viani // Proceedings of the 2016 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays. — FPGA '16. — New York, NY, USA: ACM, 2016.

— Pp. 74-79. — URL: http://doi.acm.org/10.1145/2847263.2847342.

57. Design and manufacturability tradeoffs in unidirectional and bidirectional standard cell layouts in 14 nm node / Kaushik Vaidyanathan, Siew Hoon Ng, Daniel Morris et al. // SPIE Advanced Lithography / International Society for Optics and Photonics. — 2012. — Pp. 83270K-83270K.

58. Du Yuelin, Wong Martin DF. Optimization of standard cell based detailed placement for 16 nm FinFET process // Proceedings of the conference on Design, Automation & Test in Europe / European Design and Automation Association. — 2014. — P. 357.

59. Tseitin G. S. On the complexity of derivation in propositional calculus // Automation of reasoning. — Springer, 1983. — Pp. 466-483.

60. Cook Stephen A. The complexity of theorem-proving procedures // Proceedings of the third annual ACM symposium on Theory of computing / ACM. — 1971.

— Pp. 151-158.

61. Cortadella Jordi. Area-optimal transistor folding for 1-D gridded cell design // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. — 2013. — Vol. 32, no. 11. — Pp. 1708-1721.

62. Davis Martin, Putnam Hilary. A computing procedure for quantification theory // Journal of the ACM (JACM). — 1960. — Vol. 7, no. 3. — Pp. 201-215.

63. Davis Martin, Logemann George, Loveland Donald. A machine program for theorem-proving // Communications of the ACM. — 1962. — Vol. 5, no. 7.

— Pp. 394-397.

64. Lynce Inês, Marques-Silva Joao. Efficient haplotype inference with Boolean satisfiability // Proceedings of the National Conference on Artificial Intelligence / Menlo Park, CA; Cambridge, MA; London; AAAI Press; MIT Press; 1999. — Vol. 21. — 2006. — P. 104.

65. Plaisted D. A, Greenbaum S. A structure-preserving clause form translation // Journal of Symbolic Computation. — 1986. — Vol. 2, no. 3. — Pp. 293-304.

66. de la Tour Thierry Boy. An optimality result for clause form translation // Journal of Symbolic Computation. — 1992. — Vol. 14, no. 4. — Pp. 283-301.

67. Manolios Panagiotis, Vroon Daron. Efficient circuit to CNF conversion // International Conference on Theory and Applications of Satisfiability Testing / Springer. — 2007. — Pp. 4-9.

68. Jackson Paul, Sheridan Daniel. Clause form conversions for boolean circuits // International Conference on Theory and Applications of Satisfiability Testing / Springer. — 2004. — Pp. 183-198.

69. Een Niklas, Mishchenko Alan, Sörensson Niklas. Applying logic synthesis for speeding up SAT // International Conference on Theory and Applications of Satisfiability Testing / Springer. — 2007. — Pp. 272-286.

70. Gelfond Michael, Lifschitz Vladimir. The stable model semantics for logic programming. // ICLP/SLP. — Vol. 88. — 1988. — Pp. 1070-1080.

71. Van Gelder Allen, Ross Kenneth A, Schlipf John S. The well-founded semantics for general logic programs // Journal of the ACM (JACM). — 1991. — Vol. 38, no. 3. — Pp. 619-649.

72. Answer Set Programming for Logical Analysis of Data / Katinka Becker, Martin Gebser, Torsten Schaub, Alexander Bockmayr // Workshop on Constraint-Based Methods for Bioinformatics (WCB'16). — 2016. — P. 15.

73. Exploiting the enumeration of all feature model configurations: a new perspective with distributed computing / José A Galindo, Mathieu Acher, Juan Manuel Tirado et al. // Proceedings of the 20th International Systems and Software Product Line Conference / ACM. — 2016. — Pp. 74-78.

74. Domain-Specific Heuristics in Answer Set Programming. / Martin Gebser, Benjamin Kaufmann, Javier Romero et al. // AAAI / Citeseer. — 2013.

75. All-SAT using minimal blocking clauses / Y. Yu, P. Subramanyan, N. Tsiskaridze, S. Malik // VLSI Design and 2014 13th International Conference on Embedded Systems, 2014 27th International Conference on / IEEE. — 2014. — Pp. 86-91.

76. Grumberg Orna, Schuster Assaf, Yadgar Avi. Memory efficient all-solutions SAT solver and its application for reachability analysis // International Conference on Formal Methods in Computer-Aided Design / Springer. — 2004. — Pp. 275-289.

77. A Uniform Algorithm of Solving All-SAT Using Membrane Systems / Yueguo Luo, Zhongyang Xiong, Haijun Tan, Shuyin Xia // Journal of Computational and Theoretical Nanoscience. — 2015. — Vol. 12, no. 12. — Pp. 58255832.

78. Song Bosheng, Song Tao, Pan Linqiang. Time-free solution to SAT problem by P systems with active membranes and standard cell division rules // Natural Computing. — 2015. — Vol. 14, no. 4. — Pp. 673-681.

79. Toda Takahisa, Tsuda Koji. BDD construction for all solutions SAT and efficient caching mechanism // Proceedings of the 30th Annual ACM Symposium on Applied Computing / ACM. — 2015. — Pp. 1880-1886.

80. Progressive generation of canonical sum of products using a SAT solver / Ana Petkovska, Alan Mishchenko, David Novo et al. // Proceedings of the 25th International Workshop on Logic and Synthesis, Austin, Tex. — 2016.

81. Klebanov Vladimir, Manthey Norbert, Muise Christian. SAT-based analysis and quantification of information flow in programs // International Conference on Quantitative Evaluation of Systems / Springer. — 2013. — Pp. 177-192.

82. Klebanov Vladimir, Weigl Alexander, Weisbarth Jörg. Sound Probabilistic# SAT with Projection.

83. Thurley Marc. sharpSAT-counting models with advanced component caching and implicit BCP // International Conference on Theory and Applications of Satisfiability Testing / Springer. — 2006. — Pp. 424-429.

84. Bayardo Jr Roberto J, Pehoushek Joseph Daniel. Counting models using connected components // AAAI/IAAI. — 2000. — Pp. 157-162.

85. Combining Component Caching and Clause Learning for Effective Model Counting. / Tian Sang, Fahiem Bacchus, Paul Beame et al. // SAT. — 2004. — Vol. 4. — P. 7th.

86. Sang Tian, Beame Paul, Kautz Henry. Heuristics for fast exact model counting // International Conference on Theory and Applications of Satisfiability Testing / Springer. — 2005. — Pp. 226-240.

87. Östergard Patric RJ. A fast algorithm for the maximum clique problem // Discrete Applied Mathematics. — 2002. — Vol. 120, no. 1. — Pp. 197-207.

88. Tomita Etsuji, Kameda Toshikatsu. An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments // Journal of Global optimization. — 2007. — Vol. 37, no. 1. — Pp. 95-111.

89. Bron Coen, Kerbosch Joep. Algorithm 457: finding all cliques of an undirected graph // Communications of the ACM. — 1973. — Vol. 16, no. 9. — Pp. 575-577.

90. A new algorithm for generating all the maximal independent sets / Shuji Tsukiyama, Mikio Ide, Hiromu Ariyoshi, Isao Shirakawa // SIAM Journal on Computing. — 1977. — Vol. 6, no. 3. — Pp. 505-517.

91. Visualizing plant metabolomic correlation networks using clique-metabolite matrices / Frank Kose, Wolfram Weckwerth, Thomas Linke, Oliver Fiehn // Bioin-formatics. — 2001. — Vol. 17, no. 12. — Pp. 1198-1208.

92. A parallel algorithm for enumerating all maximal cliques in complex network / Nan Du, Bin Wu, Liutong Xu et al. // Sixth IEEE International Conference on Data Mining-Workshops (ICDMW'06) / IEEE. — 2006. — Pp. 320-324.

93. Makino Kazuhisa, Uno Takeaki. New algorithms for enumerating all maximal cliques // Scandinavian Workshop on Algorithm Theory / Springer. — 2004. — Pp. 260-272.

94. Avis David, Fukuda Komei. Reverse search for enumeration // Discrete Applied Mathematics. — 1996. — Vol. 65, no. 1. — Pp. 21-46.

95. Johnson David S, Yannakakis Mihalis, Papadimitriou Christos H. On generating all maximal independent sets // Information Processing Letters. — 1988. — Vol. 27, no. 3. — Pp. 119-123.

96. McCluskey Edward J. Logic design principles with emphasis on testable semicus-tom circuits. — 1986.

97. Rudell Richard, Sangiovanni-Vincentelli Alberto. Logic synthesis for VLSI design: Ph.D. thesis / University of California, Berkeley. — 1989.

98. Coudert Olivier. Two-level logic minimization: an overview // Integration, the VLSI journal. — 1994. — Vol. 17, no. 2. — Pp. 97-140.

99. Fiser Petr, Hlavicka Jan. Implicant Expansion Methods Used in The Boom Min-imizer // IEEE DESIGN AND DIAGNOSTICS OF ELECTRONIC CIRCUITS AND SYSTEMS WORKSHOP / Citeseer. — 2001.

100. Fiser Petr, Kubâtovâ Hana. Flexible two-level Boolean minimizer BOOM-II and its applications // 9th EUROMICRO Conference on Digital System Design (DSD'06) / IEEE. — 2006. — Pp. 369-376.

101. Sapra Samir, Theobald Michael, Clarke Edmund. SAT-based algorithms for logic minimization // Computer Design, 2003. Proceedings. 21st International Conference on / IEEE. — 2003. — Pp. 510-517.

102. Savran Ibrahim, Bakos Jason D. GPU acceleration of near-minimal logic minimization // Proceedings of Symposium on Application Accelerators in HighPerformance Computing / Citeseer. — 2010.

103. Logic minimization algorithms for VLSI synthesis / Robert K Brayton, Gary D Hachtel, Curt McMullen, Alberto Sangiovanni-Vincentelli. — Springer Science & Business Media, 1984. — Vol. 2.

104. Rudell Richard L. Multiple-valued logic minimization for PLA synthesis. — 1986.

105. Suto G. Rule agnostic routing by using design fabrics // Design Automation Conference (DAC), 2012 49th ACM/EDAC/IEEE / IEEE. — 2012. — Pp. 471-475.

106. Bhanushali Kirti Narayan. Design Rule Development for FreePDK15: An Open Source Predictive Process Design Kit for 15nm FinFET Devices. — 2014.

107. Lai Kafai, Erdmann Andreas. Extending VLSI and Alternative Technology with Optical and Complementary Lithography. — 2016.

108. Layout decomposition for triple patterning lithography / Bei Yu, Kun Yuan, Duo Ding, David Z Pan // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. — 2015. — Vol. 34, no. 3. — Pp. 433-446.

109. EUV resolution enhancement techniques (RETs) for k1 0.4 and below / Stephen Hsu, Rafael Howell, Jianjun Jia et al. // SPIE Advanced Lithography / International Society for Optics and Photonics. — 2015. — Pp. 94221I-94221I.

110. Rovner Vyacheslav V. Circuit-Layout Co-optimization for Extremely Regular Design Fabrics in Nanoscale ICs: Ph.D. thesis / Carnegie Mellon University Pittsburgh, PA. — 2010.

111. Open Cell Library in 15nm FreePDK Technology / Mayler Martins, Jody Maick Matos, Renato P Ribas et al. // Proceedings of the 2015 Symposium on International Symposium on Physical Design / ACM. — 2015. — Pp. 171-178.

112. Bhanushali Kirti, Davis W Rhett. FreePDK15: An Open-Source Predictive Process Design Kit for 15nm FinFET Technology // Proceedings of the 2015 Symposium on International Symposium on Physical Design / ACM. — 2015. — Pp. 165-170.

113. Library Architecture Challenges for Cell-Based Design. / Barbara Chappell, Amanda Duncan, Kiran Ganesh et al. // Intel Technology Journal. — 2004. — Vol. 8, no. 1.

114. A 5-10GHz SiGe BiCMOS FPGA with new configurable logic block / Chao You, Jong-Ru Guo, Russell P Kraft et al. // Microprocessors and Microsystems. — 2005. — Vol. 29, no. 2. — Pp. 121-131.

115. Zhao X-A, Kolawa E, Nicolet M-A. Reaction of thin metal films with crystalline and amorphous Al2O3 // Journal of Vacuum Science & Technology A. — 1986. — Vol. 4, no. 6. — Pp. 3139-3141.

116. Hu Xiao Ming. Photolithography technology in electronic fabrication. — 2015.

117. An overview of resist processing for deep-UV lithography. / Omkaram Nalamasu, May Cheng, Allen G Timko et al. // Journal of Photopolymer Science and Technology. — 1991. — Vol. 4, no. 3. — Pp. 299-318.

118. La Fontaine Bruno. Lasers and Moore's law // SPIE Professional, October. — 2010. — P. 20.

119. A 45nm logic technology with high-k+ metal gate transistors, strained silicon, 9 Cu interconnect layers, 193nm dry patterning, and 100% Pb-free packaging / Kaizad Mistry, C Allen, Chris Auth et al. // 2007 IEEE International Electron Devices Meeting / IEEE. — 2007. — Pp. 247-250.

120. Geppert Linda. Chip making's wet new world // IEEE Spectrum. — 2004. — Vol. 41, no. 5. — Pp. 29-33.

121. Schellenberg Frank. A little light magic [optical lithography] // IEEE Spectrum.

— 2003. — Vol. 40, no. 9. — Pp. 34-39.

122. Automated optical proximity correction: a rules-based approach / Oberdan W Otto, Joseph G Garofalo, KK Low et al. // SPIE's 1994 Symposium on Microlithography / International Society for Optics and Photonics. — 1994. — Pp. 278-293.

123. The selection and creation of the rules in rules-based optical proximity correction / Rui Shi, Yici Cai, Xianlong Hong et al. // ASIC, 2001. Proceedings. 4th International Conference on / IEEE. — 2001. — Pp. 50-53.

124. Practical method for full-chip optical proximity correction / J Chen, Thomas Laidig, Kurt Wampler, Roger Caldwell // Microlithography 97 / International Society for Optics and Photonics. — 1997. — Pp. 790-803.

125. Stirniman John, Rieger Michael. Fast proximity correction with zone sampling // SPIE's 1994 Symposium on Microlithography / International Society for Optics and Photonics. — 1994. — Pp. 294-301.

126. Stirniman John, Rieger Michael, Gleason Robert. Quantifying proximity and related effects in advanced wafer processes // SPIE's 1995 Symposium on Microlithography / International Society for Optics and Photonics. — 1995. — Pp. 252-260.

127. Stirniman John, Rieger Michael. Spatial-filter models to describe IC lithographic behavior // Microlithography'97 / International Society for Optics and Photonics.

— 1997. — Pp. 469-478.

128. Cobb Nicolas, Zakhor Avideh. Large-area phase-shift mask design // SPIE's 1994 Symposium on Microlithography / International Society for Optics and Photonics.

— 1994. — Pp. 348-360.

129. Cobb Nicolas, Zakhor Avideh. Fast, low-complexity mask design // SPIE's 1995 Symposium on Microlithography / International Society for Optics and Photonics.

— 1995. — Pp. 313-327.

130. Cobb Nicolas, Zakhor Avideh. Fast sparse aerial-image calculation for OPC // 15th Annual BACUS Symposium on Photomask Technology and Management'95 / International Society for Optics and Photonics. — 1995. — Pp. 534-545.

131. Matsunawa Tetsuaki, Yu Bei, Pan David. Optical proximity correction with hierarchical Bayes model // SPIE Advanced Lithography / International Society for Optics and Photonics. — 2015.

132. Optical Proximity Correction Using a New Hyper Error Estimation Method / Pei-Shan Wu, Yu-Cheng Lin, Jui-Hung Hung, Tsai-Ming Hsieh // Proceedings of the 2nd International Conference on Computer Science and Electronics Engineering / Atlantis Press. — 2013.

133. Awad Ahmed, Takahashi Atsushi, Kodama Chikaaki. A fast manufacturability aware Optical Proximity Correction (OPC) algorithm with adaptive wafer image estimation // 2016 Design, Automation & Test in Europe Conference & Exhibition (DATE) / IEEE. — 2016. — Pp. 49-54.

134. Patterning options for N7 logic: prospects and challenges for EUV / Eelco van Set-ten, Friso Wittebrood, Eleni Psara et al. // 31st European Mask and Lithography Conference / International Society for Optics and Photonics. — 2015.

135. 5nm Test Lights Litho Path. — http://www.eetimes.com/document.asp?doc_id= 1327919. — Accessed: 2016-05-27.

136. Yaung Dun-Nian, Wuu Shou-Gwo, Chao Li-chih, Huang Kuo. Double spacer technology for making self-aligned contacts (SAC) on semiconductor integrated circuits. — 2000. — US Patent 6,165,880.

137. Studies of plasma surface interactions during short time plasma etching of 193 and 248nm photoresist materials / Xuefeng Hua, S Engelmann, GS Oehrlein et al. //

Journal of Vacuum Science & Technology B. — 2006. — Vol. 24, no. 4. — Pp. 1850-1858.

138. Fabrication of sub-10-nm silicon nanowire arrays by size reduction lithography / Yang-Kyu Choi, Ji Zhu, Jeff Grunes et al. // The Journal of Physical Chemistry B.

— 2003. — Vol. 107, no. 15.

139. Multitechnique metrology methods for evaluating pitch walking in 14 nm and beyond FinFETs / Robin Chao, Kriti Kohli, Yunlin Zhang et al. // Journal ofMi-cro/Nanolithography, MEMS, and MOEMS. — 2014. — Vol. 13, no. 4.

140. Robust self-aligned via process for 64nm pitch Dual-Damascene interconnects using pitch split double exposure patterning scheme / H Tomizawa, St Chen, DHo-rak et al. // Interconnect Technology Conference and 2011 Materials for Advanced Metallization (IITC/MAM), 2011 IEEE International / IEEE. — 2011. — Pp. 1-3.

141. Ban Yongchan, Pan David. Self-aligned double-patterning layout decomposition for two-dimensional random metals for sub-10-nm node design // Journal of Mi-cro/Nanolithography, MEMS, and MOEMS. — 2015. — Vol. 14, no. 1.

142. Spacer-is-dielectric-compliant detailed routing for self-aligned double patterning lithography / Yuelin Du, Qiang Ma, Hua Song et al. // Design Automation Conference (DAC), 2013 50th ACM/EDAC/IEEE / IEEE. — 2013. — Pp. 1-6.

143. EUV litho keeps progressing, keeps slipping. — http://www.eetimes.com/ document.asp?doc_id=1256589. — Accessed: 2016-05-27.

144. Carlson Andrew, Liu Tsu-Jae. Negative and iterated spacer lithography processes for low variability and ultra-dense integration // SPIE Advanced Lithography / International Society for Optics and Photonics. — 2008.

145. Chen Frederick. Methods for forming patterns. — 2011. — US Patent 7,919,413.

146. Subresolution assist features in extreme ultraviolet lithography / Deniz Civay, Erik Verduijn, Chris Clifford et al. // Journal of Micro/Nanolithography, MEMS, and MOEMS. — 2015. — Vol. 14, no. 2.

147. Many ways to shrink: The right moves to 10 nanometer and beyond.

— https://staticwww.asml.com/doclib/investor/asml_3_Investor_Day-Many_ ways_to_shrink_MvdBrink1.pdf. — Accessed: 2016-05-27.

148. EUV lithography scanner for sub-8nm resolution / Jan van Schoot, Koen van Ingen Schenau, Chris Valentin, Sascha Migura // SPIE Advanced Lithography / International Society for Optics and Photonics. — 2015.

149. Chen Yijian, Cheng Qi, Kang Weiling. Mandrel and spacer engineering based self-aligned triple patterning // SPIE Advanced Lithography / International Society for Optics and Photonics. — 2012.

150. Imaging performance and challenges of 10nm and 7nm Logic nodes with 0.33 NA EUV / Eelco van Setten, Guido Schiffelers, Eleni Psara et al. // 30th European Mask and Lithography Conference / International Society for Optics and Photonics. — 2014.

151. Understanding the critical challenges of self-aligned octuple patterning / Ji Yu, Wei Xiao, Weiling Kang, Yijian Chen // SPIE Advanced Lithography / International Society for Optics and Photonics. — 2014.

152. First DailyTech IDF09 Intel Demonstrates. 22nm Chips Discusses Die Shrink Roadmap // URL http://www. dailytech. com/IDF09+ Intel+ Demonstrates+ First+ 22nm+ Chips+ Discusses+ Die+ Shrink+ Roadmap/article16312. htm.

153. Lin Burn J. The future of subhalf-micrometer optical lithography // Microelectronic engineering. — 1987. — Vol. 6, no. 1. — Pp. 31-51.

154. Despite economic slowdown, Intel on track with 32nm of win. — http://arstechnica.com/gadgets/2008/12/ despite- economic- slowdown- intel- on-track-with- 32nm- of-win/. — Accessed: 2016-09-10.

155. Immersion liquids for lithography in the deep ultraviolet / Michael Switkes, Roderick R Kunz, Roger F Sinta et al. // Microlithography 2003 / International Society for Optics and Photonics. — 2003. — Pp. 690-699.

156. Defectivity in water immersion lithography / U Okoroanyanwu, J Kye, N Ya-mamoto, K Cummings // Microlithography World. — 2005. — Vol. 14, no. 4. — Pp. 4-7.

157. Implications of immersion lithography on 193-nm photoresists / J Christopher Taylor, Charles R Chambers, Ryan Deschner et al. // Microlithography 2004 / International Society for Optics and Photonics. — 2004. — Pp. 34-43.

158. Imaging capabilities of resist in deep ultraviolet liquid immersion interferometric lithography / Alex K Raub, A Frauenglass, SRJ Brueck et al. // Journal of Vacuum Science & Technology B. — 2004. — Vol. 22, no. 6. — Pp. 3459-3464.

159. One-Photon Ionization of Liquid Water upon 193nm Laser Irradiation. / Aky-hiro Iwata, Nobuaki Nakashima, Yasukazu Izawa, Chiyoe Yamanaka // Chemistry letters. — 1993. — no. 11. — Pp. 1939-1940.

160. Pixelated source and mask optimization for immersion lithography / Xu Ma, Chunying Han, Yanqiu Li et al. // JOSAA. — 2013. — Vol. 30, no. 1. — Pp. 112123.

161. Polarization aberration compensation method by adjusting illumination partial coherent factors in immersion lithography / Yue Jia, Yanqiu Li, Lihui Liu et al. // SPIE/COS Photonics Asia / International Society for Optics and Photonics. — 2014.

162. High-performance circuit design for the RET-enabled 65-nm technology node / Lars W Liebmann, Arnold E Barish, Zachary Baum et al. // Microlithography 2004 / International Society for Optics and Photonics. — 2004. — Pp. 20-29.

163. Characterization of density profile of laser-produced Sn plasma for 13.5 nm extreme ultraviolet source / Y Tao, H Nishimura, S Fujioka et al. // Applied Physics Letters. — 2005. — Vol. 86, no. 20. — P. 201501.

164. Theoretical RCI Simulation for Spectra Emitted from Sn and Xe Ions as an EUV Light Source / Takashi Kagawa, Katsunobu Nishihara, Akira Sasaki, Fu-mihiro Koike.

165. Comparison of EUV spectral and ion emission features from laser-produced Sn and Li plasmas / RW Coons, D Campos, M Crank et al. // SPIE Advanced Lithography / International Society for Optics and Photonics. — 2010. — Pp. 763636763636.

166. Excimer lasers for superhigh NA 193-nm lithography / Rainer Paetzel, Hans Albrecht, Peter Lokai et al. // Microlithography 2003 / International Society for Optics and Photonics. — 2003. — Pp. 1665-1671.

167. Spectral control of emissions from tin doped targets for extreme ultraviolet lithography / SS Harilal, B O'Shay, MS Tillack et al. // Journal of Physics D: Applied Physics. — 2006. — Vol. 39, no. 3. — P. 484.

168. Power up: 120 Watt injection-locked ArF excimer laser required for both multi-patterning and 450 mm wafer lithography / Takeshi Asayama, Youichi Sasaki, Takayuki Nagashima et al. // SPIE Advanced Lithography / International Society for Optics and Photonics. — 2013.

169. EUV lithography: status, future requirements and challenges / Vadim Banine, Maarten van Kampen, Andrei Yakunin, Vladimir Ivanov. — 2013.

170. Das Sunil R. A new light source for EUV lithography // Spectrum, IEEE. — 2008.

— Vol. 45, no. 3. — Pp. 14-14.

171. Chen Frederick T. Asymmetry and thickness effects in reflective EUV masks // Microlithography 2003 / International Society for Optics and Photonics. — 2003.

— Pp. 347-357.

172. EUV production insertion: Factors to watch. — https://www.asml.com/ euv-is-at-the-cusp-of-being-introduced-in-volume-chip-production-the-industrializat en/s41905?rid=41906. — Accessed: 2016-12-10.

173. Hamm Robert, Hamm Marianne. The beam business: Accelerators in industry // Physics Today. — 2011. — Vol. 64, no. 6.

174. ASML demonstrates EUV with 130W light source, customers achieving 70 percent uptime. — http://www.dvhardware.net/article62846.html. — Accessed: 2016-05-20.

175. Demagnification in proximity x-ray lithography and extensibility to 25 nm by optimizing Fresnel diffraction / Yuli Vladimirsky, Antony Bourdillon, Olga Vladimirsky et al. // Journal of Physics D: Applied Physics. — 1999. — Vol. 32, no. 22. — P. L114.

176. Near-field x-ray lithography to 15 nm / Antony J Bourdillon, Gwyn P Williams, Yuli Vladimirsky, Chris B Boothroyd // Microlithography 2004 / International Society for Optics and Photonics. — 2004. — Pp. 546-557.

177. Sidewall slopes of SU-8 HARMST using deep X-ray lithography / Kaushal Dhirendra Vora, Bow Yuen Shew, Erol C Harvey et al. // Journal of Micromechanics and Microengineering. — 2008. — Vol. 18, no. 3.

178. Early K, Schattenburg ML, Smith Henry I. Absence of resolution degradation in X-ray lithography for A from 4.5 nm to 0.83 nm // Microelectronic Engineering. — 1990. — Vol. 11, no. 1-4. — Pp. 317-321.

179. Broers AN, Hoole ACF, Ryan JM. Electron beam lithography—resolution limits // Microelectronic Engineering. — 1996. — Vol. 32, no. 1. — Pp. 131-142.

180. Secondary electron generation in electron-beam-irradiated solids: resolution limits to nanolithography / Kyu Lee, SM Yoon, SC Lee et al. // J. Kor. Phys. Soc. — 2009. — Vol. 55, no. 4. — Pp. 1720-1723.

181. Anderson Erik, Chao Weilun. Double exposure makes dense high-resolution diffractive optics.

182. Dapor Maurizio, Ciappa Mauro, Fichtner Wolfgang. Monte Carlo modeling in the low-energy domain of the secondary electron emission of polymethylmethacrylate for critical-dimension scanning electron microscopy // Journal of Micro/Nano-lithography, MEMS, and MOEMS. — 2010. — Vol. 9, no. 2.

183. Long-distance charge transport in duplex DNA: the phonon-assisted polaron-like hopping mechanism / Paul T Henderson, Denise Jones, Gregory Hampikian et al. // Proceedings of the National Academy of Sciences. — 1999. — Vol. 96, no. 15. — Pp. 8353-8358.

184. Seiler H. Secondary electron emission in the scanning electron microscope // Journal of Applied Physics. — 1983. — Vol. 54, no. 11.

185. Measurement of the role of secondary electrons in EUV resist exposures. — http: //www.euvlitho.com/2013/P29.PDF. — Accessed: 2016-05-20.

186. Liddle JA, Gallatin GM, Ocola LE et al. Resist requirements and limitations for nanoscale electron-beam patterning. — 2003.

187. The inclusion of secondary electrons and Bremsstrahlung X-rays in an electron beam resist model / VV Ivin, MV Silakov, DS Kozlov et al. // Microelectronic engineering. — 2002. — Vol. 61. — Pp. 343-349.

188. Novel proximity effect including pattern-dependent resist development in electron beam nanolithography / Kenji Yamazaki, Kenji Kurihara, Toru Yamaguchi et al. // Japanese journal of applied physics. — 1997. — Vol. 36, no. 12S.

189. Influence on the secondary electron yield of the space charge induced in an insulating target by an electron beam / Raphaël Renoud, C Attard, JP Ganachaud et al. // Journal of Physics: Condensed Matter. — 1998. — Vol. 10, no. 26.

190. Technology mapping with Boolean matching, supergates and choices / Alan Mishchenko, Satrajit Chatterjee, Robert Brayton et al. — 2005.

191. Vujkovic Miodrag, Sechen Carl. Optimized power-delay curve generation for standard cell ICs // Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design / ACM. — 2002. — Pp. 387-394.

192. Correia Vinicius, Reis André. Advanced technology mapping for standard-cell generators // Proceedings of the 17th symposium on Integrated circuits and system design / ACM. — 2004. — Pp. 254-259.

193. DAG based library-free technology mapping / Felipe S Marques, LS Rosa Jr, Renato P Ribas et al. // Proceedings of the 17th ACM Great Lakes symposium on VLSI / ACM. — 2007. — Pp. 293-298.

194. Н.В. Рыженко, А.А. Сорокин. Алгоритм размещения транзисторов стандартных ячеек // Проблемы разработки перспективных микро- и наноэлектронных систем - 2014. Сборник трудов. — 2014. — № 1. — С. 133-136.

195. Riepe Michael, Sakallah Karem. Transistor placement for noncomplementary digital VLSI cell synthesis // ACM Transactions on Design Automation of Electronic Systems (TODAES). — 2003. — Vol. 8, no. 1. — Pp. 81-107.

196. Ihara Takeshi, Takahashi Atsushi, Kodama Chikaaki. Rip-up and reroute based routing algorithm for self-aligned double patterning // Proc. the 19th Workshop on Synthesis and System Integration of Mixed Information Technologies (SASIMI 2015). — 2015. — Pp. 83-88.

197. Lee Chin Yang. An algorithm for path connections and its applications // IRE transactions on electronic computers. — 1961. — no. 3. — Pp. 346-365.

198. Redundant-via enhanced maze routing for yield improvement / Gang Xu, Li-Da Huang, David Pan, Martin Wong // Proceedings of the 2005 Asia and South Pacific Design Automation Conference / ACM. — 2005. — Pp. 1148-1151.

199. Huang Li-Da, Wong Martin. Optical proximity correction (OPC): friendly maze routing // Proceedings of the 41st annual Design Automation Conference / ACM. — 2004. — Pp. 186-191.

Приложение А

Актуальные проблемы разработки нанометровых топологий компонентов

интегральных схем

Существуют различные подходы к разработке интегральных схем. Выбор методолгии проектирования оказывает большое влияние на дальнейшие стадии разработки конечного продукта. Выбор той или иной методологии определяется доступными временными ресурсами, требованиями к стоимости изготовления, производительности и энергопотреблению. Наиболее распространены 3 базовы подхода: полностью заказное проектирование, полузаказное проектирование и использование различных матричных кристаллов.

Матричные кристаллы

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

Программируемые логические интегральные схемы

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

функциональность которых можно изменить уже после изготовления самого чипа.

В случае устройств с фиксированной логикой может пройти от несколько месяцев до нескольких лет от проектирования до производства. При обнаружении каких-либо ошибок или изменении технологических требований, требуется повторить полный цикл проектирования, что существенно повышает единовременные затраты на проектирование (англ. non-recurring engineering cost, NRE) и итоговую стоимость изделия.

Для проектирования же устройств с изменяемой логикой можно достаточно быстро получить прототип, провести симуляцию и его тестирование, причем ПЛИС, использованная в прототипе аналогична той, которая будет использована в итоговом решении. При таком подходе NRE затраты практически отсутствуют. Рассмотрим различные подходы к изготовлению программируемых логических устройств.

Программируемые логические матрицы

ПЛМ представляют собой множество рядов программируемых логических вентилей И, соединенных с рядами программируемых вентилей ИЛИ. Вместе они могут объединены для представления необходимой функциональность в конъюнктивной нормальной форме. Для работы с N входными параметрами необходимо 2n логических вентилей И, для работы с M выходных сигналов необходимо 2м вентилей ИЛИ. Каждый транзистор в наборе И и ИЛИ вентилей может быть "включен"или "выключен". Данный подход отличается от программируемых пользователем матричных кристаллов ограниченными возможностями к трассировке.

Программируемые пользователем матричные кристаллы

ППВМ представляет собой полупроводниковое устройство, которое может быть сконфигурировано пользователем уже после изготовления.

Базовым элементом ППВМ являются нескоммутированные программируемые логические блоки с несколькими входами и одним выходом. Они используются для построения пользовательской логики. Такой блок состоит из таблицы истинности от нескольких переменных и триггера. Как правило, входы блока размещены на отдельных сторонах, выход же может быть выведен либо вниз от блока, либо вправо. Выходные контакты каждого логического блока могут соединяться с трассировочными сегментами в смежных каналах. Аналогично, контактная площадка блока ввода-вывода может соединяться с трассировочным элементом в любом смежном канале.

Сигнальные межсоединения проходят между блоками как в горизонтальном, так и в вертикальном направлении. Эти проводники соединяют логические блоки между собой и со входами/выходами схемы. В точках пересечения горизонтальных и вертикальных сегментов устанавливаются переключательные блоки. При таком подходе, для каждого проводника задается несколько переключателей, позволяющих подключаться к остальным смежным проводникам.

Современные ППВМ содержат миллионы логических вентилей и предоставляют мегабайты памяти. Они позволяют обрабатывать входные данные с частотой порядка 10 ГГц [114]. Также они могут содержать встроенные микропроцессоры и различные ускорители. Их сравнительно низкая стоимость и простота исправления ошибок проектирования является существенным плюсом при разработке различных устройств.

Базовые матричные кристаллы

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

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

Стандартные ячейки

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

- Простые логические компоненты (И, ИЛИ, ИЛИ-И, И-ИЛИ...), буфера, инверторы, регистры;

- Элементы памяти (RAM, ROM, CAM, регистровые файлы);

- Микропроцессорные ядра, последовательные интерфейсы, интерфейсы шин данных;

- Аналого-цифровые и радио компоненты.

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

Как правило, стандартные ячейки имеют фиксированную высоту, линии питания и земли проходят по верхнему и нижнему краю, что позволяет составлять из ячеек ряды. Вдоль линии питания проходит ряд р-канальных транзисторов, вдоль линии "земли"проходят п-канальные транзисторы.

Полностью заказные интегральные схемы

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

Высокая стоимость данного метода проектирования делает его применение обоснованным только в случае очень больших объемов производства. Однако, и сегодня отдельные компоненты СБИС, такие как память, аналоговые схемы, и стандартные ячейки выполняются на заказ.

Заключение

В данной главе были рассмотрены различные методы проектирования СБИС. В Таблице 5 показаны характеристики методов.

Таблица 5 — Сравнение методов проектирования

Метод NRE Стоимость Сложность Энергопотребление Время до выпуска Производительность Гибкость

ПЛМ Низк. Средн. Средн. Низк. Низк. Средн. Низ.

ППВМ Низк. Средн. Средн. Средн. Низк. Выс. Выс.

Стандартные Выс. Низк. Низк. Выс. Выс. Выс. Низ.

ячеики

Заказные Выс. Низк. Низк. Выс. Выс. Оч. выс. Низ.

Технология оптической литографии

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

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

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

Фотолитография (англ. photolithogгaphy) — метод получения определённого рисунка на поверхности материала, широко используемый в микроэлектронике. Один из основных приёмов планарной технологии, используемой в производстве полупроводниковых приборов. Участки подложки, на которые впоследствии будет нанесен необходимый материал, определяются нанесением фоторезиста. После экспонирования определенные участки фоторезиста становятся растворимыми и образуют окна, через которые и наносится необходимый материал.

Маска создается из кварцевого стекла, покрытого слоем хрома. Слой фоторезиста экспонируется при помощи УФ света. Участки маски, покрытые

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

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

Очистка. Если на поверхности подложки обнаружены органические или неорганические загрязнения, то как правило их удаляют в ультразвуковой ванне с использованием органических растворителей. Иногда требуется более основательная очистка с использованием смеси серной кислоты и пероксида водорода Н2Б04 + Н202 [115].

Предобработка. Подложка предварительно высушивается при температуре около 150оС на протяжении 10 минут. Подложки, которые до этого были на хранении длительное время, дополнительно очищаются. Для увеличения адгезии подложку покрывают тонким слоем адгезива, помещая ее в жидкую или газообразную среду. В качестве адгезива используют, например, гексаметилдисилазан. Дополнительно, поверхностный слой диоксида кремния вступает в реакцию с гексаметилдисилазаном и образует водоотталкивающую пленку, которая предотвращает возникновение неоднородностей между слоем фоторезиста и подложкой. После этого подложка снова просушивается, теперь уже при температуре 120оС [116].

Нанесение фоторезиста. Чаще всего подложку круглой форму покрывают фоторезистом при помощи центрифугирования. Вязкий, жидкий раствор фоторезиста покрывает подложку, после чего ее начинают вращать 30-60 секунд со скоростью от 1200 до 4800 оборотов в секунду. В результате образуется

равномерный слой фоторезиста толщиной около 0.5-2.5 микрометра. Как правило, толщина слоя меняется не более чем на 5-10 нанометров. Такая равномерность обеспечивается тем, что нижние слои фоторезиста более вязкие и цепляются за поверхность подложки, в то время как верхние слои более жидкие и стекают с края пластины. При этом различные складки на поверхности резиста сглаживаются. Стоит отметить, что при изготовлении компонентов нанометровых топологий (менее 120 нанометров) требуется крайне тонкий слой резиста (менее 0.5 микрометра). Итоговая толщина резиста во многом определяется также испарением растворителей. Излишки удаляются при помощи повторного задубливания на протяжении 30-60 секунд при температуре 90 — 100°C.

Экспонирование. После дубления, фоторезист подвергают засвечиванию через маску с использованием света в видимом или ультрафиолетовом диапазоне. Под действием света фоторезист меняет свои химические свойства. Выделяют два вида резистов: позитивный и негативный. Первый, чаще используемый на практике, под действием света становится растворимым в "проявителе", растворе, который используется для смывания резиста. В случае негативного варианта наоборот, участки, подвергшиеся действию света становятся нерастворимыми в "проявителе".

Дополнительное дубление используется перед проявлением, чтобы предотвратить искажения, возникающие под действием интерференции падающего света. Этот этап сильно зависит от времени нагрева, температуры и времени, прошедшему после экспозиции, т.к. большая часть реакций, вызванных светом, происходят именно на этапе дополнительного дубления. В частности, в этот момент резист становится растворимым [117].

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

После проявления подложка снова задубливается на протяжении 20-30 минут при температуре 120 — 180°C. На этом этапе происходит отвердевание

оставшегося фоторезиста для защиты подложки на последующих этапах нанесения примесей и травления.

Травление. На этапе травления верхний слой подложки удаляется под действием химических веществ. Различают жидкостное травление с использованием жидких реагентов и реактивное ионное травление с использованием плазмы. В производстве микроэлектроники чаще применяют последний способ, т.к. он в меньшей степени вносит искажения в итоговый шаблон. Это особенно важно в случаях, когда ширина компонентов шаблона становится сравнимой с толщиной нанесенного материала. Жидкостное травление изотропно и происходит как в направлении перпендикулярном подложке, так и в горизонтальном, под слой фоторезиста, что делает детали рисунка большего размера, чем требуется.

Разработка методов "сухого" реактивного ионного травления, вносящего минимальные искажения в шаблон, позволило изготавливать СБИС по еще меньшим технологическим нормам с использованием отработанного и общепризнанного метода фотолитографии.

Удаление фоторезиста. После того, как резист становится не нужным, он должен быть удален с подложки. Как правило, для этого используют жидкий "растворитель уменьшающий адгезию фоторезиста по отношению к подложке. Другой способ удаления резиста заключается в использовании плазмы, насыщенной кислородом, который используется как окислитель. это процесс называется "озоление" и напоминает процесс травления. Также для удаления фоторезиста используют растворитель на основе 2-Метил-2-пирролидона (англ. 1-МеШу1-2- руггоШопе, NMP). Когда резист окончательно удален, растворитель разрушается нагреванием до 80оС, не оставляя после себя никаких следов.

Фотомаска как правило меньше пластины, на которую будет наносится рисунок. Длина одной стороны оставляет около 2 см. Степпер перемещает маску шаг за шагом, поэтапно экспонируя всю пластину. Как правило, используется проективная печать — линзы, расположенные между максой и подложкой, фокусируют наносимый шаблон на поверхности подложки. Ранее использовали контакную печать, когда маска непосредственно касалась подложки, и "близкую" печать, при которой маска размещается рядом с подложкой, но не касается ее. Маска может быть такого же размера, как и размер наносимого шаблона (1х) или

же может быть больше. Например, в промышленности используют степперы 2.5х и 5х с соответствующими технологиями оптического масштабирования.

Ограничения оптической литографии

Возможность нанесения четкого изображения на подложку ограничивается длиной волны используемого источника излучения и возможностью системы линз компенсировать дифракцию при засветке фотошаблона. Современные системы фотолитографии используют эксимерные лазеры с длиной волны 193 нм, которые позволяют печатать рисунки с деталями размера около 50 нм. За последние 20 лет эксимерные лазеры оказали большое влияние на непрекращающееся развитие микроэлектроники, обусловленное законом Мура [118].

На размеры наносимого рисунка большое влияние оказывает длина волны используемого излучения. Пусть минимальный шаг затвора (минимальная ширина затвора + минимальное расстояние между двумя затворами) равно 2Ь. Разрешающая способность системы линз зависит от длины волны Ц источника излучения и отчисловой апертуры линз:

2Ь = кг Х

NA

Числовая апертура при этом равна:

NA = n sin а

, где n — коэффициент преломления среды (для воздуха он равен 1, для воды 1.33, для масла 1.5), F — апертурный угол. Увеличение F требует увеличения системы линз. Линзы, использовавшиеся в 70-ых годах, обеспечивали значение апертуры 0.2. Компания Intel для процесса 45 нм добилась апертуры 0.92 [119]. В 2008 Компани Nikon и ASML смогли увеличить апертуру до 1.35 с использованием иммерсионной литографии, учитывающей больший коэффициент преломления воды [120]. Весь этот прогресс привел к значительному удорожанию оптических систем, цена которых стала измеряться миллионами долларов. Значение параметра k обуславливается когеретностью

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

Глубина фокуса обпределяется по формуле:

ВОЕ = к2Х

NA2

, где k2 принимает значения от 0.5 до 1. Современные литографические с коротковолновым излучением и большой апертурой обеспечивают небольшую глубину фокуса. Как результат, поверхность подложки должна быть максимально плоской. В 80-ых годах использовались ртутные лампы с рабочей длиной волны 436 нм или 365 нм. Для технологии 250 нм стали использовать эксимерный лазер с длиной волны 248 нм и продолжали его применять вплоть до технологии 180 нм. Современные системы используют ArF лазеры с длиной волны 193 нм при работе с критическими слоями на процессах от 45 нм и менее. Критическими называют слои, определяющие параметры ИС. К ним относят слой поликремния для изготовления затворов, слой диффузии для стока/истока, первый металл и слой контактных площадок. Наименьший шаг затвора, которого можно добиться при числовой апертуре 1.35 и к равном 0.5, составляет 2b = 72. Соответственно, полушаг затвора равен 36 нм. Несмотря на то, что современные технологии позволяют изготавливать рисунки с деталями существенно меньше рабочей длины волны используемого излучения, процесс литографии для технологий 45 нм и менее стал существенно сложнее и дороже. Много усилий было приложено для разработки лазера с длиной волны 157 нм, однако, основные игроки на рынке микроэлектроники в итоге отказались от использования этой технологии. Ожидается, что в будущем будут применяться системы на базе источника света в сверхглубоком ультрафиолете (англ. extreme ultreviolet, EUV) с длиной волны 13.5 нм. Однако, их применение сегодня ограничивается крайне высокой стоимостью необходимых оптических систем, использование вакуума в качестве окружающей систему среды и недостаточно высокой производительностью для производственных линий.

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

улучшения разрешающей способности могут быть использованы для предварительной компенсации этого эффекта таким образом, что будет получен желаемый рисунок [121]. Эти техники включают в себя коррекции амплитуды, фазы и угла падения падающего излучения. Концы линий на краю схемы получают меньше, чем в центре, что приводит к неравномерной экспозиции.

Методы коррекции искажений в оптической литографии

Коррекция эффектов оптической близости (англ. optical proximity correction, OPC) является одним из способов повышения точности переноса изображения с маски на подложку. Целью является улучшение оптических параметров путем изменения маски. Достигается эта цель таким изменением геометрии маски, которое будет компенсировать искажения, возникающие на этапе экспонирования. Более формально задачу OPC можно поставить следующим образом: для заданного шаблона на подложке необходимо найти такую геометрию маски, которая после этапа литографии сформирует рисунок, минимально отличающийся от целевого. С этой точки зрения OPC является "обратной задачей", где OPC является процессом, обратным литографии. Изменения маски являются "предкомпенсацией", которые обеспечивают точность финального шаблона.

Как результат, OPC приводит к более предсказуемым минимальным размерам (англ. critical dimensions, CDs) компонентов и положению границ объектов. Более того, OPC позволяет варьировать различные параметры процесса литографии (англ. process window) для повышения качества изготовления различных геометрических структур.

С практической точки зрения OPC обеспечивает:

- Увеличение выхода продукции при изготовлении компонентов минимального размера из-за оптимальных параметров литографического процесса;

- Единообразие длин межсоединений, позволяющие увеличивать тактовую частоту СБИС;

- Введение правил проектирования для компонентов минимального размера.

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

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

OPC с использованием моделей предлагает способ повышения точности коррекции масок ценой повышения времени работы метода. Вносимые корректировки определяются результатами симуляций. При использовании корректных моделей оптики, фоторезиста и процесса травления, симуляция по маске может построить шаблон-результат с высокой точностью. Первые алгоритмы OPC с использованием моделей были представлены в работах [125-127]. В работах [128-130] OPC с моделированием представляется как итеративный процесс, в котором геометрические формы корректируются согласно предыдущим итерациям алгоритма. При этом скорость работы алгоритма на каждой итерации становится критичной для сокращения общего времени работы метода, что особенно важно при работе с современными технологическими процессами.

В работе [131] рассматривается метод сокращения числа итераций, необходимых для выполнения OPC с использованием иерархических баесовских

моделей. Поиск оптимальных параметров для описания входных данных выполняется методом Монте Карло по схеме марковских цепей. Решения, полученные обсуждаемым методом, оказывались лучше, чем построенниые с использованием традиционных подходов, например, линейной и нелинейной регрессий. Более того, результаты работы метода с использованием байесовских моделе могут быть использованы как начальное приближение для традиционных подходов, что также сокращает временные затраты на выполнение OPC.

За последние годы полупроводниковая индустрия добилась большого прогресса. Для того, чтобы упростить процесс литографии при изготовлении ИС и увеличит выход годных устройств, можно использовать метод коррекции эффектов оптической близости с использованием моделей. Данная техника позволяет повысить точность и аккуратность нанесения изображения. Однако, процесс симуляции литографии является ресурсоемкой процедурой. В данной работе предлагается модифицированная процедура OPC для внесения корректировок в маску. Процедура состоит из трех этапов. На первом этапе предварительно вычисляются параметры каждого шаблона. Затем, топология разделяется на отдельные участки с целью увеличения производительности и для преодоления проблем выравнивания изображения. Наконец, с использованием рядя формул выполняется поиск проблемных участков топологии. Первые два этапа повышают производительность самого алгоритма, в то время как третий этап повышает качество результирующего изображения. Экспериментальные результаты показывают, что применение рассматриваемого подхода может сократить усредненную величину ошибки размещения краев (англ. edge placement error, EPE) от 259.76 микрометров до 7.24 микрометров [132].

В работе [133] рассматривается иной подход к OPC. В процессе выполнения алгоритма вычисляются несколько карт интенсивности освещения — базовая и компенсирующие. Параметры компенсирующих карт итеративно оптимизируются с последовательным применением нескольких вычислительных ядер и при учете заданных правил проектирования. Для увеличения производительности предложеного алгоритма оптимизируемая топология вписывается в дискретную сетку. На заключительном этапе выполняются выполняется минимизация числа нарушений правил проектирования. Экспериментальные результаты показывают, что описанные алгоритм помогает автоматически разрешить от 50% до 80% нарушений топологии.

Технология множественного шаблона (англ. multi-patterning) включает в себя различные подходы к изготовлению ИС, разработанные для увеличения плотности наносимых деталей шаблона. Данная технология считается необходимой при работе с технология 10 нм, 7 нм и менее. Предполагается, что в рамках данных технологических процессов один шаг экспонирования не сможет обеспечить необходимой разрешающей способности. Таким образом возникает необходимость в обеспечении нескольких последовательных шагов экспонирования. Иначе, возникает необходимость в использовании дополнительных ограничителей на этапе травления.

Несмотря на то, что EUV литография рассматривается как основная замена фотолитографии, сам процесс вероятно не станет проще. В частности, при использовании EUV все еще будет требоваться несколько этапов экспозиции для того, чтобы сначала нанести несколько линий, а затем разрезать их [134]. И, судя по всему, выполнение разрезов также будет проводиться в несколько этапов [135].

Прямолинейный подход предполагает последовательное экспонирование и травление (не менее двух раз) для нанесения отдельных изображений в одном и том же слое. Каждая экспозиция требует отдельного нанесения слоя фоторезиста. Когда последователь нанесения рисунка завершена, итоговое изображение складывается из предварительно вытравленных подизображений. Теоретически, при помощи совмещения промежуточных изображений можно увеличивать плотность наносимых деталей неограниченно, причем величина полушага затвора обратно пропорциональна числу использованных масок. Например, при необходимости обеспечить величину полушага затвора равной 25 нм могут быть использованы две маски с полушагом 50 нм, три маски с полушагом 75 нм или же 4 маски с полушагом 100 нм. Сокращение размеров деталей может потребовать использования вспомогательных техник, таких как химическое сжатие, термическое обдувание или использования специальных пленок. Итоговый составной шаблон может быть нанесен на последний слой.

В качестве примера использование такого подхода можно назвать разделение слоя контактов на две группы: контакты затвора и контакты стока/истока, каждая из которых определяется своей маской. ИМЕК недавно использовала такой подход при изготовлении ячейки памяти SRAM с 6 транзисторами с применением "сухой" литографии [134].

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

Разновидностью данного метода является подход с замещением травления шаблона первой маски закреплением резиста [135], который позволяет наносить второй слой резиста поверх уже проявленного первого. JSR продемонстрировала топологии, полученные при помощи этого метода с использованием 32 нанометровой технологии, где фиксация резиста выполняется дополнительным дублением [136].

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

Подход с использованием спейсеров уникален в том отношении, что за единственный проход экспонирования шаг затвора может быть скоращен в два раза за счет нанесения вспомогательного слоя и сдвига рисунка. В частности, две подхода self-aligned double patterning приводят к четырехкратному сокращению шага затвора. Этот подход часто упоминается под названием self-aligned quadruple patterning (SAQP). Также подход с использованием спейсеров позволяет избежать наложения рисунков при последовательных экспозициях. Часто эта технология используется при формировании FinFET транзисторов.

Для изготовления спейсеров используют как правило твердые материалы (англ. hardmask), которые сохраняют свою форму лучше, чем фоторезист, линии которого часто подвергаются искажениям [137].

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

соседнего участка вместе с ним удаляется материал под спейсером. Такое искажение делает топологию ассиметричной: с одной стороны от спейсера материала оказывается больше, чем с противоположной [138]. Любое смещение маски для слоев критческих размеров может вызвать изменения в величине шага затвора (англ. pitch walking) [139].

Положение спейсера также зависит и от размеров шаблона, на котором он закреплен. Если шаблон слишком широк или слишком узок, то позиция спейсера может измениться в процессе травления.

В первоначальном варианте спейсеры изготавливались из проводящих материалов, что требовало дополнительных разрезов после нанесения требуемого рисунка. Современные процессы используют диэлектрики в качестве материала для спейсеров (англ. spacer-is-dielectric, SID), и таким образом спейсеры соответствуют диэлектрически пропускам между поводниками и не требуют выполнения дополнительных разрезов. Подходящее размещение спейсеров на топологии при таком подходе приобретает большое значение, как и возможность изготавливать спейсеры сложной формы, помимо нанесения линий [140; 141]. SID подход стал наиболее распространенным в силу его гибкости и необходимости использования небольшого числа дополнительных масок [142].

ИМЕК отмечает, что в случае, если EUV литография не будет готова к использованию, будет применяться технология множественного шаблона [143].

Помимо использования двукратного нанесения рисунка, также используются технологии с множественным применением спейсеров, причем в разных вариантах [144]. Подход с применение многослойных спейсеров также позволяет добиться хороших результатов [145].

Предполагалось, что литография в глубоком ультрафиолете может опираться на применение одного шага экспонирования, однако появление двумерных шаблонов в 7 нм процессе, горизонтально-вертикальная ассиметрия и дробовой шум исключили эту возможность [134; 146].

В ноябре 2014 компания ASML представила 7 нм технологический процесс (с полушагом затвора 16 нм), первый процесс предполагающий применение EUV литографии. Однако, он все также опирается на использование технологии двойного шаблона, причем даже в большей степени, чем 20 нм процесс опирался на иммерсионную литографию [147]. Технология двойного шаблона в этом случае

может быть типа EUV+EUV, хотя скорее всего распространение получит схема 193 нм+EUV, в силу относительно низкой стоимости применения 193 нм лазера.

EUV литография с большим значением параметра NA (> 0.5) предполагается необходимой для 5 нм технологического процесса (11 нм полушаг затвора). Размер рабочего поля при этом изменится с традиционного 26х33 мм на 26х16.5 мм, т.к. степень размагничивания маски в соответствующем направлении удвоится (с 4х до 8х) [148]. Таким образом, потребуется 2 этапа экспонирования, чтобы обработать обе половины рабочего поля, которое может быть обработано за один проход иммерсионной литографии.

Если SID процедуру применить после SADP, то шаг затвора может быть уменьшен в четыре раза, причем без добавления вспомогательных разрезов, помимо необходимых при двойном нанесении рисунка. Гибкость этого подхода обуславливается тем, что спейсеры выполняются изолирующим материалом, что делает сокращает число дополнительные этапов экспонирования , либо исключает их вовсе. Более того, разрешение может быть увеличено и за счет того, что маски для металлических спейсеров могут быть сами построены по технологии SADP [149]. Таким образом, металлы, наносимые методом двойного шаблона наносятся методо учетверенного шаблона без использования дополнительных масок, т.к. последний слой спейсеров является диэлектриком. Стоимость технологии множественного шаблона даже для 2D топологий обуславливается применением не более двух SAQP масок, что обеспечивается величину полушага затвора порядка 11-12 нм. EUV литография при этом не демонстрирует аналогичной гибкости при 16 нм полушаге (для технологии 7нм) [150] и, соответственно, требует такого же числа масок, что и иммерсионная литография с 193 нм длиной волны. При добавлении еще одного слоя спейсеров, технология SAQP может быть расширена до технологии self-aligned octuple patterning (SOAP) [151]. Такой подход может быть обощен до произвольной степени кратности, с учетом того факта, что слой металла, изготовленый двойным шаблоном, может быть изготовлен при помощи технологии четырехкратного шаблона без добавления масок, т.к. последний слой спейсеров наносится диэлектриком.

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

жидкой средой с коэффициентом преломления больше единицы. Разрешение при этом увеличивается пропорционально коэффициенту преломления. Современные иммерсионнные системы используют сильноочищенную воду в качестве такой среды, при работе с технологиями 45 нм и менее [152]. Единственными производителями иммерсионных систем являются компании ASML, Canon и Nikon. Впервые же идея такого подхода и первые прототипы появились в 80-ых годах [153].

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

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

Успешное развитие технологии иммерсионной литографии обусловлен не только возможностью улучшить разрешающую способность или глубину фокуса, но и своевременным выходом на рынок во время перехода от 65 нм процесса к 45 нм.

Компания Intel впервые применила иммерсионную литографию в своем 32 нм процессе с использованием high-k технологии с металлическими затворами [154].

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

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

Также известно, что свет с длиной волны 193 нм ионизирует воду [159], что приводит к появлению электронов, вступающих в реакцию с фоторезистом. Этот эффект негативно влияет на разрешение.

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

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

границу рабочего пространства и может потечь вспять, внося искажения в рисунок.

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

Системы иммерсионной литографии с большой числовой апертурой (больше 1) стали необходимыми при работе на технологиях от 45 нм и менее. Ключевой технологией при этом стала совместная работа над масками и над исгочниками излучения (англ. source-mask optimisation, SMO). В частности, были продемонстрированы алгоритмы попиксельного SMO на базе метода градиентного спуска. В работе [160] предлагается метод, использующий в качестве модели векторные изображения. Результаты работы этого метода находятся в соответствии с экспериментальными данными, полученными от современных иммерсионных систем. В этой работе также рассматриваются различные подходы к выполнению SMO: последовательный (шаг оптимизации параметров источника света, затем шаг оптимизации маски), параллельные (одновременно оптимизируются параметры и источника света, и маски), выполняется только оптимизация источника света, выполняется оптимизация только маски. Также предлагается наиболее эффективный гибридный подход, включающий в себя оптимизацию источника света, параллельную оптимизацию и отдельную оптимизацию маски.

В работе [161] демонстрируется, что по мере увеличения величины числовой апертуры и сокращению коэффициента k значительную долю искажений создает поляризационная аберрация (англ. polarization aberration, PA). В качестве решения данной пролемы предлагаются различные схемы изменения параметров источника света, уменьшающие число нарушений топологии, вызванных эффектом аберрации для слойев критических размеров. Предлагаемый метод успшно корректирует величину аберрации и в случае сложных промышленных систем оптики.

Правила проектирования

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

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

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

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

Одним из популярных способов описания правил проектирования является масштабируемая модель на основе Л параметра, характеризующего разрешающую способность технологического процесса. Чаще всего Л соответствует величине половины минимальной ширины затвора. Такие правила консервативны, т.к. все значения округляются до целого числа Л. Такой подход

позволяет переходить на новый технологический процесс простым измененим значения Л.

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

Сокращение технологических норм увеличивает число и величину искажений, возникающих при нанесении изображения на подложку. Ограничивающие правила проектирования (англ. restricting design rules, RDR) были предложены в качестве решения этой проблемы компаниями IBM и Intel [162]. Например, в слоя полисиликона для формирования затворов вводятся следующие ограничения: затворы должны быть сформированы в одном направлении, иметь одинаковую ширину и располагаться на одинаковом расстоянии друг от друга. В случае современных технологий сходные правила вводятся и для слоев металлизации.

Перспективные технологии литографии

Одной из наиболее перспективных и ожидаемых альтернатив традиционной фотолитографии является литография в глубоком ультрафиолете. В основе этого метода лежит применение источника света в экстремальном ультрафиолете с длиной волны 13.5 нм. Ожидается, что в комбинации с иммерсионной литографией этим методом можно будет изготавливать элементы 5 и 7 нанометровых технологий.

Незаряженные частицы или вещество в конденсироанном состоянии не может излучать в EUV диапазоне, в силу чего материал излучателя должны быть предварительно ионизирован. Высокотемпературный подход синтеза ионов включает в себя получение горячей плазмы высокой плотности, которая сама

по себе хорошо поглощает EUV [163]. В 2016 году в качестве источника EUV излучения используют олово, накаченное лазером [164], где источником излучения с длиной волны 13.5 нм являются ионы с высокими зарядами [165]. Стоит отметить, что эти ионы поглащают собственное излучение и легко теряют заряд под действием электронов в плазме, производя свет с большими длинами волн, что существенно снижает применимость такого источника света для литографии.

В то время как современные эксимерные лазеры обладают интенсивностью света 200[166], EUV излучение от плазмы должно быть куда мощнее, порядка 1011 [167]. Такой рост требуемой мощности указывает и соответствующие требования к требуемым источникам энергии. В частности, эксимерные лазеры требуют порядка 100 Вт, в то время как предполагаемое энергопотребление EUV системы составляет 10 кВт. Современная система иммерсионной литографии с ArF лазером потребляет не более 40 кВт [168] и обеспечивает 120 Вт мощности излучения, в то время как соответствующая EUV система будет потреблять существенно больше 40 кВт [169].

Плазмненные источники EUV излучения все еще не обеспечивают достаточной степени когерентности света [170], в отличие от KrF или ArF эксимерные лазеры. Попытки фильтрации излучения приводят к значительным потерям энергии. В свою очередь, когеретное излучение может приводить к проблемам с бликами и переотражениями [171].

EUV системы также не обеспечивают необходимой производительности. Компания ASML в своем отчете утверждает, что EUV оборудование становится рентабельным при возможности изготавливать более 60 пластин в час, если сравнивать с процессом на базе множественного шаблона. На 2016 год такое оборудование позволяет изготавливать 40 пластин в час [172].

Для обеспечения более высокого качества излучения можно использовать лазеры на свободных электронах и синхротроны. Однако, достижение необходимого уровня мощности с применением данных технологий потребуют большого объема НИОКР. Лазеры со свободными электронами обеспечивают когерентное и монохроматичное излучение с небольшим углом раствора луча. Обе технологии также предлагают непрерывный набор доступных длин волн, что может быть использовано для незаметного перехода к рентгеновскому диапазону [173].

В сентябре 2015 года ASML продемонстрировала EUV установку с источником света мощности 130 Вт и 70% непрерывным временем работы у некоторых клиентов. Однако, демонстрация длилась всего неделю, в одном случае 4 недели [174].

Рентгеновская литография является другой перспективной технологией изготовления СБИС нанометровых технологий. Длина волны менее 1 нм позволяет изготавливать мельчайшие компоненты с высокой точностью, чего крайне сложно добиться при использовании традиционной фотолитографии из-за дифракционного предела.

Маска состоит из материалов, поглощающих рентгеновское излучение, например из золота, сплавов тантала или вольфрама, нанесенных на прозрачную для рентгеновского излучения подложку, например, из карбида кремния или алмаза. Шаблон отображается на маску при помощи технологии прямой записи электронным лучом на фоторезист, который был нанесен традиционными для полупроводниковой индустрии методами. Подложка может быть дополнительно растянута для повышения точности нанесения рисунка. Для повышения разрешающей способности рентгеновоской литографии большое значение имеет использование так называемой "sweet spot" (особой точки, где излучение максимально яркое и однородное) и возможность печатать изображение, которое по размеру меньше маски [175; 176]. Мелкие структуры создают методом множественной экспозиции со сдвигами. Преимуществами данного подхода также является упрощение процесса изготовления маскок, увеличивается расстояние между маской и подложкой, увеличивается контрастность. Описанная технология позволяет работать с плотными рисунками с процессом 15 нм.

Рентгеновская литография приводит к появлению вторичных электронов, как и литография в глубоком ультрафиолете или же электронно-лучевая литография. В то время, как точность нанесения рисунка во многом определяется движением вторичных электронов, появившихся из-за эффекта Оже, первичные электроны возбуждают фоторезист на площади большей, чем покрывает сам рентгеновский луч. Это эффект приводит к умньшению контрастности изображения и к итоговой форме краев боковых сторон компонентов [177]. Различные аспекты применения рентгеновской литографии для процесса 30 нм также рассматриваются в работе [178].

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

Основным конкурентом рентгеновской литографии называют электроннолучевую литографию (англ. electron beam lithography, EBL). EBL основывается на использовании для нанесения рисунка луча электронов, которые сфокусированы и разогнаны до 20 кЭв. В качестве источников такого излучения используют эффекты термоэлектронной эмиссии, фотоэмиссии или автоэлектронной эмиссии. EBL используется для непосредственного изготовления ИС, изготовления масок для других видов литографии, например, рентгеновской, и для нанесения различных сложных шаблонов на подложку. Основные этапы электронно-лучевой литографии идентичны традиционной оптической. Обе технологии применяют различные фоторезисты и химикаты для закрепления засвеченной части подложки. Наиболее распространенным фоторезистом для электронной литографии является полиметилметакрилат (англ. polymethylmethacrylate, PMMA). PMMA разрушается до мономеров под действием электронов, которые потом удаляются "проявителем" метилизобутилкетоном (англ. methyl-isobutylketone, MIBK).

У электронно-лучевой литографии есть ряд преимуществ по сравнению с фотолитографией. Во-первых, высокая разрешающая способность порядка 20 нм. Во-вторых, с ее помощью можно отпечатывать сложные сгенерированные компьютером шаблоны напрямую на подложке. Электронно-лучевая литография — гибкая технология, которая способна работать с разнообразными материалами и практически с любыми требуемыми шаблонами. С другой стороны, это крайне

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

При использовании современной оптики электронно-лучевая литография может с легкостью работать с деталями рисунка размером в несколько нм. Разрешающая способность такой системы в основном ограничивается абберациями и пространственным зарядом. Также на разрешающую способность негативно влияют эффекты прямого рассеивания электронов в слое резиста (эффект расширения луча) и эффект возникновения вторичных электронов в слое резиста [179; 180].

В 2007 году была продемонстрирована технология двойного нанесения рисунка с использованием электронно-лучевой литографии при изготовлении ИС с полушагом затвора 15 нм [181]. При этом технология с полушагом затвора 30 нм так и не была освоена из-за возникновения вторичных электронов. Этот эффект компенсируется при использовании двойного шаблона за счет увеличенного расстояния между деталями рисунка. Прямое рассеивание электронов может быть скомпенсировано за счет использования электронного луча с более высокой энергией или за счет уменьшения толщины слоя резиста, при этом появления вторичных электронов избежать невозможно. Электроны низких энергий могут покрывать расстояния до нескольких нанометрах в слоях современных фоторезистов, таких как РММА. Такое поведение обуславливается тем, что основными механизмами торможения заряженных частиц таких энергий являются столкновения с фононами и поляронами [182]. Поляроны могут вызывать скачки на расстояния до 20 нм [183]. Стоит отметить, что расстояния, покрываемые вторичными электронами, не могут быть представлены в виде точных значений и описываются как вероятностные величины, вычисляемые методом Монте Карло для разных значений энергий, вплоть до менее 1 эВ. Такой подход необходим, т.к. максимум энергии вторичных электронов значительно меньше 10 эВ [184]. Таким образом, итоговое значение разрешающей способности электронно-лучевой литографии не описываются конкретными числовыми параметрами, как это происходит с традиионными оптическими системами [179]. Для того, чтобы результаты работы

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

В работе [185] демонстрируется, что электроны с энергией порядка 50-100 эВ могут проникнуть в промышленный фоторезист, например РРМА, на глубину более 10 нм, вызывая пробои в слое нижележащего диэлектрика.

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

Наименьшие детали рисунка, которые могут быть нанесены при помощи электонно-лучевой литографии как правило отдалены от остальной части изображения. В случае, когда два компонента рисунка находятся рядом, электроны во время экспозиции могут проникать в соседнии области, увеличивая само избражение и снижая его контрастность, т.е. разницу между самыми яркими и темными участками. Управлять параметрами вложенных или расположенных рядом деталей рисунка в таком случае затруднительно. Для большинства резистов такие проблемы возникают при работе с линиями шириной менее 25 нм. В работе [186] утверждается, что работа с линиями шириной менее 20 нм невозможна вовсе.

На практике, дальность распространения вторичных электронов довольно велика и может превышать 100 нм [187]. Чаще всего, однако, это расстояние не превышает 30 нм [188].

Эффекты близости также возникают в ситуации, когда электрон покидает поверхность резиста и проникает обратно на расстоянии десятков нанометров [189]

Эффекты близости, вызванные появлением вторичных электронов, могут быть скомпенсированы через решение обратной задачи: необходимо вычислить функцию экспозиции Е(х,у), которая обеспечивает требуемое

значение интенсивности излучения D(x,y) при учетет функции распределения вторичных электронов в точке PSF(x,y). Необходимо помнить, что ошибка в вычислении интенсивности излучения (в силу, к примеру, дробного шума) приводит к ошибкам компенсации эффектов близости.

Построение списка соединений

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

Альтернативным способом технологического отображения является автоматический синтез стандартных ячеек [192; 193] при необходимости (англ. library-free). Предполагается, что необходимые элементы могут быть сгенерированы при необходимости. Процедура технологического отображения сначала определяет, какие ячейки необходимы для реализации ИС, после чего они генерируются системами автоматического синтеза. Как уже упоминалось, большее число стандартных ячеек в библиотеке приводит к лучшем результатам синтеза ИС, что может быть обеспечено на этапе технологического отображения без использования библиотек. Применение такого подхода осложняется отсутствием точной информации о поведении элемента библиотеки в силу по причине трудоемкости процедуры характеризации. Метод технологического

отображения с использованием характеризованных библиотек остается основным, используемым в промышленности.

Задача размещения

В данной работе представлен алгоритм размещения транзисторов в стандартных ячейках. Подход основан на перечислении возможных частичных размещений с использованием весовой функции качества. Частичные размещения, упорядоченные в горизонтальном направлении, сортируются согласно значению весовой функции. Функция качества вычисляется динамически, и позволяет оценить возможность дальнейшей трассировки без построения полного размещения. Неперспективные и заведомо не трассируемые частичные решения удаляются из рассмотрения. Лучшие промежуточные решения используются для создания последующих размещений до тех пор, пока все транзисторы не размещены. Алгоритм показал свою применимость на широком классе стандартных ячеек и успешно используется в процессе промышленной разработки библиотек стандартных элементов [194].

В работе рассматривается метод автоматического синтеза топологий стандартных ячеек, основанный на алгоритме решения задачи SAT. Задача трассировки стандартных ячеек сводится к решению задачи выполнимости булевых формул. Описанный подход гарантирует, что результирующие ячейки будут минимальной площади и, вместе с тем, могут быть страссированы. В процессе размещения каждый КМОП транзистор рассматривается независимо, что позволяет достичь меньшей площади, по сравнению с подходом, основанном на рассмотрении P и N пар транзисторов. Результаты работы рассматриваемого метода сравниваются с результатми метода размещения на основе решения задачи целочисленного программирования и с результатами работы коммерческого программного комплекса. Экспериментальные результаты показывают, что алгоритм с использованием SAT может генерировать размещения минимальной площади значительно быстрее, чем метод на базе целочисленного программирования. 32 стандартных ячейки были размещены на 54% быстрее,

чем с использованием коммерческого решения. Площадь при этом увеличилась всего на 3% [50].

В работе [195] предлагается подход для автоматического размещения транзисторов внутри стандартной ячейки. В предлагаемом алгоритме множество транзисторов разделяется на цепочки с общей диффузией, после чего выполняется размещение таких цепочек. На следующем этапе выполняется попытка перемещения транзистора из одной цепочки в другую подходящую. такие перемещения выполняются с целью увеличения трассировочного ресурса для построения соединений как в рамках одной цепочки транзисторов, так и между несколькими.

Методы автоматической трассировки

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

Добавление вспомогательных переходных отверстий позволяет сократить выход бракованных ИС, проблемы в которых были вызваны нарушениями в переходных отверстиях. Однако, существующие подходы основаны на добавлении переходных отверстий в топологию уже после этапа детальной трассировки. В данной работе предлагается метод детальной трассировки, учитывающий возможность добавления вспомогательных переходных отверстий на последующих этапах. Задача трассировки решается при помощи волнового алгоритма [197] с дополнительными ограничениями на переходные отверстия. Затем задача сводится к проблеме поиска кратчайших путей с учетом ограничений

и решается методом Лагранжевых релаксаций. Экспериментальные результаты показывают, что предлагаемый подход позволяет строить топологии с большим числом вспомогательных переходных отверстий, по сравнению с методами. основанными на традиционном волновом алгоритме [198].

По мере сокращенния технологических норм и переходу к нанометровым тезнологиям, критические размеры компонентов ИС становятся меньше длины волны рабочего тела лазера в системе оптической литографии. Неизбежно возникающие при этом эффекты световой дифракции оказывают все большее негативное влияние на итоговый выход годных устройств в процессе производства. Одним из способов улучшения выхода является семейство методов коррекции эффектов оптической близости (англ. optical proximity correction, OPC), который компенсирует искажения, вызванные дифракцией. Однако, эта процедра ресурсозатратна и итоговый результат сильно зависит от качества исходной топологии. В данной работе рассматривается метод детальной трассировки на основе волнового алгоритма, который учитывает эффекты дифракции. Симметрия оптических систем позволяет эффективно рассчитывать дифракцию и сохранять результаты вычислений в таблицах. Целевая функция трассировщика минимизирует оптические искажения с использованием табличных значений. Сначала задача трассировки решается волновым алгоритмом с учетом ограничений, затем формулируется задача поиска кратчайших путей с учетом ограничений. Итоговая задача решается методом лагранжевых релаксаций [199].