Параллельное программирование с OpenMP Бахтин Владимир Александрович Ассистент кафедры системного программированния факультета ВМК, МГУ им. М. В. Ломоносова. - презентация

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

2 Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 2 из 149 Содержание Тенденции развития современных процессоров Существующие подходы для создания параллельных программ OpenMP – модель параллелизма по управлению Конструкции распределения работы Конструкции для синхронизации нитей. Система поддержки выполнения OpenMP-программ.

3 В течение нескольких десятилетий развитие ЭВМ сопровождалось удвоением их быстродействия каждые года. Это обеспечивалось и повышением тактовой частоты и совершенствованием архитектуры (параллельное и конвейерное выполнение команд). Узким местом стала оперативная память. Знаменитый закон Мура, так хорошо работающий для процессоров, совершенно не применим для памяти, где скорости доступа удваиваются в лучшем случае каждые 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) Тенденции развития современных процессоров Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 3 из 149

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

5 Тенденции развития современных процессоров Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 5 из 149 Суперкомпьютер Jaguar Cray XT5-HE Opteron Six Core 2.6 GHz Пиковая производительность TFlop/s Число ядер в системе Производительность на Linpack TFlop/s (75.4% от пиковой) Энергопотребление комплекса кВт Важным параметром становится – Power Efficency (Megaflops/watt) Как добиться максимальной производительности на Ватт => Chip MultiProcessing, многоядерность.

6 Тенденции развития современных процессоров Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 6 из 149 AMD Opteron серии 6100 (Magny- Cours) 6176 SE 12 2,3 ГГц, 12 МБ L3 Cache ,4 ГГц, 12 МБ L3 Cache встроенный контроллер памяти (4 канала памяти DDR3) до 42.7 GB/s 4 канала «точка-точка» с использованием HyperTransort 3.0 до 25.6 GB/s

7 Тенденции развития современных процессоров Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. Intel Xeon серии 5600 (Nehalem) X ,33 ГГц, 12 нитей, 12 МБ L3 Cache X ,46 ГГц, 8 нитей, 12 МБ L3 Cache Intel® Turbo Boost Intel® Hyper-Threading Intel® QuickPath Intel® Intelligent Power 7 из 149

8 Тенденции развития современных процессоров Intel Core i7 980X (Gulftown) 3,33 ГГц 6 ядeр 12 потоков с технологией Intel Hyper-Threading 12 МБ кэш-памяти Intel Smart Cache встроенный контроллер памяти (3 канала памяти DDR МГц ) технология Intel QuickPath Interconnect Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 8 из 149

9 Тенденции развития современных процессоров Intel Itanium 9350 (Tukwila) 1,73 ГГц 4 ядeр 8 потоков с технологией Intel Hyper-Threading 24 МБ L3 кэш-памяти технология Intel QuickPath Interconnect технология Intel Turbo Boost Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 9 из 149

10 Тенденции развития современных процессоров IBM Power7 3,5 - 4,0 ГГц 8 ядер x 4 нити Simultaneuos MultiThreading L1 64КБ L2 256 КБ L3 32 МБ встроенный контроллер памяти Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 10 из 149

11 Тенденции развития современных процессоров Темпы уменьшения латентности памяти гораздо ниже темпов ускорения процессоров + прогресс в технологии изготовления кристаллов => CMT (Chip MultiThreading) Опережающий рост потребления энергии при росте тактовой частоты + прогресс в технологии изготовления кристаллов => CMP (Chip MultiProcessing, многоядерность) И то и другое требует более глубокого распараллеливания для эффективного использования аппаратуры Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 11 из 149

12 Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 12 из 149 Содержание Тенденции развития современных процессоров Существующие подходы для создания параллельных программ OpenMP – модель параллелизма по управлению Конструкции распределения работы Конструкции для синхронизации нитей. Система поддержки выполнения OpenMP-программ.

