Алгоритм DCSC поиска компонент сильной связности

Алгоритм DCSC поиска компонент сильной связности
Последовательный алгоритм
Последовательная сложность	[math]O(n \ln n)[/math]
Объём входных данных	[math]O(m + n)[/math]
Объём выходных данных	[math]O(n)[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math]O(E)[/math]
Ширина ярусно-параллельной формы	[math]C * O(ln(u))[/math]

Основные авторы описания: И.В.Афанасьев

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

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

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

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

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

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

1.2 Математическое описание алгоритма

Пусть [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 Вычислительное ядро алгоритма

Основными вычислительными операциями алгоритма является поиск вершин, достижимых из выбранной вершины [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 Макроструктура алгоритма

Алгоритм 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 Схема реализации последовательного алгоритма

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

Входные данные:
  граф с вершинами 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 Последовательная сложность алгоритма

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

1.7 Информационный граф

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.8 Ресурс параллелизма алгоритма

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

На верхнем уровне алгоритм 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] параллельных операций.

1.9 Входные и выходные данные алгоритма

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

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

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

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

1.10 Свойства алгоритма

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

2 Программная реализация алгоритма

2.1 Особенности реализации последовательного алгоритма

2.2 Локальность данных и вычислений

2.2.1 Локальность реализации алгоритма

2.2.1.1 Структура обращений в память и качественная оценка локальности

2.2.1.2 Количественная оценка локальности

2.3 Возможные способы и особенности параллельной реализации алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.4.1 Масштабируемость алгоритма

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

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

2.4.2 Масштабируемость реализации алгоритма

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

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

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

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

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

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

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

2.7 Существующие реализации алгоритма

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

3 Литература

↑ 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.
↑ 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.
↑ 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.
↑ 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.

[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.

[1]

[2]

[3]

[4]