Параллельные алгоритмы. Лабораторная работы №5. Виртуальные топологии.. Виртуальные топологии
 Скачать 0.87 Mb.
|
|
МИНОБРНАУКИ РОССИИ САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ ЭЛЕКТРОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ «ЛЭТИ» ИМ. В.И. УЛЬЯНОВА (ЛЕНИНА) Кафедра МО ЭВМ ОТЧЕТ по лабораторной работе № 5 по дисциплине «Параллельные алгоритмы» Тема: Виртуальные топологии.
Санкт-Петербург 2021 Цель работы.Создание виртуальной топологии – графа. Написание параллельной программы на языке С, использующей операции и функции пересылки данных библиотеки MPI между соседними процессами собственного коммуникатора, связанными друг с другом виртуальными отношениями – дугами абстрактного графа. Задание. Вариант 12. Число процессов K является четным: K = 2N (1 < N < 6). В каждом процессе дано целое число A. Используя функцию MPI_Graph_create, определить для всех процессов топологию графа, в которой все процессы четного ранга (включая главный процесс) связаны в цепочку: 0 — 2 — 4 — 6 — … — (2N − 2), а каждый процесс нечетного ранга R (1, 3, …, 2N − 1) связан с процессом ранга R − 1 (в результате каждый процесс нечетного ранга будет иметь единственного соседа, первый и последний процессы четного ранга будут иметь по два соседа, а остальные — «внутренние» — процессы четного ранга будут иметь по три соседа). Пример графа на рисунке 1.  Рисунок 1. Пример топологии графа. Переслать число A из каждого процесса всем процессам-соседям. Для определения количества процессов-соседей и их рангов использовать функции MPI_Graph_neighbors_count и MPI_Graph_neighbors. Пересылку выполнять с помощью функции MPI_Sendrecv. Во всех процессах вывести полученные числа в порядке возрастания рангов переславших их процессов. Выполнение работы. Краткое описание выбранного алгоритма решения задачи: Программа запускается на нескольких процессах. Главным процессом считается процесс с рангом 0. Для начала проверяется корректность количества процессов. При некорректном значении, программа останавливается и процесс с рангом 0 выводит сообщение об ошибке. Затем объявляется и заполняется переменная А – двузначное (трехзначное) целое число процесса, в первом разряде (первых двух разрядах) которого ранг текущего процесса, а в последнем разряде случайное целое число в диапазоне от 0 до 9. Далее, подготавливаются необходимые массивы и с помощью функции MPI_Graph_create создается виртуальная топология графа согласно заданию, включающая все процессы исходного коммуникатора. Каждое неориентированное ребро неорграфа представляет собой две ориентированные дуги, соединяющие конечные вершины ребра между собой. Затем, с помощью функции MPI_Graph_neighbors_count у каждого процесса вычисляется количество соседних процессов, после чего с помощью функции MPI_Graph_neighbors заполняется массив рангов соседних вершин. Далее, выделяется результирующий буфер для чисел соседних процессов. В цикле с помощью функции MPI_Sendrecv производится одновременная передача числа А соседним процессам и прием чисел от соседних процессов, которые кладутся в результирующий буфер в порядке возрастания рангов переславших их процессов. Наконец, результирующий массив чисел соседних процессов выводится на экран каждым процессом. Формальное описание алгоритма с использованием аппарата Сетей Петри. (рис. 2).  Рисунок 2. Описание алгоритма с помощью Сетей Петри. Листинг программы (файл lab_5.c): # include # include # include # include "mpi.h" int main(int argc, char* argv[]) { int procCount, procRank; MPI_Init(&argc, &argv); MPI_Comm_size(MPI_COMM_WORLD, &procCount); MPI_Comm_rank(MPI_COMM_WORLD, &procRank); if (procCount % 2 != 0 || procCount / 2 <= 1 || procCount / 2 >= 6) { if (procRank == 0) printf("Ошибка! Запуск программы на некорректном числе процессов: %d", procCount); return 0; } srand(time(NULL) + 60 * procRank); double timeBegin = MPI_Wtime(); int A = procRank * 10 + rand() % 10; printf("Процесс %d генерирует свое число: '%02d'\n", procRank, A); MPI_Comm graphComm; int *outArcsCounts = (int*)malloc(procCount * sizeof(int)); outArcsCounts[0] = 2; for (int i = 1; i < procCount - 2; i++) { if (i % 2 == 0) outArcsCounts[i] = outArcsCounts[i - 1] + 3; else outArcsCounts[i] = outArcsCounts[i - 1] + 1; } outArcsCounts[procCount - 2] = outArcsCounts[procCount - 3] + 2; outArcsCounts[procCount - 1] = outArcsCounts[procCount - 2] + 1; int arcCount = (procCount - 1) * 2; int *arcs = (int*)malloc(arcCount * sizeof(int)); arcs[0] = 1; arcs[1] = 2; int index = 1; int offset = 0; do { arcs[++index] = offset; arcs[++index] = offset; arcs[++index] = offset + 3; arcs[++index] = offset + 4; offset += 2; } while (arcs[index] != procCount); arcs[index] -= 2; MPI_Graph_create(MPI_COMM_WORLD, procCount, outArcsCounts, arcs, 1, &graphComm); int neighborsCount; MPI_Graph_neighbors_count(graphComm, procRank, &neighborsCount); int *neighbors = (int*)malloc(neighborsCount * sizeof(int)); MPI_Graph_neighbors(graphComm, procRank, neighborsCount, neighbors); MPI_Status status; int *result = (int*)malloc(neighborsCount * sizeof(int)); for (int i = 0; i < neighborsCount; i++) { printf("\x1b[1mПроцесс %d посылает свое число: '%02d' соседу с рангом %d\x1b[0m\n", procRank, A, neighbors[i]); MPI_Sendrecv(&A, 1, MPI_INT, neighbors[i], 0, result + i, 1, MPI_INT, neighbors[i], 0, graphComm, &status); } printf("\x1b[1;31mПроцесс %d принимает результирующий набор чисел от своих соседей:", procRank); for (int i = 0; i < neighborsCount; i++) { printf(" \x1b[1;4m%02d", result[i]); } printf("\x1b[0m\n"); free(outArcsCounts); free(arcs); free(neighbors); free(result); double timeEnd = MPI_Wtime(); printf("\x1b[32mПроцесс %d завершил работу. Время, затраченное им на программу: \x1b[0m\x1b[1;43m%g\x1b[0m\n", procRank, timeEnd - timeBegin); MPI_Finalize(); return 0; } Результаты работы программы на 1…N процессах (рис. 3-6):  Рисунок 3. Пример запуска программы на четырех процессах.  Рисунок 4. Пример запуска программы на шести процессах.  Рисунок 5. Пример запуска программы на восьми процессах.  Рисунок 6. Пример запуска программы на десяти процессах. График зависимости времени выполнения программы от числа процессов (рис. 7).  Рисунок 7. График зависимости времени выполнения программы от числа процессов. По рисунку 7 можно сделать вывод, что в данном случае с ростом числа процессов время выполнения программы возрастает. Это происходит, потому что с ростом числа процессов возрастает и количество дуг графа, а, следовательно, увеличивается и число передач друг другу данных, значит, растет и время работы программы. График ускорения (эффективности) – рис. 8.  Рисунок 8. График зависимости ускорения программы от числа процессов По рисунку 8 можно сделать вывод, что в данном случае ускорение наоборот уменьшается с ростом числа процессов и программа замедляется, но чем больше процессов, тем интенсивность замедления ниже. Вывод. В ходе выполнения работы было освоено создание и использование виртуальных топологий, приобретены навыки взаимодействия между соседними процессами, абстрактно связанными между собой; была написана на языке С и запущена параллельная программа, осуществляющая пересылку данных между соседними процессами собственного коммуникатора, связанными друг с другом виртуальными отношениями – дугами абстрактного графа. Был произведен замер времени выполнения параллельных программ, исследовано ускорение, и его зависимость от числа процессов: с ростом числа процессов увеличивается и время работы программы, а, следовательно, снижается ускорение. |