Исследование масштабируемости итерационных алгоритмов при суперкомпьютерном моделировании физических процессов
Ежова Н.А., Соколинский Л.Б.

Статья посвящена разработке методики исследования масштабируемости ресурсоемких итерационных алгоритмов, применяемых в моделировании сложных физических процессов на суперкомпьютерных системах. В основе предлагаемой методики лежит модель параллельных вычислений BSF (Bulk Synchronous Farm), позволяющая на ранней стадии разработки итерационного алгоритма определить границу его масштабируемости. Модель BSF предполагает представление алгоритма в виде операций над списками с использованием функций высшего порядка. При этом рассматривается два класса представлений: BSF-M (Map BSF) и BSF-MR (Map-Reduce BSF). Предлагаемая методика описывается на примере решения систем линейных алгебраических уравнений методом Якоби. Для метода Якоби строится два итерационных алгоритма: Jacobi-M на основе представления BSF-M и Jacobi-MR на основе представления BSF-MR. Для указанных алгоритмов с помощью стоимостных метрик модели BSF даются аналитические оценки для ускорения, эффективности распараллеливания и верхней границы масштабируемости для многопроцессорных вычислительных систем с распределенной памятью. Приводится информация о реализации этих алгоритмов на языке C++ с использованием программного шаблона BSF и библиотеки параллельного программирования MPI. Демонстрируются результаты масштабных вычислительных экспериментов, выполненных на кластерной вычислительной системе. На основе экспериментальных результатов дается анализ адекватности оценок, полученных аналитическим путем с помощью стоимостных метрик модели BSF.

Ключевые слова: итерационный алгоритм, модель параллельных вычислений BSF, оценка масштабируемости, ускорение, эффективность распараллеливания, метод Якоби, кластерные вычислительные системы.

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

  • Ежова Н.А. – Южно-Уральский государственный университет, факультет вычислительной математики и информатики, просп. Ленина, 76, 454080, Челябинск; преподаватель, e-mail: EzhovaNA@susu.ru
  • Соколинский Л.Б. – Южно-Уральский государственный университет, факультет вычислительной математики и информатики, просп. Ленина, 76, 454080, Челябинск; проректор по информатизации, e-mail: Leonid.Sokolinsky@susu.ru