Так вышло, что мне пришлось тесно столкнуться с изучением параллельных вычислений и в частности MPI. Пожалуй, направление это на сегодняшний день является весьма перспективным, так что хотелось бы показать хабраюзерам основы этого процесса.
Данная формула легко поддается распараллеливанию, так как искомое число является суммой отдельных слагаемых и благодаря этому каждый отдельный процессор может заняться вычислением отдельных слагаемых.
Количество слагаемых, которое будет рассчитываться в каждом отдельно взятом процессоре, зависит как и от длины интервала n, так и от имеющегося количества процессоров k, которые смогут участвовать в процессе вычисления. Так, например, если длина интервала n=4, а в вычислениях участвуют пять процессоров (k=5), то с первого по четвертый процессоры получат по одному слагаемому, а пятый будет не задействован. В случае же если n=10, а k=5, каждому процессору достанется по два слагаемых для вычисления.
Изначально, первый процессор с помощью функции широковещательной рассылки MPI_Bcast отправляет остальным значение заданной пользователями переменной n. В общем случае функция MPI_Bcast имеет следующий формат:
int MPI_Bcast(void *buffer, int count, MPI_Datatype datatype, int root, MPI_Comm comm), где buffer – это адрес буфера с элементом, сount – количество элементов, datatype – соответствующий тип данных в MPI, root – ранг главного процессора, который занимается пересылкой, а comm- имя коммуникатора.
В моем случае в роли главного процессора, как уже говорилось, будет выступать первый процессор с рангом 0.
После того число n будет успешно отправлено, каждый процессор займется вычислением своих слагаемых. Для этого в каждом шаге цикла к числу i, которое изначально равно рангу процессора, будет прибавляться число, равное количеству процессоров участвующих в вычислениях. Если число в ходе следующих действий число i превысит заданное пользователем число n, выполнение цикла для данного процессора остановится.
В ходе выполнения цикла слагаемые будут прибавляться в отдельную переменную и, после его завершения, полученная сумма отправится в главный процессор. Для этого будет использоваться функция операции приведения MPI_Reduce. В общем виде она выглядит следующим образом:
int MPI_Reduce(void *buf, void *result, int count, MPI_Datatype datatype, MPI_Op op, int root, MPI_Comm comm)
Она объединяет элементы входного буфера каждого процесса в группе, используя операцию op, и возвращает объединенное значение в выходной буфер процесса с номером root. Результатом такой операции будет единственное значение, благодаря чему функция приведения и получила свое название.
После выполнения программы на всех процессорах, первый процессор получит общую сумму слагаемых, которая и будет являться нужным нам значение экспоненты.
Следует заметить, что и в параллельном и последовательном методах вычисления экспоненты, для нахождения факториала используется рекурсивная функция. В ходе принятия решения по способу распараллеливания выполняемой задачи, я рассматривал вариант нахождения факториала также на разных процессорах, но в итоге такой вариант был принят мной нерациональным.
Первостепенной задачей все же является нахождение значения экспоненты и если процессоры начнут вычислять каждый факториал каждого слагаемого раздельным образом, это может привести к прямо обратно эффекту, а именно значительной потери в производительности и скорости вычисления.
Объясняется это тем, что в данном случае начнется весьма большая нагрузка на коммуникационную среду, которая и без того зачастую является слабым звеном в системах параллельных вычислений. Если же вычисление факториала будет происходить на каждом процессоре частным образом, нагрузка на линии коммуникаций будет минимальна. Данный случай можно назвать хорошим примером того, что и задача распараллеливания тоже должна порой иметь свои границы.
#include "mpi.h"
#include
#include
using namespace std;double Fact(int n)
{
if (n==0)
return 1;
else
return n*Fact(n-1);
}int main(int argc, char *argv)
{
SetConsoleOutputCP(1251);
int n;
int myid;
int numprocs;
int i;
int rc;
long double drob,drobSum=0,Result, sum;
double startwtime = 0.0;
double endwtime;N = atoi(argv);
if (rc= MPI_Init(&argc, &argv))
{
cout << "Ошибка запуска, выполнение остановлено " << endl;
MPI_Abort(MPI_COMM_WORLD, rc);
}MPI_Comm_size(MPI_COMM_WORLD,&numprocs);
MPI_Comm_rank(MPI_COMM_WORLD,&myid);if (myid == 0)
{Startwtime = MPI_Wtime();
}
MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);for (i = myid; i <= n; i += numprocs)
{
drob = 1/Fact(i);
drobSum += drob;
}MPI_Reduce(&drobSum, &Result, 1, MPI_LONG_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD);
cout.precision(20);
if (myid == 0)
{
cout << Result << endl;
endwtime = MPI_Wtime();
cout << (endwtime-startwtime)*1000 << endl;
}MPI_Finalize();
return 0;
}
* This source code was highlighted with Source Code Highlighter .
В этом посте мы расскажем об организации обмена данными с помощью MPI на примере библиотеки Intel MPI Library. Думаем, что эта информация будет интересна любому, кто хочет познакомиться с областью параллельных высокопроизводительных вычислений на практике.
Мы приведем краткое описание того, как организован обмен данными в параллельных приложениях на основе MPI, а также ссылки на внешние источники с более подробным описанием. В практической части вы найдете описание всех этапов разработки демонстрационного MPI-приложения «Hello World», начиная с настройки необходимого окружения и заканчивая запуском самой программы.
MPI является наиболее распространенным стандартом интерфейса передачи данных в параллельном программировании. Стандартизацией MPI занимается MPI Forum . Существуют реализации MPI под большинство современных платформ, операционных систем и языков. MPI широко применяется при решении различных задач вычислительной физики, фармацевтики, материаловедения, генетики и других областей знаний.
Параллельная программа с точки зрения MPI - это набор процессов, запущенных на разных вычислительных узлах. Каждый процесс порождается на основе одного и того же программного кода.
Основная операция в MPI - это передача сообщений. В MPI реализованы практически все основные коммуникационные шаблоны: двухточечные (point-to-point), коллективные (collective) и односторонние (one-sided).
Для демонстрации я выбрал сервис Amazon Elastic Compute Cloud (Amazon EC2). Новым пользователям Amazon предоставляет пробный год бесплатного использования серверами начального уровня.
Работа с Amazon EC2 интуитивно понятна. В случае возникновения вопросов, можно обратиться к подробной документации (на англ.). При желании можно использовать любой другой аналогичный сервис.
Создаем два рабочих виртуальных сервера. В консоли управления выбираем EC2 Virtual Servers in the Cloud , затем Launch Instance (под «Instance» подразумевается экземпляр виртуального сервера).
Следующим шагом выбираем операционную систему. Intel MPI Library поддерживает как Linux, так и Windows. Для первого знакомства с MPI выберем OC Linux. Выбираем Red Hat Enterprise Linux 6.6 64-bit
или SLES11.3/12.0
.
Выбираем Instance Type
(тип сервера). Для экспериментов нам подойдет t2.micro (1 vCPUs, 2.5 GHz, Intel Xeon processor family, 1 GiB оперативной памяти). Как недавно зарегистрировавшемуся пользователю, мне такой тип можно было использовать бесплатно - пометка «Free tier eligible». Задаем Number of instances
: 2 (количество виртуальных серверов).
После того, как сервис предложит нам запустить Launch Instances (настроенные виртуальные сервера), сохраняем SSH-ключи, которые понадобятся для связи с виртуальными серверами извне. Состояние виртуальных серверов и IP адреса для связи с серверами локального компьютера можно отслеживать в консоли управления.
Важный момент: в настройках Network & Security / Security Groups
необходимо создать правило, которым мы откроем порты для TCP соединений, - это нужно для менеджера MPI-процессов. Правило может выглядеть так:
Type: Custom TCP Rule
Protocol: TCP
Port Range: 1024-65535
Source: 0.0.0.0/0
И, напоследок, небольшой опрос по поводу возможных тем для будущих публикаций, посвященных высокопроизводительным вычислениям.
Только зарегистрированные пользователи могут участвовать в опросе. , пожалуйста.
Распараллеливание на языке Си
Пример 3b . Распараллеливание на языке Фортран
Пример 4a . Определение характеристик системного таймера на языке Си
Пример 4b . Определение характеристик системного таймера на языке Фортран
Пример 5a . Обмен сообщениями двух процессов на языке Си
Пример 5b . Обмен сообщениями двух процессов на языке Фортран
Пример 6a . Обмен сообщениями четных и нечетных процессов на языке Си
Пример 6b . Обмен сообщениями четных и нечетных процессов на языке Фортран
Пример 7a . Пересылка несуществующему процессу на языке Си
Пример 7b . Пересылка несуществующему процессу на языке Фортран
Пример 8a . Буферизованная посылка данных на языке Си
Пример 8b . Буферизованная посылка данных на языке Фортран
Пример 9a . Получение информации об атрибутах сообщения на языке Си
Пример 9b . Получение информации об атрибутах сообщения на языке Фортран
Пример 10a . Определение латентности и пропускной способности на языке Си
Пример 10b . Определение латентности и пропускной способности на языке Фортран
Пример 11a . Обмен по кольцевой топологии при помощи неблокирующих операций на языке Си
Пример 11b . Обмен по кольцевой топологии при помощи неблокирующих операций на языке Фортран
Пример 12a . Коммуникационная схема «мастер - рабочие» на языке Си
Пример 12b . Коммуникационная схема «мастер - рабочие» на языке Фортран
Пример 13a . Транспонирование матрицы на языке Си
Пример 13b . Транспонирование матрицы на языке Фортран
Пример 14a . Схема итерационного метода с обменом по кольцевой топологии при помощи отложенных запросов на языке Си
Пример 14b . Схема итерационного метода с обменом по кольцевой топологии при помощи отложенных запросов на языке Фортран
Пример 15a . Обмен по кольцевой топологии при помощи процедуры MPI_Sendrecv на языке Си
Пример 15b . Обмен по кольцевой топологии при помощи процедуры MPI_SENDRECV на языке Фортран
Пример 16a . Моделирование барьерной синхронизации на языке Си
Пример 16b . Моделирование барьерной синхронизации на языке Фортран
Пример 17a . Моделирование глобального суммирования при помощи схемы сдваивания и коллективной операции MPI_Reduce на языке Си
Пример 17b . Моделирование глобального суммирования при помощи схемы сдваивания и коллективной операции MPI_Reduce на языке Фортран
Пример 18a . Пользовательская глобальная функция на языке Си
Пример 18b . Пользовательская глобальная функция на языке Фортран
Пример 19a . Работа с группами на языке Си
Пример 19b . Работа с группами на языке Фортран
Пример 20a . Разбиение коммуникатора на языке Си
Пример 20b . Разбиение коммуникатора на языке Фортран
Пример 21a . Перенумерация процессов на языке Си
Пример 21b . Перенумерация процессов на языке Фортран
Пример 22a . Cхема «мастер - рабочие» с использованием интеркоммуникатора на языке Си
Пример 22b . Схема «мастер - рабочие» с использованием интеркоммуникатора на языке Фортран
Пример 23a . Cхема «мастер - рабочие» с использованием графовой топологии на языке Си
Пример 23b . Схема «мастер - рабочие» с использованием графовой топологии на языке Фортран
Пример 24a . Перестановка столбцов матрицы в обратном порядке на языке Си
Пример 24b . Перестановка столбцов матрицы в обратном порядке на языке Фортран
Пример 25a . Пересылка упакованных данных на языке Си
Пример 25b . Пересылка упакованных данных на языке Фортран
master.c
slave.c
Пример 26a. Схема «мастер - рабочие» с использованием порождения процессов на языке Си
master.f
slave.f
Пример 26b. Схема «мастер - рабочие» с использованием порождения процессов на языке Фортран
server.c
client.c
Пример 27a. Обмен данными между сервером и клиентом посредством публичного имени на языке Си
server.f
client.f
Пример 27b. Обмен данными между сервером и клиентом посредством публичного имени на языке Фортран
Пример 28a
Пример 28b
Пример 29a . Обмен по кольцевой топологии при помощи односторонних коммуникаций на языке Си
Пример 29b . Обмен по кольцевой топологии при помощи односторонних коммуникаций на языке Фортран
Пример 30a . Обмен по кольцевой топологии при помощи односторонних коммуникаций на языке Си
Пример 30b . Обмен по кольцевой топологии при помощи односторонних коммуникаций на языке Фортран
Пример 31a . Буферизованное чтение из файла на языке Си
Пример 31b . Буферизованное чтение из файла на языке Фортран
Пример 32a . Коллективное чтение из файла на языке Си
Пример 32b . Коллективное чтение из файла на языке Фортран
Пример 33a . Обработка ошибок на языке Си
Пример 33b . Обработка ошибок на языке Фортран
Пример 34a . Условная компиляция на языке Си
Пример 34b
Пример 34c . Условная компиляция на языке Фортран
Пример 35a . Работа с системными таймерами на языке Си
Пример 35b . Работа с системными таймерами на языке Фортран
Пример 36a . Параллельная область на языке Си
Пример 36b . Параллельная область на языке Фортран
Пример 37a . Опция reduction на языке Си
Пример 37b . Опция reduction на языке Фортран
Пример 38a . Процедура omp_set_num_threads и опция num_threads на языке Си
Пример 38b . Процедура omp_set_num_threads и опция num_threads на языке Фортран
Пример 39a . Процедуры omp_set_dynamic и omp_get_dynamic на языке Си
Пример 39b . Процедуры omp_set_dynamic и omp_get_dynamic на языке Фортран
Пример 40a . Вложенные параллельные области на языке Си
Пример 40b . Вложенные параллельные области на языке Фортран
Пример 41a . Функция omp_in_parallel на языке Си
Пример 41b . Функция omp_in_parallel на языке Фортран
Пример 42a . Директива single и опция nowait на языке Си
Пример 42b . Директива single и опция nowait на языке Фортран
Пример 43a . Опция copyprivate на языке Си
Пример 43b . Опция copyprivate на языке Фортран
Пример 44a . Директива master на языке Си
Пример 44b . Директива master на языке Фортран
Пример 45a . Опция private на языке Си
Пример 45b . Опция private на языке Фортран
Пример 46a . Опция shared на языке Си
Пример 46b . Опция shared на языке Фортран
Пример 47a . Опция firstprivate на языке Си
Пример 47b . Опция firstprivate на языке Фортран
Пример 48a . Директива threadprivate на языке Си
Пример 48b . Директива threadprivate на языке Фортран
Пример 49a . Опция copyin на языке Си
Пример 49b . Опция copyin на языке Фортран
Пример 50a . Процедуры omp_get_num_threads и omp_get_thread_num на языке Си
Пример 50b . Процедуры omp_get_num_threads и omp_get_thread_num на языке Фортран
Пример 51a . Директива for на языке Си
Пример 51b . Директива do на языке Фортран
Пример 52a . Опция schedule на языке Си
Пример 52b . Опция schedule на языке Фортран
Пример 53a . Опция schedule на языке Си
Наиболее распространенной технологией программирования для параллельных систем с распределенной памятью в настоящее время является MPI (Message Passing Interface). Основным способом взаимодействия параллельных процессов друг с другом в таких системах является передача сообщений (Message Passing). По сути MPI – это библиотека и среда исполнения для параллельных программ на языках C или Fortran. В данном пособии будут описаны примеры программ на языке С.
Изначально MPI позволяет использовать модель программирования MIMD (Multiple Instruction Multiple Data) – много потоков инструкций и данных, т.е. объединение различных программ с различными данными. Но программирование для такой модели на практике оказывается слишком сложным, поэтому обычно используется модель SIMD (Single Program Multiple Data) –одна программа и много потоков данных. Здесь параллельная программа пишется так, чтобы разные ее части могли одновременно выполнять свою часть задачи, таким образом, достигается параллелизм. Поскольку все функции MPI содержаться в библиотеке, то при компиляции параллельной программы необходимо будет прилинковать соответствующие модули.
Под параллельной программой в рамках MPI понимается множество одновременно выполняемых процессов. Процессы могут выполняться на разных процессорах, но на одном процессоре могут располагаться и несколько процессов (в этом случае их исполнение осуществляется в режиме разделения времени). При запуске MPI – программы на кластере на каждом из его узлов будет выполняться своя копия программы, выполняющая свою часть задачи, из этого следует, что параллельная программа – это множество взаимодействующих процессов, каждый из которых работает в своем адресном пространстве. В предельном случае для выполнения параллельной программы может использоваться один процессор - как правило, такой способ применяется для начальной проверки правильности параллельной программы.
Количество процессов и число используемых процессоров определяется в момент запуска параллельной программы средствами среды исполнения MPI - программ и в ходе вычислений меняться не может. Все процессы программы последовательно перенумерованы от 0 до np-1, где np есть общее количество процессов. Номер процесса называется рангом процесса.
Взаимодействуют параллельные процессы между собой при помощи посылки сообщений. Методы посылки (их называют коммуникации) бывают двух видов – коллективные(collective) и “точка-точка” (point-to-point). При коллективных коммуникациях процесс посылает нужную информацию одновременно целой группе процессов, еще есть более общий случай, когда внутри группы процессов передача информации идет от каждого процесса к каждому. Более простыми коммуникациями являются коммуникации типа ”точка-точка”, когда один процесс посылает информацию второму или они оба обмениваются информацией. Функции коммуникаций – основные функции библиотеки MPI. Кроме этого, обязательными функциями являются функции инициализации и завершения MPI – MPI_Init и MPI_Finalize. MPI_Init должна вызываться в самом начале программ, а MPI_Finalize – в самом конце. Все остальные функции MPI должны вызываться между этими двумя функциями.
Как процесс узнает о том, какую часть вычислений он должен выполнять? Каждый процесс, исполняющийся на кластере, имеет свой уникальный номер – ранг. Когда процесс узнает свой ранг и общее количество процессов, он может определить свою часть работы. Для этого в MPI существуют специальные функции – MPI_Comm_rank и MPI_Comm_size. MPI_Comm_rank возвращает целое число - ранг процесса, вызвавшего ее, а MPI_Comm_size возвращает общее число работающих процессов.
Процессы отлаживаемой параллельной программы пользователя объединяются в группы. Под коммуникатором в MPI понимается специально создаваемый служебный объект, объединяющий в своем составе группу процессов и ряд дополнительных параметров (контекст), используемых при выполнении операций передачи данных. Коммуникатор, автоматически создаваемый при запуске программы и включающий в себя все процессы на кластере, называется MPI_COMM_WORLD. В ходе вычислений могут создаваться новые и удаляться существующие группы процессов и коммуникаторы. Один и тот же процесс может принадлежать разным группам и коммуникаторам. Коллективные операции применяются одновременно для всех процессов коммуникатора, поэтому для них одним из параметров всегда будет выступать коммуникатор.
При выполнении операций передачи сообщений в функциях MPI необходимо указывать тип пересылаемых данных. MPI содержит большой набор базовых типов данных, основанных на стандартных типах данных языка С. Кроме того, программист может конструировать свои типы данных при помощи специальных функций MPI. Ниже приведена таблица соответствия для базовых типов данных.
| Константы MPI | ТИП данных языка С |
| MPI_INT | signed int |
| MPI_UNSIGNED | unsigned int |
| MPI_SHORT | signed int |
| MPI_LONG | signed long int |
| MPI_UNSIGNED_SHORT | unsigned int |
| MPI_UNSIGNED_LONG | unsigned long int |
| MPI_FLOAT | float |
| MPI_DOUBLE | double |
| MPI_LONG_DOUBLE | long double |
| MPI_UNSIGNED_CHAR | unsigned char |
| MPI_CHAR | signed char |
Пример запуска библиотеки MPI: логин student, пароль s304.
#include
#include
int main (int argc, char *argv)
/* Инициализация MPI */
MPI_Init (&argc, &argv);
/* получение ранга процесса */
MPI_Comm_rank (MPI_COMM_WORLD, &rank);
/* получение общего числа процессов */
MPI_Comm_size (MPI_COMM_WORLD, &size);
printf("Hello world from process %d of %d\n", rank, size);
/* завершение MPI */
Для компиляции используется компилятор и линковщик. Командная строка mpicc. (см. mpicc….- help)
Каждый из запущенных процессов должен вывести на экран свой ранг и общее число процессов. Попробуем откомпилировать и запустить эту программу.
$ mpicc hello.c –o hello.o
$ mpicc hello.o –o hello
Файл hello и будет исполняемым файлом примера. Можно запустить его на одной машине и посмотреть, что число процессоров будет равно 1, а ранг процесса 0:
$ ./hello
Hello world from process 0 of 1
При работе на сервере для запуска используется команда mpirun . У нее есть два основных аргумента – имя файла, содержащего адреса узлов и число узлов, на котором будет запущена программа.
$ mpirun n0-6 –v hosts hello
Hello world from process 0 of 7
Hello world from process 3 of 7
Hello world from process 5 of 7
Hello world from process 4 of 7
Hello world from process 2 of 7
Hello world from process 6 of 7
Hello world from process 1 of 7
Программа будет запущена на 7 узлах (включая сервер), а адреса этих узлов находятся в файле hosts. Печать на экран осуществлялась процессами не по порядку их рангов. Это связано с тем, что запуск процессов не синхронизирован, однако в MPI существуют специальные функции для синхронизации процессов.
Простейшая программа не содержит функций передачи сообщений. В реальных же задачах процессам требуется взаимодействовать друг с другом. Естественно, на передачу сообщений тратится время, что снижает коэффициент распараллеливания задачи. Чем выше скорость интерфейса передачи сообщений (например Ethernet 10Mb/sec и Gigabit Ethernet), тем меньше будут затраты на передачу данных. Т.к. время обмена данными между процессами намного (на порядки) больше времени доступа к собственной памяти, распределение работы между процессами должно быть ‘крупнозернистым’, нужно избегать ненужных пересылок данных.
Среди задач численного анализа встречается немало задач, распараллеливание которых очевидно. Например, численное интегрирование сводится фактически к (многочисленному) вычислению подинтегральной функции (что естественно доверить отдельным процессам), при этом главный процесс управляет процессом вычислений (определяет стратегию распределения точек интегрирования по процессам и собирает частичные суммы). Подобным же распараллеливанием обладают задачи поиска и сортировки в линейном списке, численного нахождения корней функций, поиск экстремумов функции многих переменных, вычисление рядов и другие. В этой лабораторной работе мы рассмотрим два параллельных алгоритма вычисления числа π.
Вычисление числа π методом численного интегрирования
Известно, что
Заменяя вычисление интеграла конечным суммированием, имеем 
, где , n-число участков суммирования при численном интегрировании. Площадь каждого участка вычисляется как произведение ширины ‘полоски’ на значение функции в центре ‘полоски’, далее площади суммируются главным процессом (используется равномерная сетка).
Очевидно, что распараллеливание этой задачи легко сделать, если каждый процесс будет считать свою частичную сумму, а затем передаст результат вычислений главному процессу. Как избежать здесь повторяющихся вычислений? Процесс должен знать свой ранг, общее число процессов и число интервалов, на которое будет разбит отрезок (чем больше интервалов, тем выше будет точность). Тогда в цикле от 1 до числа интервалов процесс будет вычислять площадь полоски на i-ом интервале, а затем переходить не на следующий i+1интевал, а на интервал i+m, где m-число процессов. Как мы уже знаем, для получения ранга и общего числа процессов существуют функции MPI_Comm_rank и MPI_Comm_size . Перед началом вычислений главный процесс должен передать всем остальным число интервалов, а после вычислений собрать у них полученные частичные суммы и просуммировать их, в MPI это реализуется передачей сообщений. Для передачи сообщений здесь удобно использовать функцию коллективного взаимодействия MPI_Bcast , которая рассылает одинаковые данные от одного процесса всем остальным. Для сбора частичных сумм есть 2 варианта - можно использовать MPI_Gather , которая собирает данные со всех процессов и отдает их одному (получается массив из m элеменов, где m-число процессов) или MPI_Reduce . MPI_Reduce действует аналогично MPI_Gather – собирает данные от всех процессов и отдает одному, но не в виде массива, а предварительно производит определенную операцию между элементами массива, например, суммирование и после этого отдает один элемент. Для этой задачи более удобным выглядит использование MPI_Reduce . Текст программы приведен ниже
#include "mpi.h"
#include
#include
double f(double a)
return (4.0 / (1.0 + a*a));
int main(int argc, char *argv)
int n, myid, numprocs, i;
double PI25DT = 3.141592653589793238462643;
double mypi, pi, h, sum, x;
double startwtime, endwtime;
MPI_Init(&argc,&argv);
MPI_Comm_size(MPI_COMM_WORLD,&numprocs);
MPI_Comm_rank(MPI_COMM_WORLD,&myid);
startwtime = MPI_Wtime();
MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);
h = 1.0 / (double) n;
for (i = myid + 1; i <= n; i += numprocs)
x = h * ((double)i - 0.5);
MPI_Reduce(&mypi, &pi, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD);
printf("pi is approximately %.16f, Error is %.16f\n",
pi, fabs(pi - PI25DT));
endwtime = MPI_Wtime();
printf("wall clock time = %f\n",
endwtime-startwtime);
Рассмотрим подробнее вызовы функий MPI_Bcast и MPI_Reduce :
MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD) – содержимое переменной n и одного элемента типа MPI_INT из процесса с рангом 0 посылается всем остальным процессам (MPI_COMM_WORLD – все процессы в коммуникаторе) в ту же переменную n. После этого вызова каждый процесс будет знать общее число интервалов. По окончании вычислений MPI_Reduce(&mypi, &pi, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD) суммирует (параметр MPI_SUM) значения из переменных mypi типа MPI_DOUBLE каждого процесса и записывает результат в переменную pi процесса с рангом 0. Для замера времени вычислений главный процесс использует функцию MPI_Wtime.
double MPI_Wtime();
MPI_Wtime возвращает число секунд в формате числа с плавающей точкой, представляющее время, прошедшее с момента старта программы.
Вычисление числа π методом Монте-Карло
Для вычисления значения πможно использовать метод ‘стрельбы’. В применении к данному случаю метод заключается в генерации равномерно распределенныхна двумерной области точек и определении .
Вычисленное таким образом значение π является приближенным, в общем случае точность вычисления искомого значения повышается с увеличением числа ‘выстрелов’ и качества генетатора случайных чисел; подобные методы используются в случае трудностей точной числовой оценки.
Параллельный алгоритм вычисления числа π данным методом во многом похож на предыдущий рассмотренный нами алгоритм. Для генерации случайных чисел нужно использовать функцию srand, которой в качестве агрумента (семени последовательности) задавать ранг процесса, таким образов, у каждого процесса будет своя последовательность.
#include
void srand(unsigned seed);
Функция srand() устанавливает исходное число для последовательности, генерируемой функцией rand().
#include
int rand(void);
Функция rand() генерирует последовательность псевдослучайных чисел. При каждом обращении к функции возвращается целое в интервале между нулем и значением RAND_MAX.
Для сбора результата здесь также удобно использовать MPI_Reduce с заданием операции суммирования (MPI_SUM), затем разделить полученную сумму на число процессоров, получив среднее арифметическое.
int MPI_Reduce(void* sendbuf, void* recvbuf, int count,
MPI_Datatype datatype, MPI_Op op, int root, MPI_Comm comm);
Параметры:
sendbuf адрес посылающего буфера
recvbuf адрес принимающего буфера
op операция редукции
comm коммуникатор
int MPI_Bcast(void *buffer, int count, MPI_Datatype datatype, int root,
MPI_Comm comm);
Параметры:
buffer адрес посылающего/принимающего буфера
count количество элементов в посылающем буфере (целое)
datatype тип данных элементов посылающего буфера
root номер главного процесса (целое)
comm коммуникатор
Задание : в соответствии с номером варианта откомпилировать и запустить параллельную программы, вычисляющую число π по заданному алгоритму.
Запустить задачу на одном узле и с кластера, на заданном количестве узлов. Оценить время выполнения вычислений, точность и коэффициент распараллеливания Амдала с учетом сетевой задержки теоретически и по результатам выполнения работы.
Варианты заданий
| № Варианта | Алгоритм | Число процессоров | Число итераций на каждом процессоре |
| Численное интегрирование | |||
| Монте-Карло | |||
| Численное интегрирование | |||
| Монте-Карло | |||
| Численное интегрирование | |||
| Монте-Карло | |||
| Численное интегрирование | |||
| Монте-Карло | |||
| Численное интегрирование | |||
| Монте-Карло | |||
| Численное интегрирование | |||
| Монте-Карло | |||
| Численное интегрирование | |||
| Монте-Карло | |||
| Численное интегрирование | |||
| Монте-Карло | |||
| Численное интегрирование | |||
| Монте-Карло | |||
| Численное интегрирование | |||
| Монте-Карло |
· Постановка задачи, вариант.
· Текст параллельной программы на языке С согласно заданию.
· Результаты запуска программы на одном узле, время выполнения t i , результат вычислений, ошибка.
· Результаты запуска программы на сервере, время выполнения, результат вычислений, ошибка.
· Описать параллельный алгоритм, информационные потоки при выполнении программы и загрузку КЭШ-памяти узлов. Вычислить по результатам работы программы коэффициент Амдала - К j .
· Учитывая результаты работы группы студентов, построить гистограмму зависимости К j , t i от количества процессоров участвующих в вычислениях.
