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

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

Государственное образовательное учреждение

высшего профессионального образования

"Ижевский государственный технический университет имени М.Т. Калашникова"

Отчет по курсовой работе по дисциплине "Вычислительные системы"

На тему: "Вычисление определенных интегралов методом прямоугольников с помощью MPI"

Выполнил: магистрант гр. МО2-781-1

Иванов А.А.

Проверил: к. т. н., доцент кафедры ВТ

Петухов К.Ю.

Ижевск, 2012

Содержание

• 1. Программирование в Message Passing Interface (MPI)
• 2. Как использовать MPI
• 3. Программы MPI
• 4. Запуск MPI программ
• 5. Метод прямоугольников
• Литература

1. Программирование в Message Passing Interface (MPI)

MPI - это библиотека передачи сообщений, собрание функций на C/C++ (или подпрограмм в Фортране, которые, зная MPI для C/C++, легко изучить самостоятельно), облегчающих коммуникацию (обмен данными и синхронизацию задач) между процессами параллельной программы с распределенной памятью. Разделенная память - память, которая разделена на сегменты, каждый из которых может быть напрямую доступен только одному узлу из параллельных процессоров. Акроним (сокращение по первым буквам) установлен для Message Passing Interface (интерфейс передачи сообщений).

MPI является на данный момент фактическим стандартом и самой развитой переносимой библиотекой параллельного программирования с передачей сообщений.

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

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

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

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

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

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

2. Как использовать MPI

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

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

Отлаживая параллельную версию удостоверьтесь сначала, что запуски вашей программы успешны на нескольких узлах. Затем постепенно увеличивайте число узлов, например, от 2 до 4, затем 8, и т.д. Таким путем вы не будете тратить впустую много машинного времени на дополнительные ошибки.

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

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

Привязка к языку C

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

rc = MPI_Xxxxx (parameter,.)

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

Программа на C должна включать файл "mpi. h". Он содержит определения для констант и функций MPI.

Функции MPI

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

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

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

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

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

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

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

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

MPI_Comm_rank возвращает номер текущего процесса (ранг = номер по-порядку)

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

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

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

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

MPI_Finalize

Сообщения MPI

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

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

старт буфера, число, тип данных	цель, тег, коммуникатор
ДАННЫЕ	ОБОЛОЧКА

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

Данные

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

Старт буфера

Адрес, где данные начинаются. Например, начало массива в вашей программе.

Число

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

Тип данных

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

Типы данных уже определенные для вас называются "основными типами данных" и перечислены ниже:

Типы данных MPI	Типы данных C
MPI_CHAR	signed char
MPI_SHORT	signed short int
MPI_INT	signed int
MPI_LONG	signed long int
MPI_UNSIGNED_CHAR	unsigned char
MPI_UNSIGNED_SHORT	unsigned short int
MPI_UNSIGNED	unsigned int
MPI_UNSIGNED_LONG	unsigned long int
MPI_FLOAT	float
MPI_DOUBLE	double
MPI_LONG_DOUBLE	long double
MPI_BYTE
MPI_PACKED

Оболочка (конверт)

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

Назначение или источник

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

Тег

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

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

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

Аналогия

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

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

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

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

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

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

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

Пример

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

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

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

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

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

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

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

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

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

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

В нижеприведенном примере коммуникационным шаблоном является 2-мерная решетка (2D-mesh). Каждый из шести блоков представляет процесс. Каждый процесс должен обменяться данными с соседями выше и ниже, справа и слева. Кодирование этой коммуникации проще если процессы группируются по столбцам (для коммуникаций выше/ниже) и строкам (для коммуникаций направо/налево). Итак, каждый процесс принадлежит трем коммуникаторам, что указывается словами в блоке этого процесса: один коммуникатор на все процессы (мировой коммуникатор по умолчанию), один коммуникатор на его строку и один коммуникатор на его столбец. Эти коммуникаторы указаны как следует ниже:

метод прямоугольник интеграл программирование

Это также прямо связано с использованием коллективных коммуникаторов.

