2. Анализ задачи
Если вы всё установили и настроили, и при этом у вас даже заработал примитивный тестовый пример с первого раза, считайте, что вам уже повезло. Можете даже немного расслабиться. Но ненадолго, так как впереди ещё решение поставленной задачи и её распараллеливание.
Лучше всего рассматривать решение задачи на конкретном примере. Причём, пример должен быть не слишком простым, так как элементарных примеров и так полно в интернете. Итак, предположим, что нам нужно решить уравнение теплопроводности и ускорить решение с использованием параллельного алгоритма. В общем виде уравнение записывается следующим образом:
где k, c, d – коэффициенты, которые могут в общем случае зависеть от времени и координаты; F – функция источника (также может зависеть от времени и координаты).
Чтобы немного упростить себе жизнь, рассмотрим одномерный случай. При этом пусть с=0, k и F – константы, а на границах отрезка начальные значения нулевые. Тогда получаем следующее уравнение:
Обращаясь к теории численных методов, записываем решение этого уравнения (явная схема):
Или же, в другом виде:
Что можно почерпнуть из этого уравнения с точки зрения программирования? Во-первых, в нём присутствуют значения функции в двух моментах времени: прошлом и текущем. Во-вторых, необходимо хранить значения u в разных точках пространства (прямой). Итак, нам нужны 2 массива длины, равной размерности пространства. Первый – для прошлого момента времени, второй – для текущего. Обозначим их U_old и U_new соответственно. Тогда их объявление и инициализация на языке С++ следующие:
double *U_old, *U_new;
int DIM=sizeX+1;
U_old=new double [DIM];
U_new=new double [DIM];
for(int i=0;i
U_new[i]=0;
>
Источник поместим в одну точку пространства (середина отрезка) и далее о нём больше вспоминать не будем:
Помимо вышесказанного, необходимо также параметризовать в коде программы значения констант уравнения и вычислить значения интервалов dx, dt:
int tmax=1, xmax=1;
int sizeT=10, sizeX=8;
double K=0.01, D=0.4, F=1000;
double dt=(double)tmax/sizeT, dx=(double)xmax/sizeX;
Далее вспомним, что в вычислениях нам нужно делить на dx 2 . Как известно, эта операция очень медленная, а значение dx при этом не меняется (не зависит от времени). Тогда уместно будет посчитать величину 1/dx 2 заранее и потом не делить, а умножать на данное значение:
С учётом всех замечаний, последовательный алгоритм решения одномерного уравнения теплопроводности имеет вид:
int main(int argc,char *argv[])
//Variables’ initialization
int tmax=1, xmax=1;
int sizeT=10, sizeX=8;
double K=0.01, D=0.4, F=1000;
double dt=(double)tmax/sizeT, dx=(double)xmax/sizeX;
double dx2inv=1/(dx*dx);
double *U_old, *U_new;
int DIM=sizeX+1;
U_old=new double [DIM];
U_new=new double [DIM];
for(int i=0;i
U_new[i]=0;
>
//Source:
U_old[sizeX/2]=F;
3. Разработка параллельного алгоритма
Итак, у нас уже есть алгоритм решения задачи. Осталось только его распараллелить. Правильнее, конечно, проектировать параллельный алгоритм сразу же, без промежуточной стадии в виде последовательной версии, но для не слишком сложных задач такой способ, я считаю, немного проще.
Начнём с того, что является необходимым в любой (или практически в любой) MPI-программе. Рассмотрим следующий код:
MPI_Init(&argc,&argv);
MPI_Comm_size(MPI_COMM_WORLD,&numprocs);
MPI_Comm_rank(MPI_COMM_WORLD,&myid);
MPI_Finalize();
Первая и последняя функции инициализируют и завершают работу MPI, и являются обязательными для использования этого интерфейса. А вот без остальных двух функций просто нельзя обойтись. Они записывают в переменные numprocs и myid значения количества доступных процессоров (потоков) и идентификатор каждого процессора (потока). К примеру, в однопоточной системе numprocs=1, а myid=0.
Вернёмся теперь к разработанному нами последовательному алгоритму решения уравнения. Очевидно, что в нём самой сложной с точки зрения вычислений частью является следующий цикл:
Именно этот цикл мы и будем распараллеливать, то есть равномерно распределять вычисления между доступными в системе процессорами. Из-за того, что текущее значение функции сильно зависит от прошлого, распараллеливать по времени нет смысла: чтобы посчитать следующий шаг, нас необходимо дождаться расчёта предыдущего. Поэтому будем как-то распределять по процессорам итерации цикла по пространственной координате. Для этого достаточно поделить отрезок х на numprocs интервалов и, что самое главное, обеспечить обмен между потоками посчитанными значениями на границах:
Для начала, зададим границы интервалов для каждого потока с идентификатором myid:
int piece=sizeX/numprocs; //размер части отрезка
int lbound, rbound; //левая и правая границы отрезка
lbound=myid*piece+1;
rbound=lbound+piece-1;
if(myid==numprocs-1 && sizeX%2==0) rbound—;
- сначала начинает работать поток 0 (myid=0). Посчитав значения функции на всём своём интервале, он передаёт потоку 1 сообщение со значением функции в своей правой границе;
- поток 1 получает сообщение от потока 0, благодаря чему может посчитать значение в своей левой границе; затем он вычисляет оставшиеся значения и отправляет 2 сообщения: потоку 0 – значение функции в левой границе, а потоку 2 – в правой и т.д. до тех пор, пока потоками не будут посчитаны значения функции на всём отрезке;
- повторение первых 2 пунктов для следующего момента времени.
Пожалуй, каждая строчка с приёмом/передачей сообщения требует отдельного комментария.
Если myid>0, то активируем приём сообщения от потока с идентификатором myid-1 и тегом 1 (то есть, будут приниматься сообщения только с тегом 1). Статус обмена будет записан в объявленную ранее переменную status. Это необходимо для использования функции приёма сообщения. Значение функции U, переданное в этом сообщении, записывается в массив U_new на 1 позицию «левее» текущей левой границы интервала.
Всем потокам, кроме последнего, активировать синхронную передачу сообщения (Ssend) потоку myid+1 с тегом 1. В сообщении передать значение в массиве U_new в правой границе интервала. Синхронная передача сообщения используется потому, что нам существенно, в каком порядке потоки начинают работать над расчётами. О разновидностях использованного нами двухточечного обмена можно (и желательно) почитать в других источниках.
Если момент времени не последний, то потокам с идентификатором myid>0 активировать синхронную передачу сообщения потоку myid-1 с тегом 2. В сообщении передаётся значение в массиве U_new в левой границе интервала.
Теперь все значения посчитаны, но хранятся они в разных потоках. Поэтому надо на какой-то из потоков возложить роль сборщика данных. Пусть это будет поток 0. Тогда он будет принимать от всех остальных потоков значения функции на их интервалах:
Последний штрих в коде нашей программы – это подсчёт времени работы алгоритма. Ведь мы, собственно, столько мучились с распараллеливанием ради ускорения работы. Для этого можно воспользоваться функцией MPI_Wtime():
double startwtime = 0.0, endwtime;
startwtime = MPI_Wtime();
//цикл с параллельными вычислениями
endwtime = MPI_Wtime();
cout
Код получившейся программы:
int main(int argc,char *argv[])
int myid, numprocs;
MPI_Status status;
double startwtime = 0.0, endwtime;
int namelen;
char processor_name[MPI_MAX_PROCESSOR_NAME];
MPI_Init(&argc,&argv);
MPI_Comm_size(MPI_COMM_WORLD,&numprocs);
MPI_Comm_rank(MPI_COMM_WORLD,&myid);
MPI_Get_processor_name(processor_name,&n amelen);
Чтобы разработанная нами программа заработала в многопоточном режиме, нужны дополнительные усилия. А точнее, надо запустить командную строку Windows, перейти в каталог установленного MPICH2 или msmpi, в папку bin. У меня полный путь к этой директории выглядит следующим образом:
C:\Program Files\Microsoft HPC Pack 2008 R2\Bin
Далее в командной строке ввести следующую команду:
К примеру, это может выглядеть так:
start mpiexec –n 4 С:/program.exe
Внимание! Файл с результатами вычислений (results.txt) будет создан в том каталоге, где находится mpiexec, а не ваша программа. То есть, в моём случае, в директории C:\Program Files\Microsoft HPC Pack 2008 R2\Bin
Если у вас всё получилось и программа работает (причём, правильно, причём, быстрее, чем последовательный алгоритм), то я вас поздравляю! Дальнейшее знакомство с MPI в ваших руках 😉
P.S. Надеюсь, кому-то этот гид поможет 🙂
Метки:
А.С. Антонов — Параллельное программирование с использованием технологии MPI
PDF-файл из архива «А.С. Антонов — Параллельное программирование с использованием технологии MPI», который расположен в категории » «. Всё это находится в предмете «распределенные операционные системы» из 8 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст из PDF
Почему делать на заказ в разы дороже, чем купить готовую учебную работу на СтудИзбе? Наши учебные работы продаются каждый год, тогда как большинство заказов выполняются с нуля. Найдите подходящий учебный материал на СтудИзбе!
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Нет! Мы не выполняем работы на заказ, однако Вы можете попросить что-то выложить в наших социальных сетях.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает — и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе «Студизба»
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.