Технологии автоматического дедуктивного распараллеливания в языке Planning C

Владимир Викторович Пекунов

Работа посвящена решению проблемы автоматического распараллеливания C-программ с применением средств построения языковых расширений языка Planning C 2.0. Предложены механизмы реализации расширений, доказана теорема об их реализуемости. Предложена новая технология распараллеливания тел циклов, состоящих из двух зависимых по данным частей. Предложена технология оптимизирующей векторизации многократно выполняемых циклов с расходящимися трассами итераций на векторных расширителях.

Глава 1. Подходы к распараллеливанию императивных программ

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

а) провести краткий обзор современных основных подходов к автоматическому/автоматизированному распараллеливанию;

б) выбрать наиболее соответствующий поставленным в работе целям подход;

в) определить средства распараллеливания и программную платформу для реализации автоматического распараллеливания.

1.1. Обзор подходов к автоматическому/автоматизированному распараллеливанию

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

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

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

1. В наиболее простом случае (преимущественно параллелизм по данным), распараллеливание может производиться непосредственно компилятором (при этом исходный код, с формальной точки зрения, практически не меняется), который, в частности, может применить векторные инструкции. К таким компиляторам относятся, например, GNU C/C++ Compiler и Intel C++ Compiler. Несколько условно можно отнести к этой градации плагин-компилятор VAST¹, который работает с промежуточными представлениями компилируемой программы и может встраиваться в иные компиляторы, выполняя ряд распараллеливающих оптимизаций циклов и векторизаций.

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

2. В более сложных случаях выполняется полноценный анализ (специализированной системой) с последующей частичной переработкой кода исходной программы, в который вставляются те или иные директивы распараллеливания, соответствующие одному из стандартных интерфейсов распараллеливания (DVM [9], MPI, OpenMP [4, 27]). Это достаточно «быстрый» и «дружелюбный» по отношению к программисту (поскольку структура кода, в целом, не претерпевает существенных изменений и может быть легко проанализирована, например, в целях обучения) вариант. Кроме того, здесь:

а) не предъявляются повышенные требования к компилятору;

б) более широк диапазон выявляемых паттернов параллелизма (в частности, параллелизма по задачам);

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

В качестве примеров можно назвать системы распараллеливания YUCCA, PLUTO [32] и AutoPar [37], использующие для распараллеливания директивы OpenMP, S2P [40], использующую OpenMP и pThreads, а также PIPS [29], в которой используются MPI и OpenMP.

3. В наиболее сложном случае возможна глубокая проработка исходного кода параллелизатором с достаточно активным диалогом с программистом, что, вероятно, позволяет в наибольшей степени выявить потенциально параллельные фрагменты и дать наиболее эффективный выходной код. Однако это, фактически, уже полуавтоматическое распараллеливание. Здесь можно назвать, например, системы ParaWise [23], Tournavitis [32] и САПФОР/ПАРФОР [3, 8].

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

1.2. Выбор платформы автоматизации распараллеливания и средств распараллеливания

Как уже упоминалось выше, большинство известных систем автоматического распараллеливания использует OpenMP и/или MPI, что вероятно, во многом объясняется их широкой поддержкой или непосредственно в компиляторах (OpenMP) или в специализированных библиотеках (MPI). Это существенный аргумент и мы, несомненно, в данной работе рассмотрим возможность применения некоторых, базирующихся на применении OpenMP технологий автоматического распараллеливания, подразумевающих, например, применение сверхоптимистичных вычислений [16], использующих предицирующие каналы, построенные на базе OpenMP. Данная задача является новой.

Отметим, что существует еще один, достаточно интересный вариант средств распараллеливания — расширение Cilk++² [32], для которого известны как независимые реализации, так и реализации в ряде версий GNU C++ Compiler. Его серьезным достоинством является предельная простота базовых средств, включающих всего три ключевых слова: cilk_spawn (запуск параллельного процесса), cilk_sync (ожидание завершения порожденных процессов), cilk_for (распараллеливание циклов). Такая простота, во многом, объясняется тем, что гранулой параллелизма по задачам является обычная C-функция, что в значительной степени перекликается с идеями, реализованными в T-системе [4].

