Algorithm level

Difference between revisions of "Boruvka's algorithm"

From Algowiki
Jump to navigation Jump to search
 
(49 intermediate revisions by 2 users not shown)
Line 26: Line 26:
 
=== Computational kernel of the algorithm ===
 
=== Computational kernel of the algorithm ===
  
Основными операциями являются:
+
The basic operations of the algorithm are:
# Поиск минимального по весу исходящего ребра в каждом фрагменте.
+
# Search for the outgoing edge with the least weight in each fragment.
# Объединение фрагментов.
+
# Merging fragments.
  
 
=== Macro structure of the algorithm ===
 
=== Macro structure of the algorithm ===
  
В задаче требуется указать в данном связном взвешенном графе дерево, соединяющее все его вершины и имеющее наименьший возможный суммарный вес рёбер.  
+
For a given connected undirected graph, the problem is to find the tree that connects all the vertices and has the minimum total weight.  
  
Классический пример (из статьи Борувки) – спроектировать наиболее дешёвую электрическую сеть, зная стоимость устройства каждого участка электрической линии.
+
The classical example (taken from Borůvka's paper) is to design the cheapest electrical network if the price for each piece of electric line is known.
  
Пусть задан связный граф <math>G=(V,E)</math> с вершинами <math>V = ( v_{1}, v_{2}, ..., v_{n} )</math> и рёбрами <math>E = ( e_{1}, e_{2}, ..., e_{m} )</math>. Каждому ребру <math>e \in E</math> приписан вес <math>w(e)</math>.  
+
Let <math>G=(V,E)</math> be a connected graph with the vertices <math>V = ( v_{1}, v_{2}, ..., v_{n} )</math> and the edges <math>E = ( e_{1}, e_{2}, ..., e_{m} )</math>. Each edge <math>e \in E</math> is assigned the weight <math>w(e)</math>.  
  
Требуется построить дерево <math>T^* \subseteq E</math>, связывающее все вершины, и имеющее наименьший возможный вес среди всех таких деревьев:
+
It is required to construct the tree <math>T^* \subseteq E</math> that connects all the vertices and has the least possible weight among all such trees:
  
<math> w(T^* )= \min_T( w(T)) </math>
+
<math> w(T^* )= \min_T( w(T)) </math>.
  
где вес множества рёбер есть сумма их весов:
+
The weight of a set of edges is the sum of their weights:
  
 
<math>w(T)=\sum_{e \in T} (w(T))</math>
 
<math>w(T)=\sum_{e \in T} (w(T))</math>
  
Если граф <math>G</math> не является связным, то дерева, связывающего все вершины, не существует.  
+
If <math>G</math> is not connected, then there is no tree connecting all of its vertices.
  
В этом случае необходимо найти минимальной остовное дерево для каждой компоненты связности <math>G</math>. Набор таких деревьев называется минимальным остовным лесом (сокращённо MSF – Minimum Spanning Forest).
+
In this case, it is required to find the minimum spanning tree for each connected component of <math>G</math>. The collection of such trees is called the minimum spanning forest (abbreviated as MSF).
  
==== Вспомогательный алгоритм: система непересекающихся множеств (Union-Find)====
+
==== Auxiliary algorithm: system of disjoint sets (Union-Find)====
  
Во всех алгоритмах решения задачи требуется отслеживать, каким уже построенным фрагментам дерева принадлежат те или иные вершины графа. Для этого используется структура данных «система непересекающихся множеств» (Union-Find). Данная структура поддерживает две операции:
+
Every algorithm for solving this problem must be able to decide which of the already constructed fragments contains a given vertex of the graph. To this end, the data structure called a «system of disjoint sets» (Union-Find) is used. This structure supports the following two operations:
  
1. <math>FIND(v) = w</math> – по вершине v возвращает вершину w – «корень» фрагмента, которому принадлежит вершина v. При этом гарантируется, что вершины u и v принадлежат одному и тому же фрагменту, тогда и только тогда, когда <math>FIND(u) = FIND(v)</math>.
+
1. <math>FIND(v) = w</math> – for a given vertex v, returns the vertex w, which is the root of the fragment that contains v. It is guaranteed that u and v belong to the same fragment if and only if <math>FIND(u) = FIND(v)</math>.
  
2. <math>MERGE(u, v)</math> – объединяет два фрагмента, которым принадлежат вершины <math>u</math> и <math>v.</math> (Если они уже лежат в одном фрагменте, то ничего не происходит.) При практической реализации удобно, чтобы данная операция возвращала значение истина, если объединение фрагментов имело место, и ложь в противном случае.
+
2. <math>MERGE(u, v)</math> – combines two fragments that contain the vertices <math>u</math> and <math>v.</math> (If these vertices already belong to the same fragment, then nothing happens.) It is convenient that, in a practical implementation, this operation would return the value "true" if the fragments were combined and the value "false," otherwise.
  
 
==== Последовательная версия====
 
==== Последовательная версия====
  
Классический последовательный алгоритм Union-Find описан в статье Тарьяна. Каждой вершине v приписывается указатель на вершину-родителя <math>parent(v)</math>.
+
The classical serial algorithm Union-Find is described in a Tarjan's paper. Each vertex v is assigned the indicator to the parent vertex <math>parent(v)</math>.
  
1. Изначально <math>parent(v) := v</math> для всех вершин.
+
1. At first, <math>parent(v) := v</math> for all the vertices.
  
2. <math>FIND(v)</math> выполняется следующим образом: полагаем <math>u := v</math>, и далее следуем по указателям <math>u := parent(u)</math> до тех пор, пока не станет <math>u = parent(u)</math>. Это и будет результат операции. Дополнительно можно «схлопывать» дерево: присвоить всем посещённым вершинами: <math>parent(u_i) := u</math>, либо производить схлопывание по пути: <math>parent(u) := parent(parent(u)))</math>.
+
2. <math>FIND(v)</math> is executed as follows: set <math>u := v</math>; then follow the indicators <math>u := parent(u)</math> until the relation <math>u = parent(u)</math> is obtained. This is the result of the operation. An additional option is the merging of tree: for all the visited vertices, set <math>parent(u_i) := u</math> or perform the merging operation along the way: <math>parent(u) := parent(parent(u)))</math>.
  
