лекции (OpenMP), страница 4

Принципы и парадигмы. /Э. Таненбаум, М. ван Стеен. – СПб. Питер, 2003 Операционные системы распределенныхвычислительных систем (распределенные ОС).Крюков Виктор Алексеевич.http://parallel.ru/krukov/index.htmlМосква, 2015 г.Параллельное программирование с OpenMP: OpenMP - модельпараллелизма по управлению © Бахтин В.А.34 из 36Вопросы?Вопросы?Москва, 2015 г.Параллельное программирование с OpenMP: OpenMP - модельпараллелизма по управлению © Бахтин В.А.35 из 36КонтактыБахтин В.А., кандидат физ.-мат. наук, заведующийсектором, Институт прикладной математики им.М.В.Келдыша РАНbakhtin@keldysh.ruМосква, 2015 г.Параллельное программирование с OpenMP: OpenMP - модельпараллелизма по управлению © Бахтин В.А.36 из 36Интернет УниверситетСуперкомпьютерных технологийОсновные понятияУчебный курсПараллельное программирование сOpenMPБахтин В.А., кандидат физ.-мат.

наук,заведующий сектором,Институт прикладной математики им.М.В.Келдыша РАНСодержаниеДирективы и клаузы Понятие структурного блока Компиляция OpenMP-программы Параллельная область (директиваPARALLEL) Понятие задачи (директива TASK)Москва, 2015 г.Параллельное программирование с OpenMP: Основные понятия© Бахтин В.А.2 из 42Директивы и клаузыСпецификации параллелизма в OpenMP представляют собой директивывида: #pragma omp название-директивы[ клауза[ [,]клауза]...]Например: #pragma omp parallel default (none) private (i,j)Исполняемые директивы: barrier taskwait taskyield flushОписательная директива: threadprivateМосква, 2015 г.Параллельное программирование с OpenMP: Основные понятия© Бахтин В.А.3 из 42Структурный блокДействие остальных директив распространяется на структурный блок:#pragma omp название-директивы[ клауза[ [,]клауза]...]{структурный блок}Структурный блок: блок кода с одной точкой входа и одной точкойвыхода.#pragma omp parallel{…mainloop: res[id] = f (id);if (res[id] != 0) goto mainloop;if (id == 0) exit (0);…}Структурный блокМосква, 2015 г.#pragma omp parallel{…mainloop: res[id] = f (id);…}if (res[id] != 0) goto mainloop;Не структурный блокПараллельное программирование с OpenMP: Основные понятия© Бахтин В.А.4 из 42Составные директивы#pragma omp parallel private(i){#pragma omp for firstprivate(n)for (i = 1; i <= n; i ++){A[i]=A[i]+ B[i];}}Москва, 2015 г.#pragma omp parallel for private(i) \firstprivate(n)for (i = 1; i <= n; i ++){A[i]=A[i]+ B[i];}Параллельное программирование с OpenMP: Основные понятия© Бахтин В.А.5 из 42Компиляция OpenMP-программыПроизводительКомпиляторОпция компиляцииGNUgcc-fopenmpIBMXL C/C++ / Fortran-qsmp=ompSun MicrosystemsC/C++ / Fortran-xopenmpIntelC/C++ / Fortran-openmp | -qopenmp/QopenmpPortland GroupC/C++ / Fortran-mpMicrosoftVisual Studio C++/openmpМосква, 2015 г.Параллельное программирование с OpenMP: Основные понятия© Бахтин В.А.6 из 42Условная компиляция OpenMP-программы#include <stdio.h>int main(){#ifdef _OPENMPprintf("Compiled by an OpenMP-compliant implementation.\n");#endifreturn 0;}В значении переменной _OPENMP зашифрован год и месяц (yyyymm)версии стандарта OpenMP, которую поддерживает компилятор.Москва, 2015 г.Параллельное программирование с OpenMP: Основные понятия© Бахтин В.А.7 из 42Использование функций поддержи выполнения OpenMPпрограмм (OpenMP API runtime library)#include <stdio.h>#include <omp.h> // Описаны прототипы всех функций и типов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;}Москва, 2015 г.Параллельное программирование с OpenMP: Основные понятия© Бахтин В.А.8 из 42Использование функций поддержи выполненияOpenMP-программ (OpenMP API runtime library)#include <stdio.h>int omp_get_num_threads(void){return 1;В стандарте OpenMP описаны «заглушки»}для всех функций библиотеки поддержкиint omp_get_thread_num(void)– требуются при компиляции даннойпрограммы компилятором без поддержки{OpenMP.return 0;}Опция для компилятора Intel:int main()-qopenmp-stubs{#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;}Москва, 2015 г.Параллельное программирование с OpenMP: Основные понятия© Бахтин В.А.9 из 42Параллельная область (директива 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) proc_bind ( master | close | spread )//OpenMP 4.0Москва, 2015 г.Параллельное программирование с OpenMP: Основные понятия© Бахтин В.А.10 из 42Вычисление числа 14.04.0(1+x2)dx = 0Мы можемаппроксимировать интегралкак сумму прямоугольников:2.0N F(x )x  ii=00.0Москва, 2015 г.1.0XГде каждый прямоугольникимеет ширину x и высотуF(xi) в середине интервалаПараллельное программирование с OpenMP: Основные понятия© Бахтин В.А.11 из 42Вычисление числа .

