Основные конструкции OpenMP

Основные принципы OpenMP

OpenMP - это интерфейс прикладного программирования для создания многопоточных приложений, предназначенных в основном для параллельных вычислительных систем с общей памятью. OpenMP состоит из набора директив для компиляторов и библиотек специальных функций. Стандарты OpenMP разрабатывались в течение последних 15 лет применительно к архитектурам с общей памятью. Описание стандартов OpenMP и их реализации при программировании на алгоритмических языках Fortran и C/C++ можно найти в [2.1-2.6]. Наиболее полно вопросы программирования на OpenMP рассмотрены в монографиях [2.7-2.8]. В последние годы весьма активно разрабатывается расширение стандартов OpenMP для параллельных вычислительных систем с распределенной памятью (см., например, работы [2.9]). В конце 2005 года компания Intel анонсировала продукт Cluster OpenMP, реализующий расширение OpenMP для вычислительных систем с распределенной памятью. Этот продукт позволяет объявлять области данных, доступные всем узлам кластера, и осуществлять передачу данных между узлами кластера неявно с помощью протокола Lazy Release Consistency.

OpenMP позволяет легко и быстро создавать многопоточные приложения на алгоритмических языках Fortran и C/C++. При этом директивы OpenMP аналогичны директивам препроцессора для языка C/C++ и являются аналогом комментариев в алгоритмическом языке Fortran. Это позволяет в любой момент разработки параллельной реализации программного продукта при необходимости вернуться к последовательному варианту программы.

В настоящее время OpenMP поддерживается большинством разработчиков параллельных вычислительных систем: компаниями Intel, Hewlett-Packard, Silicon Graphics, Sun, IBM, Fujitsu, Hitachi, Siemens, Bull и другими. Многие известные компании в области разработки системного программного обеспечения также уделяют значительное внимание разработке системного программного обеспечения с OpenMP. Среди этих компаний отметим Intel, KAI, PGI, PSR, APR, Absoft и некоторые другие. Значительное число компаний и научно-исследовательских организаций, разрабатывающих прикладное программное обеспечение, в настоящее время использует OpenMP при разработке своих программных продуктов. Среди этих компаний и организаций отметим ANSYS, Fluent, Oxford Molecular, NAG, DOE ASCI, Dash, Livermore Software, а также и российские компании ТЕСИС, Центральную геофизическую экспедицию и российские научно-исследовательские организации, такие как Институт математического моделирования РАН, Институт прикладной математики им. Келдыша РАН, Вычислительный центр РАН, Научно-исследовательский вычислительный центр МГУ, Институт химической физики РАН и другие.

Принципиальная схема программирования в OpenMP

Любая программа, последовательная или параллельная, состоит из набора областей двух типов: последовательных областей и областей распараллеливания. При выполнении последовательных областей порождается только один главный поток (процесс). В этом же потоке инициируется выполнение программы, а также происходит ее завершение. В последовательной программе в областях распараллеливания порождается также только один, главный поток, и этот поток является единственным на протяжении выполнения всей программы. В параллельной программе в областях распараллеливания порождается целый ряд параллельных потоков. Порожденные параллельные потоки могут выполняться как на разных процессорах, так и на одном процессоре вычислительной системы. В последнем случае параллельные процессы (потоки) конкурируют между собой за доступ к процессору. Управление конкуренцией осуществляется планировщиком операционной системы с помощью специальных алгоритмов. В операционной системе Linux планировщик задач осуществляет обработку процессов с помощью стандартного карусельного ( round-robin ) алгоритма. При этом только администраторы системы имеют возможность изменить или заменить этот алгоритм системными средствами. Таким образом, в параллельных программах в областях распараллеливания выполняется ряд параллельных потоков. Принципиальная схема параллельной программы изображена на рис.2.1.

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

Выполнение параллельных потоков в параллельной области программы начинается с их инициализации. Она заключается в создании дескрипторов порождаемых потоков и копировании всех данных из области данных главного потока в области данных создаваемых параллельных потоков. Эта операция чрезвычайно трудоемка - она эквивалентна примерно трудоемкости 1000 операций. Эта оценка чрезвычайно важна при разработке параллельных программ c помощью OpenMP, поскольку ее игнорирование ведет к созданию неэффективных параллельных программ, которые оказываются зачастую медленнее их последовательных аналогов. В самом деле: для того чтобы получить выигрыш в быстродействии параллельной программы, необходимо, чтобы трудоемкость параллельных процессов в областях распараллеливания программы существенно превосходила бы трудоемкость порождения параллельных потоков. В противном случае никакого выигрыша по быстродействию получить не удастся, а зачастую можно оказаться даже и в проигрыше.

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

На основании изложенного выше можно сделать следующий важный вывод: при выделении параллельных областей программы и разработке параллельных процессов необходимо, чтобы трудоемкость параллельных процессов была не менее 2000 операций деления. В противном случае параллельный вариант программы будет проигрывать в быстродействии последовательной программе. Для эффективной работающей параллельной программы этот предел должен быть существенно превышен.

Синтаксис директив в OpenMP

