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

Москва, 2012 г. 2 из 36 Содержание Директивы и клаузы Понятие структурного блока Компиляция OpenMP-программы Параллельная область (директива PARALLEL) Понятие задачи (директива TASK) Параллельное программирование с OpenMP: Основные понятия © Бахтин В.А.

Директивы и клаузы Спецификации параллелизма в OpenMP представляют собой директивы вида: #pragma omp название-директивы[ клауза[ [,]клауза]...] Например: #pragma omp parallel default (none) shared (i,j) Исполняемые директивы: barrier taskwait taskyield flush Описательная директива: threadprivate Параллельное программирование с OpenMP: Основные понятия © Бахтин В.А. 3 из 36 Москва, 2012 г.

Структурный блок Действие остальных директив распространяется на структурный блок: #pragma omp название-директивы[ клауза[ [,]клауза]...] { структурный блок } Структурный блок: блок кода с одной точкой входа и одной точкой выхода. #pragma omp parallel { … mainloop: res[id] = f (id); if (res[id] != 0) goto mainloop; if (id == 0) exit (0); … } Структурный блок #pragma omp parallel { … mainloop: res[id] = f (id); … } if (res[id] != 0) goto mainloop; Не структурный блок Параллельное программирование с OpenMP: Основные понятия © Бахтин В.А. 4 из 36 Москва, 2012 г.

Составные директивы Параллельное программирование с OpenMP: Основные понятия © Бахтин В.А. 5 из 36 Москва, 2012 г. #pragma omp parallel private(i) { #pragma omp for firstprivate(n) for (i = 1; i

Компиляция OpenMP-программы ПроизводительКомпиляторОпция компиляции GNUgcc-fopenmp IBMXL 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: Основные понятия © Бахтин В.А. 6 из 36 Москва, 2012 г.

Условная компиляция OpenMP-программы #include int main() { #ifdef _OPENMP printf("Compiled by an OpenMP-compliant implementation.\n"); #endif return 0; } В значении переменной _OPENMP зашифрован год и месяц (yyyymm) версии стандарта OpenMP, которую поддерживает компилятор. Параллельное программирование с OpenMP: Основные понятия © Бахтин В.А. 7 из 36 Москва, 2012 г.

Использование функций поддержи выполнения OpenMP- программ (OpenMP API runtime library) #include #include // Описаны прототипы всех функций и типов int main() { #pragma omp parallel { int id = omp_get_thread_num (); int numt = omp_get_num_threads (); printf(Thread (%d) of (%d) threads alive\n, id, numt); } return 0; } Параллельное программирование с OpenMP: Основные понятия © Бахтин В.А. 8 из 36 Москва, 2012 г.

#include int omp_get_num_threads(void) { return 1; } int omp_get_thread_num(void) { return 0; } int main() { #pragma omp parallel { int id = omp_get_thread_num (); int numt = omp_get_num_threads (); printf(Thread (%d) of (%d) threads alive\n, id, numt); } return 0; } Использование функций поддержи выполнения OpenMP-программ (OpenMP API runtime library) В стандарте OpenMP описаны «заглушки» для всех функций библиотеки поддержки – требуются при компиляции данной программы компилятором без поддержки OpenMP. Параллельное программирование с OpenMP: Основные понятия © Бахтин В.А. 9 из 36 Москва, 2012 г.

Параллельная область (директива PARALLEL) #pragma omp parallel [ клауза[ [, ] клауза]...] структурный блок где клауза одна из : default(shared | none) private(list) firstprivate(list) shared(list) reduction(operator: list) if(scalar-expression) num_threads(integer-expression) copyin(list) Параллельное программирование с OpenMP: Основные понятия © Бахтин В.А. 10 из 36 Москва, 2012 г.

Вычисление числа 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 из 36 Параллельное программирование с OpenMP: Основные понятия © Бахтин В.А. Москва, 2012 г.

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

13 из 36 #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

14 из 36 Параллельное программирование с OpenMP: Основные понятия © Бахтин В.А. Москва, 2012 г. При взаимодействии через общую память нити должны синхронизовать свое выполнение. #pragma omp parallel { sum = sum + val; } Конфликт доступа к данным Результат зависит от порядка выполнения команд. Требуется взаимное исключение критических интервалов. ВремяThread 0 Thread 1 1LOAD R1,sum 2LOAD R2,val 3ADD R1,R2LOAD R1,sum 4LOAD R2,val 5ADD R1,R2 6STORE R1,sum 7

