Курс лекций "Параллельная обработка данных"

Воеводин В.В., д.ф.-м.н., зам. директора НИВЦ МГУ
Сайт PARALLEL.RU

Содержание

Лекция 5. Технологии параллельного программирования. Message Passing Interface (MPI)

План лекции:

• MPI. Терминология и обозначения
• Общие процедуры MPI
• Прием/передача сообщений между отдельными процессами
• Объединение запросов на взаимодействие
• Совмещенные прием/передача сообщений
• Коллективные взаимодействия процессов
• Синхронизация процессов
• Работа с группами процессов
• Предопределенные константы
• Примеры MPI-программ

MPI. Терминология и обозначения

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

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

Атрибуты сообщения - номер процесса-отправителя, номер процесса-получателя и идентификатор сообщения. Для них заведена структура MPI_Status, содержащая три поля: MPI_Source (номер процесса отправителя), MPI_Tag (идентификатор сообщения), MPI_Error (код ошибки); могут быть и добавочные поля.

Идентификатор сообщения (msgtag) - атрибут сообщения, являющийся целым неотрицательным числом, лежащим в диапазоне от 0 до 32767.
Процессы объединяются в группы, могут быть вложенные группы. Внутри группы все процессы перенумерованы. С каждой группой ассоциирован свой коммуникатор. Поэтому при осуществлении пересылки необходимо указать идентификатор группы, внутри которой производится эта пересылка. Все процессы содержатся в группе с предопределенным идентификатором MPI_COMM_WORLD.

При описании процедур MPI будем пользоваться словом OUT для обозначения "выходных" параметров, т.е. таких параметров, через которые процедура возвращает результаты.

Общие процедуры MPI

int MPI_Init( int* argc, char*** argv)

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

Возвращает: в случае успешного выполнения - MPI_SUCCESS, иначе - код ошибки. (То же самое возвращают и все остальные функции, рассматриваемые в данном руководстве.)

int MPI_Finalize( void )

MPI_Finalize - завершение параллельной части приложения. Все последующие обращения к любым MPI-процедурам, в том числе к MPI_Init, запрещены. К моменту вызова MPI_Finalize некоторым процессом все действия, требующие его участия в обмене сообщениями, должны быть завершены.
Сложный тип аргументов MPI_Init предусмотрен для того, чтобы передавать всем процессам аргументы main:

int main(int argc, char** argv)
{
      MPI_Init(&argc, &argv);
          ...
      MPI_Finalize();
}

int MPI_Comm_size( MPI_Comm comm, int* size)

Определение общего числа параллельных процессов в группе comm.

• comm - идентификатор группы
• OUT size - размер группы

int MPI_Comm_rank( MPI_Comm comm, int* rank)

Определение номера процесса в группе comm. Значение, возвращаемое по адресу &rank, лежит в диапазоне от 0 до size_of_group-1.

• comm - идентификатор группы
• OUT rank - номер вызывающего процесса в группе comm

double MPI_Wtime(void)

Функция возвращает астрономическое время в секундах (вещественное число), прошедшее с некоторого момента в прошлом. Гарантируется, что этот момент не будет изменен за время существования процесса.

Прием/передача сообщений между отдельными процессами

Прием/передача сообщений с блокировкой

int MPI_Send(void* buf, int count, MPI_Datatype datatype, int dest, int msgtag, MPI_Comm comm)

• buf - адрес начала буфера посылки сообщения
• count - число передаваемых элементов в сообщении
• datatype - тип передаваемых элементов
• dest - номер процесса-получателя
• msgtag - идентификатор сообщения
• comm - идентификатор группы

Блокирующая посылка сообщения с идентификатором msgtag, состоящего из count элементов типа datatype, процессу с номером dest. Все элементы сообщения расположены подряд в буфере buf. Значение count может быть нулем. Тип передаваемых элементов datatype должен указываться с помощью предопределенных констант типа. Разрешается передавать сообщение самому себе.

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

int MPI_Recv(void* buf, int count, MPI_Datatype datatype, int source, int msgtag, MPI_Comm comm, MPI_Status *status)

• OUT buf - адрес начала буфера приема сообщения
• count - максимальное число элементов в принимаемом сообщении
• datatype - тип элементов принимаемого сообщения
• source - номер процесса-отправителя
• msgtag - идентификатор принимаемого сообщения
• comm - идентификатор группы
• OUT status - параметры принятого сообщения

Прием сообщения с идентификатором msgtag от процесса source с блокировкой. Число элементов в принимаемом сообщении не должно превосходить значения count. Если число принятых элементов меньше значения count, то гарантируется, что в буфере buf изменятся только элементы, соответствующие элементам принятого сообщения. Если нужно узнать точное число элементов в сообщении, то можно воспользоваться подпрограммой MPI_Probe.

