Загрузка и синхронизация в OpenMP

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

Рассмотрению процессов балансировки процессов в вычислительных системах посвящено много литературы (см., например, работы [3.1-3.14]). В настоящее время можно выделить две основных группы методов решения проблем балансировки: статические и динамические. В основе статических методов лежит принцип геометрического параллелизма, когда вычислительный процесс представляется в виде взвешенного графа, а затем этот граф разбивается на эквивалентные части [3.1-3.9]. Для решения таких задач используются различные спектральные и эвристические подходы, а также их комбинации. Отметим, что для построения графов, описывающих вычислительный процесс, важно иметь и учитывать как можно больше априорной информации о процессе, поскольку в этом случае повышается точность описания.

В методах динамической балансировки априорная информация не используется. В них процессы загружаются в освободившиеся процессоры по мере освобождения последних [3.10]. При этом более равномерная загрузка процессоров получается при достаточно большом количестве независимых процессов. Решение о загрузке процессоров может приниматься по-разному: либо в одном отдельном управляющем процессе, либо в разных управляющих процессах, каждый из которых ассоциирован с вычислительным процессом. Последний подход известен также как метод коллективного решения. Этот подход развивается и разработан в Институте математического моделирования РАН [3.11]. Апробация динамической балансировки, основанной на идеях коллективного решения, показала эффективность подхода при решении различных классов вычислительных задач математической физики.

Отметим также, что в библиотеке PVM имеются средства управления процессами (Process Management), работающие в рамках системы управления ресурсами (General Resource Manager - GRM) [3.12]. Использование этих средств совместно с библиотекой PVM MPI позволяет существенно улучшить балансировку и производительность параллельных кластеров [3.13-3.14].

Синхронизация процессов в OpenMP

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

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

Во-вторых, было отмечено, что неявно (по умолчанию) синхронизация параллельных процессов обеспечивается при выполнении циклов в параллельном режиме. Была упомянута директива nowait для устранения неявной синхронизации при завершении циклов. Однако пользоваться этой директивой следует весьма и весьма аккуратно, предварительно проанализировав порядок работы программы и убедившись, что отмена синхронизации не приведет к порче данных и непредсказуемым результатам.

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

Всего в OpenMP существует шесть типов синхронизации:

Далее подробно рассмотрим эти типы.

Синхронизация типа atomic

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

Для задания этого типа синхронизации в OpenMP в программах, написанных на языке C/C++, используется прагма

#pragma omp atomic 
<операторы программы>

В программах, написанных на языке Fortran, задание синхронизации типа atomic осуществляется с помощью следующего предложения OpenMP:

c$omp atomic 
<операторы программы>

Отметим, что синхронизация atomic является альтернативой директивы reduction. Применяется эта синхронизация только для операторов, следующих непосредственно за определяющей ее директивой. Синхронизация atomic - очень дорогая операция с точки зрения трудоемкости выполнения программы. Она выполняется автоматически по умолчанию при завершении циклов в параллельном режиме. Для того чтобы ее исключить, следует использовать директиву nowait.

Пример установки синхронизации типа atomic приведен во фрагменте программы в примере 3.1.

integer, dimension (8) :: a, index
      data index/ 1, 1, 2, 3, 1, 4, 1, 5 /
с$omp parallel private (I), shared (a, index)
c$omp do
      do I =1, 8
с$omp atomic
         a(index(I)) = a(index(I)) + index(I)
      enddo
с$omp end parallel

В приведенном примере в параллельном режиме синхронизируются только вычисления оператора

a(index(I)) = a(index(I)) + index(I)

Синхронизация типа critical

Этот тип синхронизации используется для описания структурных блоков, выполняющихся только в одном потоке из всего набора параллельных потоков.

Для задания синхронизации типа critical в OpenMP в программах, написанных на языке C/C++, используется прагма

#pragma omp critical [ name ] 
<структурный блок программы>

В программах, написанных на языке Fortran, задание синхронизации типа critical осуществляется с помощью следующего предложения OpenMP:

c$omp critical [ name ] 
< структурный блок программы > 
c$omp end critical [ name ]

Здесь name - имя критической секции ( critical section ). Разные критические секции независимы, если они имеют разные имена. Не поименованные критические секции относятся к одной и той же секции.

Пример использования синхронизации типа critical приведен во фрагменте программы (пример 3.2). В этом примере определены две критических секции name1 и name2, каждая из которых выполняется только в одном из параллельных потоков. Этот тип синхронизации очень важен для достижения пиковой производительности программ.

integer :: cnt1, cnt2
с$omp parallel private (i)
с$omp shared (cnt1, cnt2)

с$omp do
   do i = 1, n
      ... do work ...
      if (condition1) then
с$omp critical (name1)
         cnt1 = cnt1 + 1
с$omp end critical (name1)
      else
с$omp critical (name1)
         cnt1 = cnt1 - 1
с$omp end critical (name1)
      endif
      if (condition2) then
с$omp critical (name2)
         cnt2 = cnt2+1
с$omp end critical (name2)
      endif
   enddo
с$omp end parallel

Синхронизация типа barrier

Синхронизация типа barrier устанавливает режим ожидания завершения работы всех запущенных в программе параллельных потоков при достижении точки barrier.

Для задания синхронизации типа barrier в OpenMP в программах, написанных на языке C/C++, используется прагма

#pragma omp barrier

В программах, написанных на языке Fortran, задание синхронизации типа barrier осуществляется с помощью следующего предложения OpenMP:

c$ omp barrier

Пример использования синхронизации типа barrier приведен во фрагменте программы (пример 3.3). В этом примере синхронизируется выполнение блока операторов <assignment>. Следующий блок <dependent work> начинает свою работу во всех параллельных потоках лишь только после того, как во всех параллельных потоках будут завершено выполнение блока <assignment>.

Отметим, что неявно синхронизация типа barrier по умолчанию устанавливается в конце циклов. Для ее отмены можно воспользоваться директивой OpenMP nowait. Вопросы применения этой директивы подробно рассматривались в предыдущей лекции в разделе, посвященном операторам циклов.

с$omp parallel
с$omp do
      do i = 1, n
         <assignment>
с$omp barrier
         <dependent work>
      enddo
с$omp end parallel

Здесь же отметим, что на языке Fortran определение директивы nowait выглядит так:

c$omp end do nowait

а на языке C/C++ - так:

#pragma omp for nowait