13 Существующие подходы для создания параллельных программ Автоматическое / автоматизированное распараллеливание Библиотеки нитей Win32 API POSIX Библиотеки передачи сообщений MPI OpenMP Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 13 из 149

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

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

16 Автоматическое распараллеливание Polaris, CAPO, WPP, SUIF, VAST/Parallel, OSCAR, Intel/OpenMP, UTL 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]]); указатели (ассоциация по памяти); сложный межпроцедурный анализ. Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 16 из 149

17 Автоматизированное распараллеливание 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 Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 17 из 149

18 Автоматизированное распараллеливание 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;} } Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 18 из 149 1) {A[i] += b;} } Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 18 из 149">

19 #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

20 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

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

22 #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 Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 22 из 149

23 for (i = myid + 1; i

24 #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

25 Достоинства использования OpenMP вместо MPI для многоядерных процессоров Возможность инкрементального распараллеливания Упрощение программирования и эффективность на нерегулярных вычислениях, проводимых над общими данными Ликвидация дублирования данных в памяти, свойственного MPI- программам Объем памяти пропорционален быстродействию процессора. В последние годы увеличение производительности процессора достигается увеличением числа ядер, при этом частота каждого ядра не увеличивается. Наблюдается тенденция к сокращению объема оперативной памяти, приходящейся на одно ядро. Присущая OpenMP экономия памяти становится очень важна. Наличие локальных и/или разделяемых ядрами КЭШей будут учитываться при оптимизации OpenMP-программ компиляторами, что не могут делать компиляторы с последовательных языков для MPI-процессов. Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 25 из 149

26 Oak Ridge National Laboratory Суперкомпьютер Jaguar Cray XT5-HE Opteron Six Core 2.6 GHz 2 место в TOP Пиковая производительность TFlop/s Число ядер в системе Производительность на Linpack TFlop/s (75.4% от пиковой) Updrage: замена 4-х ядерных процессоров AMD Opteron на 6-ти ядерные процессоры AMD Opteron Результат: 2-ое место в TOP500 в июне ое место в TOP500 в ноябре 2009 Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 26 из 149

27 Тесты NAS BT3D Навье-Стокс, метод переменных направлений CGОценка наибольшего собственного значения симметричной разреженной матрицы EPГенерация пар случайных чисел Гаусса FTБыстрое преобразование Фурье, 3D спектральный метод ISПараллельная сортировка LU3D Навье-Стокс, метод верхней релаксации MG3D уравнение Пуассона, метод Multigrid SP3D Навье-Стокс, Beam-Warning approximate factorization Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 27 из 149

28 Тесты NAS Analyzing the Effect of Different Programming Models Upon Performance and Memory Usage on Cray XT5 Platforms Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 28 из 149

29 Тесты NAS Analyzing the Effect of Different Programming Models Upon Performance and Memory Usage on Cray XT5 Platforms Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 29 из 149

30 Достоинства использования OpenMP вместо MPI для многоядерных процессоров #define Max(a,b) ((a)>(b)?(a):(b)) #define L 8 #define ITMAX 20 int i,j,it,k; double eps, MAXEPS = 0.5; double A[L][L], B[L][L]; int main(int an, char **as) { for (it=1; it < ITMAX; it++) { eps= 0.; for(i=1; j

31 Достоинства использования OpenMP вместо MPI для многоядерных процессоров Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. Для получения программы, способной работать на кластере, необходимо распределить данные и вычисления между процессорами. После распределения данных требуется организовать межпроцессорные взаимодействия. В данном случае - для доступа к удаленным данным используются теневые грани, которые являются источником дублирования данных. После распределения данных требуется организовать межпроцессорные взаимодействия. В данном случае - для доступа к удаленным данным используются теневые грани, которые являются источником дублирования данных. 31 из 149

32 Тесты NAS Analyzing the Effect of Different Programming Models Upon Performance and Memory Usage on Cray XT5 Platforms Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 32 из 149

33 Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 33 из 149 Содержание Тенденции развития современных процессоров Существующие подходы для создания параллельных программ OpenMP – модель параллелизма по управлению Конструкции распределения работы Конструкции для синхронизации нитей. Система поддержки выполнения OpenMP-программ.

34 История OpenMP 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 Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 34 из 149

35 OpenMP Architecture Review Board AMD Cray Fujitsu HP IBM Intel NEC The Portland Group, Inc. SGI Sun Microsoft ASC/LLNL cOMPunity EPCC NASA RWTH Aachen University Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 35 из 149

36 Все процессоры имеют доступ к любой точке памяти с одинаковой скоростью. Процессоры подключены к памяти либо с помощью общей шины, либо с помощью crossbar-коммутатора. Аппаратно поддерживается когерентность кэшей. Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. Cимметричные мультипроцессорные системы (SMP) 36 из 149

37 Fujitsu SPARC Enterprise M9000 SPARC64 VII 2,88 / 2,52 GHz 64 процессоров, 256 ядер, 512 нитей (Simultaneous Multi Threading) 4TB памяти OS Solaris 10 Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. Cимметричные мультипроцессорные системы (SMP) 37 из 149

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

39 Системы с неоднородным доступом к памяти (NUMA) SGI Altix UV (UltraVioloet) Intel® Xeon® quad-, six- or eight-core 7500 series (2048 cores) 16 TB памяти Interconnect Speed 15 ГБ/с, 1мкс Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 39 из 149

40 Компиляторы, поддеживающие OpenMP OpenMP 3.0: Intel 11.0: Linux, Windows and MacOS Sun Studio Express 11/08: Linux and Solaris PGI 8.0: Linux and Windows IBM 10.1: Linux and AIX GNU gcc (4.4.0) Предыдущие версии OpenMP: Absoft Pro FortranMP Lahey/Fujitsu Fortran 95 PathScale HP Microsoft Visual Studio 2010 C++ Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 40 из 149

41 Обзор основных возможностей OpenMP 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 лет Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 41 из 149

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

43 Структурный блок Действие остальных директив распространяется на структурный блок: #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; Неструктурный блок Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 43 из 149

44 Компиляция 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 Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 44 из 149

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

46 Использование функций поддержи выполнения 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; } Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 46 из 149

