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

Далее, следует отметить, что в последние десятилетия в практике параллельных вычислений достаточно широко используются векторные расширители (обычные процессоры с векторными инструкциями или многоядерные видеокарты с потоковыми процессорами 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], имеющий серьезные предпосылки для реализации указанных средств на базе аппарата сканеров и дедуктивных макросов, задействуемого на уровне многостадийной гибкой схемы препроцессинга, поддерживающей последовательную многократную переработку кода.

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