Прежде чем перейти к статье, хочу вам представить, экономическую онлайн игру 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;
}Вместо заключения
В приведенных примерах был сделан акцент на параллельном программировании, поскольку, на мой взгляд, это самые интересные возможности языка. Более подробно (хотя и более сложным стилем) можно почитать про возможности языка в документации, выложенной в репозитории
