Интернет Университет
Суперкомпьютерных технологий
Конструкции распределения работы
Учебный курс
Параллельное программирование с
OpenMP
Бахтин В.А., кандидат физ.-мат. наук,
заведующий сектором,
Институт прикладной математики им.
М.В.Келдыша РАН
Содержание
Распределение витков циклов.
Циклы с зависимостью по данным. Организация конвейерного
выполнения для циклов с зависимостью по данным.
Распределение нескольких структурных блоков между нитями
(директива SECTION).
Выполнение структурного блока одной нитью (директива
SINGLE).
Распределение операторов одного структурного блока между
нитями (директива WORKSHARE).
Москва, 2015 г.
Параллельное программирование с OpenMP: Конструкции
распределения работы © Бахтин В.А.
2 из 42
Вычисление числа
1
4.0
(1+x )
4.0
2
dx =
F(x) = 4.0/(1+x2)
0
Мы можем
аппроксимировать интеграл
как сумму прямоугольников:
2.0
N
F(x )x
i
i=0
0.0
Москва, 2015 г.
X
1.0
Где каждый прямоугольник
имеет ширину x и высоту
F(xi) в середине интервала
Параллельное программирование с OpenMP: Конструкции
распределения работы © Бахтин В.А.
3 из 42
Вычисление числа . Последовательная
программа.
#include
int main ()
{
int n =100000, i;
double pi, h, sum, x;
h = 1.0 / (double) n;
sum = 0.0;
for (i = 1; i <= n; i ++)
{
x = h * ((double)i - 0.5);
sum += (4.0 / (1.0 + x*x));
}
pi = h * sum;
printf("pi is approximately %.16f”, pi);
return 0;
}
Москва, 2015 г.
Параллельное программирование с OpenMP: Конструкции
распределения работы © Бахтин В.А.
4 из 42
Вычисление числа на OpenMP
#include
#include
int main ()
{
int n =100000, i;
double pi, h, sum, x;
h = 1.0 / (double) n;
sum = 0.0;
#pragma omp parallel default (none) private (i,x) shared (n,h) reduction(+:sum)
{
int id = omp_get_thread_num();
int numt = omp_get_num_threads();
for (i = id + 1; i <= n; i=i+numt)
{
x = h * ((double)i - 0.5);
sum += (4.0 / (1.0 + x*x));
}
}
pi = h * sum;
printf("pi is approximately %.16f”, pi);
return 0;
}
Москва, 2015 г.
Параллельное программирование с OpenMP: Конструкции
распределения работы © Бахтин В.А.
5 из 42
Вычисление числа на OpenMP
#include
#include
int main ()
{
int n =100000, i;
double pi, h, sum, x;
h = 1.0 / (double) n;
sum = 0.0;
#pragma omp parallel default (none) private (i,x) shared (n,h) reduction(+:sum)
{
#pragma omp for schedule (static, 1)
for (i = 1; i <= n; i++)
{
x = h * ((double)i - 0.5);
sum += (4.0 / (1.0 + x*x));
}
}
pi = h * sum;
printf(“pi is approximately %.16f”, pi);
return 0;
}
Москва, 2015 г.
Параллельное программирование с OpenMP: Конструкции
распределения работы © Бахтин В.А.
6 из 42
Вычисление числа на OpenMP
#include
int main ()
{
int n =100000, i;
double pi, h, sum, x;
h = 1.0 / (double) n;
sum = 0.0;
#pragma omp parallel default (none) private (i,x) shared (n,h) reduction(+:sum)
{
int iam = omp_get_thread_num();
int numt = omp_get_num_threads();
int start = iam * n / numt + 1;
int end = (iam + 1) * n / numt;
if (iam == numt -1) end = n;
for (i = start; i <= end; i++)
{
x = h * ((double)i - 0.5);
sum += (4.0 / (1.0 + x*x));
}
}
pi = h * sum;
printf(“pi is approximately %.16f”, pi);
return 0;
}
Москва, 2015 г.
Параллельное программирование с OpenMP: Конструкции
распределения работы © Бахтин В.А.
7 из 42
Вычисление числа на OpenMP
#include
#include
int main ()
{
int n =100000, i;
double pi, h, sum, x;
h = 1.0 / (double) n;
sum = 0.0;
#pragma omp parallel default (none) private (i,x) shared (n,h) reduction(+:sum)
{
#pragma omp for schedule (static)
for (i = 1; i <= n; i++)
{
x = h * ((double)i - 0.5);
sum += (4.0 / (1.0 + x*x));
}
}
pi = h * sum;
printf(“pi is approximately %.16f”, pi);
return 0;
}
Москва, 2015 г.
Параллельное программирование с OpenMP: Конструкции
распределения работы © Бахтин В.А.
8 из 42
Распределение витков цикла
#pragma omp for [клауза[[,]клауза] ... ]
for (init-expr; test-expr; incr-expr) структурный блок
где клауза одна из :
private(list)
firstprivate(list)
lastprivate(list)
reduction(operator: list)
schedule(kind[, chunk_size])
collapse(n)
ordered
nowait
Москва, 2015 г.
Параллельное программирование с OpenMP: Конструкции
распределения работы © Бахтин В.А.
9 из 42
Распределение витков цикла
init-expr : var = loop-invariant-expr1
| integer-type var = loop-invariant-expr 1
| random-access-iterator-type var = loop-invariant-expr 1
| pointer-type var = loop-invariant-expr 1
relational-op: <
test-expr:
| <=
var relational-op loop-invariant-expr2
| loop-invariant-expr2 relational-op var | >
| >=
incr-expr: ++var
var: signed or unsigned integer type
| var++
| random access iterator type
| --var
| pointer type
| var -| var += loop-invariant-integer- expr
| var -= loop-invariant-integer- expr
| var = var + loop-invariant-integer- expr
| var = loop-invariant-integer- expr + var
| var = var - loop-invariant-integer- expr
Москва, 2015 г.
Параллельное программирование с OpenMP: Конструкции
распределения работы © Бахтин В.А.
10 из 42
Parallel Random Access Iterator Loop (OpenMP 3.0)
#include
void iterator_example()
{
std::vector
std::vector
#pragma omp parallel for default(none) shared(vec)
for (it = vec.begin(); it < vec.end(); it++)
{
// do work with *it //
}
}
Москва, 2015 г.
Параллельное программирование с OpenMP: Конструкции
распределения работы © Бахтин В.А.
11 из 42
Использование указателей в цикле (OpenMP 3.0)
void pointer_example ()
{
char a[N];
#pragma omp for default (none) shared (a,N)
for (char *p = a; p < (a+N); p++ )
{
use_char (p);
}
}
for (char *p = a; p != (a+N); p++ ) - ошибка
Москва, 2015 г.
Параллельное программирование с OpenMP: Конструкции
распределения работы © Бахтин В.А.
12 из 42
Вложенность конструкций распределения работы
void work(int i, int j) {}
void wrong1(int n)
{
#pragma omp parallel default(shared)
{
int i, j;
#pragma omp for
for (i=0; i < n; i++) {
/* incorrect nesting of loop regions */
#pragma omp for
for (j=0; j < n; j++)
work(i, j);
}
}
}
Москва, 2015 г.
Параллельное программирование с OpenMP: Конструкции
распределения работы © Бахтин В.А.
13 из 42
Вложенность конструкций распределения работы
void work(int i, int j) {}
void good_nesting(int n)
{
int i, j;
#pragma omp parallel default(shared)
{
#pragma omp for
for (i=0; i < n; i++) {
#pragma omp parallel shared(i, n)
{
#pragma omp for
for (j=0; j < n; j++)
work(i, j);
}
}
}
}
Москва, 2015 г.
Параллельное программирование с OpenMP: Конструкции
распределения работы © Бахтин В.А.
14 из 42
Распределение витков многомерных циклов. Клауза
collapse (OpenMP 3.0)
void work(int i, int j) {}
void good_collapsing(int n)
{
int i, j;
#pragma omp parallel default(shared)
{
#pragma omp for collapse (2)
for (i=0; i
work(i, j);
}
}
}
Клауза collapse:
collapse (положительная целая константа)
Москва, 2015 г.
Параллельное программирование с OpenMP: Конструкции
распределения работы © Бахтин В.А.
15 из 42
Распределение витков многомерных циклов. Клауза
collapse (OpenMP 3.0)
void work(int i, int j) {}
void error_collapsing(int n)
{
int i, j;
#pragma omp parallel default(shared)
{
#pragma omp for collapse (2)
for (i=0; i
// Ошибка
for (j=0; j < n; j++)
work(i, j);
}
}
}
Клауза collapse может быть использована только для распределения
витков тесно-вложенных циклов.
Москва, 2015 г.
Параллельное программирование с OpenMP: Конструкции
распределения работы © Бахтин В.А.
16 из 42
Распределение витков многомерных циклов. Клауза
collapse (OpenMP 3.0)
void work(int i, int j) {}
void error_collapsing(int n)
{
int i, j;
#pragma omp parallel default(shared)
{
#pragma omp for collapse (2)
for (i=0; i
// Ошибка
work(i, j);
}
}
}
Клауза collapse может быть использована только для распределения
витков циклов с прямоугольным индексным пространством.
Москва, 2015 г.
Параллельное программирование с OpenMP: Конструкции
распределения работы © Бахтин В.А.
17 из 42
Распределение витков цикла. Клауза schedule
Клауза schedule:
schedule(алгоритм планирования[, число_итераций])
Где алгоритм планирования один из:
schedule(static[, число_итераций]) - статическое планирование;
schedule(dynamic[, число_итераций]) - динамическое планирование;
schedule(guided[, число_итераций]) - управляемое планирование;
schedule(runtime) - планирование в период выполнения;
schedule(auto) - автоматическое планирование (OpenMP 3.0).
#pragma omp parallel for private(tmp) shared (a) schedule (runtime)
for (int i=0; i
tmp = a[i][j];
a[i][j]=a[j][i];
a[j][i]=tmp;
}
Москва, 2015 г.
Параллельное программирование с OpenMP: Конструкции
распределения работы © Бахтин В.А.
18 из 42
Распределение витков цикла. Клауза schedule
#pragma omp parallel for schedule(static)
for(int i = 1; i <= 100; i++)
Результат выполнения программы на 4-х ядерном процессоре будет
следующим:
Поток 0 получает право на выполнение итераций 1-25.
Поток 1 получает право на выполнение итераций 26-50.
Поток 2 получает право на выполнение итераций 51-75.
Поток 3 получает право на выполнение итераций 76-100.
Москва, 2015 г.
Параллельное программирование с OpenMP: Конструкции
распределения работы © Бахтин В.А.
19 из 42
Распределение витков цикла. Клауза schedule
#pragma omp parallel for schedule(static, 10)
for(int i = 1; i <= 100; i++)
Результат выполнения программы на 4-х ядерном процессоре будет
следующим:
Поток 0 получает право на выполнение итераций 1-10, 41-50, 81-90.
Поток 1 получает право на выполнение итераций 11-20, 51-60, 91-100.
Поток 2 получает право на выполнение итераций 21-30, 61-70.
Поток 3 получает право на выполнение итераций 31-40, 71-80.
Москва, 2015 г.
Параллельное программирование с OpenMP: Конструкции
распределения работы © Бахтин В.А.
20 из 42
Распределение витков цикла. Клауза schedule
#pragma omp parallel for schedule(dynamic, 15)
for(int i = 0; i < 100; i++)
Результат выполнения программы на 4-х ядерном процессоре может
быть следующим:
Поток 0 получает право на выполнение итераций 1-15.
Поток 1 получает право на выполнение итераций 16-30.
Поток 2 получает право на выполнение итераций 31-45.
Поток 3 получает право на выполнение итераций 46-60.
Поток 3 завершает выполнение итераций.
Поток 3 получает право на выполнение итераций 61-75.
Поток 2 завершает выполнение итераций.
Поток 2 получает право на выполнение итераций 76-90.
Поток 0 завершает выполнение итераций.
Поток 0 получает право на выполнение итераций 91-100.
Москва, 2015 г.
Параллельное программирование с OpenMP: Конструкции
распределения работы © Бахтин В.А.
21 из 42
Распределение витков цикла. Клауза schedule
число_выполняемых_потоком_итераций =
max(число_нераспределенных_итераций/omp_get_num_threads(),
число_итераций)
#pragma omp parallel for schedule(guided, 10)
for(int i = 0; i < 100; i++)
Пусть программа запущена на 4-х ядерном процессоре.
Поток 0 получает право на выполнение итераций 1-25.
Поток 1 получает право на выполнение итераций 26-44.
Поток 2 получает право на выполнение итераций 45-59.
Поток 3 получает право на выполнение итераций 60-69.
Поток 3 завершает выполнение итераций.
Поток 3 получает право на выполнение итераций 70-79.
Поток 2 завершает выполнение итераций.
Поток 2 получает право на выполнение итераций 80-89.
Поток 3 завершает выполнение итераций.
Поток 3 получает право на выполнение итераций 90-99.
Поток 1 завершает выполнение итераций.
Поток 1 получает право на выполнение 99 итерации.
Москва, 2015 г.
Параллельное программирование с OpenMP: Конструкции
распределения работы © Бахтин В.А.
22 из 42
Распределение витков цикла. Клауза schedule
#pragma omp parallel for schedule(runtime)
for(int i = 0; i < 100; i++) /* способ распределения витков цикла между
нитями будет задан во время выполнения программы*/
При помощи переменных среды:
csh:
setenv OMP_SCHEDULE "dynamic,4“
ksh:
export OMP_SCHEDULE="static,10“
Windows:
set OMP_SCHEDULE=auto
или при помощи функций системы поддержки:
void omp_set_schedule(omp_sched_t kind, int modifier);
Москва, 2015 г.
Параллельное программирование с OpenMP: Конструкции
распределения работы © Бахтин В.А.
23 из 42
Распределение витков цикла. Клауза schedule
#pragma omp parallel for schedule(auto)
for(int i = 0; i < 100; i++)
Способ распределения витков цикла между нитями определяется
реализацией компилятора.
На этапе компиляции программы или во время ее выполнения
определяется оптимальный способ распределения.
Москва, 2015 г.
Параллельное программирование с OpenMP: Конструкции
распределения работы © Бахтин В.А.
24 из 42
Распределение витков цикла. Клауза nowait
void example(int n, int m, float *a, float *b, float *y, float *z)
{
int i;
#pragma omp parallel
{
#pragma omp for nowait
for (i=1; i
#pragma omp for nowait
for (i=0; i
}
}
Клауза nowait отменяет барьерную синхронизацию по завершении
выполнении цикла
Москва, 2015 г.
Параллельное программирование с OpenMP: Конструкции
распределения работы © Бахтин В.А.
25 из 42
Распределение витков цикла. Клауза nowait
void example(int n, float *a, float *b, float *z)
{
int i;
#pragma omp parallel
{
#pragma omp for schedule(static) nowait
for (i=0; i
#pragma omp for schedule(static) nowait
for (i=0; i
}
}
Верно, если количество итераций у циклов совпадает и параметры
клаузы schedule совпадают (STATIC + число_итераций).
Москва, 2015 г.
Параллельное программирование с OpenMP: Конструкции
распределения работы © Бахтин В.А.
26 из 42
Распределение витков цикла. Клауза nowait
void example(int n, float *a, float *b, float *z)
{
int i;
float sum = 0.0;
#pragma omp parallel
{
#pragma omp for schedule(static) nowait reduction (+: sum)
for (i=0; i
sum += c[i];
}
#pragma omp for schedule(static) nowait
for (i=0; i
#pragma omp barrier
printf(“sum of array is %.16f”, sum);
}
}
Москва, 2015 г.
Параллельное программирование с OpenMP: Конструкции
распределения работы © Бахтин В.А.
27 из 42
Распределение циклов с зависимостью по данным
for(int i = 1; i < 100; i++)
a[i]= a[i-1] + a[i+1]
Между витками цикла с индексами i1 и i2 ( i1
эти витка осуществляют обращение к одному элементу массива по
схеме запись-чтение или чтение-запись.
Если виток i1 записывает значение, а виток i2 читает это значение, то
между этими витками существует потоковая зависимость или просто
зависимость i1 -> i2.
Если виток i1 читает “старое” значение, а виток i2 записывает “новое”
значение, то между этими витками существует обратная зависимость
i1<- i2.
В обоих случаях виток i2 может выполняться только после витка i1.
Москва, 2015 г.
Параллельное программирование с OpenMP: Конструкции
распределения работы © Бахтин В.А.
28 из 42
Распределение циклов с зависимостью по данным
for (int i = 0; i < n; i++) {
x = (b[i] + c[i]) / 2;
a[i] = a[i + 1] + x;
// ANTI dependency
}
#pragma omp parallel shared(a, a_copy) private (x)
{
#pragma omp for
for (int i = 0; i < n; i++) {
a_copy[i] = a[i + 1];
}
#pragma omp for
for (int i = 0; i < n; i++) {
x = (b[i] + c[i]) / 2;
a[i] = a_copy[i] + x;
}
}
Москва, 2015 г.
Параллельное программирование с OpenMP: Конструкции
распределения работы © Бахтин В.А.
29 из 42
Распределение циклов с зависимостью по данным
for (int i = 1; i < n; i++) {
b[i] = b[i] + a[i - 1];
a[i] = a[i] + c[i]; // FLOW dependency
}
b[1] = b[1] + a[0];
#pragma omp parallel for shared(a,b,c)
for (int i = 1; i < n; i++) {
a[i] = a[i] + c[i];
b[i + 1] = b[i + 1] + a[i];
}
a[n - 1] = a[n - 1] + c[n - 1];
Москва, 2015 г.
Параллельное программирование с OpenMP: Конструкции
распределения работы © Бахтин В.А.
30 из 42
Распределение циклов с зависимостью по данным.
Клауза и директива ordered
void print_iteration(int iter) {
#pragma omp ordered
printf("iteration %dn", iter);
}
int main( ) {
int i;
#pragma omp parallel
{
#pragma omp for ordered
for (i = 0 ; i < 5 ; i++) {
print_iteration(i);
another_work (i);
}
}
}
Москва, 2015 г.
Результат выполнения программы:
iteration 0
iteration 1
iteration 2
iteration 3
iteration 4
Параллельное программирование с OpenMP: Конструкции
распределения работы © Бахтин В.А.
31 из 42
Распределение циклов с зависимостью по данным.
Клауза ordered
Цикл с зависимостью по данным может быть распараллелен с
помощью клаузы ordered:
#pragma omp parallel for ordered
for(int i = 1; i < 100; i++) {
#pragma omp ordered
{
a[i]= a[i-1] + a[i+1]
}
}
Москва, 2015 г.
Параллельное программирование с OpenMP: Конструкции
распределения работы © Бахтин В.А.
32 из 42
Распределение циклов с зависимостью по данным.
Организация конвейерного выполнения цикла.
for(int i = 1; i < M; i++)
for(int j = 1; j < N; j++)
a[i][j] = (a[i-1][j] + a[i][j-1] + a[i+1][j] + a[i][j+1]) / 4
Нить 0
Москва, 2015 г.
Нить 1
Нить N
Параллельное программирование с OpenMP: Конструкции
распределения работы © Бахтин В.А.
33 из 42
Распределение циклов с зависимостью по данным.
Организация конвейерного выполнения цикла.
for(int i = 1; i < M; i++)
for(int j = 1; j < N; j++)
a[i][j] = (a[i-1][j] + a[i][j-1] + a[i+1][j] + a[i][j+1]) / 4
Москва, 2015 г.
Параллельное программирование с OpenMP: Конструкции
распределения работы © Бахтин В.А.
34 из 42
Распределение циклов с зависимостью по данным.
Организация конвейерного выполнения цикла.
int iam, numt, limit;
int *isync = (int *)
malloc(omp_get_max_threads()*sizeof(int));
#pragma omp parallel private(iam,numt,limit)
{
iam = omp_get_thread_num ();
numt = omp_get_num_threads ();
limit=min(numt-1,N-2);
isync[iam]=0;
#pragma omp barrier
for (int i=1; i
for (;isync[iam-1]==0;) {
#pragma omp flush (isync)
}
isync[iam-1]=0;
#pragma omp flush (isync)
}
Москва, 2015 г.
#pragma omp for schedule(static) nowait
for (int j=1; j
a[i][j+1])/4;
}
if (iam
#pragma omp flush (isync)
}
isync[iam]=1;
#pragma omp flush (isync)
}
}
}
Параллельное программирование с OpenMP: Конструкции
распределения работы © Бахтин В.А.
35 из 42
Распределение циклов с зависимостью по данным.
Организация конвейерного выполнения цикла.
#include
int main () {
#pragma omp parallel private(iam,numt)
{
iam = omp_get_thread_num ();
numt = omp_get_num_threads ();
for (int newi=1; newi
#pragma omp for
for (int j=1; j
a[i][j]=(a[i-1][j] + a[i][j-1] + a[i+1][j] + a[i][j+1])/4;
}
}
}
}
}
Москва, 2015 г.
Параллельное программирование с OpenMP: Конструкции
распределения работы © Бахтин В.А.
36 из 42
Распределение нескольких структурных блоков между
нитями (директива sections).
#pragma omp sections [клауза[[,] клауза] ...]
{
[#pragma omp section]
структурный блок
[#pragma omp section
структурный блок ]
...
}
где клауза одна из :
private(list)
firstprivate(list)
lastprivate(list)
reduction(operator: list)
nowait
Москва, 2015 г.
void XAXIS();
void YAXIS();
void ZAXIS();
void example()
{
#pragma omp parallel
{
#pragma omp sections
{
#pragma omp section
XAXIS();
#pragma omp section
YAXIS();
#pragma omp section
ZAXIS();
}
}
}
Параллельное программирование с OpenMP: Конструкции
распределения работы © Бахтин В.А.
37 из 42
Выполнение структурного блока одной нитью
(директива SINGLE).
#pragma omp single [клауза[[,] клауза] ...]
структурный блок
где клауза одна из :
private(list)
firstprivate(list)
copyprivate(list)
nowait
Структурный блок будет выполнен
одной из нитей. Все остальные
нити будут дожидаться
результатов выполнения блока,
если не указана клауза NOWAIT.
Москва, 2015 г.
#include
float x, y;
#pragma omp threadprivate(x, y)
void init() {
#pragma omp single copyprivate(x,y)
scanf("%f %f", &x, &y);
}
int main () {
#pragma omp parallel
{
init ();
parallel_work ();
}
}
Параллельное программирование с OpenMP: Конструкции
распределения работы © Бахтин В.А.
38 из 42
Распределение операторов одного структурного блока
между нитями (директива WORKSHARE).
SUBROUTINE EXAMPLE (AA, BB, CC, DD, EE, FF, GG, HH, N)
INTEGER N
REAL AA(N,N), BB(N,N), CC(N,N)
REAL DD(N,N), EE(N,N), FF(N,N)
REAL GG(N,N), HH(N,N)
REAL SHR
!$OMP PARALLEL SHARED(SHR)
!$OMP WORKSHARE
AA = BB
CC = DD
WHERE (EE .ne. 0) FF = 1 / EE
SHR = 1.0
GG (1:50,1) = HH(11:60,1)
HH(1:10,1) = SHR
!$OMP END WORKSHARE
!$OMP END PARALLEL
END SUBROUTINE EXAMPLE
Москва, 2015 г.
Параллельное программирование с OpenMP: Конструкции
распределения работы © Бахтин В.А.
39 из 42
Спасибо за внимание!
Вопросы?
Москва, 2015 г.
Параллельное программирование с OpenMP: Конструкции
распределения работы © Бахтин В.А.
40 из 42
Следующая тема
Конструкции для синхронизации нитей
Москва, 2015 г.
Параллельное программирование с OpenMP: Конструкции
распределения работы © Бахтин В.А.
41 из 42
Контакты
Бахтин В.А., кандидат физ.-мат. наук, заведующий
сектором, Институт прикладной математики им.
М.В.Келдыша РАН
bakhtin@keldysh.ru
Москва, 2015 г.
Параллельное программирование с OpenMP: Конструкции
распределения работы © Бахтин В.А.
42 из 42