Purdom's, Boost Graph Library

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

1 Ссылки

Boost Graph Library (функция transitive_closure).

2 Локальность данных и вычислений

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

Для демонстрации эффективности представлены графики времени выполнения различных режимов вычислений в зависимости от размера входного графа.

Основной характеристикой для сравнения было выбрано время выполнения, так как производительность (определенная как TEPS, то есть число ребер графа, которое алгоритм обрабатывает в секунду) для данной операции не отражает реальной ситуации.

Дело в том, что сложность выбранного алгоритма Пурдома зависит от количества ребер в графе нелинейно и, кроме того, зависит еще и от структуры графа (количества сильно связанных компонент).

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

Анализируя время выполнения, можно оценить, насколько понижается эффективность обработки графа при увеличении его размера (данные перестают помещаться в кэш, в память GPU, узла и т.д.). На представленных графиках по оси X граф с каждым делением увеличивается в два раза, и по такому графику можно оценивать, насколько увеличилось время выполнения. Также время выполнения можно сравнивать для различных версий, например, последовательной CPU, параллельной CPU или же GPU. На приведенной диаграмме (рисунок 1) для различных размеров графа (от 2^20 до 2^26) представлено время выполнения трех различных версий: последовательной, параллельной CPU и GPU. Шкала на данной диаграмме логарифмическая.