Я должен найти лучший алгоритм из уже известных для параллельного вычисления связанных компонент графа.
Вот краткое описание моих данных и компьютерной архитектуры:
- У меня есть доступ к вычислительному кластеру с несколькими тысячами
процессоры (память не разделяется, но я ожидаю, что там должно быть
достаточно памяти в одном узле, чтобы оценить мои потребности в целом
данные).
- мой график имеет довольно небольшое отношение числа ребер к числу вершин (около 5)
- Я ожидаю, что большинство подключенных компонентов будет очень маленьким (2-3 вершины)
- однако будут очень большие компоненты с миллионами вершин (составляющие даже до 10% от общего числа вершин).
Я читал о параллельных алгоритмах для вычисления связанных компонентов графов. Как я уже заметил, некоторые из них основаны на классическом подходе BFS для сериализованного случая. Если честно, я немного потерялся в количестве этих алгоритмов. Кто-нибудь может дать мне какой-нибудь совет, какой алгоритм будет лучшим для моих целей?