Лекция 4. Параллельное программирование для ресурсоёмких задач численного моделирования в физике

1. Параллельное программирование для ресурсоёмких задач численного моделирования в физике

Центр компьютерной физики
Кафедра общей физики и волновых процессов
Лаборатория Инженерной Физики
Параллельное программирование
для ресурсоёмких задач численного
моделирования в физике
В.О. Милицин, Д.Н. Янышев, И.А. Буткарев

2.

2

3. Содержание лекции

Основные принципы OpenMP
(продолжение)
Разделение работы (work-sharing constructs)
Синхронизация в OpenMP
Дополнительные возможности OpenMP
3

4. Принцип организации

Принцип организации
Использование потоков (общее адресное пространство)
Пульсирующий (fork-join) параллелизм
Главный поток по мере необходимости инициирует
параллельные потоки
Параллелизм включается в обычную последовательную
программу, которая сохраняет свою работоспособность в
обычном режиме
4

5. Разделение работы (work-sharing constructs)

Do/for - распараллеливание циклов (параллелизм данных)
Sections - функциональное распараллеливание
Single - директива для указания последовательного
выполнения кода
Физический факультет МГУ им М.В.Ломоносова
5

6. Конструкции 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
Физический факультет МГУ им М.В.Ломоносова
Пример
6

7. Предложение schedule ( type, [ chunk] )

static – итерации делятся на блоки по chunk итераций и статически
разделяются между потоками; если параметр chunk не определен,
итерации делятся между потоками равномерно и непрерывно
dynamic – распределение итерационных блоков осуществляется
динамически (по умолчанию chunk=1)
guided – размер итерационного блока уменьшает экспоненциально
при каждом распределении; chunk определяет минимальный
размер блока (по умолчанию chunk=1)
runtime – правило распределения определяется переменной
OMP_SCHEDULE (при использовании runtime параметр chunk
задаваться не должен)
Физический факультет МГУ им М.В.Ломоносова
7

8. Пример schedule ( static )

В этом случае петли цикла линейно распределяются между потоками
по следующей схеме
Физический факультет МГУ им М.В.Ломоносова
8

9. Пример schedule ( static , chunk )

В этом случае петли цикла распределяются между потоками
порциями размера chunk по следующей схеме
Физический факультет МГУ им М.В.Ломоносова
9

10. Пример schedule ( dynamic , chunk )

Вся загрузка делиться на
порции размера chunk
По умолчанию chunk=1
Каждая очередная порция
загружается в очередной
освободившийся поток
Физический факультет МГУ им М.В.Ломоносова
10

11. Пример schedule ( guided , chunk )

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

12. Тип schedule ( runtime [ , chunk ] )

В этом случае загрузка порций данных по потокам
определяется значением переменной окружения
OMP_SCHEDULE
Значение этой переменной проверяется перед каждой
загрузкой
По умолчанию оно имеет значение static
chunk определяет размер порции данных загружаемых в поток
Примеры задания переменной окружения
$ export OMP_SCHEDULE=static, 1000
$ export OMP_SCHEDULE=dynamic
Физический факультет МГУ им М.В.Ломоносова
12

13. Директивное предложение reduction

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

14. Примеры реализации предложения reduction

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

15. Конструкция sections

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

16. Пример конструкции sections

Каждая параллельная
секция выполняется в
параллельном потоке
Реализуется
функциональная
декомпозиция
Неявно в конце section
реализуется операция barrier
(для ее подавления следует
использовать предложение
nowait)
Физический факультет МГУ им М.В.Ломоносова
16

17. Конструкция single

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)
Физический факультет МГУ им М.В.Ломоносова
17

18. Пример конструкции single

Конструкция single используется
для выполнения блока
программы в параллельном
режиме только в одном потоке
Эта конструкция эквивалентна
конструкции section, но имеет
более простой синтаксис
Для предотвращения неявного
выполнения операции barrier
следует использовать
предложение nowait
Физический факультет МГУ им М.В.Ломоносова
18

