Основы многопоточного и распределенного программирования

       

Библиотеки параллельного программирования


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

При создании программ с разделяемыми переменными на языке С обычно используют стандартную библиотеку Pthreads. При использовании обмена сообщениями стандартными считаются библиотеки MPI и PVM; обе они имеют широко используемые общедоступные реа­лизации, которые поддерживают как С, так и Фортран. ОрепМР является новым стандартом программирования с разделяемыми переменными, который реализован основными производите­лями быстродействующих машин. В отличие от Pthreads, ОрепМР является набором директив компилятора и подпрограмм, имеет связывание, соответствующее языку Фортран, и обеспечивает поддержку вычислений, параллельных по данным. Далее в разделе показано, как запрограммиро­вать метод итераций Якоби с помощью библиотек Pthreads и MPI, а также директив ОрепМР.

12.1.1. Учебный пример: Pthreads

Библиотека Pthreads была представлена в разделе 4.6, где рассматривались подпрограммы для использования потоков и семафоров. В разделе 5.5 были описаны и проиллюстрированы подпро­граммы для блокировки и условных переменных. Эти механизмы можно использовать и в про­грамме, реализующей метод итераций Якоби (листинг 12.1) и полученной непосредственно из программы с разделяемыми переменными (см. листинг 11.2). Как обычно в программах, исполь­зующих Pthreads, главная подпрограмма инициализирует атрибуты потока, читает аргументы из командной строки, инициализирует глобальные переменные и создает рабочие процессы. По­сле того как завершаются вычисления в рабочих процессах, главная программа выдает результаты.

Программа в листинге 12.2 содержит три функции: main, Coordinator и Worker. Пред­полагается, что выполняются все numWorkers+1 экземпляров программы. (Они запускаются с помощью команд, специфичных для конкретной версии MPI.) Каждый экземпляр начина­ется с выполнения подпрограммы main, которая инициализирует MPI и считывает аргумен­ты командной строки.
Затем в зависимости от номера (идентификатора) экземпляра из main шзывается либо управляющий процесс Coordinator, либо рабочий Worker.

Каждый процесс worker отвечает за полосу "точек. Сначала он инициализирует обе свои гетки и определяет своих соседей, left и right. Затем рабочие многократно обмениваются с соседями краями своих полос и обновляют свои точки. После numlters циклов обмена-обновления каждый рабочий отправляет строки своей полосы управляющему процессу, вы­числяет максимальную разность между парами точек на своей полосе и, наконец, вызывает MPl_Reduce, чтобы отправить mydiff управляющему процессу.

Процесс Coordinator просто собирает результаты, отправляемые рабочими процесса­ми. Сначала он получает строки окончательной сетки от всех рабочих. Затем вызывает под-

454                                                      Часть 3. Синхронное параллельное программирование

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

12.1.3. Учебный пример: ОрепМР



ОрепМР — это набор директив компилятора и библиотечных подпрограмм, используемых для выражения параллельности с разделением памяти. Прикладные программные интерфей­сы (APIs) для ОрепМР были разработаны группой, представлявшей основных производите­лей быстродействующего аппаратного и программного обеспечения. Интерфейс Фортрана был определен в конце 1997 года, интерфейс C/C++ — в конце 1998, но стандартизация обо­их продолжается. Интерфейсы поддерживают одни и те же функции, но выражаются по-разному из-за лингвистических различий между Фортраном, С и C++.

Интерфейс ОрепМР в основном образован набором директив компилятора. Программист добавляет их в последовательную программу, чтобы указать компилятору, какие части про­граммы должны выполняться параллельно, и задать точки синхронизации.


Директивы можно добавлять постепенно, поэтому ОрепМР обеспечивает распараллеливание существующего программного обеспечения. Эти свойства ОрепМР отличают ее от библиотек Pthread и MPI, которые содержат подпрограммы, вызываемые из последовательной программы и компонуе­мые с нею, и требуют от программиста вручную распределять работу между процессами.

Ниже описано и проиллюстрировано использование ОрепМР для Фортран-программ. Вначале представлена последовательная программа для метода итераций Якоби. Затем в нее добавлены директивы ОрепМР, выражающие параллельность. В конце раздела кратко описа­ны дополнительные директивы и интерфейс C/C++.

В листинге 12.3 представлен эскиз последовательной программы для метода итераций Яко­би. Ее синтаксис своеобразен, поскольку программа написана с использованием соглашений Фортрана по представлению данных с фиксированной точкой. Строки с комментариями начи­наются с буквы с в первой колонке, а декларации и операторы — с колонки 7. Дополнительные комментарии начинаются символом !. Все комментарии продолжаются до конца строки.





Последовательная программа состоит из двух подпрограмм: main и jacobi. В подпро­грамме main считываются значения п (размер сетки с границами) и maxiters (максимальное число итераций), а затем вызывается подпрограмма jacobi. Значения дан­ных хранятся в общей области памяти и, следовательно, неявно передаются из main в ja­cobi. Это позволяет jacobi распределять память для массивов grid и new динамически.

