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

Введение

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

Подспорьем для параллельного программирования являются специализированные языки, например, Cilk. С применением данного языка можно обеспечить вызовы функций асинхронно до тех пор, пока в родительской функции не будет достигнута точка синхронизации. Этот стиль параллелизма называется "разделяй и властвуй" (divide and conquer), или fork-join parallelism. В нём программа подразделяется на более мелкие задачи, которые планируются к параллельному выполнению. Помимо Cilk существуют специализированные библиотеки, например, Java Fork Join.

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

В настоящее время отсутствуют программы, позволяющие успешно справляться с автоматической параллелизацией. Это связано, например, с наличием в программах вложенных функций, сложных выражений формирования циклов при которых усложняется анализ зависимостей по данным. Наиболее известными программными продуктами, реализующими автоматизированный подход, являются ^[1,2]: Parawise, Polaris, Cetus, Pluto, Polly, Par4All, CAPO, WPP, SUIF, VAST/PARALLEL, OSCAR, САПФОР.

Проведем сравнительный анализ на примере Parawise. Рассмотрим шаги алгоритма, отвечающего за преобразования последовательного в параллельный код в программном продукте Parawise (см. рис. 1):

1. Получение последовательного кода.
2. Анализ зависимостей последовательного кода на основе пользовательских данных и запись информации в БД.
3. Разделение входного кода на токены (объекты, создающиеся из лексемы в процессе лексического анализа, например, “{”, “}”, “case”, “do”, “else”, “for”, “if”, “sizeof” и т.д.) и запись информации в БД при участии пользователя.
4. Контроль масок (контроль максимальных и минимальных значений для условий) и запись информации в БД при участии пользователя.
5. Вычисление и генерация структуры синтаксического дерева и запись информации в БД.
6. Оптимизация кода (снижение использования памяти) и запись информации в БД.
7. Генерация кода и переход к следующему разделу кода в п.3, либо формирование результата преобразования последовательного кода в параллельный код.

Рисунок 1. Алгоритм работы Parawise

На рисунке 2 представлены шаги преобразования последовательного кода в параллельный для программного продукта CAPO.

Рисунок 2. Алгоритм работы CAPO

1. Получение последовательного кода, который требуется распараллеливать.
2. Анализ зависимостей в полученном последовательном коде с обрабатываемыми пользовательскими данными и запись данных в БД.
3. На основе входных зависимостей, БД, данных взаимодействия с пользователем и переменных, используемых в анализе, формирование анализа на уровне циклов параллельных областей.
4. Оптимизация областей и циклов на основе анализа на уровне циклов параллельных областей и переменных, используемых в анализе, формирование оптимизации областей и циклов.
5. На основе полученных данных производится обнаружение дублирования в блоках. В БД вносятся промежуточные данные и происходит опрос пользователя на корректировку данных.
6. Выполнение прямой вставки полученными данными, генерация кода, обмен данными с БД.

Заметим, что Parawise и CAPO работают по схожему алгоритму, как и программы Cetus, Pluto, Polly, Par4All, CAPO, WPP, SUIF, VAST/PARALLEL, OSCAR, САПФОР. Одним из минусов является то, что данные программные продукты десктопные, т.е. имеют зависимость от целевой платформы (нельзя запустить на разных операционных системах), также требуется отслеживать обновление программного продукта. Отдельно следует выделить блок взаимодействия с пользователем, при котором пользователь выбирает требуемое решение. Реализация данного блока, представленная в CAPO и Parawise, исключает возможность автоматического параллелизма. Это требует от программиста наличие знаний в области параллельного программирования ^[3,4].

Предлагаемый в статье подход позволяет перейти к автоматизации перевода параллельного программного кода с наименьшим участием оператора, так как блок взаимодействия с пользователем является само обучаемым, основанным на глубоком обучении (deep learning) ^[5,6].

Архитектура транслятора

При разработке транслятора позволяющего преобразовать последовательный код в параллельный было принято решение сделать веб-приложение. Данное решение вызвано следующими факторами:

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

Проект транслятора имеет микросервисную архитектуру (рис. 3). Приложение состоит из нескольких программ (сервисов):

• сервис обработки запросов (обработчик запросов),
• сервис построения синтаксического дерева,
• сервис преобразования кода,
• база данных на базе СУБД PostgreSQL.

Сервис обработки запросов позволяет принимать REST-запросы пользователя, а именно запрос на преобразование последовательного кода в параллельный ^[7,8]. В запросе указывается последовательный код, требуемый для распараллеливания, а также язык программирования, на котором он написан. Также сервис позволяет делать запросы к базе данных для получения данных о синтаксическом дереве и преобразованном коде.

Рисунок 3. Архитектура транслятора

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

Сервисы формирования параллельной программы

Сервис преобразования кода забирает данные о построенном синтаксическом дереве из БД, строит различные схемы распараллеливания для исходной программы. Далее производится оценка построенной схемы по набору правил полученных из БД соответствующего синтаксису языка преобразования текста из синтаксического дерева, и строит текст программы с применением принципов параллельного программирования и записывает в БД ^[9,10]. Создание параллельной программы можно рассмотреть на диаграмме последовательностей (рис. 4). Дадим описание данной диаграммы.

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

