Математическое и алгоритмическое обеспечение создания компиляторов предметно-­ориентированных языков для специализированных вычислительных машин тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат наук Советов Петр Николаевич

• Советов Петр Николаевич
• кандидат наук
• 2020

Оглавление диссертации кандидат наук Советов Петр Николаевич

Введение

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

специализированных вычислительных машин

1.1 Компиляторы предметно-ориентированных языков для специализированных вычислительных машин

1.2 Архитектура компилятора

1.3 Лексический и синтаксический разбор

1.4 Промежуточные представления

1.5 Оптимизирующие преобразования

1.6 Задний план компилятора

1.6.1 Машинно-зависимая оптимизация

1.6.2 Выбор команд

1.6.3 Планирование команд

1.6.4 Распределение регистров

1.6.5 Комбинированные подходы

1.7 Выводы

Глава 2. Методы и алгоритмы автоматизации создания заднего плана

компилятора

2.1 Модель заднего плана компилятора

2.2 Граф зависимостей по данным и состоянию памяти

2.3 Переписывание графа зависимостей

2.4 Метод синтеза правил машинно-зависимой оптимизации

2.4.1 Извлечение шаблонов из графа зависимостей

2.4.2 Синтез машинно-зависимой части правила с помощью SMT-решателя

2.5 Выбор команд с помощью SMT-решателя

2.5.1 Порождение всех вариантов выбора команд на основе

графа И/ИЛИ

2.5.2 Получение допустимого решения

Стр.

2.5.3 SMT-решатель в режиме бинарного поиска

2.6 Совместное планирование команд и распределение регистров с помощью SMT-решателя

2.6.1 Планирование команд

2.6.2 Распределение регистров

2.7 Выводы

Глава 3. Языки описания фаз компиляции

3.1 Язык описания синтаксического разбора

3.1.1 Формальное определение

3.1.2 Разбор операций с приоритетами

3.1.3 Примеры использования

3.2 Язык описания преобразований программ

3.2.1 Формальное определение

3.2.2 Примеры использования

3.3 Язык описания шаблонов команд

3.4 Выводы

Глава 4. Разработка компилятора для задач шифрования в области

Интернета вещей

4.1 Предварительные сведения

4.1.1 Низкоресурсная криптография для Интернета вещей

4.1.2 Предметно-ориентированный язык для задач криптографии

4.1.3 Специализированная вычислительная машина для симметричного шифрования

4.2 Проектирование архитектуры компилятора JC

4.3 Разработка фазы синтаксического разбора

4.4 Применение синтеза правил машинно-зависимой оптимизации

4.5 Разработка фазы выбора команд

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

4.7 Выводы

Заключение

Стр.

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

Список литературы

Список рисунков

Список таблиц

Приложение А. Результаты синтеза правил машинно-зависимой

оптимизации

Приложение Б. Акты о внедрении

Введение

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

Актуальность темы.

В настоящее время все активнее применяются специализированные вычислительные машины1 (СВМ), отличающиеся от процессоров общего назначения специализацией своей вычислительной структуры и предметно-ориентированным набором команд.

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

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

Программирование СВМ, как считают лауреаты премии Тьюринга, Д. Паттерсон и Дж. Хеннесси [1], должно осуществляться на высокоуровневых предметно-ориентированных языках (DSL), чтобы создание прикладных программ для СВМ было доступно не только системным программистам, но и экспертам в выбранной предметной области.

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

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

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

1В настоящей работе под специализированными вычислительными машинами подразумеваются спецпроцессоры.

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

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

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

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

Степень разработанности темы. Вопросами разработки оптимизирующих компиляторов занимались многие исследователи, среди которых: Ершов А.П., Касьянов В.Н., Лавров С.С., Поттосин И.В., Терехов А.Н., Турчин В.Ф., Backus J.W., Click C., Cocke J., Cooper K.D., Corporaal H., CytronR., Ellis J.R., Ferrante J., Frances A.J., Fraser C.W., Hack S., Kildall G.A., Leupers R., Proebsting, T.A., Wegman M., Zadeck F.K.

Исследованиями в области создания предметно-ориентированных языков занимались: Киселев О.Е., Fowler M., Hudak P., Hughes J., Rompf T., Schorre D.V., Visser E. и др.

Для задач автоматизации построения компиляторов могут быть использованы методы синтеза программ. Вопросы синтеза программ исследовались в работах Тыугу Э.Х. Bodik R., Gulwani S., Massalin H., Solar-Lezama A. и др.

Перспективным подходом к точному решению NP-полных задач, возникающих при создании генератора кода для специализированных вычислительных машин, является использование SMT-решателей, то есть программных библиотек для решения NP-полной задачи выполнимости формул в теориях. Вопросами применения SMT-решателей в составе компиляторов занимались: Buchwald S., Phothilimthana P.M., Regehr J. и др.

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

Объектом исследования является компилятор предметно-ориентированного языка для специализированной вычислительной машины.

Предмет исследования определен паспортом специальности 05.13.11, области исследований №1 («модели, методы и алгоритмы проектирования и анализа программ и программных систем, их эквивалентных преобразований, верификации и тестирования») и №2 («языки программирования и системы программирования, семантика программ»), а также перечнем задач, решаемых в диссертации.

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

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

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

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

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

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

5. Разработать методику совместного планирования команд и распределения регистров.

6. На основе разработанного математического и алгоритмического обеспечения реализовать компилятор для задач низкоресурсной криптографии из области Интернета вещей.

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

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

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

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

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

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

Результаты диссертационного исследования применены при разработке компилятора предметно-ориентированного языка для задач программно-конфигурируемого радио в ООО «Системы технического зрения». Целевой код порождается компилятором для софт-процессора на основе крупноблочной ре-конфигурируемой матрицы.

Результаты диссертационного исследования использовались в учебном процессе РТУ МИРЭА в ряде дисциплин: «Анализ сложности алгоритмов», «Структуры и алгоритмы обработки данных» и «Конфигурационное управление».

Основные результаты и научные положения, выносимые на защиту:

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

2. Метод и алгоритмическое обеспечение автоматического синтеза правил машинно-зависимой оптимизации с использованием анализа набора программ из выбранной предметной области. Алгоритмическое обеспечение включает в себя алгоритм извлечения шаблонов и алгоритм синтеза линейной программы для СВМ по спецификации.