19. Пример конструкции single nowait

#pragma omp parallel
for(Iterator i = list.begin(); i != list.end(); ++i )
{
#pragma omp single nowait
SomeLongAction(*i);
}
итератор будет в каждом потоке свой
функция SomeLongAction будет выполнена для каждого
элемента списка единожды
приводит к большой дополнительной синхронизации
Рекомендуемый минимальный размер последовательного
задания 10000 инструкций
Физический факультет МГУ им М.В.Ломоносова
19

20. Использование опции nowait

Использование опции nowait
#pragma omp for nowait
for (i=0; i<N; i++)
b[i] = f(a[i]);
#pragma omp for nowait
for (i=0; i<N; i++)
c[i] = g(a[i]);
Физический факультет МГУ им М.В.Ломоносова
#pragma omp for nowait
for (i=0; i<N; i++)
b[i] = f(a[i]);
#pragma omp for nowait
for (i=0; i<N; i++)
c[i] = g(b[i]);
20

21. Совместимость директив и их параметров

Физический факультет МГУ им М.В.Ломоносова
21

22. Синхронизация в OpenMP

Типы синхронизации в OpenMP
critical
atomic
barrier
master
ordered
flush
22

23. Синхронизация в OpenMP: тип critical

Поток описанный как critical
section выполняется в
монопольном режиме процессора
Синтаксис
C/C++
#pragma omp critical [ (name) ]
structured_block
FORTRAN
!$omp critical [ (name) ]
structured_block
!$omp end critical [ (name) ]
Разные критические секции
независимы, если они имеют
разные имена
Не поименованные критические
секции относятся к одной и той же
секции
23

24. Синхронизация в OpenMP: тип atomic

Предотвращает прерывания доступа, чтения и записи данных,
находящихся в общей памяти, со стороны других потоков
Синтаксис
C/C++
#pragma omp atomic
statement
FORTRAN
!$omp atomic
statement
Является альтернативой reduction
Применяется только к переменной в левой части оператора
присваивания следующего непосредственно за описанием
Дорогая операция с точки зрения временных затрат при
выполнении программы (но быстрее critical). Использование
рационально при относительно редком обращении к общим
переменным
24

25. Синхронизация в OpenMP: тип barrier

Устанавливает режим ожидания завершения
работы всех потоков по достижению barrier
Синтаксис
C/C++
#pragma omp barrier
FORTRAN
!$omp barrier
25

26. Синхронизация в OpenMP: тип master

В этом случае следующий за описанием блок
выполняется только в главном потоке. Остальные
потоки обходят этот блок без неявного режима barrier
Синтаксис
C/C++
#pragma omp master
structured_block
FORTRAN
!$omp master
structured_block
!$omp end master
26

27. Синхронизация в OpenMP: тип ordered

В этом случае в следующем за описанием блоке циклы
выполняются в порядке, как в последовательной
программе
Синтаксис
C/C++
#pragma omp ordered
structured_block
FORTRAN
!$omp ordered
structured_block
!$omp end ordered
int* arr = new int[10];
for(int i = 0; i < 10; i++)
arr[i] = i;
#pragma omp parallel for ordered
for (int i = 1; i < 10; i++)
{
#pragma omp ordered
arr[i] = arr[i - 1];
}
for(int i = 0; i < 10; i++)
printf("\narr[%d] = %d", i, arr[i]);
27

28. Синхронизация в OpenMP: тип flush

В этом случае значения всех общих переменных потоков должны быть
“сброшены” в память
Синтаксис
C/C++
#pragma omp flush(var1 [, var2]…)
FORTRAN
!$omp flush(var1 [, var2]…)
28

29. Дополнительные возможности

29

30. Миграция данных с помощью директивы threadprivate в Fortran

