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

Floyd-Warshall, scalability

Материал из Алговики
Версия от 10:49, 5 июля 2022; ASA (обсуждение | вклад) (Новая страница: «{{level-i}} Основные авторы описания: Екатерина Шевченко = Ссылки = = Локальность данных и вы...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к навигации Перейти к поиску


Основные авторы описания: Екатерина Шевченко

1 Ссылки

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

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

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

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

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

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

Возможность обрабатывать фрагменты независимо означает хорошую масштабируемость алгоритма. Сдерживающие факторы:
1)Пропускная способность памяти при чтении данных графа.
2)Соперничество потоков при выполнении атомарных операций с памятью.
3)Синхронизация после каждого подшага алгоритма.

Алгоритм Флойда-Уоршелла обладает большим потенциалом масштабируемости, так как вычисление кратчайших путей можно распределить между независимыми процессами вплоть до вычисления каждым отдельным процессом одного элемента матрицы смежности.

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

Проведём исследование масштабируемости параллельной реализации алгоритма. Работа выполнена с использованием оборудования Центра коллективного пользования сверхвысокопроизводительными вычислительными ресурсами МГУ имени М.В. Ломоносова. Сильная масштабируемость показывает, как меняется время решения задачи с увеличением количества процессоров (или вычислительных узлов) при неизменном общем объёме задачи.

Сравнение времени параллельной работы алгоритма Флойда-Уоршелла в зависимости от количества процессоров.
Ускорение параллельного алгоритма Флойда-Уоршелла с ростом числа процессоров.

Как видно из представленных графиков параллельный алгоритм сильно масштабируем.

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

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