Блокировка гарантирует, что после возврата из подпрограммы все элементы сообщения приняты и расположены в буфере buf.

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

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

int MPI_Get_count( MPI_Status *status, MPI_Datatype datatype, int *count)

• status - параметры принятого сообщения
• datatype - тип элементов принятого сообщения
• OUT count - число элементов сообщения

По значению параметра status данная подпрограмма определяет число уже принятых (после обращения к MPI_Recv) или принимаемых (после обращения к MPI_Probe или MPI_Iprobe) элементов сообщения типа datatype.

int MPI_Probe( int source, int msgtag, MPI_Comm comm, MPI_Status *status)

• source - номер процесса-отправителя или MPI_ANY_SOURCE
• msgtag - идентификатор ожидаемого сообщения или MPI_ANY_TAG
• comm - идентификатор группы
  
• OUT status - параметры обнаруженного сообщения
  

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

Прием/передача сообщений без блокировки

int MPI_Isend(void *buf, int count, MPI_Datatype datatype, int dest, int msgtag, MPI_Comm comm, MPI_Request *request)

• buf - адрес начала буфера посылки сообщения
• count - число передаваемых элементов в сообщении
• datatype - тип передаваемых элементов
• dest - номер процесса-получателя
• msgtag - идентификатор сообщения
• comm - идентификатор группы
• OUT request - идентификатор асинхронной передачи

Передача сообщения, аналогичная MPI_Send, однако возврат из подпрограммы происходит сразу после инициализации процесса передачи без ожидания обработки всего сообщения, находящегося в буфере buf. Это означает, что нельзя повторно использовать данный буфер для других целей без получения дополнительной информации о завершении данной посылки. Окончание процесса передачи (т.е. того момента, когда можно переиспользовать буфер buf без опасения испортить передаваемое сообщение) можно определить с помощью параметра request и процедур MPI_Wait и MPI_Test.
Сообщение, отправленное любой из процедур MPI_Send и MPI_Isend, может быть принято любой из процедур MPI_Recv и MPI_Irecv.

int MPI_Irecv(void *buf, int count, MPI_Datatype datatype, int source, int msgtag, MPI_Comm comm, MPI_Request *request)

• OUT buf - адрес начала буфера приема сообщения
• count - максимальное число элементов в принимаемом сообщении
• datatype - тип элементов принимаемого сообщения
• source - номер процесса-отправителя
• msgtag - идентификатор принимаемого сообщения
• comm - идентификатор группы
• OUT request - идентификатор асинхронного приема сообщения

Прием сообщения, аналогичный MPI_Recv, однако возврат из подпрограммы происходит сразу после инициализации процесса приема без ожидания получения сообщения в буфере buf. Окончание процесса приема можно определить с помощью параметра request и процедур MPI_Wait и MPI_Test.

int MPI_Wait( MPI_Request *request, MPI_Status *status)

• request - идентификатор асинхронного приема или передачи
• OUT status - параметры сообщения

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

int MPI_Waitall( int count, MPI_Request *requests, MPI_Status *statuses)

• count - число идентификаторов
• requests - массив идентификаторов асинхронного приема или передачи
• OUT statuses - параметры сообщений

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

int MPI_Waitany( int count, MPI_Request *requests, int *index, MPI_Status *status)

• count - число идентификаторов
• requests - массив идентификаторов асинхронного приема или передачи
• OUT index - номер завершенной операции обмена
• OUT status - параметры сообщений

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

int MPI_Waitsome( int incount, MPI_Request *requests, int *outcount, int *indexes, MPI_Status *statuses)

• incount - число идентификаторов
• requests - массив идентификаторов асинхронного приема или передачи
• OUT outcount - число идентификаторов завершившихся операций обмена
• OUT indexes - массив номеров завершившихся операции обмена
• OUT statuses - параметры завершившихся сообщений

Выполнение процесса блокируется до тех пор, пока по крайней мере одна из операций обмена, ассоциированных с указанными идентификаторами, не будет завершена. Параметр outcount содержит число завершенных операций, а первые outcount элементов массива indexes содержат номера элементов массива requests с их идентификаторами. Первые outcount элементов массива statuses содержат параметры завершенных операций.

int MPI_Test( MPI_Request *request, int *flag, MPI_Status *status)

• request - идентификатор асинхронного приема или передачи
• OUT flag - признак завершенности операции обмена
• OUT status - параметры сообщения

Проверка завершенности асинхронных процедур MPI_Isend или MPI_Irecv, ассоциированных с идентификатором request. В параметре flag возвращает значение 1, если соответствующая операция завершена, и значение 0 в противном случае. Если завершена процедура приема, то атрибуты и длину полученного сообщения можно определить обычным образом с помощью параметра status.

