Householder (reflections) method for the QR decomposition, SCALAPACK
Содержание
1 Ссылки
Для проведения экспериментов использовалась реализация метода Хаусхолдера, представленная в пакете SCALAPACK библиотеки Intel MKL (метод pdgehrd).
2 Локальность данных и вычислений
2.1 Локальность реализации алгоритма
2.1.1 Структура обращений в память и качественная оценка локальности
2.1.2 Количественная оценка локальности
3 Масштабируемость алгоритма и его реализации
3.1 Масштабируемость алгоритма
3.2 Масштабируемость реализации алгоритма
Проведём исследование масштабируемости вширь реализации согласно методике. Исследование проводилось на суперкомпьютере "Ломоносов-2" Суперкомпьютерного комплекса Московского университета.
Набор и границы значений изменяемых параметров запуска реализации алгоритма:
- число процессоров [16:100] с шагом n^2;
- размер матрицы [1000 : 16000] с шагом 1000.
В результате проведённых экспериментов был получен следующий диапазон эффективности реализации алгоритма:
- минимальная эффективность реализации 0.00012%;
- максимальная эффективность реализации 0.0416%.
На следующих рисунках приведены графики производительности и эффективности выбранной реализации алгоритма в процедуре PDGEQRF из Scalapack в зависимости от изменяемых параметров запуска.
4 Динамические характеристики и эффективность реализации алгоритма
Все результаты получены на суперкомпьютере «Ломоносов-2». Использовались процессоры Intel Xeon E5-2697v3, сеть FDR Infiniband а также компилятор Intel с опциями, рекомнедованными Intel MKL Advisor. На рисунках показана эффективность реализации метода Хаусхолдера (отражений) QR-разложения квадратной матрицы для размерности матрицы 20000, запуск проводился на 100 ядрах, выполнялось 11 итераций.
На графике загрузки процессора видно, что почти все время работы программы средний уровень загрузки составляет около 85%. Это хорошая картина для программ, запущенных c использованием технологии Hyper Threading т.е. всех виртуальных ядер доступных для данной архитектуры. К концу итерации виден более высокий уровень интенсивности вычислений в срванении со началом и серединой вычислений.
На графике числа процессов, ожидающих вхождения в стадию счета (Loadavg), видно, что на протяжении всей работы программы значение этого параметра постоянно снижается со среднего значения 100 и к концу итерации снижается до 80. Это указывает на изменяющуюся загрузку аппаратных ресурсов процессами, однако их число для узла слишком велико, что с одной стороны может указывать на не очень рациональные опции компиляции, которые могут приводить к снижению производительности из-за накладных расходов на переключение контекста между нитями.
На графике кэш-промахов первого уровня видно, что число промахов достаточно низкое и находится на уровне 5 млн/сек в среднем по всем узлам. Интересен факт снижения числа промахов к концу каждой итерации, хотя снижение и не очень значительное, но вполне заметное.
На графике кэш-промахов второго уровня видно, что число промахов достаточно тоже низкое и находится на уровне 1 млн/сек в среднем по всем узлам. На графике промахов второго уровня факт снижения числа промахов к концу итерации проявляется более явно и снижение и более значительное и заметное (с 1.2 млн до 0.5 млн.).
На графике кэш-промахов последнего уровня видно, что число промахов достаточно небольшое и быстро убывает с уровня 75 тыс/сек до 20 тыс/сек в среднем по всем узлам. Это указывает на то, что задача достаточно хорошо укладывается в кэш-память третьего уровня, особенно к концу итерации.
На графике скорости передачи данных по сети Infiniband наблюдается достаточно низкая интенсивность использования коммуникационной сети на каждой итерации. Причем к концу каждой итерации интенсивность передачи данных сильно снижается. Это указывает на бОльшую необходимость в обмене данными между процессами в начале итерации и большую локальность вычислений к концу итерации. Наблюдается так же разбалансированность пересылок между максимальной и минимальной интенсивностью среди использованных узлов.
На графике скорости передачи данных в пакетах в секунду наблюдается большая «кучность» показаний максимального минимального и среднего значений в сравнении с графиком скорости передачи в байт/сек. Это говорит о том, что, вероятно, процессы обмениваются сообщениями различной длины, что указывает на неравномерное распределение данных. Также наблюдается рост интенсивности использования сети к концу каждой итерации. Особенно это различие заметно к концу итерации.
В целом, по данным системного мониторинга работы программы можно сделать вывод о том, что программа работала стабильно и эффективно использовала память. Использование памяти и коммуникационной среды не достаточно интенсивное, что может стать указывать на факторы снижения эффективности и увеличении производительности при существенном росте размера задачи. Для существующей в SCALAPACK параллельной реализаций характерно сильное снижение числа кэш-промахов и обменов к концу итерации
