Разработка масштабируемых методов и параллельных алгоритмов решения больших разреженных систем уравнений на многопроцессорных вычислительных системах применительно к задачам вычислительной гидрогазодинамикиНИР

Development of scalable parallel algorithms for solving large sparse systems of linear algebraic equations related with computational fluid dynamics applications

Источник финансирования НИР

грант Президента РФ

Этапы НИР

# Сроки Название
1 1 января 2016 г.-31 декабря 2016 г. Разработка масштабируемых методов и параллельных алгоритмов решения больших разреженных систем уравнений на многопроцессорных вычислительных системах применительно к задачам вычислительной гидрогазодинамики
Результаты этапа:
2 1 января 2017 г.-31 декабря 2017 г. Разработка масштабируемых методов и параллельных алгоритмов решения больших разреженных систем уравнений на многопроцессорных вычислительных системах применительно к задачам вычислительной гидрогазодинамики
Результаты этапа: Разработан алгоритм распараллеливания основных операций этапа решения систем уравнений с блочными матрицами. Разработан параллельный алгоритм расчета турбулентных течений вязкой несжимаемой жидкости, основанный на усреднении по ансамблям реализаций.
3 1 января 2018 г.-30 ноября 2018 г. Разработка масштабируемых методов и параллельных алгоритмов решения больших разреженных систем уравнений на многопроцессорных вычислительных системах применительно к задачам вычислительной гидрогазодинамики
Результаты этапа: В ходе завершающего этапа настоящего проекта выполнены работы по разработке алгоритмов распараллеливания этапа построения иерархии матриц многосеточного метода для решения систем линейных алгебраических уравнений (СЛАУ) с блочными матрицами. Для этих целей был выбран агрегативный вариант многосеточного метода построения иерархии матриц. Данный метод позволяет естественным образом использовать созданные ранее наработки при построении иерархии матриц для скалярных систем уравнений (системы уравнений, записанные для единичного дифференциального уравнения). Главным отличием по сравнению со скалярными системами уравнений является формирование матрицы СЛАУ на огрубленном уровне, когда при умножении матрицы текущего уровня на матрицу перехода между уровнями необходимо предусмотреть обобщение данной операции на случай когда элемент матрицы СЛАУ является подматрицей размера m x m, где m — число неизвестных, ассоциированных с каждой точкой расчетной сетки. Благодаря созданной на предыдущем этапе инфраструктуре для работы с блочными матрицами, представленными в формате BCSR, реализация данной опции не требует существенных изменений разработанных ранее алгоритмов распараллеливания. Здесь может быть переиспользован алгоритм распараллеливания умножения двух разреженных матриц, разработанный на первом этапе в 2016 году. Требуемые изменения касаются возможности умножения матриц, представленных в разных форматах, в частности CSR и BCSR. В случае когда локальный подблок блочной матрицы представляется в плотном виде, необходимые изменения сводятся к расширению маски для коммуникаций и замене операции умножения двух скаляров на операцию умножения подблока матрицы на число. За счет роста объема вычисления по сравнению с коммуникациями (количество пересылаемых сообщений остается неизменным, происходит лишь некоторое увеличение их размера), и, тем самым, улучшения перекрытия коммуникаций вычислениями, данная операция демонстрирует для блочных матриц несколько лучшие результаты сильной масштабируемости, позволяя расширить пределы сильной масштабируемости в 1.5-2 раза. Проведены оценки эффективности использования представления локальных подблоков матрицы в плотном виде и рассмотрена целесообразность их представления в одном из разреженных форматов. Данные оценки показали, что выбор оптимального варианта будет зависеть от нескольких факторов, в первую очередь от размера подблока (количество одновременно решаемых дифференциальных уравнений) и регулярности расположения ненулевых элементов в подблоках в диагональном и недиагональных элементах матрицы. Для подблоков малого размера целесообразно использовать плотное представление, тогда как при увеличении размера подблока выбор оптимального способа представления данных может варьироваться в зависимости от особенностей конкретной матрицы, и сделать априорный выбор представляется невозможным. Многосеточные методы решения СЛАУ широко применяются не только в качестве отдельных решателей, но и в качестве предобуславливателей для итерационных методов подпространства Крылова (например, метод сопряженных градиентов, CG, стабилизированный метод бисопряженных градиентов, BiCGStab, обобщенный метод минимальных невязок, GMRES, и другие). Помимо оригинальных формулировок данных методов, в литературе имеется ряд публикаций, связанных с переформулированием данных методов с целью сокращения временных затрат на локальные (в ходе умножения матрицы на вектор) и глобальные (операции редукции при расчете скалярных произведений векторов) коммуникации. К числу модифицированных стабилизированных методов бисопряженных градиентов можно отнести Reordered BiCGStab, Improved BiCGStab, Pipelined BiCGStab и ряд других, где потенциальный выигрыш во времени выполнения коммуникаций сочетается с дополнительными накладными операциями с векторами. При этом, имеющееся обилие методов не дает ответа на вопрос об области применимости каждого из них. Для систематизации и оценки области применимости указанных методов предложена аналитическая модель, позволяющая предсказать время расчета одной итерации метода в зависимости от размера СЛАУ, количества используемых вычислительных узлов, пропускной способности шины памяти вычислительной системы и времени исполнения операций типа Allreduce. Отличительной особенностью данной модели является использование в качестве базового показателя объема пересылаемых по шине памяти данных, а не количества операций с плавающей точкой. В ходе апробации модели показано, что характеристики, основанные на объеме пересылаемых данных, точнее описывают производительность алгоритмов, относящихся к классу «memory bound». Для указанных алгоритмов предложены дополнительные модификации, направленные на группирование векторных операций. Это позволяет переиспользовать уже загруженные из памяти данные для одновременного выполнения нескольких операций с векторами, и тем самым несколько сократить время выполнения данных алгоритмов. Причем, если для оригинального метода BiCGStab рассмотренная процедура слияния векторных операций обеспечивает выигрыш порядка 15%, то для модифицированных методов данная процедура позволяет сократить объем загружаемых данных в процессе выполнения операций с векторами почти вдвое. С помощью предложенной модели проведена оценка области применимости указанных алгоритмов. Показано, что для диапазона размеров задач в пересчете на один вычислительный узел, превышающих 200 тыс. неизвестных, вплоть до масштабов нескольких сотен узлов целесообразно использовать оригинальный метод BiCGStab. Reordered BiCGStab оказывается предпочтительным на масштабах 50-100 тыс. элементов на вычислительный узел, тогда как в пределе сверхвысокой масштабируемости с вычислительной нагрузкой на узел не более нескольких десятков тысяч элементов преимущественным оказывается использование метода Pipelined BiCGStab. При этом, следует заметить, что на практике на таких масштабах задач существенно возрастает вклад локальных коммуникаций при умножении матрицы на вектор, что может привести к общей деградации производительности и фактическому замедлению расчета. В настоящее время проводится работа по обобщению оценок и результатов на случай расчетов со многими правыми частями; материалы готовятся к публикации.

Прикрепленные к НИР результаты

Для прикрепления результата сначала выберете тип результата (статьи, книги, ...). После чего введите несколько символов в поле поиска прикрепляемого результата, затем выберете один из предложенных и нажмите кнопку "Добавить".