Лабораторная работа 2 (Решение задачи поиска кратчайшего пути в обыкновенном графе с учетом веса рёбер (Захаров))

Посмотреть архив целиком

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

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

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

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

Лабораторная работа № 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


Время

(сек)

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

Число

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


Ускорение

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

Число

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







Число вершин 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 <stdio.h>

#include

#include

#include

#include

#include

#include

#include <mpi.h>



// --- Настройки программы ---


// Включение режима отладки

#define DEBUG



Случайные файлы

Файл
153643.rtf
sociologia.doc
91797.rtf
30819.rtf
70765.rtf




Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.