47 #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. Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 47 из 149

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

49 001 Модель памяти в OpenMP Нить 001 Нить 001 Нить Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 49 из 149

50 001 Модель памяти в OpenMP Нить Нить 1 static int i = 0; … = i + 1; i = i + 1; i = 0 i = 1 … = i + 2; // ? #pragma omp flush (i) i = 1 Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 50 из 149

51 Консистентность памяти в OpenMP Корректная последовательность работы нитей с переменной: Нить0 записывает значение переменной - write(var) Нить0 выполняет операцию синхронизации – flush (var) Нить1 выполняет операцию синхронизации – flush (var) Нить1 читает значение переменной – read (var) Директива flush: #pragma omp flush [(list)] - для Си !$omp flush [(list)] - для Фортран Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 51 из 149

52 Консистентность памяти в OpenMP 1. Если пересечение множеств переменных, указанных в операциях flush, выполняемых различными нитями не пустое, то результат выполнения операций flush будет таким, как если бы эти операции выполнялись в некоторой последовательности (единой для всех нитей). 2. Если пересечение множеств переменных, указанных в операциях flush, выполняемых одной нитью не пустое, то результат выполнения операций flush, будет таким, как если бы эти операции выполнялись в порядке определяемом программой. 3. Если пересечение множеств переменных, указанных в операциях flush, пустое, то операции flush могут выполняться независимо (в любом порядке). Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 52 из 149

