DCSC algorithm for finding the strongly connected components

Алгоритм DCSC поиска компонент сильной связности
Sequential algorithm
Serial complexity	[math]O(|V| \ln(|V|))[/math]
Input data	[math]O(|V| + |E|)[/math]
Output data	[math]O(|V|)[/math]
Parallel algorithm
Parallel form height	[math]C * O(ln(u))[/math]
Parallel form width	[math]O(|E|)[/math]

Primary author of this description: I.V.Afanasyev.

1 Properties and structure of the algorithm

1.1 General description of the algorithm

Алгоритм DCSC (Divide and Conquer Strong Components) finds strongly connected components of a directed graph with the expected complexity [math]O(|V| \ln |V|)[/math] (assuming that the node degrees are bounded by a constant).

In the literature on GPU implementations of the algorithm, it is typically called the Forward-Backward algorithm (shortly, the FB-algorithm).

From the outset, the algorithm was designed for parallel realization. Indeed, at each step, it finds a strongly connected component and selects up to three subsets in the graph that contain other connected components and can be processed in parallel. Moreover, the selection of these subsets and the strongly connected component can be done in parallel (using parallel breadth-first searches). It should be noted that the iterations of breadth-first searches need not to be synchronized because their aim is to determine reachable nodes rather than find the distances to these nodes.

The algorithm is well suitable for graphs that consist of a small number of large strongly connected components. A significant increase in the number of strongly connected components implies that the complexity of the algorithm also increases significantly (proportionally to the number of components). For this reason, the algorithm may become less efficient than Tarjan's algorithm, which selects strongly connected components in the course of one graph traversal.

The following modification of the algorithm was proposed to improve its efficiency for graphs with a large number of trivial (that is, of size 1 or 2) strongly connected components: prior to executing the classical algorithm, the so-called Trim step is performed. This step, described in a later section, allows one to select all the trivial strongly connected components. For instance, for RMAT graphs, an application of the Trim step leaves in the graph only a few large strongly connected components. For such components, the complexity of the algorithm is not large.

1.2 Mathematical description of the algorithm

Пусть [math]v[/math] – некоторая вершина графа. Определим следующие множества вершин:

⎯ [math]Fwd(v)[/math] – вершины, достижимые из [math]v[/math] .

⎯ [math]Pred(v)[/math] – вершины, из которых достижима [math]v[/math] (эквивалентно – вершины, достижимые из [math]v[/math] в графе, полученном из [math]G[/math] обращением всех рёбер).

Используя эти множества, разобьём все вершины графа на четыре области:

⎯ [math]V_1 = Fwd(v) \cap Pred(v) [/math]

⎯ [math]V_2 = Fwd(v) \setminus Pred(v) [/math]

⎯ [math]V_3 = Pred(v) \setminus Fwd(v)[/math]

⎯ [math]V_4 = V \setminus Pred(v) \setminus Fwd(v)[/math]

Тогда можно утверждать следующее:

1. Область [math]V_1[/math] является компонентой сильной связности.

2. Любая другая компонента сильной связности полностью содержится в одной из областей [math]V_2[/math], [math]V_3[/math], или [math]V_4[/math].

1.3 Computational kernel of the algorithm

Основными вычислительными операциями алгоритма является поиск вершин, достижимых из выбранной вершины [math]v[/math], а так же поиск вершин, из которых достижима выбранная вершина [math]v[/math]. Обе данные операции могут быть реализованы через поиски в ширину, устроенные следующим образом:

1. Вершина [math]v_0[/math] помещается в начало в очереди и помечается ее как посещенная

2. Верхняя вершина [math]v[/math] извлекается из очереди. Для всех ребер [math](v, u)[/math], исходящих из вершины [math]v[/math], проверяется, является ли посещенной вершина [math]u[/math]. В случае, если является, вершина [math]u[/math] помещается в начало очереди.

3. Происходит переход на шаг 2 до тех пор, пока в очереди есть вершины.

1.4 Macro structure of the algorithm

Алгоритм DCSC состоит в следующем:

1. Поместить в очередь множество [math]V[/math].

