Е.Ю. Алексеева Механико-математический факультет Южно-Уральского государственного университета

Содержание лекции Структура, области применения, этапы разработки и характеристики производительности параллельной программы Основные принципы OpenMP Механико-математический факультет Южно-Уральского государственного университета

4 Параллельная программа Механико-математический факультет Южно-Уральского государственного университета процесс Последовательная программа один поток управлениянесколько потоков управления Процесс = последовательная программа = последовательность операторов Параллельная программа процесс

5 Взаимодействие процессов Механико-математический факультет Южно-Уральского государственного университета Разделяемые переменные один процесс осуществляет запись в переменную, считываемую другим процессом Пересылка сообщений один процесс отправляет сообщение, которое получает другой процесс Память / Сеть

6 Классы приложений Механико-математический факультет Южно-Уральского государственного университета Многопоточные системы Распределенные системы Синхронные параллельные вычисления

7 Многопоточные системы Механико-математический факультет Южно-Уральского государственного университета Примеры приложений оконные системы на персональных компьютерах или рабочих станциях многопроцессорные операционные системы и системы с разделением времени системы реального времени, управляющие электростанциями, космическими аппаратами и т.д. Признаки число процессов (потоков) больше числа процессоров

8 Распределенные системы Механико-математический факультет Южно-Уральского государственного университета Примеры приложений файловые серверы в сети системы баз данных для банков, заказа авиабилетов и т.д. Web-серверы сети Internet предпринимательские системы, объединяющие компоненты производства отказоустойчивые системы, которые продолжают работать независимо от сбоя в компонентах Признаки компоненты выполняются на машинах, связанных локальной или глобальной сетью

9 Синхронные параллельные вычисления Механико-математический факультет Южно-Уральского государственного университета Примеры приложений научные вычисления, которые моделируют и имитируют такие явления, как глобальный климат, эволюция солнечной системы или результат действия нового лекарства графика и обработка изображений, включая создание спецэффектов в кино крупные комбинаторные или оптимизационные задачи, например, планирование авиаперелетов или экономическое моделирование Признаки количество процессов (потоков) равно числу процессоров процессы выполняют одни и те же действия, но с собственной частью данных (параллельность по данным), или решают различные задачи (параллельность по задачам)

10 Основные классы научных приложений Сеточные вычисления для приближенных решений дифференциальных уравнений в частных производных Точечные вычисления для моделирования систем взаимодействующих тел Матричные вычисления для решения систем линейных уравнений Механико-математический факультет Южно-Уральского государственного университета

11 Этапы разработки параллельной программы Последовательная программа выбор наилучшего алгоритма оптимизация Параллельная программа коррекция алгоритма (наилучший параллельный алгоритм наилучший последовательный алгоритм) распределение вычислений между процессами (производительность определяться временем работы наиболее загруженного процессора) дизайн взаимодействий и синхронизации между процессами (необходимо избегать состояния гонок и взаимных блокировок) Механико-математический факультет Южно-Уральского государственного университета

12 Закон Амдала – время выполнения последовательной программы – время выполнения параллельной программы на n процессорах – ускорение параллельной программы – время выполнения последовательной части алгоритма – время выполнения параллельной части алгоритма – доля последовательной части алгоритма – доля параллельной части алгоритма Механико-математический факультет Южно-Уральского государственного университета

13 Закон Амдала Механико-математический факультет Южно-Уральского государственного университета

14 Сетевой закон Амдала – время затрачиваемое на создание процессов и их диспетчеризацию взаимодействие процессов синхронизацию – доля времени приходящегося на обслуживание параллельной программы – время выполнения параллельной программы на n процессорах Механико-математический факультет Южно-Уральского государственного университета

CPU Общая физическая память RAM CPU Коммуникационная сеть RAM CPU SMP – архитектура SMP ccNUMA – архитектура Обмен данными между процессами через обмен сообщениями (Message Passing Interface - MPI) Библиотеки обмена сообщениями (Message Passing Libraries - MPL): Message Passing Interface – MPI Parallel Virtual Machine – PVM Shmem от Cray и SGI Многопоточное программирование с помощью нитей (threads) OpenMP – организация нитей с помощью директив компилятора Обмен данными между процессами через обмен сообщениями (Message Passing Interface - MPI) MPP – архитектура CPU RAM R R Подсистема ввода / вывода CPU Системы с распределенной памятью Системы с общей памятью Параллельные архитектуры Механико-математический факультет Южно-Уральского государственного университета