3. Методика выбора команд на основе сведения к задаче SMT и с декларативным представлением шаблонов набора команд в виде графа И/ИЛИ. Графовое представление позволяет компактно описать шаблоны машинных команд. Свойство префиксности и наличие общих узлов в графе позволяют избежать сопоставления с заведомо неподходящими фрагментами шаблонов команд.

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

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

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

- синтезированные правила позволили сократить число выбранных команд для теста Магма на 28% и для теста AES на 30% по сравнению с набором правил, сформированным вручную;

- использование графа И/ИЛИ позволило заменить 501555 шаблонов команд представлением, близким к структуре АЛУ СВМ и занимающим 54 строки на разработанном языке описания шаблонов команд;

- анализ графа зависимостей программы в фазе совместного планирования команд и распределения регистров дал возможность сократить число сформированных SMT-ограничений в 3.3-27.6 раз;

- сокращение объема целевого кода с помощью компилятора JC, по сравнению с GCC/RISC-V, составило: 1.5-3.6 раз для базового варианта СВМ и 2.2-5.8 раз для варианта VLIW.

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

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

Апробация работы. Основные положения и результаты работы докладывались и обсуждались на конференциях:

- международная научно-практическая конференция «Высокопроизводительные вычислительные системы и технологии в научных исследованиях, автоматизации управления и производства» 2017, 2019 гг.;

- профессиональная конференция для Python-разработчиков Moscow Python Conf++ 2018;

- XXII Научная конференция по радиофизике, посвященная 100-летию Нижегородской радиолаборатории, 2018;

- международная научная конференция «ИТ-Стандарт» 2018, 2019 гг.;

- научно-техническая конференция студентов и аспирантов РТУ МИРЭА 2018, 2019, 2020 гг.

По теме диссертации опубликовано 7 научных работ, из них 3 — в научных рецензируемых изданиях, рекомендуемых ВАК, в том числе 2 публикации в журналах, входящих в перечень ВАК по специальности 05.13.11.

Получено 3 патента на изобретение и 2 свидетельства о государственной регистрации программы.

Объем и структура работы. Диссертация состоит из введения, 4 глав, заключения и 2 приложений. Полный объем диссертации составляет 126 страниц, включая 23 рисунка и 10 таблиц. Список литературы содержит 112 наименований.

Глава 1. Анализ современных методов разработки компиляторов для специализированных вычислительных машин

1.1 Компиляторы предметно-ориентированных языков для специализированных вычислительных машин

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

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

В таблице 1 приведены примеры компиляторов для СВМ. Эти компиляторы имеют дело не с языками общего назначения, а с DSL [3], каждый из которых специально разработан для заданной узкой предметной области.

Таблица 1 — Примеры компиляторов для СВМ

СВМ Предметная область DSL Компилятор

Google Pixel Visual Core Обработка изображений Halide Halide [4]

Google TPU Машинное обучение TensorFlow XLA [5]

Barefoot Tofino Программно определяемые сети P4 P4c [6]

GreenArrays GA144 Системы управления с низким энергопотреблением Chlorophyll Chlorophyll [7]

К положительным сторонам использования DSL для программирования СВМ можно отнести:

- использование предметно-ориентированной нотации, а не низкоуровневых pragma-директив или intrinsic-функций;

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

Примером ограничений, введенных в DSL, является язык P4 [8], предназначенный для обработки сетевых пакетов, в котором отсутствуют указатели и циклы.

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

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

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

2. Подход codesign [9; 10]. Прототипирование компилятора в процессе проектирования СВМ. Этот подход позволяет находить компромиссные решения, касающиеся архитектуры СВМ, качества порождаемого целевого кода и выразительности DSL.

Подход codesign становится все актуальнее с ростом числа СВМ, которые спроектированы специально для использования в конкретных системах на кристалле.

При этом современные средства разработки перенацеливаемых компиляторов, такие, как LLVM и GCC, обладают рядом недостатков:

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

- модуль заднего плана компилятора ориентирован на порождение кода для популярных процессорных архитектур CISC и RISC, а не для СВМ;

- алгоритмы порождения кода являются эвристическими, не гарантирующими точного решения задач компиляции;

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

В этой связи имеется необходимость в специальном исследовании методов быстрой разработки DSL-компиляторов для СВМ.

1.2 Архитектура компилятора

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

В архитектуре компилятора (рис. 1.1) можно выделить:

1. Передний план, преобразующий входной текст на DSL во внутреннее представление.

2. Оптимизирующие преобразования, параметры которых могут быть машинно-зависимыми.

3. Машинно-зависимый задний план для порождения целевого кода СВМ.

Для быстрой разработки переднего плана DSL-компилятора существуют

языковые верстаки (language workbench) [11], наиболее развитыми из которых являются Spoofax [12; 13] и MPS [14]. Это большие программные системы, предполагающие использование языка Java, что может затруднить их интеграцию с проектом компилятора, реализованном на другом языке. Кроме того, эти системы осуществляют преобразования программ на уровне AST, а в модуле заднего плана оптимизирующего компилятора используется графовое представление программы (раздел 1.4).

1.3 Лексический и синтаксический разбор

К популярным генераторам синтаксических анализаторов относятся Flex/Bison [15], поддерживающий разбор методом LALR, а также ANTLR [16], основанный на методе LL(*). Эти инструменты позволяют описать грамматику DSL декларативно, в БНФ-подобной нотации.

Исходный текст

Передний план

"Г" IR

I

IR

Л

Целевой код

Рисунок 1.1 — Архитектура оптимизирующего компилятора

Для реализации сложных вариантов синтаксического разбора DSL могут потребоваться следующие возможности, которых Flex/Bison и ANTLR не обеспечивают:

- объединенный лексико-синтаксический разбор (scannerless parsing);

- поддержка вложенных грамматик [17];

- поддержка контекстно-зависимых грамматик.

Приведенными возможностями обладает, в частности, инструмент Ohm [18], основанный на формализме PEG, а также инструмент SDF3 [19], в котором реализован метод SGLR.

Формализм PEG [20] отличается простотой и гибкостью построения синтаксического разбора. Для PEG характерны: представление грамматики на основе БНФ и регулярных выражений, упорядоченный выбор альтернатив, синтаксический разбор методом рекурсивного спуска с откатом.

