Tarjan-Vishkin biconnected components, scalability
Основные авторы описания: И.В.Афанасьев
Ссылки
Локальность данных и вычислений
Локальность реализации алгоритма
Структура обращений в память и качественная оценка локальности
Количественная оценка локальности
Масштабируемость алгоритма и его реализации
Масштабируемость алгоритма
Масштабируемость реализации алгоритма
Проведём исследование масштабируемости параллельной реализации алгоритма Тарьяна-Вишкина согласно методике. Исследование проводилось на суперкомпьютере "Ломоносов-2" Суперкомпьютерного комплекса Московского университета.
Набор и границы значений изменяемых параметров запуска реализации алгоритма:
- размер графа [2^18 : 2^26].
Проведем отдельные исследования масштабируемости вширь реализации алгоритма Тарьяна-Вишкина.
Основной характеристикой для сравнения было выбрано время выполнения, так как производительность (определения как TEPS то есть число ребер графа, которое алгоритм обрабатывает в секунду) для данной операции не отражает реальную эффективность обработки.
Анализируя время выполнения можно оценить, насколько понижается эффективность обработки графа при увеличении его размера (данные перестают помещаться в кэш, в память GPU, узла и т.д.).
