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

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

ISBN 978-5-0056-3553-2

Создано в интеллектуальной издательской системе Ridero

Введение

В настоящее время активно развиваются технологии, связанные с решением ряда интеллектуальных задач, подразумевающих обработку больших массивов структурированных или слабо структурированных данных с применением более или менее трудоемких логических [12], символьных [11] или численных алгоритмов (см., например, [2, 14, 21]. Это, в первую очередь, технологии интеллектуальной обработки данных, к которым относятся разнообразные алгоритмы поиска логических и/или математических формальных закономерностей в данных (Big Data/Data Mining [7, 22]): деревья решения, машины поддерживающих векторов [22], нейронные сети [22, 24], МГУА [7] и иные интерполяторы и экстраполяторы [11]. Во вторую очередь, назовем элементы технологий поддержки диалога с пользователем на естественном языке (см., например, [22]). Далее назовем ряд технологий математического моделирования различных процессов, например, в сплошных средах: моделирования образования и распространения загрязнений [10, 13, 14, 35], прогнозирования погоды [41], прогнозирования изменений климата [6, 41], моделирования обтекания различных технических объектов [28], прочностные и иные трудоемкие расчеты, связанные с моделированием (см., например, [5]).

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

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

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

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

Итак, данная работа будет посвящена автоматическому распараллеливанию C-программ (дающих высокую эффективность исполнения кода, поскольку язык С – один из наиболее близких к машинному, уступающий, возможно, лишь языкам класса Форт), однако изложенные в ней технологии пригодны для распараллеливания программ, написанных и на иных алгоритмических языках.

Целью данной работы является повышение эффективности исполнения C-программ, исполняемых на различных типах параллельных/распределенных систем, к которым можно отнести не только суперЭВМ, но и подавляющее большинство современных рядовых ЭВМ (в том числе с SIMT-расширителями, такими как многоядерные видеокарты). Соответственно, следует стремиться: а) к максимальной многоплатформенности получаемых распараллеленных C-программ и б) к оптимальной трудоемкости разработки адекватных параллелизаторов, подразумевающей достаточную мощность средств разработки в сочетании с их простотой. Для достижения данной цели сформулируем задачи:

а) рассмотреть современные подходы к автоматизированному распараллеливанию императивных (в том числе написанных на языке C) программ;

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

в) предложить новые технологии распараллеливания, применение которых может быть автоматизировано;

г) разработать подход и алгоритмы автоматического распараллеливания C-программ;

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

Глава 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.