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

2 из 49 Москва, 2012 г. Технология параллельного программирования OpenMP : Функциональная отладка OpenMP-программ Содержание Трудно обнаруживаемые ошибки типа race condition (конфликт доступа к данным). Ошибки типа deadlock (взаимная блокировка нитей). Ошибки, связанные с использованием неинициализированных переменных. Автоматизированный поиск ошибок в OpenMP- программах при помощи Intel Thread Checker (Intel Parallel Inspector) и Sun Studio Thread Analyzer (Oracle Solaris Studio).

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

4 из 49 Ошибка возникает при одновременном выполнении следующих условий: Две или более нитей обращаются к одной и той же ячейке памяти. По крайней мере, один из этих доступов к памяти является записью. Нити не синхронизируют свой доступ к данной ячейки памяти. При одновременном выполнении всех трех условий порядок доступа становится неопределенным. Конфликт доступа к данным Москва, 2012 г. Технология параллельного программирования OpenMP : Функциональная отладка OpenMP-программ

5 из 49 Использование различных компиляторов (различных опций оптимизации, включение/отключение режима отладки при компиляции программы), применение различных стратегий планирования выполнения нитей в различных ОС, может приводить к тому, что в каких-то условиях (например, на одной вычислительной машине) ошибка не будет проявляться, а в других (на другой машине) – приводить к некорректной работе программы. От запуска к запуску программа может выдавать различные результаты в зависимости от порядка доступа. Отловить такую ошибку очень тяжело. Причиной таких ошибок, как правило являются: неверное определение класса переменной, отсутствие синхронизации. Конфликт доступа к данным Москва, 2012 г. Технология параллельного программирования OpenMP : Функциональная отладка OpenMP-программ

6 из 49 Конфликт доступа к данным Москва, 2012 г. Технология параллельного программирования OpenMP : Функциональная отладка OpenMP-программ #define N float a[N], tmp; #pragma omp parallel { #pragma omp for for(int i=0; i

7 из 49 Конфликт доступа к данным Москва, 2012 г. Технология параллельного программирования OpenMP : Функциональная отладка OpenMP-программ #define N float a[N], tmp; #pragma omp parallel { #pragma omp for for(int i=0; i

8 из 49 Конфликт доступа к данным Москва, 2012 г. Технология параллельного программирования OpenMP : Функциональная отладка OpenMP-программ file1.c int counter = 0; #pragma omp threadprivate(counter) int increment_counter() { counter++; return(counter); } file2.c extern int counter; int decrement_counter() { counter--; return(counter); }

9 из 49 Директива threadprivate threadprivate – переменные сохраняют глобальную область видимости внутри каждой нити #pragma omp threadprivate (Var) Var = 1 Var = 2 … = Var Если количество нитей не изменилось, то каждая нить получит значение, посчитанное в предыдущей параллельной области. Технология параллельного программирования OpenMP : Функциональная отладка OpenMP-программ Москва, 2012 г.

10 из 49 Конфликт доступа к данным Москва, 2012 г. Технология параллельного программирования OpenMP : Функциональная отладка OpenMP-программ file1.c int counter = 0; #pragma omp threadprivate(counter) int increment_counter() { counter++; return(counter); } file2.c extern int counter; #pragma omp threadprivate(counter) int decrement_counter() { counter--; return(counter); }

11 из 49 Конфликт доступа к данным Москва, 2012 г. Технология параллельного программирования OpenMP : Функциональная отладка OpenMP-программ #define N 100 #define Max(a,b) ((a)>(b)?(a):(b)) float A[N], maxval; #pragma omp parallel { #pragma omp master maxval = 0.0; #pragma omp for for(int i=0; i

12 из 49 Конфликт доступа к данным Москва, 2012 г. Технология параллельного программирования OpenMP : Функциональная отладка OpenMP-программ #define N 100 #define Max(a,b) ((a)>(b)?(a):(b)) float A[N], maxval; #pragma omp parallel { #pragma omp master maxval = 0.0; #pragma omp for for(int i=0; i(b)?(a):(b)) float A[N], maxval; #pragma omp parallel { #pragma omp master maxval = 0.0; #pragma omp for for(int i=0; i

