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

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

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

3 3 из 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 4 из 26 При взаимодействии через общую память нити должны синхронизовать свое выполнение. int i=0; #pragma omp parallel { i++; } Взаимное исключение критических интервалов Москва, 2009 г. Результат зависит от порядка выполнения команд. Требуется взаимное исключение критических интервалов. ВремяThread0Thread1 1load i (i = 0) 2incr i (i = 1) 3->->load i (i = 0) 4incr i (i = 1) 5store i (i = 1) 6

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

6 Вычисление числа 4.0 (1+x 2 ) dx = 0 1 F(x i ) x i = 0 N Мы можем аппроксимировать интеграл как сумму прямоугольников: Где каждый прямоугольник имеет ширину x и высоту F(x i ) в середине интервала F(x) = 4.0/(1+x 2 ) X из 26 Москва, 2009 г. Параллельное программирование с OpenMP: Конструкции для синхронизации нитей © Бахтин В.А.

7 7 из 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

8 8 из 26 #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

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

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

11 11 из 26 #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

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

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

14 14 из 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

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

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

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

18 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

19 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

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

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

22 22 из 26 #pragma omp taskwait int fibonacci(int n) { int i, j; if (n

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

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

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

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