Параллельный алгоритм многоуровневого метода вложенных сечений для вычислительных систем с общей памятью
Пирова А.Ю., Мееров И.Б., Козинов Е.А., Лебедев С.А.

Рассматривается задача переупорядочения строк и столбцов симметричной положительно определенной разреженной матрицы с целью уменьшения числа ненулевых элементов в факторе Холецкого. %количества вновь появляющихся ненулевых элементов в процессе разложения %(факторизации) этой матрицы методом Холецкого. Данная задача является NP-полной. Для ее решения используются эвристические алгоритмы, основанные на применении методов теории графов. Предлагается параллельный алгоритм переупорядочения для вычислительных систем с общей памятью. В качестве базы для распараллеливания используется модификация многоуровневого метода вложенных сечений, ранее реализованная авторами в виде библиотеки с открытым исходным кодом MORSy. Основная идея распараллеливания заключается в организации и параллельной обработке очереди задач, которые могут быть решены независимо. В отличие от широко распространенных аналогов, применяющих MPI для организации параллелизма как на распределенной, так и на общей памяти, предложенный алгоритм использует возможности стандарта OpenMP 3.0. Вычислительные эксперименты выполнены на симметричных положительно определенных матрицах из коллекции университета Флориды. Показано, что параллельный код MORSy дает сходные или лучшие перестановки в сравнении с библиотекой ParMETIS для всех тестовых матриц, кроме одной, в большинстве случаев опережая ParMETIS по времени работы. Программная реализация выполнена в виде библиотеки с открытым исходным кодом и доступна для скачивания на сайте Приволжского научно-образовательного центра суперкомпьютерных технологий.

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

Название статьи, аннотация и ключевые слова на английском языке

  • Пирова А.Ю. – Нижегородский государственный университет им. Н.И. Лобачевского (ННГУ), факультет вычислительной математики и кибернетики, просп. Гагарина, 23, 603950, г. Нижний Новгород; мл. науч. сотр., e-mail: anna.yu.malova@gmail.com
  • Мееров И.Б. – Нижегородский государственный университет им. Н.И. Лобачевского (ННГУ), факультет вычислительной математики и кибернетики, просп. Гагарина, 23, 603950, г. Нижний Новгород; зам. зав. кафедрой, e-mail: meerov@vmk.unn.ru
  • Козинов Е.А. – Нижегородский государственный университет им. Н.И. Лобачевского (ННГУ), факультет вычислительной математики и кибернетики, просп. Гагарина, 23, 603950, г. Нижний Новгород; ассистент, e-mail: evgeniy.kozinov@gmail.com
  • Лебедев С.А. – Нижегородский государственный университет им. Н.И. Лобачевского (ННГУ), факультет вычислительной математики и кибернетики, просп. Гагарина, 23, 603950, г. Нижний Новгород; программист, e-mail: sergey.a.lebedev@gmail.com