Здравствуйте, уважаемые читатели.
Предлагаю всем, кто заинтересуется, обсудить некоторые основные идеи классического и параллельного программирования в расширении 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_last(X1,Y1); /* Добавляем в путь (стек) найденную клетку */
X = X1; Y = Y1; /* На следующем шаге будем исходить из этой клетки */
}
}
}
} else if (plan_empty)
cout<<"NO PATHn"; /* Не дошли до места назначения */
}
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). Есть простой демонстрационный транслятор, реализующий, помимо вышеизложенного, еще некоторые интересные вещи.
Автор: Vladimir Pekunov
