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

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

3 из 50 При взаимодействии через общую память нити должны синхронизовать свое выполнение. int i=0; #pragma omp parallel { i++; } Конфликт доступа к данным Москва, 2010 г. Параллельное программирование с OpenMP: Функциональная отладка OpenMP-программ © Бахтин В.А. ВремяThread0Thread1 1load i (i = 0) 2incr i (i = 1) 3->->load i (i = 0) 4incr i (i = 1) 5store i (i = 1) 6

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

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

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

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

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

10 из 50 Конфликт доступа к данным Москва, 2010 г. Параллельное программирование с 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 из 50 Конфликт доступа к данным Москва, 2010 г. Параллельное программирование с 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 из 50 Конфликт доступа к данным Москва, 2010 г. Параллельное программирование с 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 из 50 Конфликт доступа к данным Москва, 2010 г. Параллельное программирование с 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 из 50 Конфликт доступа к данным Москва, 2010 г. Параллельное программирование с 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(runtime) nowait for (i=0; i

15 из 50 Конфликт доступа к данным Москва, 2010 г. Параллельное программирование с 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(runtime) for (i=0; i

16 из 50 Конфликт доступа к данным Москва, 2010 г. Параллельное программирование с 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 из 50 Конфликт доступа к данным Москва, 2010 г. Параллельное программирование с 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 из 50 Распределение циклов с зависимостью по данным for(int i = 1; i < 100; i++) a[i]= a[i-1] + a[i+1] Между витками цикла с индексами i1 и i2 ( i1 i2. Если виток i1 читает старое значение, а виток i2 записывает новое значение, то между этими витками существует обратная зависимость i1

19 из 50 Распределение циклов с зависимостью по данным Цикл с зависимостью по данным может быть распараллелен с помощью конструкции ordered: #pragma omp parallel for ordered for(int i = 1; i < 100; i++) { #pragma omp ordered { a[i]= a[i-1] + a[i+1] } Параллельное программирование с OpenMP: Функциональная отладка OpenMP-программ © Бахтин В.А. Москва, 2010 г.

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

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

22 из 50 Распределение циклов с зависимостью по данным. Организация конвейерного выполнения цикла. 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

23 из Модель памяти в OpenMP Нить 001 Нить 001 Нить Параллельное программирование с OpenMP: Функциональная отладка OpenMP-программ © Бахтин В.А. Москва, 2010 г.

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

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

26 из 50 Распределение циклов с зависимостью по данным. Организация конвейерного выполнения цикла. 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

42 из 50 Автоматизированный поиск ошибок. Intel Thread Checker Москва, 2010 г. Параллельное программирование с OpenMP: Функциональная отладка OpenMP-программ © Бахтин В.А. Инструментация программы: Linux: -g -openmp [–tcheck] Windows: /Zi /Qopenmp [/Qtcheck], link with /fixed:no Запуск программы на выполнение и анализ результатов: [export OMP_NUM_THREADS=2] tcheck_cl program arguments Инструментация программы компилятором позволяет предоставить информацию о найденных ошибках с указанием имен переменных, с которыми эти ошибки связаны

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

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

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

46 из 50 Автоматизированный поиск ошибок. Sun Thread Analyzer Москва, 2009 г. Параллельное программирование с OpenMP: Функциональная отладка OpenMP-программ © Бахтин В.А. if (iam==0) { data = … user_lock (); } 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); } Может выдавать сообщения об ошибках там где их нет

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

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

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

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