Новости
О Центре
Кластер
Обучение
Основной курс по параллельному программированию
Учебные курсы
Магистратура
Дополнительное образование
Работы студентов
Библиотека
Исследования
Конференции
Полезные ссылки
NVIDIA
Контакты
О сайте
Имя:
Пароль:
запомнить:
Забыли пароль? Регистрация

Алгоритм Прима

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

Охватывающим деревом неориентированного графа 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, факультета ВМК Красичков Евгений и Пушкова Ольга.

Новости

22.10.2012
04.09.2012
05.04.2012
06.03.2012
02.03.2012