[ О реализации численных методов
решения СЛАУ на основе гибридных
моделей программирования
Б.И. Краснопольский
к.ф.-м.н.
Старший научный сотрудник
Лаборатория общей аэродинамики
НИИ механики МГУ
Семинар «Суперкомпьютерные технологии в науке, образовании и промышленности»
МГУ им. М.В. Ломоносова, 15 мая 2012 г.
План доклада Два направления:
Библиотека численных методов решения разреженных систем линейных алгебраических уравнений Приложение для прямого численного моделирования турбулентных течений в областях сложной формы 2/ 1. Библиотека численных методов решения разреженных систем линейных алгебраических уравнений 1. Предназначение Подавляющее большинство задач механики сплошных сред в том или ином виде сводится к решению систем линейных алгебраических уравнений Одни из наиболее “тяжелых” - системы уравнений, полученные в результате разностной аппроксимации эллиптических уравнений в частных производных Эллиптические уравнения встречаются во многих областях физики:
Гидродинамика (расчет полей давления) Электричество и магнетизм (распределения потенциалов) Задачи напряженно-деформированного состояния материалов (прогиб мембран и оболочек) Время решения такой СЛАУ зачастую составляет более 90% по сравнению с остальными вычислениями при расчете нового шага по времени 4/ 1. Текущее состояние вопроса...
Наиболее популярные библиотеки:
Trilinos Aztec/AztecOO CG, CGS, BiCGStab, GMRES и пр.
ILU-предобуславливатели ML (> 3К procs) AMG/SAMG Hypre CG, CGS, BiCGStab, GMRES и пр.
BoomerAMG (~ 200К cores) AMG *LparSol (~ 10K cores) CG, CGS, BiCGStab, GMRES и пр.
ILU-предобуславливатели AMG 5/ 1. Hypre: On the Road to Exascale Позиционируется как один из инструментов для создания больших пользовательских вычислительных приложений в Exascale-перспективе * A.H. Baker, R.D. Falgout, T. Gamblin, Tz.V. Kolev, M. Schulz, and U.M. Yang. Scaling Algebraic Multigrid Solvers: On the Road to Exascale. Proceedings of Competence in High Performance Computing, CiHPC 2010. 6/ 1. Hypre: MPI+OpenMP «Почти» open-source Масштабируемость внутри одного узла Произведение разреженной матрицы на вектор:
Использование OpenMP модели приводит к ускорению в 2-2.5 раза!
MCSup: Multi-Core Support library, API для управления выделением памяти между процессорами и привязки процессов MCSup не распространяется с hypre!
* 4 x Quad-core AMD Opteron processors (4 NUMA nodes) * A.H. Baker, R.D. Falgout, T. Gamblin, Tz.V. Kolev, M. Schulz, and U.M. Yang. Scaling Algebraic Multigrid Solvers: On the Road to Exascale. Proceedings of Competence in High Performance Масштабируемость внутри одного узла 2 х 12-core AMD Opteron 2 х 6-core Intel Nehalem 1. NUMA архитектура Non-Uniform Memory Access
NUMA NUMA
NUMA NUMA
Можно ли добиться повышения эффективности методов решения больших сильно-разреженных систем линейных алгебраических уравнений (итерационные методы подпространства Крылова, многосеточные методы) по сравнению с hypre?..Возможные пути повышения эффективности методов:
Модификация численных методов Использование других гибридных моделей программирования Многомерное разбиение матриц Балансировка вычислений на всех уровнях вложенности Уменьшение количества процессов на нижних уровнях вложенности 1. Модификация численных методов Reordered BiCGStab Типы вычислительных операции метода:
MPI_IAllreduce — неблокирующий аналог глобальной редукции * B. Krasnopolsky. The Reodered BiCGStab Method For Distributed Memory Computer Systems // Procedia Computer Science, 2010, v. 1, pp. 213-218. 12/ По аналогии с Mvapich:
Редукция между процессами внутри узла: через общую память Редукция между узлами: коммуникации «точка-точка» по биномиальному дереву Прототипы функций (в стадии реализации):
MPIShM_IAllreduce_init ( … ) Инициализация MPIShM_IAllreduce_shm_op ( … ) Локальная редукция MPIShM_IAllreduce_shm_finalize ( … ) Завершение локальной редукции, MPIShM_IAllreduce_process ( … ) Обработка завершившихся обменов MPIShM_IAllreduce_finalize ( … ) Завершение операции 1. Гибридная модель MPI+ShM MPI + Posix Shared Memory Более низкоуровневая модель по сравнению с MPI+OpenMP Простой и прозрачный способ распределения и привязки процессов между ядрами внутри узла 1. Гибридная модель MPI+ShM MPI + Posix Shared Memory Более низкоуровневая модель по сравнению с MPI+OpenMP Простой и прозрачный способ распределения и привязки процессов между ядрами внутри узла Запуск обычной MPI программы 1. Гибридная модель MPI+ShM MPI + Posix Shared Memory Более низкоуровневая модель по сравнению с MPI+OpenMP Простой и прозрачный способ распределения и привязки процессов между ядрами внутри узла Запуск обычной MPI программы «Объединение» памяти между подмножеством MPI-процессов 1. Гибридная модель MPI+ShM Умножение матрицы на вектор Простейший вариант умножения матрицы на вектор: y = A x Вектор x расположен в общей памяти;
Вектор x целиком доступен всем процессам, но принадлежит одному процессу (выделен в одном NUMA-узле) * Априори неэффективно для NUMA архитектуры, но дает оценку нижнего предела эффективности гибридной модели 1. Гибридная модель MPI+ShM BiCGStab, результаты, Зилант Размер матрицы 3.3М неизвестных, до 7 ненулевых элементов в каждой строке 1. Многомерное разбиение матриц «Стандартный» подход: построчное разбиение матрицы между вычислительными процессами Альтернативы:
Одномерное разбиение по столбцам Двумерное разбиение матрицы?..
Алгоритмы поиска оптимального разбиения графов и гиперграфов:
ParMetis PT-Scotch Zoltan Задача Неймана для уравнения Пуассона в кубической области на равномерной сетке (7-точечный шаблон пространственной аппроксимации) Фиксированное количество итераций метода (BiCGStab+AMG) Ускорение определено как:
1.*Результаты масштабируемости 1.*Результаты масштабируемости Ломоносов, MPI+ShM 1.*Результаты масштабируемости Пиковые ускорения для различных тестовых матриц:
Размер матрицы, Оптимальное млн. строк количество узлов 1.*Внутриузловая масштабируемость 156 сек.
1.*Внутриузловая масштабируемость Вычислительная система Используются все имеющиеся ядра на узле Размер блока – количество “агрегированных” MPI-процессов Можно ли добиться повышения эффективности методов решения больших сильно-разреженных систем линейных алгебраических уравнений (итерационные методы подпространства Крылова, многосеточные методы) по сравнению с hypre?..
2. Приложение для прямого численного моделирования турбулентных течений в областях 2. «Простые» и «сложные» области “Простые” области – задачи, где для “Сложные” области – задачи, где для решения уравнения Пуассона для решения уравнения Пуассона для давления возможно применение прямых давления необходимо использование Рассматривается течение вязкой несжимаемой жидкости Уравнение неразрывности:
Уравнения Навье-Стокса:
Число Рейнольдса:
Граничные условия:
распределение скоростей по границе, прилипание, проскальзывание, периодичность, распределение давления по границе, «сопряженные» расчеты* Расчет шага по времени:
1. Расчет предварительного поля скоростей в центрах ячеек:
схема Адамса-Башфорта:
2. Расчет предварительных скоростей на гранях ячеек 3. Формулировка уравнения для давления относительно скоростей на гранях ячеек, расчет скоростей на гранях ячеек 4. Расчет поля скоростей в центрах ячеек * Mahesh K., Constantinescu G., Moin P. A numerical method for large-eddy simulation in complex geometries // Journal of computational physics. 2004. V. 197. Pp. 215-240.
Аппроксимация нелинейных членов Аппроксимация градиента давления на гранях ячеек Аппроксимация градиента давления в центрах ячеек * Mahesh K., Constantinescu G., Moin P. A numerical method for large-eddy simulation in complex geometries // Journal of computational physics. 2004. V. 197. Pp. 215-240.
Неструктурированные сетки: ячейка описывается только номерами восьми образующих вершин.
Вся информация о сетке хранится в двух списках:
1. Список вершин, содержит номер и координаты вершины 2. Список ячеек, содержит номер ячейки и номера восьми образующих ячейку вершин При построении аппроксимации уравнений используется еще один вспомогательный список:
3. Список граней, содержит номер грани и номера образующих эту грань ячеек Такая схема представления расчетных сеток обеспечивает минимальное дублирование данных между вычислительными процессами и хорошую масштабируемость приложения по памяти.
Интерфейс с существующими специализироICEM CFD cgnslib ванными пакетами для пре/пост-процессинга Входные данные: CGNS формат Информация о расчетной сетке и граничных условиях Файл может быть создан как из коммерческих сеточных генераторов, так и с помощью специализированной openApplication source библиотеки Выходные данные: SILO формат Обеспечивает простой импорт данных в Ориентирован на обработку больших объемов данных вычислительных процессов могут быть Осредненный профиль продольной Распределение среднеквадратичных В сравнении с: Kim J., Moin P., Mozer R. Turbulence statistics in fully developed channel flow at low Reynolds number // Journal of Fluid Mechanics, 1987, V. 177, P. 133-166.
Первичные результаты масштабируемости получены для трех тестовых задач обтекания трехмерной прямоугольной каверны 2. Результаты масштабируемости Размер задачи, М Время расчета на 8 узлах, сек Минимальное время, сек * Создан прототип приложения для расчета турбулентных течений в областях сложной формы. Заложенные в основу методы и алгоритмы обеспечивают хорошие характеристики ускорения времени расчета задачи и масштабируемости по памяти.
* Получены первичные данные верификации алгоритма, удовлетворительной точности результатов расчетов.
* Создание интерфейса для проведения «сопряженных»
расчетов обеспечит возможность расчета широкого круга задач для верификации приложения.
Спасибо за внимание!
Н.В. Никитину за ценные замечания и конструктивную критику результатов работ Вл.В. Воеводину и С.А. Жуматию за предоставленный доступ к вычислительным ресурсам Суперкомпьютерного комплекса Московского университета и помощь в решении технических вопросов Компании «Т-Сервисы» за предоставленную возможность проведения ряда расчетов на вычислительной системе «Зилант»
«