OpenMP: средства распараллеливания для многопроцессорных систем

Нельзя не отметить, что львиная часть коммерчески доступных программ для многопроцессорных систем распараллелена именно в модели общего поля памяти - сделать это как правило проще, чем в MPI, и естественнее воспринимается обычными "последовательными" программистами [3]. Кроме того, при таком подходе нет необходимости в дополнительных пересылках данных. Появление стандарта OpenMP позволит поддерживать переносимость распараллеленных программ между различными компьютерами архитектур SMP и ccNUMA.

Средства распараллеливания для систем с общим полем памяти

Анализ спецификации OpenMP предварим краткой информацией о том, какие средства распараллеливания в модели общей памяти были доступны программистам до того, как появился новый стандарт.

Прежде всего, это средства наиболее высокого уровня - автоматические распараллеливающие компиляторы. В этом случае программист формально не заботится о том, чтобы распараллелить программу и не меняет исходный последовательный код. Подобные компиляторы существуют, в частности, для систем SGI Challenge/Power Challenge [4] и Origin 200/2000 [5], HP/Convex Exemplar [6] и др. Аналогичные средства в компиляторах компьютеров Cray Research [4] обозначаются словом autotasking (дословно "автоматическое разбиение на задачи") и обычно включают языки Фортран и Cи (например, Power Fortran и Power C для систем SGI; в системе компиляторов MIPSpro 7.2 им на смену пришло новое поколение - средства APO, - Automatic Parallelization Option). Такие компиляторы могут распознавать присущий программе параллелизм и организовывать ее выполнение в виде нескольких процессов-нитей, одновременно исполняемых на разных процессорах. Более того, во многих случаях, когда компилятор распознает, например, "стандартные" операции линейной алгебры (скажем, умножение матриц), он генерирует обращения к специальным высокоэффективным (написанным на ассемблере) библиотечным подпрограммам, изначально ориентированным для работы на параллельных системах (библиотека BLAS и т.п.) [4].

Противоположный подход связан с параллелизмом на уровне задач (macrotasking в терминологии Cray Research). При данном подходе параллелизм вносится в программу полностью "вручную": пользователь самостоятельно вставляет обращения к библиотеке нитей, в том числе к примитивам, предусмотренным стандартом POSIX pthreads [7].

Естественно, что "золотая середина" лежит как раз между двумя крайностями - полностью автоматическим распараллеливанием и кодированием с явным вызовом нитей; это подход, который основывается на распараллеливании обычных последовательных программ компилятором, но "с подсказками" пользователя, помещающего в исходный текст программы директивы в виде комментариев. Эти директивы указывают компилятору на параллелизм на уровне циклов и отдельных фрагментов программы. Соответствующие средства в терминологии Cray Research называются microtasking.

Автоматическое распараллеливание весьма затруднено тем обстоятельством, что компилятору трудно (если вообще возможно) распознать взаимозависимости по данным, возможности возникновения тупиков, ситуаций типа "гонки" (race condition) и другие подобные ситуации, которые зачастую определяются поведением программы уже на этапе выполнения. Поэтому возможность получить "подсказку" от пользователя может быть очень ценна. В прикладном программном обеспечении суперкомпьютерного центра Института органической химии РАН на SMP-системе SGI Power Challenge используется именно такой подход к распараллеливанию. Набор соответствующих директив, реализованных в компиляторе Power Fortran 77 (как и в других компиляторах "семейства" Power), включает поднабор, соответствующий рекомендациям Форума параллельных вычислений PCF (Parallel Computing Forum), а также собственные директивы, такие, как С$doacross.

Подобные наборы директив достаточно распространены и поддерживаются компиляторами, предлагаемыми известной фирмой Kuck & Associates для разных аппаратных платформ: Sun, DEC, SGI и др. Новый стандарт OpenMP относится именно к такому подходу распараллеливания с применением директив - "подсказок пользователя". Директивы OpenMP во многом похожи на директивы PCF.

Однако стандарт OpenMP не ограничивается только набором директив, а специфицирует API, который, кроме директив компилятору, включает набор подпрограмм времени выполнения, а также переменные окружения. Далее мы рассмотрим основные особенности OpenMP применительно к языку Fortran. Соответствующий официальный документ можно найти на Web-cервере [8]. Аналогичные средства для языков Си/C++ планируется стандартизовать летом этого года.

Концептуальные идеи OpenMP