15 из 36 #include int main () { int n =100000, i; double pi, h, x; double *sum; h = 1.0 / (double) n; sum=(double *)malloc(omp_get_max_threads()*sizeof(double)); #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

16 из 36 #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

Клауза reduction Параллельное программирование с OpenMP: Основные понятия © Бахтин В.А. 17 из 36 Москва, 2012 г. 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

Клауза if if(scalar-expression) В зависимости от значения scalar-expression для выполнения структурного блока будет создана группа нитей или он будет выполняться одной нитью. #include int main() { int n = 0; printf("Enter the number of intervals: (0 quits) "); scanf("%d",&n); #pragma omp parallel if (n>10) { int id = omp_get_thread_num (); #pragma omp for for (int i=0; i

Клауза num_threads num_threads(integer-expression) integer-expression задает максимально возможное число нитей, которые будут созданы для выполнения структурного блока #include int main() { int n = 0; printf("Enter the number of intervals: (0 quits) "); scanf("%d",&n); omp_set_dynamic(1); #pragma omp parallel num_threads(10) { int id = omp_get_thread_num (); func (n, id); } return 0; } Параллельное программирование с OpenMP: Основные понятия © Бахтин В.А. 19 из 36 Москва, 2012 г.

Определение числа нитей в параллельной области Число создаваемых нитей зависит от: клаузы if клаузы num_threads значений переменных, управляющих выполнением OpenMP- программы: –dyn-var (включение/отключение режима, в котором количество создаваемых нитей может изменяться динамически: OMP_DYNAMIC, omp_set_dynamic()) –nthreads-var (максимально возможное число нитей, создаваемых при входе в параллельную область: OMP_NUM_THREADS, omp_set_num_threads()) –thread-limit-var (максимально возможное число нитей, создаваемых для выполнения всей OpenMP-программы: OMP_THREAD_LIMIT) –nest-var (включение/отключение режима поддержки вложенного параллелизма:OMP_NESTED, omp_set_nested()) –max-active-level-var (максимально возможное количество вложенных параллельных областей: OMP_MAX_ACTIVE_LEVELS, omp_set_max_active_levels()) Параллельное программирование с OpenMP: Основные понятия © Бахтин В.А. 20 из 36 Москва, 2012 г.

Определение числа нитей в параллельной области Пусть ThreadsBusy - количество OpenMP нитей, выполняемых в данный момент; Пусть ActiveParRegions - количество активных параллельных областей; if в директиве parallel существует клауза if then присвоить переменной IfClauseValue значение выражения в клаузе if; else IfClauseValue = true; if в директиве parallel существует клауза num_threads then присвоить переменной ThreadsRequested значение выражения в клаузе num_threads; else ThreadsRequested = nthreads-var; ThreadsAvailable = (thread-limit-var - ThreadsBusy + 1); Параллельное программирование с OpenMP: Основные понятия © Бахтин В.А. 21 из 36 Москва, 2012 г.

Определение числа нитей в параллельной области if (IfClauseValue == false) then number of threads = 1; else if (ActiveParRegions >= 1) and (nest-var == false) then number of threads = 1; else if (ActiveParRegions == max-active-levels-var) then number of threads = 1; else if (dyn-var == true) and (ThreadsRequested ThreadsAvailable) then number of threads = [ 1 : ThreadsAvailable ]; else if (dyn-var == false) and (ThreadsRequested ThreadsAvailable) then number of threads зависит от реализации компилятора; Параллельное программирование с OpenMP: Основные понятия © Бахтин В.А. 22 из 36 Москва, 2012 г.

Определение числа нитей в параллельной области #include int main (void) { omp_set_nested(1); omp_set_max_active_levels(8); omp_set_dynamic(0); omp_set_num_threads(2); #pragma omp parallel { omp_set_num_threads(3); #pragma omp parallel { … } Параллельное программирование с OpenMP: Основные понятия © Бахтин В.А. 23 из 36 Москва, 2012 г.

