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

Хочу написать здесь об одном из своих проектов -- языке 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, last);
}

/* Вызов: 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 <iostream>

using namespace std;

chain A1() throw(int DATA) { // Первая стадия конвейера
  for (int i = 0; i < 30; i++)
      throw_last(i);
}

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

int main() {
  int IDs[2] = {0,1}; // MPI-Идентификаторы узлов, на которых будет запущен конвейер

  clustered(IDs) plan_parallel_chain(0, A1(), B1(0));

  return 0;
}

Немного о транзакционной памяти

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

#include <stdlib.h>

#include <iostream>

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;
}

Еще немного о параллельных вычислениях

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

Также в языке есть некоторые менее стандартные средства для работы на кластерных системах, а именно – атомарные глобальные переменные, семафор, каналы и барьер. Приведу (без комментариев) небольшой, тоже достаточно абстрактный пример работы с атомарной глобальной переменной DATA на кластерной топологии «клика».

#pragma plan clustered

#include <iostream>>

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<<endl;
           plan_topology_quit();
        }
     }
  }
}

int main() {
  const int N = 5;

  DATA = new cvar(int)(1);

  if (plan_cluster_id() == 0) *DATA = 0;

  int IDS[N];
  for (int i = 0; i < N; i++)
      IDS[i] = i;

  clustered(IDS) clique(N)/N;

  delete DATA;

  return 0;
}

Вместо заключения

В приведенных примерах был сделан акцент на параллельном программировании, поскольку, на мой взгляд, это самые интересные возможности языка. Более подробно (хотя и более сложным стилем) можно почитать про возможности языка в документации, выложенной в репозитории