Backward substitution, scalability
Основные авторы описания: А.М.Теплов (раздел 3).
Содержание
1 Ссылки
2 Локальность данных и вычислений
2.1 Локальность реализации алгоритма
2.1.1 Структура обращений в память и качественная оценка локальности
2.1.2 Количественная оценка локальности
3 Масштабируемость алгоритма и его реализации
3.1 Масштабируемость алгоритма
3.2 Масштабируемость реализации алгоритма
Проведём исследование масштабируемости параллельной реализации алгоритма согласно методике. Исследование проводилось на суперкомпьютере "Ломоносов"[1] Суперкомпьютерного комплекса Московского университета. Набор и границы значений изменяемых параметров запуска реализации алгоритма:
- число процессоров [8, 16. 24, 32, 48, 64, 96, 128, 192, 256];
- размер матрицы [1024 : 4096] с шагом 1024.
В результате проведённых экспериментов был получен следующий диапазон эффективности реализации алгоритма:
- минимальная эффективность реализации 1.152e-15%;
- максимальная эффективность реализации 5.39e-10%.
На следующих рисунках приведены графики производительности и эффективности выбранной реализации алгоритма в зависимости от изменяемых параметров запуска.
По результатам проведенной серии экспериментов можно сделать вывод о том, что алгоритм резко снижает эффективность своей работы при выходе за пределы одного узла, т.е. когда обмен сообщениями начинает использовать коммуникационную сеть. Однако алгоритм достаточно быстро увеличивает производительность и эффективность при увеличении размера матрицы. Это указывает на то, что объем вычислений на один процесс является недостаточным для эффективного выполнения. Потому сильная масштабируемость будет очень ограничена.
4 Динамические характеристики и эффективность реализации алгоритма
Для проведения экспериментов использовалась реализация алгоритма обратной подстановки. Все результаты получены на суперкомпьютере "Ломоносов". Использовались процессоры Intel Xeon X5570 с пиковой производительностью в 94 Гфлопс, а также компилятор intel 13.1.0. На рисунках показана эффективность реализации алгоритма обратной подстановки на 32 процессах.
На графике загрузки процессора видно, что почти все время работы программы уровень загрузки составляет около 50%. Это указывает на равномерную загруженность вычислениями процессоров, при использовании 8 процессов на вычислительный узел и без использования Hyper Threading.
На Рисунке 4 показан график количества операций с плавающей точкой в секунду. На графике видна общая низкая производительность вычислений около 150 Мфлопс в пике и около 75 Мфлопс в среднем по всем узлам.
На графике кэш-промахов первого уровня видно, что число промахов не очень большое для нескольких ядер и находится на уровне 3,5 млн/сек в среднем (в пике до 8,5 млн/сек), что указывает на не очень интенсивные вычисления в большей части процессов. Это указывает на неравномерное распределение вычислений и не очень высокую производительность приложения.
На графике кэш-промахов третьего уровня видно, что число промахов очень немного и находится на уровне 1,2 млн/сек в среднем, однако в пике по всем узлам значения доходят до 3 млн/сек. Соотношение кэш промахов L1|L3 для процессов с доходит до 3, однако в среднем около 2,5. Это указывает на очень плохую локальность вычислений как у части процессов, так и для всех в среднем, и это является признаком низкой производительности.
На графике обращений в память видна достаточно типичная картина для таких приложений. Активность чтения достаточно низкая, что в совокупности с низкими значениями кэш-промахов L3 указывает на хорошую локальность. Хорошая локальность приложения так же указывает на то, что значения около 1 млн/сек для задачи является результатом высокой производительности вычислений, хотя и присутствует неравномерность между процессами.
На графике записей в память видна похожая картина неравномерности вычислений, при которой одновременно активно выполняют запись только несколько процессов. Это коррелирует с другими графиками выполнения. Стоит отметить, достаточно низкое число обращений на запись в память. В совокупности с другими индикаторами это скорее указывает на общую низкую производительность приложения.
На графике скорости передачи данных по сети Infiniband наблюдается очень низкая скорость передачи данных в байтах в секунду. Это говорит о том, что процессы между собой обмениваются неинтенсивно и вероятно достаточно малыми порциями данных, потому как производительность вычислений является низкой. Стоит отметить, что скорость передачи отличается между процессами, что указывает на дисбаланс вычислений.
На графике скорости передачи данных в пакетах в секунду наблюдается очень высокая интенсивность передачи данных выраженная в пакетах в секунду. Это говорит о том, что, вероятно, процессы обмениваются не очень существенными объемами данных, но очень интенсивно. Так же наблюдается почти меньший дизбаланс между процессами чем наблюдаемый в графиках использования памяти и вычислений и передачи данных в байтах/сек. Это указывает на то, что процессы обмениваются по алгоритму одинаковым числом пакетов, однако получают разные объемы данных и ведут неравномерные вычисления. Скорее всего активность Infiniband является одной из основных причин снижения производительности
На графике числа процессов, ожидающих вхождения в стадию счета (Loadavg), видно, что на протяжении всей работы программы значение этого параметра постоянно и приблизительно равняется 8. Это свидетельствует о стабильной работе программы с загруженными вычислениями всеми узлами. Это указывает на очень рациональную и статичную загрузку аппаратных ресурсов процессами. И показывает достаточно хорошую эффективность выполняемой реализации. В целом, по данным системного мониторинга работы программы можно сделать вывод о том, что программа работала неэффективно, но стабильно. Использование памяти не очень интенсивное, а использование коммуникационной среды крайне интенсивное, при этом объемы передаваемых данных очень низкие. Это указывает на требовательность к латентности коммуникационной среды алгоритмической части программы. Низкая эффективность связана судя по всему с достаточно высоким объемом пересылок на каждом процессе, интенсивными обменами сообщениями.
5 Результаты прогонов
- ↑ Воеводин Вл., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. Практика суперкомпьютера «Ломоносов» // Открытые системы, 2012, N 7, С. 36-39.