53 Классы переменных В модели программирования с разделяемой памятью: Большинство переменных по умолчанию считаются SHARED Глобальные переменные совместно используются всеми нитями (shared) Фортран: COMMON блоки, SAVE переменные, MODULE переменные Си: file scope, static Динамически выделяемая память (ALLOCATE, malloc, new) Но не все переменные являются разделяемыми... Стековые переменные в подпрограммах (функциях), вызываемых из параллельного региона, являются PRIVATE. Переменные, объявленные внутри блока операторов параллельного региона являются приватными. Счетчики циклов, витки которых распределяются между нитями при помощи конструкций FOR и PARALLEL FOR. Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 53 из 149

54 Классы переменных double Array1[100]; int main() { int Array2[100]; #pragma omp parallel { int iam = omp_get_thread_num(); work(Array2, iam); printf(%d\n, Array2[0]); } extern double Array1[100]; void work(int *Array, int iam) { double TempArray[100]; static int count;... } TempArray,iam Array1, Array2, count Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 54 из 149

55 Можно изменить класс переменной при помощи конструкций: SHARED (список переменных) PRIVATE (список переменных) FIRSTPRIVATE (список переменных) LASTPRIVATE (список переменных) THREADPRIVATE (список переменных) DEFAULT (PRIVATE | SHARED | NONE) Классы переменных Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 55 из 149

56 Конструкция PRIVATE Конструкция «private(var)» создает локальную копию переменной «var» в каждой из нитей. Значение переменной не инициализировано Приватная копия не связана с оригинальной переменной В OpenMP 2.5 значение переменной «var» не определено после завершения параллельной конструкции #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; } Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 56 из 149

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

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

59 Конструкция THREADPRIVATE Отличается от применения конструкции PRIVATE: –с PRIVATE глобальные переменные маскируются –THREADPRIVATE сохраняют глобальную область видимости внутри каждой нити #pragma omp threadprivate (Var) Var = 1 Var = 2 … = Var Если количество нитей не изменилось, то каждая нить получит значение, посчитанное в предыдущей параллельной области. Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 59 из 149

60 Конструкция DEFAULT Меняет класс переменной по умолчанию: DEFAULT (SHARED) – действует по умолчанию DEFAULT (PRIVATE) – есть только в Fortran DEFAULT (NONE) – требует определить класс для каждой переменной 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 ……… } Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 60 из 149

61 Параллельная область (директива 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) Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 61 из 149

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

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

64 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

65 При взаимодействии через общую память нити должны синхронизовать свое выполнение. #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 Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 65 из 149

66 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

67 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

68 Клауза reduction reduction(operator:list) Внутри паралельной области для каждой переменной из списка list создается копия этой переменной. Эта переменная инициализируется в соответствии с оператором operator (например, 0 для «+»). Для каждой нити компилятор заменяет в параллельной области обращения к редукционной переменной на обращения к созданной копии. По завершении выполнения параллельной области осуществляется объединение полученных результатов. ОператорНачальное значение +0 *1 -0 &~0 |0 ^0 &&1 ||0 Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 68 из 149

69 Клауза 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 (); func (n, id); } return 0; } Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 69 из 149 10) { int id = omp_get_thread_num (); func (n, id); } return 0; } Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 69 из 149">

70 Клауза 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; } Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 70 из 149

71 Определение числа нитей в параллельной области Число создаваемых нитей зависит от: клаузы 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()) Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 71 из 149

72 Определение числа нитей в параллельной области Пусть 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); Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 72 из 149

73 Определение числа нитей в параллельной области 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 зависит от реализации компилятора; Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 73 из 149

74 Определение числа нитей в параллельной области #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 { … } Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 74 из 149

75 Клауза 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(); } Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 75 из 149

76 Содержание Тенденции развития современных процессоров Существующие подходы для создания параллельных программ OpenMP – модель параллелизма по управлению Конструкции распределения работы Конструкции для синхронизации нитей Система поддержки выполнения OpenMP-программ Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 76 из 149

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

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

