Просмотр кода страницы Tarjan-Vishkin biconnected components, scalability

{{level-i}}

Основные авторы описания: [[Участник:Elijah|И.В.Афанасьев]]

= Ссылки =

= Локальность данных и вычислений =
== Локальность реализации алгоритма ==
=== Структура обращений в память и качественная оценка локальности ===
=== Количественная оценка локальности ===
= Масштабируемость алгоритма и его реализации =
== Масштабируемость алгоритма ==
== Масштабируемость реализации алгоритма ==

Проведём исследование масштабируемости параллельной реализации алгоритма Тарьяна-Вишкина согласно [[Scalability methodology|методике]]. Исследование проводилось на суперкомпьютере "Ломоносов-2" [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета].

Набор и границы значений изменяемых [[Глоссарий#Параметры запуска|параметров запуска]] реализации алгоритма: 


*	размер графа [2^18 : 2^26].

Проведем отдельные исследования масштабируемости вширь реализации алгоритма Тарьяна-Вишкина.

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

Анализируя время выполнения можно оценить, насколько понижается эффективность обработки графа при увеличении его размера (данные перестают помещаться в кэш, в память GPU, узла и т.д.). 


[[file:Tarjan vishkin scaling wide.png|thumb|center|700px|Рисунок 1. Параллельная реализация алгоритма Тарьяна-Вишкина масштабируемость вширь: производительность в зависимости от размера графа]]

= Динамические характеристики и эффективность реализации алгоритма =
= Результаты прогонов =

[[Категория:Статьи в работе]]

[[En:Tarjan-Vishkin biconnected components, scalability]]