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

Параллельное программирование с OpenMP: Отладка эффективности OpenMP-программ © Бахтин В.А. Москва, 2010 г. 2 из 31 Содержание Основные характеристики производительности Стратегии распределения витков цикла между нитями (клауза schedule) Отмена барьерной синхронизации по окончании выполнения цикла (клауза nowait) Локализация данных Задание поведения нитей во время ожидания (переменная OMP_WAIT_POLICY) Оптимизация OpenMP-программы при помощи Intel Thread Profiler

Параллельное программирование с OpenMP: Отладка эффективности OpenMP-программ © Бахтин В.А. Москва, 2010 г. 3 из 31 Основные характеристики производительности Полезное время - время, которое потребуется для выполнения программы на однопроцессорной ЭВМ. Общее время использования процессоров равно произведению времени выполнения программы на многопроцессорной ЭВМ (максимальное значение среди времен выполнения программы на всех используемых ею процессорах время работы MASTER-нити) на число используемых процессоров. Главная характеристика эффективности параллельного выполнения - коэффициент эффективности равен отношению полезного времени к общему времени использования процессоров. Разница между общим временем использования процессоров и полезным временем представляет собой потерянное время. Существуют следующие составляющие потерянного времени: накладные расходы на создание группы нитей; потери из-за простоев тех нитей, на которых выполнение программы завершилось раньше, чем на остальных (несбалансированная нагрузка нитей); потери из-за синхронизации нитей (например, из-за чрезмерного использования общих данных); потери из-за недостатка параллелизма, приводящего к дублированию вычислений на нескольких процессорах (недостаточный параллелизм).