В PEG отсутствуют встроенные средства поддержки левосторонней рекурсии. Наличие левосторонней рекурсии усложняет, в первую очередь, разбор операций с приоритетами. Предложенные способы введения поддержки левосторонней рекурсии в PEG отличаются высокими накладными расходами [21; 22].

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

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

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

Преодоление этих недостатков возможно с использованием библиотеки комбинаторов синтаксического разбора [24], например, библиотеки Parsec [25].

Библиотека комбинаторов [26] — один из способов создания eDSL [27] на основе поверхностного встраивания (shallow embedding) [28]. Комбинаторы определяются с помощью функций высшего порядка и лексических замыканий. Библиотека комбинаторов содержит свободно компонуемые конструкции DSL с семантикой, отличной от хост-языка.

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

1.4 Промежуточные представления

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

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

Компиляторы LLVM и GCC в качестве основного промежуточного представления (IR) используют управляющий граф в форме SSA, узлами которого являются линейные участки — списки операций. В таком IR операции полностью упорядочены, что препятствует оптимизациям кода для СВМ: перемещению команд и их распараллеливанию.

Графовые IR отличаются использованием ребер зависимостей по данным и управлению для связи между узлами-операциями. Графовое IR может выступать в качестве единого представления программы во всех фазах компиляции. К его достоинствам относятся: явно заданная в графовой форме информация об элементах программы и использование алгоритмов на графах для анализа и преобразований программ. Примеры графовых IR: Р-схемы [30], PDG [31], PDW [32], Sea of Nodes [33], Firm [34], Graal IR [35], Thorin [36], VSDG [37], Pegasus [38], RVSDG [39].

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

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

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

В компиляторе libFirm [34] реализована возможность распараллеливания обращений к памяти. Получение зависимости по управлению от операции обращения к памяти осуществляется с помощью узла Proj. Для синхронизации параллельных обращений к памяти используется узел Sync.

1.5 Оптимизирующие преобразования

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

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

В компиляторах LLVM и libFirm правила локальной оптимизации представлены в виде объемной и трудно поддерживаемой императивной реализации на C/C++. В компиляторе языка Go локальные оптимизации описаны декларативно — набором правил на специальном DSL [41].

Ручное создание правил, даже если правила представлены на выразительном DSL — рутинный, подверженный ошибкам процесс. По этой причине предложены методы автоматического синтеза правил локальной оптимизации [42].

В системах Optgen [43] и Souper [44] синтез правой части правила по шаблону из левой части осуществляется с использованием SMT-решателя — программной библиотеки для решения NP-полной задачи выполнимости формул в теориях.

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

Многие высокоуровневые преобразования, в том числе предметно-ориентированные, могут быть представлены в виде преобразований дерева абстрактного синтаксиса (AST).

В языке преобразований программ Stratego [45; 46] работа с AST реализована с помощью системы переписывания термов. Особенностью Stratego является использование композиций из стратегий [47], предназначенных для управления порядком применения правил и определения различных вариантов обхода AST-узлов. Благодаря этим возможностям преобразования программ в Stratego могут

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

В системе Nanopass [48] фазы преобразований программ реализованы с помощью двух языков: 1) язык define-language для определения формы AST в фазе преобразования, 2) язык define-pass для преобразования программ с автоматизацией обхода AST. Система Nanopass в меньшей степени использует декларативный подход, чем Stratego. При этом Nanopass является программной библиотекой на языке Scheme, что упрощает ее расширяемость и интеграцию с проектом компилятора на Scheme.

Для внутрипроцедурной и межпроцедурной оптимизации кода могут быть применены готовые модули, среди которых LLVM, libFirm и MLIR [49]. Эти модули используют представление в форме SSA в качестве входного и выходного IR. При этом контроль над применяемыми оптимизирующими преобразованиями в рассматриваемых инструментах осуществляется с помощью внешних опций и является недостаточно детальным. Особую проблему это представляет при использовании автонастройки компилятора [50; 51], важной для адаптации компилятора к новой СВМ.

Список литературы диссертационного исследования кандидат наук Советов Петр Николаевич, 2020 год

Список литературы

1. Hennessy, J. L. A new golden age for computer architecture [Текст] / J. L. Hennessy, D. A. Patterson // Communications of the ACM. — 2019. — Янв. — Т. 62, № 2. — С. 48—60.

2. Основные тенденции развития архитектур специализированных многоядерных процессоров [Текст] / Г. С. Елизаров [и др.] // Известия вузов. ЭЛЕКТРОНИКА. — 2018. — Т. 23, № 2. — С. 161.

3. Mernik, M. When and how to develop domain-specific languages [Текст] / M. Mernik, J. Heering, A. M. Sloane // ACM computing surveys (CSUR). — 2005. — Т. 37, № 4. — С. 316-344.

4. Halide: a language and compiler for optimizing parallelism, locality, and recomputation in image processing pipelines [Текст] / J. Ragan-Kelley [и др.] // Acm Sigplan Notices. — 2013. — Т. 48, № 6. — С. 519—530.

5. Kaufman, S. Learned TPU Cost Model for XLA Tensor Programs [Текст] / S. Kaufman, P. M. Phothilimthana, M. Burrows // Proceedings of the Workshop on ML for Systems at NeurIPS 2019. — 2019. — С. 1—6.

6. Stubbe, H. P4 compiler & interpreter: A survey [Текст] / H. Stubbe // Future Internet (FI) and Innovative Internet Technologies and Mobile Communication (IITM). — 2017. — Т. 47.

7. Chlorophyll: Synthesis-aided compiler for low-power spatial architectures [Текст] / P. M. Phothilimthana [и др.] // ACM SIGPLAN Notices. — 2014. — Т. 49, № 6. - С. 396-407.

8. P4: Programming protocol-independent packet processors [Текст] / P. Bosshart [и др.] // ACM SIGCOMM Computer Communication Review. — 2014. — Т. 44, №3. —С. 87—95.

9. Sampson, A. Hardware-software co-design: not just a cliché [Текст] / A. Sampson, J. Bornholt, L. Ceze // 1st Summit on Advances in Programming Languages (SNAPL 2015). — Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. 2015.

10. Советов, П. Н. Автоматизация проектирования специализированных процессоров с использованием подхода compiler-in-the-loop [Текст] / П. Н. Советов // Труды XXII научной конференции по радиофизике, посвященной 100-летию Нижегородской радиолаборатории. — 2018. — С. 530—532.

