'

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

Понравилась презентация – покажи это...





Слайд 0

Конструкции для синхронизации нитей Учебный курс Параллельное программирование с OpenMP Бахтин В.А., кандидат физ.-мат. наук, заведующий сектором, Институт прикладной математики им. М.В.Келдыша РАН


Слайд 1

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


Слайд 2

3 из 26 #pragma omp master структурный блок /*Структурный блок будет выполнен MASTER-нитью группы. По завершении выполнения структурного блока барьерная синхронизация нитей не выполняется*/ #include <stdio.h> 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: Конструкции для синхронизации нитей © Бахтин В.А.


Слайд 3

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


Слайд 4

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


Слайд 5

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


Слайд 6

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


Слайд 7

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


Слайд 8

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


Слайд 9

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


Слайд 10

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


Слайд 11

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


Слайд 12

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


Слайд 13

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


Слайд 14

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


Слайд 15

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


Слайд 16

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


Слайд 17

18 из 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<size; i++) { #pragma omp task process(i); } } #pragma omp barrier } Директива barrier Москва, 2009 г. Параллельное программирование с OpenMP: Конструкции для синхронизации нитей © Бахтин В.А.


Слайд 18

19 из 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<n; i++) { work(i, 0); /* incorrect nesting of barrier region in a loop region */ #pragma omp barrier work(i, 1); } } } Директива barrier Москва, 2009 г. Параллельное программирование с OpenMP: Конструкции для синхронизации нитей © Бахтин В.А.


Слайд 19

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


Слайд 20

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


Слайд 21

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


Слайд 22

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


Слайд 23

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


Слайд 24

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


Слайд 25

26 из 26 Бахтин В.А., кандидат физ.-мат. наук, заведующий сектором, Институт прикладной математики им. М.В.Келдыша РАН bakhtin@keldysh.ru Контакты Москва, 2009 г. Параллельное программирование с OpenMP: Конструкции для синхронизации нитей © Бахтин В.А.


×

HTML:





Ссылка: