Учебное пособие саранск издательство свмо 2013 2 удк 004. 42 Ббк з97 Авторский знак о753
 Скачать 6.58 Mb.
|
|
МИНИСТЕРСТВО НАУКИ И ОБРАЗОВАНИЯ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «МОРДОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. Н. П. ОГАРЁВА» Жалнин Р.В., Панюшкина Е.Н., Пескова Е.Е., Шаманаев П.А. ОСНОВЫ ПАРАЛЛЕЛЬНОГО ПРОГРАММИРОВАНИЯ С ИСПОЛЬЗОВАНИЕМ ТЕХНОЛОГИЙ MPI И OPENMP УЧЕБНОЕ ПОСОБИЕ САРАНСК ИЗДАТЕЛЬСТВО СВМО 2013 2 УДК 004.42 ББК З97 Авторский знак О-753 А в т о р ы : Жалнин Руслан Викторович, Панюшкина Елена Николаевна, Пескова Елизавета Евгеньевна,Шаманаев Павел Анатольевич Рецензенты: - кафедра высшей математики ФГБОУ ВПО «Ульяновский государственный технический университет»; - ректор ФГБОУ ДПО «Мордовский институт переподготовки кадров агробизнеса» доктор технических наук, профессор Чаткин М.Н. Авторский знак О-753 Основы параллельного программирования с использованием технологий MPI и OpenMP: учебное пособие / Р.В. Жалнин, Е.Н. Панюшкина, Е. Е. Пескова, П.А. Шаманаев. – Саранск: Изд-во СВМО, 2013. – 78 с. Настоящее учебное пособие содержит систематическое изложение основ параллельных вычислений с помощью технологий MPI и OpenMP. Пособие включает в себя описание основных процедур, необходимых для написания параллельных программ с использованием языка программирования С++. Приводятся примеры небольших законченных программ. Предназначено для студентов и магистрантов, обучающихся по направлениям и специальностям «Прикладная математика и информатика», «Фундаментальная информатика и информационные технологии». Пособие может быть полезно аспирантами и научным работникам, использующих в своих исследованиях параллельные вычисления. Публикуется на основании устава Средневолжского математического общества (пп. 2.4 и 2.5) и по решению редакционного отдела СВМО. ISBN 978-5-901661-32-1 ©Жалнин Р.В., Панюшкина Е.Н., Пескова Е.Е., Шаманаев П.А., 2013 ©Издательство СВМО, 2013 3 СОДЕРЖАНИЕ ВВЕДЕНИЕ 5 1. ХАРАКТЕРИСТИКА СРЕДСТВ ПРОГРАММИРОВАНИЯ МНОГОПРОЦЕССОРНЫХ СИСТЕМ 6 1.1. Системы с общей памятью 6 1.2. Системы с распределенной памятью 7 2. ПАРАЛЛЕЛЬНОЕ ПРОГРАММИРОВАНИЕ С ИСПОЛЬЗОВАНИЕМ ТЕХНОЛОГИИ MPI 9 2.1 Основные понятия 9 2.2 Базовые функции MPI 11 2.3 Типы данных 13 2.4 Процедуры передачи/приема сообщений между отдельными процессами 14 2.4.1 Обмен сообщениями с блокировкой 14 2.4.2 Обмен сообщениями без блокировки 17 2.4.3 Обмен сообщениями при помощи одной функции 19 2.5 Коллективные взаимодействия процессов 20 2.5.1 Барьерная синхронизация 21 2.5.2 Передача данных от одного процесса всем. Широковещательная рассылка данных 21 2.5.3. Передача данных от всех процессов одному. Операции редукции 23 2.5.4. Функции распределения и сбора данных 24 2.6 Эффективность параллельных вычислений 27 2.7 Примеры параллельных алгоритмов и программ 28 2.7.1 Алгоритм суммирования ряда чисел 28 2.7.2 Алгоритм умножения матрицы на вектор 30 2.7.3 Алгоритм умножения матриц 34 2.7.4 Алгоритм решения СЛАУ методом Гаусса 39 2.7.5 Алгоритм параллельной пузырьковой сортировки 41 3. ПАРАЛЛЕЛЬНОЕ ПРОГРАММИРОВАНИЕ С ИСПОЛЬЗОВАНИЕМ ТЕХНОЛОГИИ OPENMP 45 3.1 Введение в технологию OpenMP 45 3.2 Основные понятия 46 3.2.1 Модель параллельной программы 46 3.2.2 Директивы и функции 48 3.3 Основные конструкции OpenMP 49 3.3.1 Параллельные секции, переменные среды и замер времени 49 3.3.2 Директивы single и master 55 4 3.3.3 Классы переменных 58 3.4 Варианты распределения работы между нитями 59 3.4.1 Низкоуровневое программирование 59 3.4.2 Распараллеливание оператора цикла 60 3.4.3 Параллельные секции 63 3.4.4 Задачи 65 3.5 Синхронизация 67 3.5.1 Директивы barrier и ordered 67 3.5.2 Критические секции 69 3.5.3 Директива atomic 70 3.5.4 Замки 71 3.5.5Директива flush 73 3.6 Примеры программ с использованием технологии OpenMP 74 БИБЛИОГРАФИЧЕСКИЙ СПИСОК 76 5 ВВЕДЕНИЕ В современном мире существует большое количество задач, для решения которых необходимо использовать огромные вычислительные мощности. Требования к точности и скорости решения таких задач постоянно возрастают. Одним из основных способов ускорения вычислений является создание параллельных вычислительных систем. Распараллеливание вычислительного процесса невозможно без представления о методах решения поставленных задач, об архитектуре параллельных вычислительных систем, а также математическом обеспечении, которое имеют эти системы. Важно знать класс методов, удобных для реализации на параллельной системе, и алгоритмическую структуру этих методов, а также изучить средства параллельного программирования. Данное пособие предназначено для использования в учебных курсах, посвященных средствам параллельного программирования. Сначала дается краткая характеристика средств программирования многопроцессорных вычислительных систем. Затем приводятся основные сведения об используемых в настоящее время технологиях параллельного программирования – OpenMP(для компьютеров с общей памятью) и MPI(для кластерных систем и компьютеров с распределенной памятью), что и занимает значительную часть пособия. Знакомство с данными средствами параллельного программирования включает в себя описание модели параллельной программы, характеристику основных процедур, функций и типов данных. Все параграфы снабжены наглядными примерами – программами на языке С++. Пособие предназначено для студентов, аспирантов, начинающих свое знакомство с параллельными технологиями а также всех тех, кто планирует их использование для решения своих задач. 6 1. ХАРАКТЕРИСТИКА СРЕДСТВ ПРОГРАММИРОВАНИЯ МНОГОПРОЦЕССОРНЫХ СИСТЕМ В данной главе мы кратко рассмотрим средства параллельного программирования для многопроцессорных систем. Основной характеристикой при классификации многопроцессорных систем является наличие общей (SMP системы) или распределенной (MPP системы) памяти. Это различие является важнейшим фактором, определяющим способы параллельного программирования. 1.1. Системы с общей памятью К системам этого типа относятся компьютеры с SMP архитектурой, различные разновидности NUMA систем и мультипроцессорные векторно-конвейерные компьютеры [4,7]. Характерным словом для этих компьютеров является “единый”: единая оперативная память, единая операционная система, единая подсистема ввода-вывода. Только процессоры образуют множество. Каждая пользовательская программа также запускается как отдельный процесс. Операционная система сама распределяет процессы по процессорам. В принципе, для распараллеливания программ можно использовать механизм порождения процессов. Однако этот механизм не очень удобен, поскольку каждый процесс функционирует в своем адресном пространстве, и основное достоинство этих систем – общая память – не может быть использован простым и естественным образом. Для распараллеливания программ используется механизм порождения нитей (threads) – легковесных процессов, для которых не создается отдельного адресного пространства, но которые на многопроцессорных системах также распределяются по процессорам [1,9]. В последние годы все более популярной становится система программирования OpenMP, являющаяся во многом обобщением и расширением этих наборов директив. Интерфейс OpenMP задуман как стандарт для программирования в модели общей памяти. В OpenMP входят спецификации набора директив компилятору, процедур и переменных среды. Разработчик не создает новую параллельную программу, а просто добавляет в текст последовательной программы OpenMP-директивы. При этом система программирования OpenMP предоставляет разработчику большие возможности по контролю над поведением параллельного приложения. Вся программа разбивается на последовательные и параллельные области. Все последовательные области выполняет главная нить, порождаемая при запуске программы, а при входе в параллельную область главная нить порождает 7 дополнительные нити. Предполагается, что OpenMP-программа без какой- либо модификации должна работать как на многопроцессорных системах, так и на однопроцессорных. В последнем случае директивы OpenMP просто игнорируются. Следует отметить, что наличие общей памяти не препятствует использованию технологий программирования, разработанных для систем с распределенной памятью [3,6,13]. 1.2. Системы с распределенной памятью В системах этого типа на каждом вычислительном узле функционирует собственные копии операционной системы, под управлением которых выполняются независимые программы. Это могут быть как действительно независимые программы, так и параллельные ветви одной программы. В этом случае единственно возможным механизмом взаимодействия между ними является механизм передачи сообщений [1,7,8]. В 1994 г. был принят стандарт механизма передачи сообщений MPI (Message Passing Interface). Основная цель, которую ставили перед собой разработчики MPI – это обеспечение полной независимости приложений, написанных с использованием MPI, от архитектуры многопроцессорной системы, без какой-либо существенной потери производительности. MPI – это библиотека функций, обеспечивающая взаимодействие параллельных процессов с помощью механизма передачи сообщений. Библиотека включает в себя множество функций передачи сообщений типа точка-точка, развитый набор функций для выполнения коллективных операций и управления процессами параллельного приложения [2,5,10]. Альтернативный подход предоставляет парадигма параллельной обработки данных, которая реализована в языке высокого уровня HPF. От программиста требуется только задать распределение данных по процессорам, а компилятор автоматически генерирует вызовы функций синхронизации и передачи сообщений (неудачное расположение данных может вызвать существенное увеличение накладных расходов). Для распараллеливания циклов используются либо специальные конструкции языка, либо директивы компилятору, задаваемые в виде псевдокомментариев. Язык HPF реализует идею инкрементального распараллеливания и модель общей памяти на системах с распределенной памятью. Эти два обстоятельства и определяют простоту программирования и соответственно привлекательность этой технологии. Одна и та же программа, без какой-либо модификации, должна эффективно работать как на однопроцессорных системах, так и на многопроцессорных вычислительных системах. Программы на языке HPF 8 существенно короче функционально идентичных программ, использующих прямые вызовы функций обмена сообщениями [7,8]. Следует отметить область, где механизму передачи сообщений нет альтернативы – это обслуживание функционального параллелизма. Если каждый узел выполняет свой собственный алгоритм, существенно отличающийся от того, что делает соседний процессор, а взаимодействие между ними имеет нерегулярный характер, то ничего другого, кроме механизма передачи сообщений, предложить невозможно. 9 2. ПАРАЛЛЕЛЬНОЕ ПРОГРАММИРОВАНИЕ С ИСПОЛЬЗОВАНИЕМ ТЕХНОЛОГИИ MPI 2.1 Основные понятия Наиболее распространенной технологией программирования параллельных компьютеров с распределенной памятью является технология MPI [2,10]. Основным способом взаимодействия параллельных процессов в таких системах является передача сообщений друг другу. Это и отражено в названии технологии – Message Passing Interface. Под параллельной программой в рамках MPI понимается множество одновременно выполняемых процессов. Процессы могут выполняться на разных процессорах, но на одном процессоре могут располагаться и несколько процессов (в этом случае их исполнение осуществляется в режиме разделения времени). В предельном случае для выполнения параллельной программы может использоваться один процессор – как правило, такой способ применяется для начальной проверки правильности параллельной программы. Каждый процесс параллельной программы порождается на основе копии одного и того же программного кода. Данный программный код, представленный в виде исполняемой программы, должен быть доступен в момент запуска параллельной программы на всех используемых процессорах. Исходный программный код для исполняемой программы разрабатывается на алгоритмических языках C или Fortran с применением той или иной реализации библиотеки MPI. Количество процессов и число используемых процессоров определяется в момент запуска параллельной программы средствами среды исполнения MPI программ и в ходе вычислений не может меняться без применения специальных, но редко задействуемых средств динамического порождения процессов и управления ими, появившихся в стандарте MPI версии 2.0. Все процессы программы последовательно перенумерованы от 0 до p1, где p есть общее количество процессов. Номер процесса именуется рангом процесса. Основу MPI составляют операции передачи сообщений. Среди предусмотренных в составе MPI функций различаются парные (pointtopoint) операции между двумя процессами и коллективные (collective) коммуникационные действия для одновременного взаимодействия нескольких процессов. 10 Для выполнения парных операций могут использоваться разные режимы передачи, среди которых синхронный, блокирующий и др. Процессы параллельной программы объединяются в группы. Другим важным понятием MPI, описывающим набор процессов, является понятие коммуникатора. Под коммуникатором в MPI понимается специально создаваемый служебный объект, который объединяет в своем составе группу процессов и ряд дополнительных параметров (контекст), используемых при выполнении операций передачи данных. Парные операции передачи данных выполняются только для процессов, принадлежащих одному и тому же коммуникатору. Коллективные операции применяются одновременно для всех процессов одного коммуникатора. Как результат, указание используемого коммуникатора является обязательным для операций передачи данных в MPI. В ходе вычислений могут создаваться новые и удаляться существующие группы процессов и коммуникаторы. Один и тот же процесс может принадлежать разным группам и коммуникаторам. Все имеющиеся в параллельной программе процессы входят в состав конструируемого по умолчанию коммуникатора с идентификатором MPI_COMM_WORLD. При выполнении операций передачи сообщений для указания передаваемых или получаемых данных в функциях MPI необходимо указывать тип пересылаемых данных. MPI содержит большой набор базовых типов данных, во многом совпадающих с типами данных в алгоритмических языках C и Fortran. Кроме того, в MPI имеются возможности создания новых производных типов данных для более точного и краткого описания содержимого пересылаемых сообщений. Итак, если сформулировать коротко, MPI – это библиотека функций, обеспечивающая взаимодействие параллельных процессов с помощью механизма передачи сообщений. Это библиотека, состоящая примерно из 130 функций, в число которых входят: Функции инициализации и закрытия MPI-процессов; Функции, реализующие парные операции; Функции, реализующие коллективные операции; Функции для работы с группами процессов и коммуникаторами; Функции для работы со структурами данных; Функции формирования топологии процессов. Изучение MPI начнем с рассмотрения базового набора функций, образующих минимально полный набор, достаточный для написания простейших программ. 11 MPI_Init'>2.2 Базовые функции MPI Любая MPI-программа должна начинаться с вызова функции инициализации MPI – функции MPI_Init. В результате выполнения этой функции создается группа процессов, в которую помещаются все процессы приложения, и создается область связи, описываемая предопределенным коммуникатором MPI_COMM_WORLD. Эта область связи объединяет все процессы-приложения. Процессы в группе упорядочены и пронумерованы от 0 до size-1, где size равно числу процессов в группе. Синтаксис функции инициализации MPI_Init на языке C выглядит следующим образом: int MPI_Init(int *argc, char ***argv), где • argc — указатель на количество параметров командной строки, • argv — параметры командной строки, применяемые для инициализации среды выполнения MPI программы. Параметрами функции являются количество аргументов в командной строке и адрес указателя на массив символов текста самой командной строки. Последней вызываемой функцией MPI обязательно должна являться функция: int MPI_Finalize(void). Функция закрывает все MPI-процессы и ликвидирует все области связи [2]. Как результат, можно отметить, что структура параллельной программы, разработанная с использованием MPI, должна иметь следующий вид: #include "mpi.h" int main(int argc, char *argv[]) { <программный код без использования функций MPI> MPI_Init(&argc, &argv); <программный код с использованием функций MPI> MPI_Finalize(); <программный код без использования функций MPI> return 0; } Следует отметить: • файл mpi.h содержит определения именованных констант, прототипов функций и типов данных библиотеки MPI; 12 • функции MPI_Init и MPI_Finalize являются обязательными и должны быть выполнены (и только один раз) каждым процессом параллельной программы; • перед вызовом MPI_Init может быть использована функция MPI_Initialized для определения того, был ли ранее выполнен вызов MPI_Init, а после вызова MPI_Finalize – MPI_Finalized аналогичного предназначения. Рассмотренные примеры функций дают представление синтаксиса именования функций в MPI. Имени функции предшествует префикс MPI, далее следует одно или несколько слов названия, первое слово в имени функции начинается с заглавного символа, слова разделяются знаком подчеркивания. Названия функций MPI, как правило, поясняют назначение выполняемых функцией действий. Определение количества процессов в выполняемой параллельной программе осуществляется при помощи функции: |