Данный проект направлен на развитие новой версии 3.x системы SAPFOR (System FOR Automated Parallelization), предназначенной для автоматизации распараллеливания программ в модели DVMH, OpenMP и др. Работы направлены как на расширение уже реализованных возможностей по анализу и распараллеливанию С программ, так и на добавление в систему поддержки языка Fortran. Работы выполняются на базе фронтендов для С — Clang и для Fortran — Flang, а также на базе единого представления программ в виде LLVM IR. В состав системы входят статические и динамические анализаторы, преобразователи кода и интерактивная подсистема, реализованная в виде плагина для Visual Studio Code, а также подсистема автоматизации запуска тестов.
Разработка ведется в основном на C++ 17, некоторые компоненты системы написаны на JavaScript и TypeScript (интерактивная оболочка) и Perl (подсистема тестирования).
Выполняемые работы можно разделить на несколько группы, но стоит понимать, что такое деление достаточно условно, все работы взаимосвязаны и направлены на достижение общей цели: упростить разработку параллельных программ.

Статический анализ

Анализ свойств исходной программы, необходимых для ее распараллеливания. Свойства могут касаться как соответствия синтаксических конструкций языка ограничениям выбранной модели параллелизма (например, тесная вложенность циклов, каноническая форма циклов и т.д.), так и относиться к потоку управления и потоку данных внутри программы (наличие зависимостей по данным, достижимость определенных точек кода, наличие разных указателей на одну и ту же область памяти, наличие инвариантов цикла и др.). Анализ выполняется как на уровне исходного кода программы, представленного в виде абстрактного синтаксического дерева (Flang или Clang AST), так и в виде внутреннего низкоуровневого представления LLVM IR.

Динамический анализ

В отличие от статического, данный вид анализа выполняется в процессе выполнения программы, запущенной над заранее подготовленными входными данными. За счет конкретизации используемых данных можно получить более точные результаты анализа, в точности отследив выполнение программы, но в отличие от статического анализа, результаты которого верны для всевозможных входных данных, выводы, сделанные в ходе динамического анализа, могут оказаться неверными при запуске программы в других условиях. Кроме того любые дополнительные действия над программой, связанные с ее исследованием в процессе выполнения, приводят к дополнительным накладным расходам. Такие накладные расходы могут приводить к невозможности дождаться завершения динамического анализа. Таким образом, при разработке средств динамического анализа необходимо принимать компромиссные решения, чтобы обеспечить его выполнимость и полноту получаемых данных. Динамический анализ может быть направлен на получение информации, связанной с профилем выполнением программы, в том числе с определением наиболее ресурсоемких участков кода, занимающих максимальное время выполнения и требующих распараллеливание или оптимизацию в первую очередь. Также динамический анализ может быть направлен на получение свойств объектов программы, таких как переменные, циклы, функции и др., например, обнаружение зависимостей по данным. В системе SAPFOR анализ выполняется в первую очередь за счет модификации представления программы в виде LLVM IR (вставки обращений к библиотеке динамического анализа) и реализации соответствующей библиотеки анализа.

Преобразование исходного кода

Выполнение преобразований, необходимых для распараллеливания программы (например, для устранения найденных зависимостей или других проблем), а также для повышения ресурса параллелизма в программе. Преобразования выполняются на уровне исходного кода программы с использованием соответствующих фронтендов (Flang — Фортран, Clang — Си). Проверки допустимости преобразований реализуются как на уровне исходного кода на базе абстрактного синтаксического дерева программы (синтаксические и семантические проверки), так и на уровне внутреннего представления LLVM IR (семантические проверки).

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

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

Интерактивная оболочка

Система SAPFOR опирается на тесное взаимодействие с пользователем и неотъемлемой ее частью является интерактивная оболочка, отвечающая за поддержание процесса распараллеливания программы. Работы в данном направлении связаны как с реализацией непосредственно интерактивной составляющей (плагин для Microsoft Visual Studio Code, JavaScript, TypeScript), так и с получением требуемых данных от подсистем анализа и преобразования (LLVM IR, Clang, Flang, C++17). Интерактивная составляющая включает: визуализацию найденных системой свойств программы (работа с памятью, зависимости по данным в циклах, граф потока управления, структура программы и др.); создание и управление проектом, описывающим программу; контроль версий программы, порождаемых в ходе ее преобразования и распараллеливания; создание сценариев анализа и модификации программы.

Первые шаги

Исходные коды доступны на GitHub, документацию можно найти в разеделе Wiki.
Основные репозитории относящиеся к SAPFOR 3.x:

• tsar — статически анализатор и основной компонент SAPFOR, управляющий распараллеливанием (С++ 17),
• dyna — динамический анализатор (С++),
• bcl — вспомогательная библиотека шаблонов С++ (С++ 17),
• tsar-advisor — интерактивная оболочка (плагин для Visual Studio Code) (TypeScript, JavaScript).

Эти репозитории входят в репозиторий sapfor как под-модули, загружать нужно sapfor:

git clone --recurse-submodules https://github.com/dvm-system/sapfor

Cборка системы возможна на Windows, Linux и Mac OS. Возможны два способа сборки:

• Сборка внутри Docker контейнера, разработка и запуск SAPFOR также внутри этого контейнера. Потребуется установленный Docker и Visual Studio Сode (см. Wiki).
• Сборка непосредственно в вашей ОС (см. Wiki).

Литература

Статический анализ

Автоматизация распараллеливания

Динамический анализ

Интерактивная оболочка