Уровень реализации

Tarjan-Vishkin biconnected components, scalability: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[досмотренная версия][досмотренная версия]
(Новая страница: «{{level-i}} Основные авторы описания: И.В.Афанасьев = Ссылки = = Локальность да...»)
 
 
Строка 34: Строка 34:
 
[[Категория:Статьи в работе]]
 
[[Категория:Статьи в работе]]
  
[[En:The computational core of the Graph500 benchmark on MPI]]
+
[[En:Tarjan-Vishkin biconnected components, scalability]]

Текущая версия на 15:43, 6 июля 2022


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

1 Ссылки

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

2.1 Локальность реализации алгоритма

2.1.1 Структура обращений в память и качественная оценка локальности

2.1.2 Количественная оценка локальности

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

3.1 Масштабируемость алгоритма

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

Проведём исследование масштабируемости параллельной реализации алгоритма Тарьяна-Вишкина согласно методике. Исследование проводилось на суперкомпьютере "Ломоносов-2" Суперкомпьютерного комплекса Московского университета.

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


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

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

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

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


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

4 Динамические характеристики и эффективность реализации алгоритма

5 Результаты прогонов