Министерство образования и науки Российской Федерации

Федеральное агентство по образованию

Нижегородский государственный университет

им. Н.И. Лобачевского

В.А. Гришагин, А.Н. Свистунов

ПАРАЛЛЕЛЬНОЕ ПРОГРАММИРОВАНИЕ

НА ОСНОВЕ MPI

Учебное пособие

Нижний Новгород

Издательство Нижегородского госуниверситета 2005 УДК 004.421.2 ББК 32.973.26-018.2 Г 82 Г 82. Гришагин В.А., Свистунов А.Н. Параллельное программирование на основе MPI. Учебное пособие – Нижний Новгород: Изд-во ННГУ им.Н.И. Лобачевского, 2005. - 93 с.

ISBN 5-85746-758-6 Настоящее пособие содержит описание инструментальных средств разработки параллельных программ для многопроцессорных вычислительных комплексов на основе библиотеки MPI (Message Passing Interface), которая является одной из наиболее распространенных систем параллельного программирования. Наряду с рассмотрением основных возможностей библиотеки пособие включает примеры практических параллельных программ, иллюстрирующих основные принципы и приемы параллельного программирования в среде MPI. Для облегчения трудоемкого процесса поиска ошибок программирования излагаемый материал содержит раздел по отладке и профилированию параллельных программ.

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

Пособие разработано в рамках выполнения гранта Конкурсного центра фундаментального естествознания (КЦФЕ) Рособразования № Е02-1.0-58.

ББК 32.973.26-018. ISBN 5-85746-758- Гришагин В.А., Свистунов А.Н., Введение Создание многопроцессорных (параллельных) вычислительных систем (ПВС) является стратегической линией развития компьютерной техники, обусловливаемой существованием в любой текущий момент времени актуальных задач фундаментальной и прикладной науки, для анализа и исследования которых производительности существующих средств вычислительной техники оказывается недостаточно. Тем не менее практическое использование параллельных вычислительных систем не является столь широким, как это могло бы быть потенциально возможным. К основным сдерживающим факторам широкого распространения параллельных вычислений следует отнести большую стоимость и разнообразие архитектурного построения ПВС, существенно более высокую (по сравнению с последовательным программированием) трудоемкость разработки эффективных параллельных алгоритмов и программ.

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

Применение кластеров может также в некоторой степени снизить проблемы, связанные с разработкой параллельных алгоритмов и программ, поскольку повышение вычислительной мощности отдельных процессоров позволяет строить кластеры из сравнительно небольшого количества (несколько десятков) отдельных компьютеров (lowly parallel processing). Это приводит к тому, что для параллельного выполнения в алгоритмах решения вычислительных задач достаточно выделять только крупные независимые части расчетов (coarse granularity), что, в свою очередь, снижает сложность построения параллельных методов вычислений и уменьшает потоки передаваемых данных между компьютерами кластера. Вместе с этим следует отметить, что организация взаимодействия вычислительных узлов кластера при помощи передачи сообщений обычно приводит к значительным временным задержкам, что накладывает дополнительные ограничения на тип разрабатываемых параллельных алгоритмов и программ.

