Алгоритм Пурдома - История изменений

ASA в 09:59, 5 июля 2022

2022-07-05T09:59:16Z

@@ Строка 183: / Строка 183: @@
 == Программная реализация алгоритма ==
 === Особенности реализации последовательного алгоритма ===
 === Возможные способы и особенности параллельной реализации алгоритма ===
+=== Результаты прогонов ===
 === Выводы для классов архитектур ===
 == Литература ==

Ikramov: /* Масштабируемость реализации алгоритма */

2017-11-19T18:19:29Z

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

← Предыдущая версия		Версия от 18:19, 19 ноября 2017
Строка 199:		Строка 199:
	Дело в том, что сложность выбранного алгоритма Пурдома зависит от количества ребер в графе нелинейно и, кроме того, зависит еще и от структуры графа (количества сильно связанных компонент).		Дело в том, что сложность выбранного алгоритма Пурдома зависит от количества ребер в графе нелинейно и, кроме того, зависит еще и от структуры графа (количества сильно связанных компонент).

	[[file:Замыкание scaling wide.png\|thumb\|center\|700px\|Рисунок 2. Параллельная реализация алгоритма Пурдома: масштабируемость различных версий: ~~производительность~~ в зависимости от размера графа.]]		[[file:Замыкание scaling wide.png\|thumb\|center\|700px\|Рисунок 3. Параллельная реализация алгоритма Пурдома: масштабируемость различных версий: время выполнения в зависимости от размера графа.]]

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

Ikramov: /* Масштабируемость реализации алгоритма */

2017-11-19T17:53:07Z

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

← Предыдущая версия		Версия от 17:53, 19 ноября 2017
Строка 195:		Строка 195:
	Для демонстрации эффективности представлены графики времени выполнения различных режимов вычислений в зависимости от размера входного графа.		Для демонстрации эффективности представлены графики времени выполнения различных режимов вычислений в зависимости от размера входного графа.

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

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

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

	Анализируя время выполнения можно оценить, насколько понижается эффективность обработки графа при увеличении его размера (данные перестают помещаться в кэш, в память GPU, узла и т.д.). На представленных графиках по оси X граф с каждым делением увеличивается в два раза, и по ~~представленному~~ графику можно оценивать, ~~на сколько~~ увеличилось время выполнения.		Анализируя время выполнения, можно оценить, насколько понижается эффективность обработки графа при увеличении его размера (данные перестают помещаться в кэш, в память GPU, узла и т.д.). На представленных графиках по оси X граф с каждым делением увеличивается в два раза, и по такому графику можно оценивать, насколько увеличилось время выполнения.
	~~Так же~~ время выполнения можно сравнивать для различных версий, например, последовательной CPU, параллельной CPU или же GPU.		Также время выполнения можно сравнивать для различных версий, например, последовательной CPU, параллельной CPU или же GPU.
	На приведенной диаграмме (рисунок 1) для различных размеров графа (от 2^20 до 2^26) представлено время выполнения трех различных версий: последовательной, параллельной CPU и GPU. Шкала на данной диаграмме логарифмическая.		На приведенной диаграмме (рисунок 1) для различных размеров графа (от 2^20 до 2^26) представлено время выполнения трех различных версий: последовательной, параллельной CPU и GPU. Шкала на данной диаграмме логарифмическая.

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

2017-11-19T14:10:03Z

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

← Предыдущая версия		Версия от 14:10, 19 ноября 2017
Строка 188:		Строка 188:
	===== Количественная оценка локальности =====		===== Количественная оценка локальности =====
	=== Возможные способы и особенности параллельной реализации алгоритма ===		=== Возможные способы и особенности параллельной реализации алгоритма ===
	Программа, реализующая поиск транзитного замыкания, состоит CPU части, отвечающей за общую координацию вычислений, использующей вспомогательные классы.

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

Elijah: /* Вычислительное ядро алгоритма */

2017-11-19T14:08:42Z

Вычислительное ядро алгоритма

← Предыдущая версия		Версия от 14:08, 19 ноября 2017
Строка 36:		Строка 36:
	Важно заметить, что некоторые алгоритмы поиска сильно-связанных компонент (например, DCSC) также основываются на поисках в ширину. Таким образом, вычислительным ядром алгоритма можно считать поиск в ширину. В свою очередь вычислительным ядром алгоритма поиска в ширину является обход вершин, смежных с выбранной вершиной, с последующим добавлением еще не посещенных вершин в множество "передовых" вершин.		Важно заметить, что некоторые алгоритмы поиска сильно-связанных компонент (например, DCSC) также основываются на поисках в ширину. Таким образом, вычислительным ядром алгоритма можно считать поиск в ширину. В свою очередь вычислительным ядром алгоритма поиска в ширину является обход вершин, смежных с выбранной вершиной, с последующим добавлением еще не посещенных вершин в множество "передовых" вершин.

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

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

Elijah: /* Вычислительное ядро алгоритма */

2017-11-19T14:07:01Z

Вычислительное ядро алгоритма

← Предыдущая версия		Версия от 14:07, 19 ноября 2017
Строка 36:		Строка 36:
	Важно заметить, что некоторые алгоритмы поиска сильно-связанных компонент (например, DCSC) также основываются на поисках в ширину. Таким образом, вычислительным ядром алгоритма можно считать поиск в ширину. В свою очередь вычислительным ядром алгоритма поиска в ширину является обход вершин, смежных с выбранной вершиной, с последующим добавлением еще не посещенных вершин в множество "передовых" вершин.		Важно заметить, что некоторые алгоритмы поиска сильно-связанных компонент (например, DCSC) также основываются на поисках в ширину. Таким образом, вычислительным ядром алгоритма можно считать поиск в ширину. В свою очередь вычислительным ядром алгоритма поиска в ширину является обход вершин, смежных с выбранной вершиной, с последующим добавлением еще не посещенных вершин в множество "передовых" вершин.

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

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

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

2017-11-19T11:56:27Z

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

← Предыдущая версия		Версия от 11:56, 19 ноября 2017
Строка 145:		Строка 145:
	Инициализация сильно связанных компонент [1] может производиться параллельно и требует <math>\|V\|</math> операций.		Инициализация сильно связанных компонент [1] может производиться параллельно и требует <math>\|V\|</math> операций.

	Поиск сильно связанных компонент может иметь различный ресурс параллелизма, в зависимости от выбора алгоритма.		Поиск сильно связанных компонент может иметь различный ресурс параллелизма в зависимости от выбора алгоритма.

	Добавление вершин и ребер к графу промежуточного представления [2]-[7] требует <math>\|E\|</math> и <math>\|u\|</math> операций (<math>u</math> - число сильно связанных компонент исходного графа), которые ~~так же~~ могут выполняться параллельно. При этом, вершины и ребра добавляются к графу независимо друг от друга, поэтому добавление вершин может производиться параллельно с добавлением ребер.		Добавление вершин и ребер к графу промежуточного представления [2]-[7] требует <math>\|E\|</math> и <math>\|u\|</math> операций (<math>u</math> - число сильно связанных компонент исходного графа), которые также могут выполняться параллельно. При этом вершины и ребра добавляются к графу независимо друг от друга, поэтому добавление вершин может производиться параллельно с добавлением ребер.

	Проверка номеров сильно связанных компонент [8] ~~так же~~ может выполняться параллельно и требует <math>\|n\|</math> операций (<math>n</math> - число пар вершин, подаваемых на выход), которые ~~так же~~ могут выполняться параллельно.		Проверка номеров сильно связанных компонент [8] также может выполняться параллельно и требует <math>\|n\|</math> операций (<math>n</math> - число пар вершин, подаваемых на выход), которые также могут выполняться параллельно.

	В случае ~~принаделжности~~ вершин одной пары к одной сильно ~~связанный~~ компоненте, производится поиск в ширину [BFS], для каждой соответствующей пары. Данные поиски в ширину ~~так же~~ могут выполняться параллельно друг другу, при ~~том~~ каждый поиск в ширину имеет определенный ресурс параллелизма, описанный в соответствующем [[Поиск_в_ширину_(BFS)\|разделе]].		В случае принадлежности вершин одной пары к одной сильно связанной компоненте производится поиск в ширину [BFS] для каждой соответствующей пары. Данные поиски в ширину также могут выполняться параллельно друг другу, при этом каждый поиск в ширину имеет определенный ресурс параллелизма, описанный в соответствующем [[Поиск_в_ширину_(BFS)\|разделе]].

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

Ikramov: /* Последовательная сложность алгоритма */

2017-11-19T09:19:05Z

Последовательная сложность алгоритма