Основные конструкции OpenMP - это директивы компилятора или прагмы (директивы препроцессора) языка C/C++. Ниже приведен общий вид директивы OpenMP прагмы.

#pragma omp конструкция [предложение [предложение] … ]

В языке Fortran директивы OpenMP являются строками-комментариями специального типа. Ниже в примере 2.3 приведены примеры таких строк в общем виде. Для обычных последовательных программ директивы OpenMP не изменяют структуру и последовательность выполнения операторов. Таким образом, обычная последовательная программа сохраняет свою работоспособность. В этом и состоит гибкость распараллеливания с помощью OpenMP.

Большинство директив OpenMP применяется к структурным блокам. Структурные блоки - это последовательности операторов с одной точкой входа в начале блока и одной точкой выхода в конце блока.

c$omp конструкция [предложение [предложение] … ]
!$omp конструкция [предложение [предложение] … ]
*$omp конструкция [предложение [предложение] … ]

В примерах 2.4 и 2.5 показаны примеры структурного и неструктурного блоков соответственно во фрагментах программ, написанных на языке Fortran. Видно, что в первом примере рассматриваемый блок является структурным, поскольку имеет одну точку входа и одну точку выхода. Во втором примере рассматриваемый блок не является структурным, поскольку имеет две точки входа. Следовательно, использование конструкций OpenMP для его распараллеливания некорректно. Из этих примеров видно, что директивы OpenMP, применяемые к структурным блокам, аналогичны операторным скобкам begin и end в алгоритмических языках Algol и Pascal.

c$omp parallel

   10 wrk (id) = junk (id)
      res (id) = wrk (id)**2
      if (conv (res)) goto 10

c$omp end parallel

         print *, id

c$omp parallel
   
   10 wrk (id) = junk (id)
   30 res (id) = wrk (id)**2
      if (conv (res)) goto 20
      goto 10

c$omp end parallel

      if (not_done) goto 30
   20 print *, id

В следующем фрагменте программы (Пример 2.6) показан общий вид основных директив OpenMP на языке Fortran.

c$omp  parallel
c$omp shared (var1, var2, …)
c$omp private (var1, var2, …)
c$omp firstprivate (var1, var2, …)
c$omp lastprivate (var1, var2, …)
c$omp reduction (operator | intrinsic: var1, var2, …)
c$omp if (expression)
c$omp default (private | shared | none)
       [Структурный блок программы]
c$omp end parallel

В рассматриваемом фрагменте предложение OpenMP shared используется для описания общих переменных. Как уже отмечалось ранее, общие переменные позволяют организовать обмен данными между параллельными процессами в OpenMP. Предложение private используется для описания внутренних (локальных) переменных для каждого параллельного процесса. Предложение firstprivate применяется для описания внутренних переменных параллельных процессов, однако данные в эти переменные импортируются из главного потока. Предложение reduction позволяет собрать вместе в главном потоке результаты вычислений частичных сумм, разностей и т. п. из параллельных потоков. Предложение if является условным оператором в параллельном блоке. И, наконец, предложение default определяет по умолчанию тип всех переменных в последующем параллельном структурном блоке программы. Далее механизм работы этих предложений будет рассмотрен более подробно. В заключение отметим, что символ амперсанд в шестой позиции строки используется для продолжения длинных директив OpenMP, не умещающихся на одной строке в программах на Fortran (см. рис.2.6).

Ниже во фрагменте программы (Пример 2.7) приведен общий вид основных директив OpenMP на языке C/C++.

# pragma omp parallel                         \
         private (var1, var2, …)              \
         shared (var1, var2, …)               \
         firstprivate (var1, var2, …)         \
         lastprivate (var1, var2, …)          \
         copyin (var1, var2, …)               \
         reduction (operator: var1, var 2, …) \
         if (expression)                      \
         default (shared | none)              \
{
   [ Структурный блок программы]
}

По сравнению с предыдущим, в рассматриваемом фрагменте появилось еще одно дополнительное предложение OpenMP - copyin. Оно позволяет легко и просто передавать данные из главного потока в параллельные. В Fortran также существует аналогичная возможность, однако механизм ее реализации несколько иной. Подробнее эти возможности будут рассмотрены далее. Кроме того, отметим, что вместо Fortran-директивы OpenMP

c$omp end parallel

в C/C++ используются обычные фигурные скобки. Для продолжения длинных директив на следующих строках в программах на C/C++ применяется символ "обратный слэш" в конце строки (см. пример 2.7).

Рассмотренные в настоящем разделе директивы OpenMP не охватывают весь спектр директив. В следующих разделах рассмотрим более подробно основные директивы OpenMP и механизм их работы.

Особенности реализации директив OpenMP

В этом разделе рассмотрим некоторые специфические особенности реализации директив OpenMP.

Количество потоков в параллельной программе определяется либо значением переменной окружения OMP_NUM_THREADS, либо специальными функциями, вызываемыми внутри самой программы. Задание переменной окружения OMP_NUM_THREADS в операционной системе Linux осуществляется следующим образом с помощью команды

export OMP_NUM_THREADS=256

Здесь было задано 256 параллельных потоков.

