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

Москва, 2010 г. Параллельное программирование с OpenMP: Конструкции для синхронизации нитей © Бахтин В.А. 2 из 49 Содержание Конструкции для синхронизации нитей. –Директива MASTER –Директива CRITICAL –Директива ATOMIC –Семафоры –Директива BARRIER –Директива TASKWAIT –Директива FLUSH Система поддержки выполнения OpenMP- программ. –Внутренние переменные, управляющие выполнением OpenMP-программы (ICV-Internal Control Variables). –Задание/опрос значений ICV-переменных. –Функции работы со временем.

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

4 из 49 Взаимное исключение критических интервалов Москва, 2010 г. Параллельное программирование с OpenMP: Конструкции для синхронизации нитей © Бахтин В.А. При взаимодействии через общую память нити должны синхронизовать свое выполнение. #pragma omp parallel { sum = sum + val; } Результат зависит от порядка выполнения команд. Требуется взаимное исключение критических интервалов. ВремяThread 0 Thread 1 1LOAD R1,sum 2LOAD R2,val 3ADD R1,R2LOAD R1,sum 4LOAD R2,val 5ADD R1,R2 6STORE R1,sum 7

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

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

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

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

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

13 из 49 Состояния семафора: 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 Москва, 2010 г. Параллельное программирование с OpenMP: Конструкции для синхронизации нитей © Бахтин В.А.

14 из 49 #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 из 49 #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; } Использование семафоров Москва, 2010 г. void skip(int i) {} void work(int i) {} Параллельное программирование с OpenMP: Конструкции для синхронизации нитей © Бахтин В.А.

16 из 49 #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); } Использование семафоров Москва, 2010 г. 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 из 49 #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); } Использование семафоров Москва, 2010 г. 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 из 49 Точка в программе, достижимая всеми нитями группы, в которой выполнение программы приостанавливается до тех пор пока все нити группы не достигнут данной точки и все явные задачи, выполняемые группой нитей будут завершены. #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 из 49 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 из 49 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 Москва, 2010 г. Параллельное программирование с OpenMP: Конструкции для синхронизации нитей © Бахтин В.А.

21 из 49 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 Москва, 2010 г. Параллельное программирование с OpenMP: Конструкции для синхронизации нитей © Бахтин В.А.

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

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

Н.Новгород, 2008 г. Основы параллельных вычислений: Введение © Гергель В.П. 24 из 49 Конструкции для синхронизации нитей. –Директива MASTER –Директива CRITICAL –Директива ATOMIC –Семафоры –Директива BARRIER –Директива TASKWAIT –Директива FLUSH Система поддержки выполнения OpenMP- программ. –Внутренние переменные, управляющие выполнением OpenMP-программы (ICV-Internal Control Variables). –Задание/опрос значений ICV-переменных. –Функции работы со временем. Содержание

25 из 49 Для параллельных областей: nthreads-var thread-limit-var dyn-var nest-var max-active-levels-var Для циклов: run-sched-var def-sched-var Для всей программы: stacksize-var wait-policy-var Internal Control Variables. Москва, 2010 г. Параллельное программирование с OpenMP: Система поддержки выполнения OpenMP-программ © Бахтин В.А.

