Что такое OpenMP

   Что такое OpenMP? 

   OpenMP (Open Multi-Processing) - это набор директив компилятора, библиотечных процедур и переменных окружения, которые предназначены для программирования многопоточных приложений на многопроцессорных системах с общей памятью (SMP-системах).

   Первый  стандарт OpenMP был разработан в 1997 г. как API, ориентированный на написание  легко переносимых многопоточных  приложений. Сначала он был основан  на языке Fortran, но позднее включил  в себя и языки Си и Си++.

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

   Разработчики  OpenMP хотели предоставить простой способ создания потоков в приложениях, не требуя от программиста знаний о создании, синхронизации и уничтожении потоков, а также необходимости определения, сколько потоков следует создать. Для этого разработчики OpenMP создали независимый от платформы набор прагм, директив, вызовов функций и переменных среды, которые явным образом указывают компилятору, как и где именно следует вставить потоки в приложение. Большинство циклов можно распараллелить, вставив всего одну прагму непосредственно перед циклом. Более того, оставив исполнение рутинных функций компилятору и OpenMP, вы можете больше времени уделить определению того, какие циклы следует распараллелить, и как наилучшим образом изменить структуру алгоритмов для достижения максимальной производительности. Максимальная производительность OpenMP реализуется при использовании этого инструмента для распараллеливания "горячих точек", - наиболее трудоемких циклов в приложении.

   Разработку  спецификации OpenMP ведут несколько  крупных производителей вычислительной техники и программного обеспечения, чья работа регулируется некоммерческой организацией "OpenMP Architecture Review Board" (ARB). 

   Прагмы OpenMP 

   Спецификация OpenMP определяет набор прагм. Прагма - это директива компилятора, указывающая, как обрабатывать код, следующий за прагмой. Наиболее существенной является прагма #pragma omp parallel, определяющая область параллельности.

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

   Число потоков в группе, выполняющихся  в области параллельности, можно  контролировать несколькими способами. Один из них -- использование переменной среды OMP_NUM_THREADS. Другой способ -- вызов процедуры omp_set_num_threads(). Еще один способ -- использование выражения num_threads в сочетании с прагмой parallel.

   В OpenMP поддерживаются две основных конструкции  разделения работы для указания того, что работу в области параллельности следует разделить между потоками группы. Эти конструкции разделения работы - циклы и разделы. Прагма #pragma omp forиспользуется для циклов, а прагма #pragma omp sections используется для разделов -- блоков кода, которые могут быть выполнены параллельно.

   Прагма #pragma omp barrier дает всем потокам указание ожидать друг друга перед тем, как они продолжат выполнение за барьером. Как было отмечено выше, в конце области параллельности имеется неявный барьер. Прагма #pragma omp master дает компилятору указание о том, что следующий блок кода должен выполняться только главным потоком. Прагма #pragma omp singleпоказывает, что следующий блок кода должен выполняться только одним потоком группы; этот поток не обязательно должен быть главным. Прагма #pragma omp critical может использоваться для защиты блока кода, который должен выполняться одновременно только одним потоком. Конечно, все эти прагмы имеют смысл только в контексте прагмы parallel (области параллельности). 

   Процедуры OpenMP 

   OpenMP предоставляет ряд процедур, которые  можно использовать для получения  сведений о потоках в программе. В их число входят omp_get_num_threads(), omp_set_num_threads(), omp_get_max_threads(), omp_in_parallel() и другие. Кроме того, OpenMP предоставляет ряд процедур блокировки, которые можно использовать для синхронизации потоков. 

   Переменные среды OpenMP 

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

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

   Помимо  переменных среды, предусмотренных  стандартом OpenMP, компиляторы Sun Studio предоставляют  дополнительный набор специфических переменных среды, обеспечивающий дополнительные возможности управления средой времени выполнения. Эти переменные описаны в Руководстве пользователя по OpenMP. 

   Технология OpenMP 

   Стандарт  OpenMP создавался для упрощения разработки параллельных программ для вычислительных систем с общей памятью, а так же для распараллеливания уже существующих последовательных программ. Стандартом определены специальные комментарии (команды препроцессору для C/C++) – директивы компилятору, непосредственно управляющие параллелизмом программы, вспомогательные функции, позволяющие создавать алгоритмы, ориентированные на параллельное выполнение, и переменные окружения, управляющие процессом выполнения параллельных областей. 

