Распараллеливание метода сопряженных градиентов с эффективным ILU-предобуславливателем

О.А. Бессонов (ИПМех РАН)

Данная работа посвящена исследованию эффективных предобуславливателей для решения эллиптических уравнений методом сопряженных градиентов на регулярных сетках, а также разработке и реализации параллельного предобуславливателя "неявной" природы на основе идеи неполного разложения матрицы в варианте "Modified Incomplete LU-decomposition" (M-ILU). В работе анализируется принцип неполного разложения для конструирования предобуславливателей метода сопряженных градиентов и проводится сравнение вычислительных затрат и скорости сходимости для разных вариантов. Далее рассматривается возможность эффективного распараллеливания неполного разложения с учетом неявности (рекурсивности) его алгоритма.

В качестве метода распараллеливания используется обобщение метода встречной прогонки с проведением исключения внедиагональных членов матрицы одновременно в трех пространственных направлениях, что позволяет произвести разбиение трехмерной прямоугольной расчетной области на 8 октантов с независимой обработкой в разных процессорах. Дополнительное увеличение потенциала распараллеливания до 16 процессоров обеспечивается использованием конвейерного метода. В работе рассматриваются особенности реализации алгоритма, а также приводятся и обсуждаются разультаты распараллеливания.

Программа решателя реализована в модели распараллеливания OpenMP для вычислительных систем с общей памятью с организацией NuMA и может использоваться на будущих машинах, построенных на новых многоядерных процессорах Intel Xeon Core-i7 и AMD Opteron K10. Описанный метод распараллеливания может быть реализован в модели MPI и гибридной модели MPI/OpenMP для систем с распределенной памятью (кластеров).

Настоящая работа проводится в рамках Европейского интегрированного проекта по изучению лесных пожаров "FireParadox".