13 из 49 Конфликт доступа к данным Москва, 2012 г. Технология параллельного программирования OpenMP : Функциональная отладка OpenMP-программ #define N 100 #define Max(a,b) ((a)>(b)?(a):(b)) float A[N], maxval; #pragma omp parallel { #pragma omp master maxval = 0.0; #pragma omp for for(int i=0; i(b)?(a):(b)) float A[N], maxval; #pragma omp parallel { #pragma omp master maxval = 0.0; #pragma omp barrier #pragma omp for for(int i=0; i

14 из 49 Конфликт доступа к данным Москва, 2012 г. Технология параллельного программирования OpenMP : Функциональная отладка OpenMP-программ void example(int n, int m, float *a, float *b, float *с, float *z) { int i; float sum = 0.0; #pragma omp parallel { #pragma omp for schedule(runtime) nowait for (i=0; i

15 из 49 Конфликт доступа к данным Москва, 2012 г. Технология параллельного программирования OpenMP : Функциональная отладка OpenMP-программ void example(int n, int m, float *a, float *b, float *с, float *z) { int i; float sum = 0.0; #pragma omp parallel { #pragma omp for schedule(runtime) for (i=0; i

16 из 49 Конфликт доступа к данным Москва, 2012 г. Технология параллельного программирования OpenMP : Функциональная отладка OpenMP-программ void example(int n, float *a, float *b, float *с, float *z) { int i; float sum = 0.0; #pragma omp parallel { #pragma omp for nowait reduction (+: sum) for (i=0; i

17 из 49 Конфликт доступа к данным Москва, 2012 г. Технология параллельного программирования OpenMP : Функциональная отладка OpenMP-программ void example(int n, float *a, float *b, float *с, float *z) { int i; float sum = 0.0; #pragma omp parallel { #pragma omp for schedule(static) nowait reduction (+: sum) for (i=0; i

18 из 49 Распределение циклов с зависимостью по данным. Организация конвейерного выполнения цикла. for(int i = 1; i < N; i++) for(int j = 1; j < N; j++) a[i][j] = (a[i-1][j] + a[i][j-1] + a[i+1][j] + a[i][j+1]) / 4 Технология параллельного программирования OpenMP : Функциональная отладка OpenMP-программ Москва, 2012 г.

19 из 49 Распределение циклов с зависимостью по данным. Организация конвейерного выполнения цикла. int isync[NUMBER_OF_THREADS]; int iam, numt, limit; #pragma omp parallel private(iam,numt,limit) { iam = omp_get_thread_num (); numt = omp_get_num_threads (); limit=min(numt-1,N-2); isync[iam]=0; #pragma omp barrier for (int i=1; i0) && (iam

20 из Модель памяти в OpenMP Нить 001 Нить 001 Нить Технология параллельного программирования OpenMP : Функциональная отладка OpenMP-программ Москва, 2012 г.

21 из Нить Нить 1 static int i = 0; … = i + 1; i = i + 1; i = 0 i = 1 … = i + 2; // ? #pragma omp flush (i) i = 1 Модель памяти в OpenMP Технология параллельного программирования OpenMP : Функциональная отладка OpenMP-программ Москва, 2012 г.

22 из 49 Консистентность памяти в OpenMP Корректная последовательность работы нитей с переменной: Нить0 записывает значение переменной - write(var) Нить0 выполняет операцию синхронизации – flush (var) Нить1 выполняет операцию синхронизации – flush (var) Нить1 читает значение переменной – read (var) Директива flush: #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, если изменилось состояние семафора. Технология параллельного программирования OpenMP : Функциональная отладка OpenMP-программ Москва, 2012 г.

23 из 49 Распределение циклов с зависимостью по данным. Организация конвейерного выполнения цикла. int isync[NUMBER_OF_THREADS]; int iam, numt, limit; #pragma omp parallel private(iam,numt,limit) { iam = omp_get_thread_num (); numt = omp_get_num_threads (); limit=min(numt-1,N-2); isync[iam]=0; #pragma omp barrier for (int i=1; i0) && (iam

24 из 49 Конфликт доступа к данным Москва, 2012 г. Технология параллельного программирования OpenMP : Функциональная отладка OpenMP-программ #define ITMAX 20 #define Max(a,b) ((a)>(b)?(a):(b)) double MAXEPS = 0.5; double grid[L][L], tmp[L][L],eps; #pragma omp parallel { for (int it=0;it

25 из 49 Конфликт доступа к данным Москва, 2012 г. Технология параллельного программирования OpenMP : Функциональная отладка OpenMP-программ #define Max(a,b) ((a)>(b)?(a):(b)) double MAXEPS = 0.5; double grid[L][L], tmp[L][L],eps; #pragma omp parallel { for (int it=0;it

26 из 49 Взаимная блокировка нитей Москва, 2012 г. Технология параллельного программирования OpenMP : Функциональная отладка OpenMP-программ #define N 10 int A[N],B[N], sum; #pragma omp parallel num_threads(10) { int iam=omp_get_thread_num(); if (iam ==0) { #pragma omp critical (update_a) #pragma omp critical (update_b) sum +=A[iam]; } else { #pragma omp critical (update_b) #pragma omp critical (update_a) sum +=B[iam]; }

27 из 49 Семафоры в OpenMP Москва, 2012 г. Технология параллельного программирования OpenMP : Функциональная отладка OpenMP-программ #include #define N 100 #define Max(a,b) ((a)>(b)?(a):(b)) int main () { omp_lock_t lck; float A[N], maxval; #pragma omp parallel { #pragma omp master maxval = 0.0; #pragma omp barrier #pragma omp for for(int i=0; i

28 из 49 Семафоры в OpenMP Москва, 2012 г. Технология параллельного программирования OpenMP : Функциональная отладка OpenMP-программ #include #define N 100 #define Max(a,b) ((a)>(b)?(a):(b)) int main () { omp_lock_t lck; float A[N], maxval; omp_init_lock(&lck); #pragma omp parallel { #pragma omp master maxval = 0.0; #pragma omp barrier #pragma omp for for(int i=0; i

29 из 49 Взаимная блокировка нитей Москва, 2012 г. Технология параллельного программирования OpenMP : Функциональная отладка OpenMP-программ #pragma omp parallel { int iam=omp_get_thread_num(); if (iam ==0) { omp_set_lock (&lcka); omp_set_lock (&lckb); x = x + 1; omp_unset_lock (&lckb); omp_unset_lock (&lcka); } else { omp_set_lock (&lckb); omp_set_lock (&lcka); x = x + 2; omp_unset_lock (&lcka); omp_unset_lock (&lckb); }

30 из 49 Взаимная блокировка нитей Москва, 2012 г. Технология параллельного программирования OpenMP : Функциональная отладка OpenMP-программ #pragma omp parallel { int iam=omp_get_thread_num(); if (iam ==0) { omp_set_lock (&lcka); while (x

31 из 49 Неинициализированные переменные Москва, 2012 г. Технология параллельного программирования OpenMP : Функциональная отладка OpenMP-программ #define N 100 #define Max(a,b) ((a)>(b)?(a):(b)) float A[N], maxval, localmaxval; maxval = localmaxval = 0.0; #pragma omp parallel private (localmaxval) { #pragma omp for for(int i=0; i

32 из 49 Неинициализированные переменные Москва, 2012 г. Технология параллельного программирования OpenMP : Функциональная отладка OpenMP-программ #define N 100 #define Max(a,b) ((a)>(b)?(a):(b)) float A[N], maxval, localmaxval; maxval = localmaxval = 0.0; #pragma omp parallel firstprivate (localmaxval) { #pragma omp for for(int i=0; i

33 из 49 Неинициализированные переменные Москва, 2012 г. Технология параллельного программирования OpenMP : Функциональная отладка OpenMP-программ int tmp = 0; #pragma omp parallel { #pragma omp for firstprivate(tmp), lastprivate (tmp) for (int j = 0; j < 100; ++j) { if (j

34 из 49 Неинициализированные переменные Москва, 2012 г. Технология параллельного программирования OpenMP : Функциональная отладка OpenMP-программ static int counter; #pragma omp threadprivate(counter) int main () { counter = 0; #pragma omp parallel { counter++; }

35 из 49 Неинициализированные переменные Москва, 2012 г. Технология параллельного программирования OpenMP : Функциональная отладка OpenMP-программ static int counter; #pragma omp threadprivate(counter) int main () { counter = 0; #pragma omp parallel copyin (counter) { counter++; }

36 из 49 Автоматизированный поиск ошибок. Intel Thread Checker (Intel Parallel Inspector) Москва, 2012 г. Технология параллельного программирования OpenMP : Функциональная отладка OpenMP-программ KAI Assure for Threads (Kuck and Associates) Анализ программы основан на процедуре инструментации. Инструментация – вставка обращений для записи действий, потенциально способных привести к ошибкам: работа с памятью, вызовы операций синхронизации и работа с потоками. Может выполняться: автоматически (бинарная инструментация) на уровне исполняемого модуля (а также dll-библиотеки) и/или по указанию программиста на уровне исходного кода (компиляторная инструментация Windows).

37 из 49 Автоматизированный поиск ошибок. Intel Thread Checker Москва, 2012 г. Технология параллельного программирования OpenMP : Функциональная отладка OpenMP-программ Для каждой использованной в программе переменной сохраняется: адрес переменной; тип использования (read или write); наличие/отсутствие операции синхронизации; номер строки и имя файла; call stack. Инструментация программы + большой объем сохраняемой информации для каждого обращения = существенные накладные расходы и замедление выполнения программы.

38 из 49 Пакет тестов SPLASH-2 (Stanford Parallel Applications for Shared Memory) на 4-х ядерной машине Москва, 2012 г. Технология параллельного программирования OpenMP : Функциональная отладка OpenMP-программ

39 из 49 Автоматизированный поиск ошибок. Sun Thread Analyzer Москва, 2012 г. Технология параллельного программирования OpenMP : Функциональная отладка OpenMP-программ Инструментация программы: cc -xinstrument=datarace -g -xopenmp=noopt test.c Накопление информации о программе: еxport OMP_NUM_THREADS=2 collect -r race./a.out collect -r deadlock./a.out collect -r all./a.out Получение результатов анализа программы tha test.1.er => GUI er_print test.1.er => интерфейс командной строки

40 из 49 Автоматизированный поиск ошибок. Sun Thread Analyzer Москва, 2012 г. Технология параллельного программирования OpenMP : Функциональная отладка OpenMP-программ if (iam==0) { user_lock (); data = … … } else { user_lock (); … = data; … } if (iam==0) { ptr1 = mymalloc(sizeof(data_t)); ptr1->data = myfree(ptr1); } else { ptr2 = mymalloc(sizeof(data_t)); ptr2->data = myfree(ptr2); } Может выдавать сообщения об ошибках там где их нет

41 из 49 Intel Thread Checker и Sun Thread Analyzer Москва, 2012 г. Технология параллельного программирования OpenMP : Функциональная отладка OpenMP-программ ПрограммаJacobian Solver Sparse Matrix- Vector multiplication Adaptive Integration Solver Mem MFLOP/ s Mem MFLOP/ s MemTime Intel on 2 Threads s Intel Thread Checker on 2 Threads s Intel Thread Checker –tcheck Sun on 2 Threads s Sun Thread Analyzer on 2 Threads s

42 из 49

43 из 49

44 из 49

45 из 49

46 из 49

47 из 49 Спасибо за внимание! Вопросы? Москва, 2012 г. Технология параллельного программирования OpenMP : Функциональная отладка OpenMP-программ

48 из 49 Отладка эффективности OpenMP-программ. Следующая тема Москва, 2012 г. Технология параллельного программирования OpenMP : Функциональная отладка OpenMP-программ

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