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

Предлагаю всем, кто заинтересуется, обсудить некоторые основные идеи классического и параллельного программирования в расширении C++, основанном на процедурах/функциях с планированием повторного входа (ПППВ/ФППВ). В минимальном варианте — это процедура или функция, у которой есть статический или динамический план исполнения. План является, вообще говоря, деком, состоящим из элементов-структур, каждая из которых имеет поля, аналогичные по типу и имени параметрам соответствующей функции/процедуры. План может пополняться как извне (до вызова процедуры/функции, с помощью некоторых простых приемов), так и изнутри (это основной подход) с помощью специальных вызовов помещения в начало plan_first(...) или в конец plan_last(...) плана.

ПППВ/ФППВ исполняется последовательно или параллельно, в соответствии с планом. В последовательном режиме она вызывается заново для каждого элемента плана (элемент по умолчанию извлекается из начала плана) и отрабатывает его полностью (до естественного завершения ПППВ/ФППВ или до return). При каждом вызове параметры ПППВ/ФППВ заполняются данными из одноименных полей текущего элемента плана. Как уже было сказано, в процессе исполнения любого из этапов, в план могут вставляться новые этапы, которые будут исполнены ПППВ/ФППВ далее. Для поддержки параллел��ного режима (в простейшем случае) в план помимо этапов могут вставляться специальные маркеры-барьеры, делящие план на группы. С помощью директивы plan_group_parallelize можно включить параллельное исполнение текущей (располагающейся в начале плана) группы, при этом она рассматривается как группа задач (task pool), из которой процессоры/ядра набирают себе на исполнение этапы-задачи. С помощью директивы plan_group_vectorize можно отправить группу задач на векторный вычислитель, такой как многоядерная видеокарта (правда, при этом в оформлении программы могут возникнуть некоторые особенности — например, может потребоваться явно отметить, какие из блоков программы предназначены только для векторного вычислителя, какие — только дя ЦПУ, какие — и для ЦПУ и для векторного
устройства).

Уже такой базовый подход дает, как минимум:

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

Чтобы не затруднять понимание, сразу приведу пару примеров.

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

reenterable[ARR_SIZE] TreeSum(TreeNode * Cur, reduction(+) DataItem & 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;
}

Волновой алгоритм Ли: поиск пути в лабиринте.

const int NL = 10; /* Размер лабиринта */
const unsigned char W = 0xFF; /* Стенка */
/* Лабиринт */
unsigned char Labirint[NL][NL] =
{
 {W,W,W,W,W,W,W,W,W,W},
 {W,0,0,0,0,0,0,0,0,W},
 {W,0,W,W,0,0,W,0,0,W},
 {W,0,0,W,0,0,W,0,0,W},
 {W,0,0,W,W,0,W,0,0,W},
 {W,0,0,0,W,W,W,0,0,W},
 {W,0,0,0,0,0,0,0,0,W},
 {W,0,0,0,0,0,0,0,0,W},
 {W,0,0,0,0,0,0,0,0,W},
 {W,W,W,W,W,W,W,W,W,W},
};
/* Приращения для сдвига относительно текущей клетки влево, вверх, вниз, вправо */
signed char OffsX[4] = {-1,0,0,+1};
signed char OffsY[4] = {0,-1,+1,0};

const char FirstX = 8; /* Точка отправления */
const char FirstY = 8;
const char LastX  = 5; /* Точка назначения */
const char LastY  = 4;

chain[NL*NL] FindLi(unsigned char X, unsigned char Y, int Num) throw(unsigned char X, unsigned char Y)
{
 char Found = 0;

 for (int i=0; !Found && i<4; i++) { /* Просматриваем клетки рядом */
   unsigned char X1 = X+OffsX[i];
   unsigned char Y1 = Y+OffsY[i];
   if (X1>=0 && X1<NL && Y1>=0 && Y1<NL && Labirint[Y1][X1]==0) {
      /* Если клетка еще не пронумерована */
      Labirint[Y1][X1] = Num; /* Нумеруем */
      if (X1==LastX && Y1==LastY) /* Если последняя */
         Found = 1; /* Сигнализируем окончание */
      else /* Если не последняя */
         plan_last(X1,Y1,Num+1); /* Помещаем в очередь */
   }
 }

 if (Found) {
    clear_plan; /* Очищаем план просмотра клеток */
    X = LastX; Y = LastY;
    throw_last(X,Y); /* Помещаем в "стек" точку назначения (последнюю) */
    while (X!=FirstX || Y!=FirstY) { /* Пока не дошли до точки отправления */
      char PointFound = 0; /* Поиск следующей клетки пути */
      for (int i=0; !PointFound && i<4; i++) {
        unsigned char X1 = X+OffsX[i];
        unsigned char Y1 = Y+OffsY[i]; /* Кандидат на следующую клетку пути */
        if (X1>=0 && X1<NL && Y1>=0 && Y1<NL && Labirint[Y1][X1] &&
            Labirint[Y1][X1]<Labirint[Y][X]) {
            /* Если клетка не пуста и имеет меньший номер */
            /* У клеток стенок самые большие номера, в рассмотрение не попадают */
           PointFound = 1;
           throw_first(X1,Y1); /* Добавляем в путь (стек) найденную клетку */
           X = X1; Y = Y1; /* На следующем шаге будем исходить из этой клетки */
        }
      }
    }
 } else if (plan_empty)
    cout<<"NO PATH\n"; /* Не дошли до места назначения */
}

chain[NL*2] OutLi(unsigned char X, unsigned char Y) {
  cout<<"("<<(int)Y<<","<<(int)X<<") ";
}

