Размещено на http://www.allbest.ru/

Введение

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

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



1. Теория разработки параллельных программ на основе библиотеки MPI

многопроцессорный вычислительный коммуникатор программа

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

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

MPI имеет следующие особенности:

* MPI ? библиотека, а не язык. Она определяет имена, вызовы процедур и результаты их работы. Программы, которые пишутся на FORTRAN, C, и C++ компилируются обычными компиляторами и связаны с MPI-библиотекой.

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

* MPI соответствует модели многопроцессорной ЭВМ с передачей сообщений.

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

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

MPI_Init - Инициализация MPI

MPI_Comm_size - Определение числа процессов

MPI_Comm_rank - Определение процессом собственного номера

MPI_Send - Посылка сообщения

MPI_Recv - Получение сообщения

MPI_Finalize - Завершение программы MPI

Обращение к MPI_Init должно быть первым обращением в MPI-программе, оно устанавливает "среду" MPI. В каждом выполнении программы может выполняться только один вызов MPI_Init.

Коммуникатор MPI_COMM_WORLD описывает состав процессов и связи между ними. Вызов MPI_Comm_size возвращает в numprocs число процессов, которые пользователь запустил в этой программе. Значение numprocs ? размер группы процессов, связанной с коммуникатором MPI_COMM_WORLD. Процессы в любой группе нумеруются последовательными целыми числами, начиная с 0.

Вызывая MPI_ Comm_rank, каждый процесс выясняет свой номер (rank) в группе, связанной с коммуникатором.

После выполнения MPI_Finalize() любые операции MPI выполняться не будут.



1.1 Что предлагает MPI

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

Стандартизация

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

Переносимость

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

Эффективность работы

Множество внешних инструментов, включая PVM, Express и P4 (см. краткий глоссарий терминов в приложении 1), пыталось обеспечить стандартизованное окружение для параллельных вычислений, но, тем не менее, ни одна из этих попыток не показала такой высокой эффективности работы, как MPI. Богатство возможностей MPI имеет целый набор качественных реализаций. Эти реализации обеспечивают асинхронную коммуникацию, эффек- тивное управление буфером сообщения, эффективные группы, и богатые функциональные возможности. MPI включает большой набор коллективных операций коммуникации, виртуальных топологий и различных способов коммуникации, и, кроме того, MPI поддерживает библиотеки и неоднородные сети.

Имеющиеся в настоящее время реализации включают:

• MPICH: реализация Argonne National Lab;

• LAM: реализация Ohio Supercomputer Center;

• MPI/Pro: реализация MPI Software Technology;

• IBM MPI: реализация IBM для кластерных систем;

• SP и RS/6000 CHIMP: реализация Edinburgh Parallel Computing Centre;

• UNIFY: реализация Mississippi State University

MPI имеется в наличии на многих массивно параллельных системах. ВЦ РАН и МСЦ используют MPICH-реализацию MPI.



2. Программы MPI

2.1 Формат функций MPI

Во-первых, рассмотрим форматы фактических вызовов, используемых MPI.

Для C общий формат имеет вид

rc = MPI_Xxxxx(parameter,...)

Заметим, что, как и в любой команде С, регистр здесь важен. Например,MPI должно быть записано заглавными буквами, то же относится и к первой букве после подчеркивания. Все последующие символы должны быть в нижнем регистре. Переменная rc - это некий код возврата, имеющий целый тип. В случае успеха, он принимает значение MPI_SUCCESS. Программа на C должна включать файл mpi.h". Он содержит определения для констант и функций MPI. Заметим, что константы в MPI, такие как MPI_SUCCESS, MPI_INT, записываются заглавными буквами. Для C исключением к вышеприведенным функциям являются функции времени (MPI_Wtime и MPI_Wtick), которые являются функциями как в C, так и в Фортране, и возвращают действительные числа с двойной точностью.

2.2 Функции MPI

Основная схема программы MPI состоит из следующих общих этапов:

1. Инициализация для коммуникаций

2. Коммуникации распределения данных по процессам

3. Выход "чистым" способом из системы передачи сообщений по завершении коммуникаций

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

Инициализация для коммуникаций

• MPI_Init инициализирует окружение MPI

• MPI_Comm_size возвращает число процессов

• MPI_Comm_rank возвращает номер текущего процесса (ранг =

• номер по-порядку)

Коммуникации распределения данных по процессам

• MPI_Send отправляет сообщение

• MPI_Recv получает сообщение

• Выход из системы передачи сообщений

• MPI_Finalize



3. Сообщения MPI

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

Сообщение = данные (3 параметра) + оболочка (3 параметра)

Типичный состав сообщения в MPI смотрите рис. 3.1:

Рис.3.1

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

3.1 Данные

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

Число

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

Тип данных

Тип данных, которые будут передаваться - с плавающей точкой, например. Этот тип данных должен быть тем же самым в вызовах функций отправки и получения. Исключением из этого правила является тип данных MPI_PACKED, который является одним из способов обработки сообщений со смешанным типом данных (предпочтительнее использовать метод с производными типами данных). Проверка типов в этом случае не нужна. Предопределенные в MPI типы данных называют "основными типами данных", они перечислены ниже.

Основные типы данных MPI для C смотрите рис. 3.2

Рис. 3.2

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

Некоторые производные типы данных:

* Contiguous

* Vector

* Hvector

* Indexed

* Hindexed

* Struct

3.2 Оболочка

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

Цель (назначение или источник)

Этот аргумент устанавливают равным рангу процесса в комммуникаторе (см. ниже). Ранг меняется от 0 до (size-1), где size - это число процессов в коммуникаторе. Назначение определяется отправкой и используется, чтобы определить маршрут сообщения к соответствующему процессу. Источник определяется получением. Только сообщения, идущие от этого источника, могут быть приняты при вызове получения, но получение может установить источник в MPI_ANY_SOURCE, чтобы указать, что любой источник приемлем.

Тег

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

Коммуникатор

Коммуникатор, определенный при отправке должен равняться коммуникатору, определенному при получении. Несколько шире коммуникаторы обсуждаются далее в п. 3.3, а сейчас будет достаточно знать, что коммуникатор определяет коммуникационную "вселенную", и то, что процессы могут принадлежать более чем к одному коммуникатору. В этом модуле мы будем иметь дело только с предопределенным коммуникатором MPI_COMM_WORLD, который включает все процессы приложения.

Аналогия

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

1. Лицо, получающее иск (точнее, его идентификационный номер). Это - назначение.

2. Какой месяц охватывает этот иск. Так как лицо получает двенадцать исков в год, ему необходимо знать за какой месяц приходит этот иск. Это - тег.

3. На какую потребность выпускается иск. Лицу надо знать, за что получает он этот иск: иск ли это за электричество или иск за телефон. Это - коммуникатор

3.3 Коммуникаторы

Зачем нужны коммуникаторы?

Раскроем теперь смысл понятия коммуникатора. Сейчас обсудим только детали, касающиеся использования коммуникаторов. Более глубокое описание коммуникаторов будет дано в модуле «Управление группами и коммуникаторами MPI». Сообщение будет воспринято при вызове функции приема, если будут точно определены источник, тег и коммуникатор. Тег позволяет программе различать типы сообщений. Источник упрощает программирование. Вместо того, чтобы иметь уникальный тег для каждого сообщения, каждый процесс, отправляющий одну и ту же информацию, может использовать тот же тег. Но зачем нужен коммуникатор? Рассмотрим пример Предположим, вы передаете сообщения между вашими процессами, и, кроме того, используете ряд откуда-либо полученных библиотек, которые также порождают процессы, выполняемые на различных узлах, взаимодействующих друг с другом с помощью MPI. В этом случае вам нужно быть уверенным, что отправленные вами сообщения придут к вашим процессам и не будут смешаны с сообщениями, отправленными к процессам из библиотечных функций. Допустим, вы имеете три процесса, взаимодействующих друг с другом. Кроме того, каждый процесс вызывает библиотечную функцию, и три параллельные части библиотеки взаимодействуют друг с другом. Вам хочется иметь два различных "пространства" сообщений, один для ваших сообщений и один для библиотечных сообщений. Вам не хотелось бы получить какое- либо перемешивание этих сообщений.

Рис. 3.1 Намеченное поведение коммуникаций между процессами

Блоки на рис.3.1 представляют собой части параллельных процессов. Время растет сверху вниз на каждой диаграмме. Цифры в круглых скобках НЕ параметры, а номера процессов. Например, send(1) означает отправку сообщения процессу 1, recv(any) означает получение сообщения от любого процесса. Пользовательский (вызывающий) код находится в белом (незатененном) блоке. Затененный блок (вызываемый) представляет собой пакет (параллельной) библиотеки, вызванной пользователем. Наконец, стрелки представляют собой перемещение сообщения от отправителя Тем кнеполучателю менее, нет. никакой гарантии, что события произойдут в нужном порядке, так как относительное расписание процессов на различных узлах может меняться от исполнения к исполнению. Предположим, вы изменили третий процесс, добавив некоторые вычисления вначале. Последовательность событий может оказаться такой, что представлена на рис. 3.2.

Рис. 3.2 Возможное неверное поведение коммуникаций

