Технология параллельного программирования OpenMP Шальнов Евгений Вадимович Автор слайдов: Бахтин Владимир Александрович. - презентация

1 Технология параллельного программирования OpenMP Шальнов Евгений Вадимович Автор слайдов: Бахтин Владимир Александрович

2 Существующие подходы для создания параллельных программ Автоматическое / автоматизированное распараллеливание Библиотеки нитей Win32 API POSIX Библиотеки передачи сообщений MPI OpenMP

3 4.0 (1+x 2 ) dx = 0 1 F(x i ) x i = 0 N Мы можем аппроксимировать интеграл как сумму прямоугольников: Где каждый прямоугольник имеет ширину x и высоту F(x i ) в середине интервала F(x) = 4.0/(1+x 2 ) X 0.0 Вычисление числа

4 #include int main () { int n =100000, i; double pi, h, sum, x; h = 1.0 / (double) n; sum = 0.0; for (i = 1; i

5 #include "mpi.h" #include int main (int argc, char *argv[]) { int n =100000, myid, numprocs, i; double mypi, pi, h, sum, x; MPI_Init(&argc,&argv); MPI_Comm_size(MPI_COMM_WORLD,&numprocs); MPI_Comm_rank(MPI_COMM_WORLD,&myid); MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD); h = 1.0 / (double) n; sum = 0.0; Вычисление числа с использованием MPI