Параллельное программирование с OpenMP: Отладка эффективности OpenMP-программ © Бахтин В.А. Москва, 2010 г. 4 из 31 Накладные расходы на создание группы нитей void work(int i, int j) {} for (int i=0; i < n; i++) { for (int j=0; j < n; j++) { work(i, j); } #pragma omp parallel for for (int i=0; i < n; i++) { for (int j=0; j < n; j++) { work(i, j); } for (int i=0; i < n; i++) { #pragma omp parallel for for (int j=0; j < n; j++) { work(i, j); }

Параллельное программирование с OpenMP: Отладка эффективности OpenMP-программ © Бахтин В.А. Москва, 2010 г. 5 из 31 Алгоритм Якоби for (int it=0;it

Параллельное программирование с OpenMP: Отладка эффективности OpenMP-программ © Бахтин В.А. Москва, 2010 г. 6 из 31 Накладные расходы на создание группы нитей #include void work(int i) {} int N=0; scanf(«%d»,&N); #pragma omp parallel for if(N>100) for (int i=0; i < N; i++) { work(i); }

Параллельное программирование с OpenMP: Отладка эффективности OpenMP-программ © Бахтин В.А. Москва, 2010 г. 7 из 31 Накладные расходы на создание группы нитей #include void work_on_four_threads(int i) {} #pragma omp parallel num_threads(4) { int iam = omp_get_thread_num (); work_on_four_threads(iam); } omp_set_num_threads (4); #pragma omp parallel { int iam = omp_get_thread_num (); work_on_four_threads(iam); } omp_set_dynamic (1);

Параллельное программирование с OpenMP: Отладка эффективности OpenMP-программ © Бахтин В.А. Москва, 2010 г. 8 из 31 Несбалансированная нагрузка нитей void work(int i, int j) {} int num_threads = omp_get_max_threads(); /*N > num_threads */ #pragma omp for for (int i=0; i < N; i++) { for (int j=0; j < M; j++) { work(i, j); } /*(N N)*/ for (int i=0; i < N; i++) { #pragma omp for for (int j=0; j < M; j++) { work(i, j); } /*OpenMP 3.0*/ #pragma omp for collapse(2) for (int i=0; i < N; i++) { for (int j=0; j < M; j++) { work(i, j); }

Параллельное программирование с OpenMP: Отладка эффективности OpenMP-программ © Бахтин В.А. Москва, 2010 г. 9 из 31 Вложенный параллелизм void work(int i, int j) {} #pragma omp parallel for for (int i=0; i < N; i++) { #pragma omp parallel for for (int j=0; j < M; j++) { work(i, j); } /*OpenMP 3.0*/ #pragma omp parallel for collapse(2) for (int i=0; i < N; i++) { for (int j=0; j < M; j++) { work(i, j); }

Параллельное программирование с OpenMP: Отладка эффективности OpenMP-программ © Бахтин В.А. Москва, 2010 г. 10 из 31 Балансировка нагрузки нитей. Клауза schedule Клауза schedule: schedule(алгоритм планирования[, число_итераций]) Где алгоритм планирования один из: schedule(static[, число_итераций]) - статическое планирование; schedule(dynamic[, число_итераций]) - динамическое планирование; schedule(guided[, число_итераций]) - управляемое планирование; schedule(runtime) - планирование в период выполнения; schedule(auto) - автоматическое планирование (OpenMP 3.0). #pragma omp parallel for schedule(static) for(int i = 0; i < 100; i++) A[i]=0.;

Параллельное программирование с OpenMP: Отладка эффективности OpenMP-программ © Бахтин В.А. Москва, 2010 г. 11 из 31 Балансировка нагрузки нитей. Клауза schedule #pragma omp parallel for schedule(static, 10) for(int i = 1; i

Параллельное программирование с OpenMP: Отладка эффективности OpenMP-программ © Бахтин В.А. Москва, 2010 г. 12 из 31 Балансировка нагрузки нитей. Клауза schedule #pragma omp parallel for schedule(dynamic, 15) for(int i = 0; i < 100; i++) Результат выполнения программы на 4-х ядерном процессоре может быть следующим: Поток 0 получает право на выполнение итераций Поток 1 получает право на выполнение итераций Поток 2 получает право на выполнение итераций Поток 3 получает право на выполнение итераций Поток 3 завершает выполнение итераций. Поток 3 получает право на выполнение итераций Поток 2 завершает выполнение итераций. Поток 2 получает право на выполнение итераций Поток 0 завершает выполнение итераций. Поток 0 получает право на выполнение итераций

Параллельное программирование с OpenMP: Отладка эффективности OpenMP-программ © Бахтин В.А. Москва, 2010 г. 13 из 31 Балансировка нагрузки нитей. Клауза schedule число_выполняемых_потоком_итераций = max(число_нераспределенных_итераций/omp_get_num_threads(), число_итераций) #pragma omp parallel for schedule(guided, 10) for(int i = 0; i < 100; i++) Пусть программа запущена на 4-х ядерном процессоре. Поток 0 получает право на выполнение итераций Поток 1 получает право на выполнение итераций Поток 2 получает право на выполнение итераций Поток 3 получает право на выполнение итераций Поток 3 завершает выполнение итераций. Поток 3 получает право на выполнение итераций Поток 2 завершает выполнение итераций. Поток 2 получает право на выполнение итераций Поток 3 завершает выполнение итераций. Поток 3 получает право на выполнение итераций Поток 1 завершает выполнение итераций. Поток 1 получает право на выполнение 99 итерации.

Параллельное программирование с OpenMP: Отладка эффективности OpenMP-программ © Бахтин В.А. Москва, 2010 г. 14 из 31 Балансировка нагрузки нитей. Клауза schedule #pragma omp parallel for schedule(runtime) for(int i = 0; i < 100; i++) /* способ распределения витков цикла между нитями будет задан во время выполнения программы*/ При помощи переменных среды: csh: setenv OMP_SCHEDULE "dynamic,4 ksh: export OMP_SCHEDULE="static,10 Windows: set OMP_SCHEDULE=auto или при помощи функций системы поддержки: void omp_set_schedule(omp_sched_t kind, int modifier);

Параллельное программирование с OpenMP: Отладка эффективности OpenMP-программ © Бахтин В.А. Москва, 2010 г. 15 из 31 Балансировка нагрузки нитей. Клауза schedule #pragma omp parallel for schedule(auto) for(int i = 0; i < 100; i++) Способ распределения витков цикла между нитями определяется реализацией компилятора. На этапе компиляции программы или во время ее выполнения определяется оптимальный способ распределения.

Параллельное программирование с OpenMP: Отладка эффективности OpenMP-программ © Бахтин В.А. Москва, 2010 г. 16 из 31 Балансировка нагрузки нитей. Клауза schedule #pragma omp parallel for private(tmp) shared (a) schedule (runtime) for (int i=0; i

Параллельное программирование с OpenMP: Отладка эффективности OpenMP-программ © Бахтин В.А. Москва, 2010 г. 17 из 31 Отмена барьерной синхронизации по окончании выполнения цикла. Клауза nowait void example(int n, float *a, float *b, float *z, int n) { int i; #pragma omp parallel { #pragma omp for schedule(static) nowait for (i=0; i

Параллельное программирование с OpenMP: Отладка эффективности OpenMP-программ © Бахтин В.А. Москва, 2010 г. 18 из 31 Локализация данных #pragma omp parallel shared (var) { { var = … } Модификация общей переменной в параллельной области должна осуществляться в критической секции (critical/atomic/omp_set_lock). Если локализовать данную переменную (например, private(var)), то можно сократить потери на синхронизацию нитей.

Параллельное программирование с OpenMP: Отладка эффективности OpenMP-программ © Бахтин В.А. Москва, 2010 г. 19 из 31 Потери из-за синхронизации нитей Москва, 2010 г. #define Max(a,b) ((a)>(b)?(a):(b)) double MAXEPS = 0.5; double grid[L][L], tmp[L][L],eps; for (int it=0;it

Параллельное программирование с OpenMP: Отладка эффективности OpenMP-программ © Бахтин В.А. Москва, 2010 г. 20 из 31 Локализация данных Москва, 2010 г. #define Max(a,b) ((a)>(b)?(a):(b)) double MAXEPS = 0.5; double grid[L][L], tmp[L][L],eps,localeps; for (int it=0;it

Параллельное программирование с OpenMP: Отладка эффективности OpenMP-программ © Бахтин В.А. Москва, 2010 г. 21 из 31 Локализация данных Москва, 2010 г. double grid[L][L], tmp[L][L],eps,MAXEPS; int num_threads = omp_get_max_threads(); double *localeps = (double *)malloc(num_threads*sizeof(double)); for (int it=0;it

Параллельное программирование с OpenMP: Отладка эффективности OpenMP-программ © Бахтин В.А. Москва, 2010 г. 22 из 31 Потери из-за синхронизации нитей Москва, 2010 г. int i=0; #pragma omp parallel { #pragma omp critical I++;... }

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

Параллельное программирование с OpenMP: Отладка эффективности OpenMP-программ © Бахтин В.А. Москва, 2010 г. 24 из 31 Потери из-за синхронизации нитей Москва, 2010 г. int i=0; #pragma omp parallel { #pragma omp critical i++;... } int i=0; #pragma omp parallel { #pragma omp atomic i++;... }

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

Параллельное программирование с OpenMP: Отладка эффективности OpenMP-программ © Бахтин В.А. Москва, 2010 г. 26 из 31 Распределение циклов с зависимостью по данным. #pragma omp parallel private(iam,numt,limit) { for (int i=1; i

Параллельное программирование с OpenMP: Отладка эффективности OpenMP-программ © Бахтин В.А. Москва, 2010 г. 27 из 31 Переменная OMP_WAIT_POLICY. Подсказка OpenMP-компилятору о желаемом поведении нитей во время ожидания. Значение переменной можно изменить: setenv OMP_WAIT_POLICY ACTIVE setenv OMP_WAIT_POLICY active setenv OMP_WAIT_POLICY PASSIVE setenv OMP_WAIT_POLICY passive IBM AIX SPINLOOPTIME= Sun Studio setenv SUNW_MP_THR_IDLE SPIN setenv SUNW_MP_THR_IDLE SLEEP setenv SUNW_MP_THR_IDLE SLEEP(2s) setenv SUNW_MP_THR_IDLE SLEEP(20ms) setenv SUNW_MP_THR_IDLE SLEEP(150mc)

Параллельное программирование с OpenMP: Отладка эффективности OpenMP-программ © Бахтин В.А. Москва, 2010 г. 28 из 31 Оптимизация для DSM-систем #pragma omp parallel for for (int i=1; i

Параллельное программирование с OpenMP: Отладка эффективности OpenMP-программ © Бахтин В.А. Москва, 2010 г. 29 из 31 Intel Thread Profiler Предназначен для анализа производительности OpenMP- приложений или многопоточных приложений с использованием потоков Win32 API и POSIX. Визуализация выполнения потоков во времени помогает понять их функции и взаимодействие. Инструмент указывает на узкие места, снижающие производительность. Инструментация программы: Linux: -g [-openmp_profile] Windows: /Zi [/-Qopenmp_profile], link with /fixed:no

Параллельное программирование с OpenMP: Отладка эффективности OpenMP-программ © Бахтин В.А. Москва, 2010 г. 30 из 31 Спасибо за внимание! Вопросы?

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