79 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; for (i = start; i

80 #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

81 Распределение витков цикла #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 Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 81 из 149

82 Распределение витков цикла 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 Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 82 из 149

83 Parallel Random Access Iterator Loop (OpenMP 3.0) #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 // } Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 83 из 149

84 Использование указателей в цикле (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++ ) - ошибка Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 84 из 149

85 Вложенность конструкций распределения работы 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); } Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 85 из 149

86 Вложенность конструкций распределения работы 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); } Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 86 из 149

87 Распределение витков многомерных циклов. Клауза collapse (OpenMP 3.0) 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

88 Распределение витков многомерных циклов. Клауза collapse (OpenMP 3.0) 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

89 Распределение витков многомерных циклов. Клауза collapse (OpenMP 3.0) 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

90 Распределение витков цикла. Клауза schedule Клауза 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

91 Распределение витков цикла. Клауза schedule #pragma omp parallel for schedule(static, 10) for(int i = 1; i

92 Распределение витков цикла. Клауза schedule #pragma omp parallel for schedule(dynamic, 15) for(int i = 0; i < 100; i++) Результат выполнения программы на 4-х ядерном процессоре может быть следующим: Поток 0 получает право на выполнение итераций Поток 1 получает право на выполнение итераций Поток 2 получает право на выполнение итераций Поток 3 получает право на выполнение итераций Поток 3 завершает выполнение итераций. Поток 3 получает право на выполнение итераций Поток 2 завершает выполнение итераций. Поток 2 получает право на выполнение итераций Поток 0 завершает выполнение итераций. Поток 0 получает право на выполнение итераций Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 92 из 149

93 Распределение витков цикла. Клауза schedule число_выполняемых_потоком_итераций = max(число_нераспределенных_итераций/omp_get_num_threads(), число_итераций) #pragma omp parallel for schedule(guided, 10) for(int i = 0; i < 100; i++) Пусть программа запущена на 4-х ядерном процессоре. Поток 0 получает право на выполнение итераций Поток 1 получает право на выполнение итераций Поток 2 получает право на выполнение итераций Поток 3 получает право на выполнение итераций Поток 3 завершает выполнение итераций. Поток 3 получает право на выполнение итераций Поток 2 завершает выполнение итераций. Поток 2 получает право на выполнение итераций Поток 3 завершает выполнение итераций. Поток 3 получает право на выполнение итераций Поток 1 завершает выполнение итераций. Поток 1 получает право на выполнение 99 итерации. Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 93 из 149

94 Распределение витков цикла. Клауза schedule #pragma omp parallel for schedule(runtime) for(int i = 0; i < 100; i++) /* способ распределения витков цикла между нитями будет задан во время выполнения программы*/ При помощи переменных среды: csh: setenv OMP_SCHEDULE "dynamic,4 ksh: export OMP_SCHEDULE="static,10 Windows: set OMP_SCHEDULE=auto или при помощи функций системы поддержки: void omp_set_schedule(omp_sched_t kind, int modifier); Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 94 из 149

95 Распределение витков цикла. Клауза schedule #pragma omp parallel for schedule(auto) for(int i = 0; i < 100; i++) Способ распределения витков цикла между нитями определяется реализацией компилятора. На этапе компиляции программы или во время ее выполнения определяется оптимальный способ распределения. Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 95 из 149

