Lanczos, C++, MPI
Содержание
1 Ссылки
Для исследования масштабируемости рассматриваемого алгоритма Ланцоша без переортогонализации была реализована программа на языке С++ с использованием технологии MPI.
2 Локальность данных и вычислений
2.1 Локальность реализации алгоритма
2.1.1 Структура обращений в память и качественная оценка локальности
2.1.2 Количественная оценка локальности
3 Масштабируемость алгоритма и его реализации
3.1 Масштабируемость алгоритма
3.2 Масштабируемость реализации алгоритма
Дальнейшее исследование было проведено на суперкомпьютере "Ломоносов" Суперкомпьютерного комплекса МГУ[1].
Важно отметить, что реализованная программа выполняет только первую часть алгоритма - формирование трёхдиагональной матрицы T_j. Вторая часть алгоритма (задача поиска собственных значений матрицы T_j) может быть решена несколькими методами, каждый из которых обладает своей эффективностью распараллеливания и характерными свойствами. Подробно этот вопрос уже обсуждался в статье ранее, поэтому не будем ещё раз заострять на этом внимание и останавливаться.
Сборка осуществлялась со следующими параметрами:
- Компилятор intel/15.0.090
- Openmpi/1.8.4-icc
В серии проведённых расчётов рассматривались следующие числовые значения параметров:
- Размер n задачи и, соответственно, матрицы A, задействованной в операции умножения на вектор: [2000 : 30000] с шагом 1000
- Число p процессоров: 1, 2, 4, 16, 32, 48, 64, 96, 128, 192, 256
- Число итераций в алгоритме: k=350
Число k взято таким вопреки информации в начале статьи, где говорится, что значение k редко превышает 10^2 (хоть мы и имеем право брать его любым по нашему усмотрению). Это сделано исключительно для лучшей визуализации пиков на графиках в данном разделе и наглядности получаемых результатов, так как при меньших на порядок значениях параметра k времена выполнения программ были слишком малы даже при минимальных числах процессоров и максимальных размерах n задачи.
На рис. 1 изображён график зависимости времени выполнения программы от числа процессоров и размера n задачи.
Многочисленные тесты показали при малых количествах ядер уменьшение времени выполнения программы почти в 2 раза при увеличении числа ядер в 2 раза на всём диапазоне размеров матриц, что и отражает сильный излом на первом графике. Изменение значений времени можно легко оценить по предоставленной цветовой шкале. Был построен график эффективности распараллеливания (parallel efficiency) в зависимости от числа процессоров и размера задачи, изображённый на рис. 2. Получены следующие результаты численных экспериментов:
- Средняя эффективность распараллеливания программы составила: 42.5576% ;
- Минимальная эффективность реализации: 0.674% (число процессоров 256 и минимальный размер матрицы 2000);
- Максимальная эффективность реализации: 77.773% (число процессоров 2, размер матрицы 20000).
Нужно понимать, что это лишь экстремумы, соответствующие двум экспериментам, которые сами по себе не дают полной картины и не позволяют однозначно судить о параллельных качествах алгоритма и реализующей его программы при столь большом числе параметров и проводимых расчётов.
На основании рис. 2 можно отметить следующие значимые и важные факты:
- Имеется ярко выраженный спад эффективности при минимальном рассматриваемом размере матрицы n=2000 вдоль всей оси OY, отвечающей за число процессоров;
- Присутствуют два пика эффективности (жёлтого цвета на рис. 3): при числе p процессоров 2 и 128. Затем при дальнейшем увеличении числа процессоров с 128 до 256 наблюдается постепенное уменьшение эффективности реализации. Это связано с увеличением накладных расходов и затрат времени на обмены сообщениями между процессами.