Шаг 37.
Параллельные алгоритмы. Средства построения параллельных программ. MPI: основные понятия и определения

    На этом шаге мы рассмотрим некоторые основные понятия и определения, используемык в MPI.

    Рассмотрим ряд понятий и определений, являющихся основополагающими для стандарта MPI.

Понятие параллельной программы

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

    Каждый процесс параллельной программы порождается на основе копии одного и того же программного кода (модель SPMP). Данный программный код, представленный в виде исполняемой программы, должен быть доступен в момент запуска параллельной программы на всех используемых процессорах. Исходный программный код для исполняемой программы разрабатывается на алгоритмических языках C или Fortran с применением той или иной реализации библиотеки MPI.

    Количество процессов и число используемых процессоров определяется в момент запуска параллельной программы средствами среды исполнения MPI-программ и в ходе вычислений не может меняться без применения специальных, но редко задействуемых средств динамического порождения процессов и управления ими, появившихся в стандарте MPI версии 2.0. Все процессы программы последовательно перенумерованы от 0 до p-1, где p есть общее количество процессов. Номер процесса именуется рангом процесса.

    Для разделения фрагментов кода между процессами обычно следующий подход: при помощи функции MPI_Comm_rank определяется ранг процесса, а затем в соответствии с рангом выделяются необходимые для процесса участки программного кода. Наличие в одной и той же программе фрагментов кода разных процессов также значительно усложняет понимание и, в целом, разработку MPI-программы. Как результат, можно рекомендовать при увеличении объема разрабатываемых программ выносить программный код разных процессов в отдельные программные модули (функции). Общая схема MPI-программы в этом случае будет иметь вид:

MPI_Comm_rank (MPI_COMM_WORLD, &ProcRank);
if ( ProcRank = = 0 ) DoProcess0();
else if ( ProcRank = = 1 ) DoProcess1();
else if ( ProcRank = = 2 ) DoProcess2();

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

MPI_Comm_rank (MPI_COMM_WORLD, &ProcRank);
if ( ProcRank = = 0 ) DoManagerProcess();
else DoWorkerProcesses();

Операции передачи данных

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

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

    Описание основных функций MPI приведено в приложении 1.

Понятие коммуникаторов

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

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

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

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

Типы данных

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

    В самом общем виде под производным типом данных в MPI можно понимать описание набора значений предусмотренного в MPI типа, причем в общем случае описываемые значения не обязательно непрерывно располагаются в памяти. Задание типа в MPI принято осуществлять при помощи карты типа (type map) в виде последовательности описаний входящих в тип значений; каждое отдельное значение описывается указанием типа и смещения адреса месторасположения от некоторого базового адреса, т.е.

TypeMap = {(type0, disp0), ..., (typen-1, dispn-1)}.

    Часть карты типа с указанием только типов значений именуется в MPI сигнатурой типа:

TypeSignature = {type0,...,typen-1}.

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

    Поясним рассмотренные понятия на следующем примере. Пусть в сообщение должны входить значения переменных:

double a; // адрес 24 
double b; // адрес 40 
int    n; // адрес 48 

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

{(MPI_DOUBLE, 0),
(MPI_DOUBLE, 16),
(MPI_INT,    24)}

    Дополнительно для производных типов данных в MPI используется следующий ряд новых понятий:

  1. Нижняя граница типа: lb(TypeMap) = minj(dispj);
  2. Верхняя граница типа: ub(TypeMap) = maxj(dispj + sizeof(typej)) + дельта;
  3. Протяженность типа: extent (TypeMap) = ub(TypeMap) - lb(TypeMap).

    Согласно определению, нижняя граница есть смещение для первого байта значений рассматриваемого типа данных. Соответственно, верхняя граница представляет собой смещение для байта, располагающегося вслед за последним элементом рассматриваемого типа данных. При этом величина смещения для верхней границы может быть округлена вверх с учетом требований выравнивания адресов. Так, одно из требований, которые налагают некоторые реализации языков C и Fortran, состоит в том, чтобы адрес элемента был кратен длине этого элемента в байтах. Например, если тип int занимает четыре байта, то адрес элемента типа int должен нацело делиться на четыре. Именно это требование и отражается в определении верхней границы типа данных MPI. Поясним данный момент на ранее рассмотренном примере набора переменных a, b и n, для которого нижняя граница равна 0, а верхняя принимает значение 32 (величина округления 6 или 4 в зависимости от размера типа int). Здесь следует отметить, что требуемое выравнивание определяется по типу первого элемента данных в карте типа.

    Следует также указать на различие понятий "протяженность" и "размер типа". Протяженность - это размер памяти в байтах, который нужно отводить для одного элемента производного типа. Размер типа данных - это число байтов, которые занимают данные (разность между адресами последнего и первого байтов данных). Различие в значениях протяженности и размера опять же в величине округления для выравнивания адресов. Так, в рассматриваемом примере размер типа равен 28, а протяженность - 32 (предполагается, что тип int занимает четыре байта).

    Для снижения сложности в MPI предусмотрено несколько различных способов конструирования производных типов:

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

    Перед использованием созданный тип должен быть объявлен, а при завершении использования - аннулирован при помощи специальных функций.

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

    На следующем шаге мы закончим изучение этого вопроса.




Предыдущий шаг Содержание Следующий шаг