Нижегородский государственный университет им. Н.И.Лобачевского Факультет Вычислительной математики и кибернетики Раздел 4_1. Параллельное программирование на основе MPI Образовательный комплекс Введение в методы параллельного программирования Гергель В.П., профессор, д.т.н. Кафедра математического обеспечения ЭВМ

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 2 из 56 MPI: основные понятия и определения Введение в MPI –Инициализация и завершение MPI программ –Определение количества и ранга процессов –Прием и передача сообщений –Определение времени выполнение MPI программы –Коллективные операции передачи данных Пример: программа вычисления числа Заключение Содержание

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 3 из 56 Введение… –распределять вычислительную нагрузку, –организовать информационное взаимодействие (передачу данных) между процессорами. Решение всех перечисленных вопросов обеспечивает MPI -интерфейс передачи данных (message passing interface) В вычислительных системах с распределенной памятью процессоры работают независимо друг от друга. Для организации параллельных вычислений необходимо уметь:

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 4 из 56 Введение… В рамках MPI для решения задачи разрабатывается одна программа, она запускается на выполнение одновременно на всех имеющихся процессорах Для организации различных вычислений на разных процессорах: –Есть возможность подставлять разные данные для программы на разных процессорах, –Имеются средства для идентификации процессора, на котором выполняется программа Такой способ организации параллельных вычислений обычно именуется как модель "одна программа множество процессов" (single program multiple processes or SPMP)

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 5 из 56 Введение… В MPI существует множество операций передачи данных: –Обеспечиваются разные способы пересылки данных, –Реализованы практически все основные коммуникационные операции. Эти возможности являются наиболее сильной стороной MPI (об этом, в частности, свидетельствует и само название MPI)

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 6 из 56 Введение… Что означает MPI? MPI - это стандарт, которому должны удовлетворять средства организации передачи сообщений. MPI – это программные средства, которые обеспечивают возможность передачи сообщений и при этом соответствуют всем требованиям стандарта MPI: –программные средства должны быть организованы в виде библиотек программных модулей (библиотеки MPI), –должны быть доступны для наиболее широко используемых алгоритмических языков C и Fortran.

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 7 из 56 Введение… Достоинства MPI MPI позволяет существенно снизить остроту проблемы переносимости параллельных программ между разными компьютерными системами. MPI содействует повышению эффективности параллельных вычислений - практически для каждого типа вычислительных систем существуют реализации библиотек MPI. MPI уменьшает сложность разработки параллельных программ: –большая часть основных операций передачи данных предусматривается стандартом MPI, –имеется большое количество библиотек параллельных методов, созданных с использованием MPI.

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 8 из 56 Введение История разработки MPI 1992 г. Начало работ над стандартом библиотеки передачи сообщений (Oak Ridge National Laboratory, Rice University). Ноябрь 1992 г. Объявление рабочего варианта стандарта MPI 1. Ноябрь 1993 г. Обсуждение стандарта на конференции Supercomputing'93. 5 мая 1994 г. Окончательный вариант стандарта MPI Июня 1995 г. Новая версия стандарта - MPI Июля 1997 г. Опубликован стандарт MPI-2: Extensions to the Message-Passing Interface. Разработка стандарта MPI производится международным консорциумом MPI Forum

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 9 из 56 MPI: основные понятия и определения… Понятие параллельной программы Под параллельной программой в рамках MPI понимается множество одновременно выполняемых процессов: –Процессы могут выполняться на разных процессорах; вместе с этим, на одном процессоре могут располагаться несколько процессов, –Каждый процесс параллельной программы порождается на основе копии одного и того же программного кода (модель SPMP). Исходный программный код разрабатывается на алгоритмических языках C или Fortran с использованием библиотеки MPI. Количество процессов и число используемых процессоров определяется в момент запуска параллельной программы средствами среды исполнения MPI программ. Все процессы программы последовательно перенумерованы. Номер процесса именуется рангом процесса.

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 10 из 56 MPI: основные понятия и определения… В основу MPI положены четыре основные концепции: Тип операции передачи сообщения Тип данных, пересылаемых в сообщении Понятие коммуникатора (группы процессов) Понятие виртуальной топологии

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 11 из 56 MPI: основные понятия и определения… Операции передачи данных Основу MPI составляют операции передачи сообщений. Среди предусмотренных в составе MPI функций различаются: –парные (point-to-point) операции между двумя процессами, –коллективные (collective) коммуникационные действия для одновременного взаимодействия нескольких процессов.

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 12 из 56 MPI: основные понятия и определения… Понятие коммуникаторов… Коммуникатор в MPI - специально создаваемый служебный объект, объединяющий в своем составе группу процессов и ряд дополнительных параметров (контекст): –парные операции передачи данных выполняются для процессов, принадлежащих одному и тому же коммуникатору, –Коллективные операции применяются одновременно для всех процессов коммуникатора. Указание используемого коммуникатора является обязательным для операций передачи данных в MPI.

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 13 из 56 MPI: основные понятия и определения… Понятие коммуникаторов В ходе вычислений могут создаваться новые и удаляться существующие коммуникаторы. Один и тот же процесс может принадлежать разным коммуникаторам. Все имеющиеся в параллельной программе процессы входят в состав создаваемого по умолчанию коммуникатора с идентификатором MPI_COMM_WORLD. При необходимости передачи данных между процессами из разных групп необходимо создавать глобальный коммуникатор (intercommunicator).

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 14 из 56 MPI: основные понятия и определения… Типы данных При выполнении операций передачи сообщений для указания передаваемых или получаемых данных в функциях MPI необходимо указывать тип пересылаемых данных. MPI содержит большой набор базовых типов данных, во многом совпадающих с типами данных в алгоритмических языках C и Fortran. В MPI имеются возможности для создания новых производных типов данных для более точного и краткого описания содержимого пересылаемых сообщений.

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 15 из 56 MPI: основные понятия и определения Виртуальные топологии Логическая топология линий связи между процессами имеет структуру полного графа (независимо от наличия реальных физических каналов связи между процессорами). В MPI имеется возможность представления множества процессов в виде решетки произвольной размерности При этом, граничные процессы решеток могут быть объявлены соседними и, тем самым, на основе решеток могут быть определены структуры типа тор. В MPI имеются средства и для формирования логических (виртуальных) топологий любого требуемого типа.

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 16 из 56 Введение в разработку параллельных программ с использованием MPI… Основы MPI… Инициализация и завершение MPI программ –Первой вызываемой функцией MPI должна быть функция: (служит для инициализации среды выполнения MPI программы; параметрами функции являются количество аргументов в командной строке и текст самой командной строки.) –Последней вызываемой функцией MPI обязательно должна являться функция: int MPI_Init ( int *agrc, char ***argv ) int MPI_Finalize (void)

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 17 из 56 Введение в разработку параллельных программ с использованием MPI… Основы MPI… Инициализация и завершение MPI программ –структура параллельной программы, разработанная с использованием MPI, должна иметь следующий вид: #include "mpi.h" int main ( int argc, char *argv[] ) { MPI_Init ( &agrc, &argv ); MPI_Finalize(); return 0; }

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 18 из 56 Введение в разработку параллельных программ с использованием MPI… Основы MPI… Определение количества и ранга процессов… –Определение количества процессов в выполняемой параллельной программе осуществляется при помощи функции: –Для определения ранга процесса используется функция: int MPI_Comm_size ( MPI_Comm comm, int *size ) int MPI_Comm_rank ( MPI_Comm comm, int *rank )

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 19 из 56 Введение в разработку параллельных программ с использованием MPI… Основы MPI… Определение количества и ранга процессов… –Как правило, вызов функций MPI_Comm_size и MPI_Comm_rank выполняется сразу после MPI_Init: #include "mpi.h" int main ( int argc, char *argv[] ) { int ProcNum, ProcRank; MPI_Init ( &agrc, &argv ); MPI_Comm_size ( MPI_COMM_WORLD, &ProcNum); MPI_Comm_rank ( MPI_COMM_WORLD, &ProcRank); MPI_Finalize(); return 0; }

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 20 из 56 Введение в разработку параллельных программ с использованием MPI… Основы MPI… Определение количества и ранга процессов… –Коммуникатор MPI_COMM_WORLD создается по умолчанию и представляет все процессы выполняемой параллельной программы; –Ранг, получаемый при помощи функции MPI_Comm_rank, является рангом процесса, выполнившего вызов этой функции, и, тем самым, переменная ProcRank будет принимать различные значения в разных процессах.

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 21 из 56 Введение в разработку параллельных программ с использованием MPI… Основы MPI… Передача сообщений… –Для передачи сообщения процесс-отправитель должен выполнить функцию: int MPI_Send(void *buf, int count, MPI_Datatype type, int dest, int tag, MPI_Comm comm), где - buf – адрес буфера памяти, в котором располагаются данные отправляемого сообщения, - count – количество элементов данных в сообщении, - type - тип элементов данных пересылаемого сообщения, - dest - ранг процесса, которому отправляется сообщение, - tag - значение-тег, используемое для идентификации сообщений, - comm - коммуникатор, в рамках которого выполняется передача данных.

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 22 из 56 Введение в разработку параллельных программ с использованием MPI… Основы MPI… Передача сообщений… MPI_DatatypeC Datatype MPI_BYTE MPI_CHARsigned char MPI_DOUBLEDouble MPI_FLOATFloat MPI_INTInt MPI_LONGLong MPI_LONG_DOUBLElong double MPI_PACKED MPI_SHORTshort MPI_UNSIGNED_CHARunsigned char MPI_UNSIGNEDunsigned int MPI_UNSIGNED_LONGunsigned long MPI_UNSIGNED_SHORTunsigned short Базовые типы данных MPI для алгоритмического языка C

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 23 из 56 Введение в разработку параллельных программ с использованием MPI… Основы MPI… Передача сообщений –Отправляемое сообщение определяется через указание блока памяти (буфера), в котором это сообщение располагается. Используемая для указания буфера триада (buf, count, type) входит в состав параметров практически всех функций передачи данных, –Процессы, между которыми выполняется передача данных, обязательно должны принадлежать коммуникатору, указываемому в функции MPI_Send, –Параметр tag используется только при необходимости различения передаваемых сообщений, в противном случае в качестве значения параметра может быть использовано произвольное целое число.

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 24 из 56 Введение в разработку параллельных программ с использованием MPI… Основы MPI… Прием сообщений… –Для приема сообщения процесс-получатель должен выполнить функцию: int MPI_Recv(void *buf, int count, MPI_Datatype type, int source,int tag, MPI_Comm comm, MPI_Status *status), где - buf, count, type – буфер памяти для приема сообщения - source - ранг процесса, от которого должен быть выполнен прием сообщения, - tag - тег сообщения, которое должно быть принято для процесса, - comm - коммуникатор, в рамках которого выполняется передача данных, - status – указатель на структуру данных с информацией о результате выполнения операции приема данных.

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 25 из 56 Введение в разработку параллельных программ с использованием MPI… Основы MPI… Прием сообщений… –Буфер памяти должен быть достаточным для приема сообщения, а тип элементов передаваемого и принимаемого сообщения должны совпадать; при нехватке памяти часть сообщения будет потеряна и в коде завершения функции будет зафиксирована ошибка переполнения, –При необходимости приема сообщения от любого процесса- отправителя для параметра source может быть указано значение MPI_ANY_SOURCE, –При необходимости приема сообщения с любым тегом для параметра tag может быть указано значение MPI_ANY_TAG,

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 26 из 56 Введение в разработку параллельных программ с использованием MPI… Основы MPI… Прием сообщений… –Параметр status позволяет определить ряд характеристик принятого сообщения: Функция возвращает в переменной count количество элементов типа type в принятом сообщении. -status.MPI_SOURCE – ранг процесса-отправителя принятого сообщения, -status.MPI_TAG - тег принятого сообщения. MPI_Get_count(MPI_Status *status, MPI_Datatype type, int *count )

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 27 из 56 Введение в разработку параллельных программ с использованием MPI… Основы MPI… Прием сообщений Функция MPI_Recv является блокирующей для процесса- получателя, т.е. его выполнение приостанавливается до завершения работы функции. Таким образом, если по каким-то причинам ожидаемое для приема сообщение будет отсутствовать, выполнение параллельной программы будет блокировано.

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 28 из 56 Введение в разработку параллельных программ с использованием MPI… Основы MPI… Первая параллельная программа с использованием MPI… –Каждый процесс определяет свой ранг, после чего действия в программе разделяются (разные процессы выполняют различные действия), –Все процессы, кроме процесса с рангом 0, передают значение своего ранга нулевому процессу, –Процесс с рангом 0 сначала печатает значение своего ранга, а далее последовательно принимает сообщения с рангами процессов и также печатает их значения, –Возможный вариант результатов печати процесса 0: Hello from process 0 Hello from process 2 Hello from process 1 Hello from process 3

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 29 из 56 Введение в разработку параллельных программ с использованием MPI… Основы MPI… Первая параллельная программа с использованием MPI (замечания)… –Порядок приема сообщений заранее не определен и зависит от условий выполнения параллельной программы (более того, этот порядок может изменяться от запуска к запуску). Если это не приводит к потере эффективности, следует обеспечивать однозначность расчетов и при использовании параллельных вычислений: Указание ранга процесса-отправителя регламентирует порядок приема сообщений. MPI_Recv(&RecvRank, 1, MPI_INT, i, MPI_ANY_TAG, MPI_COMM_WORLD, &Status)

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 30 из 56 Введение в разработку параллельных программ с использованием MPI… Основы MPI… Первая параллельная программа с использованием MPI (замечания)… –Можно рекомендовать при увеличении объема разрабатываемых программ выносить программный код разных процессов в отдельные программные модули (функции). Общая схема MPI программы в этом случае будет иметь вид: MPI_Comm_rank(MPI_COMM_WORLD, &ProcRank); if ( ProcRank == 0 ) DoProcess0(); else if ( ProcRank == 1 ) DoProcess1(); else if ( ProcRank == 2 ) DoProcess2();

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 31 из 56 Введение в разработку параллельных программ с использованием MPI… Основы MPI Первая параллельная программа с использованием MPI (замечания) –Для контроля правильности выполнения все функции MPI возвращают в качестве своего значения код завершения. При успешном выполнении функции возвращаемый код равен MPI_SUCCESS. Другие значения кода завершения свидетельствуют об обнаружении тех или иных ошибочных ситуаций в ходе выполнения функций: - MPI_ERR_BUFFER – неправильный указатель на буфер, - MPI_ERR_COMM – неправильный коммуникатор, - MPI_ERR_RANK – неправильный ранг процесса и др.

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 32 из 56 Введение в разработку параллельных программ с использованием MPI… Определение времени выполнение MPI программы –Необходимо определять время выполнения вычислений для оценки достигаемого ускорения за счет использования параллелизма, –Получение времени текущего момента выполнения программы обеспечивается при помощи функции: –Точность измерения времени может зависеть от среды выполнения параллельной программы. Для определения текущего значения точности может быть использована функция: (время в секундах между двумя последовательными показателями времени аппаратного таймера используемой системы) double MPI_Wtime(void) double MPI_Wtick(void)

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 33 из 56 Введение в разработку параллельных программ с использованием MPI… Начальное знакомство с коллективными операциями передачи данных… –Будем использовать учебную задачу суммирования элементов вектора x: –Для решения необходимо разделить данные на равные блоки, передать эти блоки процессам, выполнить в процессах суммирование полученных данных, собрать значения вычисленных частных сумм на одном из процессов и сложить значения частичных сумм для получения общего результата решаемой задачи, –Для более простого изложения примера процессам программы будут передаваться весь суммируемый вектор, а не отдельные блоки этого вектора.

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 34 из 56 Введение в разработку параллельных программ с использованием MPI… Начальное знакомство с коллективными операциями передачи данных… Передача данных от одного процесса всем процессам программы… –Необходимо передать значения вектора x всем процессам параллельной программы, –Можно воспользоваться рассмотренными ранее функциями парных операций передачи данных: Повторение операций передачи приводит к суммированию затрат (латентностей) на подготовку передаваемых сообщений, Данная операция может быть выполнена за меньшее число операций передачи данных. MPI_Comm_size(MPI_COMM_WORLD,&ProcNum); for (i=1; i

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 35 из 56 Введение в разработку параллельных программ с использованием MPI… Начальное знакомство с коллективными операциями передачи данных… Передача данных от одного процесса всем процессам программы… –Широковещательная рассылка данных может быть обеспечена при помощи функции MPI: int MPI_Bcast(void *buf,int count,MPI_Datatype type, int root,MPI_Comm comm), где - buf, count, type – буфер памяти с отправляемым сообщением (для процесса с рангом 0), и для приема сообщений для всех остальных процессов, - root - ранг процесса, выполняющего рассылку данных, - comm - коммуникатор, в рамках которого выполняется передача данных.

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 36 из 56 Введение в разработку параллельных программ с использованием MPI… Начальное знакомство с коллективными операциями передачи данных… Передача данных от одного процесса всем процессам программы… –Функция MPI_Bcast осуществляет рассылку данных из буфера buf, содержащего count элементов типа type с процесса, имеющего номер root, всем процессам, входящим в коммуникатор comm

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 37 из 56 Введение в разработку параллельных программ с использованием MPI… Начальное знакомство с коллективными операциями передачи данных… Передача данных от одного процесса всем процессам программы –Функция MPI_Bcast определяет коллективную операцию, вызов функции MPI_Bcast должен быть осуществлен всеми процессами указываемого коммуникатора, –Указываемый в функции MPI_Bcast буфер памяти имеет различное назначение в разных процессах: Для процесса с рангом root, с которого осуществляется рассылка данных, в этом буфере должно находиться рассылаемое сообщение. Для всех остальных процессов указываемый буфер предназначен для приема передаваемых данных.

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 38 из 56 Введение в разработку параллельных программ с использованием MPI… Начальное знакомство с коллективными операциями передачи данных… Передача данных от всех процессов одному процессу… –Процедура сбора и последующего суммирования данных является примером часто выполняемой коллективной операции передачи данных от всех процессов одному процессу, в которой над собираемыми значениями осуществляется та или иная обработка данных.

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 39 из 56 Введение в разработку параллельных программ с использованием MPI… Начальное знакомство с коллективными операциями передачи данных… Передача данных от всех процессов одному процессу… int MPI_Reduce(void *sendbuf, void *recvbuf,int count, MPI_Datatype type, MPI_Op op,int root,MPI_Comm comm), где - sendbuf - буфер памяти с отправляемым сообщением, - recvbuf – буфер памяти для результирующего сообщения ( только для процесса с рангом root), - count - количество элементов в сообщениях, - type – тип элементов сообщений, - op - операция, которая должна быть выполнена над данными, - root - ранг процесса, на котором должен быть получен результат, - comm - коммуникатор, в рамках которого выполняется операция.

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 40 из 56 Введение в разработку параллельных программ с использованием MPI… Начальное знакомство с коллективными операциями передачи данных… Типы операций MPI для функций редукции данных… ОперацияОписание MPI_MAX Определение максимального значения MPI_MIN Определение минимального значения MPI_SUM Определение суммы значений MPI_PROD Определение произведения значений MPI_LAND Выполнение логической операции "И" над значениями сообщений MPI_BAND Выполнение битовой операции "И" над значениями сообщений MPI_LOR Выполнение логической операции "ИЛИ" над значениями сообщений MPI_BOR Выполнение битовой операции "ИЛИ" над значениями сообщений MPI_LXOR Выполнение логической операции исключающего "ИЛИ" над значениями сообщений MPI_BXOR Выполнение битовой операции исключающего "ИЛИ" над значениями сообщений MPI_MAXLOC Определение максимальных значений и их индексов MPI_MINLOC Определение минимальных значений и их индексов

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 41 из 56 Введение в разработку параллельных программ с использованием MPI… Начальное знакомство с коллективными операциями передачи данных… Типы операций MPI для функций редукции данных… –MPI_MAX и MPI_MIN ищут поэлементные максимум и минимум; –MPI_SUM вычисляет поэлементную сумму векторов; –MPI_PROD вычисляет поэлементное произведение векторов; –MPI_LAND, MPI_BAND, MPI_LOR, MPI_BOR, MPI_LXOR, MPI_BXOR - логические и двоичные операции И, ИЛИ, исключающее ИЛИ; –MPI_MAXLOC, MPI_MINLOC - поиск индексированного минимума/максимума

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 42 из 56 Введение в разработку параллельных программ с использованием MPI… Начальное знакомство с коллективными операциями передачи данных… Передача данных от всех процессов одному процессу… –Функция MPI_Reduce определяет коллективную операцию и, тем самым, вызов функции должен быть выполнен всеми процессами указываемого коммуникатора, все вызовы функции должны содержать одинаковые значения параметров count, type, op, root, comm, –Передача сообщений должна быть выполнена всеми процессами, результат операции будет получен только процессом с рангом root, –Выполнение операции редукции осуществляется над отдельными элементами передаваемых сообщений.

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 43 из 56 Введение в разработку параллельных программ с использованием MPI… Начальное знакомство с коллективными операциями передачи данных… Передача данных от всех процессов одному процессу (пример для операции суммирования)

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 44 из 56 Введение в разработку параллельных программ с использованием MPI Начальное знакомство с коллективными операциями передачи данных Синхронизация вычислений –Синхронизация процессов, т.е. одновременное достижение процессами тех или иных точек процесса вычислений, обеспечивается при помощи функции MPI: –Функция MPI_Barrier определяет коллективную операцию, при использовании должна вызываться всеми процессами коммуникатора. –Продолжение вычислений любого процесса произойдет только после выполнения функции MPI_Barrier всеми процессами коммуникатора. int MPI_Barrier(MPI_Comm comm);

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 45 из 56 Пример: Вычисление числа … Значение числа может быть получено при помощи интеграла Для численного интегрирования применим метод прямоугольников

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 46 из 56 Распределим вычисления между p процессорами (циклическая схема) Получаемые на отдельных процессорах частные суммы должны быть просуммированы Пример: Вычисление числа … - Процессор 0 - Процессор 1 - Процессор 2

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 47 из 56 #include "mpi.h" #include double f(double a) { return (4.0 / (1.0 + a*a)); } int main(int argc, char *argv) { int ProcRank, ProcNum, done = 0, n = 0, i; double PI25DT = ; double mypi, pi, h, sum, x, t1, t2; MPI_Init(&argc,&argv); MPI_Comm_size(MPI_COMM_WORLD,&ProcNum); MPI_Comm_rank(MPI_COMM_WORLD,&ProcRank); while (!done ) { // основной цикл вычислений if ( ProcRank == 0) { printf("Enter the number of intervals: "); scanf("%d",&n); t1 = MPI_Wtime(); } Пример: Вычисление числа …

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 48 из 56 Пример: Вычисление числа MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD); if (n > 0) { // вычисление локальных сумм h = 1.0 / (double) n; sum = 0.0; for (i = ProcRank + 1; i

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 49 из 56 Заключение… В первой презентации раздела рассмотрены понятия и определения, являющиеся основополагающими для стандарта MPI (параллельная программа, операция передачи сообщения, тип данных, коммуникатор, виртуальная топология). Дано быстрое и простое введение в разработку параллельных программ с использованием MPI. Приведен пример параллельной программы с использованием MPI

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 50 из 56 Сложность параллельных программ, разработанных с использованием MPI Проблема отладки параллельных программ Вопросы для обсуждения

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 51 из 56 Разработайте программу для нахождения минимального (максимального) значения среди элементов вектора. Разработайте программу для вычисления скалярного произведения двух векторов. Разработайте программу, в которой два процесса многократно обмениваются сообщениями длиной n байт. Выполните эксперименты и оцените зависимость времени выполнения операции данных от длины сообщения. Сравните с теоретическими оценками, построенными по модели Хокни. Темы заданий для самостоятельной работы

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 52 из 56 Информационный ресурс Интернет с описанием стандарта MPI: Одна из наиболее распространенных реализаций MPI библиотека MPICH представлена на Библиотека MPICH2 с реализацией стандарта MPI-2 содержится на unix.mcs.anl.gov/mpi/mpich2http://www- unix.mcs.anl.gov/mpi/mpich2 Русскоязычные материалы о MPI имеются на сайте Ссылки

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 53 из 56 Воеводин В.В., Воеводин Вл.В. (2002). Параллельные вычисления. – СПб.: БХВ-Петербург.БХВ-Петербург Корнеев В.В. (2003) Параллельное программирование в MPI. Москва-Ижевск: Институт компьютерных исследований,2003 Немнюгин С., Стесик О. (2002). Параллельное программирование для многопроцессорных вычислительных систем – СПб.: БХВ-Петербург. Group, W., Lusk, E., Skjellum, A. (1994). Using MPI. Portable Parallel Programming with the Message-Passing Interface. – MIT Press. Group, W., Lusk, E., Skjellum, A. (1999a). Using MPI - 2nd Edition: Portable Parallel Programming with the Message Passing Interface (Scientific and Engineering Computation). - MIT Press. Литература…

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 54 из 56 Group, W., Lusk, E., Thakur, R. (1999b). Using MPI- 2: Advanced Features of the Message Passing Interface (Scientific and Engineering Computation). - MIT Press. Pacheco, P. (1996). Parallel Programming with MPI. - Morgan Kaufmann. Quinn, M. J. (2004). Parallel Programming in C with MPI and OpenMP. – New York, NY: McGraw-Hill. Snir, M., Otto, S., Huss-Lederman, S., Walker, D., Dongarra, J. (1996). MPI: The Complete Reference. - MIT Press, Boston, 1996.MPI: The Complete ReferenceMIT Press, Литература

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 55 из 56 Авторский коллектив Гергель В.П., профессор, д.т.н., руководитель Гришагин В.А., доцент, к.ф.м.н. Абросимова О.Н., ассистент (раздел 10) Лабутин Д.Ю., ассистент (система ПараЛаб) Курылев А.Л., ассистент (лабораторные работы 4, 5) Сысоев А.В., ассистент (раздел 1) Гергель А.В., аспирант (раздел 12, лабораторная работа 6) Лабутина А.А., аспирант (разделы 7,8,9, лабораторные работы 1, 2, 3, система ПараЛаб) Сенин А.В., аспирант (раздел 11, лабораторные работы по Microsoft Compute Cluster) Ливерко С.В. (система ПараЛаб)

Н.Новгород, 2005 г. Основы параллельных вычислений: Параллельное программирование на основе MPI © Гергель В.П. 56 из 56 Целью проекта является создание образовательного комплекса "Многопроцессорные вычислительные системы и параллельное программирование", обеспечивающий рассмотрение вопросов параллельных вычислений, предусматриваемых рекомендациями Computing Curricula 2001 Международных организаций IEEE-CS и ACM. Данный образовательный комплекс может быть использован для обучения на начальном этапе подготовки специалистов в области информатики, вычислительной техники и информационных технологий. Образовательный комплекс включает учебный курс "Введение в методы параллельного программирования" и лабораторный практикум "Методы и технологии разработки параллельных программ", что позволяет органично сочетать фундаментальное образование в области программирования и практическое обучение методам разработки масштабного программного обеспечения для решения сложных вычислительно-трудоемких задач на высокопроизводительных вычислительных системах. Проект выполнялся в Нижегородском государственном университете им. Н.И. Лобачевского на кафедре математического обеспечения ЭВМ факультета вычислительной математики и кибернетики ( Выполнение проекта осуществлялось при поддержке компании Microsoft. О проекте