Пример

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

   Число потоков в группе, выполняющихся  параллельно, можно контролировать несколькими способами. Один из них - использование переменной окружения OMP_NUM_THREADS. Другой способ - вызов процедуры omp_set_num_threads(). Еще один способ - использование выражения num_threads в сочетании с директивой parallel.

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

   Рисунок 1: Пример выполнения параллельного участка 

   В OpenMP память подразделяется на 2 вида: общая память и локальная память.

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

   Локальная память доступна только одной нити. 
 
 
 

   Ошибки, возникающие при  использовании OpenMP 

   В 2004-2005 годах в University of Kassel(Германия) проводилось исследование, целью которого было выявление наиболее часто совершаемых ошибок, обусловленных некорректным использованием функций и директив OpenMP, и приводящих к неверному выполнению программы. Эксперимент проводился на студентах этого университета, которые должны были написать некоторую программу с использованием OpenMP версии 2.5 или более ранней. Большинство испытуемых ранее не имели опыта работы с OpenMP, что позволило выявить ошибки, допускаемые начинающими программистами. В результате были обнаружены следующие ошибки [3]:

1. Незащищенный доступ к общим переменным.

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

   - все нити только читают переменную, тогда ошибки нет, т.к. значение  переменной в любой момент  времени остается неизменным.

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

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

2. Использование механизма замков без директивы flush.

   Этот  пункт является ошибкой только для  ранних версий OpenMP(до версии 2.5).

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

3. Чтение общих переменных без директивы flush.

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

4. Использование переменных как приватных, хотя таковыми они не являются.

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

5. Использование предложения ordered без конструкции ordered.

   Предполагается, что если в директиве распараллеливания  цикла указано условие ordered, то внутри этого цикла должна располагаться область, помеченная как ordered. Это означает, что указанная область должна быть выполнена в том же порядке (по итерациям цикла), что и в последовательной программе. Отсутствие такой области в теле цикла, при наличии условия ordered считается ошибкой.

6. Переменная распараллеливаемого цикла объявлена как общая.

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

7. Отсутствие слова for в директиве parallel for

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

8. Изменение числа нитей в параллельной области программы.

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

9. Снятие замка нитью, которая его не устанавливала.

   Замок может быть снят только нитью, установившей его.

10. Изменение переменной распараллеленного цикла внутри него.

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

   Из перечисленных ошибок наиболее частыми и трудно отслеживаемыми являются ошибки 1 и 4. Но поскольку отличить их друг от друга во время выполнения программы в большинстве случаев невозможно, то следует их объединить в одну группу. Назовем ее ошибками общей переменной.

   Приведенный список ошибок не является полным и  поэтому следует сказать еще  о паре ошибок, которые могут возникнуть в OpenMP-программе:

• Ошибка инициализации. Суть этой ошибки заключается в том, что в программе может возникнуть ситуация, когда происходит чтение переменной, которой еще не присвоили начальное значение. Технология OpenMP только увеличивает число возможных причин этой ошибки. Дело в том, что приватные переменные могут быть определены по-разному. Обычная приватная переменная (private) при входе в область, где она, таким образом, определена, не имеет начального значения. Однако, если сделать ее firstprivate, то кроме того, что она становится приватной, так ей еще будет присвоено значение, которое переменная имела до данной области. В OpenMP существуют разные параметры директив, которые аналогичным образом определяют передачу значений от исходных приватным переменным и от приватных исходным переменным. Поэтому, если программист неправильно задал тип приватной переменной, то, скорее всего, проявится именно эта ошибка.
• Ошибка взаимной блокировки (deadlock). Это классическая ошибка, которая возникает, когда несколько нитей сначала захватывают в собственное пользование некоторые ресурсы, а затем пытаются захватить ресурсы, захваченные другими нитями. В результате все нити блокируются и программа виснет. Простейшим примером взаимной блокировки в OpenMP является случай, когда в одной критической секции находится другая, но с таким же именем. В этом случае нить, когда дойдет до второй критической секции, заблокирует сама себя. Этот вид ошибок искать не очень сложно, т.к. найти место зависания программы обычно не составляет особого труда.

   Отладка параллельных программ 

   Процесс отладки параллельных программ можно  условно поделить на традиционную и  автоматическую.

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

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

   С чего начать 

   Параллелизовать программу можно несколькими  способами. Во-первых, следует определить, нужна ли параллелизация. Некоторые  алгоритмы не годятся для параллелизации. Если создается новый проект, можно  выбрать алгоритм, который может  быть параллелизован. До начала попыток параллелизации очень важно убедиться, что код выполняется правильно в последовательном режиме. Определите временные характеристики при последовательном выполении, по которым можно будет принять решение о целесообразности параллелизации.

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

   Когда программа готова для параллелизации, можно применить ряд функций  и средств Sun Studio, которые помогут достигнуть цели. Они кратко описаны ниже. 

   Автоматическая  параллелизация 

   Можно попробовать применить ключ автоматической параллелизации компилятора (-xautopar). Доверив  параллелизацию компилятору, программист  может параллелизовать программу без каких-либо усилий со своей стороны. Кроме того, автоматический параллелизатор может помочь определить фрагменты кода, которые можно параллелизовать с помощью прагм OpenMP, и особенности, которые могут помешать параллелизации (например, зависимости между повторениями тела цикла). Комментарии компилятора можно просмотреть, скомпилировав программу с ключом -g и использовав служебную программу er_src(1) из состава Sun Studio, например, следующим образом:

   % cc -g -xautopar -c source.c

   % er_src source.o 

   Автоопределение области действия 

   Одним из наиболее распространенных типов  ошибок в программировании с использованием OpenMP являются ошибки в определении  области действия, когда область  действия переменной указывается неверно, например, переменная определяется как общая (частная), в то время как ее нужно определить как частную (общую). Функция автоопределения области действия в компиляторах Sun Studio освобождает программиста от задачи определения областей действия переменных. Поддерживаются два расширения OpenMP: оператор __auto и оператор default(__auto). Подробности приведены в Руководстве пользователя по OpenMP. 

   Отладчик dbx 

   Отладчик Sun Studio, dbx, поддерживает работу с потоками и может использоваться для отладки  программы, использующей OpenMP. Для отладки программы, использующей OpenMP, следует, во-первых, скомпилировать программу без какой-либо оптимизации, использовав ключи компилятора -xopenmp=noopt -g, затем запустить dbx для отладки полученного исполнимого модуля. С помощью dbx можно устанавливать точки останова внутри области параллельности и выполнять код в области параллельности в пошаговом режиме, проверять переменные, являющиеся частными для потока, и так далее. 

   Анализатор  производительности 

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

   Положительные стороны 

