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