Конструкции для синхронизации нитей

Москва, 2009 г.
Параллельное программирование с OpenMP: Конструкции для синхронизации нитей © Бахтин В.А.
из 26
Содержание
Директива MASTER
Директива CRITICAL
Директива ATOMIC
Семафоры
Директива BARRIER
Директива TASKWAIT
Директива FLUSH
Директива ORDERED

из 26
#pragma omp master
структурный блок
/*Структурный блок будет выполнен MASTER-нитью группы. По завершении выполнения структурного блока барьерная синхронизация нитей не выполняется*/
#include
void init(float *a, float *b ) {
#pragma omp master
scanf("%f %f", a, b);
#pragma omp barrier
}
int main () {
float x,y;
#pragma omp parallel
{
init (&x,&y);
parallel_work (x,y);
}
}
Директива master
Москва, 2009 г.
Параллельное программирование с OpenMP: Конструкции для синхронизации нитей © Бахтин В.А.

из 26
При взаимодействии через общую память нити должны синхронизовать свое выполнение.
int i=0;
#pragma omp parallel {
i++;
}
Взаимное исключение критических интервалов
Москва, 2009 г.
Результат зависит от порядка выполнения команд. Требуется взаимное исключение критических интервалов.
Параллельное программирование с OpenMP: Конструкции для синхронизации нитей © Бахтин В.А.

из 26
Решение проблемы взаимного исключения должно удовлетворять требованиям:
в любой момент времени только одна нить может находиться внутри критического интервала;
если ни одна нить не находится в критическом интервале, то любая нить, желающая войти в критический интервал, должна получить разрешение без какой либо задержки;
ни одна нить не должна бесконечно долго ждать разрешения на вход в критический интервал (если ни одна нить не будет находиться внутри критического интервала бесконечно);
не должно существовать никаких предположений о скоростях процессоров.
Взаимное исключение критических интервалов
Москва, 2009 г.
Параллельное программирование с OpenMP: Конструкции для синхронизации нитей © Бахтин В.А.

Вычисление числа π
из 26
Москва, 2009 г.
Параллельное программирование с OpenMP: Конструкции для синхронизации нитей © Бахтин В.А.

из 26
#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;
}
Вычисление числа π. Последовательная программа.
Москва, 2009 г.
Параллельное программирование с OpenMP: Конструкции для синхронизации нитей © Бахтин В.А.