int main() {
 cout<<"Find the path in the simple labirint (Li algorithm) :\n";
 Labirint[FirstY][FirstX] = 1;
 plan_chain(0,FindLi(FirstX,FirstY,2),OutLi(0,0)); /* Конвейер из двух процедур */
 cout<<"\n";

 return 0;
}

И еще один абстрактный пример работы с многоядерной видеокартой, который приведу без пояснений. Возможно, кому-нибудь будет интересно догадаться, как он работает.

#pragma plan vectorized

#include <iostream>

using namespace std;

#pragma plan common begin

#define N 5
#define threads 100

#pragma plan common end

#pragma plan gpu begin
#define addition 0.01
#pragma plan gpu end

float MUL = 3.14;

float * _OUT = NULL;

reenterable void proc(bool init, int k, _global(1) float * mul, _global(threads) int * sizes, int n, _local(__planned__.n) float * out) {
  int i;
  if (init) {
     for (i = 0; i < threads; i++) {
         plan_last(false, i, mul, sizes, sizes[i], out);
         out += sizes[i];
     }
     plan_group_vectorize(NULL);
  } else
     for (i = 0; i < n; i++) {
         *out = k*(*mul);
#ifdef __GPU__
         *out += addition;
#endif
         out++;
     }
}

int main() {
  int * sizes = new int[threads];

  int NN = 0;
  for (int i = 0; i < threads; i++) {
      sizes[i] = 1 + i % 2;
      NN += sizes[i];
  }

  _OUT = new float[NN];

  cout<<"MAX group size = "<<vector_max_size(NULL)<<endl;

  proc(true, 0, &MUL, sizes, 0, _OUT);

  for (int i = 0; i < NN; i++)
      cout<<_OUT[i]<<" ";
  cout<<endl;

  delete[] _OUT;
  delete[] sizes;

  return 0;
}

Теперь, отмечу, что если рассматривать ПППВ/ФППВ как некий элементарный узел вычислительной топологии (графа) и определить конструкции, позволяющие одной ПППВ/ФППВ пополнять план другой (соседней по графу) ПППВ/ФППВ, то можно дествительно работать с достаточно сложными вычислительными топологиями, причем как в случае общей, так и в случае раздельной памяти (например, на кластере — там передача элементов плана по графу будет выполняться с помощью простых операций передачи по сети). Операции пополнения плана другой ПППВ/ФППВ называются throw_first(...) и throw_last(...). Их параметры определяются параметрами вызова соответствующих принимающих ПППВ/ФППВ. Если какая-либо ПППВ/ФППВ имеет только одного соседа-приемника в топологии (например, в конвейере), то параметры самые обычные. Если соседей-приемников несколько, то один из параметров делается специальным — адресным. Все одноименные (соответствующие одной ПППВ/ФППВ) узлы графа-топологии нумеруются, поэтому в адресном параметре указывается имя принимающей ПППВ/ФППВ за которым в квадратных скобках идет ее номер. Топологии пока предлагается описывать или статически (особыми конструкциями для вектора/конвейера или списками дуг для произвольного г��афа) или полустатически — когда список дуг генерируется специальными (порождающими код) вставками — макромодулями (могут быть, например, написаны по схожей с PHP идеологией — вставки генерируют фрагмент текста программы, можно использовать любой язык в зависимости от задач, хоть PHP, хоть GNU Prolog). Технически не исключена и возможность обычного динамического порождения топологии с помощью вызовов неких функций.

Для полноценной работы дополнительно всегда могут использоваться каналы/ленивые переменные, транзакционная память, барьеры, семафоры и т.п.

Приведу несколько примеров с различными топологиями.

Вычисление на конвейере минимального и максимального элементов дерева.

chain[ARR_SIZE] TreeMax(TreeNode * Cur, reduction(max) DataItem & MaxResult)
{
 static DataItem 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[ARR_SIZE] TreeMin(TreeNode * Cur, reduction(min) DataItem & MinResult)
{
 if (Cur==Root) plan_group_parallelize;
 MinResult = Cur->Data;
}

void TreeMinMax(DataItem & Min, DataItem & Max)
{
 Max.fill(0.0);
 Min.fill(1000.0);
 
 plan_parallel_chain(0,TreeMax(Root,Max),TreeMin(Root,Min));
}

Пример с топологией «иголка с ушком», может применяться для тестирования производительности конкретной реализации

#include <iostream>

using namespace std;

bool stop;

chain A(bool init) throw(bool init, int N) {
  stop = false;
  throw_first(false, 1);
  Sleep(2000);
  stop = true;
}

chain B(bool init, int N) throw(bool init, bool _stop, int N) {
  if (!init) {
     if (stop) throw_first(false, true, N);
     else throw_first(false, false, N+1);
  }
}

chain C(bool init, bool _stop, int N) throw(bool init, int N) {
  if (!init) {
     if (_stop) {
        cout<<N;
        plan_topology_quit(); /* Завершение работы топологии */
     } else throw_first(false, N+1);
  }
}

int main() {
  plan_topology { /* Начало описания топологии */
    plan_parallel_chain(A(true)->B(true,0)->C(true,false,0)); /* Прямые связи топологии */
    plan_parallel_reverse(C(true,false,0)->B(true,0)); /* Одна обратная связь */
  }/3;

  return 0;
}

Все, что описано выше, реализовано в качестве расширения C++ (Planning C). Есть простой демонстрационный транслятор, реализующий, помимо вышеизложенного, еще некоторые интересные вещи.