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

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

2022-07-06T12:13:01Z

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

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

2017-11-22T09:41:53Z

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

← Предыдущая версия		Версия от 09:41, 22 ноября 2017
Строка 225:		Строка 225:
	==== Масштабируемость алгоритма ====		==== Масштабируемость алгоритма ====

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

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

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

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

2017-11-22T09:16:38Z

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

← Предыдущая версия		Версия от 09:16, 22 ноября 2017
Строка 225:		Строка 225:
	==== Масштабируемость алгоритма ====		==== Масштабируемость алгоритма ====

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

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

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

2017-11-22T08:37:25Z

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

← Предыдущая версия		Версия от 08:37, 22 ноября 2017
Строка 227:		Строка 227:
	Алгоритм обладает значительным потенциалом масштабируемости, так как, во-первых, поиск в ширину, на котором он основывается, поддается эффективному распараллеливанию либо при помощи квадратичнго подхода, либо при помощи параллельных очередей (по очереди на процессор).		Алгоритм обладает значительным потенциалом масштабируемости, так как, во-первых, поиск в ширину, на котором он основывается, поддается эффективному распараллеливанию либо при помощи квадратичнго подхода, либо при помощи параллельных очередей (по очереди на процессор).

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

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

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

2017-11-22T08:36:04Z

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

← Предыдущая версия		Версия от 08:36, 22 ноября 2017
Строка 227:		Строка 227:
	Алгоритм обладает значительным потенциалом масштабируемости, так как, во-первых, поиск в ширину, на котором он основывается, поддается эффективному распараллеливанию либо при помощи квадратичнго подхода, либо при помощи параллельных очередей (по очереди на процессор).		Алгоритм обладает значительным потенциалом масштабируемости, так как, во-первых, поиск в ширину, на котором он основывается, поддается эффективному распараллеливанию либо при помощи квадратичнго подхода, либо при помощи параллельных очередей (по очереди на процессор).

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

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

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

2017-11-22T08:35:39Z

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

← Предыдущая версия		Версия от 08:35, 22 ноября 2017
Строка 227:		Строка 227:
	Алгоритм обладает значительным потенциалом масштабируемости, так как, во-первых, поиск в ширину, на котором он основывается, поддается эффективному распараллеливанию либо при помощи квадратичнго подхода, либо при помощи параллельных очередей (по очереди на процессор).		Алгоритм обладает значительным потенциалом масштабируемости, так как, во-первых, поиск в ширину, на котором он основывается, поддается эффективному распараллеливанию либо при помощи квадратичнго подхода, либо при помощи параллельных очередей (по очереди на процессор).

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

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

Ikramov: /* Свойства алгоритма */

2017-11-21T19:09:06Z

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

← Предыдущая версия		Версия от 19:09, 21 ноября 2017
Строка 213:		Строка 213:
	=== Свойства алгоритма ===		=== Свойства алгоритма ===

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

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

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

2017-11-21T14:23:20Z

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

← Предыдущая версия		Версия от 14:23, 21 ноября 2017
Строка 193:		Строка 193:
	Ресурс параллелизма операции поиска в ширину подробно описан в соответствующем разделе ([[Поиск_в_ширину_(BFS)]]). В зависимости от выбора формата хранения графа, подход к параллельной реализации поиска в ширину может быть линейным или квадратичным (в худшем случае).		Ресурс параллелизма операции поиска в ширину подробно описан в соответствующем разделе ([[Поиск_в_ширину_(BFS)]]). В зависимости от выбора формата хранения графа, подход к параллельной реализации поиска в ширину может быть линейным или квадратичным (в худшем случае).

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

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

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

2017-11-21T13:02:53Z

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

← Предыдущая версия		Версия от 13:02, 21 ноября 2017
Строка 191:		Строка 191:
	Этап 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) могут быть успешно векторизованы.		Этап 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)]]). В зависимости от выбора формата хранения графа, подход к параллельной реализации поиска в ширину может быть линейным или квадратичным (в худшем случае).		Ресурс параллелизма операции поиска в ширину подробно описан в соответствующем разделе ([[Поиск_в_ширину_(BFS)]]). В зависимости от выбора формата хранения графа, подход к параллельной реализации поиска в ширину может быть линейным или квадратичным (в худшем случае).

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

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

2017-11-21T12:02:36Z

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

← Предыдущая версия		Версия от 12:02, 21 ноября 2017
Строка 189:		Строка 189:
	На верхнем уровне алгоритм DCSC может параллельно выполнять FB-шаги, продемонстрированные на рисунке 1. Таким образом, на каждом рекурсивном шаге алгоритма могут рекурсивно порождаться до 3 новых параллельных процессов, общее число которых равно числу сильно связанных компонент графа. Кроме того, поиски в ширину в исходном и транспонированном графах независимы и также могут выполняться параллельно друг с другом. Таким образом, на верхнем уровне может выполняться до <math> 2*u/log\|u\|</math> параллельных потоков, где <math> u </math> - это число сильно связанных компонент графа. Важно заметить, что вычисления FB-шагов одного уровня (а также всех последующих рекурсивных) абсолютно независимы по данным, так как производятся в непересекающихся множествах вершин графа, поэтому могут производиться в том числе и на различных узлах. Кроме того, составные шаги алгоритма (поиск в ширину и шаг Trim) также имеют значительный потенциал параллелизма, описанный далее.		На верхнем уровне алгоритм DCSC может параллельно выполнять FB-шаги, продемонстрированные на рисунке 1. Таким образом, на каждом рекурсивном шаге алгоритма могут рекурсивно порождаться до 3 новых параллельных процессов, общее число которых равно числу сильно связанных компонент графа. Кроме того, поиски в ширину в исходном и транспонированном графах независимы и также могут выполняться параллельно друг с другом. Таким образом, на верхнем уровне может выполняться до <math> 2*u/log\|u\|</math> параллельных потоков, где <math> u </math> - это число сильно связанных компонент графа. Важно заметить, что вычисления FB-шагов одного уровня (а также всех последующих рекурсивных) абсолютно независимы по данным, так как производятся в непересекающихся множествах вершин графа, поэтому могут производиться в том числе и на различных узлах. Кроме того, составные шаги алгоритма (поиск в ширину и шаг 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) могут быть успешно векторизованы.		Этап 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)]]). В зависимости от выбора формата хранения графа, подход к параллельной реализации поиска в ширину может быть линейным или квадратичным (в худшем случае).		Ресурс параллелизма операции поиска в ширину подробно описан в соответвующем разделе ([[Поиск_в_ширину_(BFS)]]). В зависимости от выбора формата хранения графа, подход к параллельной реализации поиска в ширину может быть линейным или квадратичным (в худшем случае).