3. <math>MERGE(u, v)</math> выполняется следующим образом: вначале находим корневые вершины <math>u := FIND(u), v := FIND(v)</math>. Если <math>u = v</math>, то исходные вершины принадлежат одному фрагменту и объединения фрагментов не происходит. В противном случае полагаем одно из <math>parent(u) := v</math> или <math>parent(v) := u</math>. Дополнительно можно отслеживать количество вершин в каждом из фрагментов, чтобы меньший фрагмент подсоединять к большему, а не наоборот (оценки сложности доказываются именно при такой реализации, однако на практике алгоритм хорошо работает и без подсчёта количества вершин).
+
3. <math>MERGE(u, v)</math> is executed as follows: first, find the root vertices <math>u := FIND(u), v := FIND(v)</math>. If <math>u = v</math>, then the original vertices belong to the same fragment and no merging occurs. Otherwise, set either <math>parent(u) := v</math> or <math>parent(v) := u</math>. In addition, one can keep track of the number of vertices in each fragment in order to add the smaller fragment to the greater one rather than otherwise. (Complexity estimates are derived exactly for such an implementation; however, in practice, the algorithm performs well even without counting the number of vertices.)
  
 
=== Implementation scheme of the serial algorithm ===
 
=== Implementation scheme of the serial algorithm ===
  
В алгоритме Борувки фрагменты минимального остовного дерева наращиваются постепенно присоединением минимального ребра, выходящего из каждого фрагмента.
+
In Borůvka's algorithm, the fragments of the minimum spanning tree are build up gradually by joining minimum edges outgoing from each fragment.
  
1. В самом начале каждая вершина является отдельным фрагментом.
+
1. At the start of the algorithm, each vertex is a separate fragment.
  
2. На каждом шаге:
+
2. At each step:
  
* Для каждого фрагмента определяется минимальное по весу исходящее ребро.
+
* For each fragment, the outgoing edge with the minimum weight is determined.  
  
* Минимальные рёбра добавляются в минимальное остовное дерево, а соответствующие фрагменты объединяются.
+
* Minimum edges are added to the minimum spanning tree, and the corresponding fragments are combined.
  
3. Алгоритм останавливается, когда остаётся только один фрагмент, либо когда ни у одного из фрагментов нет исходящих рёбер.
+
3. The algorithm terminates when only one fragment is left or no fragment has outgoing edges.
  
Поиск минимальных исходящих рёбер может выполняться независимо для каждого фрагмента. Таким образом, данную стадию вычислений можно эффективно параллелизовать (в том числе с использованием массового параллелизма графических ускорителей).
+
The search for minimum outgoing edges can be performed independently for each fragment. Therefore, this stage of computations can be efficiently parallelized (including the use of the mass parallelism of graphic accelerators).  
  
Объединение фрагментов также может быть реализовано параллельно, с использованием описанной выше параллельной версии структуры Union-Find.
+
The merging of fragments can also be implemented in parallel by using the parallel version of the algorithm Union-Find, which was described above.  
  
Аккуратный подсчёт количества активных фрагментов позволяет остановить алгоритм Борувки на один шаг раньше обычного:
+
An accurate count of the number of active fragments permits to terminate Borůvka's algorithm at one step earlier compared to the above description:
  
1. В начале итерации счётчик активных фрагментов обнуляется.
+
1. At the start of the algorithm, the counter of active fragments is set to zero.
  
2. На этапе поиска минимальных рёбер счётчик увеличивается на единицу для каждого фрагмента, у которого были исходящие рёбра.
+
2. At the stage of search for minimum edges, the counter is increased by one for each fragment that has outgoing edges.
  
3. На этапе объединения фрагментов счётчик уменьшается на единицу каждый раз, когда операция <math>MERGE(u, v)</math> вернула значение истина.
+
3. At the stage of combining fragments, the counter is decreased by one each time when the operation <math>MERGE(u, v)</math> returns the value "true".
  
Если в конце итерации счётчик равен 0 или 1, то вычисления останавливаются.
+
If, at the end of an iteration, the value of the counter is 0 or 1, then the algorithm stops. Parallel processing is possible at the stage of sorting edges by weight; however, the basic part of the algorithm is serial.
Параллелизм возможен на этапе сортировки рёбер по весу, однако основной ход алгоритма является последовательным.
 
  
 
=== Serial complexity of the algorithm ===
 
=== Serial complexity of the algorithm ===
  
Последовательная сложность алгоритма Борувки для графа с <math>|V|</math> вершинами и <math>|E|</math> рёбрами составляет <math>O(|E| \ln(|V|))</math> операций.
+
The serial complexity of Borůvka's algorithm for a graph with <math>|V|</math> vertices and  <math>|E|</math> edges is <math>O(|E| \ln(|V|))</math> operations.
  
 
=== Information graph ===
 
=== Information graph ===
  
В описанном подходе существует два уровня параллелизма: параллелизм в классическом алгоритме Борувки (нижний), и параллелизм в алгоритме обработка графа, не помещающегося в память.
+
There are two levels of parallelism in the above description: the parallelism in the classical Borůvka's algorithm (lower level) and the parallelism in the processing of a graph that does not fit in the memory.
 
   
 
   
'''Нижний уровень параллелизма''': поиск минимальных исходящих рёбер может выполняться независимо для каждого фрагмента, благодаря чему данную стадию вычислений можно эффективно параллелизовать (как на GPU, так и на CPU). Объединение фрагментов также может быть реализовано параллельно, с использованием описанной структуры Union-Find.  
+
'''Lower level of parallelism''': search for minimum outgoing edges can be performed independently for each fragment, which permits to efficiently parallelize (both on GPU and CPU) this stage of the process. The merging of fragments can also be executed in parallel with the use of the above algorithm Union-Find.  
  
