'

Отладка эффективности OpenMP-программ.

Понравилась презентация – покажи это...





Слайд 0

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


Слайд 1

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


Слайд 2

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


Слайд 3

Накладные расходы на создание группы нитей 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); } }


Слайд 4

Алгоритм Якоби for (int it=0;it<ITMAX; it++) { for (int i=1; i<N-1; i++ ) for( int j=1; j<N-1; j++ ) temp[i][j] = 0.25 * ( grid[i-1][j] + grid[i+1][j] + grid[i][j-1] + grid[i][j+1]); for (int i=0; i<N; i++ ) for( int j=0; j<N; j++ ) grid[i][j] = temp[i][j]; } for (int it=0;it<ITMAX; it++) { #pragma omp parallel for for (int i=1; i<N-1; i++ ) for (int j=1; j<N-1; j++ ) temp[i][j] = 0.25 * ( grid[i-1][j] + grid[i+1][j] + grid[i][j-1] + grid[i][j+1]); #pragma omp parallel for for (int i=1; i<N-1; i++ ) for (int j=1; j<N-1; j++ ) grid[i][j] = temp[i][j]; } #pragma omp parallel { for (int it=0;it<ITMAX; it++) { #pragma omp for for (int i=1; i<N-1; i++ ) for (int j=1; j<N-1; j++ ) temp[i][j] = 0.25 * ( grid[i-1][j] + grid[i+1][j] + grid[i][j-1] + grid[i][j+1]); #pragma omp for for (int i=1; i<N-1; i++ ) for (int j=1; j<N-1; j++ ) grid[i][j] = temp[i][j]; } }


Слайд 5

Накладные расходы на создание группы нитей #include <stdio.h> 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); }


Слайд 6

Накладные расходы на создание группы нитей #include <omp.h> 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);


Слайд 7

Несбалансированная нагрузка нитей 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<=num_threads) && (M>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); } }


Слайд 8

Вложенный параллелизм 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); } }


Слайд 9

Балансировка нагрузки нитей. Клауза 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.;


Слайд 10

Балансировка нагрузки нитей. Клауза schedule #pragma omp parallel for schedule(static, 10) for(int i = 1; i <= 100; i++) Результат выполнения программы на 4-х ядерном процессоре может быть следующим: Поток 0 получает право на выполнение итераций 1-10, 41-50, 81-90. Поток 1 получает право на выполнение итераций 11-20, 51-60, 91-100. Поток 2 получает право на выполнение итераций 21-30, 61-70. Поток 3 получает право на выполнение итераций 31-40, 71-80


Слайд 11

Балансировка нагрузки нитей. Клауза schedule #pragma omp parallel for schedule(dynamic, 15) for(int i = 0; i < 100; i++) Результат выполнения программы на 4-х ядерном процессоре может быть следующим: Поток 0 получает право на выполнение итераций 1-15. Поток 1 получает право на выполнение итераций 16-30. Поток 2 получает право на выполнение итераций 31-45. Поток 3 получает право на выполнение итераций 46-60. Поток 3 завершает выполнение итераций. Поток 3 получает право на выполнение итераций 61-75. Поток 2 завершает выполнение итераций. Поток 2 получает право на выполнение итераций 76-90. Поток 0 завершает выполнение итераций. Поток 0 получает право на выполнение итераций 91-100.


Слайд 12

Балансировка нагрузки нитей. Клауза schedule число_выполняемых_потоком_итераций = max(число_нераспределенных_итераций/omp_get_num_threads(), число_итераций) #pragma omp parallel for schedule(guided, 10) for(int i = 0; i < 100; i++) Пусть программа запущена на 4-х ядерном процессоре. Поток 0 получает право на выполнение итераций 1-25. Поток 1 получает право на выполнение итераций 26-44. Поток 2 получает право на выполнение итераций 45-59. Поток 3 получает право на выполнение итераций 60-69. Поток 3 завершает выполнение итераций. Поток 3 получает право на выполнение итераций 70-79. Поток 2 завершает выполнение итераций. Поток 2 получает право на выполнение итераций 80-89. Поток 3 завершает выполнение итераций. Поток 3 получает право на выполнение итераций 90-99. Поток 1 завершает выполнение итераций. Поток 1 получает право на выполнение 99 итерации.


Слайд 13

Балансировка нагрузки нитей. Клауза 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);


Слайд 14

Балансировка нагрузки нитей. Клауза schedule #pragma omp parallel for schedule(auto) for(int i = 0; i < 100; i++) Способ распределения витков цикла между нитями определяется реализацией компилятора. На этапе компиляции программы или во время ее выполнения определяется оптимальный способ распределения.


Слайд 15

Балансировка нагрузки нитей. Клауза schedule #pragma omp parallel for private(tmp) shared (a) schedule (runtime) for (int i=0; i<N-2; i++) for (int j = i+1; j< N-1; j++) { tmp = a[i][j]; a[i][j]=a[j][i]; a[j][i]=tmp; } export OMP_SCHEDULE="static" export OMP_SCHEDULE="static,10" export OMP_SCHEDULE="dynamic" export OMP_SCHEDULE="dynamic,10"


Слайд 16

Отмена барьерной синхронизации по окончании выполнения цикла. Клауза 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<n; i++) c[i] = (a[i] + b[i]) / 2.0; #pragma omp for schedule(static) nowait for (i=0; i<n; i++) z[i] = sqrt(c[i]); } }