26 из 49 void work(); int main () { omp_set_num_threads(3); #pragma omp parallel { omp_set_num_threads(omp_get_thread_num ()+2); #pragma omp parallel work(); } Internal Control Variables. nthreads-var Москва, 2010 г. Параллельное программирование с OpenMP: Система поддержки выполнения OpenMP-программ © Бахтин В.А. Не корректно в OpenMP 2.5 Корректно в OpenMP 3.0

27 из 49 Internal Control Variables. nthreads-var Москва, 2010 г. Параллельное программирование с OpenMP: Система поддержки выполнения OpenMP-программ © Бахтин В.А. Определяет максимально возможное количество нитей в создаваемой параллельной области. Начальное значение: зависит от реализации. Существует одна копия этой переменной для каждой задачи. Значение переменной можно изменить: C shell: setenv OMP_NUM_THREADS 16 Korn shell: export OMP_NUM_THREADS=16 Windows: set OMP_NUM_THREADS=16 void omp_set_num_threads(int num_threads); Узнать значение переменной можно: int omp_get_max_threads(void);

28 из 49 Internal Control Variables. thread-limit-var Москва, 2010 г. Параллельное программирование с OpenMP: Система поддержки выполнения OpenMP-программ © Бахтин В.А. Определяет максимальное количество нитей, которые могут быть использованы для выполнения всей программы. Начальное значение: зависит от реализации. Существует одна копия этой переменной для всей программы. Значение переменной можно изменить: C shell: setenv OMP_THREAD_LIMIT 16 Korn shell: export OMP_THREAD_LIMIT=16 Windows: set OMP_THREAD_LIMIT=16 Узнать значение переменной можно: int omp_get_thread_limit(void)

29 из 49 Internal Control Variables. dyn-var Москва, 2010 г. Параллельное программирование с OpenMP: Система поддержки выполнения OpenMP-программ © Бахтин В.А. Включает/отключает режим, в котором количество создаваемых нитей при входе в параллельную область может меняться динамически. Начальное значение: Если компилятор не поддерживает данный режим, то false. Иначе – зависит от реализации. Существует одна копия этой переменной для каждой задачи. Значение переменной можно изменить: C shell: setenv OMP_DYNAMIC true Korn shell: export OMP_DYNAMIC=true Windows: set OMP_DYNAMIC=true void omp_set_dynamic(int dynamic_threads); Узнать значение переменной можно: int omp_get_dynamic(void);

30 из 49 Internal Control Variables. nest-var Москва, 2010 г. Параллельное программирование с OpenMP: Система поддержки выполнения OpenMP-программ © Бахтин В.А. Включает/отключает режим поддержки вложенного параллелизма. Начальное значение: false. Существует одна копия этой переменной для каждой задачи. Значение переменной можно изменить: C shell: setenv OMP_NESTED true Korn shell: export OMP_NESTED=false Windows: set OMP_NESTED=true void omp_set_nested(int nested); Узнать значение переменной можно: int omp_get_nested(void);

31 из 49 Internal Control Variables. max-active-levels-var Москва, 2010 г. Параллельное программирование с OpenMP: Система поддержки выполнения OpenMP-программ © Бахтин В.А. Задает максимально возможное количество активных вложенных параллельных областей. Начальное значение: зависит от реализации. Существует одна копия этой переменной для всей программы. Значение переменной можно изменить: C shell: setenv OMP_MAX_ACTIVE_LEVELS 2 Korn shell: export OMP_MAX_ACTIVE_LEVELS=3 Windows: set OMP_MAX_ACTIVE_LEVELS=4 void omp_set_max_active_levels (int max_levels); Узнать значение переменной можно: int omp_get_max_active_levels(void);

32 из 49 Internal Control Variables. run-sched-var Москва, 2010 г. Параллельное программирование с OpenMP: Система поддержки выполнения OpenMP-программ © Бахтин В.А. Задает способ распределения витков цикла между нитями, если указана клауза schedule(runtime). Начальное значение: зависит от реализации. Существует одна копия этой переменной для каждой задачи. Значение переменной можно изменить: C shell: setenv OMP_SCHEDULE "guided,4" Korn shell: export OMP_SCHEDULE "dynamic,5" Windows: set OMP_SCHEDULE=static void omp_set_schedule(omp_sched_t kind, int modifier); Узнать значение переменной можно: void omp_get_schedule(omp_sched_t * kind, int * modifier ); typedef enum omp_sched_t { omp_sched_static = 1, omp_sched_dynamic = 2, omp_sched_guided = 3, omp_sched_auto = 4 } omp_sched_t;

33 из 49 Internal Control Variables. run-sched-var Москва, 2010 г. Параллельное программирование с OpenMP: Система поддержки выполнения OpenMP-программ © Бахтин В.А. void work(int i); int main () { omp_sched_t schedules [] = {omp_sched_static, omp_sched_dynamic, omp_sched_guided, omp_sched_auto}; omp_set_num_threads (4); #pragma omp parallel { omp_set_schedule (schedules[omp_get_thread_num()],0); #pragma omp parallel for schedule(runtime) for (int i=0;i

34 из 49 Internal Control Variables. def-sched-var Москва, 2010 г. Параллельное программирование с OpenMP: Система поддержки выполнения OpenMP-программ © Бахтин В.А. Задает способ распределения витков цикла между нитями по умолчанию. Начальное значение: зависит от реализации. Существует одна копия этой переменной для всей программы. void work(int i); int main () { #pragma omp parallel { #pragma omp for for (int i=0;i

35 из 49 Internal Control Variables. stack-size-var Москва, 2010 г. Параллельное программирование с OpenMP: Система поддержки выполнения OpenMP-программ © Бахтин В.А. Каждая нить представляет собой независимо выполняющийся поток управления со своим счетчиком команд, регистровым контекстом и стеком. Переменная stack-size-var задает размер стека. Начальное значение: зависит от реализации. Существует одна копия этой переменной для всей программы. Значение переменной можно изменить: setenv OMP_STACKSIZE B setenv OMP_STACKSIZE "3000 k " setenv OMP_STACKSIZE 10M setenv OMP_STACKSIZE "10 M " setenv OMP_STACKSIZE "20 m" setenv OMP_STACKSIZE "1G" setenv OMP_STACKSIZE 20000

36 из 49 Internal Control Variables. stack-size-var Москва, 2010 г. Параллельное программирование с OpenMP: Система поддержки выполнения OpenMP-программ © Бахтин В.А. int main () { int a[1024][1024]; #pragma omp parallel private (a) { for (int i=0;i

37 из 49 Internal Control Variables. wait-policy-var Москва, 2010 г. Параллельное программирование с OpenMP: Система поддержки выполнения OpenMP-программ © Бахтин В.А. Подсказка OpenMP-компилятору о желаемом поведении нитей во время ожидания. Начальное значение: зависит от реализации. Существует одна копия этой переменной для всей программы. Значение переменной можно изменить: setenv OMP_WAIT_POLICY ACTIVE setenv OMP_WAIT_POLICY active setenv OMP_WAIT_POLICY PASSIVE setenv OMP_WAIT_POLICY passive IBM AIX SPINLOOPTIME= YIELDLOOPTIME=40000

38 из 49 Internal Control Variables. Приоритеты Москва, 2010 г. Параллельное программирование с OpenMP: Система поддержки выполнения OpenMP-программ © Бахтин В.А. клаузавызов функциипеременная окруженияICV omp_set_dynamic()OMP_DYNAMICdyn-var omp_set_nested()OMP_NESTEDnest-var num_threadsomp_set_num_threads()OMP_NUM_THREADSnthreads-var scheduleomp_set_schedule()OMP_SCHEDULErun-sched-var scheduledef-sched-var OMP_STACKSIZEstacksize-var OMP_WAIT_POLICYwait-policy-var OMP_THREAD_LIMITthread-limit-var omp_set_max_active_ levels() OMP_MAX_ACTIVE_ LEVELS max-active-levels-var

39 из 49 int omp_get_num_threads(void); - возвращает количество нитей в текущей параллельной области #include void work(int i); void test() { int np; np = omp_get_num_threads(); /* np == 1*/ #pragma omp parallel private (np) { np = omp_get_num_threads(); #pragma omp for schedule(static) for (int i=0; i < np; i++) work(i); } Система поддержки выполнения OpenMP- программ. Москва, 2010 г. Параллельное программирование с OpenMP: Система поддержки выполнения OpenMP-программ © Бахтин В.А.

40 из 49 int omp_get_thread_num(void); - возвращает номер нити в группе [0: omp_get_num_threads()-1] #include void work(int i); void test() { int iam; iam = omp_get_thread_num(); /* iam == 0*/ #pragma omp parallel private (iam) { iam = omp_get_thread_num(); work(iam); } Система поддержки выполнения OpenMP- программ. Москва, 2010 г. Параллельное программирование с OpenMP: Система поддержки выполнения OpenMP-программ © Бахтин В.А.

41 из 49 int omp_get_num_procs(void); - возвращает количество процессоров, на которых программа выполняется #include void work(int i); void test() { int nproc; nproc = omp_get_num_ procs(); #pragma omp parallel num_threads(nproc) { int iam = omp_get_thread_num(); work(iam); } Система поддержки выполнения OpenMP- программ. Москва, 2010 г. Параллельное программирование с OpenMP: Система поддержки выполнения OpenMP-программ © Бахтин В.А.

42 из 49 int omp_get_level(void) - возвращает уровень вложенности для текущей параллельной области. #include void work(int i) { #pragma omp parallel { int ilevel = omp_get_level (); } void test() { int ilevel = omp_get_level (); /*ilevel==0*/ #pragma omp parallel private (ilevel) { ilevel = omp_get_level (); int iam = omp_get_thread_num(); work(iam); } Система поддержки выполнения OpenMP- программ. Москва, 2010 г. Параллельное программирование с OpenMP: Система поддержки выполнения OpenMP-программ © Бахтин В.А.

43 из 49 int omp_get_active_level(void) - возвращает количество активных параллельных областей (выполняемых 2-мя или более нитями). #include void work(int iam, int size) { #pragma omp parallel { int ilevel = omp_get_active_level (); } void test() { int size = 0; int ilevel = omp_get_active_level (); /*ilevel==0*/ scanf("%d",&size); #pragma omp parallel if (size>10) { int iam = omp_get_thread_num(); work(iam, size); } Система поддержки выполнения OpenMP- программ. Москва, 2010 г. Параллельное программирование с OpenMP: Система поддержки выполнения OpenMP-программ © Бахтин В.А.

44 из 49 int omp_get_ancestor_thread_num (int level) - для нити, вызвавшей данную функцию, возвращается номер нити- родителя, которая создала указанную параллельную область. omp_get_ancestor_thread_num (0) = 0 If (level==omp_get_level()) { omp_get_ancestor_thread_num (level) == omp_get_thread_num (); } If ((level omp_get_level())) { omp_get_ancestor_thread_num (level) == -1; } Система поддержки выполнения OpenMP- программ. Москва, 2010 г. Параллельное программирование с OpenMP: Система поддержки выполнения OpenMP-программ © Бахтин В.А.

45 из 49 int omp_get_team_size(int level); - количество нитей в указанной параллельной области. omp_get_team_size (0) = 1 If (level==omp_get_level()) { omp_get_team_size (level) == omp_get_num _threads (); } If ((level omp_get_level())) { omp_get_team_size (level) == -1; } Система поддержки выполнения OpenMP- программ. Москва, 2010 г. Параллельное программирование с OpenMP: Система поддержки выполнения OpenMP-программ © Бахтин В.А.

46 из 49 double omp_get_wtime(void); - возвращает для нити астрономическое время в секундах, прошедшее с некоторого момента в прошлом. Если некоторый участок окружить вызовами данной функции, то разность возвращаемых значений покажет время работы данного участка. Гарантируется, что момент времени, используемый в качестве точки отсчета не будет, не будет изменен за время выполнения программы. double start; double end; start = omp_get_wtime(); /*... work to be timed...*/ end = omp_get_wtime(); printf("Work took %f seconds\n", end - start); double omp_get_wtick(void); - возвращает разрешение таймера в секундах (количество секунд между последовательными импульсами таймера). Система поддержки выполнения OpenMP- программ. Функции работы со временем Москва, 2010 г. Параллельное программирование с OpenMP: Система поддержки выполнения OpenMP-программ © Бахтин В.А.

47 из 49 Спасибо за внимание! Вопросы? Москва, 2010 г. Параллельное программирование с OpenMP: Система поддержки выполнения OpenMP-программ © Бахтин В.А.

48 из 49 Наиболее часто встречаемые ошибки в OpenMP- программах. Функциональная отладка OpenMP- программ. Следующая тема Москва, 2010 г. Параллельное программирование с OpenMP: Система поддержки выполнения OpenMP-программ © Бахтин В.А.

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