Здравствуйте, уважаемые читатели.
Хочу написать здесь об одном из своих проектов — языке 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/
Добавить комментарий