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

Содержание

Слайд 2

Москва, 2009 г.

Параллельное программирование с OpenMP: Конструкции для синхронизации нитей © Бахтин

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

из 26

Содержание

Директива MASTER
Директива CRITICAL
Директива ATOMIC
Семафоры
Директива BARRIER
Директива TASKWAIT
Директива FLUSH
Директива ORDERED

Слайд 3

из 26

#pragma omp master
структурный блок
/*Структурный блок будет выполнен MASTER-нитью группы.

из 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: Конструкции для синхронизации нитей © Бахтин В.А.

Слайд 4

из 26

При взаимодействии через общую память нити должны синхронизовать свое выполнение.

из 26 При взаимодействии через общую память нити должны синхронизовать свое выполнение.

int i=0;
#pragma omp parallel {
i++;
}

Взаимное исключение критических интервалов

Москва, 2009 г.

Результат зависит от порядка выполнения команд. Требуется взаимное исключение критических интервалов.

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

Слайд 5

из 26

Решение проблемы взаимного исключения должно удовлетворять требованиям:
в любой момент

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

Взаимное исключение критических интервалов

Москва, 2009 г.

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

Слайд 6

Вычисление числа π

из 26

Москва, 2009 г.

Параллельное программирование с OpenMP: Конструкции для

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

Слайд 7

из 26

#include
int main ()
{
int n =100000, i;
double pi,

из 26 #include int main () { int n =100000, i; double
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: Конструкции для синхронизации нитей © Бахтин В.А.

Слайд 8

из 26

#include
#include
int main ()
{
int n =100000, i;
double

из 26 #include #include int main () { int n =100000, i;
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: Конструкции для синхронизации нитей © Бахтин В.А.

Слайд 9

из 26

int from_ list(float *a, int type);
void work(int i, float *a);
void

из 26 int from_ list(float *a, int type); void work(int i, float
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: Конструкции для синхронизации нитей © Бахтин В.А.

Слайд 10

из 26

#pragma omp atomic
expression-stmt
где expression-stmt:
x binop= expr
x++
++x
x--
--x
Здесь х – скалярная переменная,

из 26 #pragma omp atomic expression-stmt где expression-stmt: x binop= expr x++
expr – выражение со скалярными типами, в котором не присутствует переменная х.
где binop - не перегруженный оператор:
+
*
-
/
&
^
|
<<
>>

Директива atomic

Москва, 2009 г.

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

Слайд 11

из 26

#include
#include
int main ()
{
int n =100000, i;
double

из 26 #include #include int main () { int n =100000, i;
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: Конструкции для синхронизации нитей © Бахтин В.А.

Слайд 12

из 26

Концепцию семафоров описал Дейкстра (Dijkstra) в 1965
Семафор - неотрицательная

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

Семафоры

Москва, 2009 г.

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

Слайд 13

из 26

Состояния семафора:
uninitialized
unlocked
locked
void omp_init_lock(omp_lock_t *lock); /* uninitialized to unlocked*/
void omp_destroy_lock(omp_lock_t *lock);

из 26 Состояния семафора: uninitialized unlocked locked void omp_init_lock(omp_lock_t *lock); /* uninitialized
/* 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: Конструкции для синхронизации нитей © Бахтин В.А.

Слайд 14

из 26

#include
int main ()
{
int n =100000, i;
double pi,

из 26 #include int main () { int n =100000, i; double
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: Конструкции для синхронизации нитей © Бахтин В.А.

Слайд 15

из 26

#include
#include
int main()
{
omp_lock_t lck;
int id;
omp_init_lock(&lck);
#pragma

из 26 #include #include int main() { omp_lock_t lck; int id; omp_init_lock(&lck);
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: Конструкции для синхронизации нитей © Бахтин В.А.

Слайд 16

из 26

#include
typedef struct {
int a,b;
omp_lock_t lck; } pair;
void

из 26 #include typedef struct { int a,b; omp_lock_t lck; } pair;
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: Конструкции для синхронизации нитей © Бахтин В.А.

Слайд 17

из 26

#include
typedef struct {
int a,b;
omp_nest_lock_t lck; } pair;
void

из 26 #include typedef struct { int a,b; omp_nest_lock_t lck; } pair;
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: Конструкции для синхронизации нитей © Бахтин В.А.

Слайд 18

из 26

Точка в программе, достижимая всеми нитями группы, в которой выполнение

из 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: Конструкции для синхронизации нитей © Бахтин В.А.

Слайд 19

из 26

void work(int i, int j) {}
void wrong(int n)
{
#pragma omp parallel

из 26 void work(int i, int j) {} void wrong(int n) {
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: Конструкции для синхронизации нитей © Бахтин В.А.

Слайд 20

из 26

void work(int i, int j) {}
void wrong(int n)
{
#pragma omp parallel

из 26 void work(int i, int j) {} void wrong(int n) {
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: Конструкции для синхронизации нитей © Бахтин В.А.

Слайд 21

из 26

void work(int i, int j) {}
void wrong(int n)
{
#pragma omp parallel

из 26 void work(int i, int j) {} void wrong(int n) {
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: Конструкции для синхронизации нитей © Бахтин В.А.

Слайд 22

из 26

#pragma omp taskwait
int fibonacci(int n) {
int i, j;
if

из 26 #pragma omp taskwait int fibonacci(int n) { int i, j;
(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: Конструкции для синхронизации нитей © Бахтин В.А.

Слайд 23

из 26

#pragma omp flush [(список переменных)]
По умолчанию все переменные приводятся в

из 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: Конструкции для синхронизации нитей © Бахтин В.А.

Слайд 24

из 26

Спасибо за внимание!
Вопросы?

Москва, 2009 г.

Параллельное программирование с OpenMP: Конструкции для

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

Слайд 25

из 26

Система поддержки выполнения OpenMP-программ. Переменные окружения, управляющие выполнением OpenMP-программы.

Следующая тема

Москва,

из 26 Система поддержки выполнения OpenMP-программ. Переменные окружения, управляющие выполнением OpenMP-программы. Следующая
2009 г.

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

Имя файла: Конструкции-для-синхронизации-нитей.pptx
Количество просмотров: 117
Количество скачиваний: 0