Автору не удалось найти сведений о реализации систем автоматического распараллеливания с применением Cilk++, поэтому разработка средств такого распараллеливания представляет не только потенциальный практический, но и определенный теоретический интерес. При этом задача автоматического распараллеливания будет сведена к адекватной расстановке директив cilk_sync, cilk_spawn и cilk_for.

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

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

Далее отметим, что задача автоматического распараллеливания подразумевает решение нескольких типовых подзадач:

а) лексико-синтаксический разбор (парсинг) исходной программы;

б) распознавание реализованного в программе алгоритма с определением потенциально параллельных фрагментов;

в) отбор фрагментов, распараллеливание которых дает существенный выигрыш по времени;

г) реструктуризация алгоритма (вставка директив распараллеливания);

д) формирование распараллеленного выходного кода.

Задача лексико-синтаксического разбора, в простейшем случае, может выполняться специальным автоматом, построенным в соответствии с формальной грамматикой входного языка программирования. Здесь обычно применяются программные средства по типу bison/flex (yacc/lex), в значительной степени облегчающие построение указанного автомата.

Автоматы, однако, не являются лучшим выбором. Следует отметить, что сопутствующее решение второй нетривиальной задачи (распознавания алгоритма с определением потенциального параллелизма) может потребовать еще более сложного нечеткого/эвристического анализа (см., например, подход [43], предполагающий поиск характерных структур/сигнальных признаков и вычисление метрик сходства кода, после чего применяется классифицирующее дерево решений), принимающего во внимание «разбросанные» по тексту программы фрагменты алгоритма. Такая потенциальная возможность побуждает прибегнуть к более сложным средствам лексико-синтаксического разбора, допускающим не только схожий с автоматным подход, но и сканирование исходного текста, например, в соответствии с элементами некоторой контекстно-зависимой грамматики.

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

Вышеуказанные требования в полной мере реализуются компилятором языка Planning C 2.0 (данный язык является расширением языка C, [20]), допускающим оперативную разработку языковых расширений на базе сканеров (основанных на мощном механизме регулярных выражений, дополненных возможностями задействования подключаемых логико-синтаксических операций и предикатов), выделяющих языковые конструкции, и дедуктивных макросов (на базе языка GNU Prolog), потенциально позволяющих выполнить глубокий интеллектуально-логический анализ задачи и генерацию выходного кода. Данный компилятор поддерживает гибкую многостадийную схему препроцессинга исходных программ, позволяющую проводить многостадийную распараллеливающую трансформацию исходной программы ([исходный код на языке C — > код с высокоуровневыми директивами распараллеливания Planning C — > код C++ с более низкоуровневыми директивами распараллеливания OpenMP/OpenCL] или [исходный код на языке C — > код C++ с более низкоуровневыми директивами распараллеливания Cilk++]).

Таким образом, выберем в качестве платформы компилятор Planning C 2.0.

Выводы к первой главе

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

По тем же соображениям, в качестве конечных средств распараллеливания выбраны OpenMP, OpenCL и Cilk++, реализующие основные виды параллелизма (по данным и по задачам) на широком классе вычислительных систем. Проанализирован состав подзадач, потенциально решаемых при автоматическом распараллеливании. Показано, что такие подзадачи могут потребовать применения как стандартных автоматных, так и нестандартных сканирующих средств лексико-синтаксического анализа и средств интеллектуальной трансформации распознанных алгоритмов с генерацией программ по трансформированным алгоритмам. С учетом сказанного, в качестве программной платформы был выбран компилятор Planning C 2.0 [19], имеющий серьезные предпосылки для реализации указанных средств на базе аппарата сканеров и дедуктивных макросов, задействуемого на уровне многостадийной гибкой схемы препроцессинга, поддерживающей последовательную многократную переработку кода.

Примечания

1

Информация получена с сайта http://www.crescentbaysoftware.com

2

См., например, https://www.cilkplus.org