2. Параллельно обрабатывать очередь. Для каждого элемента очереди [math]V[/math]:

а) Выбрать произвольную ведущую вершину [math]v \in V[/math].

б) Вычислить множества [math]Fwd(v)[/math], [math]Pred(v)[/math] (эти два вычисления можно производить параллельно, кроме того, как указано выше, сами эти вычисления хорошо параллелизуются).

в) Добавить множество [math] V_1[/math] в список компонент сильной связности.

г) Добавить множества [math] V_2[/math], [math]V_3[/math] и [math]V_4[/math] в очередь.

3. Алгоритм завершает работу, когда очередь пуста и не осталось активных процессов-обработчиков.

Для улучшения балансировки нагрузки на первых шагах можно выбирать не одну ведущую вершину, а сразу несколько. Тогда, если они принадлежат различным компонентам связности, граф будет сразу разбит на большое количество областей, которые будут далее обрабатываться параллельно.

Важной модификацией алгоритма является шаг Trim, производимый перед основными вычислениями алгоритма DCSC, который может быть описан следующим образом:

1. Пометить все вершины из [math]v \in V[/math] активными.

2. Для каждой вершины [math]v[/math]вычислить число входящих ([math]in(v)[/math]) и исходящих ([math]out(v)[/math]) дуг [math](v, u) \in E[/math], таких, что вершина [math]u[/math] - активная.

3. Все вершины [math]v \in V[/math] , для которых [math]in(v)[/math] или [math]out(v)[/math] равно нулю, пометить как неактивные.

4. Переходить на шаг 2, до тех пор, пока число активных вершин не перестанет изменяться.

Кроме того, в зависимости от схемы хранения графа может потребоваться предварительное нахождение транспонированного к нему для более эффективной реализации как шага trim, так и поиска вершин, из которых достижима заданная вершина [math]v[/math] в вычислительном ядре алгоритма.

1.5 Implementation scheme of the serial algorithm

Последовательный алгоритм реализуется следующим псевдокодом:

Входные данные:
  граф с вершинами V, рёбрами E;
Выходные данные: номера компонент сильной связанности c(v) до каждой вершины v ∈ V.

compute_scc_with_trim(G)
{
	G’ = transpose(G)
	G = trim(G)
	compute_scc()
}

compute_scc(V, G, G’)
{
	p = pivot(V)

	fwd = bfs(G, p);
	pred = bfs(G’, p);

	compute_scc(fwd / pred, G, G’)
	compute_scc(pred / fwd, G, G’)
	compute_scc(V / pred / fwd, G, G’)
}

pivot(V)
{
	return random v in V
}

trim(G)
{
	for each v in V(G)
		active[v] = true

	changes = false
	do
	{
		for each v in V
			in_deg(v) = compute_in_degree(v)
			out_deg(v) = compute_out_degree(v)
		
		for each v in V
			if (in_deg[v] == 0 || out_deg[v] == 0)
				active[v] = false
				changes = true
	} while (!changes)
	return active
}

bfs здесь стандартный поиск в ширину, описанный в соответствующем разделе, результатом которого являются все узлы, достижимые из вершины [math] p [/math] в графе [math] G [/math]

1.6 Serial complexity of the algorithm

Ожидаемая последовательная сложность алгоритма составляет [math]O(|V| \ln(|V|))[/math] при условии, что степень вершин ограничена сверху константой.

1.7 Information graph

На рисунке 1 представлен информационный граф алгоритма DCSC, демонстрирующий связь между его основным частями.

Рисунок 1. Информационный граф алгоритма DCSC(Forward-Backward-Trim).

Итак, алгоритм состоит из первоначального шага Trim, выбора pivot-вершины [1], поиска в ширину в прямом и транспонированном графах (forward и backward BFS), обработке результатов поиска [2], проверки необходимости проведения последующих рекурсивных шагов [3], а так же рекурсивных вызовах FB-step. Далее будут приведены более подробные информационные графы для каждой из частей, а так же дана подробная расшифровка соотвесвующих операций, а в следующем разделе и оценим ресурс параллелизма для каждой части алгоритма.

