Supercomputer Software Department

Проект РФФИ 14-07-00381 "Локальные системные алгоритмы для параллельной реализации больших численных моделей на пета- и экза-флопсных мультикомпьютерах"

Разрабатываются и изучаются локальные алгоритмы организации параллельных вычислений, реализующих большие численные модели, на пета- и экза-флопсных мультикомпьютерах. Предлагаются необходимые проектные решения для разработки и реализации языка и системы конструирования таких прикладных параллельных программ, формулируются и анализируются возникающие проблемы разработки различных компонентов такой системы и предлагаются решения.

Алгоритмы предполагается использовать при разработке системы фрагментированного программирования LuNA. Проект LuNA направлен на создание системы автоматической генерации параллельных программ численного моделирования и имеет целью исключить полностью параллельное программирование из процесса разработки крупномасштабных численных моделей. Основная проблема, возникшая в этом проекте, - непригодность базовых системных алгоритмов конструирования программ в случае, когда предполагается использовать вычислители с большим числом вычислительных узлов (В.Э.Малышкин. ПРОБЛЕМЫ ПАРАЛЛЕЛЬНОЙ РЕАЛИЗАЦИИ КРУПНОМАСШТАБНЫХ ЧИСЛЕННЫХ МОДЕЛЕЙ НА ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ ЭКЗАФЛОПСНОЙ ПРОИЗВОДИТЕЛЬНОСТИ // ж. Проблемы информатики, 2015, Новосибирск, стр. 71-82.) для исполнения программ моделирования.

В 2014 г. проведен анализ методов реализации крупномасштабных численных моделей с большим объемом используемых при моделировании данных. Сформулированы проблемы параллельной реализации таких моделей. Предложены подходы к автоматизации создания параллельных программ численного моделирования и даже полного исключения параллельного программирования из процесса создания модели. Разработаны распределенные алгоритмы балансировки, распределения ресурсов и управления на основе моделирования природных явлений.

В 2015 г. цели проекта на 2015 год определяются потребностями разработки проекта системы фрагментированного программирования LuNA в новых распределенных системных алгоритмах с локальными взаимодействиями (РСАЛВ). Проект направлен на исключение параллельного программирования из процесса создания крупномасштабных численных моделей. Основная задача - разработать экспериментальный технологический РСАЛВ для распределенного динамического распределения ресурсов мультикомпьютера в ходе крупномасштабного моделирования на экзафлопсных мультикомпьютерах.

В 2015 г. разработан технологический распределенный системный алгоритм с локальными взаимодействиями для распределенного динамического распределения ресурсов мультикомпьютера в ходе крупномасштабного численного моделирования на экзафлопсных мультикомпьютерах (алгоритм «веревочка», Rope-of-Beads (RoB)). Выполнена и протестирована реализация алгоритма. Назначение алгоритма в его текущем варианте – использование в системах конструирования параллельных программ для мультикомпьютеров для решения проблемы статического и динамического распределения распределенной памяти. Отсутствие таких технологических алгоритмов хорошего качества является одной из основных причин того, что для распределенного программирования и поныне в основном используется MPI, что по своим возможностям примерно соответствует уровню программирования в ассемблере в последовательном программировании. Системным алгоритмам попросту не хватает интеллекта для решения с приемлемым качеством ряда сложных задач конструирования программ.

Основная идея построения алгоритма - моделировании в нем распределенных во времени и пространстве природных процессов типа диффузии, гравитации и/или растекания жидкости в системе сообщающихся сосудов, в которые вносятся технологические модификации для получения приемлемого по качеству конечного результата. Если прямо моделировать в алгоритме распределения любое из перечисленных явлений, то результат будет неприемлемым в первую очередь по времени поиска нужного распределения. Скажем, алгоритм на базе диффузии будет медленно распространять возмущения по всему пространству процессорного поля.

Поэтому используется идея кривой (кривая Гильберта), проходящей через каждую точку пространства, в данном случае – через каждый узел мультикомпьютера, с нанизанными на неё процессами. Миграции процессов соответствует передвижение процессов по веревочке с соответствующим изменением назначения ресурсов процессу и сохранением отношения соседства (Victor Malyshkin, Vladislav Perepelkin, and Georgy Schukin. Distributed Algorithm of Data Allocation in the Fragmented Programming System LuNA // Springer, LNCS, Vol. 9251, pp. 80-85. DOI: 10.1007/978-3-319-21909-7_8).

Алгоритм работает в каждом узле мультикомпьютера, асинхронно, с использованием только своих данных и данных из узлов 1-окрестности текущего узла. Выравнивание нагрузки с непременным сохранением отношения соседства на множестве процессов происходит параллельно и распределенно.

Сравнение качества распределения (времени работы решателя уравнения Пуассона) алгоритмов на основе Hash-функции и веревочки приведены ниже.

Видно, что верёвочка существенно превосходит алгоритм на базе Hash-функции, что говорит о лучшем сохранении отношения соседства (входные переменные процессов прикладной программы находятся ближе к узлу, где процессы исполняются) и о более равномерной загрузке узлов мультикомпьютера.

Демонстрация работы алгоритма RoB для метода частиц в ячейках (PIC) приведена на следующем рисунке (разные ПЭ обозначены разными цветами).

В 2016 г. на основе алгоритма RoB разработана новая версия алгоритма для двумерных топологий структур данных и вычислительных сетей (алгоритм "платочек", Patch-of-Cells (PoC)). Демонстрация работы алгоритма PoC представлена на рисунке ниже (разные ПЭ обозначены разными цветами).