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

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

Под графом G понимается упорядоченная пара (V,E), где V-множество вершин, а E-множество пар вершин(ребра).В графе каждому ребру может быть приписана некоторая хактеристика, выражаемая неотрицательным числом,-вес ребра.Граф в общем случае будем считать ориентированным. В качестве решения задачи поиска минимальных путей на графе можно использовать алгоритм Флойда.Его реализация и была одной из задач данной работы.

Т.о необходимо разработать параллельную и последовательную программу для выполнения алгоритма Флойда. Провести анализ эффективности разработанной параллельной программы, провести эксперимент: определить время выполнения параллельной программы и полученное ускорения, а затем сравнить экспериментальные данные с данными об эффективности, полученными аналитически.

Метод решения

Как уже было ранее сказанно, для нахождения минимальных путей будем использовать алгоритм Флойда. На вход алгоритм получает информацию об исходгом графе,который будем представлять в виде матрицы смежности А.На выходе алгоритм преобразует исходную матрицу в матрицу минимальных путей. Сложность метода, предложенного Флойдом имеет порядок n^3. Общая схема последовательного алгоритма:

for (k = 0; k < n; k++)

for (i = 0; i < n; i++)

for (j = 0; j < n; j++)

A[i,j] = min(A[i,j],A[i,k]+A[k,j]);

Реализация операции определения минимума должна учитывать способ указания в матрице не существующих дуг.

Параллельная схема

Более эффективный способ алгоритма может состоять в одновременном выполнении нескольких операций обновления значений матрицы A. Покажем корректность такого способа организации параллелизма. Покажем, что на итерации k не происходит изменения элементов A[i,k] и A[k,j] ни для одной пары индексов (i,j). Рассмотрим выражение, по которому происходит изменение элементов матрицы A:

A[i,j] ← min (A[i,j], A[i,k] + A[k,j]).

Для i=k получим A[k,j] ← min (A[k,j], A[k,k] + A[k,j]), но тогда значение A[k,j] изменится, тк A[k,j]=0

Для j=k получим A[i,k] ← min (A[i,k], A[i,k] + A[k,k]),

но тогда значение A[k,j] изменится, тк A[k,j]=0

Это и показывает неизменность значений А[i,k]

Т.о параллельный алгоритм Флойда заключается в том, что на k-й итерации мы отсылаем k-ю строку всем процессам, а затем каждый процесс выполняет последовательный алгоритм Флойда для полосы матрицы смежности,одновременно обновляя значение матрицы.

Анализ эффективности

Общая трудоёмкость последовательного алгоритма равна n³. Для параллельного алгоритма на отдельной итерации каждый процессор выполняет обновление элементов матрицы А. Всего в подзадачах n²/p таких элементов, число итераций алгоритма равно n, таким образом, показатели ускорения и эффективности параллельного алгоритма Флойда имеют вид (p – число процессоров):

S_p = n³/(n³/p) = p,

E_p = n³/(p(n³⁄p)) = 1.

Общий анализ сложности дает идеальные показатели эффективности параллельных вычислений.

Коммуникационная операция, выполняемая на каждой итерации алгоритма Флойда, состоит в передаче одной из строк матрицы D всем процессорам вычислительной системы. Выполнение такой операции может быть выполнено за log₂ p шагов.

Общая длительность выполнения коммуникационных операций:

T_p(comm) = n log₂ p (α + wn/β),

где α – латентность сети передачи данных, β – пропускная способность сети, w – размер элемента матрицы в байтах.

Общее время выполнения параллельного алгоритма Флойда:

T_p = n²(n/p) τ + n log₂ p (α + wn/β),

где τ есть время выполнения операции выбора минимального значения.

Демонстрация

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

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

Процессор:Intel(R) Core(TM)2 Quad CPU 2.40 GHz
2.00 Gb RAM

В результате экспериментов выло определенно т=0.04277*10^(-6), латентность 0.000004 сек, пропусная способность 60 Мб/сек

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

Время выполнения:
Количество вершин графа	Последовательный алгоритм	Параллельный алгоритм
		2 процессора			4 процессора
		Время Теор	Время	Ускорение	Время Теор	Время	Ускорение
300	1.2800	0.592	0.6440	1.9875	0.29	0.3607	3.5486
500	5.7780	2.72	2.9278	1.9735	1.36	1.5480	3.7325
700	16.1870	7.39	8.1228	1.9927	3.72	4.1388	3.9110
1000	47.4600	21.49	23.8135	1.9929	10.72	12.5903	3.7696
1500	161.0710	76.63	80.6261	1.9977	36.145	41.5459	3.8769

Теоретическое ускорение алгоритма =р-числу процессоров. Т.е в данном случае теоретическое ускорение 2 и 4 соответсвенно для двух и четырех процессоров. Результаты эксперимента очень близко приблизились к теоретическому и подтвердили теоретическое обоснование.

Об авторах

Авторы работы:

Косарева Елена гр 8409
Зак Дмитрий гр 8410