Просмотреть состояние переменной окружения OMP_NUM_THREADS можно, например, с помощью следующей команды:

export | grep OMP_NUM_THREADS

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

Каждый поток выполняет структурный блок программы, включенный в параллельный регион. В общем случае синхронизации между потоками нет, и заранее предсказать завершение потока нельзя. Управление синхронизацией потоков и данных осуществляется программистом внутри программы. После завершения выполнения параллельного структурного блока программы все параллельные потоки за исключением главного прекращают свое существование.

Пример ветвления во фрагменте программы, написанной на языке C/C++, в зависимости от номера параллельного потока показан в примере 2.8.

#pragma omp parallel
{
      myid = omp_get_thread_num ( ) ;
      if (myid == 0)
         do_something ( ) ;
      else
         do_something_else (myid) ;
}

В этом примере в первой строке параллельного блока вызывается функция omp_get_thread_num, возвращающая номер параллельного потока. Этот номер сохраняется в локальной переменной myid.Далее в зависимости от значения переменной myid вызывается либо функция do_something() в первом параллельном потоке с номером 0, либо функция do_something_else(myid) во всех остальных параллельных потоках.

В OpenMP существуют различные режимы выполнения (Execution Mode) параллельных структурных блоков. Возможны следующие режимы:

export OMP_DYNAMIC

omp_set_dynamic()

export OMP_STATIC

omp_set_static()

setenv OMP_NESTED TRUE

omp_set_nested( TRUE | FALSE )

Директивы OpenMP

Теперь перейдем к подробному рассмотрению директив OpenMP и механизмов их реализации.

Директивы shared, private и default

Эти директивы (предложения OpenMP) используются для описания типов переменных внутри параллельных потоков.

Предложение OpenMP

shared( var1, var2, …, varN )

определяет переменные var1, var2, …, varN как общие переменные для всех потоков. Они размещаются в одной и той же области памяти для всех потоков.

Предложение OpenMP

private( var1, var2, …, varN )

определяет переменные var1, var2, …, varN как локальные переменные для каждого из параллельных потоков. В каждом из потоков эти переменные имеют собственные значения и относятся к различным областям памяти: локальным областям памяти каждого конкретного параллельного потока.

В качестве иллюстрации использования директив OpenMP shared и private рассмотрим фрагмент программы (Пример 2.9). В этом примере переменная a определена как общая и является идентификатором одномерного массива. Переменные myid и x определены как локальные переменные для каждого из параллельных потоков. В каждом из параллельных потоков локальные переменные получают собственные значения. После чего при выполнении условия x<1.0 значение локальной переменной x присваивается myid -й компоненте общего для всех потоков массива a. Значение x будет неопределенным, если не определить x как переменную типа private. Отметим, что значения private -переменных не определены до и после блока параллельных вычислений.

c$omp parallel shared (a)
c$omp private (myid, x)
      myid = omp_get_thread_num ( )
      x = work (myid)
      if (x < 1.0) then
         a (myid) = x
      endif

Предложение OpenMP

default ( shared | private | none )

задает тип всех переменных, определяемых по умолчанию в последующем параллельном структурном блоке как shared, private или none. Например, если во фрагменте программы (примере 2.9) вместо

private( myid, x )

написать

default( private )

то определяемые далее по умолчанию переменные myid и x будут автоматически определены как private.

Директивы firstprivate и lastprivate

Директивы (предложения) OpenMP firstprivate и lastprivate используются для описания локальных переменных, инициализируемых внутри параллельных потоков. Переменные, описанные как firstprivate, получают свои значения из последовательной части программы. Переменные, описанные как lastprivate, сохраняют свои значения при выходе из параллельных потоков при условии их последовательного выполнения.

Предложение OpenMP

firstprivate( var1, var2, ..., varN )

определяет переменные var1, var2, ..., varN как локальные переменные для каждого из параллельных потоков, причем инициализация значений этих переменных происходит в самом начале параллельного структурного блока по значениям из предшествующего последовательного структурного блока программы.

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

program first
    integer :: myid, c
       integer, external :: omp_get_thread_num
       c=98
!$omp parallel private (myid)
!$omp firstprivate (c)
      myid = omp_get_thread_num ( )
      write (6, *) 'T: ', myid, 'c=', c
!$omp end parallel
      end program first

T:1 с=98
T:3 с=98
T:2 с=98
T:0 с=98

Предложение OpenMP

lastprivate( var1, var2, ..., varN )

определяет переменные var1, var2, ..., varN как локальные переменные для каждого из параллельных потоков, причем значения этих переменных сохраняются при выходе из параллельного структурного блока при условии, что параллельные потоки выполнялись в последовательном порядке.

В качестве иллюстрации рассмотрим фрагмент программы (Пример 2.11). В этом примере локальная переменная i принимает различные значения в каждом потоке параллельного структурного блока. После завершения параллельного структурного блока переменная i сохраняет свое последнее значение, полученное в последнем параллельном потоке, при условии последовательного выполнения всех параллельных потоков, т. е. n=N+1.

c$omp  do shared ( x )
c$omp lastprivate ( i)
       do i = 1, N
          x (i) = a
       enddo
       n = i