Прогрес не стоїть на місці: OpenMP 4.5



Все тече, все змінюється, і OpenMP продовжує активно розвиватися. Майже три роки тому стандарт став підтримувати не тільки паралелізм завдань, але і за даними (векторизацію), про що я докладно писав. Саме час подивитися, що з'явилося в останній версії, випущеної в листопаді 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). Про цю пам'ять можна легко знайти безліч постів, наприклад . В цілому, ідея досить цікава і може давати приріст продуктивності при певних умовах. Варто відзначити, що в додатках можуть зустрічатися різні вимоги до механізму синхронізації: в одних випадках конфлікти при зверненні до загальних даних виникають досить часто, в інших ми захищаємо системні виклики (наприклад, операції вводу-виводу), або взагалі додаємо синхронізацію для перестраховки, тому що майже ніколи не зустрічаються конфлікти (хеш-карти). Хотілося б мати можливість вибирати реалізацію об'єктів синхронізації в залежності від наших необхідностей.

Але, як нам відомо, якщо просто використовувати 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'а (вивантаженні обчислень на різні прискорювачі).
Саме ця частина зазнала істотні зміни, які можуть вплинути навіть на компилируемость коду, написаного з використанням минулого стандарту. Сподіваюся, ця тема буде цікава і тоді я обов'язково напишу продовження. Як кажуть, «далі буде...».
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.