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

Таким образом, выберем в качестве платформы компилятор 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. Синтаксис и семантика макромодуля

Предлагается следующий синтаксис декларации дедуктивного макромодуля (все элементы в описании могут разделяться пробелами):

2.1.1. Синтаксис и семантика макромодуля

Предлагается следующий синтаксис декларации дедуктивного макромодуля (все элементы в описании могут разделяться пробелами):

Здесь произвольный_Planning_C_код должен представлять собой фрагмент синтаксически корректного языкового выражения, не содержащего символа «@». Это может быть описатель любого статического элемента генерируемого кода. GNU_PROLOG_выражение может содержать вызовы любых предикатов GNU Prolog, в том числе генерирующих консольный вывод  результаты этого вывода и будут использоваться в качестве сгенерированных фрагментов кода. В большинстве случаев вывод будет генерироваться предикатом write.

Обращение к макромодулю имеет формат:

имя_модуля « (» [значение_параметра] {»,» значение_параметра}»)» «;»

В точке обращении к макромодулю компилятором выполняются следующие действия:

а) вычисляются все параметры обращения;

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

в) из текста модуля исключаются все предикаты, из которых формируется текст логической GNU Prolog-программы;

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

д) в программу на Planning C вместо обращения к макромодулю вставляется код, содержащий префиксную строку (которая может быть пустой) и результирующий текст модуля, обрамленный фигурными скобками.

Необходимо детализировать возможные типы параметров. Каждый параметр (после выполнения всех макроподстановок и подстановок значений констант, определенных в программе с помощью ключевого слова const) должен быть константным выражением, содержащим только неименованные константы. Такое выражение может быть числом/числовым выражением, или строкой (заключенной в апострофы), или списком, который может содержать числа, строки и другие списки. Числовые выражения вычисляются, применительно к результирующим значениям действуют следующие простые правила:

 целые числа так и считаются целыми;

 близкие к нулю вещественные константы считаются целочисленными нулями;

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

 прочие значения считаются вещественными.

Развернутый в константное выражение параметр распознается по следующим правилам:

а) если он начинается с « [», то это список, который передается в макромодуль без изменения вплоть до»]» с учетом сбалансированности по вложенным парам квадратных скобок;

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

в) иначе делается попытка распознать параметр как число/числовое выражение.

Определение макромодуля может содержать обращения к иным макромодулям, записанным в той же форме «имя_модуля (параметры);». Таким образом, реализованы вложенные макромодули, с помощью которых можно (в некоторых случаях) сократить общий объем модулей и повысить гибкость их применения.

2.1.2. Расширение базовой семантики макромодуля: порождающее программирование

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

префиксная_строка « {» сгенерированный_макромодулем_код»}»

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