11. Fowler, M. Language workbenches: The killer-app for domain specific languages [Текст] / M. Fowler. — 2005.

12. Kats, L. C. The spoofax language workbench: rules for declarative specification of languages and IDEs [Текст] / L. C. Kats, E. Visser // Proceedings of the ACM international conference on Object oriented programming systems languages and applications. — 2010. — С. 444—463.

13. Visser, E. Understanding software through linguistic abstraction [Текст] / E. Visser // Science of Computer Programming. — 2015. — Янв. — Т. 97. — С. 11-16.-URL: https://doi.org/10.10167j.scico.2013.12.001.

14. Voelter, M. Language modularity with the MPS language workbench [Текст] / M. Voelter, V. Pech // 2012 34th International Conference on Software Engineering (ICSE). — IEEE, 06.2012.

15. Levine, J.Flex & Bison: Text Processing Tools [Текст] / J. Levine. — "O'Reilly Media, Inc.", 2009.

16. Parr, T. LL (*) the foundation of the ANTLR parser generator [Текст] / T. Parr, K. Fisher // ACM Sigplan Notices. — 2011. — Т. 46, № 6. — С. 425—436.

17. Kats, L. C. Pure and declarative syntax definition: paradise lost and regained [Текст] / L. C. Kats, E. Visser, G. Wachsmuth // Proceedings of the ACM international conference on Object oriented programming systems languages and applications. — 2010. — С. 918—932.

18. Warth, A. Modular semantic actions [Текст] / A. Warth, P. Dubroy, T. Garnock-Jones//ACM SIGPLAN Notices. — 2017. — Май. — Т. 52, №2. — С. 108—119.

19. Souza, L. E. A. de. Multi-Purpose Syntax Definition with SDF3 [Текст] / L. E. A. de Souza, E. Visser //. — 2020.

20. Ford, B. Parsing expression grammars: a recognition-based syntactic foundation [Текст] / B. Ford // Proceedings of the 31st ACM SIGPLAN-SIGACT symposium on Principles of programming languages. — 2004. — С. 111—122.

21. Warth, A. Packrat parsers can support left recursion [Текст] / A. Warth, J. R. Douglass, T. Millstein // Proceedings of the 2008 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation. — 2008. — С. 103-110.

22. Tratt, L. Direct left-recursive parsing expression grammars [Текст] / L. Tratt // School of Engineering and Information Sciences, Middlesex University. — 2010.

23. Pratt, V. R. Top down operator precedence [Текст] / V. R. Pratt // Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages - POPL '73. — ACM Press, 1973.

24. Hutton, G. Higher-order functions for parsing [Текст] / G. Hutton // Journal of functional programming. — 1992. — Т. 2, № 3. — С. 323—343.

25. Leijen, D. Parsec: Direct style monadic parser combinators for the real world [Текст] / D. Leijen, E. Meijer. — 2001.

26. Hughes, /.The design of a pretty-printing library [Текст] / J. Hughes // International School on Advanced Functional Programming. — Springer. 1995. —С. 53-96.

27. Hudak, P. Building domain-specific embedded languages [Текст] / P. Hudak // Acm computing surveys (csur). — 1996. — Т. 28, 4es. — 196—es.

28. Svenningsson, J. Combining deep and shallow embedding for EDSL [Текст] / J. Svenningsson, E. Axelsson // International symposium on trends in functional programming. — Springer. 2012. — С. 21—36.

29. Simple and efficient construction of static single assignment form [Текст] / M. Braun [и др.] // International Conference on Compiler Construction. — Springer 2013. - С. 102-122.

30. Ершов, А. Об операторных схемах над общей и распределенной памятью [Текст] / А. Ершов // Кибернетика. — 1968. — № 4. — С. 63—71.

31. Ferrante, /.The program dependence graph and its use in optimization [Текст] / J. Ferrante, K. J. Ottenstein, J. D. Warren // ACM Transactions on Programming Languages and Systems (TOPLAS). — 1987. — Июль. — Т. 9, № 3. — С. 319-349.

32. Ottenstein, K. J. The program dependence web: a representation supporting control-, data-, and demand-driven interpretation of imperative languages [Текст] / K. J. Ottenstein, R. A. Ballance, A. B. MacCabe // Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation. — 1990. — С. 257—271.

33. Click, C. Combining analyses, combining optimizations [Текст] / C. Click, K. D. Cooper // ACM Transactions on Programming Languages and Systems (TOPLAS). - 1995. - Т. 17, № 2. - С. 181-196.

34. Braun, M. Firm-a graph-based intermediate representation [Текст] / M. Braun, S. Buchwald, A. Zwinkau. — 2011.

35. Graal IR: An Extensible Declarative Intermediate Representation [Текст] / G. Duboscq [и др.] // Proceedings of the Asia-Pacific Programming Languages and Compilers Workshop. — 2013.

36. Leißa, R. A graph-based higher-order intermediate representation [Текст] / R. Leißa, M. Köster, S. Hack // 2015 IEEE/ACM International Symposium on Code Generation and Optimization (CGO). — IEEE. 2015. — С. 202—212.

37. Lawrence, A. C. Optimizing compilation with the value state dependence graph [Текст] : тех. отч. / A. C. Lawrence ; University of Cambridge, Computer Laboratory. — 2007.

38. Budiu, M. Pegasus: An efficient intermediate representation [Текст] : тех. отч. / M. Budiu, S. C. Goldstein ; CARNEGIE-MELLON UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE. — 2002.

39. RVSDG: An Intermediate Representation for Optimizing Compilers [Текст] / N. Reissmann [и др.] // arXiv preprint arXiv:1912.05036. — 2019.

40. The LLVM Target-Independent Code Generator [Электронный ресурс]. — URL: https://llvm.org/docs/CodeGenerator.html (дата обр. 20.08.2020).

41. Generic.rules [Электронный ресурс]. — URL: https: //github. com/golang/ go /blob/ master / src/ cmd/ compile/ internal / ssa/ gen/ generic. rules (дата обр. 20.08.2020).

42. Советов, П. Н. Синтез линейных программ для стековой машины [Текст] / П. Н. Советов // Высокопроизводительные вычислительные системы и технологии. — 2019. — Т. 3, № 1. — С. 17—22.