Клауза copyin copyin(list) Значение каждой threadprivate-переменной из списка list, устанавливается равным значению этой переменной в master-нити float* work; int size; float val; #pragma omp threadprivate(work,size,val) void compute() { int i; work = (float*)malloc( sizeof(float)*size); for( i = 0; i < size; ++i ) work[i] = val; … // computation of work array elements } int main() { read_from_file (); // read values of val and size variables from file #pragma omp parallel copyin(val,size) compute(); } Параллельное программирование с OpenMP: Основные понятия © Бахтин В.А. 24 из 36 Москва, 2012 г.

Понятие задачи Задачи появились в OpenMP 3.0 Каждая задача: Представляет собой последовательность операторов, которые необходимо выполнить. Включает в себя данные, которые используются при выполнении этих операторов. Выполняется некоторой нитью. В OpenMP 3.0 каждый оператор программы является частью одной из задач. При входе в параллельную область создаются неявные задачи (implicit task), по одной задаче для каждой нити. Создается группа нитей. Каждая нить из группы выполняет одну из задач. По завершении выполнения параллельной области, master-нить ожидает, пока не будут завершены все неявные задачи. Параллельное программирование с OpenMP: Основные понятия © Бахтин В.А. 25 из 36 Москва, 2012 г.

Понятие задачи. Директива task Явные задачи (explicit tasks) задаются при помощи директивы: #pragma omp task [клауза[[,] клауза]...] структурный блок где клауза одна из : if (scalar-expression) final (scalar-expression) //OpenMP 3.1 untied mergeable //OpenMP 3.1 shared (list) private (list) firstprivate (list) default ( shared | none ) В результате выполнения директивы task создается новая задача, которая состоит из операторов структурного блока; все используемые в операторах переменные могут быть локализованы внутри задачи при помощи соответствующих клауз. Созданная задача будет выполнена одной нитью из группы. Параллельное программирование с OpenMP: Основные понятия © Бахтин В.А. 26 из 36 Москва, 2012 г.

Использование директивы task. #pragma omp for for (i=0; i

Использование директивы task. typedef struct node node; struct node { int data; node * next; }; void increment_list_items(node * head) { #pragma omp parallel { #pragma omp single { node * p = head; while (p) { #pragma omp task process(p); p = p->next; } Параллельное программирование с OpenMP: Основные понятия © Бахтин В.А. 28 из 36 Москва, 2012 г.

Использование директивы task. Клауза if double *item; int main() { #pragma omp parallel shared (item) { #pragma omp single { int size; scanf("%d",&size); item = (double*)malloc(sizeof(double)*size); for (int i=0; i 10) process(item[i]); } Если накладные расходы на организацию задач превосходят время, необходимое для выполнения блока операторов этой задачи, то блок операторов будет немедленно выполнен нитью, выполнившей директиву task. Параллельное программирование с OpenMP: Основные понятия © Бахтин В.А. 29 из 36 Москва, 2012 г.

Использование директивы task. #define LARGE_NUMBER double item[LARGE_NUMBER]; extern void process(double); int main() { #pragma omp parallel shared (item) { #pragma omp single { for (int i=0; i

Использование директивы task. Клауза untied #define LARGE_NUMBER double item[LARGE_NUMBER]; extern void process(double); int main() { #pragma omp parallel { #pragma omp single { #pragma omp task untied { for (int i=0; i

Использование директивы task. Параллельное программирование с OpenMP: Основные понятия © Бахтин В.А. 32 из 36 Москва, 2012 г. int fibonacci(int n) { int i, j; if (n

Использование директивы task. final void fib (int n, int d) { int x, y; if (n < 2) return 1; #pragma omp task final (d > LIMIT) mergeable x = fib (n - 1, d + 1); #pragma omp task final (d > LIMIT) mergeable y = fib (n - 2, d + 1); #pragma omp taskwait return x + y; } int omp_in_final (void); Параллельное программирование с OpenMP: Основные понятия © Бахтин В.А. 33 из 36 Москва, 2012 г.

34 из 36 Вопросы? Параллельное программирование с OpenMP: Основные понятия © Бахтин В.А. Москва, 2012 г.

35 из 36 Конструкции распределения работы Следующая тема Параллельное программирование с OpenMP: Основные понятия © Бахтин В.А. Москва, 2012 г.

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