Последовательнаяпрограмма.#include <stdio.h>int main (){int n =100000, i;double pi, h, sum, x;h = 1.0 / (double) n;sum = 0.0;for (i = 1; i <= n; i ++){x = h * ((double)i - 0.5);sum += (4.0 / (1.0 + x*x));}pi = h * sum;printf("pi is approximately %.16f”, pi);return 0;}Москва, 2015 г.Параллельное программирование с OpenMP: Основные понятия© Бахтин В.А.12 из 42Вычисление числа  на OpenMP сиспользовнием критической секции#include <stdio.h>#include <omp.h>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 <= n; i=i+numt){x = h * ((double)i - 0.5);#pragma omp criticalsum += (4.0 / (1.0 + x*x));}}pi = h * sum;printf("pi is approximately %.16f”, pi);return 0;}Москва, 2015 г.Параллельное программирование с OpenMP: Основные понятия© Бахтин В.А.13 из 42Конфликт доступа к даннымПри взаимодействии через общую память нити должны синхронизоватьсвое выполнение.#pragma omp parallel{sum = sum + val;}ВремяThread 0Thread 11LOAD R1,sum2LOAD R2,val3ADD R1,R2LOAD R3,sum4LOAD R4,val5ADD R3,R46STORE R3,sum7STORE R1,sumРезультат зависит от порядка выполнения команд.

Требуется взаимноеисключение критических интервалов.Москва, 2015 г.Параллельное программирование с OpenMP: Основные понятия© Бахтин В.А.14 из 42Вычисление числа  на OpenMP сиспользовнием критической секции#include <omp.h>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();double local_sum = 0.0;for (i = id + 1; i <= n; i=i+numt){x = h * ((double)i - 0.5);local_sum += (4.0 / (1.0 + x*x));}#pragma omp criticalsum += local_sum;}pi = h * sum;printf("pi is approximately %.16f”, pi);return 0;}Параллельное программирование с OpenMP: Основные понятияМосква, 2015 г.© Бахтин В.А.15 из 42Вычисление числа .

