Решение задачи поиска кратчайшего пути в обыкновенном графе с учетом веса рёбер (Захаров) (Лабораторная работа 2), страница 2
Описание файла
Файл "Решение задачи поиска кратчайшего пути в обыкновенном графе с учетом веса рёбер (Захаров)" внутри архива находится в папке "Лабораторная работа 2". Документ из архива "Лабораторная работа 2", который расположен в категории "". Всё это находится в предмете "параллельные системы и параллельные вычисления" из 9 семестр (1 семестр магистратуры), которые можно найти в файловом архиве НИУ «МЭИ» . Не смотря на прямую связь этого архива с НИУ «МЭИ» , его также можно найти и в других разделах. Архив можно найти в разделе "лабораторные работы", в предмете "параллельные системы и параллельные вычисления" в общих файлах.
Онлайн просмотр документа "Решение задачи поиска кратчайшего пути в обыкновенном графе с учетом веса рёбер (Захаров)"
Текст 2 страницы из документа "Решение задачи поиска кратчайшего пути в обыкновенном графе с учетом веса рёбер (Захаров)"
Ускорение
Зависимость ускорения параллельного решения от числа исполнителей
Число
исполнителей
Число вершин 5000
| Число | Число | Общее число исполнителей | Время | Ускорение |
| 1 | 1 | 1 | 4258,69080 | 1,00000 |
| 1 | 2 | 2 | 3365,79638 | 1,26528 |
| 1 | 3 | 3 | 3155,48778 | 1,34961 |
| 1 | 4 | 4 | 3032,89401 | 1,40417 |
| 2 | 4 | 8 | 2613,66307 | 1,62940 |
| 3 | 4 | 12 | 2494,06053 | 1,70753 |
| 4 | 4 | 16 | 2348,68895 | 1,81322 |
| 5 | 4 | 20 | 2210,08987 | 1,92693 |
| 6 | 4 | 24 | 2152,93922 | 1,97808 |
| 7 | 4 | 28 | 2092,35569 | 2,03536 |
| 8 | 4 | 32 | 2064,00386 | 2,06332 |
| 9 | 4 | 36 | 2048,90946 | 2,07852 |
| 10 | 4 | 40 | 2026,13181 | 2,10188 |
| 11 | 4 | 44 | 1996,91874 | 2,13263 |
| 12 | 4 | 48 | 1980,00442 | 2,15085 |
| 13 | 4 | 52 | 1966,96728 | 2,16511 |
| 14 | 4 | 56 | 1957,97176 | 2,17505 |
| 15 | 4 | 60 | 1953,48963 | 2,18004 |
| 16 | 4 | 64 | 1948,60094 | 2,18551 |
Время
(сек)
Зависимость времени решения задачи от числа исполнителей
Число
исполнителей
Ускорение
Зависимость ускорения параллельного решения от числа исполнителей
Число
исполнителей
Приложение. Код программы.
#include
#include
#include
#include
#include
#include
#include
#include
// --- Настройки программы ---
// Включение режима отладки
#define DEBUG
// Число запусков теста
#define TEST_COUNT 5
// Ограничения на генерируемые веса рёбер
#define MIN_WEIGHT 1
#define MAX_WEIGHT 9
// Связность графа
#define DENSITY 0.80
// Число вершин графа
#define V_SIZE 100
// Тип числа вершин в графе
typedef int vsize;
// Тип весов рёбер графа
typedef int weight;
// Путь к файлу логов
#define LOG_PATH "log.txt"
// Определение бесконечного веса ребра
#define INF 100
// --- Настройки MPI ---
// Индекс главного (управляющего) процесса
#define MAIN_PROC 0
// Тип числа вершин в графе
#define MPI_VSIZE MPI_INT
// Тип весов рёбер графа
#define MPI_WEIGHT MPI_INT
weight get_random(weight a, weight b, float density, weight inf);
vsize gen_random(vsize a, vsize b);
void print_log(const char *message, ...);
void print_err(const char *message);
int main(int argc, char *argv[])
{
// Число процессов и номер текущего процесса
int procNum = 1;
int procRank = MAIN_PROC;
// Время начала работы главного процесса
double startTime;
vsize i, j, k, p, h;
// Число вершин графа G=(V,E), |V|=n
vsize n = V_SIZE;
// Номера начальной и конечной вершин искомого пути
vsize Vstart, Vend;
MPI_Init(&argc, &argv);
MPI_Comm_size(MPI_COMM_WORLD, &procNum);
MPI_Comm_rank(MPI_COMM_WORLD, &procRank);
MPI_Status status;
// Пути к файлам матрицы смежности, запросов и результата
const char *M_path = "M.txt";
const char *Q_path = "query.txt";
const char *R_path = "result.txt";
FILE *Mstream;
FILE *Qstream;
FILE *Rstream;
// Результаты замеров времени работы главного процесса
double *results;
vsize *Wrows = NULL;
vsize *Nrows = NULL;
if(procRank == MAIN_PROC)
{
// Выделение памяти под результаты замеров времени
results = (double *) malloc(TEST_COUNT * sizeof(double));
if(results == NULL)
{
print_err("Не удалось выделить память");
MPI_Abort(MPI_COMM_WORLD, MPI_ERR_OTHER);
return 0;
}
}
// Запускаем тест TEST_COUNT раз
for(h = 0; h < TEST_COUNT; h++)
{
MPI_Barrier(MPI_COMM_WORLD);
if(procRank == MAIN_PROC)
{
// Фиксируем время начала работы главного процесса
startTime = MPI_Wtime();
// Пытаемся открыть файлы с матрицей смежности и запросов
Mstream = fopen(M_path, "r");
Qstream = fopen(Q_path, "r");
// Обработка ошибок при открытии файлов
if(Mstream == NULL || Qstream == NULL)
{
if((Mstream != NULL && fclose(Mstream))
|| (Qstream != NULL && fclose(Qstream)))
{
print_log("[ERROR] Не удалось закрыть файлы исходных данных");
MPI_Abort(MPI_COMM_WORLD, MPI_ERR_OTHER);
free(results);
return 0;
}
srand((unsigned int) time(NULL));
if(n <= 0)
{
print_log("[ERROR] Не удалось сгенерировать файл с матрицей смежности: Не верно задана размерность матрицы");
MPI_Abort(MPI_COMM_WORLD, MPI_ERR_OTHER);
free(results);
return 0;
}
Mstream = fopen(M_path, "w");
Qstream = fopen(Q_path, "w");
if(Mstream == NULL || Qstream == NULL)
{
print_err("Не удалось сгенерировать файлы");
MPI_Abort(MPI_COMM_WORLD, MPI_ERR_OTHER);
free(results);
return 0;
}
// Записываем число вершин графа
if(fprintf(Mstream, "%d\n", n) < 0)
{
print_err("Не удалось сгенерировать файлы");
MPI_Abort(MPI_COMM_WORLD, MPI_ERR_OTHER);
fclose(Mstream);
fclose(Qstream);
free(results);
return 0;
}
vsize Msize = n * n;
weight *M = (weight*) malloc(Msize * sizeof(weight*));
if(M == NULL)
{
print_err("Не удалось выделить память");
MPI_Abort(MPI_COMM_WORLD, MPI_ERR_OTHER);
fclose(Mstream);
fclose(Qstream);
free(results);
return 0;
}
for(i = 0; i < n; i++)
{
for(j = 0; j < n; j++)
{
if(j < i)
M[i*n + j] = M[j*n + i];
else if(j == i)
M[i*n + j] = 0;
else
M[i*n + j] = get_random(MIN_WEIGHT, MAX_WEIGHT, (float) DENSITY, INF);
}
}
for(i = 0; i < n; i++)
{
for(j = 0; j < n - 1; j++)
{
if(fprintf(Mstream, "%d ", M[i*n + j]) < 0)
{
print_err("Не удалось сгенерировать файлы");
MPI_Abort(MPI_COMM_WORLD, MPI_ERR_OTHER);
fclose(Mstream);
fclose(Qstream);
free(results);
free(M);
return 0;
}
}
if(fprintf(Mstream, "%d\n", M[(i + 1) * n - 1]) < 0)
{
print_err("Не удалось сгенерировать файлы");
MPI_Abort(MPI_COMM_WORLD, MPI_ERR_OTHER);
fclose(Mstream);
fclose(Qstream);
free(results);
free(M);
return 0;
}
}
free(M);
vsize r1, r2;
do
{
r1 = gen_random(1, n);
r2 = gen_random(1, n);
} while(n > 1 && r1 == r2);
if(fprintf(Qstream, "%d -> %d", r1, r2) < 0)
{
print_err("Не удалось сгенерировать файлы");
MPI_Abort(MPI_COMM_WORLD, MPI_ERR_OTHER);
fclose(Mstream);
fclose(Qstream);
free(results);
return 0;
}
if(fclose(Mstream) || fclose(Qstream))
{
print_err("Не удалось закрыть файлы");
MPI_Abort(MPI_COMM_WORLD, MPI_ERR_OTHER);
free(results);
return 0;
}
// Не учитываем время, затраченное на генерацию файлов
startTime = MPI_Wtime();
Mstream = fopen(M_path, "r");
Qstream = fopen(Q_path, "r");
#ifdef DEBUG
if(Mstream == NULL || Qstream == NULL)
{
print_err("Не удалось открыть файлы");
MPI_Abort(MPI_COMM_WORLD, MPI_ERR_OTHER);
free(results);
return 0;
}
#endif // DEBUG
}
#ifdef DEBUG
// Считываем число вершин в графе
if(fscanf(Mstream, "%d\n", &n) <= 0)
{
print_log("[ERROR] Не удалось считать число вершин графа");
MPI_Abort(MPI_COMM_WORLD, MPI_ERR_OTHER);
fclose(Mstream);
fclose(Qstream);
free(results);
return 0;
}
// Проверка числа вершин
if(n <= 0)
{
print_log("[ERROR] Не верно задано число вершин графа: |V| = n должно быть больше нуля");
MPI_Abort(MPI_COMM_WORLD, MPI_ERR_OTHER);
fclose(Mstream);
fclose(Qstream);
free(results);
return 0;
}
// Чтение начальной и конечной вершин искомого пути
if(fscanf(Qstream, "%d -> %d", &Vstart, &Vend) <= 0)
{
print_log("[ERROR] Не удалось считать число вершин графа");
MPI_Abort(MPI_COMM_WORLD, MPI_ERR_OTHER);
fclose(Mstream);
fclose(Qstream);
free(results);
return 0;
}
Vstart--; Vend--;
// Проверка начальной и конечной вершин искомого пути
if(Vstart < 0 || Vend = n || Vend >= n)
{
print_log("[ERROR] Не верно заданы начальная и конечная вершины искомого пути");
MPI_Abort(MPI_COMM_WORLD, MPI_ERR_OTHER);
fclose(Mstream);
fclose(Qstream);
free(results);
return 0;
}
#else
fscanf(Mstream, "%d\n", &n);
fscanf(Qstream, "%d -> %d", &Vstart, &Vend);
Vstart--; Vend--;
#endif // DEBUG
fclose(Qstream);
// Делим строки матрицы W между процессами
Wrows = (vsize *) malloc(procNum * sizeof(vsize));
Nrows = (vsize *) malloc(procNum * sizeof(vsize));
p = (vsize) floor(double(n / procNum));
for(i = 0; i < procNum; i++)
{
Wrows[i] = p;
Nrows[i] = i * p;
}
p = n % procNum;
for(i = 0; p != 0; p--)
{
Wrows[i]++;
for(j = i + 1; j < procNum; j++)
Nrows[j]++;
i = (i < procNum) ? i + 1 : 0;
}
// Запись информации о группе тестов в лог-файл
if(h == 0)
{
print_log("----------------------------------------------\n
Число процессоров %d\n
Число вершин %d\n
Память %f МБ\n\n",
procNum, n,
(double) (n*n*sizeof(weight) + n*n*sizeof(vsize))) / 1024.0 / 1024.0;
#ifdef DEBUG
print_log("[DEBUG] Распределение строк матрицы M между процессами:\n{");
for(i = 0; i < procNum - 1; i++)
print_log("%d (%d), ", Wrows[i], Nrows[i]);
print_log("%d (%d)}\n\n", Wrows[procNum - 1], Nrows[procNum - 1]);
#endif // DEBUG
}
}
vsize Wr;
vsize Wn;
if(procRank == MAIN_PROC)
{
Wr = Wrows[MAIN_PROC];
Wn = Nrows[MAIN_PROC];
}
// Рассылка всем исполнителям числа вершин в графе и числа обрабатываемых строк матрицы W
MPI_Bcast(&n, 1, MPI_VSIZE, MAIN_PROC, MPI_COMM_WORLD);
MPI_Scatter(Wrows, 1, MPI_VSIZE, &Wr, 1, MPI_VSIZE, MAIN_PROC, MPI_COMM_WORLD);
MPI_Scatter(Nrows, 1, MPI_VSIZE, &Wn, 1, MPI_VSIZE, MAIN_PROC, MPI_COMM_WORLD);
vsize Msize = n * n;
vsize Psize = n * n;
vsize Ms = Wr * n;
vsize Ps = Wr * n;
// Матрица смежности
weight *M = (weight*) malloc(Msize * sizeof(weight));
// Матрица предшествования
vsize *P = (vsize*) malloc(Psize * sizeof(vsize));
#ifdef DEBUG
if(M == NULL || P == NULL)
{
print_err("Не удалось выделить память");
MPI_Abort(MPI_COMM_WORLD, MPI_ERR_OTHER);
fclose(Mstream);
free(results);
return 0;
}
#endif // DEBUG
if(procRank == MAIN_PROC)
{
// Чтение матрицы смежности
for(i = 0; i < Msize; i++)
fscanf(Mstream, "%d", &M[i]);
fclose(Mstream);
// Инициализация матрицы предшествования
for(i = 0; i < n; i++)
{
for(j = 0; j < n; j++)
P[i*n + j] = (M[i*n + j] == INF) ? -1 : i;
}
}
// Параллельная реализация алгоритма Флойда-Уоршелла
for(k = 0; k < n; k++)
{
MPI_Bcast(M, Msize, MPI_WEIGHT, MAIN_PROC, MPI_COMM_WORLD);
MPI_Bcast(P, Psize, MPI_VSIZE, MAIN_PROC, MPI_COMM_WORLD);
for(i = Wn; i < Wn + Wr; i++)
{
for(j = 0; j < n; j++)
{
if(M[i*n + j] > (M[i*n + k] + M[k*n + j]))
{
P[i*n + j] = P[k*n + j];
M[i*n + j] = M[i*n + k] + M[k*n + j];
}
}
}
// Отправка фрагментов матриц на главный процесс
if(procRank != MAIN_PROC)
{
MPI_Send(&M[Wn * n], Ms, MPI_WEIGHT, MAIN_PROC, 0, MPI_COMM_WORLD);
MPI_Send(&P[Wn * n], Ps, MPI_VSIZE, MAIN_PROC, 0, MPI_COMM_WORLD);
}
else
{
// Приём фрагментов матриц на главном процессе
for(p = 0; p < procNum; p++)
{
if(p != MAIN_PROC)
{
MPI_Recv(&M[Nrows[p] * n], Wrows[p] * n, MPI_WEIGHT, p, MPI_ANY_TAG, MPI_COMM_WORLD, &status);
MPI_Recv(&P[Nrows[p] * n], Wrows[p] * n, MPI_VSIZE, p, MPI_ANY_TAG, MPI_COMM_WORLD, &status);
}
}
}
}
#ifdef DEBUG
if(procRank == MAIN_PROC && !h)
{
print_log("[DEBUG] Матрица весов кратчайших путей:\n");
for(i = 0; i < n; i++)
{
for(j = 0; j < n - 1; j++)
{
if(M[i*n + j] >= INF)
print_log("- ");
else
print_log("%d ", M[i*n + j]);
}
if(M[(i + 1)*n - 1] >= INF)
print_log("-\n");
else
print_log("%d\n", M[(i + 1)*n - 1]);
}
print_log("\n[DEBUG] Матрица предшествования:\n");
for(i = 0; i < n; i++)
{
for(j = 0; j < n - 1; j++)
{
if(P[i*n + j] == -1)
print_log("- ");
else
print_log("%d ", P[i*n + j] + 1);
}
if(P[(i + 1)*n - 1] == -1)
print_log("-\n");
else
print_log("%d\n", P[(i + 1)*n - 1] + 1);
}
print_log("\n");
}
#endif // DEBUG
if(procRank == MAIN_PROC)
{
// Вершины искомого пути (в обратном порядке)
vsize *path = (vsize*) malloc(n * sizeof(vsize));
i = 0;
path[i] = Vend;
do
{
i++;
if(i < n)
path[i] = P[Vstart*n + path[i-1]];
} while(i < n && path[i] != Vstart);
// Запись результата в файл
Rstream = fopen(R_path, "w");
if(M[Vstart*n + Vend] >= INF)
{
fprintf(Rstream, "Путь из вершины %d в вершину %d не существует\n", Vstart + 1, Vend + 1);
}
else
