Просмотр кода страницы Boruvka's, scalability

{{level-i}}

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

= Ссылки =

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

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

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

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

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

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

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

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

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

[[file:MST scaling strong.png|thumb|center|700px|Рисунок 1. Параллельная реализация алгоритма Борувки масштабируемость CPU версии: производительность в зависимости от числа запущенных CPU-потоков.]]

[[file:MST scaling wide.png|thumb|center|700px|Рисунок 2. Параллельная реализация алгоритма Борувки масштабируемость различных версий реализации алгоритма: производительность в зависимости от размера графа]]

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

Все результаты получены на суперкомпьютере «Ломоносов-2». Использовались процессоры Intel Xeon E5-2697v3, задача решалась для графа большого размера на одном узле. 
На рисунках показана эффективность реализации алгоритма Борувки, запуск проводился на 1 узле для графа 2^27, выполнялась 1 итерация.
[[file:Boruvka cpu.png|thumb|center|700px|Рисунок 3. График загрузки CPU при выполнении алгоритма Борувки]]

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

[[file:Boruvka Loadavg.png|thumb|center|700px|Рисунок 4. График числа процессов, ожидающих вхождения в стадию счета (Loadavg), при работе алгоритма Борувки]]

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

 [[file:Boruvka L1.png|thumb|center|700px|Рисунок 5. График кэш-промахов L1 в секунду при работе алгоритма Борувки]]
 
На графике кэш-промахов первого уровня видно, что число промахов очень высокое и находится на уровне 40 млн/сек . Интересен факт увеличения числа промахов к концу итерации до уровня в 70 млн/сек.

 [[file:Boruvka L2.png|thumb|center|700px|Рисунок 6. График кэш-промахов L1 в секунду при работе алгоритма Борувки]]
 
На графике кэш-промахов второго уровня видно, что число промахов тоже достаточно высокое и находится на уровне 30 млн/сек . На графике промахов второго уровня факт увеличения числа промахов к концу итерации проявляется более явно и увеличивается до значения в 50млн/сек.

 [[file:Boruvka L3.png|thumb|center|700px|Рисунок 7. График кэш-промахов L3 в секунду при работе алгоритма Борувки]]

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

[[file:Boruvka Inf data.png|thumb|center|700px|Рисунок 8. График скорости передачи по сети Infiniband в байт/сек при работе алгоритма Борувки]]

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

 [[file:Boruvka inf pckts.png|thumb|center|700px|Рисунок 9. График скорости передачи по сети Infiniband в пакетах/сек при работе алгоритма Борувки]]

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

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

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

[[En:Boruvka's, scalability]]