43. Buchwald, S. Optgen: A generator for local optimizations [Текст] / S. Buchwald // International Conference on Compiler Construction. — Springer. 2015. —С. 171-189.

44. Souper: A Synthesizing Superoptimizer [Текст] / R. Sasnauskas [и др.] // CoRR. -2017. - Т. abs/1711.04422.

45. Program transformation with scoped dynamic rewrite rules [Текст] / M. Bravenboer [и др.] // Fundamenta Informaticae. — 2006. — Т. 69, № 1/2. — С. 123-178.

46. Bravenboer, M. Rewriting Strategies for Instruction Selection [Текст] / M. Bravenboer, E. Visser // Rewriting Techniques and Applications (RTA'02). Т. 2378 / под ред. S. Tison. — Copenhagen, Denmark : Springer-Verlag, 07.2002. — С. 237—251. — (Lecture Notes in Computer Science).

47. Visser, E. A survey of rewriting strategies in program transformation systems [Текст] / E. Visser // Electronic Notes in Theoretical Computer Science. — 2001. —Т. 57, №2.

48. Keep, A. W. A nanopass framework for commercial compiler development [Текст] / A. W. Keep, R. K. Dybvig // Proceedings of the 18th ACM SIGPLAN international conference on Functional programming. — 2013. — С. 343—350.

49. MLIR: A Compiler Infrastructure for the End of Moore's Law [Текст] / C. Lattner [и др.] // arXiv preprint arXiv:2002.11054. — 2020.

50. Opentuner: An extensible framework for program autotuning [Текст] / J. Ansel [и др.] // Proceedings of the 23rd international conference on Parallel architectures and compilation. — 2014. — С. 303—316.

51. SPIRAL: Extreme Performance Portability [Текст] / F. Franchetti [и др.] // Proceedings of the IEEE. — 2018.— Нояб. — Т. 106, № 11. — С. 1935—1968.— URL: https://doi.org/10.1109/jproc.2018.2873289.

52. Leupers, R. Compiler design issues for embedded processors [Текст] / R. Leupers // IEEE Design & Test of Computers. — 2002. — Т. 19, № 4. — С. 51-58.

53. Koes, D. R Near-optimal instruction selection on dags [Текст] / D. R. Koes, S. C. Goldstein // Proceedings of the sixth annual IEEE/ACM international symposium on Code generation and optimization - CGO '08. — ACM Press, 2008.

54. Hennessy, J. L. Postpass code optimization of pipeline constraints [Текст] / J. L. Hennessy, T. Gross // ACM Transactions on Programming Languages and Systems (TOPLAS). - 1983. - Т. 5, № 3. - С. 422-448.

55. Register allocation via coloring [Текст] / G. J. Chaitin [и др.] // Computer languages. - 1981. - Т. 6, № 1. - С. 47-57.

56. Program synthesis [Текст] / S. Gulwani, O. Polozov, R. Singh [и др.] // Foundations and Trends® in Programming Languages. — 2017. — Т. 4, № 1/ 2. — С. 1-119.

57. Massalin, H. Superoptimizer: a look at the smallest program [Текст] / H. Massalin // ACM SIGARCH Computer Architecture News. — 1987. — Т. 15, № 5. — С. 122-126.

58. Srinivasan, V. Synthesis of machine code from semantics [Текст] / V. Srinivasan, T. Reps // Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation. — 2015. — С. 596—607.

59. Buchwald, S. Synthesizing an instruction selection rule library from semantic specifications [Текст] / S. Buchwald, A. Fried, S. Hack//Proceedings of the 2018 International Symposium on Code Generation and Optimization. — 2018. — С. 300-313.

60. Synthesis of loop-free programs [Текст] / S. Gulwani [и др.] // ACM SIGPLAN Notices. — 2011. — Июнь. — Т. 46, № 6. — С. 62.

61. Autogenerating fast packet-processing code using program synthesis [Текст] / X. Gao [и др.] // Proceedings of the 18th ACM Workshop on Hot Topics in Networks. — 2019. — С. 150—160.

62. Lezama, A. S. Program synthesis by sketching [Текст] : дис. ... канд. / Lezama A Solar. — PhD thesis, EECS Department, University of California, Berkeley, 2008.

63. Blindell, G. H. Instruction selection: principles, methods, and applications [Текст] / G. H. Blindell. — Springer, 2016.

64. TableGen [Электронный ресурс]. — URL: https://llvm.org/docs/TableGen/ (дата обр. 20.08.2020).

65. Fraser, C. W. BURG: fast optimal instruction selection and tree parsing [Текст] / C. W. Fraser, R. R. Henry, T. A. Proebsting // ACM Sigplan Notices. — 1992. — Т. 27, № 4. — С. 68—76.

66. Buchwald, S. Instruction selection by graph transformation [Текст] / S. Buchwald, A. Zwinkau // Proceedings of the 2010 international conference on Compilers, architectures and synthesis for embedded systems. — 2010. — С. 31-40.

67. Complete and practical universal instruction selection [Текст] / G. H. Blindell [и др.] // ACM Transactions on Embedded Computing Systems (TECS). — 2017. —Т. 16, 5s. — С. 1-18.

68. Cooper, K. D. An experimental evaluation of list scheduling [Текст] / K. D. Cooper, P. J. Schielke, D. Subramanian // TR98. — 1998. — Т. 326.

69. Declarative, SAT-solver-based Scheduling for an Embedded Architecture with a Flexible Datapath [Текст] / N. Frolov [и др.]. — 2011.

70. Wilken, K. Optimal instruction scheduling using integer programming [Текст] / K. Wilken, J. Liu, M. Heffernan // Acm sigplan notices. — 2000. — Т. 35, № 5. — С. 121-133.

71. Malik, A. M. Optimal basic block instruction scheduling for multiple-issue processors using constraint programming [Текст] / A. M. Malik, J. McInnes, P. Van Beek // International journal on artificial intelligence tools. — 2008. — Т. 17, № 01. — С. 37—54.

72. Ершов, А. П. Сведение задачи распределения памяти при составлении программ к задаче раскраски вершин графов [Текст] / А. П. Ершов // Доклады Академии наук. Т. 142. — Российская академия наук. 1962. — С. 785—787.

73. Лавров, С. С. Об экономии памяти в замкнутых операторных схемах [Текст] / С. С. Лавров // Журнал вычислительной математики и математической физики. — 1961. — Т. 1, № 4. — С. 687—701.

