Прогресс не стоит на месте: OpenMP 4.5
Всё течет, всё меняется, и OpenMP продолжает активно развиваться. Почти три года назад стандарт стал поддерживать не только параллелизм по задачам, но и по данным (векторизацию), про что я подробно писал. Самое время посмотреть, что появилось в последней версии, выпущенной в ноябре 2015, и что уже поддерживается на данный момент в компиляторах от Intel. Ну что, приступим!
Конструкция taskloop
Рассмотрим некоторый цикл, который мы хотим распараллелить по задачам с помощью OpenMP. Раньше мы бы просто написали директиву parallel for перед ним, и нашли своё счастье. Что-то вроде такого:
#pragma omp parallel for
for (int j = 0; jНо «всё меняется когда приходят они» — новые стандарты и возможности. Теперь появилась возможность не просто отдавать на выполнение всем потокам какие-то куски итераций, а создавать для них задачи (task«и), которые будут распределяться по потокам. Реализуется это с помощью конструкции taskloop:
#pragma omp taskloop
Написав эту директиву перед циклом for, мы тем самым говорим, что итерации этого цикла нужно поделить на куски, и для выполнения каждого из них создать задачу. Далее эти задачи будут выполняться потоками, но при этом нет прямой привязки выполнения какого-то куска итераций конкретным потоком. При этом мы можем контролировать число задач с помощью клаузы num_tasks, а также размер самих кусков через grainsize. Если мы зададим 32 задачи с помощью num_tasks (32), то при числе итераций равном 1024, каждая будет выполнять по 32 итерации цикла. Честно говоря, и в предыдущем стандарте OpenMP 4.0 можно было сделать это:
#pragma omp taskgroup
{
for (int tmp = 0; tmp < 32; tmp++)
#pragma omp task
for (int i = tmp * 32; i < tmp * 32 + 32; i++)
do_useful_job(i);
}
Но теперь наш код будет ещё проще, особенно если циклы вложенные или используются итераторы.
С помощью grainsize мы можем задать число итераций, которое должно выполняться одной задачей, и, таким образом, число задач будет вычислено автоматически. Возникает вопрос, что же лучше использовать — «классический» parallel for, или конструкцию taskloop?
Если ваш код не использует работу с задачами, то вряд ли будет иметь смысл заменять parallel for на taskloop. Преимущество будет проявляться при несбалансированности итераций циклов и при наличии других задач, которые могут выполняться параллельно с итерациями. Вот пример из свежей документации к OpenMP 4.5:
void long_running_task(void);
void loop_body(int i, int j);
void parallel_work(void) {
int i, j;
#pragma omp taskgroup
{
#pragma omp task
long_running_task(); // can execute concurrently
#pragma omp taskloop private(j) grainsize(500) nogroup
for (i = 0; i < 10000; i++) { // can execute concurrently
for (j = 0; j < i; j++) {
loop_body(i, j);
}
}
}
}
Здесь мы создаём задачу, которая будет выполнять долгую по времени выполнения функцию long_running_task, и в этой же группе задач (taskgroup) выполняем итерации цикла с помощью taskloop, «отдав» каждой задаче по 500 итераций. Функция будет выполняться, возможно, параллельно с итерациями цикла. Клауза nogroup позволяет не создавать неявную группу (taskgroup) для конструкции taskloop, таким образом мы не выйдем из функции parallel_work до тех пор, пока не выполняться все задачи (с итерациями цикла и функцией long_running_task).
Стоит отметить, что работа с задачами эффективнее за счёт того, что не будет возникать ситуации oversubscription, при которой используется слишком большое количество логических потоков, что существенно повышает издержки в операционной системе из-за того, что ей приходится вводить повременной доступ к аппаратным ресурсам. Работая с физическими потоками напрямую, разработчик берет на себя ответственность за соблюдение соответствия параллелизма в приложении и имеющихся аппаратных ресурсов. Кстати, ещё стандарт OpenMP 3.0 дал возможность работать с задачами, а не потоками.
Яркий пример, который показывает необходимость в задачах — это использование библиотечных функций в параллельных регионах. Скажем, той же dgemm из MKL, которая может быть как последовательной, так и параллельной. В итоге может получиться так, что мы будем работать с большим числом логических потоков, что, вполне вероятно, отрицательно скажется на производительности.
Функционал taskloop уже поддерживается компилятором Intel. Кстати, появилась и возможность задавать задачам разный приоритет через клаузу priority. В этом случае рантайм будет выполнять задачи с большим приоритетом в первую очередь. Правда, в компиляторе этого пока ещё нет.
Параллелизм doacross
Существует ряд алгоритмов, у которых имеются хорошо структурированные итерационные зависимости. Примером могут быть многие алгоритмы из трафаретных вычислений, применяемые в научных расчётах при решении дифференциальных уравнений методом конечных разностей, в задачах вычислительной механики.
В этих случаях нам может понадобиться распараллелить данные циклы, но при этом «сложность» вычислений на каждой итерации должна быть существенной, чтобы потоки не тратили большую часть времени на ожидание друг друга.
В общем случае, порядок, в котором выполняются итерации, не определён. Но ещё в стандарте 4.0 появилась конструкция ordered, позволяющая указать определённые части цикла, которые должны выполняться в последовательном порядке. Вот простой пример, когда это может быть полезно:
#pragma omp for ordered schedule(dynamic)
for(int n=0; n<100; ++n)
{
files[n].compress();
#pragma omp ordered
send(files[n]);
}
В цикле параллельно «сжимаются» 100 файлов, но их «пересылка» осуществляется строго в возрастающей последовательности. Если один из потоков выполнил сжатие 10 го файла, но 9ый ещё не был отослан, то поток будет ожидать отправки и не будет начинать компрессию нового. Таким образом, все потоки работают параллельно до части ordered, где выполнение происходит последовательно. Это будет работать хорошо в случае, если код вне ordered блока выполняется существенное время.
В новом стандарте, и компилятор от Intel тоже поддерживает данную «фичу», теперь есть возможность с помощью ordered и дополнительной клаузы depend обозначить хорошо структурированные зависимости в циклах.
#pragma omp for ordered(2)
for (int i = 0; i < M; i++)
for (int j = 0; j < N; j++)
{
a[i][j] = foo (i, j);
#pragma omp ordered depend (sink: i - 1, j) depend (sink: i, j - 1)
b[i][j] = bar (a[i][j], b[i - 1][j], b[i][j - 1]);
#pragma omp ordered depend (source)
baz (a[i][j], b[i][j]);
}
Посмотрим на этот пример. В данном случае только внешний цикл распределяется для выполнения по потокам. Директива ordered depend (sink) блокирует выполнение итераций i, j до тех пор, пока выполнение в итерациях i-1, j и i, j-1 не достигнет следующей директивы ordered depend (source).
В данном примере компилятор проигнорирует depend (sink: i, j — 1), так как только итерации внешнего цикла распределяется по потокам, а значит, при выполнении итерации i, j, итерация i, j-1 гарантированно выполнена.
Кстати, для директивы ordered теперь можно указывать и клаузу simd для использования в циклах при векторизации:
#pragma omp ordered simd
В этом случае можно указать часть кода в SIMD цикле, которая будет выполняться в лексическом порядке. Таким образом, задаётся небольшой участок, который не будет векторизован.
Общие данные
Ссылки C++ раньше разрешалось использовать только в клаузах shared, но сейчас нет этого ограничения и они вполне себе могут быть и в клаузах private/firstprivate.
Другое ожидаемое улучшение связано с редукциями в циклах. Напомню, что они позволяют решать проблему синхронизации:
int sum = 0;
#pragma omp parallel for reduction(+:sum)
for (int i = 0; i < N; i++)
sum += val[i];
Например, в данном случае мы вычислим значение переменной sum корректно, создав в каждом потоке свою копию, и просуммировав полученные значения для каждого из них в конце. Для этого используется клауза reduction, с указанием оператора и переменной.
Так вот редукции нельзя было делать для элементов массива. То есть если sum является массивом размера N, и мы хотели бы сделать редукцию для sum[i], то нужно самому придумывать что-то вроде этого (возможно, не самое лучшее решение):
#pragma omp parallel
{
int sum_private[N];
#pragma omp for
for (int i=0 ; i < N ; i++ )
{
for (int j=0; j <=N; j++)
{
sum_private[i] += val[j];
}
}
#pragma omp critical
{
for(int i=0; i < N; i++)
sum[i] += sum_private[i];
}
}
В стандарте 4.0 стало возможным создавать свои редукции (user defined reduction), но для этого нам нужно было создавать свой тип данных (обертку) — структуру или класс:
struct user_def_red { int sum[10]; };
Определять операцию, например, сложения:
void add_user_def_red(struct user_def_red * x, struct user_def_red * y)
{
int i;
for (i = 0; i<10; i++)
x->sum[i] += y->sum[i];
}
И объявлять саму редукцию:
#pragma omp declare reduction(Add_test: struct user_def_red: \
add_user_def_red(&omp_out, &omp_in)) initializer( \
omp_priv={{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}} )
И вот только после этого, можно было использовать массив в качестве переменной для редукции:
#pragma omp parallel for reduction(Add_test: Sum_red)
for (n = 0; n < 10; ++n)
for (m = 0; m <= n; ++m)
Sum_red.sum[n] += val[m];
Стоит отметить, что последняя версия компилятора Intel 17.0 Update 1 всё ещё «не осилила» поддержку редукций массивов для С++.
Кроме этого, стандарт теперь позволяет объявлять нестатические члены класса как private внутри функций-членов класса (тоже нестатических), используя только его имя, то есть без явного обращения с помощью указателя this).
Средства синхронизации
Современные процессоры поддерживают транзакционную память, например IBM BlueGene/Q или Intel TSX (Intel Transactional Synchronization Extensions). Про эту память можно легко найти множество постов, например этот. В целом, идея достаточно интересная и может давать прирост производительности при определённых условиях. Стоит отметить, что в приложениях могут встречаться различные требования к механизму синхронизации: в одних случаях конфликты при обращении к общим данным возникают достаточно часто, в других мы защищаем системные вызовы (например, операции ввода-вывода), или вообще добавляем синхронизацию для перестраховки, потому что почти никогда не встречаются конфликты (хэш-карты). Хотелось бы иметь возможность выбирать реализацию объектов синхронизации в зависимости от наших необходимостей.
Но, как нам известно, если просто использовать OpenMP директивы для синхронизации, например, такие как critical, или работать с механизмом замков через функции omp_init_lock, omp_set_lock и omp_unset_lock, то вряд ли компилятор создаст код, использующий транзакционную память и соответствующие инструкции.
Теперь на уровне стандарта появилась возможность указывать, какие типы объектов синхронизации мы хотим использовать. Делается это с помощью новых функций «с подсказками»:
omp_init_lock_with_hint(omp_lock_t *lock, omp_lock_hint_t hint)
omp_init_nest_lock_with_hint(omp_nest_lock_t *lock, omp_lock_hint_t hint)
Через аргумент hint мы можем задать тип синхронизации, который нас удовлетворяет:
omp_lock_hint_none
omp_lock_hint_uncontended
omp_lock_hint_contended
omp_lock_hint_nonspeculative
omp_lock_hint_speculative
Таким образом, если нам необходимо использовать транзакционную память, мы задаём hint как omp_lock_hint_speculative, а компилятор будет генерировать соответствующие инструкции. Для компилятора Intel мы будем использовать Intel TSX как реализацию:
void example_locks()
{
omp_lock_t lock;
omp_init_lock_with_hint(&lock, omp_hint_speculative);
#pragma omp parallel
{
omp_set_lock(&lock);
do_some_protected_job();
omp_unset_loc(&lock);
}
}
Можно и для критической секции задавать тип через клаузу hint, при этом она должна иметь явное имя:
void example_critical_with_hint()
{
#pragma omp parallel for
for (int i=0; I < N; i++)
{
Data d= get_some_data(i);
#pragme omp critical (HASH) hint(omp_hint_speculative)
hash.insert(d);
}
}
Что осталось «за кадром»?
Кроме всего сказанного, в стандарте появилось много мелких улучшений, которые делают наши жизнь лучше. Например, возможность задавать в клаузе linear для #pragma omp declare simd дополнительных опций val, uval и ref. Это позволяет нам явно указать, что же на самом деле «линейно» — сами адреса или значения. Особенно актуально это будет для разработчиков на Фортране, где аргументы функций передаются по ссылке, а не значению, что приводило к потере производительности при использовании директивы declare simd из-за генерации gather инструкций.
Я умышленно не стал ничего говорить об огромной теме, которая заслуживает отдельного внимания — инструменты OpenMP для offload«а (выгрузке вычислений на различные ускорители).
Именно эта часть претерпела существенные изменения, которые могут повлиять даже на компилируемость кода, написанного с использованием прошлого стандарта. Надеюсь, эта тема будет интересна и тогда я обязательно напишу продолжение. Как говорится, «продолжение следует…».
