DCSC for finding the strongly connected components, C++, MPI, Parallel Boost Graph Library

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

1 Ссылки

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

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

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

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

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

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

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

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

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

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

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