Основные принципы OpenMP OpenMP – это интерфейс прикладного программирования для создания многопоточных приложений в вычислительных системах с общей памятью OpenMP состоит из набора директив компиляторов и библиотек специальных функций OpenMP позволяет легко и быстро создавать многопоточные приложения на алгоритмических языках FORTRAN, C, C++ Стандарты OpenMP разрабатывались в течении последних 15 лет, применительно к архитектурам с общей памятью OpenMP поддерживается следующими основными разработчиками Оборудования: Intel, HP, SGI, Sun, IBM Системного программного обеспечения: Intel, KAI, PGI, PSR, APR, Absoft Прикладного программного обеспечения: ANSYS, Fluent, Oxford Molecular, NAG, DOE ASCI, Dash, Livermore Software, ТЕСИС, ЦГЭ, … Механико-математический факультет Южно-Уральского государственного университета

Стандарт OpenMP директивы процедуры переменные среды OpenMP ARB (ARchitecture Board) для языков Fortran и C/C /98 гг. концепции X3H5 (ANSI стандарт, 1993) - MPP POSIX Threads (Ptheads), IEEE c, 1995 – Unix Механико-математический факультет Южно-Уральского государственного университета

Достоинства OpenMP инкрементальное распараллеливание гибкость контроля и единственность разрабатываемого кода эффективность стандартизованность Single Program Multiple Data program para … if (процесс=мастер) then if (процесс=мастер) then master master else else slave slave end if end if …end Механико-математический факультет Южно-Уральского государственного университета

Начала программирования в OpenMP В моделях с общей памятью для обмена данными между потоками следует использовать общие переменные В противном случае возможен конфликт при доступе к данным Для предотвращения таких конфликтов следует использовать процедуру синхронизации (synchronization) Следует иметь ввиду, что процедура синхронизации очень дорогая операция и ее желательно избегать или применять как можно реже Механико-математический факультет Южно-Уральского государственного университета

Структура параллельной программы Набор директив компилятора определение параллельной области разделение работы синхронизация Библиотека функций Набор переменных окружения Механико-математический факультет Южно-Уральского государственного университета

Формат записи директив Формат C/C++ #pragma omp имя_директивы [clause,…] FORTRAN c$omp имя_директивы [clause,…] !$omp имя_директивы [clause,…] *$omp имя_директивы [clause,…] Пример #pragma omp parallel default(shared) private(beta,pi) Механико-математический факультет Южно-Уральского государственного университета

Основные конструкции OpenMP Большинство директив OpenMP применяется к структурным блокам. Структурные блоки – это последовательность операторов с одной точкой входа в начале блока и одной точкой выхода в конце блока. Структурный блок Неструктурный блок Механико-математический факультет Южно-Уральского государственного университета

Порождение нитей PARALLEL [clause,…]... END PARALLEL (основная директива OpenMP) создается набор (team) из N потоков (входной поток является основным потоком этого набора (master thread) и имеет номер 0) Код области дублируется или разделяется между потоками для параллельного выполнения в конце области синхронизация потоков – выполняется ожидание завершения вычислений всех потоков; дальнейшие вычисления продолжает выполнять только основной поток. Механико-математический факультет Южно-Уральского государственного университета

Порождение нитей FORTRAN C/C++ Механико-математический факультет Южно-Уральского государственного университета

Определение параллельной области Количество потоков определяется переменной окружения OMP_NUM_THREADS функцией omp_set_num_threads() Каждый поток имеет свой номер thread_number определяется функцией omp_get_thread_num() - от нуля (главный поток) и до OMP_NUM_THREADS-1) Каждый поток выполняет структурный блок программы, включенный в параллельный регион В общем случае синхронизации между потоками нет. После завершения параллельного блока все потоки за исключением главного прекращают свое существование Механико-математический факультет Южно-Уральского государственного университета

Определение параллельной области Режимы выполнения (Execution Mode) параллельных блоков динамический (Dynamic Mode) – количество потоков определяется ОС переменн ая окружения OMP_DYNAMIC функция omp_set_dynamic() статический (Static Mode) – количество потоков определяется программистом переменная окружения OMP_STATIC функция omp_set_static() Возможна вложенность параллельных структурных блоков (во многих реализациях не обеспечивается) по умолчанию во вложенной области создается один поток управление - функция omp_set_nested() или переменная OMP_NESTED Механико-математический факультет Южно-Уральского государственного университета

Директивные предложения (clauses) OpenMP shared(var1, var2, …) переменные var1,… являются общими для всех потоков и относятся к одной области памяти private(var1, var2, …) переменные var1, var2,… имеют собственные значения внутри каждого потока и относятся кразным областям памяти firstprivate(var1, var2, …) переменные имеют тип private и инициализируются в начале структурного блока lastprivate(var1, var2, …) переменные имеют тип private и сохраняют свои значения при выходе из структурного блока if(condition) следующий параллельный блок выполняется только в том случае, если condition=TRUE default(shared|private|none) определяет по умолчанию тип всех переменных определяемых по умолчанию в следующем параллельном структурном блоке schedule (type [,chunk]) определяет распределение петель циклов по потокам reduction (operator | intrinsic: var1, var2, …) гарантирует безопасное вычисление разностей, сумм, произведений и т.д. (operator задает операцию) по петлям циклов Механико-математический факультет Южно-Уральского государственного университета