Функции коллективной коммуникации: Функции обмена сообщениями, которые обмениваются данными среди всех процессов в группе. Эти функции обычно включают функцию барьера для синхронизации, функцию рассылки (broadcast) для отправки данных от одного процессора всем процессорам, и функции сборки/разброса (gather/scatter).

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

4. Запуск MPI программ

Компиляция

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

MS Visual C/C++:

Добавьте MPICH. lib..

Из командной строки:

MS Visual C/C++:

mpicc prog. c (после активизации setup_visualc)

Настройки для сборки и счета

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

np определяет число задач на выполнение

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

-h | - help показывает аргументы командной строки для mpirun

mpi_debug включает дополнительную проверку на входные параметры и дополнительный выход если ошибки возникнут при выполнении.

maxtime предельное время счета. Обязательный параметр в МСЦ.

5. Метод прямоугольников

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

В этой статье подробно разберем метод прямоугольников для приближенного вычисления определенного интеграла.

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

Пусть функция y = f (x) непрерывна на отрезке [a; b]. Нам требуется вычислить определенный интеграл

Обратимся к понятию определенного интеграла. Разобьем отрезок [a; b] на n частей точками . Внутри каждого отрезка выберем точку . Так как по определению определенный интеграл есть предел интегральных сумм при бесконечном уменьшении длины элементарного отрезка разбиения , то любая из интегральных сумм является приближенным значением интеграла

.

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

Если отрезок интегрирования [a; b] разбить на РАВНЫЕ части длины h точками (то есть ) и в качестве точек выбрать СЕРЕДИНЫ элементарных отрезков (то есть ), то приближенное равенство можно записать в виде . Это и есть формула метода прямоугольников. Ее еще называют формулой средних прямоугольников из-за способа выбора точек .

называют шагом разбиения отрезка [a; b].

Приведем графическую иллюстрацию.

Из чертежа видно, что подынтегральная функция y = f (x) приближается кусочной ступенчатой функцией.

Описание алгоритма:

Даны функция F (x) на интервале [XMIN,XMAS] и значение N.

Разобьем интервал на N равноотстоящих друг от друга точек:

X (I) = ( (N - I) * XMIN + (I - 1) * XMAX) / (N - 1)

Таким образом у мы получили N-1 интервалов.

Предположим что мы имеем N процессоров:

Процессор 0 назначим главным, предназначенным для вычисления интеграла F (X) на всем интервале [X (1), X (N)]. Процессорам 1. (N-1) ставятся в соответствие подинтервалы [X (I), X (I+1)]. Затем вычисляется интеграл Q (I) методом прямоугольников для каждого отрезка интервала функции F (x).

Процессор 0 передает процессору I границы отведенного ему подинтервала. Процессор I возвращает процессору 0 вычисленное значение Q (i).

Листинг программы на языке С.

# include <stdlib. h>

# include <stdio. h>

# include <math. h>

# include <time. h>

# include "mpi. h"

int main (int argc, char *argv []);

double f (double x);

void timestamp (void);

/******************************************************************************/

int main (int argc, char *argv [])

