Householder (reflections) method for reducing a symmetric matrix to tridiagonal form, SCALAPACK
Содержание
1 Ссылки
Для проведения экспериментов использовалась реализация метода Хаусхолдера, представленная в пакете SCALAPACK библиотеки Intel MKL (метод pdgehrd).
2 Локальность данных и вычислений
2.1 Локальность реализации алгоритма
2.1.1 Структура обращений в память и качественная оценка локальности
2.1.2 Количественная оценка локальности
3 Масштабируемость алгоритма и его реализации
3.1 Масштабируемость алгоритма
3.2 Масштабируемость реализации алгоритма
Проведём исследование масштабируемости вширь реализации согласно методике. Исследование проводилось на суперкомпьютере "Ломоносов-2" Суперкомпьютерного комплекса Московского университета.
Набор и границы значений изменяемых параметров запуска реализации алгоритма:
- число процессоров [16:81] с шагом n^2;
- размер матрицы [1000 : 16000] с шагом 1000.
В результате проведённых экспериментов был получен следующий диапазон эффективности реализации алгоритма:
- минимальная эффективность реализации 4.763e-05%;
- максимальная эффективность реализации 0.011%.
На следующих рисунках приведены графики производительности и эффективности выбранной реализации алгоритма в процедуре PDSYTRD из Scalapack в зависимости от изменяемых параметров запуска.
4 Динамические характеристики и эффективность реализации алгоритма
Все результаты получены на суперкомпьютере «Ломоносов-2». Использовались процессоры Intel Xeon E5-2697v3, сеть FDR Infiniband, а также компилятор Intel с опциями, рекомендованными Intel MKL Advisor. На рисунках показана эффективность реализации метода Хаусхолдера (отражений) для приведения симметричных матриц к трёхдиагональному виду для размерности матрицы 15000, запуск проводился на 81 ядре.
На графике загрузки процессора видно, что почти все время работы программы средний уровень загрузки составляет около 90%. Это хорошая картина для программ, запущенных c использованием технологии Hyper Threading, т.е. всех виртуальных ядер, доступных для данной архитектуры. К концу итерации виден более высокий уровень интенсивности вычислений в сравнении с началом и серединой вычислений.
На графике числа процессов, ожидающих вхождения в стадию счета (Loadavg), видно, что на протяжении всей работы программы значение этого параметра постоянно и приблизительно равняется 140 и только к концу итерации снижается до 80. Это свидетельствует о стабильной работе программы на протяжении всего выполнения со 140 нитями на одном узле или около 10 нитей на 1 физическое ядро на каждом узле. Это указывает на статичную загрузку аппаратных ресурсов процессами, однако их число для узла слишком велико, что может указывать на не очень рациональные опции компиляции, которые могут приводить к снижению производительности из-за накладных расходов на переключение контекста между нитями.
На графике кэш-промахов первого уровня видно, что число промахов достаточно низкое и находится на уровне 5 млн/сек в среднем по всем узлам. Интересен факт снижения числа промахов к концу итерации, хотя снижение и не очень значительное, но вполне заметное.
На графике кэш-промахов второго уровня видно, что число промахов тоже достаточно низкое и находится на уровне 1 млн/сек в среднем по всем узлам. На графике промахов второго уровня факт снижения числа промахов к концу итерации проявляется более явно и снижение более значительное и заметное (с 1.2 млн до 0.5 млн.).
На графике кэш-промахов последнего уровня видно, что число промахов достаточно небольшое и быстро убывает с уровня 90 тыс/сек до 0 в среднем по всем узлам. Это указывает на то, что задача достаточно хорошо укладывается в кэш-память третьего уровня, особенно к концу итерации.
На графике скорости передачи данных по сети Infiniband наблюдается достаточно низкая интенсивность использования коммуникационной сети на каждой итерации. Причем к концу каждой итерации интенсивность передачи данных сильно снижается. Это указывает на бОльшую необходимость в обмене данными между процессами в начале итерации и большую локальность вычислений к концу итерации.
На графике скорости передачи данных в пакетах в секунду наблюдается большая «кучность» показаний максимального минимального и среднего значений в сравнении с графиком скорости передачи в байт/сек. Это говорит о том, что, вероятно, процессы обмениваются сообщениями различной длины, что указывает на неравномерное распределение данных. Также наблюдается рост интенсивности использования сети к концу каждой итерации. Особенно это различие заметно к концу итерации.
В целом, по данным системного мониторинга работы программы можно сделать вывод о том, что программа работала стабильно и эффективно использовала память. Использование памяти и коммуникационной среды недостаточно интенсивное, что может указывать на снижение эффективности и увеличение производительности при существенном росте размера задачи. Для существующей в SCALAPACK параллельной реализации характерно сильное снижение числа кэш-промахов и обменов к концу итерации.
