Algorithm level

DCSC algorithm for finding the strongly connected components

From Algowiki
Jump to navigation Jump to search


Алгоритм 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[1][2][3] (англ. Divide and Conquer Strong Components – компоненты сильной связности по принципу «Разделяй и властвуй») находит компоненты сильной связности ориентированного графа с ожидаемой работой [math]O(|V| \ln |V|)[/math] (при условии ограниченной констатой степени вершин).

Так же алгоритм носит другое название - Forward-Backward (сокр. FB-algorithm), в основном в литературе, связанной с его GPU-реализациями. [4]

Алгоритм изначально предназначен для параллельной реализации: на каждом шаге он находит одну компоненту сильной связности и выделяет до трёх подмножеств графа, которые содержат другие компоненты связности и могут обрабатываться параллельно. Кроме того, выделение данных подмножеств и сильно связанной компоненты на каждом шаге так же может производиться параллельно (с использованием параллельных поисков в ширину). Следует отметить, что в данном случае не требуется синхронизации между итерациями поиска в ширину, поскольку требуется только определить достижимые вершины, но не расстояния до них.

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

Для увеличения эффективности работы алгоритма на графах с большим числом тривиальных сильно-связанных компонент (размера 1 или 2), предложена модификация алгоритма: перед началом работы классического алгоритма, производится шаг Trim, описанный в следующих разделах, позволяющий выделять все тривиальные сильно-связанные компоненты. В результате, к примеру в RMAT графах, после шага Trim в графе остается всего лишь несколько компонент сильной связанности большого размера, на которых алгоритм будет иметь небольшую алгоритмическую сложность.

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.1 Implementation peculiarities of the serial algorithm

2.2 Locality of data and computations

2.2.1 Locality of implementation

2.2.1.1 Structure of memory access and a qualitative estimation of locality
2.2.1.2 Quantitative estimation of locality

2.3 Possible methods and considerations for parallel 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.5 Dynamic characteristics and efficiency of the algorithm implementation

2.6 Conclusions for different classes of computer architecture

2.7 Existing implementations of the algorithm

3 References

  1. ↑ Fleischer, Lisa K, Bruce Hendrickson, and Ali Pınar. “On Identifying Strongly Connected Components in Parallel.” In Lecture Notes in Computer Science, Volume 1800, Springer, 2000, pp. 505–11. doi:10.1007/3-540-45591-4_68.
  2. ↑ McLendon, William, III, Bruce Hendrickson, Steven J Plimpton, and Lawrence Rauchwerger. “Finding Strongly Connected Components in Distributed Graphs.” Journal of Parallel and Distributed Computing 65, no. 8 (August 2005): 901–10. doi:10.1016/j.jpdc.2005.03.007.
  3. ↑ Hong, Sungpack, Nicole C Rodia, and Kunle Olukotun. “On Fast Parallel Detection of Strongly Connected Components (SCC) in Small-World Graphs,” Proceeedings of SC'13, 1–11, New York, New York, USA: ACM Press, 2013. doi:10.1145/2503210.2503246.
  4. ↑ Jiˇr ́ı Barnat, Petr Bauch, Lubosˇ Brim, and Milan Cˇesˇka. Computing Strongly Connected Components in Parallel on CUDA. Faculty of Informatics, Masaryk University, Botanicka ́ 68a, 60200 Brno, Czech Republic.
Retrieved from "https://algowiki-project.org/algowiki/en/index.php?title=DCSC_algorithm_for_finding_the_strongly_connected_components&oldid=1041"