Национальный Исследовательский Университет

МОСКОВСКИЙ ЭНЕРГЕТИЧЕСКИЙ ИНСТИТУТ

Институт автоматики и вычислительной техники

Кафедра прикладной математики

Лабораторная работа № 2

Решение задачи поиска кратчайшего пути

в обыкновенном графе с учетом веса рёбер

Курс «Параллельные системы и параллельные вычисления»

Выполнил

студент 5 курса группы А-13-08

Захаров Антон

Преподаватель

Панков Николай Александрович

Постановка задачи

Пусть дана матрица смежности графа :

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

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

Последовательный алгоритм решения

Алгоритм Флойда-Уоршелла

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

Пусть вершины графа пронумерованы от до и введено обозначение для длины кратчайшего пути от до , который кроме самих вершин , проходит только через вершины . Очевидно, что – длина (вес) ребра , если таковое существует (в противном случае его длина может быть обозначена как ).

Существует два варианта значения :

1. Кратчайший путь между , не проходит через вершину , тогда

2. Существует более короткий путь между i,\;j, проходящий через k, тогда он сначала идёт от до , а потом от до . В этом случае, очевидно,

Таким образом, для нахождения значения функции достаточно выбрать минимум из двух обозначенных значений.

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

1. for (k = 0; k < n; k++) {

2. for (i = 0; i < n; i++) {

3. for (j = 0; j < n; j++) {

4. if(M[i][j] > M[i][k] + M[k][j]) {

5. P[i][j] = P[k][j];

6. M[i][j] = M[i][k] + M[k][j];

7. } } } }

Параллельный алгоритм решения

В данной работе предложена параллельная реализация алгоритма Флойда-Уоршелла: матрица смежности и исходная матрица предшествования рассылаются на все узлы, каждый узел вычисляет по одной полосе фиксированного размера двух искомых матриц (матрицы весок кратчайших путей и матрицы предшествования). На каждой k-ой итерации происходит объединение результатов и повторная рассылка матриц узлам.

Результаты вычислительного эксперимента

Число вершин 100

Число узлов	Число исполнителей на узле	Общее число исполнителей	Время решения1 (сек)	Ускорение
1	1	1	0,14214	1,00000
1	2	2	0,09310	1,52670
1	3	3	0,05993	2,37179
1	4	4	0,04455	3,19037
2	4	8	0,03193	4,45093
3	4	12	0,02803	5,07051
4	4	16	0,02795	5,08462
5	4	20	0,02715	5,23588
6	4	24	0,02502	5,68143
7	4	28	0,02364	6,01243
8	4	32	0,02168	6,55732
9	4	36	0,01996	7,12086
10	4	40	0,01854	7,66733
11	4	44	0,01818	7,81905
12	4	48	0,01765	8,05527
13	4	52	0,01685	8,43797
14	4	56	0,01468	9,68230
15	4	60	0,01404	10,12669
16	4	64	0,01392	10,21372

Время

(сек)

Зависимость времени решения задачи от числа исполнителей

Число

исполнителей

Ускорение

Зависимость ускорения параллельного решения от числа исполнителей

Число

исполнителей

Число вершин 1000

Число узлов	Число исполнителей на узле	Общее число исполнителей	Время решения (сек)	Ускорение
1	1	1	33,69080	1,00000
1	2	2	29,90218	1,12670
1	3	3	28,03377	1,20179
1	4	4	24,94928	1,35037
2	4	8	23,22013	1,45093
3	4	12	22,15756	1,52051
4	4	16	20,86606	1,61462
5	4	20	19,63473	1,71588
6	4	24	19,12699	1,76143
7	4	28	18,58876	1,81243
8	4	32	18,33688	1,83732
9	4	36	18,20278	1,85086
10	4	40	18,00042	1,87167
11	4	44	17,74089	1,89905
12	4	48	17,59062	1,91527
13	4	52	17,47480	1,92797
14	4	56	17,39488	1,93682
15	4	60	17,35506	1,94127
16	4	64	17,31163	1,94614

Время

(сек)

Зависимость времени решения задачи от числа исполнителей

Число

исполнителей