74. George, L. Iterated register coalescing [Текст] / L. George, A. W. Appel // ACM Transactions on Programming Languages and Systems (TOPLAS). — 1996. — Т. 18, № 3. — С. 300-324.

75. Bouchez, F. Allocation de registres et vidage en mémoire [Текст] / F. Bouchez // Master's thesis, ENS Lyon. — 2005.

76. Hack, S. Register allocation for programs in SSA-form [Текст] / S. Hack, D. Grund, G. Goos // International Conference on Compiler Construction. — Springer 2006. - С. 247-262.

77. Pereira, F. M. Q. A survey on register allocation [Текст] : тех. отч. / F. M. Q. Pereira ; Technical report, University of California, United States of America. — 2008.

78. Quintao Pereira, F. M. Register allocation by puzzle solving [Текст] / F. M. Quintao Pereira, J. Palsberg // Proceedings of the 29th ACM SIGPLAN Conference on Programming Language Design and Implementation. — 2008. — С. 216-226.

79. Fu, C. A faster optimal register allocator [Текст] / C. Fu, K. Wilken // 35th Annual IEEE/ACM International Symposium on Microarchitecture, 2002.(MICR0-35). Proceedings. — IEEE. 2002. — С. 245—256.

80. Koes, D. R. A global progressive register allocator [Текст] / D. R. Koes, S. C. Goldstein // ACM SIGPLAN Notices. - 2006. - Т. 41, № 6. -С. 204-215.

81. Buchwald, S. SSA-based register allocation with PBQP [Текст] / S. Buchwald, A. Zwinkau, T. Bersch // International Conference on Compiler Construction. — Springer 2011.-С. 42-61.

82. Вьюкова, Н. И. Генерация кода методом точного совместного решения задач выбора и планирования команд [Текст] / Н. И. Вьюкова, В. А. Галатенко, С. В. Самборский // Программная инженерия. — 2014. — № 6. — С. 8—15.

83. Иванов, Д. С. Распределение регистров при планировании инструкций для архитектуры «Эльбрус-90микро» [Текст] / Д. С. Иванов // Вопросы рад-поэлектропикп. Серия Электронная Вычислительная техника. — 2011. — №3. —С. 70—82.

84. Chang, C.-M. Using integer linear programming for instruction scheduling and register allocation in multi-issue processors [Текст] / C.-M. Chang, C.-M. Chen, C.-T. King // Computers & Mathematics with Applications. — 1997. — Нояб. — Т. 34, №9.-С. 1-14.-URL: https://doi.org/10.1016/s0898-1221(97)00184-3.

85. Combinatorial register allocation and instruction scheduling [Текст] / R. C. Lozano [и др.] // ACM Transactions on Programming Languages and Systems (TOPLAS). - 2019. - Т. 41, № 3. - С. 1-53.

86. Kjellin, M. Adapting a constraint-based compiler tool to a new VLIW architecture [Текст] : дис. ... канд. / Kjellin Martin. — Master's thesis, Uppsala University, Sweden, 2018. Ongoing work, 2019.

87. Eriksson, M. Integrated Code Generation for Loops [Текст] / M. Eriksson, C. Kessler // ACM Transactions on Embedded Computing Systems. — 2012. — Июнь. — Т. 11S, № 1. — С. 1—24. — URL: https://doi.org/10.1145/2180887. 2180896.

88. Roselli, S. F. SMT solvers for job-shop scheduling problems: Models comparison and performance evaluation [Текст] / S. F. Roselli, K. Bengtsson, K. Akesson //2018 IEEE 14th International Conference on Automation Science and Engineering (CASE). — IEEE. 2018. — С. 547—552.

89. Hoffmann, C. M. Pattern matching in trees [Текст] / C. M. Hoffmann, M. J. O'Donnell // Journal of the ACM (JACM). — 1982. — Т. 29, № 1. — С. 68-95.

90. Algorithms for generating ordered solutions for explicit AND/OR structures [Текст] / P. Ghosh [и др.] // Journal of Artificial Intelligence Research. — 2012. -Т.44. — С. 275-333.

91. Santos Souza, U. dos. Revisiting the complexity of and/or graph solution [Текст] / U. dos Santos Souza, F. Protti, M. D. da Silva // Journal of Computer and System Sciences. - 2013. - Т. 79, № 7. - С. 1156-1163.

92. Bj0rner, N. vZ — an optimizing SMT solver [Текст] / N. Bj0rner, A.-D. Phan, L. Fleckenstein // International Conference on Tools and Algorithms for the Construction and Analysis of Systems. — Springer. 2015. — С. 194—199.

93. Sebastiani, R. Optimization in SMT with LA(Q) Cost Functions [Текст] / R. Sebastiani, S. Tomasi // International Joint Conference on Automated Reasoning. — Springer. 2012. — С. 484—498.

94. Советов, П. Н. Библиотека универсального автоформатирования кода для проблемно-ориентированных языков [Текст] / П. Н. Советов // ИТ-Стандарт. - 2018. - № 3. - С. 1-7.

95. Советов, П. Н. Разработка многопоточного софт-процессора со стековой архитектурой на основе совместной оптимизации программной модели и системной архитектуры [Текст] / П. Н. Советов, И. Е. Тарасов // Многоядерные процессоры, параллельное программирование, ПЛИС, системы обработки сигналов. — 2017. — № 7. — С. 8—19.

96. Автоматизация проектирования многопроцессорной системы на базе ПЛИС для управления во встраиваемых приложениях [Текст] / И. Е. Тарасов [и др.] // Экономика и менеджмент систем управления. — 2017. — Т. 25, №3.1. —С. 179—185.

97. Ford, B. Packrat parsing: simple, powerful, lazy, linear time, functional pearl [Текст] /B. Ford// ACM SIGPLANNotices. — 2002. — Т. 37, № 9. — С. 36—47.

98. Becket, R. DCGs + Memoing = Packrat Parsing but Is It Worth It? [Текст] / R. Becket, Z. Somogyi // International Symposium on Practical Aspects of Declarative Languages. — 2008. — С. 182—196.

99. Findler, R. B. Redex: Practical semantics engineering [Текст] / R. B. Findler, C. Klein, B. Fetscher. — 2014.

