ASA: Новая страница: «{{level-i}} Основные авторы описания: А.М.Теплов (раздел #Масштабируемость ал...»

2022-07-18T07:07:45Z

Новая страница: «{{level-i}} Основные авторы описания: А.М.Теплов (раздел #Масштабируемость ал...»

Новая страница

{{level-i}}

Основные авторы описания: [[Участник:Teplov|А.М.Теплов]] (раздел [[#Масштабируемость алгоритма и его реализации|3]]).

= Ссылки =

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

Проведём исследование масштабируемости параллельной реализации алгоритма согласно [[Scalability methodology|методике]]. Исследование проводилось на суперкомпьютере "Ломоносов"<ref name="Lom">Воеводин Вл., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. Практика суперкомпьютера «Ломоносов» // Открытые системы, 2012, N 7, С. 36-39.</ref> [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета].
Набор и границы значений изменяемых [[Глоссарий#Параметры запуска|параметров запуска]] реализации алгоритма:

* число процессоров [8, 16. 24, 32, 48, 64, 96, 128, 192, 256];
* размер матрицы [1024 : 4096] с шагом 1024.

В результате проведённых экспериментов был получен следующий диапазон [[Глоссарий#Эффективность реализации|эффективности реализации]] алгоритма:

* минимальная эффективность реализации 1.152e-15%;
* максимальная эффективность реализации 5.39e-10%.

На следующих рисунках приведены графики [[Глоссарий#Производительность|производительности]] и эффективности выбранной реализации алгоритма в зависимости от изменяемых параметров запуска.

[[file:BS perf.png|thumb|center|700px|Рисунок 1. Параллельная реализация алгоритма. Изменение производительности в зависимости от числа процессоров и размера матрицы.]]
[[file:BS eff.png|thumb|center|700px|Рисунок 2. Параллельная реализация алгоритма. Изменение эффективности в зависимости от числа процессоров и размера матрицы.]]

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

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

Для проведения экспериментов использовалась реализация алгоритма обратной подстановки. Все результаты получены на суперкомпьютере "Ломоносов". Использовались процессоры Intel Xeon X5570 с пиковой производительностью в 94 Гфлопс, а также компилятор intel 13.1.0.
На рисунках показана эффективность реализации алгоритма обратной подстановки на 32 процессах.

[[file:BS CPU USER.png|thumb|center|700px|Рисунок 3. График загрузки CPU при выполнении алгоритма обратной подстановки]]

На графике загрузки процессора видно, что почти все время работы программы уровень загрузки составляет около 50%. Это указывает на равномерную загруженность вычислениями процессоров, при использовании 8 процессов на вычислительный узел и без использования Hyper Threading.

[[file:BS FLOPS.png|thumb|center|700px|Рисунок 4. График операций с плавающей точкой в секунду при выполнении алгоритма обратной подстановки]]

На Рисунке 4 показан график количества операций с плавающей точкой в секунду. На графике видна общая низкая производительность вычислений около 150 Мфлопс в пике и около 75 Мфлопс в среднем по всем узлам.

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

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

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

На графике кэш-промахов третьего уровня видно, что число промахов очень немного и находится на уровне 1,2 млн/сек в среднем, однако в пике по всем узлам значения доходят до 3 млн/сек. Соотношение кэш промахов L1|L3 для процессов с доходит до 3, однако в среднем около 2,5. Это указывает на очень плохую локальность вычислений как у части процессов, так и для всех в среднем, и это является признаком низкой производительности.

[[file:BS MEM LOAD.png|thumb|center|700px|Рисунок 7. График количества чтений из оперативной памяти при работе алгоритма обратной подстановки]]

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

[[file:BS MEM STORE.png|thumb|center|700px|Рисунок 8. График количества записей в оперативную память при работе алгоритма обратной подстановки]]

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

[[file:BS INF DATA.png|thumb|center|700px|Рисунок 9. График скорости передачи по сети Infiniband в байт/сек при работе алгоритма обратной подстановки]]

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

[[file:BS INF PCKTS.png|thumb|center|700px|Рисунок 10. График скорости передачи по сети Infiniband в пакетах/сек при работе алгоритма обратной подстановки]]

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

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

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

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

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

[[En:Backward substitution, scalability]]

Backward substitution, scalability - История изменений

ASA: Новая страница: «{{level-i}} Основные авторы описания: А.М.Теплов (раздел #Масштабируемость ал...»