На рисунке 2 представлен информационный граф шага Trim.

Рисунок 2. Информационный граф шага Trim алгоритма DCSC.

[1] - выделение памяти под массивы данных числа входящих и исходящих дуг, а так же активных вершин

[2] - инциализация переменной наличия изменений

[3] - инициализация массива сильно связанных компонент, а так же массива активных вершин.

[4] - установка переменной наличия изменений в позицию "нет изменений"

[5] - обнуление массивов числа входящих и исходящих дуг

[6] - проверка, активны ли вершины на концах каждого ребра, увеличение числа входящих/исходящих дуг для соответствующих вершин, изменение переменно наличия изменений

[7] - проверка активности всех вершин графа

[8] - присваивание номеров сильно связанных компонент с нулевой степенью входящих или исходящих вершин

[9] - проверка, происходи ли ли изменения на шаге 6, переход к следующей итерации

Информационный граф этапа поиска в ширину (Forward и Backward BFS) приведен в соответвующем разделе (Поиск_в_ширину_(BFS)).

1.8 Parallelization resource of the algorithm

Алгоритм изначально предназначен для параллельной реализации и имеет несколько уровней параллелизма.

На верхнем уровне алгоритм DCSC может параллельно выполнять шаги FB-step, продемонстрированные на рисунке 1. Таким образом, на каждом рекурсивном шаге алгоритма могут рекурсивно порождаться до 3 новых параллельных процессов, общее число которых равно числу сильно связанных компонент графа. Кроме того, поиски в ширину в исходном и транспонированному нему графах независимы, и так же могут выполняться параллельно друг с другом. Таким образом, на верхнем уровне может выполняться до [math] 2*u/log|u|[/math] параллельных потоков, где [math] u [/math] - это число сильно связанных компонент графа. Важно заметить, что вычисления шагов FB-step одного уровня (а так же всех последующих рекурсивных) абсолютно независимы по данным, так как производятся в не пересекающихся множествах вершин графа, поэтому могут производиться в том числе и на различных узлах. Кроме того, составные шаги алгоритма (поиск в ширину и шаг Trim) так же имеют значительный потенциал параллелизма, описанный далее.

Этап Trim алгоритма, информационный граф которого приведен на рисунке 2, обладает значительным ресурсом параллелизма: единственной последовательной частью является инициализация массивов и переменных (1)(2), а так же проверка условия выхода из цикла (9). Операции (3),(5),(7) и (8) абсолютно независимы и могу производиться параллельно, их число составляет [math]O(|V|)[/math]. Проверки и обновления данных в операции (6) так же могут производиться параллельно, однако обновления данных должны производиться атомарно. Число операций (6) равно [math]O(E)[/math]. Таким образом, почти все операции шага Trim могут выполняться параллельно, при том число параллельно выполняемых операций составляет [math]|V|[/math] или [math]|E|[/math]. Учитывая, что величины [math]|V|[/math] и [math]|E|[/math] для графов большого размера крайне велики, потенциал параллелизма данной части алгоритма очень значителен и достаточен для полной загрузки современных вычислительных узлов/сопроцессоров. Кроме того, операции (3),(5),(7),(8) могут быть успешно векторизованы.

Ресурс параллелизма операции поиска в ширину подробно описан в соответвующем разделе (Поиск_в_ширину_(BFS)). В зависимости от выбора формата хранения графа, подход к параллельной реализации поиска в ширину может быть линейным или квадратичным (в худшем случае).

В случае линейного подхода, на каждом алгоритма шаге поиска в ширину может выполняться [math]O(n)[/math] параллельных операций, где [math]n[/math] - это число вершин, добавленных для просмотра на предыдущем шаге. Перед началом работы алгоритма для просмотра добавляется вершина-источник, на первом шаге - все еще не посещенные смежные с ней, на втором - все еще не посещенные смежные с вершинами на первом шаге, и.т.д. Максимальное (или даже среднее) число вершин а каждом шаге оценить проблематично, так как число шагов алгоритма, число достижимых вершин, а так же структура связей между ними определены лишь структурой конкретного входного графа. В случае, если все вершины достижимы, а число шагов поиска в ширину составляет [math] r [/math], то среднее число параллельно обрабатываемых вершин на каждом шаге составляет [math] O(|V|)/r [/math]. Важно заметить, что наибольший уровень параллелизма достигается на средних шагах алгоритма, в то время как число вершин для обработки на начальных и конечных шагах может быть небольшим.