из 26
#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)
{
double local_sum = 0.0;
#pragma omp for
for (i = 1; i <= n; i++) {
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;
}
Вычисление числа π на OpenMP с использованием критической секции
Москва, 2009 г.
#pragma omp critical [(name)]
структурный блок
Параллельное программирование с OpenMP: Конструкции для синхронизации нитей © Бахтин В.А.

из 26
int from_ list(float *a, int type);
void work(int i, float *a);
void example ()
{
#pragma omp parallel
{
float *x;
int ix_next;
#pragma omp critical (list0)
ix_next = from_ list(x,0);
work(ix_next, x);
#pragma omp critical (list1)
ix_next = from_ list(x,1);
work(ix_next, x);
}
}
Директива critical
Москва, 2009 г.
Параллельное программирование с OpenMP: Конструкции для синхронизации нитей © Бахтин В.А.

из 26
#pragma omp atomic
expression-stmt
где expression-stmt:
x binop= expr
x++
++x
x--
--x
Здесь х – скалярная переменная, expr – выражение со скалярными типами, в котором не присутствует переменная х.
где binop - не перегруженный оператор:
+
*
-
/
&
^
|
<<
>>
Директива atomic
Москва, 2009 г.
Параллельное программирование с OpenMP: Конструкции для синхронизации нитей © Бахтин В.А.

из 26
#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)
{
double local_sum = 0.0;
#pragma omp for
for (i = 1; i <= n; i++) {
x = h * ((double)i - 0.5);
local_sum += (4.0 / (1.0 + x*x));
}
#pragma omp atomic
sum += local_sum;
}
pi = h * sum;
printf("pi is approximately %.16f”, pi);
return 0;
}
Вычисление числа π на OpenMP с использованием директивы atomic
Москва, 2009 г.
Параллельное программирование с OpenMP: Конструкции для синхронизации нитей © Бахтин В.А.

из 26
Концепцию семафоров описал Дейкстра (Dijkstra) в 1965
Семафор - неотрицательная целая переменная, которая может изменяться и проверяться только посредством двух функций:
P - функция запроса семафора
P(s): [if (s == 0) <заблокировать текущий процесс>; else s = s-1;]
V - функция освобождения семафора
V(s): [if (s == 0) <разблокировать один из заблокированных процессов>; s = s+1;]
Семафоры
Москва, 2009 г.
Параллельное программирование с OpenMP: Конструкции для синхронизации нитей © Бахтин В.А.

из 26
Состояния семафора:
uninitialized
unlocked
locked
void omp_init_lock(omp_lock_t *lock); /* uninitialized to unlocked*/
void omp_destroy_lock(omp_lock_t *lock); /* unlocked to uninitialized */
void omp_set_lock(omp_lock_t *lock); /*P(lock)*/
void omp_unset_lock(omp_lock_t *lock); /*V(lock)*/
int omp_test_lock(omp_lock_t *lock);
void omp_init_nest_lock(omp_nest_lock_t *lock);
void omp_destroy_nest_lock(omp_nest_lock_t *lock);
void omp_set_nest_lock(omp_nest_lock_t *lock);
void omp_unset_nest_lock(omp_nest_lock_t *lock);
int omp_test_nest_lock(omp_nest_lock_t *lock);
Семафоры в OpenMP
Москва, 2009 г.
Параллельное программирование с OpenMP: Конструкции для синхронизации нитей © Бахтин В.А.

из 26
#include
int main ()
{
int n =100000, i;
double pi, h, sum, x;
omp_lock_t lck;
h = 1.0 / (double) n;
sum = 0.0;
omp_init_lock(&lck);
#pragma omp parallel default (none) private (i,x) shared (n,h,sum,lck)
{
double local_sum = 0.0;
#pragma omp for
for (i = 1; i <= n; i++) {
x = h * ((double)i - 0.5);
local_sum += (4.0 / (1.0 + x*x));
}
omp_set_lock(&lck);
sum += local_sum;
omp_unset_lock(&lck);
}
pi = h * sum;
printf("pi is approximately %.16f”, pi);
omp_destroy_lock(&lck);
return 0;
}
Вычисление числа π на OpenMP с использованием семафоров
Москва, 2009 г.
Параллельное программирование с OpenMP: Конструкции для синхронизации нитей © Бахтин В.А.

из 26
#include
#include
int main()
{
omp_lock_t lck;
int id;
omp_init_lock(&lck);
#pragma omp parallel shared(lck) private(id)
{
id = omp_get_thread_num();
omp_set_lock(&lck);
printf("My thread id is %d.\n", id); /* only one thread at a time can execute this printf */
omp_unset_lock(&lck);
while (! omp_test_lock(&lck)) {
skip(id); /* we do not yet have the lock, so we must do something else*/
}
work(id); /* we now have the lock and can do the work */
omp_unset_lock(&lck);
}
omp_destroy_lock(&lck);
return 0;
}
Использование семафоров
Москва, 2009 г.
void skip(int i) {}
void work(int i) {}
Параллельное программирование с OpenMP: Конструкции для синхронизации нитей © Бахтин В.А.

из 26
#include
typedef struct {
int a,b;
omp_lock_t lck; } pair;
void incr_a(pair *p, int a)
{
p->a += a;
}
void incr_b(pair *p, int b)
{
omp_set_lock(&p->lck);
p->b += b;
omp_unset_lock(&p->lck);
}
void incr_pair(pair *p, int a, int b)
{
omp_set_lock(&p->lck);
incr_a(p, a);
incr_b(p, b);
omp_unset_lock(&p->lck);
}
Использование семафоров
Москва, 2009 г.
void incorrect_example(pair *p)
{
#pragma omp parallel sections
{
#pragma omp section
incr_pair(p,1,2);
#pragma omp section
incr_b(p,3);
}
}
Deadlock!
Параллельное программирование с OpenMP: Конструкции для синхронизации нитей © Бахтин В.А.

из 26
#include
typedef struct {
int a,b;
omp_nest_lock_t lck; } pair;
void incr_a(pair *p, int a)
{ /* Called only from incr_pair, no need to lock. */
p->a += a;
}
void incr_b(pair *p, int b)
{
omp_set_nest_lock(&p->lck);
/* Called both from incr_pair and elsewhere,
so need a nestable lock. */
p->b += b;
omp_unset_nest_lock(&p->lck);
}
void incr_pair(pair *p, int a, int b)
{
omp_set_nest_lock(&p->lck);
incr_a(p, a);
incr_b(p, b);
omp_unset_nest_lock(&p->lck);
}
Использование семафоров
Москва, 2009 г.
void correct_example(pair *p)
{
#pragma omp parallel sections
{
#pragma omp section
incr_pair(p,1,2);
#pragma omp section
incr_b(p,3);
}
}
Параллельное программирование с OpenMP: Конструкции для синхронизации нитей © Бахтин В.А.

из 26
Точка в программе, достижимая всеми нитями группы, в которой выполнение программы приостанавливается до тех пор пока все нити группы не достигнут данной точки и все явные задачи, выполняемые группой нитей будут завершены.
#pragma omp barrier
По умолчанию барьерная синхронизация нитей выполняется:
по завершению конструкции parallel
при выходе из конструкций распределения работ (for, single, sections, workshare) , если не указана клауза nowait.
#pragma omp parallel
{
#pragma omp master
{
int i, size;
scanf("%d",&size);
for (i=0; i
#pragma omp task
process(i);
}
}
#pragma omp barrier
}
Директива barrier
Москва, 2009 г.
Параллельное программирование с OpenMP: Конструкции для синхронизации нитей © Бахтин В.А.

из 26
void work(int i, int j) {}
void wrong(int n)
{
#pragma omp parallel default(shared)
{
int i;
#pragma omp for
for (i=0; i
work(i, 0);
/* incorrect nesting of barrier region in a loop region */
#pragma omp barrier
work(i, 1);
}
}
}
Директива barrier
Москва, 2009 г.
Параллельное программирование с OpenMP: Конструкции для синхронизации нитей © Бахтин В.А.

из 26
void work(int i, int j) {}
void wrong(int n)
{
#pragma omp parallel default(shared)
{
int i;
#pragma omp critical
{
work(i, 0);
/* incorrect nesting of barrier region in a critical region */
#pragma omp barrier
work(i, 1);
}
}
}
Директива barrier
Москва, 2009 г.
Параллельное программирование с OpenMP: Конструкции для синхронизации нитей © Бахтин В.А.

из 26
void work(int i, int j) {}
void wrong(int n)
{
#pragma omp parallel default(shared)
{
int i;
#pragma omp single
{
work(i, 0);
/* incorrect nesting of barrier region in a single region */
#pragma omp barrier
work(i, 1);
}
}
}
Директива barrier
Москва, 2009 г.
Параллельное программирование с OpenMP: Конструкции для синхронизации нитей © Бахтин В.А.

из 26
#pragma omp taskwait
int fibonacci(int n) {
int i, j;
if (n<2)
return n;
else {
#pragma omp task shared(i)
i=fibonacci (n-1);
#pragma omp task shared(j)
j=fibonacci (n-2);
#pragma omp taskwait
return i+j;
}
}
Директива taskwait
Москва, 2009 г.
int main () {
int res;
#pragma omp parallel
{
#pragma omp single
{
int n;
scanf("%d",&n);
#pragma omp task shared(res)
res = fibonacci(n);
}
}
printf (“Finonacci number = %d\n”, res);
}
Параллельное программирование с OpenMP: Конструкции для синхронизации нитей © Бахтин В.А.

из 26
#pragma omp flush [(список переменных)]
По умолчанию все переменные приводятся в консистентное состояние (#pragma omp flush):
При барьерной синхронизации
При входе и выходе из конструкций parallel, critical и ordered.
При выходе из конструкций распределения работ (for, single, sections, workshare) , если не указана клауза nowait.
При вызове omp_set_lock и omp_unset_lock.
При вызове omp_test_lock, omp_set_nest_lock, omp_unset_nest_lock
и omp_test_nest_lock, если изменилось состояние семафора.
При входе и выходе из конструкции atomic выполняется #pragma omp flush(x), где x – переменная, изменяемая в конструкции atomic.
Директива flush
Москва, 2009 г.
Параллельное программирование с OpenMP: Конструкции для синхронизации нитей © Бахтин В.А.

из 26
Спасибо за внимание!
Вопросы?
Москва, 2009 г.
Параллельное программирование с OpenMP: Конструкции для синхронизации нитей © Бахтин В.А.

из 26
Система поддержки выполнения OpenMP-программ. Переменные окружения, управляющие выполнением OpenMP-программы.
Следующая тема
Москва, 2009 г.
Параллельное программирование с OpenMP: Конструкции для синхронизации нитей © Бахтин В.А.