100. Biryukov, A. State of the art in lightweight symmetric cryptography [Текст] /

A. Biryukov, L. P. Perrin. — 2017.

101. ГОСТ 34.12-2018. Информационная технология (ИТ). Криптографическая защита информации. Блочные шифры (с Поправкой) [Текст] // М.: Стан-дартинформ. — 2018. — С. 18.

102. Browning, S. Cryptol, a DSL for cryptographic algorithms [Текст] / S. Browning // ACM SIGPLAN Commercial Users of Functional Programming on-CUFP '10.—ACM Press, 2010.

103. Everest: Towards a verified, drop-in replacement of HTTPS [Текст] / K. Bhargavan [и др.] // 2nd Summit on Advances in Programming Languages (SNAPL 2017). — Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. 2017.

104. Vale: Verifying high-performance cryptographic assembly code [Текст] /

B. Bond [и др.] // 26th {USENIX} Security Symposium ({USENIX} Security 17).-2017.-С. 917-934.

105. Jasmin: High-assurance and high-speed cryptography [Текст] / J. B. Almeida [и др.] // Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. — 2017. — С. 1807—1823.

106. Mercadier, D. Usuba: high-throughput and constant-time ciphers, by construction [Текст] / D. Mercadier, P.-E. Dagand // Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation. — 2019. — С. 157—173.

107. FaCT: a DSL for timing-sensitive computation [Текст] / S. Cauligi [и др.] // Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation - PLDI 2019. — ACM Press, 2019.

108. Елизаров, С. Г. Патент на изобретение № 2681702, Российская Федерация, МПК G06F 15/76. Арифметико-логическое устройство и способ преобразования данных с использованием такого устройства [Текст] / С. Г. Елизаров, Д. С. Марков, П. Н. Советов // Бюл. № 8. — 2019.

109. Советов, П. Н. Итеративный подход с использованием компилятора для синтеза и моделирования проблемно-ориентированного набора команд [Текст] / П. Н. Советов // International Journal of Open Information Technologies. — 2019. — Т. 7, № 10.

110. Hoder, K. ^Z-an efficient engine for fixed points with constraints [Текст] / K. Hoder, N. Bj0rner, L. De Moura // International Conference on Computer Aided Verification. — Springer. 2011. — С. 457—462.

111. De Moura, L. Z3: An efficient SMT solver [Текст] / L. De Moura, N. Bj0rner // International conference on Tools and Algorithms for the Construction and Analysis of Systems. — Springer. 2008. — С. 337—340.

112. Кручинин, В. В. Метод кодирования информационных объектов на основе деревьев И/ИЛИ [Текст] / В. В. Кручинин, Б. А. Люкшин // Доклады Томского государственного университета систем управления и радиоэлектроники. — 2010. — 1—1 (21).

Список рисунков

1.1 Архитектура оптимизирующего компилятора............... 15

1.2 Задний план оптимизирующего компилятора...............20

2.1 Модель заднего плана компилятора .................... 28

2.2 Два варианта организации П-зависимостей линейного участка программы .................................. 31

2.3 Метод синтеза правил машинно-зависимой оптимизации ........ 37

2.4 Синтез программы методом CEGIS....................42

2.5 Шаблоны команд упрощенной модели СВМ в виде графа И/ИЛИ

(узлы ИЛИ — серые круги) ......................... 48

3.1 Абстрактный синтаксис языка Parse....................60

3.2 Операционная семантика языка Parse...................62

3.3 Пример синтаксического разбора программы на языке ImpCore .... 67

3.4 Абстрактный синтаксис языка Rewrite ................... 69

3.5 Операционная семантика языка Rewrite .................. 71

3.6 Пример трансляции программы на языке ImpCore ............ 77

4.1 АЛУ СВМ [108]...............................84

4.2 Структурная схема компилятора JC .................... 85

4.3 Пример синтаксического разбора программы на языке Jasmin ..... 89

4.4 Тестирование вариантов синтаксического разбора. Показанное время разбора нормализовано относительно раздельного разбора ....... 90

4.5 Этапы фильтрации шаблонов........................91

4.6 Результаты машинно-зависимой оптимизации .............. 94

4.7 Граф И/ИЛИ шаблонов команд (узлы ИЛИ — серые круги).......96

4.8 Тестирование вариантов выбора команд .................. 98

4.9 Сравнение размеров SMT-формул, полученных для VLIW-варианта СВМ ..................................... 101

4.10 Процесс поиска решений для VLIW-варианта СВМ...........103

Список таблиц

1 Примеры компиляторов для СВМ..................... 12

2 Комбинаторы языка Parse..........................59

3 Комбинаторы языка Rewrite.........................68

4 Комбинаторы языка Select .........................78

5 Низкоресурсные симметричные шифры..................82

6 Результаты поиска шаблонов........................91

7 Найденные шаблоны для реализаций шифров Магма и AES ......92

8 Результаты SMT-выбора команд......................99

9 Результаты компиляции программ для вариантов СВМ.........100

10 Правила машинно-зависимой оптимизации, полученные с помощью компилятора JC ...............................121

Приложение А

Результаты синтеза правил машинно-зависимой оптимизации

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

- максимальное число аргументов шаблона равно двум;

- шаблон может содержать до 5 вычислительных операций или констант.

Таблица 10 — Правила машинно-зависимой оптимизации, полученные с помощью компилятора JC

Программа Набор правил

ТЕА г2 = 0xc6ef3720

((г0 + 0xc6ef3720) Л г1) г3 = г2 + г0

г4 = г3 Л П1

г2 = гог(г1, 24)

г3 = гог(г2, 4)

(г0 + (г1 << 0x4)) г4 = 0xfffffff0

г5 = г4 & г3

г6 = г0 + г5

г2 = asr(r1, 5)

г3 = 0x7ffffff

(г0 + LShR(r1J 0x5)) г3 & г2

г4 =

г5 = г4 + г0

ХТЕА г2 = гог(г0, 4)

г3 = гог(г2, 24)

г4 = 0xfffffff0

(г0 + ((г0 << 0x4) л г1)) г4 & г3

г5 =

г6 = г5 л П1

г7 = г6 + Г0

Программа Набор правил

r2 = 0xffffffe0

LShR(r0, 0x5) r3 r4 = r2 & r0 ror(r3, 5)

