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

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

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

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

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

Решение задачи поиска кратчайшего пути в обыкновенном графе с учетом веса рёбер

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

Выполнил

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

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

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

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

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

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

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

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

Тестирование проводились на компьютере со следующей конфигурацией:

ПРОЦЕССОР Intel Core i5 2500MHz Ivy Bridge

ОПЕРАТИВНАЯ ПАМЯТЬ 16Gb DDR3 1600MHz

ФИЗИЧЕСКИЙ НАКОПИТЕЛЬ OCZ-VERTEX3 (120Gb, SATA600, SSD)

ГРАФИЧЕСКИЙ ПРОЦЕССОР AMD Radeon HD 7700 (1Gb DDR5 4.6GHz)

ОПЕРАЦИОННАЯ СИСТЕМА Windows 7 Ultimate x64 (SP1)

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

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

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

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

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	0,0544	1,0000
2	0,0309	1,7627
3	0,0246	2,2153
4	0,0204	2,6607
5	0,0200	2,7151
6	0,0218	2,4954
7	0,0213	2,5541
8	0,0214	2,5446
9	0,0212	2,5689
10	0,0211	2,5801
11	0,0235	2,3119
12	0,0225	2,4204

Время

(сек)

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

Число

потоков

Ускорение

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

Число

потоков