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

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

14 сентября Москва, 2012Технология параллельного программирования OpenMP3 из 150 Тенденции развития современных процессоров В течение нескольких десятилетий развитие ЭВМ сопровождалось удвоением их быстродействия каждые года. Это обеспечивалось и повышением тактовой частоты и совершенствованием архитектуры (параллельное и конвейерное выполнение команд). Узким местом стала оперативная память. Знаменитый закон Мура, так хорошо работающий для процессоров, совершенно не применим для памяти, где скорости доступа удваиваются в лучшем случае каждые 5-6 лет. Совершенствовались системы кэш-памяти, увеличивался объем, усложнялись алгоритмы ее использования. Для процессора Intel Itanium: Latency to L1: 1-2 cycles Latency to L2: cycles Latency to L3: cycles Latency to memory: 180 – 225 cycles Важным параметром становится - GUPS (Giga Updates Per Second)

14 сентября Москва, 2012Технология параллельного программирования OpenMP4 из 150 Тенденции развития современных процессоров Время В П В П В П В П В П В П Поток Время В П В П В П Поток 1 В П В П В П В П В П В П ВП В П В П Поток 2 Поток 3 Поток 4 В - вычисления П - доступ к памяти Chip MultiThreading увеличили производительность процессора в 2 раза Поток или нить (по- английски thread) – это легковесный процесс, имеющий с другими потоками общие ресурсы, включая общую оперативную память.

14 сентября Москва, 2012Технология параллельного программирования OpenMP5 из 150 Тенденции развития современных процессоров Суперкомпьютер K computer, SPARC64 VIIIfx 2.0GHz, Tofu interconnect Пиковая производительность TFlop/s Число ядер в системе Производительность на Linpack TFlop/s (93.17 % от пиковой) Энергопотребление комплекса кВт Важным параметром становится – Power Efficency (Megaflops/watt) Как добиться максимальной производительности на Ватт => Chip MultiProcessing, многоядерность.

14 сентября Москва, 2012Технология параллельного программирования OpenMP6 из 150 Тенденции развития современных процессоров AMD Opteron серии SE 16 2,7 ГГц, 16 МБ L3 Cache ,0 ГГц, 16 МБ L3 Cache ,3 ГГц, 16 МБ L3 Cache встроенный контроллер памяти (4 канала памяти DDR3) 4 канала «точка-точка» с использованием HyperTransort 3.0

14 сентября Москва, 2012Технология параллельного программирования OpenMP7 из 150 Тенденции развития современных процессоров Intel Xeon серии E ,9 ГГц, 16 нитей, 20 МБ L3 Cache ,5 ГГц, 8 нитей, 10 МБ L3 Cache Intel® Turbo Boost Intel® Hyper-Threading Intel® QuickPath Intel® Intelligent Power

14 сентября Москва, 2012Технология параллельного программирования OpenMP8 из 150 Тенденции развития современных процессоров Intel Core i7-3960X Extreme Edition 3,3 ГГц (3,9 ГГц) 6 ядeр 12 потоков с технологией Intel Hyper-Threading 15 МБ кэш-памяти Intel Smart Cache встроенный контроллер памяти (4 канала памяти DDR3 1066/1333/1600 МГц ) технология Intel QuickPath Interconnect

14 сентября Москва, 2012Технология параллельного программирования OpenMP9 из 150 Тенденции развития современных процессоров Intel Itanium 9350 (Tukwila) 1,73 ГГц 4 ядeр 8 потоков с технологией Intel Hyper-Threading 24 МБ L3 кэш-памяти технология Intel QuickPath Interconnect технология Intel Turbo Boost

14 сентября Москва, 2012Технология параллельного программирования OpenMP10 из 150 Тенденции развития современных процессоров IBM Power7 3,5 - 4,0 ГГц 8 ядер x 4 нити Simultaneuos MultiThreading L1 64КБ L2 256 КБ L3 32 МБ встроенный контроллер памяти

14 сентября Москва, 2012Технология параллельного программирования OpenMP11 из 150 Тенденции развития современных процессоров Темпы уменьшения латентности памяти гораздо ниже темпов ускорения процессоров + прогресс в технологии изготовления кристаллов => CMT (Chip MultiThreading) Опережающий рост потребления энергии при росте тактовой частоты + прогресс в технологии изготовления кристаллов => CMP (Chip MultiProcessing, многоядерность) И то и другое требует более глубокого распараллеливания для эффективного использования аппаратуры

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

14 сентября Москва, 2012Технология параллельного программирования OpenMP13 из (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 Вычисление числа

14 сентября Москва, 2012Технология параллельного программирования OpenMP14 из 150 #include int main () { int n =100000, i; double pi, h, sum, x; h = 1.0 / (double) n; sum = 0.0; for (i = 1; i

14 сентября Москва, 2012Технология параллельного программирования OpenMP15 из 150 Polaris, CAPO, WPP, SUIF, VAST/Parallel, OSCAR, Intel/OpenMP, ParaWise icc -parallel pi.c pi.c(8): (col. 5) remark: LOOP WAS AUTO-PARALLELIZED. pi.c(8): (col. 5) remark: LOOP WAS VECTORIZED. В общем случае, автоматическое распараллеливание затруднено: косвенная индексация (A[B[i]]); указатели (ассоциация по памяти); сложный межпроцедурный анализ. Автоматическое распараллеливание

14 сентября Москва, 2012Технология параллельного программирования OpenMP16 из 150 Intel/GAP (Guided Auto-Parallel), CAPTools/ParaWise, BERT77, FORGE Magic/DM, ДВОР (Диалоговый Высокоуровневый Оптимизирующий Распараллеливатель), САПФОР (Система Автоматизации Параллелизации ФОРтран программ) for (i=0; i 0) {b=A[i]; A[i] = 1 / A[i]; } if (A[i] > 1) {A[i] += b;} } icc -guide -parallel test.cpp Автоматизированное распараллеливание

