скачать книгу бесплатно
Технологии автоматического дедуктивного распараллеливания в языке Planning C
Владимир Викторович Пекунов
Работа посвящена решению проблемы автоматического распараллеливания C-программ с применением средств построения языковых расширений языка Planning C 2.0. Предложены механизмы реализации расширений, доказана теорема об их реализуемости. Предложена новая технология распараллеливания тел циклов, состоящих из двух зависимых по данным частей. Предложена технология оптимизирующей векторизации многократно выполняемых циклов с расходящимися трассами итераций на векторных расширителях.
Технологии автоматического дедуктивного распараллеливания в языке 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[1 - Информация получена с сайта http://www.crescentbaysoftware.com], который работает с промежуточными представлениями компилируемой программы и может встраиваться в иные компиляторы, выполняя ряд распараллеливающих оптимизаций циклов и векторизаций.
Недостатками такого подхода являются: а) его «непрозрачность» и б) его сомнительная пригодность для выявления и эффективной реализации параллелизма по задачам, что может потребовать спекулятивного исполнения кода с достаточно глубоким анализом потенциальной эффективности выделения параллельных подзадач, которая может существенно зависеть как от технических характеристик конкретной ЭВМ, так и от особенностей используемой операционной системы. Данные недостатки в значительной степени могут быть устранены, если компилятор допускает оперативную разработку и встраивание высокоуровневых языковых расширений, позволяющих анализировать текущий код и автоматически модифицировать его тем или иным образом.
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++[2 - См., например, https://www.cilkplus.org] [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], имеющий серьезные предпосылки для реализации указанных средств на базе аппарата сканеров и дедуктивных макросов, задействуемого на уровне многостадийной гибкой схемы препроцессинга, поддерживающей последовательную многократную переработку кода.
Глава 2. Встроенная трансформация программ в языке Planning C
Как уже неоднократно упоминалось, задача трансформации программы в общем случае может быть достаточно нетривиальным алгоритмом, требующим применения интеллектуальных технологий логического программирования. В таком аспекте указанная задача может быть сведена к трем основным этапам: а) разбору программы с формированием набора представленных в ней фактов и взаимосвязей между ними; б) анализу полученной базы фактов с генерацией дополнительных фактов, представляющих распараллеливающие конструкции; в) генерации выходной программы на основе результирующего набора фактов.
Соответственно, целью данной главы является определение набора языковых средств Planning C 2.0, на базе которых могут быть реализованы все вышеупомянутые этапы.
Для реализации данной цели необходимо решить задачи по реализации вышеупомянутых этапов с применением логического программирования или его элементов.
2.1. Дедуктивные макромодули: средства решения задач распараллеливания и генерации выходной программы
Первоначально в языке Planning C дедуктивные макромодули предназначались для гибкой генерации описаний вычислительных топологий (этим и объясняются некоторые их не вполне очевидные синтаксические особенности), впоследствии же их применение было расширено: в настоящее время дедуктивные макромодули используются для гибкой дедуктивной генерации произвольных фрагментов программы на основе логических правил, записанных на языке GNU Prolog, имеющем бесплатный и свободно распространяемый интерпретатор. Как будет показано в настоящей работе, дедуктивные макромодули вполне могут сгенерировать и полноценную параллельную программу.
Дедуктивный макромодуль является совокупностью статических и динамических (генерируемых на одной из стадий компиляции в ходе применения предикатов GNU-Prolog) элементов. Он оформлен в виде специального программного блока и имеет параметры, в зависимости от которых им генерируется фрагмент программного кода. Соответствующий код будет вставлен в программу в точке обращения к макромодулю, в котором будут указаны конкретные значения его параметров. Предполагается, что макромодуль будет генерировать код на этапе компиляции, точнее, на стадии препроцессинговой обработки. Соответственно, это накладывает определенные ограничения на возможные значения его параметров – это должны быть выражения, которые можно вычислить на этапе препроцессинга: предположим, что это выражения, содержащие исключительно именованные и неименованные константы, в том числе те, которые формируются в результате классических макроподстановок C/C++.
2.1.1. Синтаксис и семантика макромодуля
Предлагается следующий синтаксис декларации дедуктивного макромодуля (все элементы в описании могут разделяться пробелами):
«#» «def_module» « (» префиксная_строка»)» имя_модуля « (» [имя_параметра] {»,» имя_параметра}»)» « {»
(предикат | цель | произвольный_Planning_C_код)
{(предикат | цель | произвольный_Planning_C_код}
«}» «;»
предикат = «@» имя_предиката [» (» переменные_предиката»)»] [»: -» GNU_PROLOG_выражение]».»
цель = «@» «goal» «:-» GNU_PROLOG_выражение».»
Здесь произвольный_Planning_C_код должен представлять собой фрагмент синтаксически корректного языкового выражения, не содержащего символа «@». Это может быть описатель любого статического элемента генерируемого кода. GNU_PROLOG_выражение может содержать вызовы любых предикатов GNU Prolog, в том числе генерирующих консольный вывод – результаты этого вывода и будут использоваться в качестве сгенерированных фрагментов кода. В большинстве случаев вывод будет генерироваться предикатом write.
Обращение к макромодулю имеет формат:
имя_модуля « (» [значение_параметра] {»,» значение_параметра}»)» «;»
В точке обращении к макромодулю компилятором выполняются следующие действия:
а) вычисляются все параметры обращения;
б) значения параметров подставляются в текст модуля вместо соответствующих лексем – имен параметров;
в) из текста модуля исключаются все предикаты, из которых формируется текст логической GNU Prolog-программы;
г) фрагмент модуля, содержащий какую-либо из целей, заменяется результатом доказательства этой цели (то есть блоком выведенных на консоль в ходе доказательства строк) в контексте сформированной логической GNU Prolog-программы;
д) в программу на Planning C вместо обращения к макромодулю вставляется код, содержащий префиксную строку (которая может быть пустой) и результирующий текст модуля, обрамленный фигурными скобками.
Необходимо детализировать возможные типы параметров. Каждый параметр (после выполнения всех макроподстановок и подстановок значений констант, определенных в программе с помощью ключевого слова const) должен быть константным выражением, содержащим только неименованные константы. Такое выражение может быть числом/числовым выражением, или строкой (заключенной в апострофы), или списком, который может содержать числа, строки и другие списки. Числовые выражения вычисляются, применительно к результирующим значениям действуют следующие простые правила:
– целые числа так и считаются целыми;
– близкие к нулю вещественные константы считаются целочисленными нулями;
– близкие к целым вещественные значения считаются соответствующими целыми (с округлением);
– прочие значения считаются вещественными.
Развернутый в константное выражение параметр распознается по следующим правилам:
а) если он начинается с « [», то это список, который передается в макромодуль без изменения вплоть до»]» с учетом сбалансированности по вложенным парам квадратных скобок;
б) если он начинается с «'», то это строка, которая передается без изменения вплоть до закрывающего апострофа «'» с учетом наличия в строке возможных пар апострофов, представляющих апостроф, являющийся одним из символов строки;
в) иначе делается попытка распознать параметр как число/числовое выражение.
Определение макромодуля может содержать обращения к иным макромодулям, записанным в той же форме «имя_модуля (параметры);». Таким образом, реализованы вложенные макромодули, с помощью которых можно (в некоторых случаях) сократить общий объем модулей и повысить гибкость их применения.
2.1.2. Расширение базовой семантики макромодуля: порождающее программирование
Приведем общую схему порожденного макромодулем фрагмента, которая, в ранних версиях языка, предназначалась почти исключительно для генерации описателей вычислительных топологий:
префиксная_строка « {» сгенерированный_макромодулем_код»}»
Уже очевидно, что возможно применение макромодулей для параметризованной генерации синтаксических конструкций, включающих префиксованный блок (П-блок) в фигурных скобках: деклараций структур, классов, уний, функций. Очевидно, что если ввести синтаксические средства, позволяющие убрать префиксную строку (возможность ее изменения заложена в макромодуль изначально) и обрамляющие скобки, то задача порождения принципиально произвольного Planning C-кода будет решена. Соответственно, определим два специальных предиката, управляющих порождением кода:
– prefix_off, выключающий префиксную строку,
– brackets_off, выключающий обрамляющие фигурные скобки.
Эти предикаты имеют глобальный для всего макромодуля эффект, соответственно они могут быть вызваны в любом из предикатов/целей модуля.
Таким образом, реализовано полноценное логическое порождающее программирование, которое может быть применено для решения сложных, интеллектуальных задач:
а) дедуктивного анализа фактов, представляющих, в частности, разобранную входную программу, с выработкой фактов, указывающих на необходимость применения распараллеливающих конструкций;
б) генерации кода на основании исходных и полученных фактов.