int MPI_Testall( int count, MPI_Request *requests, int *flag, MPI_Status *statuses)

• count - число идентификаторов
  
• requests - массив идентификаторов асинхронного приема или передачи
• OUT flag - признак завершенности операций обмена
  
• OUT statuses - параметры сообщений
  

В параметре flag возвращает значение 1, если все операции, ассоциированные с указанными идентификаторами, завершены (с указанием параметров сообщений в массиве statuses). В противном случае возвращается 0, а элементы массива statuses неопределены.

int MPI_Testany(int count, MPI_Request *requests, int *index, int *flag, MPI_Status *status)

• count - число идентификаторов
• requests - массив идентификаторов асинхронного приема или передачи
• OUT index - номер завершенной операции обмена
• OUT flag - признак завершенности операции обмена
• OUT status - параметры сообщения

Если к моменту вызова подпрограммы хотя бы одна из операций обмена завершилась, то в параметре flag возвращается значение 1, index содержит номер соответствующего элемента в массиве requests, а status - параметры сообщения.

int MPI_Testsome( int incount, MPI_Request *requests, int *outcount, int *indexes, MPI_Status *statuses)

• incount - число идентификаторов
• requests - массив идентификаторов асинхронного приема или передачи
• OUT outcount - число идентификаторов завершившихся операций обмена
• OUT indexes - массив номеров завершившихся операции обмена
• OUT statuses - параметры завершившихся операций
  

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

int MPI_Iprobe( int source, int msgtag, MPI_Comm comm, int *flag, MPI_Status *status)

• source - номер процесса-отправителя или MPI_ANY_SOURCE
• msgtag - идентификатор ожидаемого сообщения или MPI_ANY_TAG
• comm - идентификатор группы
• OUT flag - признак завершенности операции обмена
• OUT status - параметры обнаруженного сообщения

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

Объединение запросов на взаимодействие

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

int MPI_Send_init( void *buf, int count, MPI_Datatype datatype, int dest, int msgtag, MPI_Comm comm, MPI_Request *request)

• buf - адрес начала буфера посылки сообщения
• count - число передаваемых элементов в сообщении
• datatype - тип передаваемых элементов
• dest - номер процесса-получателя
• msgtag - идентификатор сообщения
• comm - идентификатор группы
• OUT request - идентификатор асинхронной передачи

Формирование запроса на выполнение пересылки данных. Все параметры точно такие же, как и у подпрограммы MPI_Isend, однако в отличие от нее пересылка не начинается до вызова подпрограммы MPI_Startall.

int MPI_Recv_init( void *buf, int count, MPI_Datatype datatype, int source, int msgtag, MPI_Comm comm, MPI_Request *request)

• OUT buf - адрес начала буфера приема сообщения
• count - число принимаемых элементов в сообщении
• datatype - тип принимаемых элементов
• source - номер процесса-отправителя
• msgtag - идентификатор сообщения
• comm - идентификатор группы
• OUT request - идентификатор асинхронного приема

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

MPI_Startall( int count, MPI_Request *requests)

• count - число запросов на взаимодействие
• OUT requests - массив идентификаторов приема/передачи

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

Совмещенные прием/передача сообщений

int MPI_Sendrecv( void *sbuf, int scount, MPI_Datatype stype, int dest, int stag, void *rbuf, int rcount, MPI_Datatype rtype, int source, MPI_Datatype rtag, MPI_Comm comm, MPI_Status *status)

• sbuf - адрес начала буфера посылки сообщения
• scount - число передаваемых элементов в сообщении
• stype - тип передаваемых элементов
• dest - номер процесса-получателя
• stag - идентификатор посылаемого сообщения
• OUT rbuf - адрес начала буфера приема сообщения
• rcount - число принимаемых элементов сообщения
• rtype - тип принимаемых элементов
• source - номер процесса-отправителя
• rtag - идентификатор принимаемого сообщения
• comm - идентификатор группы
• OUT status - параметры принятого сообщения

Данная операция объединяет в едином запросе посылку и прием сообщений. Принимающий и отправляющий процессы могут являться одним и тем же процессом. Сообщение, отправленное операцией MPI_Sendrecv, может быть принято обычным образом, и точно также операция MPI_Sendrecv может принять сообщение, отправленное обычной операцией MPI_Send. Буфера приема и посылки обязательно должны быть различными.

Коллективные взаимодействия процессов

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

int MPI_Bcast(void *buf, int count, MPI_Datatype datatype, int source, MPI_Comm comm)

• OUT buf - адрес начала буфера посылки сообщения
• count - число передаваемых элементов в сообщении
• datatype - тип передаваемых элементов
• source - номер рассылающего процесса
• comm - идентификатор группы