14 сентября Москва, 2012Технология параллельного программирования OpenMP17 из 150 test.cpp(49): remark #30521: (PAR) Loop at line 49 cannot be parallelized due to conditional assignment(s) into the following variable(s): b. This loop will be parallelized if the variable(s) become unconditionally initialized at the top of every iteration. [VERIFY] Make sure that the value(s) of the variable(s) read in any iteration of the loop must have been written earlier in the same iteration. test.cpp(49): remark #30525: (PAR) If the trip count of the loop at line 49 is greater than 188, then use "#pragma loop count min(188)" to parallelize this loop. [VERIFY] Make sure that the loop has a minimum of 188 iterations. #pragma loop count min (188) for (i=0; i 0) {A[i] = 1 / A[i];} if (A[i] > 1) {A[i] += b;} } Автоматизированное распараллеливание

14 сентября Москва, 2012Технология параллельного программирования OpenMP18 из 150 #include #define NUM_THREADS 2 CRITICAL_SECTION hCriticalSection; double pi = 0.0; int n =100000; void main () { int i, threadArg[NUM_THREADS]; DWORD threadID; HANDLE threadHandles[NUM_THREADS]; for(i=0; i

14 сентября Москва, 2012Технология параллельного программирования OpenMP19 из 150 void Pi (void *arg) { int i, start; double h, sum, x; h = 1.0 / (double) n; sum = 0.0; start = *(int *) arg; for (i=start; i

14 сентября Москва, 2012Технология параллельного программирования OpenMP20 из 150 При взаимодействии через общую память нити должны синхронизовать свое выполнение. Thread0: pi = pi + val; && Thread1: pi = pi + val; ВремяThread 0 Thread 1 1LOAD R1,pi 2LOAD R2,val 3ADD R1,R2LOAD R1,pi 4LOAD R2,val 5ADD R1,R2 6STORE R1,pi 7 Взаимное исключение критических интервалов Результат зависит от порядка выполнения команд. Требуется взаимное исключение критических интервалов.

14 сентября Москва, 2012Технология параллельного программирования OpenMP21 из 150 #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

14 сентября Москва, 2012Технология параллельного программирования OpenMP22 из 150 for (i = myid + 1; i

14 сентября Москва, 2012Технология параллельного программирования OpenMP23 из 150 #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

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

14 сентября Москва, 2012 Технология параллельного программирования OpenMP 25 из 150 OpenMP Fortran 1.1 OpenMP C/C OpenMP Fortran 2.0 OpenMP Fortran 2.0 OpenMP C/C OpenMP C/C OpenMP Fortran OpenMP F/C/C OpenMP F/C/C OpenMP F/C/C OpenMP F/C/C OpenMP F/C/C OpenMP F/C/C История OpenMP

14 сентября Москва, 2012 Технология параллельного программирования OpenMP 26 из 150 AMD Cray Fujitsu HP IBM Intel NEC The Portland Group, Inc. Oracle Corporation Microsoft Texas Instrument CAPS-Enterprise NVIDIA Convey Computer ANL ASC/LLNL cOMPunity EPCC LANL NASA RWTH Aachen University Texas Advanced Computing Center OpenMP Architecture Review Board

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

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

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

14 сентября Москва, 2012 Технология параллельного программирования OpenMP 30 из 150 omp_set_lock(lck) #pragma omp parallel for private(a, b) #pragma omp critical C$OMP PARALLEL DO SHARED(A,B,C) C$OMP PARALLEL REDUCTION (+: A, B) CALL OMP_INIT_LOCK (LCK) CALL OMP_TEST_LOCK(LCK) SETENV OMP_SCHEDULE STATIC,4 CALL CALL OMP_SET_NUM_THREADS(10) C$OMP DO LASTPRIVATE(XX) C$OMP ORDERED C$OMP SINGLE PRIVATE(X) C$OMP SECTIONS C$OMP MASTER C$OMP ATOMIC C$OMP FLUSH C$OMP PARALLEL DO ORDERED PRIVATE (A, B, C) C$OMP THREADPRIVATE(/ABC/) C$OMP PARALLEL COPYIN(/blk/) nthrds = OMP_GET_NUM_PROCS() C$OMP BARRIER OpenMP: API для написания многонитевых приложений Множество директив компилятора, набор функции библиотеки системы поддержки, переменные окружения Облегчает создание многонитиевых программ на Фортране, C и C++ Обобщение опыта создания параллельных программ для SMP и DSM систем за последние 20 лет OpenMP: API для написания многонитевых приложений Множество директив компилятора, набор функции библиотеки системы поддержки, переменные окружения Облегчает создание многонитиевых программ на Фортране, C и C++ Обобщение опыта создания параллельных программ для SMP и DSM систем за последние 20 лет Обзор основных возможностей OpenMP

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

14 сентября Москва, 2012 Технология параллельного программирования OpenMP 32 из 150 Действие остальных директив распространяется на структурный блок: #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; Не структурный блок Структурный блок

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++ 14 сентября Москва, 2012 Технология параллельного программирования OpenMP 33 из 150 Компиляторы, поддеживающие OpenMP

14 сентября Москва, 2012 Технология параллельного программирования OpenMP 34 из 150 ПроизводительКомпиляторОпция компиляции 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 сентября Москва, 2012 Технология параллельного программирования OpenMP 35 из 150 #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-программы

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

14 сентября Москва, 2012 Технология параллельного программирования OpenMP 37 из 150 Модель памяти в OpenMP 001 Нить 001 Нить 001 Нить

14 сентября Москва, 2012 Технология параллельного программирования OpenMP 38 из 150 Модель памяти в OpenMP 001 Нить Нить 1 static int i = 0; … = i + 1; i = i + 1; i = 0 i = 1 … = i + 2; // ? #pragma omp flush (i) i = 1

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

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

double Array1[100]; int main() { int Array2[100]; #pragma omp parallel work(Array2); printf(%d\n, Array2[0]); } 14 сентября Москва, 2012 Технология параллельного программирования OpenMP 41 из 150 extern double Array1[10]; void work(int *Array) { double TempArray[10]; static int count;... } TempArray Array1, Array2, count Классы переменных

Можно изменить класс переменной при помощи конструкций: shared (список переменных) private (список переменных) firstprivate (список переменных) lastprivate (список переменных) threadprivate (список переменных) default (private | shared | none) 14 сентября Москва, 2012 Технология параллельного программирования OpenMP 42 из 150 Классы переменных

Конструкция «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 == сентября Москва, 2012 Технология параллельного программирования OpenMP 43 из 150 Конструкция private

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

14 сентября Москва, 2012 Технология параллельного программирования OpenMP 45 из 150 lastprivate передает значение приватной переменной, посчитанной на последней итерации в глобальную переменную. int i; #pragma omp parallel { #pragma omp for lastprivate(i) for (i=0; i

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

14 сентября Москва, 2012 Технология параллельного программирования OpenMP 47 из 150 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

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

14 сентября Москва, 2012 Технология параллельного программирования OpenMP 49 из (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 Вычисление числа

14 сентября Москва, 2012Технология параллельного программирования OpenMP50 из 150 #include int main () { int n =100000, i; double pi, h, sum, x; h = 1.0 / (double) n; sum = 0.0; for (i = 1; i

14 сентября Москва, 2012Технология параллельного программирования OpenMP51 из 150 #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 сентября Москва, 2012Технология параллельного программирования OpenMP52 из 150 #include #define NUM_THREADS 32 int main () { int n =100000, i; double pi, h, sum[NUM_THREADS], x; 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

14 сентября Москва, 2012Технология параллельного программирования OpenMP53 из 150 #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(operator:list) Внутри паралельной области для каждой переменной из списка list создается копия этой переменной. Эта переменная инициализируется в соответствии с оператором operator (например, 0 для «+»). Для каждой нити компилятор заменяет в параллельной области обращения к редукционной переменной на обращения к созданной копии. По завершении выполнения параллельной области осуществляется объединение полученных результатов. 54 из 150 ОператорНачальное значение +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 Технология параллельного программирования OpenMP 14 сентября Москва, 2012

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

14 сентября Москва, 2012Технология параллельного программирования OpenMP56 из 150 Распределение витков циклов (директива for) Циклы с зависимостью по данным. Организация конвейерного выполнения для циклов с зависимостью по данным. Распределение нескольких структурных блоков между нитями (директива SECTION). Выполнение структурного блока одной нитью (директива single) Распределение операторов одного структурного блока между нитями (директива WORKSHARE) Понятие задачи Конструкции распределения работы

14 сентября Москва, 2012 Технология параллельного программирования OpenMP 57 из (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 Вычисление числа

14 сентября Москва, 2012Технология параллельного программирования OpenMP58 из 150 Вычисление числа на 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

14 сентября Москва, 2012Технология параллельного программирования OpenMP59 из 150 #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

#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 14 сентября Москва, 2012 Технология параллельного программирования OpenMP 60 из 150 Распределение витков цикла

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 14 сентября Москва, 2012 Технология параллельного программирования OpenMP 61 из 150 relational-op: < | | >= var: signed or unsigned integer type | random access iterator type | pointer type Распределение витков цикла

#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 // } 14 сентября Москва, 2012 Технология параллельного программирования OpenMP 62 из 150 Parallel Random Access Iterator Loop (OpenMP 3.0)

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++ ) - ошибка 14 сентября Москва, 2012 Технология параллельного программирования OpenMP 63 из 150 Использование указателей в цикле (OpenMP 3.0)

14 сентября Москва, 2012 Технология параллельного программирования OpenMP 64 из 150 Вложенность конструкций распределения работы void work(int i, int j) {} void wrong1(int n) { #pragma omp parallel default(shared) { int i, j; #pragma omp for for (i=0; i < n; i++) { /* incorrect nesting of loop regions */ #pragma omp for for (j=0; j < n; j++) work(i, j); }

14 сентября Москва, 2012 Технология параллельного программирования OpenMP 65 из 150 Вложенность конструкций распределения работы void work(int i, int j) {} void good_nesting(int n) { int i, j; #pragma omp parallel default(shared) { #pragma omp for for (i=0; i < n; i++) { #pragma omp parallel shared(i, n) { #pragma omp for for (j=0; j < n; j++) work(i, j); }

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

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

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

Клауза schedule: schedule(алгоритм планирования[, число_итераций]) Где алгоритм планирования один из: schedule(static[, число_итераций]) - статическое планирование; schedule(dynamic[, число_итераций]) - динамическое планирование; schedule(guided[, число_итераций]) - управляемое планирование; schedule(runtime) - планирование в период выполнения; schedule(auto) - автоматическое планирование (OpenMP 3.0). #pragma omp parallel for private(tmp) shared (a) schedule (runtime) for (int i=0; i

#pragma omp parallel for schedule(static, 10) for(int i = 1; i

#pragma omp parallel for schedule(dynamic, 15) for(int i = 1; i

число_выполняемых_потоком_итераций = max(число_нераспределенных_итераций/omp_get_num_threads(), число_итераций) #pragma omp parallel for schedule(guided, 10) for(int i = 1; i

#pragma omp parallel for schedule(runtime) for(int i = 1; i

#pragma omp parallel for schedule(auto) for(int i = 1; i

void example(int n, float *a, float *b, float *z) { int i; #pragma omp parallel { #pragma omp for schedule(static) nowait for (i=0; i

14 сентября Москва, 2012 Технология параллельного программирования OpenMP 76 из 150 Распределение витков цикла. Клауза 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

for(int i = 1; i < 100; i++) a[i]= a[i-1] + a[i+1] Между витками цикла с индексами i1 и i2 ( i1 i2. Если виток i1 читает "старое" значение, а виток i2 записывает "новое" значение, то между этими витками существует обратная зависимость i1

void print_iteration(int iter) { #pragma omp ordered printf("iteration %d\n", iter); } int main( ) { int i; #pragma omp parallel { #pragma omp for ordered for (i = 0 ; i < 5 ; i++) { print_iteration(i); another_work (i); } 14 сентября Москва, 2012 Технология параллельного программирования OpenMP 78 из 150 Распределение циклов с зависимостью по данным. Клауза и директива ordered Результат выполнения программы: iteration 0 iteration 1 iteration 2 iteration 3 iteration 4

Цикл с зависимостью по данным может быть распараллелен с помощью клаузы ordered: #pragma omp parallel for ordered for(int i = 1; i < 100; i++) { #pragma omp ordered { a[i]= a[i-1] + a[i+1] } 14 сентября Москва, 2012 Технология параллельного программирования OpenMP 79 из 150 Распределение циклов с зависимостью по данным. Клауза и директива ordered

for(int i = 1; i < M; i++) for(int j = 1; j < N; j++) a[i][j] = (a[i-1][j] + a[i][j-1] + a[i+1][j] + a[i][j+1]) / 4; 14 сентября Москва, 2012 Технология параллельного программирования OpenMP 80 из 150 Распределение циклов с зависимостью по данным. Организация конвейерного выполнения цикла

for(int i = 1; i < M; i++) for(int j = 1; j < N; j++) a[i][j] = (a[i-1][j] + a[i][j-1] + a[i+1][j] + a[i][j+1]) / 4; 14 сентября Москва, 2012 Технология параллельного программирования OpenMP 81 из 150 Распределение циклов с зависимостью по данным. Организация конвейерного выполнения цикла

14 сентября Москва, 2012 Технология параллельного программирования OpenMP 82 из 150 Распределение циклов с зависимостью по данным. Организация конвейерного выполнения цикла int iam, numt, limit; int *isync = (int *) malloc(omp_get_max_threads()*sizeof(int)); #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

14 сентября Москва, 2012 Технология параллельного программирования OpenMP 83 из 150 Распределение циклов с зависимостью по данным. Организация конвейерного выполнения цикла #pragma omp parallel { int iam = omp_get_thread_num (); int numt = omp_get_num_threads (); for (int newi=1; newi

14 сентября Москва, 2012 Технология параллельного программирования OpenMP 84 из 150 Распределение нескольких структурных блоков между нитями (директива sections) #pragma omp sections [клауза[[,] клауза]...] { [#pragma omp section] структурный блок [#pragma omp section структурный блок ]... } где клауза одна из : private(list) firstprivate(list) lastprivate(list) reduction(operator: list) nowait void XAXIS(); void YAXIS(); void ZAXIS(); void example() { #pragma omp parallel { #pragma omp sections { #pragma omp section XAXIS(); #pragma omp section YAXIS(); #pragma omp section ZAXIS(); }

#pragma omp single [клауза[[,] клауза]...] структурный блок где клауза одна из : private(list) firstprivate(list) copyprivate(list) nowait Структурный блок будет выполнен одной из нитей. Все остальные нити будут дожидаться результатов выполнения блока, если не указана клауза NOWAIT. 14 сентября Москва, 2012 Технология параллельного программирования OpenMP 85 из 150 #include float x, y; #pragma omp threadprivate(x, y) void init(float *a, float *b ) { #pragma omp single copyprivate(a,b,x,y) scanf("%f %f %f %f", a, b, &x, &y); } int main () { #pragma omp parallel { float x1,y1; init (&x1,&y1); parallel_work (); } Выполнение структурного блока одной нитью (директива single)

14 сентября Москва, 2012 Технология параллельного программирования OpenMP 86 из 150 Распределение операторов одного структурного блока между нитями (директива WORKSHARE) SUBROUTINE EXAMPLE (AA, BB, CC, DD, EE, FF, GG, HH, N) INTEGER N REAL AA(N,N), BB(N,N), CC(N,N) REAL DD(N,N), EE(N,N), FF(N,N) REAL GG(N,N), HH(N,N) REAL SHR !$OMP PARALLEL SHARED(SHR) !$OMP WORKSHARE AA = BB CC = DD WHERE (EE.ne. 0) FF = 1 / EE SHR = 1.0 GG (1:50,1) = HH(11:60,1) HH(1:10,1) = SHR !$OMP END WORKSHARE !$OMP END PARALLEL END SUBROUTINE EXAMPLE

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

14 сентября Москва, 2012 Технология параллельного программирования OpenMP 88 из 150 Понятие задачи. Директива 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 создается новая задача, которая состоит из операторов структурного блока; все используемые в операторах переменные могут быть локализованы внутри задачи при помощи соответствующих клауз. Созданная задача будет выполнена одной нитью из группы.

14 сентября Москва, 2012 Технология параллельного программирования OpenMP 89 из 150 Понятие задачи. Директива task #pragma omp for schedule(dynamic) firstprivate(i) for (i=0; i

14 сентября Москва, 2012 Технология параллельного программирования OpenMP 90 из 150 Использование директивы 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; }

14 сентября Москва, 2012 Технология параллельного программирования OpenMP 91 из 150 Использование директивы 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

14 сентября Москва, 2012 Технология параллельного программирования OpenMP 92 из 150 Использование директивы 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

14 сентября Москва, 2012 Технология параллельного программирования OpenMP 93 из 150 Использование директивы 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

14 сентября Москва, 2012 Технология параллельного программирования OpenMP 94 из 150 Использование задач. Директива taskwait #pragma omp taskwait int fibonacci(int n) { int i, j; if (n

14 сентября Москва, 2012 Технология параллельного программирования OpenMP 95 из 150 Внутренние переменные, управляющие выполнением OpenMP-программы (ICV-Internal Control Variables) Для параллельных областей: nthreads-var thread-limit-var dyn-var nest-var max-active-levels-var Для циклов: run-sched-var def-sched-var Для всей программы: stacksize-var wait-policy-var bind-var

14 сентября Москва, 2012 Технология параллельного программирования OpenMP 96 из 150 Internal Control Variables. nthreads-var void work(); int main () { omp_set_num_threads(3); #pragma omp parallel { omp_set_num_threads(omp_get_thread_num ()+2); #pragma omp parallel work(); } Существует одна копия этой переменной для каждой задачи Не корректно в OpenMP 2.5 Корректно в OpenMP 3.0

14 сентября Москва, 2012 Технология параллельного программирования OpenMP 97 из 150 Использование директивы 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);

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

14 сентября Москва, 2012Технология параллельного программирования OpenMP99 из 150 Директива master Директива critical Директива atomic Семафоры Директива barrier Директива taskwait Директива taskyield Конструкции для синхронизации нитей

14 сентября Москва, 2012Технология параллельного программирования OpenMP100 из 150 #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

14 сентября Москва, 2012Технология параллельного программирования OpenMP101 из 150 #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

Технология параллельного программирования OpenMP102 из 150 #pragma omp atomic [ read | write | update | capture ] expression-stmt #pragma omp atomic capture structured-block Если указана клауза read: v = x; Если указана клауза write: x = expr; Если указана клауза update или клаузы нет, то expression-stmt: x binop= expr; x = x binop expr; x++; ++x; x--; --x; Директива atomic х – скалярная переменная, expr – выражение, в котором не присутствует переменная х. binop - не перегруженный оператор: +, *, -, /, &, ^, |, > binop=: ++, сентября Москва, 2012

Технология параллельного программирования OpenMP103 из 150 Если указана клауза capture, то expression-stmt: v = x++; v = x--; v = ++x; v = -- x; v = x binop= expr; Если указана клауза capture, то structured-block: { v = x; x binop= expr;} { v = x; x = x binop expr;} { v = x; x++;} { v = x; ++x;} { v = x; x--;} { v = x; --x;} { x binop= expr; v = x;} { x = x binop expr; v = x;} { v = x; x binop= expr;} { x++; v = x;} { ++ x ; v = x;} { x--; v = x;} { --x; v = x;} Директива atomic

Технология параллельного программирования OpenMP104 из 150 type __sync_fetch_and_add (type *ptr, type value,...) type __sync_fetch_and_sub (type *ptr, type value,...) type __sync_fetch_and_or (type *ptr, type value,...) type __sync_fetch_and_and (type *ptr, type value,...) type __sync_fetch_and_xor (type *ptr, type value,...) type __sync_fetch_and_nand (type *ptr, type value,...) type __sync_add_and_fetch (type *ptr, type value,...) type __sync_sub_and_fetch (type *ptr, type value,...) type __sync_or_and_fetch (type *ptr, type value,...) type __sync_and_and_fetch (type *ptr, type value,...) type __sync_xor_and_fetch (type *ptr, type value,...) type __sync_nand_and_fetch (type *ptr, type value,...) bool __sync_bool_compare_and_swap (type *ptr, type oldval type newval,...) type __sync_val_compare_and_swap (type *ptr, type oldval type newval,...) Встроенные функции для атомарного доступа к памяти в GCC 14 сентября Москва, 2012

14 сентября Москва, 2012Технология параллельного программирования OpenMP105 из 150 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

14 сентября Москва, 2012Технология параллельного программирования OpenMP106 из 150 int atomic_read(const int *p) { int value; /* Guarantee that the entire value of *p is read atomically. No part of * *p can change during the read operation. */ #pragma omp atomic read value = *p; return value; } void atomic_write(int *p, int value) { /* Guarantee that value is stored atomically into *p. No part of *p can change * until after the entire write operation is completed. */ #pragma omp atomic write *p = value; } Использование директивы atomic

14 сентября Москва, 2012Технология параллельного программирования OpenMP107 из 150 int fetch_and_add(int *p) { /* Atomically read the value of *p and then increment it. The previous value is * returned. */ int old; #pragma omp atomic capture { old = *p; (*p)++; } return old; } Использование директивы atomic

14 сентября Москва, 2012Технология параллельного программирования OpenMP108 из 150 Концепцию семафоров описал Дейкстра (Dijkstra) в 1965 Семафор - неотрицательная целая переменная, которая может изменяться и проверяться только посредством двух функций: P - функция запроса семафора P(s): [if (s == 0) ; else s = s-1;] V - функция освобождения семафора V(s): [if (s == 0) ; s = s+1;] Семафоры

14 сентября Москва, 2012Технология параллельного программирования OpenMP109 из 150 Состояния семафора: uninitialized unlocked locked void omp_init_lock(omp_lock_t *lock); /* uninitialized to unlocked*/ void omp_destroy_lock(omp_lock_t *lock); /* unlocked to uninitialized */ void omp_set_lock(omp_lock_t *lock); /*P(lock)*/ void omp_unset_lock(omp_lock_t *lock); /*V(lock)*/ int omp_test_lock(omp_lock_t *lock); void omp_init_nest_lock(omp_nest_lock_t *lock); void omp_destroy_nest_lock(omp_nest_lock_t *lock); void omp_set_nest_lock(omp_nest_lock_t *lock); void omp_unset_nest_lock(omp_nest_lock_t *lock); int omp_test_nest_lock(omp_nest_lock_t *lock); Семафоры в OpenMP

14 сентября Москва, 2012Технология параллельного программирования OpenMP110 из 150 int main () { int n =100000, i; double pi, h, sum, x; omp_lock_t lck; h = 1.0 / (double) n; sum = 0.0; omp_init_lock(&lck); #pragma omp parallel default (none) private (i,x) shared (n,h,sum,lck) { double local_sum = 0.0; #pragma omp for for (i = 1; i

14 сентября Москва, 2012Технология параллельного программирования OpenMP111 из 150 #include int main() { omp_lock_t lck; int id; omp_init_lock(&lck); #pragma omp parallel shared(lck) private(id) { id = omp_get_thread_num(); omp_set_lock(&lck); printf("My thread id is %d.\n", id); /* only one thread at a time can execute this printf */ omp_unset_lock(&lck); while (! omp_test_lock(&lck)) { skip(id); /* we do not yet have the lock, so we must do something else*/ } work(id); /* we now have the lock and can do the work */ omp_unset_lock(&lck); } omp_destroy_lock(&lck); return 0; } Использование семафоров void skip(int i) {} void work(int i) {}

14 сентября Москва, 2012Технология параллельного программирования OpenMP112 из 150 Использование семафоров #include typedef struct { int a,b; omp_lock_t lck; } pair; void incr_a(pair *p, int a) { p->a += a; } void incr_b(pair *p, int b) { omp_set_lock(&p->lck); p->b += b; omp_unset_lock(&p->lck); } void incr_pair(pair *p, int a, int b) { omp_set_lock(&p->lck); incr_a(p, a); incr_b(p, b); omp_unset_lock(&p->lck); } void incorrect_example(pair *p) { #pragma omp parallel sections { #pragma omp section incr_pair(p,1,2); #pragma omp section incr_b(p,3); } Deadlock!

14 сентября Москва, 2012Технология параллельного программирования OpenMP113 из 150 Использование семафоров #include typedef struct { int a,b; omp_nest_lock_t lck; } pair; void incr_a(pair *p, int a) { p->a += a; } void incr_b(pair *p, int b) { omp_nest_set_lock(&p->lck); p->b += b; omp_nest_unset_lock(&p->lck); } void incr_pair(pair *p, int a, int b) { omp_nest_set_lock(&p->lck); incr_a(p, a); incr_b(p, b); omp_nest_unset_lock(&p->lck); } void incorrect_example(pair *p) { #pragma omp parallel sections { #pragma omp section incr_pair(p,1,2); #pragma omp section incr_b(p,3); }

14 сентября Москва, 2012Технология параллельного программирования OpenMP114 из 150 #include void something_useful ( void ); void something_critical ( void ); void foo ( omp_lock_t * lock, int n ) { int i; for ( i = 0; i < n; i++ ) #pragma omp task { something_useful(); while ( !omp_test_lock(lock) ) { #pragma omp taskyield } something_critical(); omp_unset_lock(lock); } Директива taskyield

14 сентября Москва, 2012Технология параллельного программирования OpenMP115 из 150 Точка в программе, достижимая всеми нитями группы, в которой выполнение программы приостанавливается до тех пор пока все нити группы не достигнут данной точки и все задачи, выполняемые группой нитей будут завершены. #pragma omp barrier По умолчанию барьерная синхронизация нитей выполняется: по завершению конструкции parallel; при выходе из конструкций распределения работ (for, single, sections, workshare), если не указана клауза nowait. #pragma omp parallel { #pragma omp master { int i, size; scanf("%d",&size); for (i=0; i

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

14 сентября Москва, 2012Технология параллельного программирования OpenMP117 из 150 Определяет максимально возможное количество нитей в создаваемой параллельной области. Начальное значение: зависит от реализации. Существует одна копия этой переменной для каждой задачи. Значение переменной можно изменить: 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

14 сентября Москва, 2012Технология параллельного программирования OpenMP118 из 150 Определяет максимальное количество нитей, которые могут быть использованы для выполнения всей программы. Начальное значение: зависит от реализации. Существует одна копия этой переменной для всей программы. Значение переменной можно изменить: 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

14 сентября Москва, 2012Технология параллельного программирования OpenMP119 из 150 Включает/отключает режим, в котором количество создаваемых нитей при входе в параллельную область может меняться динамически. Начальное значение: Если компилятор не поддерживает данный режим, то 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

14 сентября Москва, 2012Технология параллельного программирования OpenMP120 из 150 Включает/отключает режим поддержки вложенного параллелизма. Начальное значение: 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

14 сентября Москва, 2012Технология параллельного программирования OpenMP121 из 150 Задает максимально возможное количество активных вложенных параллельных областей. Начальное значение: зависит от реализации. Существует одна копия этой переменной для всей программы. Значение переменной можно изменить: 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

14 сентября Москва, 2012Технология параллельного программирования OpenMP122 из 150 Задает способ распределения витков цикла между нитями, если указана клауза 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

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

14 сентября Москва, 2012Технология параллельного программирования OpenMP124 из 150 Каждая нить представляет собой независимо выполняющийся поток управления со своим счетчиком команд, регистровым контекстом и стеком. Переменная 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

14 сентября Москва, 2012Технология параллельного программирования OpenMP125 из 150 int main () { int a[1024][1024]; #pragma omp parallel private (a) { for (int i=0;i

14 сентября Москва, 2012Технология параллельного программирования OpenMP126 из 150 Подсказка 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

14 сентября Москва, 2012Технология параллельного программирования OpenMP127 из 150 клаузавызов функциипеременная окружения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. Приоритеты

14 сентября Москва, 2012Технология параллельного программирования OpenMP128 из 150 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-программ

14 сентября Москва, 2012Технология параллельного программирования OpenMP129 из 150 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-программ

14 сентября Москва, 2012Технология параллельного программирования OpenMP130 из 150 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-программ

14 сентября Москва, 2012Технология параллельного программирования OpenMP131 из 150 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-программ

14 сентября Москва, 2012Технология параллельного программирования OpenMP132 из 150 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-программ

14 сентября Москва, 2012Технология параллельного программирования OpenMP133 из 150 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-программ

14 сентября Москва, 2012Технология параллельного программирования OpenMP134 из 150 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-программ

14 сентября Москва, 2012Технология параллельного программирования OpenMP135 из 150 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-программ. Функции работы со временем

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

14 сентября Москва, 2012Технология параллельного программирования OpenMP137 из 150 #pragma omp declare reduction (reduction-identifier : typename-list : combiner) [identity(identity-expr)] reduction-identifier gives a name to the operator typename-list is a list of types to which it applies combiner expression specifies how to combine values identity can specify the identity value of the operator Редукционные операции, определяемые пользователем

14 сентября Москва, 2012Технология параллельного программирования OpenMP138 из 150 #pragma omp declare reduction (merge : std::vector : omp_out.insert(omp_out.end(), omp_in.begin(), omp_in.end())) void schedule (std::vector &v, std::vector &filtered) { #pragma omp parallel for reduction (merge: filtered) for (std:vector ::iterator it = v.begin(); it < v.end(); it++) if ( filter(*it) ) filtered.push_back(*it); } omp_out refers to private copy that holds combined value omp_in refers to the other private copy Редукционные операции, определяемые пользователем

14 сентября Москва, 2012Технология параллельного программирования OpenMP139 из 150 export OMP_PLACES 0,1,2,3,8,10,12,14 Can also specify lists, groupings Planning new runtime library routines to observe and to control bindings (get_place, get/set_place_partition) Considering environment variables to: Control thread placement within a processor set Control initial placement of shared data Adapt data placement at runtime Привязка нитей к ядрам

14 сентября Москва, 2012Технология параллельного программирования OpenMP140 из 150 Расширение OpenMP для использования ускорителей … Node 1Node 64

14 сентября Москва, 2012Технология параллельного программирования OpenMP141 из 150 Алгоритм Якоби на языке Fortran PROGRAM JACOB_SEQ PARAMETER (L=4096, ITMAX=100) REAL A(L,L), B(L,L) PRINT *, '********** TEST_JACOBI **********' DO IT = 1, ITMAX DO J = 2, L-1 DO I = 2, L-1 A(I, J) = B(I, J) ENDDO DO J = 2, L-1 DO I = 2, L-1 B(I, J) = (A(I-1, J) + A(I, J-1) + A(I+1, J) + * A(I, J+1)) / 4 ENDDO END

14 сентября Москва, 2012Технология параллельного программирования OpenMP142 из 150 Алгоритм Якоби на языке Fortran Cuda PROGRAM JACOB_CUDA use cudafor use jac_cuda PARAMETER (L=4096, ITMAX=100) parameter (block_dim = 16) real, device, dimension(l, l) :: a, b type(dim3) :: grid, block PRINT *, '***** TEST_JACOBI ******* grid = dim3(l / block_dim, l / block_dim, 1) block = dim3(block_dim, block_dim, 1) DO IT = 1, ITMAX call arr_copy >>(a, b, l) call arr_renew >>(a, b, l) ENDDO END

14 сентября Москва, 2012Технология параллельного программирования OpenMP143 из 150 Алгоритм Якоби на языке Fortran Cuda module jac_cuda contains attributes(global) subroutine arr_copy(a, b, k) real, device, dimension(k, k) :: a, b integer, value :: k integer i, j i = (blockIdx%x - 1) * blockDim%x + threadIdx%x j = (blockIdx%y - 1) * blockDim%y + threadIdx%y if (i.ne.1.and. i.ne.k.and. j.ne.1.and. j.ne.k) A(I, J) = B(I, J) end subroutine arr_copy attributes(global) subroutine arr_renew(a, b, k) real, device, dimension(k, k) :: a, b integer, value :: k integer i, j i = (blockIdx%x - 1) * blockDim%x + threadIdx%x j = (blockIdx%y - 1) * blockDim%y + threadIdx%y if (i.ne.1.and. i.ne.k.and. j.ne.1.and. j.ne.k) B(I,J) =(A( I-1,J)+A(I,J-1)+A(I+1,J)+ A(I,J+1))/4 end subroutine arr_renew end module jac_cuda

14 сентября Москва, 2012Технология параллельного программирования OpenMP144 из 150 Алгоритм Якоби в модели HMPP !$HMPP jacoby codelet, target = CUDA SUBROUTINE JACOBY(A,B,L) IMPLICIT NONE INTEGER, INTENT(IN) :: L REAL, INTENT(IN) :: A(L,L) REAL, INTENT(INOUT) :: B(L,L) INTEGER I,J DO J = 2, L-1 DO I = 2, L-1 A(I,J) = B(I,J) ENDDO DO J = 2, L-1 DO I = 2, L-1 B(I,J) = (A(I-1,J ) + A(I,J-1 ) + * A(I+1,J ) + A(I,J+1 )) / 4 ENDDO END SUBROUTINE JACOBY PROGRAM JACOBY_HMPP PARAMETER (L=4096, ITMAX=100) REAL A(L,L), B(L,L) PRINT *, '**********TEST_JACOBI********** DO IT = 1, ITMAX !$HMPP jacoby callsite CALL JACOBY(A,B,L) ENDDO PRINT *, B END

14 сентября Москва, 2012Технология параллельного программирования OpenMP145 из 150 Алгоритм Якоби в модели HMPP PROGRAM JACOBY_HMPP PARAMETER (L=4096, ITMAX=100) REAL A(L,L), B(L,L) !$hmpp jac allocate, args[A;B].size={L,L} !$hmpp jac advancedload, args[B] PRINT *, '********** TEST_JACOBI **********' DO IT = 1, ITMAX !$hmpp jac region, args[A;B].noupdate=true DO J = 2, L-1 DO I = 2, L-1 A(I, J) = B(I, J) ENDDO DO J = 2, L-1 DO I = 2, L-1 B(I, J)=(A(I-1,J)+A(I,J-1)+A(I+1,J) + * A(I, J+1)) / 4 ENDDO !$hmpp jac endregion ENDDO !$hmpp jac delegatedstore, args[B] !$hmpp jac release PRINT *,B END

14 сентября Москва, 2012Технология параллельного программирования OpenMP146 из 150 Алгоритм Якоби в модели PGI APM PROGRAM JACOBY_PGI_APM PARAMETER (L=4096, ITMAX=100) REAL A(L,L), B(L,L) PRINT *, '********** TEST_JACOBI **********' !$acc data region copyin(B), copyout(B), local(A) DO IT = 1, ITMAX !$acc region DO J = 2, L-1 DO I = 2, L-1 A(I,J) = B(I,J) ENDDO DO J = 2, L-1 DO I = 2, L-1 B(I,J) = (A(I-1,J ) + A(I,J-1 ) + A(I+1,J ) + A(I,J+1 )) / 4 ENDDO !$acc end region ENDDO !$acc end data region PRINT *, B END

14 сентября Москва, 2012Технология параллельного программирования OpenMP147 из 150 Cray Compiling Environment !$omp acc_region !$omp acc_loop DO j = 1,M DO i = 2,N c(i,j) = a(i,j) + b(i,j) ENDDO !$omp end acc_loop !$omp end acc_region acc_region: acc_copy, acc_copyin, acc_copyout, acc_shared, private, firstprivate, default( |none), present, if(scalar-logical-expression), device(integer-expression), num_pes(depth:num [, depth:num]), async(handle) acc_loop: reduction(operator:list), collapse(n), schedule, cache(obj[:depth], hetero…

14 сентября Москва, 2012Технология параллельного программирования OpenMP148 из 150 Intel Many Integrated Core (MIC) !dir$ offload target(mic) !$omp parallel do do i=1,10 A(i) = B(i) * C(i) enddo !$omp end parallel

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

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