'''Верхний уровень параллелизма''': построение отдельных минимальных основных деревьев для каждого из списков ребер может производиться параллельно. Например, список ребер может разбиваться на две части, одна из которых обрабатывается на GPU, а вторая параллельно на CPU.  
+
'''Upper level of parallelism''': constructions of separate minimum spanning trees for each edge list can be performed in parallel. For instance, the overall list of edges can be partitioned into two parts of which one is processed on GPU, while the other is in parallel processed on CPU.  
  
[[file:MST low.png|thumb|center|1000px|Рисунок 1. Информационный граф нижнего уровня параллелизма]]
+
[[file:MST low.png|thumb|center|1000px|Figure 1. Information graph of the lower level of parallelism]]
  
Рассмотрим информационные графы и подробное описание каждого из них. Так же можно считать, что на рисунке 1 представлен информационный граф классического алгоритма Борувки, а на рисунке 2 — алгоритма обработки графа.
+
Consider the information graphs and their detailed descriptions. One can think that figure 1 shows the information graph of the classical Borůvka's algorithm, while figure 2 shows the information graph of the processing algorithm.
  
Нижний уровень параллелизма на графе алгоритма (рисунок 1) расположен на уровнях {3, 4, 5}, соответствующим операциям параллельного поиска минимальных исходящих ребер, а так же уровнях {6, 7, 8}, соответствующим операциям параллельного объединения деревьев. Так же, различные операции копирования {1, 2, 8, 9} выполняются параллельно. После выполнения тела цикла, производится проверка {12} того, сколько деревьев осталось на текущем шаге, и если данное число не изменилось, то происходит выход из цикла, иначе аналогичная следующая итерация.  
+
In the graph shown in figure 1, the lower level of parallelism is represented by levels {3, 4, 5}, which correspond to parallel search operations for minimum outgoing edges, and by levels {6, 7, 8}, which correspond to parallel operations of merging trees. Various copying operations {1, 2, 8, 9} are also performed in parallel. After the body of the loop has been executed, test {12} verifies how many trees are left at the current step. If this number was not changed, the loop terminates; otherwise, the algorithm passes to the next iteration.  
  
Верхний уровень параллелизма (рисунок 2), как уже говорилось, заключается в параллельном вычислении минимального основного дерева (compute mst) для различных частей графа. Перед этим производится процесс инициализации (init process), данные которого используют последующие параллельные compute mst. Затем, после параллельных вычислений mst, происходит вычисление итого основного дерево, после чего после чего полученный результат сохраняется (save results).
+
As already said, the upper level of parallelism, illustrated by figure 2, refers to the parallel computation of minimum spanning trees (operation "compute mst") for different parts of the original graph. Prior to this computation, the initialization process ("init process") is performed, and its data are used by the subsequent parallel operations "compute mst". After these parallel computations, the ultimate spanning tree is calculated, and the result obtained is saved to memory ("save results").
  
[[file:MST up.png|thumb|center|1000px|Рисунок 2. Информационный граф верхнего уровня параллелизма]]
+
[[file:MST up.png|thumb|center|1000px|Figure 2. Information graph of the upper level of parallelism]]
  
 
=== Parallelization resource of the algorithm ===
 
=== Parallelization resource of the algorithm ===
  
Итак, алгоритм Борувки обладает двумя уровнями параллелизма.
+
Thus, Borůvka's algorithm has two levels of parallelism.
  
На верхнем уровне минимальные остовные деревья могут искаться для отдельных частей списка ребер графа (параллельные compute_MST на рисунке 2). Однако, затем должно последовать финальное объединение полученных ребер и вычисление минимального остовного дерева для полученного графа, которое будет производиться последовательно.
+
At the upper level, the minimum spanning trees may be searched for separate parts of the list of graph edges (parallel operations "compute_MST" in figure 2). However, then the final union должно последовать финальное объединение полученных ребер и вычисление минимального остовного дерева для полученного графа, которое будет производиться последовательно.
  
Кроме того, вычисление каждого из минимальных остовных деревьев (параллельные compute_MST на рисунке 2) обладает внутренним ресурсом параллелизма, описанным далее. Операции инициализации и копирования данных ([1], [2], [9] на рисунке 1) могут производиться параллельно за <math>O(|V|)</math> операций. Так же параллельно могут производиться операции поиска минимальных исходящих ребер ([3],[4],[5]), при том для каждой дуги и обратной к ней независимо, что даёт <math>2*O(|E|)</math> параллельных операций. Помимо этого, операции объединения деревьев [6], [7], [8] могут так же производиться параллельно за <math>O(|V|)</math> операций.
+
Besides, the computation of each minimum spanning tree (parallel operations "compute_MST" in figure 2) has an intrinsic resource of parallelism discussed below. The operations of initialization and copying data (see [1], [2], and [9] in figure 1) can be performed in parallel in <math>O(|V|)</math> steps. The operations of searching for minimum outgoing edges (see [3],[4], and [5]) can also be executed in parallel. при том для каждой дуги и обратной к ней независимо, что даёт <math>2*O(|E|)</math> параллельных операций. Помимо этого, операции объединения деревьев [6], [7], [8] могут так же производиться параллельно за <math>O(|V|)</math> операций.
  
В результате, для классического алгоритма Борувки ширина ярусно-параллельной формы равна <math>O(|E|)</math>, а высота ЯПФ зависит от числа шагов алгоритма, и ограничена сверху <math>O(ln(|V|))</math>.
+
As a result, the width of the parallel form of the classical Borůvka's algorithm is
 +
<math>O(|E|)</math>. The height of the parallel form depends on the number of steps in the algorithm and is bounded above by <math>O(ln(|V|))</math>.
  
 
=== Input and output data of the algorithm ===
 
=== Input and output data of the algorithm ===
  
