Интернет Университет
Суперкомпьютерных технологий
Основные понятия
Учебный курс
Параллельное программирование с
OpenMP
Бахтин В.А., кандидат физ.-мат. наук,
заведующий сектором,
Институт прикладной математики им.
М.В.Келдыша РАН
Содержание
Директивы и клаузы
Понятие структурного блока
Компиляция OpenMP-программы
Параллельная область (директива
PARALLEL)
Понятие задачи (директива TASK)
Москва, 2015 г.
Параллельное программирование с OpenMP: Основные понятия
2 из 42
Директивы и клаузы
Спецификации параллелизма в OpenMP представляют собой директивы
вида:
#pragma omp название-директивы[ клауза[ [,]клауза]...]
Например:
#pragma omp parallel default (none) private (i,j)
Исполняемые директивы:
barrier
taskwait
taskyield
flush
Описательная директива:
threadprivate
Москва, 2015 г.
Параллельное программирование с OpenMP: Основные понятия
3 из 42
Структурный блок
Действие остальных директив распространяется на структурный блок:
#pragma omp название-директивы[ клауза[ [,]клауза]...]
{
структурный блок
}
Структурный блок: блок кода с одной точкой входа и одной точкой
выхода.
#pragma omp parallel
{
…
mainloop: res[id] = f (id);
if (res[id] != 0) goto mainloop;
if (id == 0) exit (0);
…
}
Структурный блок
Москва, 2015 г.
#pragma omp parallel
{
…
mainloop: res[id] = f (id);
…
}
if (res[id] != 0) goto mainloop;
Не структурный блок
Параллельное программирование с OpenMP: Основные понятия
4 из 42
Составные директивы
#pragma omp parallel private(i)
{
#pragma omp for firstprivate(n)
for (i = 1; i <= n; i ++)
{
A[i]=A[i]+ B[i];
}
}
Москва, 2015 г.
#pragma omp parallel for private(i)
firstprivate(n)
for (i = 1; i <= n; i ++)
{
A[i]=A[i]+ B[i];
}
Параллельное программирование с OpenMP: Основные понятия
5 из 42
Компиляция OpenMP-программы
Производитель
Компилятор
Опция компиляции
GNU
gcc
-fopenmp
IBM
XL C/C++ / Fortran
-qsmp=omp
Sun Microsystems
C/C++ / Fortran
-xopenmp
Intel
C/C++ / Fortran
-openmp | -qopenmp
/Qopenmp
Portland Group
C/C++ / Fortran
-mp
Microsoft
Visual Studio C++
/openmp
Москва, 2015 г.
Параллельное программирование с OpenMP: Основные понятия
6 из 42
Условная компиляция OpenMP-программы
#include
int main()
{
#ifdef _OPENMP
printf("Compiled by an OpenMP-compliant implementation.n");
#endif
return 0;
}
В значении переменной _OPENMP зашифрован год и месяц (yyyymm)
версии стандарта OpenMP, которую поддерживает компилятор.
Москва, 2015 г.
Параллельное программирование с OpenMP: Основные понятия
7 из 42
Использование функций поддержи выполнения OpenMPпрограмм (OpenMP API runtime library)
#include
#include
int main()
{
#pragma omp parallel
{
int id = omp_get_thread_num ();
int numt = omp_get_num_threads ();
printf(“Thread (%d) of (%d) threads aliven”, id, numt);
}
return 0;
}
Москва, 2015 г.
Параллельное программирование с OpenMP: Основные понятия
8 из 42
Использование функций поддержи выполнения
OpenMP-программ (OpenMP API runtime library)
#include
int omp_get_num_threads(void)
{
return 1;
В стандарте OpenMP описаны «заглушки»
}
для всех функций библиотеки поддержки
int omp_get_thread_num(void)
– требуются при компиляции данной
{
программы компилятором без поддержки
return 0;
OpenMP.
}
int main()
Опция для компилятора Intel:
{
-qopenmp-stubs
#pragma omp parallel
{
int id = omp_get_thread_num ();
int numt = omp_get_num_threads ();
printf(“Thread (%d) of (%d) threads aliven”, id, numt);
}
return 0;
}
Москва, 2015 г.
Параллельное программирование с OpenMP: Основные понятия
9 из 42
Параллельная область (директива PARALLEL)
#pragma omp parallel [ клауза[ [, ] клауза] ...]
структурный блок
где клауза одна из :
default(shared | none)
private(list)
firstprivate(list)
shared(list)
reduction(operator: list)
if(scalar-expression)
num_threads(integer-expression)
copyin(list)
proc_bind ( master | close | spread )
//OpenMP 4.0
Москва, 2015 г.
Параллельное программирование с OpenMP: Основные понятия
10 из 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: Основные понятия
11 из 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: Основные понятия
12 из 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,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);
#pragma omp critical
sum += (4.0 / (1.0 + x*x));
}
}
pi = h * sum;
printf("pi is approximately %.16f”, pi);
return 0;
}
Москва, 2015 г.
Параллельное программирование с OpenMP: Основные понятия
13 из 42
Конфликт доступа к данным
При взаимодействии через общую память нити должны синхронизовать
свое выполнение.
#pragma omp parallel
{
sum = sum + val;
}
Время
Thread 0
Thread 1
1
LOAD R1,sum
2
LOAD R2,val
3
ADD R1,R2
LOAD R3,sum
4
LOAD R4,val
5
ADD R3,R4
6
STORE R3,sum
7
STORE R1,sum
Результат зависит от порядка выполнения команд. Требуется взаимное
исключение критических интервалов.
Москва, 2015 г.
Параллельное программирование с OpenMP: Основные понятия
14 из 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,sum)
{
int id = omp_get_thread_num();
int numt = omp_get_num_threads();
double local_sum = 0.0;
for (i = id + 1; i <= n; i=i+numt)
{
x = h * ((double)i - 0.5);
local_sum += (4.0 / (1.0 + x*x));
}
#pragma omp critical
sum += local_sum;
}
pi = h * sum;
printf("pi is approximately %.16f”, pi);
return 0;
}
Москва, 2015 г.
Параллельное программирование с OpenMP: Основные понятия
15 из 42
Вычисление числа . Клауза reduction
#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: Основные понятия
16 из 42
Клауза reduction
reduction(operator:list)
Внутри паралельной области
для каждой переменной из
списка list создается копия этой
переменной. Эта переменная
инициализируется в
соответствии с оператором
operator (например, 0 для «+»).
Для каждой нити компилятор
заменяет в параллельной
области обращения к
редукционной переменной на
обращения к созданной копии.
По завершении выполнения
параллельной области
осуществляется объединение
полученных результатов.
Москва, 2015 г.
Оператор
Начальное значение
+
0
*
1
-
0
&
~0
|
0
^
0
&&
1
||
0
Least number in reduction
list item type
Largest number in
reduction list item type
max // OpenMP 3.1
min // OpenMP 3.1
Параллельное программирование с OpenMP: Основные понятия
17 из 42
Использование редукционных операций
void reduction (float *x, int *y, int n)
{
int i, b, c;
float a, d;
a = 0.0;
b = 0;
c = y[0];
d = x[0];
#pragma omp parallel for private(i) shared(x, y, n)
reduction(+:a) reduction(^:b)
reduction(min:c) reduction(max:d)
for (i=0; i
b ^= y[i];
if (c > y[i]) c = y[i];
d = fmaxf(d,x[i]);
}
}
Москва, 2015 г.
Параллельное программирование с OpenMP: Основные понятия
18 из 42
Реализация редукционных операций
#include
void reduction_by_hand (float *x, int *y, int n)
{
int i, b, b_p, c, c_p;
float a, a_p, d, d_p;
a = 0.0f;
b = 0;
c = y[0];
d = x[0];
#pragma omp parallel shared(a, b, c, d, x, y, n) private(a_p, b_p, c_p, d_p)
{
a_p = 0.0f; b_p = 0; c_p = INT_MAX; d_p = -HUGE_VALF;
#pragma omp for private(i)
for (i=0; i
}
#pragma omp critical
{
a += a_p; b ^= b_p; if( c > c_p ) c = c_p; d = fmaxf(d,d_p);
}
}
}
Москва, 2015 г.
Параллельное программирование с OpenMP: Основные понятия
19 из 42
Редукционные операции, определяемые
пользователем (OpenMP 4.0)
#pragma omp declare reduction (reduction-identifier : typename-list :
combiner) [initializer (dentity-expr)]
reduction-identifier - название редукционной операции
typename-list – тип (типы)
combiner – выражение для объединения частичных результатов
initializer – начальное значение создаваемых приватных переменных
Москва, 2015 г.
Параллельное программирование с OpenMP: Основные понятия
20 из 42
Использование редукционных операций,
определяемых пользователем (OpenMP 4.0)
struct point
{
int x;
int y;
} points[N], minp = { MAX_INT, MAX_INT };
#pragma omp declare reduction (min : struct point :
omp_out.x = omp_in.x > omp_out.x ? omp_out.x : omp_in.x,
omp_out.y = omp_in.y > omp_out.y ? omp_out.y : omp_in.y )
initializer ( omp_priv = { MAX_INT, MAX_INT })
#pragma omp parallel for reduction (min: minp)
for (int i = 0; i < N; i++)
{
if (points[i].x < minp.x) minp.x = points[i].x;
if (points[i].y < minp.y) minp.y = points[i].y;
}
Москва, 2015 г.
Параллельное программирование с OpenMP: Основные понятия
21 из 42
Клауза if
if(scalar-expression)
В зависимости от значения scalar-expression для выполнения структурного
блока будет создана группа нитей или он будет выполняться одной нитью.
#include
int main()
{
int n = 0;
printf("Enter the number of intervals: (0 quits) ");
scanf("%d",&n);
#pragma omp parallel if (n>10)
{
int id = omp_get_thread_num();
int numt = omp_get_num_threads();
for (int i = id + 1; i <= n; i=i+numt)
func (i);
}
return 0;
}
Москва, 2015 г.
Параллельное программирование с OpenMP: Основные понятия
22 из 42
Клауза num_threads
num_threads(integer-expression)
integer-expression задает максимально возможное число нитей, которые
будут созданы для выполнения структурного блока
#include
int main()
{
int n = 0;
printf("Enter the number of intervals: (0 quits) ");
scanf("%d",&n);
#pragma omp parallel num_threads(10)
{
int id = omp_get_thread_num ();
func (n, id);
}
return 0;
}
Москва, 2015 г.
Параллельное программирование с OpenMP: Основные понятия
23 из 42
Определение числа нитей в параллельной области
Число создаваемых нитей зависит от:
клаузы if
клаузы num_threads
значений переменных, управляющих выполнением OpenMP-программы:
– dyn-var (включение/отключение режима, в котором количество
создаваемых нитей может изменяться динамически: OMP_DYNAMIC,
omp_set_dynamic())
– nthreads-var (максимально возможное число нитей, создаваемых при
входе в параллельную область: OMP_NUM_THREADS,
omp_set_num_threads())
– thread-limit-var (максимально возможное число нитей, создаваемых
для выполнения всей OpenMP-программы: OMP_THREAD_LIMIT)
– nest-var (включение/отключение режима поддержки вложенного
параллелизма:OMP_NESTED, omp_set_nested())
– max-active-level-var (максимально возможное количество вложенных
параллельных областей: OMP_MAX_ACTIVE_LEVELS,
omp_set_max_active_levels())
Москва, 2015 г.
Параллельное программирование с OpenMP: Основные понятия
24 из 42
Определение числа нитей в параллельной области
Пусть ThreadsBusy - количество OpenMP нитей, выполняемых в
данный момент;
Пусть ActiveParRegions - количество активных параллельных
областей;
if в директиве parallel существует клауза if
then присвоить переменной IfClauseValue значение выражения в
клаузе if;
else IfClauseValue = true;
if в директиве parallel существует клауза num_threads
then присвоить переменной ThreadsRequested значение выражения в
клаузе num_threads;
else ThreadsRequested = nthreads-var;
ThreadsAvailable = (thread-limit-var - ThreadsBusy + 1);
Москва, 2015 г.
Параллельное программирование с OpenMP: Основные понятия
25 из 42
Определение числа нитей в параллельной области
if (IfClauseValue == false)
then number of threads = 1;
else if (ActiveParRegions >= 1) and (nest-var == false)
then number of threads = 1;
else if (ActiveParRegions == max-active-levels-var)
then number of threads = 1;
else if (dyn-var == true) and (ThreadsRequested <= ThreadsAvailable)
then number of threads = [ 1 : ThreadsRequested ];
else if (dyn-var == true) and (ThreadsRequested > ThreadsAvailable)
then number of threads = [ 1 : ThreadsAvailable ];
else if (dyn-var == false) and (ThreadsRequested <= ThreadsAvailable)
then number of threads = ThreadsRequested;
else if (dyn-var == false) and (ThreadsRequested > ThreadsAvailable)
then number of threads зависит от реализации компилятора;
Москва, 2015 г.
Параллельное программирование с OpenMP: Основные понятия
26 из 42
Определение числа нитей в параллельной области
#include
#include
int main (void)
{
omp_set_nested(1);
omp_set_max_active_levels(8);
omp_set_dynamic(0);
omp_set_num_threads(2);
#pragma omp parallel
{
omp_set_num_threads(3);
#pragma omp parallel
{
…
}
}
}
Москва, 2015 г.
Параллельное программирование с OpenMP: Основные понятия
27 из 42
Клауза copyin
copyin(list)
Значение каждой threadprivate-переменной из списка list, устанавливается
равным значению этой переменной в master-нити
float* work;
int size;
float val;
#pragma omp threadprivate(work,size,val)
void compute()
{
work = (float*)malloc( sizeof(float)*size);
for(int i = 0; i < size; ++i ) work[i] = val;
… // computation of work array elements
}
int main()
{
printf("Enter the size of array and valuen");
scanf("%d",&size);
scanf(“%f",&val);
#pragma omp parallel copyin(val,size)
compute();
}
Москва, 2015 г.
Параллельное программирование с OpenMP: Основные понятия
28 из 42
Клауза proc_bind (OpenMP 4.0)
#pragma omp parallel proc_bind(spread) num_threads(4)
{
#pragma omp parallel proc_bind(close) num_threads(2)
work();
}
Москва, 2015 г.
Параллельное программирование с OpenMP: Основные понятия
29 из 42
Понятие задачи
Задачи появились в OpenMP 3.0
Каждая задача:
Представляет собой последовательность операторов, которые
необходимо выполнить.
Включает в себя данные, которые используются при выполнении этих
операторов.
Выполняется некоторой нитью.
В OpenMP 3.0 каждый оператор программы является частью одной из
задач.
При входе в параллельную область создаются неявные задачи (implicit
task), по одной задаче для каждой нити.
Создается группа нитей.
Каждая нить из группы выполняет одну из задач.
По завершении выполнения параллельной области, master-нить
ожидает, пока не будут завершены все неявные задачи.
Москва, 2015 г.
Параллельное программирование с OpenMP: Основные понятия
30 из 42
Понятие задачи. Директива task
Явные задачи (explicit tasks) задаются при помощи директивы:
#pragma omp task [клауза[[,] клауза] ...]
структурный блок
где клауза одна из :
if (scalar-expression)
final (scalar-expression)
//OpenMP 3.1
Untied
mergeable
//OpenMP 3.1
shared (list)
private (list)
firstprivate (list)
default ( shared | none)
depend(dependence-type: list) // OpenMP 4.0
В результате выполнения директивы task создается новая задача, которая
состоит из операторов структурного блока; все используемые в операторах
переменные могут быть локализованы внутри задачи при помощи
соответствующих клауз. Созданная задача будет выполнена одной нитью из
группы.
Параллельное программирование с OpenMP: Основные понятия
31 из 42
Москва, 2015 г.
Использование директивы task.
for (i=0; i
}
#pragma omp parallel
{
…
#pragma omp single // Блок операторов, выполняемый 1-ой нитью
{
for (i=0; i
func(i);
}
}
}
Москва, 2015 г.
Параллельное программирование с OpenMP: Основные понятия
32 из 42
Использование директивы task.
typedef struct node node;
struct node {
int data;
node * next;
};
void increment_list_items(node * head)
{
#pragma omp parallel
{
#pragma omp single
{
node * p = head;
while (p) {
#pragma omp task
process(p);
p = p->next;
}
}
}
Параллельное программирование с OpenMP: Основные понятия
}
Москва, 2015 г.
33 из 42
Использование директивы task. Клауза if
double *item;
int main() {
#pragma omp parallel shared (item)
{
#pragma omp single
{
int size;
scanf("%d",&size);
item = (double*)malloc(sizeof(double)*size);
for (int i=0; i
process(item[i]);
}
}
}
Если накладные расходы на организацию задач превосходят время,
необходимое для выполнения блока операторов этой задачи, то блок
операторов будет немедленно выполнен нитью, выполнившей директиву task.
Москва, 2015 г.
Параллельное программирование с OpenMP: Основные понятия
34 из 42
Использование директивы task.
#define LARGE_NUMBER 10000000
Как правило, в компиляторах
double item[LARGE_NUMBER];
существуют ограничения на количество
extern void process(double);
создаваемых задач. Выполнение цикла,
int main() {
в котором создаются задачи, будет
#pragma omp parallel shared (item)
приостановлено. Нить, выполнявшая
{
этот цикл, будет использована для
#pragma omp single
выполнения одной из задач.
{
for (int i=0; i
process(item[i]);
}
}
}
Москва, 2015 г.
Параллельное программирование с OpenMP: Основные понятия
35 из 42
Использование директивы task. Клауза untied
#define LARGE_NUMBER 10000000
double item[LARGE_NUMBER];
extern void process(double);
Клауза untied - выполнение задачи после
int main() {
приостановки может быть продолжено
#pragma omp parallel
любой нитью группы
{
#pragma omp single
{
#pragma omp task untied
{
for (int i=0; i
process(item[i]);
}
}
}
}
Москва, 2015 г.
Параллельное программирование с OpenMP: Основные понятия
36 из 42
Использование директивы task.
int main () {
int fibonacci(int n) {
int res;
int i, j;
#pragma omp parallel
if (n<2)
{
return n;
else {
#pragma omp single
#pragma omp task shared(i)
{
i=fibonacci (n-1);
int n;
#pragma omp task shared(j)
scanf("%d",&n);
j=fibonacci (n-2);
#pragma omp task shared(res)
#pragma omp taskwait
return i+j;
res = fibonacci(n);
}
}
}
}
printf (“Finonacci number = %dn”, res);
}
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765,
10946, …
Москва, 2015 г.
Параллельное программирование с OpenMP: Основные понятия
37 из 42
Использование директивы task. Клауза final
void fib (int n, int d) {
int x, y;
if (n < 2) return 1;
#pragma omp task final (d > LIMIT) mergeable
x = fib (n - 1, d + 1);
#pragma omp task final (d > LIMIT) mergeable
y = fib (n - 2, d + 1);
#pragma omp taskwait
return x + y;
}
int omp_in_final (void);
Москва, 2015 г.
Параллельное программирование с OpenMP: Основные понятия
38 из 42
Использование директивы task. Клауза depend
depend(dependence-type: list)
где dependence-type:
in
out
inout
Секция массива:
[lower-bound : length]
[lower-bound:]
[:length]
[:]
void sort ( int n, int *a ) {
#pragma omp task depend (inout: a [ 0 : n/2 ] )
sort ( n/2, a );
#pragma omp task depend (inout: a [ n/2+1 : n/2 )
sort ( n/2, a[n/2+1] );
#pragma omp task depend (inout : a [ 0 : n / 2 ], a [ n/2+1 : n/2 ] )
merge ( n/2 , a, a[n/2+1], a );
}
Москва, 2015 г.
Параллельное программирование с OpenMP: Основные понятия
39 из 42
Вопросы?
Вопросы?
Москва, 2015 г.
Параллельное программирование с OpenMP: Основные понятия
40 из 42
Следующая тема
Конструкции распределения работы
Москва, 2015 г.
Параллельное программирование с OpenMP: Основные понятия
41 из 42
Контакты
Бахтин В.А., кандидат физ.-мат. наук, заведующий
сектором, Институт прикладной математики им.
М.В.Келдыша РАН
bakhtin@keldysh.ru
Москва, 2015 г.
Параллельное программирование с OpenMP: Основные понятия
42 из 42