Клиент отправляет REST (GET ‘/code’) запрос на преобразование последовательного кода в параллельный. Обработчик запросов вставляет новые данные в таблицу code базы данных и получает значение идентификатора нового поля. Следующим этапом обработчик запросов отправляет данные о записанном идентификаторе в сервис построения синтаксического дерева POST запросом. Сервис построения дерева получает данные о последовательном коде из БД и преобразует их в синтаксическое дерево. Результат преобразования записывается в БД и передается сервису преобразования кода POST запросом с идентификатором. Сервис преобразования кода преобразует синтаксическое дерево в параллельный код и записывает его в БД.

Построение программы выполняется в соответствии с микросервисной архитектурой. В качестве плюса микросервисов можно выделить наличие дополнительных возможностей по добавлению нового функционала программы для работы с другими языками: добавление синтаксического дерева или преобразование в параллельный код. В случае появления большей нагрузки со стороны пользователей добавляется брокер сообщений RabbitMQ или Kafka, позволяющий преобразовывать сообщение (для RabbitMQ – AMQP, Kafka – Kafka protocol) от приложения-источника в приложение-приемник, тем самым выступая между ними посредником. В этом случае клиент отправляет запрос на преобразование кода в сервис обработчика запросов. Обработчик запросов записывает данные в БД, отправляет код в брокер сообщений с идентификатором и языком программирования, который требуется преобразовать в синтаксическое дерево. Сервис построения дерева преобразовывает синтаксическое дерево в требуемый код для данного языка программирования. После этого происходит запись данных в БД и отправка идентификатора и названия языка программирования в брокер сообщений (система, преобразующая сообщение от источника данных “producer” в сообщение принимающей стороны “consumer”). Сервис преобразования кода через брокер сообщений преобразует код в параллельный эквивалент требуемого языка программирования.

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

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

Построение синтаксического дерева

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

Наиболее популярным является ANTLR4 это библиотека лексического анализа для Another Tool for Language Recognition (ANTLR). Принцип работы ANTLR основан на синтаксическом анализе входного потока данных, построения синтаксического дерева, обхода этого дерева и предоставления сгенерированного API для внедрения логики для каждого из событий обхода. API генерируется на основе “грамматики”, которая определяет структуру предложения, отдельных фраз/слов и конкретных символов. Однако данная библиотека написана давно, вследствие чего в ней отсутствует поддержка современных языков программирования и требуются дополнительные библиотеки во время выполнения.

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

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

Разработанное синтаксическое дерево характеризуется следующими этапами:

• Лексический анализ входной программы. Данный процесс характеризуется аналитическим разбором входной последовательности символов на распознанные группы – лексемы – с целью получения на выходе идентифицированных последовательностей, называемых «токенами» (подобно группировке букв в словах).
• Синтаксический анализ или синтаксический разбор – процесс сопоставления линейной последовательности лексем (слов, токенов) естественного или формального языка с его формальной грамматикой.
• К полученной структуре применяется семантический анализ, процесс выявления «смысла» синтаксических конструкций. Примером является связывание идентификатора с его объявлением, типом данных, определение результирующего типа данных выражения.
• Далее производится преобразование в промежуточный код (в нашем случае это код в формате JSON).

Рассмотрим простой пример преобразования в синтаксическое дерево.

На вход отправляем JSON посылку с последовательным кодом:

{
"code": "int main()n {n for(int i=0; i<=4; i++)n{n printf("Текст"); n} n return 0;n}",
"language": "C"
}

Где code – последовательный код, предназначенный для параллелизации; language – язык программирования, на котором написан код.

Получаем сформированное синтаксическое дерево:

{
"tree": [
{
"type": "Program"
},
{
"type": "FunctionDeclaration",
"typeVar": "int",
"id": "main",
"params": [],
"body": [
{
"type": "ForStatement",
"init": [
{
"type": "VariableDeclaration",
"id": "i",
"value": "0",
"variable": "int"
},
{
"type": "CompareExpression",
"id": "i",
"mark": "<=",
"number": "4"
},
{
"type": "UpdateExpression",
"id": "i",
"operator": "++",
"prefix": "false"
}
],
"body": [
{
"type": "StringFunctionDeclared",
"value": "Текст"
}
]
},
{
"type": "ReturnStatement",
"argument": {
"type": "Literal",
"value": "0"
}
}
]
}
]
}

Описание используемых полей:

• tree – корневое дерево проекта;
• type – тип описываемого блока;
• typeVar – тип данных;
• id – название идентификатора;
• params – параметры описываемого объекта;
• body – тело описываемого блока;
• init – инициализируемые параметры;
• value – значение заданного параметра;
• variable – тип переменной;
• mark – значение знака;
• number – значение числа;
• operator – значение оператора;
• prefix – использование префикса;
• argument – значение аргумента.

Заключение

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

В будущем планируется расширить структурное представление синтаксического дерева, дополнить сервис преобразования кода модулями преобразования последовательного кода в параллельный код с применением нейросетевого подхода ^[11,12].