Читать книгу Технологии автоматического дедуктивного распараллеливания в языке Planning C - Владимир Викторович Фомин, Владимир Викторович, Владимир Викторович Таболин - Страница 5

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

Отметим, что существует еще один, достаточно интересный вариант средств распараллеливания – расширение Cilk++2 [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.