В рамках OpenMP стандартная последовательная модель языка Fortran расширяется параллельными конструкциями SPMD (Single Program, Multiple Data), которые наиболее близки к традиционной "последовательной" идеологии.

В OpenMP используется модель параллельного выполнения fork/join. Программа начинает выполняться как один процесс, который в ОpenMP называется главной нитью (master thread). Этот процесс выполняется последовательно до тех пор, пока он не дойдет до первой параллельной конструкции (в простейшем случае - области, заключенной между директивами PARALLEL и END PARALLEL). В этот момент создается "бригада" (team) нитей, а "бригадиром" для нее является главная нить.

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

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

В этом понятии можно усмотреть определенную аналогию с известной расширенной областью DO-цикла в языке Fortran 66. Директивы, расположенные в динамическом экстенте, называются "сиротскими" (orphanded). Они позволяют при минимальных изменениях обычных последовательных программ организовать параллельное выполнение основных частей программы [3,8]. Данное расширение в OpenMP - заметный шаг вперед по сравнению с системой директив PCF.

После завершения выполнения параллельной конструкции нити бригады синхронизируются, а выполнение продолжает только главная нить. Естественно, в программе может быть много параллельных конструкций; соответственно бригады нитей могут образовываться не один раз. OpenMP предусматривает возможность вложения параллельных конструкций (пар PARALLEL/END PARALLEL).

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

По умолчанию предполагается, что все данные имеют тип SHARED и разделяются всеми нитями бригады. Однако это правило умолчания можно изменить, указав ключ DEFAULT(PRIVATE) или вовсе отменить, если задать DEFAULT(NONE). Счетчики фортрановских DO-циклов следует делать личными (PRIVATE) для каждой нити бригады. Такие личные объекты (простые переменные, массивы и т.д.) с точки зрения их обработки эквивалентны тому, как если бы для каждой нити имелась бы декларация нового объекта того же типа. Все ссылки на исходный объект в лексическом экстенте параллельной конструкции заменяются на ссылки на этот новый личный объект.

Переменные, определенные как PRIVATE, при входе в параллельную конструкцию являются неопределенными для любой нити бригады. При использовании описателя FIRSTPRIVATE личные копии переменных инициализируются данными из исходного объекта, существующего до входа в параллельную конструкцию. Детали можно найти в описании [8].

Директивы OpenMP для языка Fortran

Общий формат директив в OpenMP и соответствующие синтаксические правила выглядят очень естественно, в "фортрановском" стиле. Поскольку директивы являются фортрановскими комментариями, они и выглядят соответствующим образом.

В соответствии с возможностями иметь "фиксированную" или свободную форму записи операторов язык Fortran [9,10], применяются разные формы записи комментариев. В фиксированной форме (признак комментария - "С", "*" или "!" в первой позиции строки) директивы OpenMP выглядят так:

С$OMP имя_директивы [ключ[[,]ключ ...]]

где квадратные скобки используются традиционным образом - для обозначения возможного присутствия или отсутствия заключенных в них ключей. Вместо символа "С" в первой позиции может стоять "*" или "!", но в позициях со второй по пятую должно быть закодировано $OMP. Шестая позиция должна содержать пробел или нуль. Для продолжения директивы на другой строке первые 5 позиций должны быть заполнены "признаком" OpenMP (например, С$OMP), а в шестой позиции должен стоять символ, отличный от пробела и нуля. В свободном формате директивы должны начинаться с контекста !$OMP [8]. Далее используется кодировка "на базе" C$OMP c фиксированной формой.

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

Рассмотрение директив OpenMP начнем с конструкции, задающей параллельную область.

C$OMP PARALLEL [ключ[[,]ключ...]] 
      Блок Fortran-операторов 
С$OMP END PARALLEL 
Параллельная область в PCF-директивах выглядит аналогично: 
C$PAR PARALLEL [ключ ключ ...] 
      Блок Fortran-операторов 
С$PAR END PARALLEL

В качестве ключей в OpenMP можно использовать спецификацию типа данных, в том числе задавая PRIVATE(список) и/или SHARED(список), где "список" cодержит имена переменных, включая массивы, разделенные запятыми. В этом списке могут быть указаны также имена COMMON-блоков, которые кодируются вместе с заключающими их символами "/". В PCF-директивах также имеется возможность специфицировать тип данных, но вместо PRIVATE используется ключевое слово LOCAL.

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

IF(cкалярное_логическое_выражение)