Решение проблемы разнообразия архитектур параллельных вычислительных систем и обеспечение возможности создания мобильных (переносимых между различными компьютерными стандартизованного базового системного программного обеспечения для организации параллельных вычислений. Основным стандартом, широко используемым в настоящее время в практических приложениях, является интерфейс передачи сообщений (message passing interface - MPI). Наличие такого стандарта позволило разработать стандартные библиотеки программ (MPI-библиотеки), в которых оказалось возможным скрыть большинство архитектурных особенностей ПВС и, как результат, существенно упростить проблему создания параллельных программ. Более того, стандартизация базового системного уровня позволила в значительной степени обеспечить мобильность параллельных программ, поскольку в настоящее время реализации MPI-стандарта имеются для большинства компьютерных платформ.

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

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

Одной из основных проблем, возникающих при разработке параллельных программ, является их отладка. В отличие от последовательного случая трасса параллельной программы (времення диаграмма исполняемых операций) может меняться от запуска к запуску. Для уменьшения трудоемкости процесса анализа исполнения параллельных программ может быть рекомендована инструментальная среда MPE (Multi Processing Environment), адаптированная В.В.Травкиным и предназначенная для отладки и профилировки программ, созданных с использованием библиотеки MPI.

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

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

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

1.2. Преимущества модели с передачей данных Универсальность. Модель с передачей сообщений хорошо подходит к системам с отдельными процессорами, соединенными с помощью (быстрой или медленной) сети. Тем самым, она соответствует как большинству сегодняшних параллельных суперкомпьютеров, так и сетям рабочих станций.

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

Легкость отладки. Отладка параллельных программ обычно представляет собой непростую задачу. Модель с передачей сообщений управляет обращением к памяти более явно, чем любая другая модель (только один процесс имеет прямой доступ к любым переменным в памяти), и, тем самым, облегчает локализацию ошибочного чтения или записи в память.

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

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

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

1.3. Стандаритизация модели передачи данных (MPI) Использование модели передачи данных для разработки параллельных программ предполагает стандартизацию основных используемых понятий и применяемых средств. Подобные попытки унификации после разработки отдельных инструментальных коммуникационных библиотек привели к появлению в 1994 г.

стандарта интерфейса передачи данных (message passing interface MPI).

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

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

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

• MPI служит основой для разработки библиотек передачи данных. MPI специфицирует имена, последовательности вызова и результаты подпрограмм, вызываемых из программ на Фортране 77, и функций, вызываемых из Си-программ. Программы, написанные на Фортране 77 и Си, компилируются обычными компиляторами и связываются с библиотекой MPI;

• MPI относится к модели для передачи сообщений. Вычисление остается собранием процессов, связанных сообщениями.

2. Основные понятия MPI 2.1. Функции передачи сообщений Многие понятия MPI, которые на первый взгляд могут показаться новыми, на самом деле являются необходимыми уточнениями хорошо знакомых понятий. Рассмотрим самую элементарную операцию в библиотеке передачи сообщений - основную операцию send. Во многих современных системах передачи сообщений она выглядит следующим образом:

send(address, length, destination, tag), address - адрес в памяти начала буфера, содержащего посылаемые данные;

length - длина сообщения в байтах;

destination - идентификатор процесса, которому посылается сообщение (обычно, как целое);

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

Эта конкретная совокупность параметров часто выбирается благодаря тому, что она представляет собой хороший компромисс между тем, что нужно программисту, и тем, что эффективно реализуется аппаратурой (передача непрерывной области памяти от одного процессора другому). В частности, можно ожидать, что операционная система обеспечивает обслуживание очередей так, чтобы операция приема recv(address, maxlen, source, tag, datlen) успешно завершалась только в случае получения сообщения с нужной меткой (tag). Другие сообщения помещаются в очередь до тех пор, пока не будет выполнена соответствующая операция приема. В большинстве систем source - это выходной аргумент, указывающий, откуда пришло сообщение, хотя в некоторых системах он также может быть использован для ужесточения отбора сообщений и помещения их в очередь. При приеме address и maxlen вместе описывают буфер, в который нужно поместить принимаемые данные, datlen представляет число принятых байтов.

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

Описание буферов сообщений. Спецификация (address, length) посылаемого сообщения ранее хорошо соответствовала аппаратуре, но больше не является адекватной по двум причинам:

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

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

Решение MPI обеих этих проблем состоит в том, чтобы специфицировать сообщения на более высоком уровне и более гибким образом, чем (address, length), и чтобы отразить тот факт, что сообщение содержит более структурированные данные, чем просто строку бит. Для этого буфер сообщения в MPI определяется тройкой (address, count, datatype), описывающей count элементов данных типа datatype, начинающегося с address. Мощь этого механизма происходит от гибкости в значениях типа данных (datatype).

Прежде всего, тип данных может принимать значения элементарных типов данных в принимающем языке. Таким образом, (A, 10, MPI_REAL) описывает вектор А из 10 вещественных чисел на Фортране, вне зависимости от длины и формата числа с плавающей точкой. Реализация MPI для неоднородной сети гарантирует, что будут приняты те же 10 вещественных чисел, даже если принимающая машина имеет совершенно другой формат плавающей точки.

Используя средства MPI, пользователь может определять свои собственные типы данных, причем эти типы могут описывать "распределенные" по памяти (не непрерывные) данные.

2.2. Понятие коммуникаторов Разделение семейств сообщений. Почти все системы передачи сообщений предусматривают аргумент tag для операций send и receive. Этот аргумент позволяет программисту обрабатывать приходящие сообщения упорядоченным образом, даже если сообщения поступают в порядке, отличном от желаемого. Системы передачи сообщений помещают сообщения, пришедшие "с неверной меткой", в очередь до тех пор, пока программа не будет готова принять их. Обычно имеется возможность специфицировать "универсальную" метку, которая сопоставляется с любой меткой.

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

Решение MPI состоит в расширении понятия метки до нового понятия контекста. Контексты размещаются во время исполнения программы системой в ответ на запрос пользователя (или библиотеки) и используются для сопоставления сообщений. От метки контексты отличаются тем, что вырабатываются системой, а не пользователем, и никакое "универсальное" сопоставление не допускается.

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

Наименование процессов. Процессы принадлежат группам. Если группа содержит n процессов, то процессы внутри группы идентифицируются рангами - целыми числами от 0 до n-1. В рамках стандарта MPI предполагается, что существует начальная группа, которой принадлежат все процессы выполняемой параллельной программы. Внутри этой группы процессы нумеруются подобно тому, как они нумеруются во многих существующих системах передачи сообщений - от нуля до общего числа процессов минус один.

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

Таким образом, destination или source, специфицированные в операции посылки или приема, всегда указывают на ранг процесса в группе, идентифицированный с данным коммуникатором.

Иными словами, в MPI основная (синхронная) операция send выглядит следующим образом:

MPI_Send(buf, count, datatype, dest, tag, comm), (buf, count, datatype) описывают count элементов вида datatype, начинающихся с buf;

comm - идентифицирует группу процессов и контекст Операция receive превращается в MPI_Recv(buf, count, datatype, source, tag, comm, status).

Источник, метку и размер реально принятого сообщения можно извлечь из status.

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

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

При разработке параллельной программы с использованием MPI исходная задача разбивается на подзадачи (декомпозиция). Обычная техника состоит в следующем: каждая из подзадач оформляется в виде отдельной структурной единицы (функции, модуля), на всех процессорах запускается одна и та же программа "загрузчик", которая, в зависимости от "номера" процессора загружает ту или иную подзадачу. Такой подход (запуск одной и той же программы на всех выделенных для решения задачи процессоров) получил в литературе наименование SPMD (single program multiple data).

Рассмотрим эту технологию подробнее на примере широко используемой демонстрационной программы типа "Hello world" Первая программа int main(int argc, char* argv[]) // инициализация библиотеки MPI // получение количества процессов в программе MPI_Comm_size(MPI_COMM_WORLD, &numprocs);

// получение ранга процесса MPI_Comm_rank(MPI_COMM_WORLD, &rank);

printf ("\n Hello from process %3d", rank);

// завершение библиотеки MPI Первым в каждой MPI программе должен быть вызов MPI_Init, который должен присутствовать в каждой программе MPI и предшествует всем другим вызовам MPI1. Он устанавливает "среду" (environment) MPI. Только одно обращение к MPI_Init допускается в исполнении программы. Его аргументами являются количество аргументов командной строки процесса и собственно командная строка процесса. Почти каждая функция MPI возвращает код ошибки, который выражен либо как MPI_SUCCESS, либо как зависимый от реализации код ошибки. В этом примере (и многих других примерах) для сокращения количества кода мы не будем особенно тщательны в проверке кода возврата, предполагая, что он всегда равен MPI_SUCCESS.

Весь обмен данных в MPI связан с коммуникатором. В этой программе мы будем использовать только предопределенный коммуникатор MPI_COMM_WORLD, определяющий единый контекст и весь набор процессов параллельной программы. Определение MPI_COMM_WORLD приводится в mpi.h.

Функция MPI_Comm_size возвращает (в numprocs) число запущенных для данной программы процессов. Каким способом пользователь запускает эти процессы -зависит от реализации, но любая программа может определить число запущенных процессов с помощью данного вызова. Значение numprocs - это, по сути, размер группы, связанной с коммуникатором MPI_COMM_WORLD. Процессы каждой группы пронумерованы целыми числами, начиная с 0, которые называются рангами (rank). Каждый процесс определяет свой номер в группе, связанной с данным коммуникатором, с помощью MPI_Comm_rank. Таким образом, каждый процесс получает одно и то же число в numprocs, но разные числа в rank. Каждый процесс печатает свой ранг и общее количество запущенных процессов, затем все процессы выполняют MPI_Finalize. Эта функция должна быть выполнена каждым процессом MPI и приводит к ликвидации "среды" MPI. Никакие вызовы MPI не могут быть осуществлены процессом после вызова MPI_Finalize (повторный MPI_Init также невозможен).

За исключением MPI_Initialized, которым библиотека может определить, выполнялся ли MPI_INIT или нет.

Нужно заметить, что каждый процесс таким образом написанной и запущенной MPI-программы напечатает одно сообщение. Если все процессы были запущены на разных машинах, на каждой машине будет напечатано соответствующее сообщение2. Допустим, что мы хотим, чтобы все сообщения напечатал какой-то один процесс например, процесс с рангом 0. Кроме того, мы хотим, чтобы ранги процессов, которые он должен напечатать, передали бы ему сами процессы. Таким образом, мы хотим реализовать систему с выделенным нулевым процессом, который должен принять сообщения от всех остальных процессов.

3.1. Передача сообщений между двумя процессами MPI_Comm_size(MPI_COMM_WORLD, &n);

MPI_Comm_rank(MPI_COMM_WORLD, &rank);