Примеры реализации предложений Каждый поток имеет свою собственную копию переменных x и myid Значение x будет неопределенным, если не определить x как private Значения private-переменных не определены до и после блока параллельных вычислений Описание default автоматически определяет переменные x и myid как private private default Механико-математический факультет Южно-Уральского государственного университета

Пример реализации предложения firstprivate В каждом параллельном потоке используется своя переменная c, но значение этой переменной перед входом в параллельный блок программы берется из предшествующего последовательного блока Механико-математический факультет Южно-Уральского государственного университета

Пример реализации предложения lastprivate В этом случае переменная i определена для каждого потока в параллельном блоке После завершения параллельного блока переменная i сохраняет последнее значение, полученное в параллельном блоке, при условии его последовательного выполнения, т.е. n=N+1 Механико-математический факультет Южно-Уральского государственного университета

Пример реализации предложения if В этом примере цикл распараллеливается только в том случае ( n>2000 ), когда параллельная версия будет заведомо быстрее последовательной !!! Трудоемкость образования потоков ~ 1000 операций деления!!! Механико-математический факультет Южно-Уральского государственного университета

Разделение работы (work-sharing constructs) Do/for - распараллеливание циклов (параллелизм данных) Sections - функциональное распараллеливание Single - директива для указания последовательного выполнения кода Механико-математический факультет Южно-Уральского государственного университета

Конструкции do/for C/C++ #pragma omp for [clause...] for_loop FORTRAN c$omp do [clause...] do loop [c$omp do [nowait]] По умолчанию в конце цикла реализуется функция barrier (барьер) Для отмены функции barrier следует воспользоваться предложением nowait Здесь в качестве предложения возможны следующие конструкции schedule (type [,chunk]) ordered private (list) firstprivate (list) lastprivate (list) shared (list) reduction (operator: list) nowait Пример Механико-математический факультет Южно-Уральского государственного университета

Предложение schedule ( type, [ chunk] ) static – итерации делятся на блоки по chunk итераций и статически разделяются между потоками; если параметр chunk не определен, итерации делятся между потоками равномерно и непрерывно dynamic – распределение итерационных блоков осуществляется динамически (по умолчанию chunk=1) guided – размер итерационного блока уменьшает экспоненциально при каждом распределении; chunk определяет минимальный размер блока (по умолчанию chunk=1) runtime – правило распределения определяется переменной OMP_SCHEDULE (при использовании runtime параметр chunk задаваться не должен) Механико-математический факультет Южно-Уральского государственного университета

Пример schedule ( static ) В этом случае петли цикла линейно распределяются между потоками по следующей схеме Механико-математический факультет Южно-Уральского государственного университета

Пример schedule ( static, chunk ) В этом случае петли цикла распределяются между потоками порциями размера chunk по следующей схеме Механико-математический факультет Южно-Уральского государственного университета

Пример schedule ( dynamic, chunk) Вся загрузка делиться на порции размера chunk По умолчанию chunk=1 Каждая очередная порция загружается в очередной освободившийся поток Механико-математический факультет Южно-Уральского государственного университета

Пример schedule ( guided, chunk ) Этот режим загрузки данных в поток работает также как и dynamic, но размер данных определяется динамически, не превосходя размер chunk При этом обеспечивается достаточно сбалансированная загрузка потоков с небольшими задержками при завершении параллельной обработки Механико-математический факультет Южно-Уральского государственного университета

Тип schedule ( runtime [, chunk ] ) В этом случае загрузка порций данных по потокам определяется значением переменной окружения OMP_SCHEDULE Значение этой переменной проверяется перед каждой загрузкой По умолчанию оно имеет значение static chunk определяет размер порции данных загружаемых в поток Примеры задания переменной окружения $ setenv OMP_SCHEDULE static, 1000 $ setenv OMP_SCHEDULE dynamic Механико-математический факультет Южно-Уральского государственного университета

Директивное предложение reduction reduction (operator|intrinsic:var1[,var2]) определяет список переменных, для которых выполняется операция редукции В FORTRAN допустимы следующие операции и функции operator может быть +, -, *,.and.,.or.,.eqv.,.neqv. intrinsic может быть max, min, iand, ior, ieor В С допустимы следующие операции и функции operator может быть +, -, *, &, ^, &&, || указатели и ссылки в предложениях reduction применять нельзя Механико-математический факультет Южно-Уральского государственного университета