В случае квадратической параллелизации алгоритм поиска в ширину на каждом шаге обходит все ребра графа, таким образом выполняя [math]O(|E|)[/math] параллельных операций, что совпадает с аналогичной оценкой для шага trim. Кроме того, поиск в ширину при реализации с использованием формата списка ребер графа может быть векторизован.

Таким образом, на начальном этапе алгоритма может выполняться [math]O(|V|)[/math] или [math]O(|E|)[/math] параллельных операций. Далее следует [math]O(log(u))[/math] шагов, в каждом из которых в среднем присутствует [math]2*u/O(log(u))[/math] поисков в ширину, которые так же обладают внутренним ресурсом параллелизма: каждый поиск в ширину имеет [math]O(|E|)[/math] параллельных операций на каждом шаге при квадратическом подходе к параллелизации.

Высота и ширина ярусно-параллельной формы зависит от структуры графа (числа и расположения сильно связанных компонент), по причине аналогичной зависимости шагов FB_step от входных данных.

1.9 Input and output data of the algorithm

Входные данные: граф [math]G(V, E)[/math], [math]|V|[/math] вершин [math]v_i[/math] и [math]|E|[/math] рёбер [math]e_j = (v^{(1)}_{j}, v^{(2)}_{j})[/math].

Объём входных данных: [math]O(|V| + |E|)[/math].

Выходные данные: для каждой вершины [math]v[/math] исходного графа – номер компоненты сильной связанности, в которую входит данная вершина [math] c(v) [/math], вершины, принадлежащие одной компоненте сильно связанности имеют одинаковые номера

Объём выходных данных: [math]O(|V|)[/math].

1.10 Properties of the algorithm

Вычислительное ядро алгоритма основано на поисках в ширину, поэтому многие свойства (локальности, масштабируемости) этих алгоритмов так же схожи.

2 Software implementation of the algorithm

2.4 Scalability of the algorithm and its implementations

2.4.1 Scalability of the algorithm

Алгоритм обладает значительным потенциалом масштабируемости, так как, во-первых, поиск в ширину, на котором он основывается, поддается эффективному распараллеливанию либо при помощи квадратичнго подхода, либо при помощи параллельных очередей (по очереди на процессор).

Кроме того, дополнительный ресурс параллелизма можно получить при параллельной обработке трех получающихся множеств вершин на каждом шаге алгоритма, использую задачи и nested parallelism.

2.4.2 Scalability of of the algorithm implementation

Проведём исследование масштабируемости параллельной реализации алгоритма Forward-Backward-Trim согласно методике. Исследование проводилось на суперкомпьютере "Ломоносов-2 Суперкомпьютерного комплекса Московского университета.

Набор и границы значений изменяемых параметров запуска реализации алгоритма:

число процессоров [1 : 28] с шагом 1; размер графа [2^20 : 2^27].

Проведем отдельные исследования сильной масштабируемости вширь указанной реализации.

Производительность определена как TEPS (от англ. Traversed Edges Per Second), то есть число ребер графа, который алгоритм обрабатывает в секунду. С помощью данной метрики можно сравнивать производительность для различных размеров графа, оценивая, насколько понижается эффективность обработки графа при увеличении его размера.

Рисунок 3. Параллельная реализация алгоритма Farward-Backward-Trim, масштабируемость различных версий реализации алгоритма: производительность в зависимости от размера графа

2.7 Existing implementations of the algorithm

• C++, MPI: Parallel Boost Graph Library (функция strong_components), распределённый алгоритм DCSC сочетается с локальным поиском компонент сильной связности алгоритмом Тарьяна.