'''Входные данные''': взвешенный граф <math>(V, E, W)</math> (<math>|V|</math> вершин <math>v_i</math> и <math>|E|</math> рёбер <math>e_j = (v^{(1)}_{j},
+
'''Input data''': weighted graph <math>(V, E, W)</math> (<math>|V|</math> vertices <math>v_i</math> and <math>|E|</math> edges <math>e_j = (v^{(1)}_{j},
v^{(2)}_{j})</math> с весами <math>f_j</math>).
+
v^{(2)}_{j})</math> with weights <math>f_j</math>).
  
'''Объём входных данных''': <math>O(|V| + |E|)</math>.
+
'''Size of the input data''': <math>O(|V| + |E|)</math>.
  
'''Выходные данные''': список рёбер минимального остовного дерева (для несвязного графа – список минимальных остовных деревьев для всех компонент связности).
+
'''Output data''': the list of edges of the minimum spanning tree (for a disconnected graph, the list of minimum spanning trees for all connected components).
  
'''Объём выходных данных''': <math>O(|V|)</math>.
+
'''Size of the output data''': <math>O(|V|)</math>.
  
 
=== Properties of the algorithm ===
 
=== Properties of the algorithm ===
  
# Алгоритм останавливается за конечное число шагов, поскольку на каждом шаге становится по крайней мере на один фрагмент меньше.
+
# The algorithm terminates in a finite number of steps because, at each step, the number of fragments reduces by at least one.
# Более того, число фрагментов на каждом шаге уменьшается как минимум вдвое, так что общее число шагов составляет не более <math>\log_2 n</math>. Отсюда следует и оценка сложности алгоритма.
+
# Moreover, the number of fragments at least halves at each step; consequently, the total number of steps is at most <math>\log_2 n</math>. This implies an estimate for the complexity of the algorithm.
  
 
== Software implementation of the algorithm ==
 
== Software implementation of the algorithm ==
  
 
=== Implementation peculiarities of the serial algorithm ===
 
=== Implementation peculiarities of the serial algorithm ===
 
=== Locality of data and computations ===
 
 
На этапе поиска минимального ребра происходят следующие обращения к памяти:
 
# Чтение информации о рёбрах. Может производится последовательно.
 
# Проверка принадлежности ребра одному и тому же фрагменту - два чтения массива <math>parent(u)</math> с вероятным промахой по кэшу.
 
# Чтение и обновление минимального веса ребра фрагмента. Данная информация может быть закеширована, особенно на поздних шагах, однако обновление необходимо производить атомарно, что требует инвализации кэша.
 
 
На этапе схлопывания фрагментов требуется атомарно обновить массив <math>parent(u)</math> для каждого добавляемого в MST ребра. В зависимости от реализации параллельной структуры Union-Find корни фрагментов могут находиться ближе к началу массива, что позволяет закешировать эту наиболее часто читаемую область. Требование атомарности, однако, ограничивает эффект от такого кэширования.
 
 
==== Locality of implementation ====
 
===== Structure of memory access and a qualitative estimation of locality =====
 
 
[[file:boruvka_1.png|thumb|center|700px|Рисунок 3. Алгоритм Борувки. Общий профиль обращений в память]]
 
 
На рис. 3 представлен профиль обращений в память для реализации алгоритма Борувки. Этот алгоритм, как и большинство графовых алгоритмов, обладает нерегулярной структурой. Сразу нужно отметить, что локальность реализаций таких алгоритмов во многом зависит от структуры входного графа и может существенно меняться. В данном случае мы рассматриваем лишь один из возможных вариантов.
 
 
Можно увидеть, что общий профиль состоит из 4 достаточно схожих этапов (разделены на рис. 3 вертикальными линиями). Однако поскольку этот профиль не обладает регулярной структурой, лучше рассмотреть все этапы.
 
 
Начнем с изучения верхней части профиля (фрагмент 1 на рис. 3), которая показана на рис. 4. На каждом этапе большую часть обращений занимает последовательный перебор всех элементов данного фрагмента (выделен на рис. 4 желтым). Остальные обращения на разных этапах устроены по-разному. Если на первом этапе эти обращения разбросаны достаточно далеко друг от друга, что приводит к низкой пространственной и временной локальности, то на последнем этапе почти все обращения (не считая последовательного перебора) выполняются к одному и тому же элементу, что, естественно, характеризуется очень высокой локальностью. Подобное строение всего фрагмента приводит, скорее всего, к средним значениям и по пространственной, и по временной локальности.
 
 
[[file:boruvka_2.png|thumb|center|700px|Рисунок 4. Профиль обращений, фрагмент 1]]
 
 
Далее перейдем к изучению фрагмента 2 (рис. 5). Здесь можно увидеть, что строение каждого из 4 этапов отличается достаточно сильно. Как и в случае с фрагментом 1, каждый следующий этап обладает более высокой локальностью, однако здесь это заметно сильнее. При этом отметим, что данный фрагмент задействует всего около 60 элементов, а обращений к ним выполняется достаточно много, так что локальность в данном случае будет высока.
 
 
[[file:boruvka_3.png|thumb|center|700px|Рисунок 5. Профиль обращений, фрагмент 2]]
 
 
В целом похожая картинка наблюдается и во фрагменте 3. На рис. 6 видны 4 этапа со схожей структурой, и также задействовано около 60 элементов, что позволяет говорить о высокой локальности данного фрагмента.
 
 
[[file:boruvka_4.png|thumb|center|700px|Рисунок 6. Профиль обращений, фрагмент 3]]
 
 
Отдельное рассмотрение фрагмента 4 (рис. 7) позволяет увидеть, что локальность здесь определяется 4 последовательными переборами всех элементов данного фрагмента. Эти переборы обладают стандартной структурой – шаг по памяти 1, только 1 обращение к каждому элементу; небольшое искривление данных переборов вызвано нерегулярной активностью в других фрагментах, которая приводит к искажению визуального представления профиля. Подобный набор обращений обладает высокой пространственной, но низкой временной локальностью.
 
 
[[file:boruvka_5.png|thumb|center|500px|Рисунок 7. Профиль обращений, фрагмент 4]]
 
 
Таким образом, фрагменты 2 и 3 характеризуются высокой локальностью, другие 2 фрагмента – средней локальностью. А поскольку большая часть обращений приходится именно на фрагменты 2 и 3, можно предположить, что общая локальность должна быть достаточно высока.
 
 
===== Quantitative estimation of locality =====
 
 
Оценка выполняется на основе характеристики daps, которая оценивает число выполненных обращений (чтений и записей) в память в секунду. Данная характеристика является аналогом оценки flops применительно к работе с памятью и является в большей степени оценкой производительности взаимодействия с памятью, чем оценкой локальности. Однако она служит хорошим источником информации, в том числе для сравнения с результатами по следующей характеристике cvg.
 
 
На рисунке 8 приведены значения daps для реализаций распространенных алгоритмов, отсортированные по возрастанию (чем больше daps, тем в общем случае выше производительность). Можно увидеть, что производительность работы с памятью в данном случае достаточно неплоха – значение daps сравнимо, например, со значением для реализации метода Холецкого. Однако это значение заметно ниже самых производительных реализаций алгоритмов (например, теста Linpack), что в целом неудивительно в случае графовых алгоритмов, традиционно неэффективно работающих с памятью.
 
 
[[file:boruvka_daps.png|thumb|center|700px|Рисунок 8. Сравнение значений оценки daps]]
 
  
 
