DCSC for finding the strongly connected components, C++, MPI, Parallel Boost Graph Library
Основные авторы описания: И.В.Афанасьев
Содержание
1 Ссылки
Parallel Boost Graph Library (функция strong_components
), распределённый алгоритм DCSC сочетается с локальным поиском компонент сильной связности алгоритмом Тарьяна.
2 Локальность данных и вычислений
2.1 Локальность реализации алгоритма
2.1.1 Структура обращений в память и качественная оценка локальности
2.1.2 Количественная оценка локальности
3 Масштабируемость алгоритма и его реализации
3.1 Масштабируемость алгоритма
Алгоритм обладает значительным потенциалом масштабируемости, так как, во-первых, поиск в ширину, на котором он основывается, поддается эффективному распараллеливанию либо при помощи квадратичного подхода, либо при помощи параллельных очередей (по очереди на процессор). Во-вторых, дополнительный ресурс параллелизма можно задействовать при параллельной обработке трех получающихся множеств вершин на каждом шаге алгоритма, используя механизмы tasks и nested parallelism.
3.2 Масштабируемость реализации алгоритма
Проведём исследование масштабируемости параллельной реализации алгоритма Forward-Backward-Trim согласно методике. Исследование проводилось на суперкомпьютере "Ломоносов-2" Суперкомпьютерного комплекса Московского университета.
Набор и границы значений изменяемых параметров запуска реализации алгоритма:
число процессоров [1 : 28] с шагом 1; размер графа [2^20 : 2^27].
Проведем отдельные исследования сильной масштабируемости вширь указанной реализации.
Производительность определена как TEPS (от англ. Traversed Edges Per Second), то есть число ребер графа, который алгоритм обрабатывает в секунду. С помощью данной метрики можно сравнивать производительность для различных размеров графа, оценивая, насколько понижается эффективность обработки графа при увеличении его размера.