В подпрограмме jacobi реализован последовательный алгоритм, представленный выше влистинге 11.1. Основное различие между программами в листингах 12.3 и 11.1 обусловлено син­таксическим отличием псевдо-С от Фортрана. В Фортране нижняя граница каждой размерности массива равна 1, поэтому индексы внутренних точек матриц по строкам и столбцам принимают значения от 2 до п-1. Кроме того, Фортран сохраняет матрицы в памяти машины по столбцам, по­этому во вложенных циклах do сначала выполняются итерации по столбцам, а затем по строкам.



В ОрепМР используется модель выполнения "разветвление-слияние" (fork-join). Вначале существует один поток выполнения. Встретив одну из директив parallel, компилятор вставляет код, чтобы разделить один поток на несколько подпотоков. Вместе главный поток и подпотоки образуют так называемое множество рабочих потоков. Действительное количест­во рабочих потоков устанавливается компилятором (по умолчанию) или определяется поль­зователем — либо статически с помощью переменных среды (environment), либо динамиче­ски с помощью вызова подпрограммы из библиотеки ОрепМР.

Чтобы распараллелить программу с помощью ОрепМР, программист сначала определяет части программы, которые могут выполняться параллельно, например циклы, и окружает их директивами parallel и end parallel. Каждый рабочий поток выполняет этот код, обра­батывая разные подмножества в пространстве итераций (для циклов, параллельных по дан­ным) или вызывая разные подпрограммы (для программ, параллельных по задачам). Затем в программу добавляются дополнительные директивы для синхронизации потоков во время выполнения. Таким образом, компилятор отвечает за разделение потоков и распределение ра­боты между ними (в циклах), а программист должен обеспечить достаточную синхронизацию.

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





Каждая директива компилятора начинается с ! $отр. Первая определяет начало параллель­ного цикла do. Вторая дополняет первую, что обозначено добавлением символа & к ! $отр. Во второй директиве сообщается, что во всех рабочих потоках n, grid и new являются разде­ляемыми переменными, a i и j — локальными. Последняя директива указывает на конец па­раллельного цикла do и устанавливает точку неявной барьерной синхронизации,

В данном примере компилятор разделит итерации внешнего цикла do (no j) и назначит их рабочим процессам некоторым способом, зависящим от реализации.


Чтобы управлять назначением, программист может добавить предложение schedule. В ОрепМР поддержи­ваются различные виды назначения, в том числе по блокам, по полосам (циклически) и динамически (портфель задач). Каждый рабочий поток будет выполнять внутренний цикл do (no i) для назначенных ему столбцов.

В листинге 12.4 представлен один из способов распараллеливания тела подпрограммы j acobi с использованием директив ОрепМР. Основной поток разделяется на рабочие пото­ки для инициализации сеток, как было показано выше. Однако maxdif f инициализируется в основном потоке. Инициализация maxdif f перенесена, поскольку ее желательно выпол­нить в одном потоке до начала вычислений максимальной погрешности. (Вместо этого мож­но было бы использовать директиву single, обсуждаемую ниже.)

После инициализации разделяемых переменных следует директива parallel, разде­ляющая основной поток на несколько рабочих. В следующих двух предложениях указано, ка­кие переменные являются общими, а какие — локальными. Каждый рабочий выполняет главный цикл. В цикл добавлены директивы do для указания, что итерации внешних циклов, обновляющие grid и new, должны быть разделены между рабочими. Окончания этих циклов обозначены директивами end do, которые также обеспечивают неявные барьеры.

После главного цикла (который завершается одновременно всеми рабочими) использует­ся еще одна директива do, чтобы максимальная погрешность вычислялась параллельно. В этом разделе maxdif f используется в качестве переменной редукции, поэтому к директиве do добавлено предложение reduction. Семантика переменной редукции такова, что каждое обновление является неделимым (в данном примере с помощью функции max). В действи­тельности ОрепМР реализует переменную редукции, используя скрытые переменные в каж­дом рабочем потоке; значения этих переменных "сливаются" неделимым образом в одно на неявном барьере в конце распараллеленного цикла.

Программа в листинге 12.4 иллюстрирует наиболее важные директивы ОрепМР.


Библио­ тека содержит несколько дополнительных директив для распараллеливания, синхронизации и управления рабочей средой (data environment). Например, для обеспечения более полного управления синхронизацией операторов можно использовать следующие директивы.

critical    Выполнить блок операторов как критическую секцию. atomic         Выполнить один оператор неделимым образом.

Глава 12. Языки, компиляторы, библиотеки и инструментальные средства                       457

s ingle        В одном рабочем потоке выполнить блок операторов. barrier      Выполнить барьер, установленный для всех рабочих потоков.

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



458                                                      Часть 3 Синхронное параллельное программирование

Ключевое слово pragma обозначает директиву компилятора. Поскольку в С вместо циклов do для определенного количества итераций используются циклы for, эквивалентом дирек­тивы do в С является

pragma omp  for clauses.

В интерфейсе C/C++ нет директивы end. Вместо нее блоки кода заключаются в фигурные скобки, обозначающие область действия директив.


Содержание раздела