=== Possible methods and considerations for parallel implementation of the algorithm ===
 
=== Possible methods and considerations for parallel implementation of the algorithm ===
  
Программа, реализующая алгоритм Борувки, состоит из двух частей:  
+
A program implementing Borůvka's algorithm consists of two parts:  
  
1. части, отвечающей за общую координацию вычислений
+
1. the part that is responsible for the general coordination of computations;
  
2. части, отвечающей за параллельные вычисления на многоядерных CPU или GPU.
+
2. the part that is responsible for the parallel computations on a multi-core CPU or GPU.
  
Описанный выше последовательный алгоритм не может применяться в параллельной программе: в реализации <math>MERGE</math> результаты операций <math>FIND(u)</math> и <math>FIND(v)</math> могут постоянно меняться, что приведёт к race condition. Параллельный вариант алгоритма описан в статье.
+
The serial algorithm described above cannot be used in a parallel program: in an implementation of <math>MERGE</math>, the results of operations <math>FIND(u)</math> and <math>FIND(v)</math> may permanently vary, which results in a race condition. A parallel variant of the algorithm is described in paper
  
1. Каждой вершине v соответствует запись <math>A[v] = { parent, rank }</math>. Изначально <math>A[v] := { v, 0 }</math>.
+
1. Each vertex v is assigned the record <math>A[v] = { parent, rank }</math>. At first, <math>A[v] := { v, 0 }</math>.
  
2. Вспомогательная операция <math>UPDATE(v, rank_v, u, rank_u)</math>:
+
2. The auxiliary operation <math>UPDATE(v, rank_v, u, rank_u)</math>:
  
 
old := A[v]
 
old := A[v]
Line 215: Line 171:
 
return CAS(A[v], old, new)
 
return CAS(A[v], old, new)
  
3. Операция <math>FIND(v)</math>:
+
3. The operation <math>FIND(v)</math>:
  
 
     while v != A[v].parent do
 
     while v != A[v].parent do
Line 223: Line 179:
 
     return v
 
     return v
  
4. Операция UNION(u, v):
+
4. The operation UNION(u, v):
  
 
     while true do
 
     while true do
Line 236: Line 192:
 
             return true
 
             return true
  
Для описанной версии алгоритма гарантируется свойство wait-free. На практике может использоваться упрощённая версия без подсчёта рангов, обладающая более слабым свойством lock-free, но в ряде случаев выигрывающая по скорости.
+
This variant of the algorithm is guaranteed to have the "wait-free" property. In practice, one may use a simplified version with no count of ranks. It has a weaker "lock-free" property but, in a number of cases, wins in speed.
 
 
=== Scalability of the algorithm and its implementations ===
 
==== Scalability of the algorithm ====
 
 
 
Возможность обрабатывать фрагменты независимо означает хорошую масштабируемость алгоритма. Сдерживающими факторами являются
 
# пропускная способность памяти при чтении данных графа
 
# соперничество потоков при выполнении атомарных операций с памятью
 
# барьерная синхронизация после каждого подшага алгоритма.
 
 
 
==== Scalability of of the algorithm implementation ====
 
 
 
Проведём исследование масштабируемости параллельной реализации алгоритма Борувки согласно [[Scalability methodology|методике]]. Исследование проводилось на суперкомпьютере "Ломоносов-2 [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета].
 
 
 