{

double end_time;

double h;

int i;

int ierr;

int m;

int master = 0;

int n;

int process;

int process_id;

int process_num;

double q_global;

double q_local;

int received;

int source;

double start_time;

MPI_Status status;

int tag;

int target;

double x;

double xb [2];

double x_max = 3.0;

double x_min = 0.0;

ierr = MPI_Init (&argc, &argv);

/*

Определим номер текущего процессора.

*/

ierr = MPI_Comm_rank (MPI_COMM_WORLD, &process_id);

/*

Получение количества процессоров

*/

ierr = MPI_Comm_size (MPI_COMM_WORLD, &process_num);

/*

Проверка количества доступных процессоров

*/

if (process_id == master)

{

timestamp ();

printf ("\n");

printf ("Главный процессор: \n");

printf ("\n");

printf (" Программа для вычиления определенных интегралов,\n");

printf (" Назначение подинтервалов процессорам. \n");

printf ("\n");

printf (" количество процессоров %d\n", process_num);

start_time = MPI_Wtime ();

if (process_num <= 1)

{

printf ("\n");

printf ("главный процессор: \n");

printf (" Нужно как минимум 2 процессора! \n");

ierr = MPI_Finalize ();

printf ("\n");

printf ("Главный процессор: \n");

printf (" Ненормальное завершение работы. \n");

exit (1);

}

}

printf ("\n");

/*

рассчет точек концов подинтервалов и их рассылка по процессорам - адресатам.

*/

if (process_id == master)

{

for (process = 1; process <= process_num-1; process++)

{

xb [0] = ( (double) (process_num - process) * x_min

+ (double) (process - 1) * x_max)

/ (double) (process_num - 1);

xb [1] = ( (double) (process_num - process - 1) * x_min

+ (double) (process) * x_max)

/ (double) (process_num - 1);

target = process;

tag = 1;

printf ("Точки интервалов %f! \n", xb [0]);

ierr = MPI_Send (xb, 2, MPI_DOUBLE, target, tag, MPI_COMM_WORLD);

}

}

else

{

source = master;

tag = 1;

ierr = MPI_Recv (xb, 2, MPI_DOUBLE, source, tag, MPI_COMM_WORLD, &status);

}

/*

дождемся, когда все процессоры получать свои назначения.

*/

ierr = MPI_Barrier (MPI_COMM_WORLD);

if (process_id == master)

{

printf ("\n");

printf ("Главный процессор: \n");

printf (" Подинтервалы назначены. \n");

}

/*

каждому процессору нужно передать количество точек

для вычислений по широковещательной рассылке.

*/

m = 100;

source = master;

ierr = MPI_Bcast (&m, 1, MPI_INT, source, MPI_COMM_WORLD);

/*

каждый процессор выполняет вычисления над своим интервалом и передает результат

процессору 0.

*/

if (process_id! = master)

{

q_local = 0.0;

printf ("Процессор %d активен! \n", process_id);

for (i = 1; i <= m; i++)

{

x = ( (double) (2 * m - 2 * i + 1) * xb [0]

+ (double) (2 * i - 1) * xb [1])

/ (double) (2 * m);

q_local = q_local + f (x);

}

q_local = q_local * (xb [1] - xb [0]) / (double) (m);

target = master;

tag = 2;

ierr = MPI_Send (&q_local, 1, MPI_DOUBLE, target, tag, MPI_COMM_WORLD);

}

/*

процессор 0 ждет N-1 промежуточного результата.

*/

else

{

received = 0;

q_global = 0.0;

while (received < process_num - 1)

{

source = MPI_ANY_SOURCE;

tag = 2;

ierr = MPI_Recv (&q_local, 1, MPI_DOUBLE, source, tag, MPI_COMM_WORLD,

&status);

q_global = q_global + q_local;

received = received + 1;

}

}

/*

главный процессор выдает результат

*/

if (process_id == master)

{

printf ("\n");

printf ("Главный процессор: \n");

printf (" Интеграл ф-ии F (x) = %f\n", q_global);

printf (" Ошибка вычислений %f\n", q_global - 0.624);

end_time = MPI_Wtime ();

printf ("\n");

printf (" Время, затраченное на вычисления = %f\n",

end_time - start_time);

}

/*

Terminate MPI.

*/

ierr = MPI_Finalize ();

/*

Termiante.

*/

if (process_id == master)

{

printf ("\n");

printf ("Главный процессор: \n");

printf (" Нормальное завершение вычислений. \n");

printf ("\n");

timestamp ();

}

return 0;

}

/************************************************************/

double f (double x)

{

double value;

value = 2.0*cos (x) / (2.0 + x * x);

return value;

}

/************************************************************/

void timestamp (void)

{

# define TIME_SIZE 40

static char time_buffer [TIME_SIZE];

const struct tm *tm;

time_t now;

now = time (NULL);

tm = localtime (&now);

strftime (time_buffer, TIME_SIZE, "%d %B %Y %I: %M: %S %p", tm);

printf ("%s\n", time_buffer);

return;

# undef TIME_SIZE

}

Литература

1. http://ru. wikipedia.org/wiki/Message_Passing_Interface.

2. http://www.ccas.ru/mmes/educat/lab04k/01/basics.html#Sec1 - основы программирования в MPI.

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

4. http://www.faqs.org/faqs/mpi-faq/ - часто задаваемые вопросы по MPI.

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