Прогресс не стоит на месте: OpenMP 4.5

Всё течет, всё меняется, и OpenMP продолжает активно развиваться. Почти три года назад стандарт стал поддерживать не только параллелизм по задачам, но и по данным (векторизацию), про что я подробно писал ^[1]. Самое время посмотреть, что появилось в последней версии, выпущенной в ноябре 2015, и что уже поддерживается на данный момент в компиляторах от Intel. Ну что, приступим!

Конструкция taskloop

Рассмотрим некоторый цикл, который мы хотим распараллелить по задачам с помощью OpenMP. Раньше мы бы просто написали директиву parallel for перед ним, и нашли своё счастье. Что-то вроде такого:

#pragma omp parallel for
for (int j = 0; j<n; j++)
  do_useful_job(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). Про эту память можно легко найти множество постов, например этот ^[2]. В целом, идея достаточно интересная и может давать прирост производительности при определённых условиях. Стоит отметить, что в приложениях могут встречаться различные требования к механизму синхронизации: в одних случаях конфликты при обращении к общим данным возникают достаточно часто, в других мы защищаем системные вызовы (например, операции ввода-вывода), или вообще добавляем синхронизацию для перестраховки, потому что почти никогда не встречаются конфликты (хэш-карты). Хотелось бы иметь возможность выбирать реализацию объектов синхронизации в зависимости от наших необходимостей.

Но, как нам известно, если просто использовать 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’а (выгрузке вычислений на различные ускорители).
Именно эта часть претерпела существенные изменения, которые могут повлиять даже на компилируемость кода, написанного с использованием прошлого стандарта. Надеюсь, эта тема будет интересна и тогда я обязательно напишу продолжение. Как говорится, «продолжение следует…».

Автор: Intel

Источник ^[3]