• Поэтапное (инкрементальное) распараллеливание
• Можно распараллеливать последовательные программы поэтапно, не меняя их структуру
• Единственность разрабатываемого кода
• Нет необходимости поддерживать последовательный и параллельный вариант программы, поскольку директивы игнорируются обычными компиляторами (в общем случае)
• Эффективность
• Учет и использование возможностей систем с общей памятью
• Стандартизованность (переносимость), поддержка в наиболее распространенных языках (C/C++, Fortran) и платформах (Windows, Unix)

   Ключевые  элементы 

   Ключевыми элементами OpenMP являются: 

• конструкции для создания потоков (директива parallel),
• конструкции распределения работы между потоками (директивы DO/for и section),
• конструкции для управления работой с данными (выражения shared и private),
• конструкции для синхронизации потоков (директивы critical, atomic и barrier),
• процедуры библиотеки поддержки времени выполнения (например, omp_get_thread_num),
• переменные окружения (например, OMP_NUM_THREADS).

   Примеры программ 

   Ниже  приведены примеры программ с  использованием директив OpenMP: 

   1. Fortran

   В этой программе на языке Fortran создается заранее неизвестное число потоков (оно определяется переменной окружения OMP_NUM_THREADS перед запуском программы), каждый из которых выводит приветствие вместе со своим номером. Главный поток (имеющий номер 0) также выводит общее число потоков, но только после того, как все они «пройдут» директиву BARRIER.

         PROGRAM HELLO

         INTEGER ID, NTHRDS

         INTEGER OMP_GET_THREAD_NUM, OMP_GET_NUM_THREADS

   C$OMP PARALLEL PRIVATE(ID)

         ID = OMP_GET_THREAD_NUM()

         PRINT *, 'HELLO WORLD FROM THREAD', ID

   C$OMP BARRIER

         IF ( ID .EQ. 0 ) THEN

           NTHRDS = OMP_GET_NUM_THREADS()

           PRINT *, 'THERE ARE', NTHRDS, 'THREADS'

         END IF

   C$OMP END PARALLEL

         END 

   2. Си

   В этой программе два массива (a и b) складываются параллельно десятью потоками.

   #include <stdio.h>

   #include <omp.h>

   #define N 100

   int main(int argc, char *argv[])

   {

     float a[N], b[N], c[N];

     int i;

     omp_set_dynamic(0);      // запретить библиотеке openmp менять число потоков во время исполнения

     omp_set_num_threads(10); // установить число потоков в 10

     // инициализируем массивы

     for (i = 0; i < N; i++)

     {

         a[i] = i * 1.0;

         b[i] = i * 2.0;

     }

     // вычисляем сумму массивов

   #pragma omp parallel shared(a, b, c) private(i)

     {

   #pragma omp for

       for (i = 0; i < N; i++)

         c[i] = a[i] + b[i];

     }

     printf ("%f\n", c[10]);

     return 0;

   } 

   Существующие  реализации 

   OpenMP поддерживается многими современными  компиляторами.

• Компиляторы Sun Studio поддерживают официальную спецификацию — OpenMP 2.5 — с улучшенной производительностью под ОС Solaris; поддержка Linuxзапланирована на следующий релиз.
• Visual C++ 2005 поддерживает OpenMP в редакциях Professional и Team System.
• GCC 4.2 поддерживает OpenMP, а некоторые дистрибутивы (такие как Fedora Core 5 gcc) включили поддержку в свои версии GCC 4.1.
• Intel C++ Compiler, включая версию Intel Cluster OpenMP для программирования в системах с распределённой памятью.
• IBM XL compiler
• PGI (Portland group)
• Pathscale
• HP
• PascalABC.NET