В этом случае коммуникации не происходят, как было намечено. Первый "receive" в процессе 0 теперь получает "send" из библиотечной функции в процессе 1, а не намеченный (и теперь задержанный) "send" из процесса 2. В результате все три процесса зависают. Проблема решается разработчиком библиотеки за счет того, что библиотека запрашивает новый и уникальный коммуникатор и определяет этот коммуникатор во всех вызовах функций отправки и получения, которые делаются библиотекой. Это создает библиотечное ("вызываемое") пространство сообщений отделенное от пользовательского ("вызывающего") пространства сообщений. Можно ли было использовать теги, чтобы осуществить разделение пространства сообщений? Проблема с тегами состоит в том, что их значения задаются программистом, а он может использовать тот же тег, что и параллельная библиотека, использующая MPI. С коммуникаторами система, а не программист, осуществляет идентификацию - система назначает коммуникатор пользователю и он назначает отличный 20 коммуникатор библиотеке - так что возможность перекрытия не возникает.

Группы коммуникаторов и процессов

В дополнение к работе с параллельными библиотеками, коммуникаторы полезны также в организации коммуникаций внутри приложения. Мы описали коммуникатор, который включает все процессы в приложении. Но программист может также определить подмножество процессов, называемое группой процессов, и прикрепить один или больше коммуникаторов к этой группе процессов. Коммуникатор определяет, что коммуникация будет теперь ограничиваться этими процессами. В следующем ниже примере коммуникационным шаблоном является 2-мерная решетка (2D-mesh). Схема коммуникаций по двумерной решетке используется, например, для задач с геометрической структурой, в которой значения в соседних точках необходимы для уточнения значения в точке. Лучшим способом распараллеливания этой задачи является блочная декомпозиция данных по двум размерностям, и, затем, отображение блоков на 2- мерной решетке процессов. Решеточная топология - это абстракция, указывающая, каким процессам принадлежат соседние данные. Для точек внутри каждого процессного блока вся необходимая информация для уточнения точки содержится в этом процессе. Чтобы уточнить граничные точки процесса, необходимо знать строки и столбцы точек, содержащихся у соседей. Пусть, например, каждый из шести блоков представляет собой процесс. Каждый процесс должен обмениваться данными с соседями сверху и снизу, справа и слева. Кодировать эту коммуникацию будет проще, если процессы сгруппировать по столбцам (для коммуникаций выше/ниже) и строкам (для коммуникаций направо/налево). Итак, каждый процесс принадлежит трем коммуникаторам, что указано словами в блоке этого процесса: один коммуникатор на все процессы (мировой 21 коммуникатор, который дан по умолчанию), один коммуникатор на его строку и один коммуникатор на его столбец. Эти коммуникаторы указаны ниже рис 3.3.

Рис. 3.3 Коммуникаторы

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

4. Индивидуальное задание

Теоретические сведения для разработки программы:

Двойные интегралы обладают такими же свойствами, как и определённые интегралы (линейность, аддитивность, формулы среднего значения и т.д.).

Двойной интеграл в декартовых координатах:

Пусть функция  определена и непрерывна в замкнутой ограниченной области D плоскости 0xy.

Разобьём область D произвольным образом на элементарные ячейки , в каждой из которых зафиксируем точку, представлена в уравнении № 1:

.

Уравнение № 1

Составим сумму, сумма представлена в уравнении № 2:

,

Уравнение № 2

называемую интегральной, которая соответствует данному разбиению D на части и данному выбору точек .

Если существует предел последовательности интегральных сумм  при -диаметр ячеек  и этот предел не зависит ни от способа разбиения области D на элементарные ячейки, ни от выбора точек , то он называется двойным интегралом от функции f(x,y) по области D и представлена в уравнении № 3:



Уравнение № 3

Результаты работы программы:

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

Таблица 4.1 - «Результаты работы программы»

Кол-во входных значений Кол-во потоков	1	2	4	8	16
9000	0.0007537975907326	0.0004366477951407	0.0002305461093783	0.0001368187367916	0.0013112705200911
90000	0.0075306361541152	0.0041533205658197	0.0020909076556563	0.0010627051815391	0.0012023178860545
900000	0.0747467903420329	0.0415767226368189	0.0205570114776492	0.0104573350399733	0.0158112971112132
9000000	0.6697816345840693	0.3893552813678980	0.2064179945737124	0.1102980962023139	0.1532170288264751
90000000	6.4390025129541755	3.5495505714789033	1.7656840458512306	0.9044017465785146	0.9163652779534459



Рисунок 4.1 - Результаты работы программы на одном узле

Результаты работы программы на двух узлах представлены в таблице 4.2 и на рисунке 4.2:

Таблица 4.2 - «Результаты работы программы»

