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

Моя цель - предложение широкого ассортимента товаров и услуг на постоянно высоком качестве обслуживания по самым выгодным ценам.

Прежде чем перейти к статье, хочу вам представить, экономическую онлайн игру Brave Knights, в которой вы можете играть и зарабатывать. Регистируйтесь, играйте и зарабатывайте!

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

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

}

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

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

Источник: https://habr.com/ru/post/645533/


Интересные статьи

Интересные статьи

Обучать профессионалов намного сложнее, чем новичков. Если новичок – это чистый лист, то профи – сам как живой учебник, наполненный знаниями, устоявшимися взглядами и инт...
Сразу оговоримся, что в этой публикации мы не будем затрагивать вопросы подходов к созданию полномасштабных приложений для Web, подразумевающих наличие крупной кодовой базы, заставляющей ...
О том, что такое база KDB+, язык программирования Q, какие у них есть сильные и слабые стороны, можно прочитать в моей предыдущей статье и кратко во введении. В статье же мы реализуем на Q сервис...
В первой части статьи про язык Arend мы рассматривали простейшие индуктивные типы, рекурсивные функции, классы и множества. 2. Сортировка списков в Arend 2.1 Упорядоченные списки в Arend Опр...
В Интернете огромное количество информации по созданию Wi-Fi точек доступа на базе одноплатного ПК Raspberry. Как правило, подразумевается использование родной для «малинки» операционной системы ...