Алгоритм Тарьяна-Вишкина поиска компонент двусвязности - История изменений

ASA в 12:50, 6 июля 2022

2022-07-06T12:50:45Z

← Предыдущая версия		Версия от 12:50, 6 июля 2022
Строка 113:		Строка 113:
	== Программная реализация алгоритма ==		== Программная реализация алгоритма ==
	=== Особенности реализации последовательного алгоритма ===		=== Особенности реализации последовательного алгоритма ===
	~~=== Локальность данных и вычислений ===~~
	~~==== Локальность реализации алгоритма ====~~
	~~===== Структура обращений в память и качественная оценка локальности =====~~
	~~===== Количественная оценка локальности =====~~
	=== Возможные способы и особенности параллельной реализации алгоритма ===		=== Возможные способы и особенности параллельной реализации алгоритма ===

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

	=== ~~Масштабируемость алгоритма и его реализации ===~~		=== Результаты прогонов ===
	~~==== Масштабируемость алгоритма ====~~
	~~==== Масштабируемость реализации алгоритма ====~~
	Проведём исследование масштабируемости параллельной реализации алгоритма Тарьяна-Вишкина согласно [[Scalability methodology\|методике]]. Исследование проводилось на суперкомпьютере "Ломоносов-2 [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета].

	~~Набор и границы значений изменяемых [[Глоссарий#Параметры запуска\|параметров запуска]] реализации алгоритма:~~


	* размер графа [2^18 : 2^26].

	~~Проведем отдельные исследования масштабируемости вширь реализации алгоритма Тарьяна-Вишкина.~~

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

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


	[[file:Tarjan vishkin scaling wide.png\|thumb\|center\|700px\|Рисунок 2. Параллельная реализация алгоритма Тарьяна-Вишкина масштабируемость вширь: производительность в зависимости от размера графа]]

	~~=== Динамические характеристики и эффективность реализации алгоритма~~ ===
	=== Выводы для классов архитектур ===		=== Выводы для классов архитектур ===
	~~=== Существующие реализации алгоритма ===~~

	== Литература ==		== Литература ==

	<references />		<references />

Elijah: /* Математическое описание алгоритма */

2017-11-22T10:47:27Z

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

← Предыдущая версия		Версия от 10:47, 22 ноября 2017
Строка 23:		Строка 23:
	3. В порядке возрастания номера вершины <math>N(v) </math> выполнить следующие действия:		3. В порядке возрастания номера вершины <math>N(v) </math> выполнить следующие действия:

	a. <math>D(v) := 1+ \sum_{v \rightarrow w}D(w) </math>, величины <math>D(W)</math> определяются рекурсивно,<math>D(W)=1</math> для концевых вершин.		a. <math>D(v) := 1+ \sum_{v \rightarrow w}D(w) </math>, величины <math>D(W)</math> определяются рекурсивно, <math>D(W)=1</math> для концевых вершин.

	b. <math> L(v) := \min { \{N(v) - D(v)+1 \} \cup \{ L(w) \| v \rightarrow w \} \cup \{ N(w) \| v \cdots w \} }</math>		b. <math> L(v) := \min { \{N(v) - D(v)+1 \} \cup \{ L(w) \| v \rightarrow w \} \cup \{ N(w) \| v \cdots w \} }</math>

Elijah: /* Математическое описание алгоритма */

2017-11-22T10:47:12Z

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

← Предыдущая версия		Версия от 10:47, 22 ноября 2017
Строка 23:		Строка 23:
	3. В порядке возрастания номера вершины <math>N(v) </math> выполнить следующие действия:		3. В порядке возрастания номера вершины <math>N(v) </math> выполнить следующие действия:

	a. <math>D(v) := 1+ \sum_{v \rightarrow w}D(w) </math>, величины <math>D(W)</math> определяются рекурсивно.		a. <math>D(v) := 1+ \sum_{v \rightarrow w}D(w) </math>, величины <math>D(W)</math> определяются рекурсивно,<math>D(W)=1</math> для концевых вершин.

	b. <math> L(v) := \min { \{N(v) - D(v)+1 \} \cup \{ L(w) \| v \rightarrow w \} \cup \{ N(w) \| v \cdots w \} }</math>		b. <math> L(v) := \min { \{N(v) - D(v)+1 \} \cup \{ L(w) \| v \rightarrow w \} \cup \{ N(w) \| v \cdots w \} }</math>

Elijah: /* Математическое описание алгоритма */

2017-11-22T10:45:28Z

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

← Предыдущая версия		Версия от 10:45, 22 ноября 2017
Строка 23:		Строка 23:
	3. В порядке возрастания номера вершины <math>N(v) </math> выполнить следующие действия:		3. В порядке возрастания номера вершины <math>N(v) </math> выполнить следующие действия:

	a. <math>D(v) := 1+ \sum_{v \rightarrow w}D(w) </math>		a. <math>D(v) := 1+ \sum_{v \rightarrow w}D(w) </math>, величины <math>D(W)</math> определяются рекурсивно.

	b. <math> L(v) := \min { \{N(v) - D(v)+1 \} \cup \{ L(w) \| v \rightarrow w \} \cup \{ N(w) \| v \cdots w \} }</math>		b. <math> L(v) := \min { \{N(v) - D(v)+1 \} \cup \{ L(w) \| v \rightarrow w \} \cup \{ N(w) \| v \cdots w \} }</math>

Elijah: /* Ресурс параллелизма алгоритма */

2017-11-22T10:43:29Z

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

← Предыдущая версия		Версия от 10:43, 22 ноября 2017
Строка 80:		Строка 80:
	=== Ресурс параллелизма алгоритма ===		=== Ресурс параллелизма алгоритма ===

	Алгоритм изначально ~~параллельный~~, время работы <math>O(\ln(\|V\|))</math> на <math>O(\|V\| + \|E\|)</math> процессорах.		Алгоритм изначально разрабатывался для параллельной реализации, его время работы составляет <math>O(\ln(\|V\|))</math> на <math>O(\|V\| + \|E\|)</math> процессорах.

	Изначальные инициализации компонент и уровней вершин [1] и [3] могут выполняться параллельно за <math>O(\|V\|)</math> операций. Шаг трим [2] так же может быть выполнен за <math>O(\|E\|)</math> параллельных атомарных операций. Поиски в ширину от каждой корневой вершины [4],[BFS] производятся последовательно друг за другом, однако сами поиски в ширину обладают значительным образом параллелизма, описанным в соответствующем [[Поиск_в_ширину_(BFS)\|разделе]].		Изначальные инициализации связанных компонент и уровней вершин [1] и [3] могут выполняться параллельно за <math>O(\|V\|)</math> операций. Шаг трим [2] так же может быть выполнен за <math>O(\|E\|)</math> параллельных атомарных операций. Поиски в ширину от каждой корневой вершины [4],[BFS] производятся последовательно друг за другом, однако сами поиски в ширину обладают значительным образом параллелизма, описанным в соответствующем [[Поиск_в_ширину_(BFS)\|разделе]].

	Нумерация вершин <math>D(v)</math> в порядке обходе графа ~~поиском~~ в глубину [5],[6] ~~должно~~ выполняться сугубо последовательно за <math>O(\|V\|)</math> операций, и может, вообще говоря, серьезно снизить производительность реализации на параллельных архитектурах.		Нумерация вершин <math>D(v)</math> в обратном порядке обходе графа производится при помощи поиска в глубину [5],[6], который должен выполняться сугубо последовательно за <math>O(\|V\|)</math> операций, и может, вообще говоря, серьезно снизить производительность реализации на параллельных архитектурах.

	~~Вычисление~~ величин <math>L</math>, <math>H</math> и ребер, ~~являющихся мостами~~ [8],[9],[10] может выполняться ~~каждое~~ за <math>O(\|V\|)</math> операций.		Каждое из вычислений величин <math>L</math>, <math>H</math>, а так же проверка ребер на свойство, является ли каждое их них мостом [8],[9],[10], может выполняться параллельно за <math>O(\|V\|)</math> операций.

	Таким образом, ширина ярусно-параллельной формы алгоритма равна <math>O(\|E\|)</math>, а высота ЯПФ, вообще говоря, зависит от структуры входного графа (числа связанных компонент, и, как следствие, числа необходимых поисков в ширину).		Таким образом, ширина ярусно-параллельной формы алгоритма равна <math>O(\|E\|)</math>, а высота ЯПФ, вообще говоря, зависит от структуры входного графа (числа связанных компонент, и, как следствие, числа необходимых поисков в ширину).

Elijah: /* Информационный граф */

2017-11-22T10:33:06Z

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

← Предыдущая версия		Версия от 10:33, 22 ноября 2017
Строка 74:		Строка 74:
	[[file:tarjan_vishkin_ig.png\|thumb\|center\|600px\|Рисунок 1 – Информационный граф алгоритма Тарьяна-Вышкина]]		[[file:tarjan_vishkin_ig.png\|thumb\|center\|600px\|Рисунок 1 – Информационный граф алгоритма Тарьяна-Вышкина]]

	В начале работы алгоритм производит инциализацию связанных компонент графа [1], с последующим выделением тривиальных компонент (размера 1 и 2) [2]; затем производится инициализация уровней для всех вершин [3] при помощи последовательных поисков в ширину [4],[BFS] выполняемых до тех пор, пока все вершины не будут размечены различными уровнями.		В начале работы алгоритм производит инциализацию связанных компонент графа [1], с последующим выделением тривиальных компонент (размера 1 и 2) [2]; затем, производится инициализация уровней для всех вершин [3] при помощи последовательных поисков в ширину [4],[BFS], выполняемых до тех пор, пока все вершины не будут размечены различными уровнями.

	Далее производится поиск ребер, вошедших в остовное дерево [5], с последовательным построением данного дерева на основе поиска в глубину [6],[7]. После этого друг за другом производится вычисление необходимых метрик для каждой из вершин L, H и D [8],[9]. Перед завершением работы алгоритма на основе данных метрик производится вычисление мостов в графе [10].		Далее производится поиск ребер, вошедших в остовное дерево [5], с последовательным построением данного дерева на основе поиска в глубину [6],[7]. После этого друг за другом производится вычисление необходимых метрик для каждой из вершин L, H и D [8],[9]. Перед завершением работы алгоритма на основе данных метрик производится вычисление мостов в графе [10].

Elijah: /* Информационный граф */

2017-11-22T10:32:13Z

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

← Предыдущая версия		Версия от 10:32, 22 ноября 2017
Строка 74:		Строка 74:
	[[file:tarjan_vishkin_ig.png\|thumb\|center\|600px\|Рисунок 1 – Информационный граф алгоритма Тарьяна-Вышкина]]		[[file:tarjan_vishkin_ig.png\|thumb\|center\|600px\|Рисунок 1 – Информационный граф алгоритма Тарьяна-Вышкина]]

	В начале работы ~~производится инциализация~~ связанных компонент графа [1] ~~и выделение~~ тривиальных компонент (размера 1 и 2) [2], затем инициализация уровней для всех вершин [3] ~~и последовательные поиски~~ в ширину [4],[BFS] до тех пор, пока все вершины не будут размечены различными уровнями.		В начале работы алгоритм производит инциализацию связанных компонент графа [1], с последующим выделением тривиальных компонент (размера 1 и 2) [2]; затем производится инициализация уровней для всех вершин [3] при помощи последовательных поисков в ширину [4],[BFS] выполняемых до тех пор, пока все вершины не будут размечены различными уровнями.

	Далее ~~происходит~~ поиск ребер, ~~которые войдут~~ в остовное дерево [5] ~~и последовательное построение~~ данного дерева на основе поиска в глубину [6],[7]. ~~Затем~~ друг за другом ~~вычисляются необходимые метрики~~ для каждой их вершин L, H и D [8],[9]. ~~В конце~~ на основе данных метрик ~~вычисляются мосты~~ в графе [10].		Далее производится поиск ребер, вошедших в остовное дерево [5], с последовательным построением данного дерева на основе поиска в глубину [6],[7]. После этого друг за другом производится вычисление необходимых метрик для каждой из вершин L, H и D [8],[9]. Перед завершением работы алгоритма на основе данных метрик производится вычисление мостов в графе [10].

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

Elijah: /* Макроструктура алгоритма */

2017-11-22T10:28:16Z

Макроструктура алгоритма

← Предыдущая версия		Версия от 10:28, 22 ноября 2017
Строка 53:		Строка 53:
	• вычисление значений <math>L(v)</math> и <math>H(v)</math> для каждой вершины;		• вычисление значений <math>L(v)</math> и <math>H(v)</math> для каждой вершины;

	• пометка рёбер <math>v \rightarrow w</math> мостами, если <math>H(w)<=N(w)</math> и <math>L(w)>N(w)-D(w)</math>.		• пометка рёбер <math>v \rightarrow w</math> мостами, если <math>H(w)<=N(w)</math> и <math>L(w) > N(w)-D(w)</math>.

	Основной идеей для обеспечения завершения работы алгоритма за <math>O( \ln \|V\|)</math> шагов является систематическое использование операции удвоения указателей.		Основной идеей для обеспечения завершения работы алгоритма за <math>O( \ln \|V\|)</math> шагов является систематическое использование операции удвоения указателей.

Elijah: /* Схема реализации последовательного алгоритма */

2017-11-22T10:26:43Z

Схема реализации последовательного алгоритма

← Предыдущая версия		Версия от 10:26, 22 ноября 2017
Строка 61:		Строка 61:
	На первом шаге работы алгоритма строится остовный лес графа при помощи последовательных вызовов поисков в ширину от еще не посещенных на предыдущих шагах вершин. При необходимости может быть выполнен шаг Trim, выделяющий вершины, принадлежащие связанным компонентам единичного размера.		На первом шаге работы алгоритма строится остовный лес графа при помощи последовательных вызовов поисков в ширину от еще не посещенных на предыдущих шагах вершин. При необходимости может быть выполнен шаг Trim, выделяющий вершины, принадлежащие связанным компонентам единичного размера.

	После этого производится построение ~~островного~~ дерева при помощи поиска в глубину, с подсчетом величин <math>D(v)</math>.		После этого производится построение остовного дерева при помощи поиска в глубину, с подсчетом величин <math>D(v)</math>.

	Затем производятся вычисления величин <math>L</math> и <math>H</math> по формулам, приведенным в пунктах b,c в предыдущем разделе.		Затем производятся вычисления величин <math>L</math> и <math>H</math> по формулам, приведенным в пунктах b,c в предыдущем разделе.

Elijah: /* Математическое описание алгоритма */

2017-11-22T10:19:55Z

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

← Предыдущая версия		Версия от 10:19, 22 ноября 2017
Строка 19:		Строка 19:
	1. Для каждой компоненты связности графа найти какое-либо остовное дерево <math>T</math>.		1. Для каждой компоненты связности графа найти какое-либо остовное дерево <math>T</math>.

	2. Перенумеровать вершины <math>T</math> в порядке обратного обхода.		2. Перенумеровать вершины <math>T</math> в порядке обратного обхода <math>N(v) </math>.

	3. В порядке возрастания номера вершины <math>N(v) </math> выполнить следующие действия:		3. В порядке возрастания номера вершины <math>N(v) </math> выполнить следующие действия:

← Предыдущая версия		Версия от 10:43, 22 ноября 2017
Строка 80:		Строка 80:
	=== Ресурс параллелизма алгоритма ===		=== Ресурс параллелизма алгоритма ===

	Алгоритм изначально ~~параллельный~~, время работы <math>O(\ln(\|V\|))</math> на <math>O(\|V\| + \|E\|)</math> процессорах.		Алгоритм изначально разрабатывался для параллельной реализации, его время работы составляет <math>O(\ln(\|V\|))</math> на <math>O(\|V\| + \|E\|)</math> процессорах.

	Изначальные инициализации компонент и уровней вершин [1] и [3] могут выполняться параллельно за <math>O(\|V\|)</math> операций. Шаг трим [2] так же может быть выполнен за <math>O(\|E\|)</math> параллельных атомарных операций. Поиски в ширину от каждой корневой вершины [4],[BFS] производятся последовательно друг за другом, однако сами поиски в ширину обладают значительным образом параллелизма, описанным в соответствующем [[Поиск_в_ширину_(BFS)\|разделе]].		Изначальные инициализации связанных компонент и уровней вершин [1] и [3] могут выполняться параллельно за <math>O(\|V\|)</math> операций. Шаг трим [2] так же может быть выполнен за <math>O(\|E\|)</math> параллельных атомарных операций. Поиски в ширину от каждой корневой вершины [4],[BFS] производятся последовательно друг за другом, однако сами поиски в ширину обладают значительным образом параллелизма, описанным в соответствующем [[Поиск_в_ширину_(BFS)\|разделе]].

	Нумерация вершин <math>D(v)</math> в порядке обходе графа ~~поиском~~ в глубину [5],[6] ~~должно~~ выполняться сугубо последовательно за <math>O(\|V\|)</math> операций, и может, вообще говоря, серьезно снизить производительность реализации на параллельных архитектурах.		Нумерация вершин <math>D(v)</math> в обратном порядке обходе графа производится при помощи поиска в глубину [5],[6], который должен выполняться сугубо последовательно за <math>O(\|V\|)</math> операций, и может, вообще говоря, серьезно снизить производительность реализации на параллельных архитектурах.

	~~Вычисление~~ величин <math>L</math>, <math>H</math> и ребер, ~~являющихся мостами~~ [8],[9],[10] может выполняться ~~каждое~~ за <math>O(\|V\|)</math> операций.		Каждое из вычислений величин <math>L</math>, <math>H</math>, а так же проверка ребер на свойство, является ли каждое их них мостом [8],[9],[10], может выполняться параллельно за <math>O(\|V\|)</math> операций.

	Таким образом, ширина ярусно-параллельной формы алгоритма равна <math>O(\|E\|)</math>, а высота ЯПФ, вообще говоря, зависит от структуры входного графа (числа связанных компонент, и, как следствие, числа необходимых поисков в ширину).		Таким образом, ширина ярусно-параллельной формы алгоритма равна <math>O(\|E\|)</math>, а высота ЯПФ, вообще говоря, зависит от структуры входного графа (числа связанных компонент, и, как следствие, числа необходимых поисков в ширину).