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

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

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

Технология параллельного программирования OpenMP: Отладка эффективности OpenMP-программ Москва, 2012 г. 4 из 44 Накладные расходы на создание группы нитей 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-программ Москва, 2012 г. 5 из 44 Алгоритм Якоби for (int it=0;it

Технология параллельного программирования OpenMP: Отладка эффективности OpenMP-программ Москва, 2012 г. 6 из 44 Накладные расходы на создание группы нитей #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-программ Москва, 2012 г. 7 из 44 Накладные расходы на создание группы нитей #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-программ Москва, 2012 г. 8 из 44 Несбалансированная нагрузка нитей 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-программ Москва, 2012 г. 9 из 44 Вложенный параллелизм 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-программ Москва, 2012 г. 10 из 44 Балансировка нагрузки нитей. Клауза 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-программ Москва, 2012 г. 11 из 44 Балансировка нагрузки нитей. Клауза schedule #pragma omp parallel for schedule(static, 10) for(int i = 1; i

Технология параллельного программирования OpenMP: Отладка эффективности OpenMP-программ Москва, 2012 г. 12 из 44 Балансировка нагрузки нитей. Клауза 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-программ Москва, 2012 г. 13 из 44 Балансировка нагрузки нитей. Клауза 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-программ Москва, 2012 г. 14 из 44 Балансировка нагрузки нитей. Клауза 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-программ Москва, 2012 г. 15 из 44 Балансировка нагрузки нитей. Клауза schedule #pragma omp parallel for schedule(auto) for(int i = 0; i < 100; i++) Способ распределения витков цикла между нитями определяется реализацией компилятора. На этапе компиляции программы или во время ее выполнения определяется оптимальный способ распределения.

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

Технология параллельного программирования OpenMP: Отладка эффективности OpenMP-программ Москва, 2012 г. 17 из 44 Отмена барьерной синхронизации по окончании выполнения цикла. Клауза 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-программ Москва, 2012 г. 18 из 44 Локализация данных #pragma omp parallel shared (var) { { var = … } Модификация общей переменной в параллельной области должна осуществляться в критической секции (critical/atomic/omp_set_lock). Если локализовать данную переменную (например, private(var)), то можно сократить потери на синхронизацию нитей.

Технология параллельного программирования OpenMP: Отладка эффективности OpenMP-программ Москва, 2012 г. 19 из 44 Потери из-за синхронизации нитей Москва, 2012 г. #define Max(a,b) ((a)>(b)?(a):(b)) double MAXEPS = 0.5; double grid[L][L], temp[L][L],eps; #pragma omp parallel default (none) shared (grid,temp,eps) for (int it=0;it

Технология параллельного программирования OpenMP: Отладка эффективности OpenMP-программ Москва, 2012 г. 20 из 44 Локализация данных Москва, 2012 г. #define Max(a,b) ((a)>(b)?(a):(b)) double MAXEPS = 0.5; double grid[L][L], temp[L][L],eps; #pragma omp parallel default (none) shared (grid,temp,eps) for (int it=0;it

Технология параллельного программирования OpenMP: Отладка эффективности OpenMP-программ Москва, 2012 г. 21 из 44 Локализация данных Москва, 2012 г. double grid[L][L], temp[L][L],eps; int num_threads = omp_get_max_threads(); double *localeps = (double *)malloc(num_threads*sizeof(double)); #pragma omp parallel default (none) shared (grid,temp,eps,localeps) for (int it=0;it

Технология параллельного программирования OpenMP: Отладка эффективности OpenMP-программ Москва, 2012 г. 22 из 44 False-Sharing Москва, 2012 г.

Технология параллельного программирования OpenMP: Отладка эффективности OpenMP-программ Москва, 2012 г. 23 из 44 Потери из-за синхронизации нитей Москва, 2012 г. int i=0; #pragma omp parallel { #pragma omp critical i++;... }

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

Технология параллельного программирования OpenMP: Отладка эффективности OpenMP-программ Москва, 2012 г. 25 из 44 Потери из-за синхронизации нитей Москва, 2012 г. int i=0; #pragma omp parallel { #pragma omp critical i++;... } int i=0; #pragma omp parallel { #pragma omp atomic i++;... }

Технология параллельного программирования OpenMP: Отладка эффективности OpenMP-программ Москва, 2012 г. 26 из 44 Распределение циклов с зависимостью по данным. Организация конвейерного выполнения цикла. 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-программ Москва, 2012 г. 27 из 44 Распределение циклов с зависимостью по данным. #pragma omp parallel { for (int i=1; i

Технология параллельного программирования OpenMP: Отладка эффективности OpenMP-программ Москва, 2012 г. 28 из 44 Переменная 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-программ Москва, 2012 г. 29 из 44 Система состоит из однородных базовых модулей (плат), состоящих из небольшого числа процессоров и блока памяти. Модули объединены с помощью высокоскоростного коммутатора. Поддерживается единое адресное пространство. Доступ к локальной памяти в несколько раз быстрее, чем к удаленной. Системы с неоднородным доступом к памяти (NUMA)

Технология параллельного программирования OpenMP: Отладка эффективности OpenMP-программ Москва, 2012 г. 30 из 44 Системы с неоднородным доступом к памяти (NUMA) SGI Altix UV (UltraVioloet) Intel® Xeon® quad-, six- or eight-core 7500 series (2048 cores) 16 TB памяти Interconnect Speed 15 ГБ/с, 1мкс

Технология параллельного программирования OpenMP: Отладка эффективности OpenMP-программ Москва, 2012 г. 31 из 44 Оптимизация для cистем типа NUMA #pragma omp parallel for for (int i=1; i

Технология параллельного программирования OpenMP: Отладка эффективности OpenMP-программ Москва, 2012 г. 32 из 44 Intel Thread Profiler Предназначен для анализа производительности OpenMP- приложений или многопоточных приложений с использованием потоков Win32 API и POSIX. Визуализация выполнения потоков во времени помогает понять их функции и взаимодействие. Инструмент указывает на узкие места, снижающие производительность. Инструментация программы: Linux: -g [-openmp-profile] Windows: /Zi [/-Qopenmp-profile], link with /fixed:no

Технология параллельного программирования OpenMP: Отладка эффективности OpenMP-программ Москва, 2012 г. 33 из 44

Технология параллельного программирования OpenMP: Отладка эффективности OpenMP-программ Москва, 2012 г. 34 из 44

Технология параллельного программирования OpenMP: Отладка эффективности OpenMP-программ Москва, 2012 г. 35 из 44

Технология параллельного программирования OpenMP: Отладка эффективности OpenMP-программ Москва, 2012 г. 36 из 44

Технология параллельного программирования OpenMP: Отладка эффективности OpenMP-программ Москва, 2012 г. 37 из 44

Технология параллельного программирования OpenMP: Отладка эффективности OpenMP-программ Москва, 2012 г. 38 из 44 Intel Vtune Amplifier XE 2012

Технология параллельного программирования OpenMP: Отладка эффективности OpenMP-программ Москва, 2012 г. 39 из 44 Intel Vtune Amplifier XE 2012

Технология параллельного программирования OpenMP: Отладка эффективности OpenMP-программ Москва, 2012 г. 40 из 44 Intel Vtune Amplifier XE 2012

Технология параллельного программирования OpenMP: Отладка эффективности OpenMP-программ Москва, 2012 г. 41 из 44 Intel Vtune Amplifier XE 2012

Технология параллельного программирования OpenMP: Отладка эффективности OpenMP-программ Москва, 2012 г. 42 из 44 Intel Vtune Amplifier XE 2012

Технология параллельного программирования OpenMP: Отладка эффективности OpenMP-программ Москва, 2012 г. 43 из 44 Спасибо за внимание! Вопросы?

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