Рассылка сообщения от процесса source всем процессам, включая рассылающий процесс. При возврате из процедуры содержимое буфера buf процесса source будет скопировано в локальный буфер процесса. Значения параметров count, datatype и source должны быть одинаковыми у всех процессов.

int MPI_Gather( void *sbuf, int scount, MPI_Datatype stype, void *rbuf, int rcount, MPI_Datatype rtype, int dest, MPI_Comm comm)

• sbuf - адрес начала буфера посылки
• scount - число элементов в посылаемом сообщении
• stype - тип элементов отсылаемого сообщения
• OUT rbuf - адрес начала буфера сборки данных
• rcount - число элементов в принимаемом сообщении
• rtype - тип элементов принимаемого сообщения
• dest - номер процесса, на котором происходит сборка данных
• comm - идентификатор группы
• OUT ierror - код ошибки

Сборка данных со всех процессов в буфере rbuf процесса dest. Каждый процесс, включая dest, посылает содержимое своего буфера sbuf процессу dest. Собирающий процесс сохраняет данные в буфере rbuf, располагая их в порядке возрастания номеров процессов. Параметр rbuf имеет значение только на собирающем процессе и на остальных игнорируется, значения параметров count, datatype и dest должны быть одинаковыми у всех процессов.

int MPI_Allreduce( void *sbuf, void *rbuf, int count, MPI_Datatype datatype, MPI_Op op, MPI_Comm comm)

• sbuf - адрес начала буфера для аргументов
• OUT rbuf - адрес начала буфера для результата
• count - число аргументов у каждого процесса
• datatype - тип аргументов
• op - идентификатор глобальной операции
• comm - идентификатор группы

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

int MPI_Reduce( void *sbuf, void *rbuf, int count, MPI_Datatype datatype, MPI_Op op, int root, MPI_Comm comm)

• sbuf - адрес начала буфера для аргументов
• OUT rbuf - адрес начала буфера для результата
• count - число аргументов у каждого процесса
• datatype - тип аргументов
• op - идентификатор глобальной операции
• root - процесс-получатель результата
• comm - идентификатор группы

Функция аналогична предыдущей, но результат будет записан в буфер rbuf только у процесса root.

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

int MPI_Barrier( MPI_Comm comm)

• comm - идентификатор группы

Блокирует работу процессов, вызвавших данную процедуру, до тех пор, пока все оставшиеся процессы группы comm также не выполнят эту процедуру.

Работа с группами процессов

int MPI_Comm_split( MPI_Comm comm, int color, int key, MPI_Comm *newcomm)

• comm - идентификатор группы
• color - признак разделения на группы
• key - параметр, определяющий нумерацию в новых группах
• OUT newcomm - идентификатор новой группы

Данная процедура разбивает все множество процессов, входящих в группу comm, на непересекающиеся подгруппы - одну подгруппу на каждое значение параметра color (неотрицательное число). Каждая новая подгруппа содержит все процессы одного цвета. Если в качестве color указано значение MPI_UNDEFINED, то в newcomm будет возвращено значение MPI_COMM_NULL.

int MPI_Comm_free( MPI_Comm comm)

• OUT comm - идентификатор группы

Уничтожает группу, ассоциированную с идентификатором comm, который после возвращения устанавливается в MPI_COMM_NULL.

Предопределенные константы

Предопределенные константы типа элементов сообщений

Константы MPI	Тип в C
MPI_CHAR	signed char
MPI_SHORT	signed int
MPI_INT	signed int
MPI_LONG	signed long int
MPI_UNSIGNED_CHAR	unsigned char
MPI_UNSIGNED_SHORT	unsigned int
MPI_UNSIGNED	unsigned int
MPI_UNSIGNED_LONG	unsigned long int
MPI_FLOAT	float
MPI_DOUBLE	double
MPI_LONG_DOUBLE	long double

Другие предопределенные типы

MPI_Status - структура; атрибуты сообщений; содержит три обязательных поля:

• MPI_Source (номер процесса отправителя)
• MPI_Tag (идентификатор сообщения)
• MPI_Error (код ошибки)

MPI_Request - системный тип; идентификатор операции посылки-приема сообщения

MPI_Comm - системный тип; идентификатор группы (коммуникатора)

• MPI_COMM_WORLD - зарезервированный идентификатор группы, состоящей их всех процессов приложения

Константы-пустышки

• MPI_COMM_NULL
• MPI_DATATYPE_NULL
• MPI_REQUEST_NULL

Константа неопределенного значения

• MPI_UNDEFINED

Глобальные операции

MPI_MAX

MPI_MIN

MPI_SUM

MPI_PROD

Любой процесс/идентификатор

MPI_ANY_SOURCE

MPI_ANY_TAG

Код успешного завершения процедуры

MPI_SUCCESS

Оглавление       Назад         Далее