Chaskey ((r0 << 0xd) | LShR(r0, 0x13)) r2 r3 = ror(r0, 16) ror(r2, 3)

((r0 << 0x10) | LShR(r0, 0x10)) r2 = ror(r0, 16)

((r0 << 0x7) | LShR(r0, 0x19)) r2 r3 = ror(r0, 24) ror(r2, 1)

((r0 << 0x5) | LShR(r0, 0x1b)) r2 r3 = ror(r0, 24) ror(r2, 3)

((r0 << 0x8) | LShR(r0, 0x18)) r2 = ror(r0, 24)

SIMON ((r0 << 0x1) | LShR(r0, 0x1f)) r2 r3 = ror(r0, 7) ror(r2, 24)

((r0 << 0x8) | LShR(r0, 0x18)) r2 = ror(r0, 24)

((r0 << 0x2) | LShR(r0, 0x1e)) r2 r3 = ror(r0, 6) ror(r2, 24)

r2 = r0 A r1

SPECK ((r0 << 0x18) | LShR(r1, 0x8)) r3 r4 r5 = r2 & 0xff r3 a r1 ror(r4, 8)

((r0 << 0x3) | LShR(r0, 0x1d)) r2 r3 = ror(r0, 24) ror(r2, 5)

((r0 << 0x18) | LShR(r0, 0x8)) r2 = ror(r0, 8)

SIMECK ((r0 << 0x1) | LShR(r0, 0x1f)) r2 r3 r2 r3 = ror(r0, 24) ror(r2, 7) ror(r1, 24) r2 & 0xff

((r0 | LShR(r1, 0x1b)) & r1) r4 = asr(r3, 3)

r5 = r0 | r4

r6 = r5 & r1

Программа Набор правил

г2 _ 0x7ffffff

г3 = г0 & г2

(г0 << 0x5)

г4 = гог(г3, 24)

г5 = гог(г4, 3)

г2 = г0 & 0xff

Магма ((г0 & 0xff) + г1)

г3 _ г2 + г1

г2 = гог(г0, 8)

(LShR((r0 & 0xff00)J 0x8) + г1) г3 = г2 & 0xff

г4 = г1 + г3

г2 = гог(г0, 16)

(LShR((n0 & 0xff0000)J 0x10) + г1) г3 = г2 & 0xff

г4 = г1 + г3

г2 = гог(г0, 24)

(LShR(г0J 0x18) + г1) г3 = г2 & 0xff

г4 = г1 + г3

г2 = г0 & 0xff

AES ((г0 << 0x18) | г1) г3 = гог(г2, 8)

г4 = г3 | г1

г2 = 0xffff0000

г3 = гог(г0, 16)

((г0 << 0x10) | г1)

г4 = г2 & г3

г5 = г4 | г1

г2 = гог(г0, 24)

г3 = г2 & 0xff

((г0 << 0x8) | г1)

г4 = г3 Л г2

г5 = г4 | г1

г2 = гог(г0, 24)

(LShR(г0J 0x18) + г1) г3 = г2 & 0xff

г4 = г3 + г1

Программа Набор правил

г2 = гог(г0, 16)

(LShR((r0 & 0x^^0000), 0x10) + г1) г3 = г2 & 0xff

г4 = г3 + г1

г2 = гог(г0, 8)

(LShR((n0 & 0xff00), 0x8) + г1) г3 = г2 & 0xff

г4 = г1 + г3

г2 = г0 & 0xff

((г0 & 0xff) + г1)

г3 = г2 + г1

((г0 << 0x8) | LShR(r0, 0x18)) г2 = гог(г0, 24)

((г0 << 0x10) | LShR(r0, 0x10)) г2 = гог(г0, 16)

((г0 << 0x18) | LShR(r0, 0x8)) г2 = гог(г0, 8)

Приложение Б Акты о внедрении

МИНОБРНАУКИ РОССИИ

Федеральное государственное бюджетное образовательное учреждение высшего образования «МИРЭА — Российский технологический университет»

РТУ МИРЭА

АКТ

о внедрении результатов диссертационной работы Советова Петра Николаевича, выполненной на тему «Математическое и алгоритмическое обеспечение создания компиляторов предметно-ориентированных языков для специализированных вычислительных машин» в учебный процесс Института информационных технологий федерального государственного бюджетного образовательного учреждения высшего образования «МИРЭА — Российский технологический университет» (РТУ МИРЭА)

Настоящий акт составлен о том, что материалы диссертационной работы Советова П.Н., выполненной на тему «Математическое и алгоритмическое обеспечение создания компиляторов предметно-ориентированных языков для специализированных вычислительных машин» использованы в учебном процессе РТУ МИРЭА на кафедре корпоративных информационных систем Института информационных технологий при изучении следующих дисциплин:

1. Материалы первой главы диссертации: программы-решатели ОТ-полных задач и методы синтеза программ, использованы в учебной дисциплине «Анализ сложности алгоритмов» при рассмотрении задачи выполнимости булевых формул и вопросов полиномиального сведения к ИР-полной задаче.

2. Материалы второй главы диссертации: методики и алгоритмы с использованием БМТ-решателя, применены в учебных дисциплинах «Структуры и алгоритмы обработки данных» и «Конфигурационное управление» (задача разрешения зависимостей пакетов) при рассмотрении

Информационных технологий, к.т.н., доцен

Ученый секретарь кафедры корпоративных Информационных систем

Зав. кафедрой корпоративных информационных систем к.т.н., доцент

Директор Института

вопросов практического использован экспоненциальной вычислительной а

«04 » июня 2020 года

«Утверждаю»

Заместитель директора по науке ООО «Системы технического зрения»

Метин ИЛ .

«II» сентября 2020г.

Внедрения результа

тонной работы

Советова Петра Николаевича «Математическое и алгоритмическое обеспечение создания компиляторов предметно-ориентированных языков для специализированных вычислительных машин» на соискание учёной

степени кандидата технических наук по специальности 05.13.11 -«Математическое и программное обеспечение вычислительных машин,

Представленной на соискание учёной степени кандидата технических наук

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

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

Разработанный программный инсгрумсш выявления часто встречающихся связок операций в прикладных программах дал возможность автоматизировать создание вариантов предметно-ориентированных АЛУ спецпроцессора в цикле проектирования сотрПег-тЧИе-Ьор.

комплексов и компьютерных сетей»,