96 Распределение витков цикла. Клауза nowait void example(int n, int m, float *a, float *b, float *y, float *z) { int i; #pragma omp parallel { #pragma omp for nowait for (i=1; i

97 Распределение витков цикла. Клауза nowait 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

98 Распределение нескольких структурных блоков между нитями (директива 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(); } Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 98 из 149

99 Выполнение структурного блока одной нитью (директива SINGLE). #pragma omp single [клауза[[,] клауза]...] структурный блок где клауза одна из : private(list) firstprivate(list) copyprivate(list) nowait Структурный блок будет выполнен одной из нитей. Все остальные нити будут дожидаться результатов выполнения блока, если не указана клауза NOWAIT. #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 (x1,y1); } Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 99 из 149

100 Распределение операторов одного структурного блока между нитями (директива 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 Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 100 из 149

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

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

103 Использование директивы 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; } Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 103 из 149

104 Содержание Тенденции развития современных процессоров Существующие подходы для создания параллельных программ OpenMP – модель параллелизма по управлению Конструкции распределения работы Конструкции для синхронизации нитей Система поддержки выполнения OpenMP-программ Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 104 из 149

105 #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 Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 105 из 149

106 Взаимное исключение критических интервалов При взаимодействии через общую память нити должны синхронизовать свое выполнение. #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 Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 106 из 149

107 Решение проблемы взаимного исключения должно удовлетворять требованиям: в любой момент времени только одна нить может находиться внутри критического интервала; если ни одна нить не находится в критическом интервале, то любая нить, желающая войти в критический интервал, должна получить разрешение без какой либо задержки; ни одна нить не должна бесконечно долго ждать разрешения на вход в критический интервал (если ни одна нить не будет находиться внутри критического интервала бесконечно). Взаимное исключение критических интервалов Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 107 из 149

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

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

110 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

111 int from_ list(float *a, int type); void work(int i, float *a); void example () { #pragma omp parallel { float *x; int ix_next; #pragma omp critical (list0) ix_next = from_ list(x,0); work(ix_next, x); #pragma omp critical (list1) ix_next = from_ list(x,1); work(ix_next, x); } Директива critical Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 111 из 149

112 #pragma omp atomic expression-stmt где expression-stmt: x binop= expr x++ ++x x-- --x Здесь х – скалярная переменная, expr – выражение со скалярными типами, в котором не присутствует переменная х. где binop - не перегруженный оператор: + * - / & ^ | > Директива atomic Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 112 из 149

113 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

114 Концепцию семафоров описал Дейкстра (Dijkstra) в 1965 Семафор - неотрицательная целая переменная, которая может изменяться и проверяться только посредством двух функций: P - функция запроса семафора P(s): [if (s == 0) ; else s = s-1;] V - функция освобождения семафора V(s): [if (s == 0) ; s = s+1;] Семафоры Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 114 из 149

115 Состояния семафора: 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 Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 115 из 149

116 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

117 #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) {} Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 117 из 149

118 Точка в программе, достижимая всеми нитями группы, в которой выполнение программы приостанавливается до тех пор пока все нити группы не достигнут данной точки и все явные задачи, выполняемые группой нитей будут завершены. #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

119 void work(int i, int j) {} void wrong(int n) { #pragma omp parallel default(shared) { int i; #pragma omp for for (i=0; i

120 void work(int i, int j) {} void wrong(int n) { #pragma omp parallel default(shared) { int i; #pragma omp critical { work(i, 0); /* incorrect nesting of barrier region in a critical region */ #pragma omp barrier work(i, 1); } Директива barrier Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 120 из 149

121 void work(int i, int j) {} void wrong(int n) { #pragma omp parallel default(shared) { int i; #pragma omp single { work(i, 0); /* incorrect nesting of barrier region in a single region */ #pragma omp barrier work(i, 1); } Директива barrier Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 121 из 149

122 #pragma omp taskwait int fibonacci(int n) { int i, j; if (n

123 #pragma omp flush [(список переменных)] По умолчанию все переменные приводятся в консистентное состояние (#pragma omp flush): При барьерной синхронизации При входе и выходе из конструкций parallel, critical и ordered. При выходе из конструкций распределения работ (for, single, sections, workshare), если не указана клауза nowait. При вызове omp_set_lock и omp_unset_lock. При вызове omp_test_lock, omp_set_nest_lock, omp_unset_nest_lock и omp_test_nest_lock, если изменилось состояние семафора. При входе и выходе из конструкции atomic выполняется #pragma omp flush(x), где x – переменная, изменяемая в конструкции atomic. Директива flush Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 123 из 149

124 Содержание Тенденции развития современных процессоров Существующие подходы для создания параллельных программ OpenMP – модель параллелизма по управлению Конструкции распределения работы Конструкции для синхронизации нитей Система поддержки выполнения OpenMP-программ Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 124 из 149

125 Для параллельных областей: nthreads-var thread-limit-var dyn-var nest-var max-active-levels-var Для циклов: run-sched-var def-sched-var Для всей программы: stacksize-var wait-policy-var Internal Control Variables. Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 125 из 149

126 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(); } Internal Control Variables. nthreads-var Некорректно в OpenMP 2.5 Корректно в OpenMP 3.0 Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 126 из 149

127 Internal Control Variables. nthreads-var Определяет максимально возможное количество нитей в создаваемой параллельной области. Начальное значение: зависит от реализации. Существует одна копия этой переменной для каждой задачи. Значение переменной можно изменить: C shell: setenv OMP_NUM_THREADS 16 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); Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 127 из 149

128 Internal Control Variables. thread-limit-var Определяет максимальное количество нитей, которые могут быть использованы для выполнения всей программы. Начальное значение: зависит от реализации. Существует одна копия этой переменной для всей программы. Значение переменной можно изменить: 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) Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 128 из 149

129 Internal Control Variables. dyn-var Включает/отключает режим, в котором количество создаваемых нитей при входе в параллельную область может меняться динамически. Начальное значение: Если компилятор не поддерживает данный режим, то 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); Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 129 из 149

130 Internal Control Variables. nest-var Включает/отключает режим поддержки вложенного параллелизма. Начальное значение: 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); Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 130 из 149

