Новый язык обычного и параллельного программирования Planning C 2.014.01.2022 05:46

Здравствуйте, уважаемые читатели.

Хочу написать здесь об одном из своих проектов — языке Planning C (v2.0). Он является расширением C++, дополняющим базовый язык рядом новых конструкций. В настоящее время проект доступен в репозитории (исходный код прототипного транслятора-препроцессора, множество примеров, конвертер простых программ MPI→Planning C). От других языков Planning C отличается тем, что многие его новые конструкции построены на базе так называемых процедур с планированием повторного входа, которые в первую очередь удобны для программирования некоторых алгоритмов, использующих стек, дек или очередь (но могут использоваться и для программирования произвольных алгоритмов). Язык содержит различные средства алгоритмизации и распараллеливания, более-менее унифицированные и для обычных в наше время компьютеров с многоядерными процессорами, и для видеокарт, и для кластерных систем. Во второй версии языка были введены стандартные средства расширения языка новыми конструкциями, «интеллектуальная» мемоизация и еще некоторые возможности. Надеюсь, кому-нибудь данный язык покажется интересным, может быть даже перспективным для применения и/или развития. Сам я иногда им пользуюсь для быстрого написания некоторых расчетных параллельных программ.

В этой статье напишу лишь о самых базовых возможностях языка, преимущественно на примерах. Если тема вызовет интерес, то, возможно, впоследствии напишу еще одну-две статьи о «продвинутых»/необычных возможностях.

Немного теории

Процедура с планированием повторного входа — это процедура с планом. Процедура исполняется столько раз (последовательно или параллельно), сколько элементов содержится в плане. Элементы извлекаются из начала плана, для каждого извлеченного элемента процедура вызывается заново (в неявно присутствующем цикле). Каждый элемент содержит набор значений параметров процедуры, которые передаются в нее при обработке текущего элемента плана. План может наполняться вне процедуры или внутри нее [с помощью специальных функций вставки в начало плана (plan_first) или в конец плана (plan_last)].

Немного особенным образом обрабатываются параметры, передаваемые по ссылке — их значения просто переходят с этапа на этап. Однако если в одном из элементов плана такой параметр был спланирован с отсечением (с указанием знака »!» после значения параметра), то в процедуру при исполнении данного элемента будет передано именно указанное значение.

Функция с планированием повторного входа отличается от процедуры тем, что имеет возвращаемое значение — оно определяется результатом последнего исполненного элемента плана.

Процедуры и функции с планированием повторного входа могут объединяться в цепи (наборы таких процедур или функций), которые могут исполняться просто параллельно (режим вектора) или параллельно с передачей данных по этой цепи (режим конвейера, при этом для передачи значения в начало плана следующей процедуры используется throw_first, а в конец — throw_last).

Примеры обычных вычислений

Пример. Рассмотрим процедуру, выполняющую цикл от 0 до 5:

reenterable Loop(int x, int last) {

 cout << x << " ";

 if (++x <= last) plan_first(x);

}

/* Вызов: Loop(0,5); */

Пример. Рассмотрим последовательную нумерацию узлов двоичного дерева по уровням сверху вниз и слева направо.

typedef struct TreeTag {

  int Data;

  struct TreeTag * Left;

  struct TreeTag * Right;

} TreeNode;

int Number;

reenterable EnumerateByLevel(TreeNode * Cur) {

 Cur->Data = Number++;

 if (Cur->Left) plan_last(Cur->Left);

 if (Cur->Right) plan_last(Cur->Right);

}

/* Вызов: Number = 1; EnumerateByLevel(Root); */

Ту же функцию EnumerateByLevel можно использовать и в виде лямбда-функции, с тем отличием, что вместо функций plan_first/plan_last используются reent_first/reent_last:

auto f = reenterable (TreeNode * Cur) {

 Cur->Data = Number++;

 if (Cur->Left) reent_last(Cur->Left);

 if (Cur->Right) reent_last(Cur->Right);

}

/* Вызов: Number = 1; f(Root); */

Примеры параллельных вычислений

При планировании элементов исполнения в план могут вставляться маркеры, которые делят его на группы. По умолчанию (без маркеров) группой является весь план. Также по умолчанию любая группа исполняется последовательно, но, если вызвать директиву plan_group_parallelize, то тут же включится режим параллельного исполнения такой группы. А если вызвать plan_group_vectorize, то группа элементов плана будет запущена на видеокарте (сразу оговорюсь, что в таком случае есть ряд особенностей и ограничений на синтаксис).

Пример. Параллельно просуммируем элементы дерева, при этом воспользуемся редукцией для параметра-суммы:

