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

Boruvka's, scalability

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


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

1 Ссылки

Для проведения экспериментов использовалась реализация алгоритма Борувки, реализованная для CPU.

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

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

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

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

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

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

Возможность обрабатывать фрагменты независимо означает хорошую масштабируемость алгоритма. Сдерживающими факторами являются

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

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

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

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

  • число процессоров [1 : 28] с шагом 1;
  • размер графа [2^20 : 2^27].

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

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

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

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

Все результаты получены на суперкомпьютере «Ломоносов-2». Использовались процессоры Intel Xeon E5-2697v3, задача решалась для графа большого размера на одном узле. На рисунках показана эффективность реализации алгоритма Борувки, запуск проводился на 1 узле для графа 2^27, выполнялась 1 итерация.

Рисунок 3. График загрузки CPU при выполнении алгоритма Борувки

На графике загрузки процессора видно, что почти все время работы программы не загружены и средний уровень загрузки составляет около 10%. Это нормальная картина для программ, запущенных c использованием одного ядра в реализации.

Рисунок 4. График числа процессов, ожидающих вхождения в стадию счета (Loadavg), при работе алгоритма Борувки

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

Рисунок 5. График кэш-промахов L1 в секунду при работе алгоритма Борувки

На графике кэш-промахов первого уровня видно, что число промахов очень высокое и находится на уровне 40 млн/сек . Интересен факт увеличения числа промахов к концу итерации до уровня в 70 млн/сек.

Рисунок 6. График кэш-промахов L1 в секунду при работе алгоритма Борувки

На графике кэш-промахов второго уровня видно, что число промахов тоже достаточно высокое и находится на уровне 30 млн/сек . На графике промахов второго уровня факт увеличения числа промахов к концу итерации проявляется более явно и увеличивается до значения в 50млн/сек.

Рисунок 7. График кэш-промахов L3 в секунду при работе алгоритма Борувки

На графике кэш-промахов последнего уровня видно, что число промахов тоже достаточно большое и составляет около 30 млн/сек по всем узлам. Это указывает на то, что задача очень плохо укладывается в кэш-память, и программа постоянно работает с оперативной памятью, что объясняется очень большим размером использованного графа.

Рисунок 8. График скорости передачи по сети Infiniband в байт/сек при работе алгоритма Борувки

На графике скорости передачи данных по сети Infiniband наблюдается достаточно высокая интенсивность использования сети на первом этапе. Это объясняется программной логикой, которая предполагает чтение графа из файла с диска, коммуникации с которым происходят на Ломоносов-2 через выделенную для этих задач сеть Infiniband.

Рисунок 9. График скорости передачи по сети Infiniband в пакетах/сек при работе алгоритма Борувки

На графике скорости передачи данных в пакетах в секунду наблюдается аналогичная картина очень высокой интенсивности на первом этапе выполнения задачи. Далее сеть почти не используется.

В целом, по данным системного мониторинга работы программы можно сделать вывод о том, что программа работала стабильно интенсивно, однако очень неэффективно использовала память из-за очень большого размера графа.

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