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

Московский Энергетический Институт (Технический Университет)

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

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

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

по дисциплине «Параллельные системы и параллельное программирование»

тема: «Поиск минимального оставного дерева с использованием нитевого распараллеливания.»

Выполнил:

Машеров Д.Е.

А-13-08

Москва

2012 г.

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

Дана граф, требуется найти минимальное оставное дерева этого графа.

Охватывающим деревом (или остовом ) неориентированного графа G называется подграф T графа G, который является деревом и содержит все вершины из G. Определив вес подграфа для взвешенного графа как сумму весов входящих в подграф дуг, под минимально охватывающим деревом (МОД) T понимается охватывающее дерево минимального веса.

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

Используется алгоритм Прима.

Алгоритм начинает работу с произвольной вершины графа, выбираемой в качестве корня дерева, и в ходе последовательно выполняемых итераций расширяет конструируемое дерево до МОД. Пусть есть множество вершин, уже включенных алгоритмом в МОД, а величины , 1<= <=n, характеризуют дуги минимальной длины от вершин, еще не включенных в дерево, до множества , т.е.

(если для какой-либо вершины не существует ни одной дуги в , значение устанавливается равным ). В начале работы алгоритма выбирается корневая вершина МОД s и полагается ={s}, =0.

Действия, выполняемые на каждой итерации алгоритма Прима, состоят в следующем:

• определяются значения величин di для всех вершин, еще не включенных в состав МОД;

• выбирается вершина t графа G, имеющая дугу минимального веса до множества ;

• вершина t включается в .

После выполнения n-1 итерации метода МОД будет сформировано. Вес этого дерева может быть получен при помощи выражения

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

Итерации метода должны выполняться последовательно и, тем самым, не могут быть распараллелены. С другой стороны, выполняемые на каждой итерации алгоритма действия являются независимыми и могут реализовываться одновременно.

Каждому потоку сопоставляется свой набор вершин графа.

На каждой итерации потоки находят вершину t и дугу на своем наборе вершин. После чего веса этих дуг сравниваются и находится дуга с минимальным весом уже во всем графе. Вершина, инцидентая найденной дуге, включается в множество .

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

1. Количество вершин графа: 5 000

1. Количество вершин графа: 10 000