reenterable TreeSum(TreeNode * Cur, reduction(+) int & SumResult)

{

 if (Cur==Root) plan_group_parallelize;

 if (Cur->Left) plan_last(Cur->Left,SumResult);

 if (Cur->Right) plan_last(Cur->Right,SumResult);

 SumResult = Cur->Data;

}

Пример для работы на видеокарте (умножим массив чисел A[N] на k, получим массив B[N]):

#pragma plan vectorized

#pragma plan common begin

#define N 5

#pragma plan common end

reenterable Mul(bool init, int k, _global(N) int * A, int i, _local(1) int * out) {

  int ii;

  if (init) { // Заполняем план и далее запускаем на распараллеливание

     for (ii = 0; ii < N; ii++) {

         plan_last(false, k, A, ii, out);

         out++;

     }

     plan_group_vectorize(NULL);

  } else { // Собственно параллельная работа

         *out = A[i]*k;

  }

}

/* Вызов: Mul(true, k, A, 0, B); */

Пример параллельных вычислений на конвейере (для многоядерного процессора)

Пусть конвейер обрабатывает дерево, причем на первой его стадии находится максимальный элемент, а на второй — минимальный элемент. Первая стадия, в свою очередь, распараллеливается на 4 процессора, аналогично распараллеливается и вторая стадия. Таким образом, здесь мы имеем комбинированный параллелизм.

#ifndef __min

#define __min(a,b) ((a)<(b) ? (a) : (b))

#endif

#ifndef __max

#define __max(a,b) ((a)>(b) ? (a) : (b))

#endif

chain TreeMax(TreeNode * Cur, reduction(__max) int & MaxResult)

{ // Первая стадия конвейера

 static int DummyMin;

 throw_last(Cur, DummyMin);

 if (Cur==Root) plan_group_parallelize;

 if (Cur->Left) plan_last(Cur->Left, MaxResult);

 if (Cur->Right) plan_last(Cur->Right, MaxResult);

 MaxResult = Cur->Data;

}

chain TreeMin(TreeNode * Cur, reduction(__min) int & MinResult)

{ // Вторая стадия конвейера

 if (Cur==Root) plan_group_parallelize;

 MinResult = Cur->Data;

}

void TreeMinMax(int & Min, int & Max)

{

 Max = 0.0;

 Min = 1000.0;

// Запуск ковейера в параллельном режиме

plan_parallel_chain(0, TreeMax(Root,Max)/4, TreeMin(Root,Min)/4);

}

Пример параллельных вычислений (абстрактный) на конвейере, на кластере

На узле с идентификатором 1 выводит в стандартный поток вывода числа от 0 до 29.

#pragma plan clustered

#include 

using namespace std;

chain A1() throw(int DATA) { // Первая стадия конвейера

  for (int i = 0; i < 30; i++)

      throw_last(i);

}

chain B1(int DATA) { // Вторая стадия конвейера

  cout<

#include 

#include 

using namespace std;

const int N = 10000;

const int M = 600;

const int NF = 20;

reenterable calc_histo(bool init, int np, int * A, soft_transact_array(int) * F, double grain, int k) {

     if (init) { // Формируем план для распараллеливания

         for (int i = 0; i < N; i += np) {

              for (int j = 0; j < np; j++)

                   plan_last(false, np, A, F, grain, i + j);

              plan_group_soft_atomize; // Включаем режим параллельной работы в программной транзакционной памяти

         }

     } else { // Работа, собственно, в программной транзакционной памяти

         if (k < N) {

              int _k = A[k] / grain;

              if (_k >= NF) _k = NF - 1;

              ++(*F)[_k];

         }

     }

}

int main() {

     int * A = new int[N];

     soft_transact_array(int) F(NF);

     srand(184415);

     for (int i = 0; i < N; i++)

         A[i] = rand() % M;

     double grain = 1.0 * M / NF;

     F = 0;

     calc_histo(true, 4, A, &F, grain, 0);

// Гистограмму подсчитали, делаем проверку

     int SF = 0;

     for (int i = 0; i < NF; i++)

         SF += F[i];

     cout << SF;

     delete[] A;

     return 0;

}

#pragma plan clustered

#include >

using namespace std;

cvar(int) * DATA = NULL;

int Counter;

chain A(input_proc Src, int N) {

  int id = plan_linear_num()-1;

  if (Src == empty_proc) {

     (*DATA)++;

     Counter = 1;

     for (int i = 0; i < N; i++)

         if (i != id)

            throw_first(A[i+1], N);

  } else {

     (*DATA)++;

     Counter++;

     if (Counter == N) {

        plan_registered_barrier(topology);

        if (id == N-1) {

           cout<<**DATA<