Необходимо выполнить реализацию параллельного алгоритма Прима.
Необходимо провести вычислительные эксперименты.
Необходимо построить теоретические оценки с учетом параметров используемой вычислительной системы.
Сравнить полученные оценки с экспериментальными данными.
Теоретическая часть
Каркас неориентированного графа
Оптимальным каркасом взвешенного графа называется каркас, минимизирующий некоторую функцию от весов входящих в него ребер. Чаще всего в качестве такой функции выступает сумма весов ребер, реже — произведение. Оптимальный каркас еще называют кратчайшей связывающей сетью для данного графа.
Задача о построении кратчайшей связывающей сети встречается в различных приложениях достаточно часто.
Задача об оптимальном каркасе.
Задача об оптимальном каркасе (стягивающем дереве) состоит в следующем. Дан обыкновенный граф G=(V,E) и весовая функция на множестве ребер u: V R. Вес множества X ? E определяется как сумма весов составляющих его ребер. Требуется в графе G найти каркас минимального веса. В этом разделе будем предполагать, что граф G связен, так что решением задачи всегда будет дерево. Для решения задачи об оптимальном каркасе известно несколько алгоритмов. Рассмотрим два из них.
Алгоритм Прима.
В алгоритме Прима на каждом шаге рассматривается частичное решение задачи, представляющее собой дерево. Вначале это дерево состоит из единственной вершины, в качестве которой может быть выбрана любая вершина графа. Затем к дереву последовательно добавляются ребра и вершины, пока не получится остовное дерево, т.е. каркас. Для того чтобы из текущего дерева при добавлении нового ребра опять получилось дерево, это новое ребро должно соединять вершину дерева с вершиной, еще не принадлежащей дереву. Такие ребра будем называть подходящими относительно рассматриваемого дерева. В алгоритме Прима применяется следующее правило выбора: на каждом шаге из всех подходящих ребер выбирается ребро наименьшего веса. Это ребро вместе с одной новой вершиной добавляется к дереву. Если обозначить через U и F множества вершин и ребер строящегося дерева, то алгоритм Прима можно представить следующим образом.
Общее описание схемы программной разработки
Алгоритм № 1
Пусть граф состоит из N вершин,
ПОКА в каркасе не будет N вершин
{
Каждому процессу выделяются блоки матрицы.
На этих блоках каждый из процесс ищет минимальное по весу ребро, соединяющее некаркасную вершину с каркасной.
Каждый процесс отправляет результат первому процессу.
Первый процесс ищет минимум среди всех полученных ребер и результат отправляет всем остальным процессам.
}
Алгоритм № 2
Заводиться дополнительный массив b,длины N. Где пара ( i , b[i] ) есть ребро минимального веса и не принадлежащее каркасу, приводящее из вершины с номером i в вершину в вершину с номером b[i], где b[i] принадлежит каркасу.
Каждому процессу выделяются сегменты массива b.
ПОКА в каркасе не будет N вершин
{
На этих сегментах каждый из процессов ищет минимальное по весу ребро, соединяющее некаркасную вершину с каркасной.
Каждый процесс отправляет результат первому процессу.
Первый процесс ищет минимум среди всех полученных ребер и результат отправляет всем остальным процессам.
Каждый процесс обновляет массив b.
}
Последовательный код программы
Алгоритм № 1
Алгоритм № 2
Параллельный код программы
Алгоритм № 1
Алгоритм № 2
Анализ эффективности
Алгоритм № 1
Общий анализ сложности параллельного алгоритма Прима для нахождения минимального охватывающего дерева дает идеальные показатели эффективности параллельных вычислений:
При выполнении вычислений на отдельной итерации параллельного алгоритма Прима каждый процессор определяет номер ближайшей вершины из своего болка до охватывающего дерева. Этот поиск производиться самым безхитростным образом, то есть просматриваются все пары вершин (x,y) c x принадлежащему каркасу, а у остальному графу. Если в каркасе "k" вершин то до промотреть (n-k) ребер. Причем это делается для n/p вершинах
Как результат, с учетом общего количества итераций n время выполнения вычислительных операций параллельного алгоритма Прима может быть оценено при помощи соотношения:
Операция сбора данных от всех процессоров на одном из процессоров может быть произведена за O(log2p) итераций, при этом общая оценка длительности выполнения передачи данных определяется выражением:
где – alpha латентность сети передачи данных, beta – пропускная способность сети, а w есть размер одного пересылаемого элемента данных в байтах (коэффициент 3 в выражении соответствует числу передаваемых значений между процессорами – длина минимальной дуги и номера двух вершин, которые соединяются этой дугой).
Коммуникационная операция передачи данных от одного процессора всем процессорам вычислительной системы также может быть выполнена за ⌈log2p⌉ итераций при общей оценке времени выполнения вида:
С учетом всех полученных соотношений общее время выполнения параллельного алгоритма Прима составляет:
Алгоритм № 2
Общий анализ сложности параллельного алгоритма Прима для нахождения минимального охватывающего дерева дает идеальные показатели эффективности параллельных вычислений:
При выполнении вычислений на отдельной итерации параллельного алгоритма Прима каждый процессор определяет номер ближайшей вершины из своего блока до охватывающего дерева и осуществляет корректировку расстояний di после расширения МОД. Количество выполняемых операций в каждой из этих вычислительных процедур ограничивается сверху числом вершин, имеющихся на процессорах, т.е. величиной ⌈n/p⌉. Как результат, с учетом общего количества итераций n время выполнения вычислительных операций параллельного алгоритма Прима может быть оценено при помощи соотношения:
Операция сбора данных от всех процессоров на одном из процессоров может быть произведена за O(log2p) итераций, при этом общая оценка длительности выполнения передачи данных определяется выражением:
где – alpha латентность сети передачи данных, beta – пропускная способность сети, а w есть размер одного пересылаемого элемента данных в байтах (коэффициент 3 в выражении соответствует числу передаваемых значений между процессорами – длина минимальной дуги и номера двух вершин, которые соединяются этой дугой).
Коммуникационная операция передачи данных от одного процессора всем процессорам вычислительной системы также может быть выполнена за ⌈log2p⌉ итераций при общей оценке времени выполнения вида:
С учетом всех полученных соотношений общее время выполнения параллельного алгоритма Прима составляет:
Результаты
Эксперимент проводился на ПК со следующими характеристиками:
Intel Core 2 Duo, 2.33 MHz
Microsoft Windows 7
Компилятор MS Visual Studio 2005
Пропускной способности сети - 36 Мбайт/с.
величина w равна 4 байтам.
t – 2.4 нсек
Латентность: 0.00015 с