6 for (i = myid + 1; i

7 #include int main () { int n =100000, i; double pi, h, sum, x; h = 1.0 / (double) n; sum = 0.0; #pragma omp parallel for reduction(+:sum) private(x) for (i = 1; i

8 Тенденции развития современных процессоров OpenMP – модель параллелизма по управлению Конструкции распределения работы Конструкции для синхронизации нитей Система поддержки выполнения OpenMP-программ OpenMP 4.0 Содержание

9 Все процессоры имеют доступ к любой точке памяти с одинаковой скоростью. Процессоры подключены к памяти либо с помощью общей шины, либо с помощью crossbar-коммутатора. Аппаратно поддерживается когерентность кэшей. Cимметричные мультипроцессорные системы (SMP)

10 Спецификации параллелизма в OpenMP представляют собой директивы вида: #pragma omp название-директивы[ клауза[ [,]клауза]...] Например: #pragma omp parallel default (none) shared (i,j) Исполняемые директивы: barrier taskwait flush Описательная директива: threadprivate Директивы и клаузы

11 Действие остальных директив распространяется на структурный блок: #pragma omp название-директивы[ клауза[ [,]клауза]...] { структурный блок } Структурный блок: блок кода с одной точкой входа и одной точкой выхода. #pragma omp parallel { … mainloop: res[id] = f (id); if (res[id] != 0) goto mainloop; … exit (0); } Структурный блок #pragma omp parallel { … mainloop: res[id] = f (id); … } if (res[id] != 0) goto mainloop; Не структурный блок Структурный блок

12 OpenMP 3.1: Intel 12.0: Linux, Windows and MacOS Oracle Solaris Studio12.3: Linux and Solaris GNU gcc (4.7.0) OpenMP 3.0: PGI 8.0: Linux and Windows IBM 10.1: Linux and AIX Cray: Cray XT series Linux environment Absoft Pro FortranMP: 11.1 NAG Fortran Complier 5.3 Предыдущие версии OpenMP: Lahey/Fujitsu Fortran 95 PathScale HP Microsoft Visual Studio 2008 C++ Компиляторы, поддеживающие OpenMP

13 ПроизводительКомпиляторОпция компиляции GNUgcc-fopenmp IBM XL C/C++ / Fortran -qsmp=omp Sun MicrosystemsC/C++ / Fortran-xopenmp IntelC/C++ / Fortran -openmp /Qopenmp Portland GroupC/C++ / Fortran-mp MicrosoftVisual Studio 2008 C++/openmp Компиляция OpenMP-программы

14 #include #include // Описаны прототипы всех функций и типов int main() { #ifdef _OPENMP printf("Compiled by an OpenMP-compliant implementation.\n"); int id = omp_get_max_threads (); #endif return 0; } В значении переменной _OPENMP зашифрован год и месяц (yyyymm) версии стандарта OpenMP, которую поддерживает компилятор. Условная компиляция OpenMP-программы

15 Fork-Join параллелизм: Главная (master) нить порождает группу (team) нитей по мере небходимости. Параллелизм добавляется инкрементально. Параллельные области Выполнение OpenMP-программы

16 Модель памяти в OpenMP 001 Нить 001 Нить 001 Нить

17 Модель памяти в OpenMP 001 Нить Нить 1 static int i = 0; … = i + 1; i = i + 1; i = 0 i = 1 … = i + 2; // ? #pragma omp flush (i) i = 1

18 Корректная последовательность работы нитей с переменной: Нить0 записывает значение переменной – write (var) Нить0 выполняет операцию синхронизации – flush (var) Нить1 выполняет операцию синхронизации – flush (var) Нить1 читает значение переменной – read (var) 1: A = : flush(A) Консистентность памяти в OpenMP

19 В модели программирования с разделяемой памятью: Большинство переменных по умолчанию считаются shared Глобальные переменные совместно используются всеми нитями (shared) : Фортран: COMMON блоки, SAVE переменные, MODULE переменные Си: file scope, static Динамически выделяемая память (ALLOCATE, malloc, new) Но не все переменные являются разделяемыми... Стековые переменные в подпрограммах (функциях), вызываемых из параллельного региона, являются private. Переменные объявленные внутри блока операторов параллельного региона являются приватными. Счетчики циклов витки которых распределяются между нитями при помощи конструкций for и parallel for. Классы переменных

20 double Array1[100]; int main() { int Array2[100]; #pragma omp parallel work(Array2); printf(%d\n, Array2[0]); } extern double Array1[100]; void work(int *Array) { double TempArray[10]; static int count;... } TempArray Array1, Array2, count Классы переменных Пока о

21 Можно изменить класс переменной при помощи конструкций: shared (список переменных) private (список переменных) firstprivate (список переменных) lastprivate (список переменных) threadprivate (список переменных) default (private | shared | none) Классы переменных

22 Конструкция «private(var)» создает локальную копию переменной «var» в каждой из нитей. Значение переменной не инициализировано Приватная копия не связана с оригинальной переменной В OpenMP 2.5 значение переменной «var» не определено после завершения параллельной конструкции sum = -1.0; #pragma omp parallel for private (i,j,sum) for (i=0; i< m; i++) { sum = 0.0; for (j=0; j< n; j++) sum +=b[i][j]*c[j]; a[i] = sum; } sum == -1.0 Конструкция private

23 «firstprivate» является специальным случаем «private» Инициализирует каждую приватную копию соответствующим значением из главной (master) нити. BOOL FirstTime=TRUE; #pragma omp parallel for firstprivate(FirstTime) for (row=0; row

24 lastprivate передает значение приватной переменной, посчитанной на последней итерации в глобальную переменную. int i; #pragma omp parallel { #pragma omp for lastprivate(i) for (i=0; i

25 Отличается от применения конструкции private: private скрывает глобальные переменные threadprivate – переменные сохраняют глобальную область видимости внутри каждой нити #pragma omp threadprivate (Var) Var = 1 Var = 2 … = Var Если количество нитей не изменилось, то каждая нить получит значение, посчитанное в предыдущей параллельной области. Директива threadprivate

26 itotal = 100 #pragma omp parallel private(np,each) { np = omp_get_num_threads() each = itotal/np ……… } itotal = 100 #pragma omp parallel default(none) private(np,each) shared (itotal) { np = omp_get_num_threads() each = itotal/np ……… } Меняет класс переменной по умолчанию: default (shared) – действует по умолчанию default (private) – есть только в Fortran default (firstprivate) – есть только в Fortran OpenMP 3.1 default (none) – требует определить класс для каждой переменной Конструкция default

27 #pragma omp parallel [ клауза[ [, ] клауза]...] структурный блок где клауза одна из : default(shared | none) private(list) firstprivate(list) shared(list) reduction(operator: list) if(scalar-expression) num_threads(integer-expression) copyin(list) Параллельная область (директива parallel)

28 4.0 (1+x 2 ) dx = 0 1 F(x i ) x i = 0 N Мы можем аппроксимировать интеграл как сумму прямоугольников: Где каждый прямоугольник имеет ширину x и высоту F(x i ) в середине интервала F(x) = 4.0/(1+x 2 ) X 0.0 Вычисление числа

29 #include int main () { int n =100000, i; double pi, h, sum, x; h = 1.0 / (double) n; sum = 0.0; for (i = 1; i

30 #include int main () { int n =100000, i; double pi, h, sum, x; h = 1.0 / (double) n; sum = 0.0; #pragma omp parallel default (none) private (i,x) shared (n,h,sum) { int id = omp_get_thread_num(); int numt = omp_get_num_threads(); for (i = id + 1; i

31 #include int main () { int n =100000, i; double pi, h, x; double *sum; sum=(double *)malloc(omp_get_max_threads()*sizeof(double)); h = 1.0 / (double) n; #pragma omp parallel default (none) private (i,x) shared (n,h,sum) { int id = omp_get_thread_num(); int numt = omp_get_num_threads(); for (i = id + 1, sum[id] = 0.0; i

32 #include int main () { int n =100000, i; double pi, h, sum, x; h = 1.0 / (double) n; sum = 0.0; #pragma omp parallel default (none) private (i,x) shared (n,h) reduction(+:sum) { int id = omp_get_thread_num(); int numt = omp_get_num_threads(); for (i = id + 1; i

33 reduction(operator:list) Внутри паралельной области для каждой переменной из списка list создается копия этой переменной. Эта переменная инициализируется в соответствии с оператором operator (например, 0 для «+»). Для каждой нити компилятор заменяет в параллельной области обращения к редукционной переменной на обращения к созданной копии. По завершении выполнения параллельной области осуществляется объединение полученных результатов. ОператорНачальное значение +0 *1 -0 &~0 |0 ^0 &&1 ||0 max Least number in reduction list item type min Largest number in reduction list item type Клауза reduction

34 Тенденции развития современных процессоров OpenMP – модель параллелизма по управлению Конструкции распределения работы Конструкции для синхронизации нитей Система поддержки выполнения OpenMP-программ OpenMP 4.0 Содержание

35 Распределение витков циклов (директива for) Циклы с зависимостью по данным. Организация конвейерного выполнения для циклов с зависимостью по данным. Распределение нескольких структурных блоков между нитями (директива SECTION). Выполнение структурного блока одной нитью (директива single) Распределение операторов одного структурного блока между нитями (директива WORKSHARE) Задачи (директива TASK) Конструкции распределения работы

36 4.0 (1+x 2 ) dx = 0 1 F(x i ) x i = 0 N Мы можем аппроксимировать интеграл как сумму прямоугольников: Где каждый прямоугольник имеет ширину x и высоту F(x i ) в середине интервала F(x) = 4.0/(1+x 2 ) X 0.0 Вычисление числа

37 Вычисление числа на OpenMP int main () { int n =100000, i; double pi, h, sum, x; h = 1.0 / (double) n; sum = 0.0; #pragma omp parallel default (none) private (i,x) shared (n,h) reduction(+:sum) { int iam = omp_get_thread_num(); int numt = omp_get_num_threads(); int start = iam * n / numt + 1; int end = (iam + 1) * n / numt; if (iam == numt-1) end = n; for (i = start; i

38 #include int main () { int n =100, i; double pi, h, sum, x; h = 1.0 / (double) n; sum = 0.0; #pragma omp parallel default (none) private (i,x) shared (n,h) reduction(+:sum) { #pragma omp for schedule (static) for (i = 1; i

39 #pragma omp for [клауза[[,]клауза]... ] for (init-expr; test-expr; incr-expr) структурный блок где клауза одна из : private(list) firstprivate(list) lastprivate(list) reduction(operator: list) schedule(kind[, chunk_size]) collapse(n) ordered nowait Распределение витков цикла

40 init-expr : var = loop-invariant-expr1 | integer-type var = loop-invariant-expr1 | random-access-iterator-type var = loop-invariant-expr1 | pointer-type var = loop-invariant-expr1 test-expr: var relational-op loop-invariant-expr2 | loop-invariant-expr2 relational-op var incr-expr: ++var | var++ | --var | var -- | var += loop-invariant-integer- expr | var -= loop-invariant-integer- expr | var = var + loop-invariant-integer- expr | var = loop-invariant-integer- expr + var | var = var - loop-invariant-integer- expr relational-op: < | | >= var: signed or unsigned integer type | random access iterator type | pointer type Распределение витков цикла

41 #include void iterator_example() { std::vector vec(23); std::vector ::iterator it; #pragma omp parallel for default(none) shared(vec) for (it = vec.begin(); it < vec.end(); it++) { // do work with *it // } Parallel Random Access Iterator Loop (OpenMP 3.0)

42 void pointer_example () { char a[N]; #pragma omp for default (none) shared (a,N) for (char *p = a; p < (a+N); p++ ) { use_char (p); } for (char *p = a; p != (a+N); p++ ) - ошибка Использование указателей в цикле (OpenMP 3.0)

43 void work(int i, int j) {} void good_collapsing(int n) { int i, j; #pragma omp parallel default(shared) { #pragma omp for collapse (2) for (i=0; i

44 void work(int i, int j) {} void error_collapsing(int n) { int i, j; #pragma omp parallel default(shared) { #pragma omp for collapse (2) for (i=0; i

45 void work(int i, int j) {} void error_collapsing(int n) { int i, j; #pragma omp parallel default(shared) { #pragma omp for collapse (2) for (i=0; i

46 Распределение витков цикла. Клауза nowait void example(int n, float *a, float *b, float *z) { int i; float sum = 0.0; #pragma omp parallel { #pragma omp for schedule(static) nowait reduction (+: sum) for (i=0; i

47 Тенденции развития современных процессоров OpenMP – модель параллелизма по управлению Конструкции распределения работы Конструкции для синхронизации нитей Система поддержки выполнения OpenMP-программ OpenMP 4.0 Содержание

48 Директива master Директива critical Директива atomic Семафоры Директива barrier Конструкции для синхронизации нитей

49 #pragma omp master структурный блок /*Структурный блок будет выполнен MASTER-нитью группы. По завершении выполнения структурного блока барьерная синхронизация нитей не выполняется*/ #include void init(float *a, float *b ) { #pragma omp master scanf("%f %f", a, b); #pragma omp barrier } int main () { float x,y; #pragma omp parallel { init (&x,&y); parallel_work (x,y); } Директива master

50 #include int main () { int n =100000, i; double pi, h, sum, x; h = 1.0 / (double) n; sum = 0.0; #pragma omp parallel default (none) private (i,x) shared (n,h,sum) { double local_sum = 0.0; #pragma omp for for (i = 1; i

51 Тенденции развития современных процессоров OpenMP – модель параллелизма по управлению Конструкции распределения работы Конструкции для синхронизации нитей Система поддержки выполнения OpenMP-программ Содержание

52 Определяет максимально возможное количество нитей в создаваемой параллельной области. Начальное значение: зависит от реализации. Существует одна копия этой переменной для каждой задачи. Значение переменной можно изменить: C shell: setenv OMP_NUM_THREADS 4,3,2 Korn shell: export OMP_NUM_THREADS=16 Windows: set OMP_NUM_THREADS=16 void omp_set_num_threads(int num_threads); Узнать значение переменной можно: int omp_get_max_threads(void); Internal Control Variables. nthreads-var

53 Определяет максимальное количество нитей, которые могут быть использованы для выполнения всей программы. Начальное значение: зависит от реализации. Существует одна копия этой переменной для всей программы. Значение переменной можно изменить: C shell: setenv OMP_THREAD_LIMIT 16 Korn shell: export OMP_THREAD_LIMIT=16 Windows: set OMP_THREAD_LIMIT=16 Узнать значение переменной можно: int omp_get_thread_limit(void) Internal Control Variables. thread-limit-var

54 Включает/отключает режим, в котором количество создаваемых нитей при входе в параллельную область может меняться динамически. Начальное значение: Если компилятор не поддерживает данный режим, то false. Существует одна копия этой переменной для каждой задачи. Значение переменной можно изменить: C shell: setenv OMP_DYNAMIC true Korn shell: export OMP_DYNAMIC=true Windows: set OMP_DYNAMIC=true void omp_set_dynamic(int dynamic_threads); Узнать значение переменной можно: int omp_get_dynamic(void); Internal Control Variables. dyn-var

55 Включает/отключает режим поддержки вложенного параллелизма. Начальное значение: false. Существует одна копия этой переменной для каждой задачи. Значение переменной можно изменить: C shell: setenv OMP_NESTED true Korn shell: export OMP_NESTED=false Windows: set OMP_NESTED=true void omp_set_nested(int nested); Узнать значение переменной можно: int omp_get_nested(void); Internal Control Variables. nest-var

56 Задает максимально возможное количество активных вложенных параллельных областей. Начальное значение: зависит от реализации. Существует одна копия этой переменной для всей программы. Значение переменной можно изменить: C shell: setenv OMP_MAX_ACTIVE_LEVELS 2 Korn shell: export OMP_MAX_ACTIVE_LEVELS=3 Windows: set OMP_MAX_ACTIVE_LEVELS=4 void omp_set_max_active_levels (int max_levels); Узнать значение переменной можно: int omp_get_max_active_levels(void); Internal Control Variables. max-active-levels-var

57 Задает способ распределения витков цикла между нитями, если указана клауза schedule(runtime). Начальное значение: зависит от реализации. Существует одна копия этой переменной для каждой задачи. Значение переменной можно изменить: C shell: setenv OMP_SCHEDULE "guided,4" Korn shell: export OMP_SCHEDULE "dynamic,5" Windows: set OMP_SCHEDULE=static void omp_set_schedule(omp_sched_t kind, int modifier); Узнать значение переменной можно: void omp_get_schedule(omp_sched_t * kind, int * modifier ); typedef enum omp_sched_t { omp_sched_static = 1, omp_sched_dynamic = 2, omp_sched_guided = 3, omp_sched_auto = 4 } omp_sched_t; Internal Control Variables. run-sched-var

58 Задает способ распределения витков цикла между нитями по умолчанию. Начальное значение: зависит от реализации. Существует одна копия этой переменной для всей программы. void work(int i); int main () { #pragma omp parallel { #pragma omp for for (int i=0;i

59 Каждая нить представляет собой независимо выполняющийся поток управления со своим счетчиком команд, регистровым контекстом и стеком. Переменная stack-size-var задает размер стека. Начальное значение: зависит от реализации. Существует одна копия этой переменной для всей программы. Значение переменной можно изменить: setenv OMP_STACKSIZE B setenv OMP_STACKSIZE "3000 k" setenv OMP_STACKSIZE 10M setenv OMP_STACKSIZE "10 M" setenv OMP_STACKSIZE "20 m" setenv OMP_STACKSIZE "1G" setenv OMP_STACKSIZE Internal Control Variables. stack-size-var

60 int main () { int a[1024][1024]; #pragma omp parallel private (a) { for (int i=0;i

61 Подсказка OpenMP-компилятору о желаемом поведении нитей во время ожидания. Начальное значение: зависит от реализации. Существует одна копия этой переменной для всей программы. Значение переменной можно изменить: setenv OMP_WAIT_POLICY ACTIVE setenv OMP_WAIT_POLICY active setenv OMP_WAIT_POLICY PASSIVE setenv OMP_WAIT_POLICY passive IBM AIX SPINLOOPTIME= YIELDLOOPTIME=40000 Internal Control Variables. wait-policy-var

62 клаузавызов функциипеременная окруженияICV omp_set_dynamic()OMP_DYNAMICdyn-var omp_set_nested()OMP_NESTEDnest-var num_threadsomp_set_num_threads()OMP_NUM_THREADSnthreads-var scheduleomp_set_schedule()OMP_SCHEDULErun-sched-var scheduledef-sched-var OMP_STACKSIZEstacksize-var OMP_WAIT_POLICYwait-policy-var OMP_THREAD_LIMITthread-limit-var omp_set_max_active_ levels() OMP_MAX_ACTIVE_ LEVELS max-active-levels-var Internal Control Variables. Приоритеты

63 int omp_get_num_threads(void); -возвращает количество нитей в текущей параллельной области #include void work(int i); void test() { int np; np = omp_get_num_threads(); /* np == 1*/ #pragma omp parallel private (np) { np = omp_get_num_threads(); #pragma omp for schedule(static) for (int i=0; i < np; i++) work(i); } Система поддержки выполнения OpenMP-программ

64 int omp_get_thread_num(void); -возвращает номер нити в группе [0: omp_get_num_threads()-1] #include void work(int i); void test() { int iam; iam = omp_get_thread_num(); /* iam == 0*/ #pragma omp parallel private (iam) { iam = omp_get_thread_num(); work(iam); } Система поддержки выполнения OpenMP-программ

65 int omp_get_num_procs(void); -возвращает количество процессоров, на которых программа выполняется #include void work(int i); void test() { int nproc; nproc = omp_get_num_ procs(); #pragma omp parallel num_threads(nproc) { int iam = omp_get_thread_num(); work(iam); } Система поддержки выполнения OpenMP-программ

66 int omp_get_level(void) - возвращает уровень вложенности для текущей параллельной области. #include void work(int i) { #pragma omp parallel { int ilevel = omp_get_level (); } void test() { int ilevel = omp_get_level (); /*ilevel==0*/ #pragma omp parallel private (ilevel) { ilevel = omp_get_level (); int iam = omp_get_thread_num(); work(iam); } Система поддержки выполнения OpenMP-программ

67 int omp_get_active_level(void) - возвращает количество активных параллельных областей (выполняемых 2-мя или более нитями). #include void work(int iam, int size) { #pragma omp parallel { int ilevel = omp_get_active_level (); } void test() { int size = 0; int ilevel = omp_get_active_level (); /*ilevel==0*/ scanf("%d",&size); #pragma omp parallel if (size>10) { int iam = omp_get_thread_num(); work(iam, size); } Система поддержки выполнения OpenMP-программ 10) { int iam = omp_get_thread_num(); work(iam, size); } Система поддержки выполнения OpenMP-программ">

68 int omp_get_ancestor_thread_num (int level) - для нити, вызвавшей данную функцию, возвращается номер нити- родителя, которая создала указанную параллельную область. omp_get_ancestor_thread_num (0) = 0 If (level==omp_get_level()) { omp_get_ancestor_thread_num (level) == omp_get_thread_num (); } If ((level omp_get_level())) { omp_get_ancestor_thread_num (level) == -1; } Система поддержки выполнения OpenMP-программ

69 int omp_get_team_size(int level); - количество нитей в указанной параллельной области. omp_get_team_size (0) = 1 If (level==omp_get_level()) { omp_get_team_size (level) == omp_get_num _threads (); } If ((level omp_get_level())) { omp_get_team_size (level) == -1; } Система поддержки выполнения OpenMP-программ

70 double omp_get_wtime(void); возвращает для нити астрономическое время в секундах, прошедшее с некоторого момента в прошлом. Если некоторый участок окружить вызовами данной функции, то разность возвращаемых значений покажет время работы данного участка. Гарантируется, что момент времени, используемый в качестве точки отсчета, не будет изменен за время выполнения программы. double start; double end; start = omp_get_wtime(); /*... work to be timed...*/ end = omp_get_wtime(); printf("Work took %f seconds\n", end - start); double omp_get_wtick(void); - возвращает разрешение таймера в секундах (количество секунд между последовательными импульсами таймера). Система поддержки выполнения OpenMP-программ. Функции работы со временем

71 OpenMP Application Program Interface Version 3.1, July Антонов А.С. Параллельное программирование с использованием технологии OpenMP: Учебное пособие.-М.: Изд-во МГУ, Э. Таненбаум, М. ван Стеен. Распределенные системы. Принципы и парадигмы. – СПб. Питер, 2003 Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб.: БХВ-Петербург, Презентация ftp://ftp.keldysh.ru/K_student/MSU2012/Speckurs2012_OpenMP.ppt ftp://ftp.keldysh.ru/K_student/MSU2012/Speckurs2012_OpenMP.ppt Литература

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