УДК 004

Оптимизация гнезд циклов на кластерной вычислительной системе с помощью блочных алгоритмов и MPI

Цинзерлинг Никита Алексеевич – студент кафедры Вычислительной техники МИРЭА – Российского технологического университета.

Научный руководитель Штрекер Евгений Николаевич – кандидат технических наук, доцент кафедры Вычислительной техники МИРЭА – Российского технологического университета.

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

Ключевые слова: кластер, оптимизация, гнездо циклов, MPI, блочные алгоритмы, С++.

В последний год наблюдается резкий скачек научных исследований в России. Например, в 2021 году в России зарегистрировано 18843 научных работ, а в 20222 году зарегистрировано 25735 работ. Для проведения современных научных исследований требуется огромное время уделять на математические сложные эксперименты и расчёты, которые проводятся на специальных кластерных научных компьютерах. При увеличении количества научных работ с расчетами возникает вопрос повышения быстродействия задач в прикладном программном обеспечении для сокращения времени работы кода в суперкомпьютере, что влечет за собой проблему оптимизации гнезд циклов.

Реализация

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

В программировании гнездо циклов представляет собой систему вложенных циклов, которая используется для выполнения повторяющихся действий в зависимости от определенных условий. Каждый цикл может содержать вложенный цикл, что дает возможность создавать сложные алгоритмы и обрабатывать большие объемы данных [1].

Однако при использовании гнезд циклов необходимо учитывать, что каждый вложенный цикл может замедлить выполнение алгоритма, поэтому не рекомендуется создавать слишком глубокие гнезда циклов. Кроме того, использование неправильных условий в качестве выходных значений вложенных циклов может привести к ошибкам, поэтому требуется тщательная проверка каждого цикла перед его запуском [2].

Важным аспектом эффективной параллельной обработки является умение анализировать зависимости данных и выбирать подходящий метод распараллеливания. Владение программистским мастерством и знание параллельных языков, таких как MPI или OpenMP, также важны в данном контексте [3]. Более сложные случаи распараллеливания могут потребовать ручного переноса программы, но это может быть сложно при обнаружении ошибок в параллельном коде [4].

Тайлинг – это метод, позволяющий преобразовать алгоритм таким образом, что из множества операций возможно получить макрооперации – тайлы, которые могут быть выполнены атомарно и использованы для параллельных вычислений [1,5]. Это уменьшает время обмена данными и требования к памяти. Тайлинг не связан с разбиением массивов данных, он используется для разбиения множества операций алгоритма. Каждый цикл разбивается на глобальный и локальный циклы, где локальный цикл выполняется в рамках одного тайла. Локальные циклы должны быть самыми внутренними, а общие для операторов локальные циклы распределяются между циклами операторов. Тайлинг является эффективным инструментом для оптимизации параллельных вычислений. Рассмотрим пространство итераций гнёзд цикла, где точки – итерации, а стрелочки – порядок выполняя. (Рисунок 1).

Рисунок 1. Пространство итераций.

При решении данной задачи при использовании библиотеки MPI, можно использовать блочные алгоритмы [5]. Оптимизация блочными алгоритмами позволяет ускорить время работы к следующим изменениям итерационного пространства. (Рисунок 2).

Рисунок 2. Методы оптимизации итерационного пространства.

Скос (слева сверху на рисунке 2) – позволяет сместить итерационное пространство, что не меняет порядок его выполнения и не меняет порядок итераций.

Смена итераций (справа сверху на рисунке 2) – с помощью перемещения местами заголовков цикла можно получить ускорение за счет оптимизации работы алгоритма.

Разбиение на блоки (снизу на рисунке 2) – позволяет локализовать данные при разбиении задач в узле.

Для оптимизации и получения максимального ускорения были объединены все методы и проведены расчеты на C++ с использованием библиотеки MPI на примере реализации метода Гаусса на кластерной вычислительной системе с размером матрицы 2000 на 2000. Результаты расчета при разном числе процессоров приведены на рисунке 3.

Рисунок 3. Результаты эксперимента при различном числе потоков.

С помощью объединения методов можно получить максимальное ускорение при решении систем линейных алгебраических уравнений, а результаты ускорения представлены на рисунке 4.

Рисунок 4. Результаты ускорения.

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

Список литературы

1. Катаев, Н. А. Дополнительное распараллеливание MPI программ с помощью системы SAPFOR / Н. А. Катаев, А. С. Колганов // Вычислительные методы и программирование. – 2021. – Т. 22, № 4. – С. 239-251.
2. Катаев Н. А., Колганов А. С. Автоматизированное распараллеливание программ для гетерогенных кластеров с помощью системы SAPFOR //Вычислительные методы и программирование. – 2022. – Т. 23. – №. 4. – С. 379-394.
3. Штейнберг, Б. Я. Преобразования программ – фундаментальная основа создания оптимизирующих распараллеливающих компиляторов / Б. Я. Штейнберг, О. Б. Штейнберг // Программные системы: теория и приложения. – 2021. – Т. 12, № 1(48). – С. 21-113. – DOI 10.25209/2079-3316-2021-12-1-21-113.
4. Гуда, С. А. Автоматическая расстановка синхронизаций при распараллеливании гнезд циклов на основе решетчатого графа / С. А. Гуда // Вестник Ростовского государственного университета путей сообщения. – 2019. – № 3(75). – С. 81-87.
5. Воеводин, В. В. Суперкомпьютеры и параллельная обработка данных: учеб. пособие для вузов / В. В. Воеводин. – М.: ВМК МГУ, 2019. – 161 с.