Клауза reduction#include <stdio.h>#include <omp.h>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 <= n; i=i+numt){x = h * ((double)i - 0.5);sum += (4.0 / (1.0 + x*x));}}pi = h * sum;printf("pi is approximately %.16f”, pi);return 0;}Москва, 2015 г.Параллельное программирование с OpenMP: Основные понятия© Бахтин В.А.16 из 42Клауза reductionreduction(operator:list) Внутри паралельной областидля каждой переменной изсписка list создается копия этойпеременной. Эта переменнаяинициализируется всоответствии с операторомoperator (например, 0 для «+»).Для каждой нити компиляторзаменяет в параллельнойобласти обращения кредукционной переменной наобращения к созданной копии.По завершении выполненияпараллельной областиосуществляется объединениеполученных результатов.Москва, 2015 г.ОператорНачальное значение+0*1-0&~0|0^0&&1||0Least number inreduction list item typeLargest number inreduction list item typemax // OpenMP 3.1min // OpenMP 3.1Параллельное программирование с OpenMP: Основные понятия© Бахтин В.А.17 из 42Использование редукционных операцийvoid reduction (float *x, int *y, int n){int i, b, c;float a, d;a = 0.0;b = 0;c = y[0];d = x[0];#pragma omp parallel for private(i) shared(x, y, n) \reduction(+:a) reduction(^:b) \reduction(min:c) reduction(max:d)for (i=0; i<n; i++) {a += x[i];b ^= y[i];if (c > y[i]) c = y[i];d = fmaxf(d,x[i]);}}Москва, 2015 г.Параллельное программирование с OpenMP: Основные понятия© Бахтин В.А.18 из 42Реализация редукционных операций#include <limits.h>void reduction_by_hand (float *x, int *y, int n){int i, b, b_p, c, c_p;float a, a_p, d, d_p;a = 0.0f;b = 0;c = y[0];d = x[0];#pragma omp parallel shared(a, b, c, d, x, y, n) private(a_p, b_p, c_p, d_p){a_p = 0.0f; b_p = 0; c_p = INT_MAX; d_p = -HUGE_VALF;#pragma omp for private(i)for (i=0; i<n; i++) {a_p += x[i]; b_p ^= y[i]; if (c_p > y[i]) c_p = y[i]; d_p = fmaxf(d_p,x[i]);}#pragma omp critical{a += a_p; b ^= b_p; if( c > c_p ) c = c_p; d = fmaxf(d,d_p);}}Параллельное программирование с OpenMP: Основные понятия}Москва, 2015 г.© Бахтин В.А.19 из 42Редукционные операции, определяемыепользователем (OpenMP 4.0)#pragma omp declare reduction (reduction-identifier : typename-list :combiner) [initializer (dentity-expr)]reduction-identifier - название редукционной операцииtypename-list – тип (типы)combiner – выражение для объединения частичных результатовinitializer – начальное значение создаваемых приватных переменныхМосква, 2015 г.Параллельное программирование с OpenMP: Основные понятия© Бахтин В.А.20 из 42Использование редукционных операций,определяемых пользователем (OpenMP 4.0)struct point{int x;int y;} points[N], minp = { MAX_INT, MAX_INT };#pragma omp declare reduction (min : struct point : \omp_out.x = omp_in.x > omp_out.x ? omp_out.x : omp_in.x, \omp_out.y = omp_in.y > omp_out.y ? omp_out.y : omp_in.y ) \initializer ( omp_priv = { MAX_INT, MAX_INT })#pragma omp parallel for reduction (min: minp)for (int i = 0; i < N; i++){if (points[i].x < minp.x) minp.x = points[i].x;if (points[i].y < minp.y) minp.y = points[i].y;}Москва, 2015 г.Параллельное программирование с OpenMP: Основные понятия© Бахтин В.А.21 из 42Клауза ifif(scalar-expression)В зависимости от значения scalar-expression для выполненияструктурного блока будет создана группа нитей или он будетвыполняться одной нитью.#include <omp.h>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();int numt = omp_get_num_threads();for (int i = id + 1; i <= n; i=i+numt)func (i);}return 0;}Параллельное программирование с OpenMP: Основные понятияМосква, 2015 г.© Бахтин В.А.22 из 42Клауза num_threadsnum_threads(integer-expression)integer-expression задает максимально возможное число нитей, которыебудут созданы для выполнения структурного блока#include <omp.h>int main(){int n = 0;printf("Enter the number of intervals: (0 quits) ");scanf("%d",&n);#pragma omp parallel num_threads(10){int id = omp_get_thread_num ();func (n, id);}return 0;}Москва, 2015 г.Параллельное программирование с OpenMP: Основные понятия© Бахтин В.А.23 из 42Определение числа нитей в параллельной областиЧисло создаваемых нитей зависит от: клаузы 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())Москва, 2015 г.Параллельное программирование с OpenMP: Основные понятия© Бахтин В.А.24 из 42Определение числа нитей в параллельной областиПусть ThreadsBusy - количество OpenMP нитей, выполняемых вданный момент;Пусть ActiveParRegions - количество активных параллельныхобластей;if в директиве parallel существует клауза ifthen присвоить переменной IfClauseValue значение выражения вклаузе if;else IfClauseValue = true;if в директиве parallel существует клауза num_threadsthen присвоить переменной ThreadsRequested значение выражения вклаузе num_threads;else ThreadsRequested = nthreads-var;ThreadsAvailable = (thread-limit-var - ThreadsBusy + 1);Москва, 2015 г.Параллельное программирование с OpenMP: Основные понятия© Бахтин В.А.25 из 42Определение числа нитей в параллельной области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 : ThreadsRequested ];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 = ThreadsRequested;else if (dyn-var == false) and (ThreadsRequested > ThreadsAvailable)then number of threads зависит от реализации компилятора;Москва, 2015 г.Параллельное программирование с OpenMP: Основные понятия© Бахтин В.А.26 из 42Определение числа нитей в параллельной области#include <stdio.h>#include <omp.h>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{…}}}Москва, 2015 г.Параллельное программирование с OpenMP: Основные понятия© Бахтин В.А.27 из 42Клауза copyincopyin(list)Значение каждой threadprivate-переменной из списка list,устанавливается равным значению этой переменной в master-нитиfloat* work;int size;float val;#pragma omp threadprivate(work,size,val)void compute(){work = (float*)malloc( sizeof(float)*size);for(int i = 0; i < size; ++i ) work[i] = val;… // computation of work array elements}int main(){printf("Enter the size of array and value\n");scanf("%d",&size);scanf(“%f",&val);#pragma omp parallel copyin(val,size)compute();}Москва, 2015 г.Параллельное программирование с OpenMP: Основные понятия© Бахтин В.А.28 из 42Клауза proc_bind (OpenMP 4.0)#pragma omp parallel proc_bind(spread) num_threads(4){#pragma omp parallel proc_bind(close) num_threads(2)work();}Москва, 2015 г.Параллельное программирование с OpenMP: Основные понятия© Бахтин В.А.29 из 42Понятие задачиЗадачи появились в OpenMP 3.0Каждая задача: Представляет собой последовательность операторов, которыенеобходимо выполнить. Включает в себя данные, которые используются при выполнении этихоператоров. Выполняется некоторой нитью.В OpenMP 3.0 каждый оператор программы является частью одной иззадач. При входе в параллельную область создаются неявные задачи (implicittask), по одной задаче для каждой нити. Создается группа нитей. Каждая нить из группы выполняет одну из задач. По завершении выполнения параллельной области, master-нитьожидает, пока не будут завершены все неявные задачи.Москва, 2015 г.Параллельное программирование с OpenMP: Основные понятия© Бахтин В.А.30 из 42Понятие задачи.