Кол-во входных значений / Кол-во потоков	1	2	4	8	16
9000	0.0007815938442945	0.0004680063575506	0.0002564573660493	0.0001599360257387	0.0001156572252512
90000	0.0074913846328855	0.0047103753313422	0.0021183555945754	0.0011150157079101	0.0005718600004911
900000	0.0757572539150715	0.0415737889707088	0.0208176597952843	0.0104006938636303	0.0052353022620082
9000000	0.6576117919757962	0.3760839011520147	0.1871296493336558	0.1041500391438603	0.0524644199758768
90000000	6.4406823348253965	3.5316434074193239	1.7737049683928490	0.8969459105283022	1.0058119120076299



Рисунок 4.2 - Результаты работы программы на двух узлах

Таблица 4.3 - «Результаты работы программы на одном узле»

Кол-во входных данных	1 поток	2 потока	4 потока
	время	время	ускорение	время	ускорение
9000	0,0007537975	0,0004366477	0,0003171498	0,0002305461	0,0002061016
90000	0,0075306361	0,0041533205	0,0033773156	0,0020909073	0,0020624129
900000	0,0747467903	0,0415767226	0,0331700677	0,0205570114	0,0210197111
9000000	0,6697816345	0,3893552813	0,2804263532	0,2064179945	0,1829372867
90000000	6,4390025129	3,5495505714	2,8894519415	1,7656840458	1,7838665256
	8 потоков	16 потоков
	время	ускорение	время	ускорение
9000	0,0001368187	0,0000937273	0,0013112705	-0,0011744517
90000	0,0010627051	0,0010282024	0,0012023178	-0,0001396127
900000	0,0104573350	0,0100996764	0,0158112971	-0,0053539620
9000000	0,1102980962	0,0961198983	0,1532170288	-0,0429189326
90000000	0,9044017465	0,8612822992	0,9163652779	-0,0119635313

Таблица 4.4 - «Результаты работы программы на двух узлах»

Кол-во входных данных	1 поток	2 потока	4 потока
	время	время	ускорение	время	ускорение
9000	0,00078159384	0,00046800635	0,0003135875	0,00025645736	0,0002115490
90000	0,00749138463	0,00471037533	0,0027810093	0,00211835559	0,0025920197
900000	0,07575725391	0,04157378897	0,0341834649	0,02081765979	0,0207561292
9000000	0,65761179197	0,37608390115	0,2815278908	0,18712964933	0,1889542518
90000000	6,44068233482	3,53164340741	2,9090389274	1,77370496839	1,7579384390
	8 потоков	16 потоков
	время	ускорение	время	ускорение
9000	0,00015993602	0,0000965213	0,00011565722	0,0000442788
90000	0,00111501570	0,0010033399	0,00057186000	0,0005431557
900000	0,01040069386	0,0104169659	0,00523530226	0,0051653916
9000000	0,10415003914	0,0829796102	0,05246441997	0,0516856192
90000000	0,89694591052	0,8767590579	1,00581191200	-0,1088660015



Выводы

На основе результатов работы программы можно сделать следующие выводы:

Использование двух потоков для решения данной задачи, уменьшает время ее выполнения в два раза, так как количество входных значений на интервале разделяется между двумя ядрами;

При небольшом значении входных данных (n=9000) увеличение потоков с 1 до 8, дает выигрыш во времени примерно в 7 раз;

Данная задача выполнялась на узле, содержащем два четырехядерных процессора, поэтому при увеличении потоков до 16 происходит незначительное уменьшение времени решения данной задачи, так как в данном случае на каждое ядро процессора приходится по 2 потока;



Литература

1. Cornell Theory Center. Basics of MPI Programming

2. Богачёв К.Ю. Основы параллельного программирования. - М.: БИНОМ. Лаборатория знаний, 2003.

3. Домашняя страница MPI в Argonne National Labs (http:// www-unix.mcs.anl.gov/mpi/)

4. Часто задаваемые вопросы по MPI (http://www.faqs.org/faqs/mpi-faq/) 5. RS/6000 SP: Practical MPI Programming (http://www.redbooks.ibm.com/abstracts/sg245380.html?Open)

6. MPIСH документация в прямом доступе (http://www. cluster.bsu.by/MPI_ALL.htm)

7. Оленев Н.Н. Параллельные вычисления для идентификации параметров в моделях экономики // Высокопроизводительные параллельные вычисления на кластерных системах. Материалы четвертого Международного научно-практического семинара и Всероссийской молодежной школы. / Под ред. чл.-корр. РАН В.А.Сойфера, Самара, 2004.

8. Г.И. Шпаковский, Н.В. Серикова. Программирование для многопроцессорных систем в стандарте MPI. - МИНСК: БГУ, 2002.

9. А. А. Букатов, В. Н. Дацюк, А. И. Жегуло, Программирование многопроцессорных вычислительных систем, Ростов-на-Дону, 2003.

Размещено на Allbest.ru

...