Набор и границы значений изменяемых [[Глоссарий#Параметры запуска|параметров запуска]] реализации алгоритма:
 
 
 
* число процессоров [1 : 28] с шагом 1;
 
* размер графа [2^20 : 2^27].
 
 
 
Проведем отдельные исследования сильной масштабируемости и масштабируемости вширь реализации алгоритма Борувки.
 
 
 
Производительность определена как TEPS (от англ. Traversed Edges Per Second), то есть число ребер графа, который алгоритм обрабатывает в секунду. С помощью данной метрики можно сравнивать производительность для различных размеров графа, оценивая, насколько понижается эффективность обработки графа при увеличении его размера
 
 
 
[[file:MST scaling strong.png|thumb|center|700px|Рисунок 3. Параллельная реализация алгоритма Борувки масштабируемость CPU версии: производительность в зависимости от числа запущенных CPU-потоков.]]
 
 
 
[[file:MST scaling wide.png|thumb|center|700px|Рисунок 4. Параллельная реализация алгоритма Борувки масштабируемость различных версий реализации алгоритма: производительность в зависимости от размера графа]]
 
 
 
=== Dynamic characteristics and efficiency of the algorithm implementation ===
 
 
 
Для проведения экспериментов использовалась реализация алгоритма Борувки, реализованная для CPU. Все результаты получены на суперкомпьютере «Ломоносов-2». Использовались процессоры Intel Xeon E5-2697v3, задача решалась для графа большого размера на одном узле.
 
На рисунках показана эффективность реализации алгоритма Борувки, запуск проводился на 1 узле для графа 2^27, выполнялась 1 итерация.
 
[[file:Boruvka cpu.png|thumb|center|700px|Рисунок 9. График загрузки CPU при выполнении алгоритма Борувки]]
 
 
 
На графике загрузки процессора видно, что почти все время работы программы не загружены и средний уровень загрузки составляет около 10%. Это нормальная картина для программ, запущенных c использованием одного ядра в реализации.
 
 
 
[[file:Boruvka Loadavg.png|thumb|center|700px|Рисунок 10. График числа процессов, ожидающих вхождения в стадию счета (Loadavg), при работе алгоритма Борувки]]
 
 
 
На графике числа процессов, ожидающих вхождения в стадию счета (Loadavg), видно, что на протяжении всей работы программы значение этого параметра постоянно на уровне 2. Это указывает на постоянную загрузку аппаратных ресурсов не более чем 2 процессами, однако их число для узла слишком мало, что с одной стороны может указывать на не очень рациональные использование ресурсов.
 
 
 
[[file:Boruvka L1.png|thumb|center|700px|Рисунок 11. График кэш-промахов L1 в секунду при работе алгоритма Борувки]]
 
 
На графике кэш-промахов первого уровня видно, что число промахов очень высокое и находится на уровне 40 млн/сек . Интересен факт увеличения числа промахов к концу итерации до уровня в 70 млн/сек.
 
 
 
[[file:Boruvka L2.png|thumb|center|700px|Рисунок 12. График кэш-промахов L1 в секунду при работе алгоритма Борувки]]
 
 
На графике кэш-промахов второго уровня видно, что число промахов достаточно тоже высокое и находится на уровне 30 млн/сек . На графике промахов второго уровня факт увеличения числа промахов к концу итерации проявляется более явно и увеличивается до значения в 50млн/сек.
 
 
 
[[file:Boruvka L3.png|thumb|center|700px|Рисунок 13. График кэш-промахов L3 в секунду при работе алгоритма Борувки]]
 
 
 
На графике кэш-промахов последнего уровня видно, что число промахов тоже достаточно большое и составляет около 30 млн/сек по всем узлам. Эт указывает на то, что задача очень плохо укладывается в кэш-память, и программа постоянно работает с оперативной памятью, что объясняется очень большим размером использованного графа.
 
 
 
[[file:Boruvka Inf data.png|thumb|center|700px|Рисунок 13. График скорости передачи по сети Infiniband в байт/сек при работе алгоритма Борувки]]
 
 
 
На графике скорости передачи данных по сети Infiniband наблюдается достаточно высокая интенсивность использования сети на кпервом этапе. Это объясняется программной логикой, которая предполагает чтение графа из файла с диска, коммуникации с которым происходят на Ломоносов-2 через выделенную для этих задач сеть Infiniband.
 
 
 
[[file:Boruvka inf pckts.png|thumb|center|700px|Рисунок 14. График скорости передачи по сети Infiniband в пакетах/сек при работе алгоритма Борувки]]
 
 
 
На графике скорости передачи данных в пакетах в секунду наблюдается аналогичная картина очень высокой интенсивности на первом этапе выполнения задачи. Далее сеть почти не используется.
 
 
В целом, по данным системного мониторинга работы программы можно сделать вывод о том, что программа работала стабильно интенсивно,  однако очень неэффективно использовала память из-за очень большого размера графа.
 
  
 +
=== Run results ===
 
=== Conclusions for different classes of computer architecture ===
 
=== Conclusions for different classes of computer architecture ===
=== Existing implementations of the algorithm ===
 
 
* C++, MPI: [http://www.boost.org/libs/graph_parallel/doc/html/index.html Parallel Boost Graph Library]; функции <code>[http://www.boost.org/libs/graph_parallel/doc/html/dehne_gotz_min_spanning_tree.html#dense-boruvka-minimum-spanning-tree dense_boruvka_minimum_spanning_tree]</code>, <code>[http://www.boost.org/libs/graph_parallel/doc/html/dehne_gotz_min_spanning_tree.html#boruvka-then-merge boruvka_then_merge]</code>, <code>[http://www.boost.org/libs/graph_parallel/doc/html/dehne_gotz_min_spanning_tree.html#boruvka-mixed-merge boruvka_mixed_merge]</code> сочетают алгоритм Борувки и [[алгоритм Крускала]].
 
  
 
== References ==
 
== References ==

Latest revision as of 13:54, 5 July 2022


Алгоритм Борувки
Sequential algorithm
Serial complexity [math]O(|E|ln(|V|))[/math]
Input data [math]O(|V| + |E|)[/math]
Output data [math]O(|V|)[/math]
Parallel algorithm
Parallel form height [math]max O(ln(|V|)) [/math]
Parallel form width [math]O(|E|)[/math]


1 Properties and structure of the algorithm

1.1 General description of the algorithm

The Borůvka algorithm[1][2] was designed for constructing the minimum spanning tree in a weighted undirected graph. It is well parallelizable and is a foundation of the distributed GHS algorithm.

1.2 Mathematical description of the algorithm

Let [math]G = (V, E)[/math] be a connected undirected graph with the edge weights [math]f(e)[/math]. It is assumed that all the edges have distinct weights (otherwise, the edges can be sorted first by weight and then by index).

The Borůvka's algorithm is based on the following two facts:

  • Minimum edge of a fragment. Let [math]F[/math] be a fragment of the minimum spanning tree, and let [math]e_F[/math] be an edge with the least weight outgoing from [math]F[/math] (that is, exactly one of its ends is a vertex in [math]F[/math]). If such an edge [math]e_F[/math] is unique, then it belongs to the minimum spanning tree.
  • Merging fragments. Let [math]F[/math] be a fragment of the minimum spanning tree of [math]G[/math], while the graph [math]G'[/math] is obtained from [math]G[/math] by merging the vertices that belong to [math]F[/math]. Then the union of [math]F[/math] and the minimum spanning tree of [math]G'[/math] yields the minimum spanning tree of the original graph [math]G[/math].

At the start of the algorithm, each vertex of [math]G[/math] is a separate fragment. At the current step, the outgoing edge with the least weight (if such an edge exists) is chosen for each fragment. The chosen edges are added to the minimum spanning tree, and the corresponding fragments are merged.

1.3 Computational kernel of the algorithm

The basic operations of the algorithm are:

  1. Search for the outgoing edge with the least weight in each fragment.
  2. Merging fragments.

1.4 Macro structure of the algorithm

For a given connected undirected graph, the problem is to find the tree that connects all the vertices and has the minimum total weight.

The classical example (taken from Borůvka's paper) is to design the cheapest electrical network if the price for each piece of electric line is known.

Let [math]G=(V,E)[/math] be a connected graph with the vertices [math]V = ( v_{1}, v_{2}, ..., v_{n} )[/math] and the edges [math]E = ( e_{1}, e_{2}, ..., e_{m} )[/math]. Each edge [math]e \in E[/math] is assigned the weight [math]w(e)[/math].

It is required to construct the tree [math]T^* \subseteq E[/math] that connects all the vertices and has the least possible weight among all such trees:

[math] w(T^* )= \min_T( w(T)) [/math].

The weight of a set of edges is the sum of their weights:

[math]w(T)=\sum_{e \in T} (w(T))[/math]

If [math]G[/math] is not connected, then there is no tree connecting all of its vertices.

In this case, it is required to find the minimum spanning tree for each connected component of [math]G[/math]. The collection of such trees is called the minimum spanning forest (abbreviated as MSF).

1.4.1 Auxiliary algorithm: system of disjoint sets (Union-Find)

Every algorithm for solving this problem must be able to decide which of the already constructed fragments contains a given vertex of the graph. To this end, the data structure called a «system of disjoint sets» (Union-Find) is used. This structure supports the following two operations:

1. [math]FIND(v) = w[/math] – for a given vertex v, returns the vertex w, which is the root of the fragment that contains v. It is guaranteed that u and v belong to the same fragment if and only if [math]FIND(u) = FIND(v)[/math].

2. [math]MERGE(u, v)[/math] – combines two fragments that contain the vertices [math]u[/math] and [math]v.[/math] (If these vertices already belong to the same fragment, then nothing happens.) It is convenient that, in a practical implementation, this operation would return the value "true" if the fragments were combined and the value "false," otherwise.

1.4.2 Последовательная версия

The classical serial algorithm Union-Find is described in a Tarjan's paper. Each vertex v is assigned the indicator to the parent vertex [math]parent(v)[/math].

1. At first, [math]parent(v) := v[/math] for all the vertices.

2. [math]FIND(v)[/math] is executed as follows: set [math]u := v[/math]; then follow the indicators [math]u := parent(u)[/math] until the relation [math]u = parent(u)[/math] is obtained. This is the result of the operation. An additional option is the merging of tree: for all the visited vertices, set [math]parent(u_i) := u[/math] or perform the merging operation along the way: [math]parent(u) := parent(parent(u)))[/math].

3. [math]MERGE(u, v)[/math] is executed as follows: first, find the root vertices [math]u := FIND(u), v := FIND(v)[/math]. If [math]u = v[/math], then the original vertices belong to the same fragment and no merging occurs. Otherwise, set either [math]parent(u) := v[/math] or [math]parent(v) := u[/math]. In addition, one can keep track of the number of vertices in each fragment in order to add the smaller fragment to the greater one rather than otherwise. (Complexity estimates are derived exactly for such an implementation; however, in practice, the algorithm performs well even without counting the number of vertices.)

1.5 Implementation scheme of the serial algorithm

In Borůvka's algorithm, the fragments of the minimum spanning tree are build up gradually by joining minimum edges outgoing from each fragment.

1. At the start of the algorithm, each vertex is a separate fragment.

2. At each step:

  • For each fragment, the outgoing edge with the minimum weight is determined.
  • Minimum edges are added to the minimum spanning tree, and the corresponding fragments are combined.

3. The algorithm terminates when only one fragment is left or no fragment has outgoing edges.

The search for minimum outgoing edges can be performed independently for each fragment. Therefore, this stage of computations can be efficiently parallelized (including the use of the mass parallelism of graphic accelerators).

The merging of fragments can also be implemented in parallel by using the parallel version of the algorithm Union-Find, which was described above.

An accurate count of the number of active fragments permits to terminate Borůvka's algorithm at one step earlier compared to the above description:

1. At the start of the algorithm, the counter of active fragments is set to zero.

2. At the stage of search for minimum edges, the counter is increased by one for each fragment that has outgoing edges.

3. At the stage of combining fragments, the counter is decreased by one each time when the operation [math]MERGE(u, v)[/math] returns the value "true".

If, at the end of an iteration, the value of the counter is 0 or 1, then the algorithm stops. Parallel processing is possible at the stage of sorting edges by weight; however, the basic part of the algorithm is serial.

1.6 Serial complexity of the algorithm

The serial complexity of Borůvka's algorithm for a graph with [math]|V|[/math] vertices and [math]|E|[/math] edges is [math]O(|E| \ln(|V|))[/math] operations.

1.7 Information graph

There are two levels of parallelism in the above description: the parallelism in the classical Borůvka's algorithm (lower level) and the parallelism in the processing of a graph that does not fit in the memory.

Lower level of parallelism: search for minimum outgoing edges can be performed independently for each fragment, which permits to efficiently parallelize (both on GPU and CPU) this stage of the process. The merging of fragments can also be executed in parallel with the use of the above algorithm Union-Find.

Upper level of parallelism: constructions of separate minimum spanning trees for each edge list can be performed in parallel. For instance, the overall list of edges can be partitioned into two parts of which one is processed on GPU, while the other is in parallel processed on CPU.

Figure 1. Information graph of the lower level of parallelism

Consider the information graphs and their detailed descriptions. One can think that figure 1 shows the information graph of the classical Borůvka's algorithm, while figure 2 shows the information graph of the processing algorithm.

In the graph shown in figure 1, the lower level of parallelism is represented by levels {3, 4, 5}, which correspond to parallel search operations for minimum outgoing edges, and by levels {6, 7, 8}, which correspond to parallel operations of merging trees. Various copying operations {1, 2, 8, 9} are also performed in parallel. After the body of the loop has been executed, test {12} verifies how many trees are left at the current step. If this number was not changed, the loop terminates; otherwise, the algorithm passes to the next iteration.

As already said, the upper level of parallelism, illustrated by figure 2, refers to the parallel computation of minimum spanning trees (operation "compute mst") for different parts of the original graph. Prior to this computation, the initialization process ("init process") is performed, and its data are used by the subsequent parallel operations "compute mst". After these parallel computations, the ultimate spanning tree is calculated, and the result obtained is saved to memory ("save results").

Figure 2. Information graph of the upper level of parallelism

1.8 Parallelization resource of the algorithm

Thus, Borůvka's algorithm has two levels of parallelism.

At the upper level, the minimum spanning trees may be searched for separate parts of the list of graph edges (parallel operations "compute_MST" in figure 2). However, then the final union должно последовать финальное объединение полученных ребер и вычисление минимального остовного дерева для полученного графа, которое будет производиться последовательно.

Besides, the computation of each minimum spanning tree (parallel operations "compute_MST" in figure 2) has an intrinsic resource of parallelism discussed below. The operations of initialization and copying data (see [1], [2], and [9] in figure 1) can be performed in parallel in [math]O(|V|)[/math] steps. The operations of searching for minimum outgoing edges (see [3],[4], and [5]) can also be executed in parallel. при том для каждой дуги и обратной к ней независимо, что даёт [math]2*O(|E|)[/math] параллельных операций. Помимо этого, операции объединения деревьев [6], [7], [8] могут так же производиться параллельно за [math]O(|V|)[/math] операций.

As a result, the width of the parallel form of the classical Borůvka's algorithm is [math]O(|E|)[/math]. The height of the parallel form depends on the number of steps in the algorithm and is bounded above by [math]O(ln(|V|))[/math].

1.9 Input and output data of the algorithm

Input data: weighted graph [math](V, E, W)[/math] ([math]|V|[/math] vertices [math]v_i[/math] and [math]|E|[/math] edges [math]e_j = (v^{(1)}_{j}, v^{(2)}_{j})[/math] with weights [math]f_j[/math]).

Size of the input data: [math]O(|V| + |E|)[/math].

Output data: the list of edges of the minimum spanning tree (for a disconnected graph, the list of minimum spanning trees for all connected components).

Size of the output data: [math]O(|V|)[/math].

1.10 Properties of the algorithm

  1. The algorithm terminates in a finite number of steps because, at each step, the number of fragments reduces by at least one.
  2. Moreover, the number of fragments at least halves at each step; consequently, the total number of steps is at most [math]\log_2 n[/math]. This implies an estimate for the complexity of the algorithm.

2 Software implementation of the algorithm

2.1 Implementation peculiarities of the serial algorithm

2.2 Possible methods and considerations for parallel implementation of the algorithm

A program implementing Borůvka's algorithm consists of two parts:

1. the part that is responsible for the general coordination of computations;

2. the part that is responsible for the parallel computations on a multi-core CPU or GPU.

The serial algorithm described above cannot be used in a parallel program: in an implementation of [math]MERGE[/math], the results of operations [math]FIND(u)[/math] and [math]FIND(v)[/math] may permanently vary, which results in a race condition. A parallel variant of the algorithm is described in paper

1. Each vertex v is assigned the record [math]A[v] = { parent, rank }[/math]. At first, [math]A[v] := { v, 0 }[/math].

2. The auxiliary operation [math]UPDATE(v, rank_v, u, rank_u)[/math]:

old := A[v]

if old.parent != v or old.rank != rank_v then return false

new := { u, rank_u }

return CAS(A[v], old, new)

3. The operation [math]FIND(v)[/math]:

   while v != A[v].parent do
       u := A[v].parent
       CAS(A[v].parent, u, A[u].parent)
       v := A[u].parent
   return v

4. The operation UNION(u, v):

   while true do
       (u, v) := (FIND(u), FIND(v))
       if u = v then return false
       (rank_u, rank_v) := (A[u].rank, A[v].rank)
       if (A[u].rank, u) > (A[v].rank, v) then
           swap((u, rank_u), (v, rank_v))
       if UPDATE(u, rank_u, v, rank_u) then
           if rank_u = rank_v then
               UPDATE(v, rank_v, v, rank_v + 1)
           return true

This variant of the algorithm is guaranteed to have the "wait-free" property. In practice, one may use a simplified version with no count of ranks. It has a weaker "lock-free" property but, in a number of cases, wins in speed.

2.3 Run results

2.4 Conclusions for different classes of computer architecture

3 References

  1. Borůvka, Otakar. “O Jistém Problému Minimálním.” Práce Moravské Přírodovědecké Společnosti III, no. 3 (1926): 37–58.
  2. Jarník, Vojtěch. “O Jistém Problému Minimálním (Z Dopisu Panu O. Borůvkovi).” Práce Moravské Přírodovědecké Společnosti 6, no. 4 (1930): 57–63.