Если этот ключ закодирован, то соответствующая параллельная область кодов будет выполняться несколькими нитями только при условии, что "скалярное_логическое_выражение" истино. Например, указав IF(N.GT.1000), можно заставить компилятор породить такие коды, что во время выполнения они проверяли бы размерность (N) и выполнялись бы параллельно, только если эта размерность достаточно велика - больше 1000. Это позволяет избегать распараллеливания при маленьких размерностях, когда оно может оказаться невыгодным из-за большой доли накладных расходов.

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

Не останавливаясь на других ключах конструкции, задающей параллельную область, перейдем к анализу других директив. Если конструкция параллельной области приводит к созданию бригады нитей, то рассматриваемые далее конструкции разделения работы (они должны находиться внутри параллельной области) новых нитей не создают. Задача этих конструкций - распределить выполнение работ между членами бригады. Имеются два основных типа конструкций разделения работ - "пара" DO/END DO и "триада" SECTIONS/SECTION/END SECTIONS.

Рассмотрим сначала директиву DO, применяемую для распараллеливания циклов - одного из основных объектов распараллеливания.

C$OMP DO [ключ[[,]ключ...] 
      DO-цикл языка Fortran 
C$OMP END DO [NOWAIT] 

В качестве "ключей" можно указать описатели PRIVATE(список), FIRSTPRIVATE(список), SHARED(список), ключ REDUCTION, а также ключи ORDERED и SCHEDULE.

Ключ SCHEDULE используется для указания дисциплины планирования выполнения цикла нитями и имеет вид:

SCHEDULE(тип[,M])

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

STATIC-итерации будут распределяться между нитями статически по алгоритму round robin, порциями размером М итераций;

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

GUIDED-размер порции экспоненциально убывает для каждой новой подготавливаемой к выполнению порции, однако не может опуститься ниже N;

RUNTIME-тип планирования и величина M будут заданы во время выполнения переменной окружения OMP_SCHEDULE.

По умолчанию M=1. Если в OpenMP-директиве END DO задано NOWAIT, в конце цикла нити не синхронизируются.

Смысл ключа REDUCTION директивы С$OMP PARALLEL DO (этот ключ можно указывать и в ряде других директив OpenMP) можно проиллюстрировать следующим простым примером:

C$OMP PARALLEL DO REDUCTION(+: sum) 
C$OMP& PRIVATE(x) 
       do i=1,n 
       x=a(i) 
       sum=sum+f(x) 
       enddo 
C$OMP END PARALLEL DO 

где f(x) означает обращение, например, к оператору-функции. В данном примере использование ключа REDUCTION позволяет организовать параллельное выполнение цикла с вычислением суммы значений функции, хотя формально данный цикл не параллелизуется из-за возможности "одновременной" модификации SUM несколькими процессорами. В операторе REDUCTION кроме сложения/вычитания и умножения (первый операнд в скобках) можно указать логические операции, а также внутренние фортрановские функции, например MAX и MIN. Это позволяет находить "глобальное", cкажем, максимальное значение.

В OpenMP имеется также возможность использовать сокращения, позволяющие объединять инструкции PARALLEL/END PARALLEL и DO/ENDDO в пару PARALLEL DO/END PARALLEL DO.

Директива SECTIONS используется для распределения работы между нитями в "неитерационном" случае. Данная конструкция выглядит следующим образом:

C$OMP SECTIONS [ключ[[,]ключ...] 
C$OMP SECTION 
      блок Fortran-операторов 
[C$OMP SECTION 
         блок Fortran-операторов] 
... 
C$OMP END SECTIONS [NOWAIT]

где ключи, как и ранее, могут указывать на тип переменных (PRIVATE, FIRSTPRIVATE и т.д.), а также содержать ключ REDUCTION. OpenMP-конструкция SECTIONS позволяет нескольким нитям выполнять параллельно обычный линейный участок программы на Фортране, разбитый на "секции" - блоки операторов языка. Эти секции могут содержать в себе, в частности, вызовы фортрановских подпрограмм.

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

Богатые возможности предоставляют средства OpenMP и для синхронизации. Cоответствующие директивы позволяют, в частности, установить барьер (С$OMP BARRIER) или обеспечить "атомистическую" синхронизацию (С$OMP ATOMIC), предохраняющую от одновременной записи несколькими нитями в одно и то же поле оперативной памяти. Это позволяет предотвратить ситуацию гонки. Например, если запись производится в элемент массива a(index(i)), где i-управляющая переменная (счетчик) распараллеленного цикла, то нельзя заранее - на этапе трансляции - предсказать, не будет ли на этапе выполнения попытки одновременной записи разными нитями, имеющими разные i, в один и тот же элемент массива а. Чтобы избежать этого, следует сделать так, как это указано в следующем примере:

C$OMP ATOMIC
      a(index(i)) = a(index(i)) + b(i)

Без этой синхронизации было бы непонятно, с каким значением а(index(i)) произведено сложение.

Другая полезная директива, о которой стоит упомянуть - это C$OMP FLUSH. Она заставляет в соответствующей точке программы получить "согласованное" между нитями состояние оперативной памяти (при этом переменные из регистров будут записаны в память, сбросятся буферы записи и т.д.).

Наконец, несколько слов о директиве ORDERED. Она заставляет коды Fortran, заключенные внутри пары ORDERED/END ORDERED, выполняться в "естественном" порядке (в той, в которой итерации цикла выполняются при нормальном последовательном выполнении). Эта пара директив может присутствовать только в динамическом экстенте директивы DO (или PARALLEL DO), в которой указан ключ ORDERED. Такие директивы могут использоваться для организации печати в нормальной - скажем, по возрастанию счетчика цикла- последовательности.

Подпрограммы времени выполнения и переменные окружения

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

   subroutine OMP_SET_NUM_THREADS(N) 
устанавливает число нитей, равное N. 
   integer function OMP_GET_NUM_THREADS() 
возвращает число нитей в бригаде. 
   integer function OMP_GET_THREAD_NUM() 

возвращает номер "текущей" нити (из которой произошел вызов функции) в бригаде. Имеется также 5 подпрограмм, обеспечивающих работу с замками.

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

С$    call OMP_SET_NUM_THREADS(M)

можно обеспечить компиляцию этого обращения, устанавливающего число нитей бригады, равное М, только при указании соответствующего флага компилятора (-mp для компиляторов компании SGI). Кроме того, в приложении к описанию стандарта приведены тексты подпрограмм-"пустышек", которыми можно "забить" обращения к реальным подпрограммам OpenMP.

В случае, если в OMP-директиве DO или PARALLEL DO был указан тип планирования RUNTIME, то фактическое определение типа планирования откладывается до периода времени выполнения. В этом случае, указав перед выполнением файла

%setenv OMP_SCHEDULE "DYNAMIC" 
можно установить динамический режим планирования выполнения нитей, а указав 
%setenv OMP_SCHEDULE "GUIDED,10" 
- задать режим GUIDED с минимальной порцией в 10 итераций на нить. 

Другой важнейшей переменной окружения является OMP_NUM_THREADS, задающая число нитей в бригаде.

Что день грядущий нам готовит

Партнерами разработки стандарта OpenMP выступили наиболее крупные и известные в области параллельных вычислений производители: IBM, HP, SGI/Cray Research, DEC, Intel, Kuck & Associates, Portland Group, Absoft, Edinburgh Portable Compilers и др. В разработке также участвовали специалисты таких известных организаций, как NAG (Numerical Algorithm Group), американского энергетического департамента (участники знаменитой программы ASCI, Oxford Molecular Group и др. Результат их совместных усилий следует всемерно приветствовать, ибо до сих пор каждая фирма-производитель суперкомпьютеров, имеющих общее поле памяти, предлагала собственные средства распараллеливания. Пока же на ниве поддержки альтернативных стандартов особенно отличилась SGI: кроме директив собственной разработки она поддерживает директивы Cray Research, PCF, директивы KAP (фирмы Kuck & Associates) и ряд других. Хотя справедливости ради следует отметить, что соответствующие директивы очень часто оказываются довольно близки, по крайней мере семантически.

Другим важным моментом является то, что OpenMP - это стандарт не только для различных диалектов Unix, но и для NT. Первая известная автору реализация OpenMP выполнена компанией SGI в рамках системы компиляторов MIPSpro 7.2.1.

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

Поэтому на повестку дня встает вопрос сопоставления MPI и OpenMP. Он имеет смысл, конечно, только для систем с архитектурой SMP или ccNUMA. Несомненно, что OpenMP дает более простую парадигму распараллеливания, формулируемую на "языке" более высокого уровня. Остается вопрос о степени масштабируемости. Единственные известные автору данные были представлены на семинаре SGI [11], где было указано на близкие уровни масштабируемости в модели общего поля памяти и в MPI для ссNUMA-сервера Origin 2000 на тестах LU NAS Parallel Benchmark (классы O, A, B).

Работа выполнена при поддержке РФФИ (проект 98-07-90290).

Литература