Директива threadprivate позволяет
сохранять данные параллельных
потоков на протяжении всей
программы
Для этого необходимо поместить
переменные в common блок, а
затем описать этот блок с
помощью директивы threadprivate
В процессе миграции сохраняется
соответствие между значениями
мигрирующих переменных и
номерами потоков
Синтаксис
FORTRAN
!$omp threadprivate (/cb/[,/cb2/…])
30

31. Миграция данных с помощью директивы threadprivate в С/С++

Миграция данных с помощью директивы
threadprivate в С/С++
Синтаксис
С/С++
#pragma omp threadprivate (cb1 [, cb2]…)
Элементами списка не могут быть
ссылки или переменные не
полностью определенные, а также
адреса констант
Нельзя использовать элементы
списка в всех директивах OpenMP
кроме copyin, schedule и if
Нельзя использовать threadprivate
в динамическом режиме работы
программы
31

32. Передача данных при миграции - copyin

С помощью выражения copyin
можно просто передавать
данные из главного потока в
параллельный
Синтаксис
C/C++
copyin (var1 [,var2]…)
FORTRAN
copyin (/cb/[,/cb2/…])
На FORTRAN в copyin задаются
имена common блоков, в
которых описаны
мигрирующие переменные, а в
С/C+ - имена самих
переменных
32

33. Пример передачи данных

float* work;
int size;
float val;
#pragma omp threadprivate(work,size,val)
void build_work()
{
int i;
work = (float*)malloc( sizeof(float)*size );
for( i = 0; i < size; ++i ) work[i] = val;
}
Значение каждой threadprivateпеременной из списка
устанавливается равным
значению этой переменной в
master-нити
int main()
{
read_from_file (val, size);
#pragma omp parallel copyin(val,size)
build_work();
}
Физический факультет МГУ им М.В.Ломоносова
33

34. Дополнительные возможности OpenMP: функции блокировки

Дополнительные возможности OpenMP:
функции блокировки
C/C++
void omp_init_lock(omp_lock_t *lock) – блокирует объект с
указателем lock
void omp_destroy_lock(omp_lock_t *lock) – гарантирует, что
объект с указателем lock не инициализирован
void omp_set_lock(omp_lock_t *lock) – блокирует выполнение
потока до тех пор, пока объект открыт для операций чтения или
записи, после их завершения блокирует объект и продолжает
выполнение потока
void omp_unset_lock(omp_lock_t *lock) – открывает
заблокированный объект
int omp_test_lock(omp_lock_t *lock) – пытается заблокировать
объект не прерывая выполнения потока (возвращает TRUE или
ненулевое значение, если попытка завершилась успешно, в
противном случае возвращает 0)
необходимо включение #include <omp.h>
FORTRAN
subroutine omp_init_lock(omp_lock_t lock)
subroutine omp_destroy_lock(omp_lock_t lock)
subroutine omp_set_lock(omp_lock_t lock)
subroutine omp_unset_lock(omp_lock_t lock)
logical omp_test_lock(omp_lock_t *lock)
переменная lock должна быть целочисленной типа KIND и иметь
размерность достаточную для записи адреса
34

35. OpenMP 3.1

Концепция задач
task
taskwait
Вложенный параллелизм
Области действия internal control variables (ICVs)
Добавлена max-active-levels-var ICV
…
…
См. http://www.openmp.org/mp-documents/OpenMP3.1.pdf
http://openmp.org/mp-documents/OpenMP3.1-CCard.pdf
35

36. OpenMP 4.0

Векторизация
явная векторизация циклов: simd
комбинация с for (#pragma omp parallel for simd)
…
Гибридные системы (ускорители, GPU, …)
target
teams, distribute
…
Привязка потоков (Thread affinity: parallel proc_bind, …)
Task enhancements (cancel, taskgroup, …)
…
См. http://www.openmp.org/mp-documents/OpenMP4.0.0.pdf
http://openmp.org/mp-documents/OpenMP-4.0-C.pdf
36

37.

Физический факультет МГУ им М.В.Ломоносова
37