← Предыдущая версия		Версия от 09:19, 19 ноября 2017
Строка 107:		Строка 107:
	Первый и второй этап выполняются с помощью поиска в глубину со сложностью <math>O(\|E\|)</math>.		Первый и второй этап выполняются с помощью поиска в глубину со сложностью <math>O(\|E\|)</math>.

	На третьем этапе ~~основой~~ операцией является объединение списков вершин. В случае хранения списков в отсортированном виде объединение выполняется за линейное время. Количество списков не превосходит <math>\|V\|</math>, а в каждом списке не более <math>\mu</math> вершин, где <math>\mu</math> – количество компонент сильной связности. Общая сложность тогда составляет <math>O(\mu^2)</math>. Альтернативным ~~форматов~~ хранения списка вершин является битовая маска с такой же общей сложностью.		На третьем этапе основной операцией является объединение списков вершин. В случае хранения списков в отсортированном виде объединение выполняется за линейное время. Количество списков не превосходит <math>\|V\|</math>, а в каждом списке не более <math>\mu</math> вершин, где <math>\mu</math> – количество компонент сильной связности. Общая сложность тогда составляет <math>O(\mu^2)</math>. Альтернативным форматом хранения списка вершин является битовая маска с такой же общей сложностью.

	Сложность четвёртого этапа составляет <math>O(\mu \|V\|)</math>, так как для каждой из <math>\mu</math> компонент сильной связности за линейное время вычисляется список вершин из не более чем <math>\|V\|</math> вершин. Поскольку компоненты сильной связности не пересекаются, на данном этапе уже не требуется хранить списки в отсортированном виде.		Сложность четвёртого этапа составляет <math>O(\mu \|V\|)</math>, так как для каждой из <math>\mu</math> компонент сильной связности за линейное время вычисляется список вершин из не более чем <math>\|V\|</math> вершин. Поскольку компоненты сильной связности не пересекаются, на данном этапе уже не требуется хранить списки в отсортированном виде.

Ikramov: /* Вычислительное ядро алгоритма */

2017-11-18T00:09:51Z

Вычислительное ядро алгоритма

← Предыдущая версия		Версия от 00:09, 18 ноября 2017
Строка 30:		Строка 30:
	# Поиски в ширину в графе промежуточного представления для построения итогового транзитивного замыкания		# Поиски в ширину в графе промежуточного представления для построения итогового транзитивного замыкания

	1. В случае решения задачи проверки принадлежности к транзитивному замыканию множества заданных пар вершин, соотношение объемов различных вычислительных частей алгоритма может быть очень различным и, очевидно, зависит от числа пар входных вершин. Кроме того, данное соотношение может также зависеть от типа входного графа, так как структура и количество сильно-связанных компонент сильно влияют как на время поиска сильно-связанных компонент, так и на время выполнения поисков в ширину. Далее представлена таблица, демонстрирующая процент времени выполнения данных частей для одной из реализаций алгоритма для различных типов графов с числом вершин <math>2^{23}</math>, и числом входных пар вершин для проверки равным 10000.		1. В случае решения задачи проверки принадлежности к транзитивному замыканию множества заданных пар вершин, соотношение объемов различных вычислительных частей алгоритма может быть очень различным и, очевидно, зависит от числа пар входных вершин. Кроме того, данное соотношение может также зависеть от типа входного графа, так как структура и количество сильно-связанных компонент сильно влияют как на время поиска сильно-связанных компонент, так и на время выполнения поисков в ширину. Далее представлена таблица, демонстрирующая процент времени выполнения данных частей для одной из реализаций алгоритма для различных типов графов с числом вершин <math>2^{23}</math> и числом входных пар вершин для проверки, равным 10000.

	[[file:Purdom_time_table.png\|thumb\|center\|500px\|Рисунок 1. Сравнение времени выполнения различных частей одной из реализаций алгоритма Пурдома.]]		[[file:Purdom_time_table.png\|thumb\|center\|500px\|Рисунок 1. Сравнение времени выполнения различных частей одной из реализаций алгоритма Пурдома.]]

Ikramov: /* Вычислительное ядро алгоритма */

2017-11-18T00:06:50Z

Вычислительное ядро алгоритма

