Здравствуйте, уважаемые читатели.
Предлагаю всем, кто заинтересуется, обсудить некоторые основные идеи классического и параллельного программирования в расширении C++, основанном на процедурах/функциях с планированием повторного входа (ПППВ/ФППВ). В минимальном варианте — это процедура или функция, у которой есть статический или динамический план исполнения. План является, вообще говоря, деком, состоящим из элементов-структур, каждая из которых имеет поля, аналогичные по типу и имени параметрам соответствующей функции/процедуры. План может пополняться как извне (до вызова процедуры/функции, с помощью некоторых простых приемов), так и изнутри (это основной подход) с помощью специальных вызовов помещения в начало plan_first(...) или в конец plan_last(...) плана.
ПППВ/ФППВ исполняется последовательно или параллельно, в соответствии с планом. В последовательном режиме она вызывается заново для каждого элемента плана (элемент по умолчанию извлекается из начала плана) и отрабатывает его полностью (до естественного завершения ПППВ/ФППВ или до return). При каждом вызове параметры ПППВ/ФППВ заполняются данными из одноименных полей текущего элемента плана. Как уже было сказано, в процессе исполнения любого из этапов, в план могут вставляться новые этапы, которые будут исполнены ПППВ/ФППВ далее. Для поддержки параллельного режима (в простейшем случае) в план помимо этапов могут вставляться специальные маркеры-барьеры, делящие план на группы. С помощью директивы plan_group_parallelize можно включить параллельное исполнение текущей (располагающейся в начале плана) группы, при этом она рассматривается как группа задач (task pool), из которой процессоры/ядра набирают себе на исполнение этапы-задачи. С помощью директивы plan_group_vectorize можно отправить группу задач на векторный вычислитель, такой как многоядерная видеокарта (правда, при этом в оформлении программы могут возникнуть некоторые особенности — например, может потребоваться явно отметить, какие из блоков программы предназначены только для векторного вычислителя, какие — только дя ЦПУ, какие — и для ЦПУ и для векторного
устройства).
Уже такой базовый подход дает, как минимум:
Чтобы не затруднять понимание, сразу приведу пару примеров.
Параллельное суммирование элементов в дереве. Используется редукционный параметр SumResult.
Волновой алгоритм Ли: поиск пути в лабиринте.
И еще один абстрактный пример работы с многоядерной видеокартой, который приведу без пояснений. Возможно, кому-нибудь будет интересно догадаться, как он работает.
Теперь, отмечу, что если рассматривать ПППВ/ФППВ как некий элементарный узел вычислительной топологии (графа) и определить конструкции, позволяющие одной ПППВ/ФППВ пополнять план другой (соседней по графу) ПППВ/ФППВ, то можно дествительно работать с достаточно сложными вычислительными топологиями, причем как в случае общей, так и в случае раздельной памяти (например, на кластере — там передача элементов плана по графу будет выполняться с помощью простых операций передачи по сети). Операции пополнения плана другой ПППВ/ФППВ называются throw_first(...) и throw_last(...). Их параметры определяются параметрами вызова соответствующих принимающих ПППВ/ФППВ. Если какая-либо ПППВ/ФППВ имеет только одного соседа-приемника в топологии (например, в конвейере), то параметры самые обычные. Если соседей-приемников несколько, то один из параметров делается специальным — адресным. Все одноименные (соответствующие одной ПППВ/ФППВ) узлы графа-топологии нумеруются, поэтому в адресном параметре указывается имя принимающей ПППВ/ФППВ за которым в квадратных скобках идет ее номер. Топологии пока предлагается описывать или статически (особыми конструкциями для вектора/конвейера или списками дуг для произвольного графа) или полустатически — когда список дуг генерируется специальными (порождающими код) вставками — макромодулями (могут быть, например, написаны по схожей с PHP идеологией — вставки генерируют фрагмент текста программы, можно использовать любой язык в зависимости от задач, хоть PHP, хоть GNU Prolog). Технически не исключена и возможность обычного динамического порождения топологии с помощью вызовов неких функций.
Для полноценной работы дополнительно всегда могут использоваться каналы/ленивые переменные, транзакционная память, барьеры, семафоры и т.п.
Приведу несколько примеров с различными топологиями.
Вычисление на конвейере минимального и максимального элементов дерева.
Пример с топологией «иголка с ушком», может применяться для тестирования производительности конкретной реализации
Все, что описано выше, реализовано в качестве расширения C++ (Planning C). Есть простой демонстрационный транслятор, реализующий, помимо вышеизложенного, еще некоторые интересные вещи.
Предлагаю всем, кто заинтересуется, обсудить некоторые основные идеи классического и параллельного программирования в расширении 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 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). Есть простой демонстрационный транслятор, реализующий, помимо вышеизложенного, еще некоторые интересные вещи.
Комментарии (11)
maaGames
27.08.2017 16:52Я бы убрал спецификацию исключений, зачем лишний мусор писать?
pekunov Автор
27.08.2017 17:07В данном случае throw(...) — это не указание исключений, а спецификация параметров «принимающей» процедуры при работе в топологии. Эту часть конструкции можно не писать, если список параметров «передающей» процедуры совпадает со списком параметров «принимающей» процедуры.
maaGames
27.08.2017 17:12Т.е. это будет обработано и вырезано препроцессором? А если в коде есть функции со спецификацией исключений, то её не сломает препроцессинг?
pekunov Автор
27.08.2017 17:52Да, обработано и вырезано. Что же касается пересечения со спецификацией исключения, то теоретически путаницы не будет, поскольку спецификация исключений может быть: throw(), throw(...), throw(тип), а спецификация параметров принимающей процедуры: throw(тип имя [, тип имя ...]). Однако в текущей демо-версии транслятора путаница возникнуть может (я проверю, если есть — поправлю).
kalaider
Честно говоря, не очень понятно, зачем такие сложности — расширение языка. Да и чем подход радикально отличается от "классического" распараллеливания на общем пуле потоков (кроме того, что это делается вручную, а не автоматически)? Какой-то выделенной поддержкой векторных вычислителей и тем, что все детали реализации очереди сокрыты от пользователя? Поясните, пожалуйста.
pekunov Автор
Классическое распараллеливание на общем пуле потоков, обычно, тоже требует указания одной-двух директив (как в OpenMP) или, например, обертки Вашего кода в некий класс-пул, или вызова специальных функций, иными словами, обычно требуются дополнительные «ручные» манипуляции. С этой точки зрения предлагаемый подход, как минимум, не сложнее. При этом он, думаю, более органичен (и, не исключено, потенциально более эффективно реализуем компилятором) для распараллеливания обработки таких сложных структур данных, как граф (сеть, дерево и т.д.), а еще, возможно, больших таблиц. Кроме того, да, действительно, один и тот же прием программирования (с не очень большими декларативными изменениями) используется, вообще говоря, как для обычных многоядерных ЦПУ, так и для многоядерных видеокарт — это повышает переносимость кода и облегчает гибридное распараллеливание CPU+GPU. Применение же топологий позволяет дополнительно организовать распараллеливание на кластере. Все это, в комплексе, думаю оправдывает подход в смысле распараллеливания. Что же касается последовательного программирования, то там ПППВ/ФППВ — просто еще один способ записи некоторых алгоритмов, позволяющий не заботиться, например, о явном вводе переменной-очереди. Может быть, в таком случае это уже «синтаксический сахар».
kalaider
Сразу скажу, что я не являюсь сколь-нибудь квалифицированным специалистом по части "гетерогенных" вычислений (на кластере, на GPU и т.д.). Вот несколько мыслей, которые мне удалось из прочитенного и понятого сформулировать.
"Инвазивный подход" требует изменения синтаксиса языка, наличие транслятора/препроцессора/особую поддержку в компиляторе. Это снижает управляемость тем, что происходит за занавесом, со стороны программиста. Плохо продуманные синтаксические конструкции могут породить другие синтаксические конструкции, чтобы закрыть дыры в первых.
Как уже отмечалось, ручное распараллеливание дает большую управляемость процессом, потенциально более расширяемо, в т.ч. и на поддержку кластерных и векторных вычислений. При наличии хорошего API тоже можно все записывать единообразно.
По поводу оптимизаций компилятора сказать ничего не могу, но как-то интуитивно — особой разницы не будет. Поле для оптимизаций ведь у нас не очень большое — мне только стек и видится (первый пример в статье, например). А эмуляция стека в коде и "нативный" стек в принципе отличаются только тем, что при переполнении стековой памяти легко получить stack overflow. Поправьте, если несу бредятину)
pekunov Автор
«Инвазивный подход» все же упрощает распараллеливание и, экономя время и силы на программирование, при грамотной реализации в компиляторе будет вполне адекватен. Что же касается повышения эффективности/управляемости путем ручного распараллеливания, то я, в общем, конечно согласен. Предложенный подход не отрицает сосуществования с такими ручными средствами, они даже приветствуются иногда (в дополнение), если требуется выжать все, что только возможно.
Что же касается организации компилятором работы в кластере (при работе с топологиями из ПППВ), то у меня подход вполне стандартный: программа в неизменном виде исполняется на каждом узле, каждый узел внутри программы идентифицируется номером, в зависимости от номера программой выполняется тот или иной фрагмент кода. В качестве низкоуровневого интерфейса транслятор использует MPI.
Что же касается оптимизаций в компиляторе, то сравню с OpenMP. Например, если говорить о реализации обработки дерева, то можно, конечно написать на OpenMP 3.0 рекурсивную функцию, которая будет порождать подзадачи и затем ставить барьер на ожидание их завершения. Это две директивы, при этом транслятор, скорее всего, будет генерировать для каждой из них независимый код. В предложенном подходе можно написать ПППВ, причем потребуется одна директива распараллеливания, причем компилятор работает с ПППВ/ФППВ стандартным образом, который при желании можно попытаться довести до совершенства. Поэтому мне кажется, что в случае OpenMP у транслятора меньше информации для наиболее оптимальной организации параллельной работы.
kalaider
Ну, возможно, Вы и правы. За счет сужения области применения получаем более оптимальную трансляцию. (Но, опять же, не компиляцию.)
Честно говоря, я всегда был убежден, что синтаксические конструкции — просто синтаксический сахар. Те же
async/awaitв Boost прекрасно "эмулируются" переключением контекстов (Boost.Context)...Надо будет как-нибудь попробовать Ваш инструмент в деле, чтобы не разглагольствовать попусту)
kalaider
Да, хотелось бы взглянуть на результат работы. Вы его описываете-описываете) Надо же пощупать. Что же это за такие "еще некоторые интересные вещи"?
pekunov Автор
Работоспособную (хотя и не последнюю) версию транслятора можно скачать и посмотреть на моем сайте в разделе «Программы». Она написана на Free Pascal, простовата и не очень удобна, работает из командной строки (Linux, Windows), генерирует C++-код, который при компиляции требует OpenMP, а также может (в зависимости от транслируемой программы) требовать MPI и/или OpenCL. Что же касается интересностей, то это немного порождающего программирования, некоторые полезные применения ПППВ/ФППВ при использовании статического плана, «отчуждаемый» план и еще некоторые тонкости. Подробно (хотя и несколько тяжеловесно), если захотите, можно посмотреть в книге.