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

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

3 из 51 Конфликт доступа к данным Москва, 2013 г. Параллельное программирование с 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 из 51 Ошибка возникает при одновременном выполнении следующих условий: Две или более нитей обращаются к одной и той же ячейке памяти. По крайней мере, один из этих доступов к памяти является записью. Нити не синхронизируют свой доступ к данной ячейки памяти. При одновременном выполнении всех трех условий порядок доступа становится неопределенным. Конфликт доступа к данным Москва, 2013 г. Параллельное программирование с OpenMP: Функциональная отладка OpenMP-программ © Бахтин В.А.

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

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

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

8 из 51 Конфликт доступа к данным Москва, 2013 г. Параллельное программирование с 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 из 51 Директива threadprivate threadprivate – переменные сохраняют глобальную область видимости внутри каждой нити #pragma omp threadprivate (Var) Var = 1 Var = 2 … = Var Если количество нитей не изменилось, то каждая нить получит значение, посчитанное в предыдущей параллельной области. Параллельное программирование с OpenMP: Функциональная отладка OpenMP-программ © Бахтин В.А. Москва, 2013 г.

10 из 51 Конфликт доступа к данным Москва, 2013 г. Параллельное программирование с 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 из 51 Конфликт доступа к данным Москва, 2013 г. Параллельное программирование с OpenMP: Функциональная отладка OpenMP-программ © Бахтин В.А. #define N 100 #define Max(a,b) ((a)>(b)?(a):(b)) float A[N], B[N], maxval; #pragma omp parallel { #pragma omp master maxval = 0.0; #pragma omp for for(int i=1; i

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

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

14 из 51 Конфликт доступа к данным Москва, 2013 г. Параллельное программирование с 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 из 51 Конфликт доступа к данным Москва, 2013 г. Параллельное программирование с 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 из 51 Конфликт доступа к данным Москва, 2013 г. Параллельное программирование с 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 из 51 Конфликт доступа к данным Москва, 2013 г. Параллельное программирование с 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 из 51 Распределение циклов с зависимостью по данным. Организация конвейерного выполнения цикла. 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-программ © Бахтин В.А. Москва, 2013 г.

19 из 51 Распределение циклов с зависимостью по данным. Организация конвейерного выполнения цикла. 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-программ © Бахтин В.А. Москва, 2013 г.

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-программ © Бахтин В.А. Москва, 2013 г.

22 из 51 Консистентность памяти в 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-программ © Бахтин В.А. Москва, 2013 г.

23 из 51 Распределение циклов с зависимостью по данным. Организация конвейерного выполнения цикла. 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 из 51 Конфликт доступа к данным Москва, 2013 г. Параллельное программирование с 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 из 51 Конфликт доступа к данным Москва, 2013 г. Параллельное программирование с 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

26 из 51 Конфликт доступа к данным Москва, 2013 г. Параллельное программирование с 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

27 из 51 Взаимная блокировка нитей Москва, 2013 г. Параллельное программирование с 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]; }

28 из 51 Семафоры в OpenMP Москва, 2013 г. Параллельное программирование с 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

29 из 51 Семафоры в OpenMP Москва, 2013 г. Параллельное программирование с 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

30 из 51 Взаимная блокировка нитей Москва, 2013 г. Параллельное программирование с 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); }

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

32 из 51 Неинициализированные переменные Москва, 2013 г. Параллельное программирование с 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

33 из 51 Неинициализированные переменные Москва, 2013 г. Параллельное программирование с 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

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

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

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

37 из 51 Автоматизированный поиск ошибок. Intel Thread Checker (Intel Parallel Inspector) Москва, 2013 г. Параллельное программирование с OpenMP: Функциональная отладка OpenMP-программ © Бахтин В.А. KAI Assure for Threads (Kuck and Associates) Анализ программы основан на процедуре инструментации. Инструментация – вставка обращений для записи действий, потенциально способных привести к ошибкам: работа с памятью, вызовы операций синхронизации и работа с потоками. Может выполняться: автоматически (бинарная инструментация) на уровне исполняемого модуля (а также dll-библиотеки) и/или по указанию программиста на уровне исходного кода (компиляторная инструментация Windows). Windows: /DEBUG /Zi Linux: -g Использовать динамические runtime-библиотеки (Windows: /MDd)

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

39 из 51 Пакет тестов SPLASH-2 (Stanford Parallel Applications for Shared Memory) на 4-х ядерной машине Москва, 2013 г. Параллельное программирование с OpenMP: Функциональная отладка OpenMP-программ © Бахтин В.А.

40 из 51 Автоматизированный поиск ошибок. Sun Thread Analyzer Москва, 2013 г. Параллельное программирование с 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 => интерфейс командной строки

41 из 51 Автоматизированный поиск ошибок. Sun Thread Analyzer Москва, 2013 г. Параллельное программирование с 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); } Может выдавать сообщения об ошибках там где их нет

42 из 51 Intel Thread Checker и Sun Thread Analyzer Москва, 2013 г. Параллельное программирование с 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

43 из 51 Требования к тестам Москва, 2013 г. Параллельное программирование с OpenMP: Функциональная отладка OpenMP-программ © Бахтин В.А. При анализе ошибок связанных с многопоточностью использовать минимальные объемы данных: Сократить количество итераций в алгоритмах Минимизировать размер изображений При анализе ошибок памяти использовать максимальные объемы данных. Использовать полные тесты: Анализируется только исполняемый код Каждая ветка кода должна исполнится хотя бы один раз

44 из 51

45 из 51

46 из 51

47 из 51

48 из 51

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

50 из 51 Отладка эффективности OpenMP-программ. Следующая тема Москва, 2013 г. Параллельное программирование с OpenMP: Функциональная отладка OpenMP-программ © Бахтин В.А.

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