Слайд 17

Локализация данных #pragma omp parallel shared (var) { <критическая секция> { var = … } } Модификация общей переменной в параллельной области должна осуществляться в критической секции (critical/atomic/omp_set_lock). Если локализовать данную переменную (например, private(var)), то можно сократить потери на синхронизацию нитей.


Слайд 18

Потери из-за синхронизации нитей Москва, 2013 г. #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<ITMAX; it++) { #pragma omp barrier #pragma omp single eps= 0.; #pragma omp for for (int i=1; i<N-1; i++ ) for (int j=1; j<N-1; j++ ) { #pragma omp critical eps = Max(fabs(temp[i][j]-grid[i][j]),eps); grid[i][j] = temp[i][j]; } #pragma omp for for (int i=1; i<N-1; i++ ) for (int j=1; j<N-1; j++ ) temp[i][j] = 0.25 * ( grid[i-1][j] + grid[i+1][j] + grid[i][j-1] + grid[i][j+1]); if (eps < MAXEPS) break; }


Слайд 19

Локализация данных Москва, 2013 г. #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<ITMAX; it++) { double localeps=0.; #pragma omp for for (int i=1; i<N-1; i++ ) for (int j=1; j<N-1; j++ ) { localeps = Max(fabs(temp[i][j]-grid[i][j]),localeps); grid[i][j] = temp[i][j]; } #pragma omp single eps= 0.; #pragma omp critical eps = Max(eps,localeps); #pragma omp for for (int i=1; i<N-1; i++ ) for (int j=1; j<N-1; j++ ) temp[i][j] = 0.25 * ( grid[i-1][j] + grid[i+1][j] + grid[i][j-1] + grid[i][j+1]); if (eps < MAXEPS) break; }


Слайд 20

Локализация данных Москва, 2013 г. 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<ITMAX; it++) { int iam = omp_get_thread_num (); localeps[iam]=0.; #pragma omp for for (int i=1; i<N-1; i++ ) for (int j=1; j<N-1; j++ ) { localeps[iam] = Max(fabs(temp[i][j]-grid[i][j]),localeps[iam]); grid[i][j] = temp[i][j]; } #pragma omp single for (int i=0, eps = 0.;i<num_threads;i++) eps = Max(localeps[i],eps); #pragma omp for for (int i=1; i<N-1; i++ ) for (int j=1; j<N-1; j++ ) temp[i][j] = 0.25 * ( grid[i-1][j] + grid[i+1][j] + grid[i][j-1] + grid[i][j+1]); if (eps < MAXEPS) break; }


Слайд 21

False-Sharing Москва, 2013 г.


Слайд 22

Потери из-за синхронизации нитей Москва, 2013 г. int i=0; #pragma omp parallel { #pragma omp critical i++; ... }


Слайд 23

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


Слайд 24

Потери из-за синхронизации нитей Москва, 2013 г. int i=0; #pragma omp parallel { #pragma omp critical i++; ... } int i=0; #pragma omp parallel { #pragma omp atomic i++; ... }


Слайд 25

Распределение циклов с зависимостью по данным. Организация конвейерного выполнения цикла. Москва, 2013 г.


Слайд 26

Распределение циклов с зависимостью по данным. Москва, 2013 г.


Слайд 27

Переменная 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=100000 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)


Слайд 28

Система состоит из однородных базовых модулей (плат), состоящих из небольшого числа процессоров и блока памяти. Модули объединены с помощью высокоскоростного коммутатора. Поддерживается единое адресное пространство. Доступ к локальной памяти в несколько раз быстрее, чем к удаленной. Системы с неоднородным доступом к памяти (NUMA)


Слайд 29

Системы с неоднородным доступом к памяти (NUMA) SGI Altix UV (UltraVioloet) 1000 256 Intel® Xeon® quad-, six- or eight-core 7500 series (2048 cores) 16 TB памяти Interconnect Speed 15 ГБ/с, 1мкс http://www.sgi.com/products/servers/altix/uv/


Слайд 30

Оптимизация для cистем типа NUMA #pragma omp parallel for for (int i=1; i<N-1; i++ ) for (int j=1; j<N-1; j++ ) { // first-touch algoritm temp[i][j] = 0.; grid[i][j] = 1. + i + j; } for (int it=0;it<ITMAX; it++) { #pragma omp parallel for for (int i=1; i<N-1; i++ ) for (int j=1; j<N-1; j++ ) temp[i][j] = 0.25 * ( grid[i-1][j] + grid[i+1][j] + grid[i][j-1] + grid[i][j+1]); #pragma omp parallel for for (int i=1; i<N-1; i++ ) for (int j=1; j<N-1; j++ ) grid[i][j] = temp[i][j]; }


Слайд 31

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


Слайд 32


Слайд 33


Слайд 34


Слайд 35


Слайд 36


Слайд 37

Intel Vtune Amplifier XE 2013


Слайд 38

Intel Vtune Amplifier XE 2013


Слайд 39

Intel Vtune Amplifier XE 2013


Слайд 40

Intel Vtune Amplifier XE 2013


Слайд 41

Intel Vtune Amplifier XE 2013


Слайд 42

Спасибо за внимание! Вопросы?


Слайд 43

Бахтин В.А., кандидат физ.-мат. наук, заведующий сектором, Институт прикладной математики им. М.В.Келдыша РАН bakhtin@keldysh.ru Контакты


×

HTML:





Ссылка: