Параллельная обработка данных

       

Технологии параллельного программирования


2004 г

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

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

Лекция 5. Технологии параллельного программирования. Message Passing Interface (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

                   


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







    Forekc.ru
    Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий