Постановка задачи
Охватывающим деревом неориентированного графа
G называется подграф
T графа
G, который является деревом и содержит все вершины из
G. Определив вес подграфа для взвешенного графа как сумму весов входящих в подграф дуг, под
минимальным охватывающим деревом или
МОД T будем понимать охватывающее дерево минимального веса.
Пример неориентированного взвешенного графа и соответствующего ему
МОД:
Алгоритм поиска минимального охватывающего дерева во взвешенном графе носит название метода Прима (Robert Prim).
Необходимо:
- Выполнить реализацию параллельного алгоритма Прима.
- Провести вычислительные эксперименты.
- Построить теоретические оценки с учетом параметров используемой вычислительной системы.
- Сравнить полученные оценки с экспериментальными данными.
Метод решения
Последовательный алгоритм
Алгоритм начинает работу с произвольной вершины графа
s, выбираемой в качестве корня дерева, и в ходе последовательно выполняемых итераций расширяет дерево до
МОД. Пусть
VT есть множество вершин, уже включенных алгоритмом в МОД, а величины
di,
1 ≤ i ≤ N, характеризуют дуги минимальной длины от вершин, еще не включенных в дерево, до множества
VT, т.е.
(если для какой-то вершины
не существует ни одной дуги в
VT, значение
di устанавливается в ∞). В начале работы алгоритма выбирается корневая вершина
МОД s и полагается:
Действия, выполняемые на каждой итерации алгоритма Прима, состоят в следующем:
- определяются значения величин di для всех вершин, еще не включенных в состав МОД;
- выбирается вершина t графа G, имеющая дугу минимального веса до множества VT:
- вершина t включается в VT.
После выполнения
n-1 итерации методом
МОД будет сформировано. Вес этого дерева может быть получен при помощи выражения
Трудоемкость нахождения
МОД характеризуется квадратичной зависимостью от числа вершин графа
O(n2)
.
Параллельный алгоритм
Итерации метода должны выполняться последовательно и, тем самым, не могут быть распараллелены. С другой стороны, выполняемые на каждой итерации алгоритма действия являются независимыми и могут реализовываться одновременно. Так, например, определение величин
di может осуществляться для каждой вершины графа в отдельности, нахождение дуги минимального веса может быть реализовано по каскадной схеме и т.д.
Распределение данных между процессорами вычислительной системы должно обеспечивать независимость независимость перечисленных операций алгоритма Прима. В частности, это может быть реализовано, если каждая вершина графа располагается на процессоре вместе со всей связанной с вершиной информацией. Соблюдение данного принципа приводит к тому, что при равномерной загрузке каждый процессор
Pj, 1 ≤ j ≤ p , должен содержать:
- набор вершин
- соответствующий этому набору блок из k величин
- вертикальную полосу матрицы смежности графа G из k соседних столбцов
- общую часть набора Vj и формируемого в процессе вычислений множества вершин VT
Базовой подзадачей в параллельном алгоритме Прима может служить процедура вычисления блока значений
Δj для вершин
Vj матрицы смежности
A графа
G.
Общая схема параллельного выполнения алгоритма Прима:
- определяется вершина графа, имеющая дугу минимального веса до множества вершин уже включенных в дерево; для такого набора вершин необходимо осуществить поиск минимума по величинам di, имеющихся на каждом из процессоров, и выполнить сборку полученных значений на одном процессоре;
- номер выбранной вершины передается всем процессорам;
-
обновляются наборы величин di с учетом добавления новой вершины.
В ходе параллельных вычислений между процессорами выполняются два типа взаимодействия - сбор данных от всех процессоров на одном и передача сообщения от одного ко всем остальным.
Анализ эффективности
Общий анализ сложности параллельного алгоритма Прима даёт идеальные
показатели эффективности:
В ходе вычислений в зависимости от количества выбранных вершин вычислительная
нагрузка на процессоры может различаться. Но в общем случае такие ситуации
достаточно редку.
Для уточнения полученных показателей эффективности оценим более точно
количество выполненных операций и затраты на передачу данных между
процессами.
На каждом шаге параллельный алгоритм выбирает вершину с минимальным
расстоянием до строящегося дерева и корректирует веса di для каждой вершины.
Количество операций при каждой из этих процедур ограничено числом 
. Поэтому на выполнение n итераций
алгоритм затратит следующее время ( r - время на выполнение элементарной
операции ):
Сборка данных на одном процессоре может быть выполнена за 
итераций.
Следовательно, на передачу данных от всех процессоров системы корневому будет
затрачено время:
где a - латентность сети передачи данных, B - пропусная способность сети, w -
размер одного элемента данных в байтах.
Операция рассылки одного элемента данных требует операций и может быть выполнена
за время
Следовательно, суммарное время работы алгоритма может быть представлено
соотношением:
Это выражение показывает, что при больших n время работы параллельного
алгоритма будет определяться квадратичной частью выражения и ускорение будет
близко к идеальному. При малых же n ускорение будет определятся линейной частью
выражения и значение ускорения будет неудволетворительно.
Всё это и подтверждается численными экспериментами.
Результаты вычислительных экспериментов
Вычислительные эксперименты для оценки эффективности параллельного алгоритма Прима проводились при следующих условиях и оборудовании:
- Процессор - Intel Core 2 Duo CPU E6550, 2.33GHz
- Память - 4Gb RAM
- Операционная система - Microsoft Windows 7
- Компилятор - MS Visual Studio 2005
- Длительность τ базовой скалярной операции - 0/43 nsec
- Параметры передачи между процессами на одной машине: латентность α - 0.00000008 sec, пропускная способность β - 920,949 Mb/sec
- Параметры сети передачи данных: латентность α - 0.00012 sec, пропускная способность β - 36Mb/sec
Об авторах
Работу выполнили студенты группы 84-09, факультета ВМК Красичков Евгений и Пушкова Ольга.