← Предыдущая версия		Версия от 00:06, 18 ноября 2017
Строка 27:		Строка 27:
	Алгоритм состоит из трех важных вычислительных частей, для каждой из которых важно оценить относительное время выполнения относительно других частей.		Алгоритм состоит из трех важных вычислительных частей, для каждой из которых важно оценить относительное время выполнения относительно других частей.
	# Поиск сильно связанных компонент в исходном графе		# Поиск сильно связанных компонент в исходном графе
	# ~~Построения~~ графа промежуточного представления		# Построение графа промежуточного представления
	# ~~Поисков~~ в ширину в графе промежуточного представления для построения итогового транзитивного замыкания		# Поиски в ширину в графе промежуточного представления для построения итогового транзитивного замыкания

	1. В случае решения задачи проверки принадлежности к транзитивному замыканию ~~множество~~ заданных пар вершин, соотношение объемов различных вычислительных частей алгоритма может быть очень различным, и, очевидно, зависит от числа пар входных вершин. Кроме того, данное соотношение может ~~так же~~ зависеть от типа входного графа, так как структура и количество сильно-связанных компонент сильно влияют как на время поиска сильно-связанных компонент, так и на время выполнения поисков в ширину. Далее представлена таблица, демонстрирующая процент времени выполнения данных частей для одной из реализаций алгоритма для различных типов графов с числом вершин <math>2^{23}</math>, и числом входных пар вершин для проверки равным 10000.		1. В случае решения задачи проверки принадлежности к транзитивному замыканию множества заданных пар вершин, соотношение объемов различных вычислительных частей алгоритма может быть очень различным и, очевидно, зависит от числа пар входных вершин. Кроме того, данное соотношение может также зависеть от типа входного графа, так как структура и количество сильно-связанных компонент сильно влияют как на время поиска сильно-связанных компонент, так и на время выполнения поисков в ширину. Далее представлена таблица, демонстрирующая процент времени выполнения данных частей для одной из реализаций алгоритма для различных типов графов с числом вершин <math>2^{23}</math>, и числом входных пар вершин для проверки равным 10000.

	[[file:Purdom_time_table.png\|thumb\|center\|500px\|Рисунок 1. Сравнение ~~времни~~ выполнения различных частей ~~алгоритма Пурдома~~ одной из реализаций..]]		[[file:Purdom_time_table.png\|thumb\|center\|500px\|Рисунок 1. Сравнение времени выполнения различных частей одной из реализаций алгоритма Пурдома.]]

	Важно заметить, что некоторые алгоритмы поиска сильно-связанных компонент (например DCSC) ~~так же~~ основываются на ~~поиска~~ в ширину. Таким образом, вычислительным ядром алгоритма можно считать поиск в ширину. В свою очередь вычислительным ядром алгоритма поиска в ширину является обход вершин, ~~смежной к~~ выбранной ~~вершине~~ с ~~последующем~~ добавлением еще не посещенных вершин в множество "передовых" вершин.		Важно заметить, что некоторые алгоритмы поиска сильно-связанных компонент (например, DCSC) также основываются на поисках в ширину. Таким образом, вычислительным ядром алгоритма можно считать поиск в ширину. В свою очередь вычислительным ядром алгоритма поиска в ширину является обход вершин, смежных с выбранной вершиной, с последующим добавлением еще не посещенных вершин в множество "передовых" вершин.

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

← Предыдущая версия		Версия от 09:19, 19 ноября 2017
Строка 107:		Строка 107:
	Первый и второй этап выполняются с помощью поиска в глубину со сложностью <math>O(\|E\|)</math>.		Первый и второй этап выполняются с помощью поиска в глубину со сложностью <math>O(\|E\|)</math>.

	На третьем этапе ~~основой~~ операцией является объединение списков вершин. В случае хранения списков в отсортированном виде объединение выполняется за линейное время. Количество списков не превосходит <math>\|V\|</math>, а в каждом списке не более <math>\mu</math> вершин, где <math>\mu</math> – количество компонент сильной связности. Общая сложность тогда составляет <math>O(\mu^2)</math>. Альтернативным ~~форматов~~ хранения списка вершин является битовая маска с такой же общей сложностью.		На третьем этапе основной операцией является объединение списков вершин. В случае хранения списков в отсортированном виде объединение выполняется за линейное время. Количество списков не превосходит <math>\|V\|</math>, а в каждом списке не более <math>\mu</math> вершин, где <math>\mu</math> – количество компонент сильной связности. Общая сложность тогда составляет <math>O(\mu^2)</math>. Альтернативным форматом хранения списка вершин является битовая маска с такой же общей сложностью.

	Сложность четвёртого этапа составляет <math>O(\mu \|V\|)</math>, так как для каждой из <math>\mu</math> компонент сильной связности за линейное время вычисляется список вершин из не более чем <math>\|V\|</math> вершин. Поскольку компоненты сильной связности не пересекаются, на данном этапе уже не требуется хранить списки в отсортированном виде.		Сложность четвёртого этапа составляет <math>O(\mu \|V\|)</math>, так как для каждой из <math>\mu</math> компонент сильной связности за линейное время вычисляется список вершин из не более чем <math>\|V\|</math> вершин. Поскольку компоненты сильной связности не пересекаются, на данном этапе уже не требуется хранить списки в отсортированном виде.