Примеры реализации предложения reduction В каждом потоке определяется переменная sum для частичных сумм После завершения всех потоков частичные суммы добавляются к глобальной переменной sum В каждом потоке вычисляются частичные минимумы по значениям, в соответствующем потоке После завершения параллельного блока вычисляется минимум gmin по значениям частичных минимумов Механико-математический факультет Южно-Уральского государственного университета

C/C++ #pragma omp sections [clause...] { #pragma omp section structured_block [#pragma omp section structured_block …] } каждый фрагмент выполняется однократно разные фрагменты выполняются разными потоками завершение директивы по умолчанию синхронизируется директивы section должны использоваться только в статическом контексте Здесь в качестве предложения возможны следующие конструкции private (list) firstprivate (list) lastprivate (list) reduction (operator: list) nowait Конструкция sections FORTRAN c$omp sections [clause...] c$omp section structured_block [c$omp section structured_block …] c$omp end sections [nowait] Механико-математический факультет Южно-Уральского государственного университета

Пример конструкции sections Каждая параллельная секция выполняется в параллельном потоке Реализуется функциональная декомпозиция Неявно в конце section реализуется операция barrier (для ее подавления следует использовать предложение nowait) Механико-математический факультет Южно-Уральского государственного университета

C/C++ #pragma omp single [clause...] structured_block FORTRAN c$omp single [clause...] structured_block c$omp end single [nowait] определение фрагмента кода, который должен быть выполнен только одним потоком все остальные потоки ожидают завершения выполнения фрагмента (если не указан параметр nowait) Здесь в качестве предложения возможны следующие конструкции private (list) firstprivate (list) Конструкция single Механико-математический факультет Южно-Уральского государственного университета

Пример конструкции single Конструкция single используется для выполнения блока программы в параллельном режиме только в одном потоке Эта конструкция эквивалентна конструкции section, но имеет более простой синтаксис Для предотвращения неявного выполнения операции barrier следует использовать предложение nowait Механико-математический факультет Южно-Уральского государственного университета

Совместимость директив и их параметров Механико-математический факультет Южно-Уральского государственного университета

Переменные окружения OpenMP OMP_NUM_THREADS - определяет число нитей для исполнения параллельных областей приложения. OMP_SCHEDULE - определяет способ распределения итераций в цикле, если в директиве DO использовано предложение SCHEDULE(RUNTIME). OMP_DYNAMIC - разрешает или запрещает динамическое изменение числа нитей. OMP_NESTED - разрешает или запрещает вложенный параллелизм. Пример Механико-математический факультет Южно-Уральского государственного университета

Задание переменных окружения с помощью функций runtime OpenMP (void) omp_set_num_threads(int num_threads) – задает число потоков в области параллельных вычислений int omp_get_num_threads() – возвращает количество потоков в текущий момент int omp_get_max_threads() – возвращает максимальное количество потоков, которое может быть возвращено функцией omp_get_num_threads int_omp_get_thread_num() – возвращает номер потока от 0 до количество потоков - 1 int omp_get_num_procs() – возвращает количество процессоров доступных программе (int/logical) omp_in_parallel() – возвращает TRUE из параллельной области программы и FALSE из последовательной (void) omp_set_dynamic( TRUE | FALSE ) – определяет или отменяет динамический режим (int/logical) omp_get_dynamic() – возвращает TRUE, если режим динамический, и FALSE в противном случае (void) omp_set_nested( TRUE | FALSE ) – определяет или отменяет вложенный режим для параллельной обработки (int/logical) omp_get_nested() – возвращает TRUE, если режим вложенный, и FALSE в противном случае Механико-математический факультет Южно-Уральского государственного университета

Задание переменных окружения с помощью функций runtime OpenMP (FORTRAN vs С/С++ ) В FORTRAN, возвращающие значения, функции реализованы как функции, а функции, определяющие значения переменных, окружения как подпрограммы Тип функций в FORTRAN должен быть определен и соответствовать возвращаемым данным В С/С++ для описания вышеперечисленных функций необходимо включение #include Функции, задающие режимы работы программы, изменяют значения переменных окружения Механико-математический факультет Южно-Уральского государственного университета

Задания по OpenMP Задание N 1: Просмотреть значение переменной окружения OMP_NUM_THREADS Задание N 2: Задать значение переменной окружения OMP_NUM_THREADS равной 4 Задание N 3: Вести в текст простейшей (hello world!) программы инструкции OpenMP Задание N 4: Оттранслировать и запустить программу в параллельном режиме Задание N 5: Написать последовательную программу для расчета числа ПИ. Проверить её работу в последовательном режиме. Вставить инструкции OpenMP для распараллеливания циклов. Оттранслировать и запустить программу в параллельном режиме (при выполнении просмотреть как работают потоки с помощью системной команды top) Механико-математический факультет Южно-Уральского государственного университета