131 Internal Control Variables. max-active-levels-var Задает максимально возможное количество активных вложенных параллельных областей. Начальное значение: зависит от реализации. Существует одна копия этой переменной для всей программы. Значение переменной можно изменить: 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); Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 131 из 149

132 Internal Control Variables. run-sched-var Задает способ распределения витков цикла между нитями, если указана клауза 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; Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 132 из 149

133 Internal Control Variables. run-sched-var void work(int i); int main () { omp_sched_t schedules [] = {omp_sched_static, omp_sched_dynamic, omp_sched_guided, omp_sched_auto}; omp_set_num_threads (4); #pragma omp parallel { omp_set_schedule (schedules[omp_get_thread_num()],0); #pragma omp parallel for schedule(runtime) for (int i=0;i

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

135 Internal Control Variables. stack-size-var Каждая нить представляет собой независимо выполняющийся поток управления со своим счетчиком команд, регистровым контекстом и стеком. Переменная 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 Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 135 из 149

136 Internal Control Variables. stack-size-var int main () { int a[1024][1024]; #pragma omp parallel private (a) { for (int i=0;i

137 Internal Control Variables. wait-policy-var Подсказка 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 Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 137 из 149

138 Internal Control Variables. Приоритеты клаузавызов функциипеременная окружения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 Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 138 из 149

139 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- программ. Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 139 из 149

140 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- программ. Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 140 из 149

141 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- программ. Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 141 из 149

142 int omp_get_level(void) - возвращает уровень вложенности для текущей параллельной области. 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- программ. Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 142 из 149

143 int omp_get_active_level(void) - возвращает количество активных параллельных областей (выполняемых 2-мя или более нитями). 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- программ. Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 143 из 149 10) { int iam = omp_get_thread_num(); work(iam, size); } Система поддержки выполнения OpenMP- программ. Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 143 из 149">

144 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- программ. Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 144 из 149

145 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- программ. Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 145 из 149

146 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- программ. Функции работы со временем Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 146 из 149

147 Литература… Антонов А.С. Параллельное программирование с использованием технологии OpenMP: Учебное пособие.-М.: Изд-во МГУ, Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 147 из 149

148 Вопросы? Москва, 2011 г. Параллельное программирование с OpenMP © Бахтин В.А. 148 из 149

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