ИСПОЛЬЗОВАНИЕ ТЕХНОЛОГИИ MPI ПРИ РАСПАРАЛЛЕЛИВАНИИ ИНТЕРПОЛЯЦИИ МЕТОДОМ КУБИЧЕСКОГО СПЛАЙНА

USE OF MPI IN PARALLELIZATION OF CUBIC SPLINE INTERPOLATION METHOD

Yuri Chashin

candidate of Science., assistant professor of mathematical and software support of information systems,

Belgorod State National Research University

Russia, Belgorod

Vitaly Deev

student, Belgorod State National Research University,

Russia, Belgorod

АННОТАЦИЯ

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

ABSTRACT

The purpose of the article is to review the parallelization method cubic spline interpolation. The analysis used the input node values on the example of the sine function. During the review it was calculated key performance indicators of the parallel algorithm, compared with sequential algorithms.

Ключевые слова: MPI; параллельные вычисления; интерполяция.

Keywords: The MPI; parallel computing; interpolation.

Параллельные вычисления – одна из наиболее актуальных областей вычислительных наук в последнее десятилетие. Актуальность данной области связана прежде всего с бурным развитием численного моделирования. Численное моделирование является промежуточным элементом между аналитическими методами изучения и физическими экспериментами [1]. Рост количества задач, для решения которых необходимы параллельные вычисления обусловлен:

• Возможностью изучать явления, которые затруднительно, по некоторым причинам, изучить экспериментально.
• Необходимостью управления сложными промышленными и технологическими процессами в режиме реального времени. И в условиях неопределенности [2].
• Ростом числа задач, для решения которых необходимо обрабатывать гигантские объемы информации.

Помимо всего прочего процессоры приближаются к пределу тактовой частоты. Исторически сложилось, что выполняется закон Мура: каждые 18 месяцев производительность вычислительных систем увеличивается в 2 раза. До 21 века производительность процессов увеличивалась за счет повышения тактовой частоты. Главным тормозом здесь служило энергопотребление: при увеличении тактовой частоты на 20 %, энергопотребление возрастало на 73 % [3]. Поэтому было решено пойти другим путем. Производители процессоров стали уделять больше внимания реализации параллелизма, нежели тактовой частоте процессоров. Это достигается за счет реализации многоядерной архитектуры. Разместить на одном кристалле процессора несколько упрощенных процессоров, у которых тактовая частота была занижена, а функции АЛУ упрощены. Практически все современные устройства имеют многопроцессорную архитектуру (суперкомпьютеры, ПК, мобильные устройства).

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

Сплайны имеют многочисленные применения как в математической теории, так и в прикладной математике (в частности, в разнообразных вычислительных программах). В частности, сплайны двух переменных интенсивно используются для задания поверхностей в различных системах компьютерного моделирования. Сплайны двух аргументов называют би-сплайнами (например, бикубический сплайн), которые являются двумерными сплайнами, моделирующими поверхности. Их часто путают с B-сплайнами (базисными сплайнами), которые являются одномерными и в линейной комбинации составляют кривые — каркас для «натягивания» поверхностей. Также из базисных сплайнов возможно составить трёхмерную конструкцию для моделирования объёмных тел.

Алгоритм вычисления можно разделить на две части:

• Вычисление коэффициентов в узлах интерполяции.
• Вычисление значений сплайна в заданной точке.

Первый этап не является таким трудоемким, по сравнению со вторым,

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

Прежде всего пользователем производится ввод значений узлов входных данных. Затем, с помощью специальных директив MPI создается параллельная секция, которая будет выполняться на нескольких процессах, количество которых указывается пользователем при запуске приложения. После этого производится распределение данных между процессами. Пример распределения массива, состоящего из 100 элементов представлен на рисунке 1.

Рисунок 1. Пример распределения данных между процессами

После того, как произведено распределение данных, на каждом процессе начинается выполнение вычисления значений между входными узлами интерполяции. Для этого, на каждом из узлов производится вызов последовательной функции, реализующей метод кубических сплайнов. После выполнения вычислений каждым из процессов производится барьерная блокировка, чтобы все процессы окончили вычисление, а после этого производится сборка результатов вычислений со всех процессов в один массив на одном процессе при помощи функции MPI_Gatherv(). Пример работы данной функции проиллюстрирован на рисунке 2.

Рисунок 2. Схема работы MPI_Gatherv

После того, как все данные собраны на одном процессе выполнение алгоритма окончено.

Результаты выполнения программ на разных наборах данных приведены в таблице 1.

Таблица 1.

Результат выполнения на различных наборах данных

Ускорение при выполнении программы на 2 и 4 процессах по сравнению с последовательным выполнением представлено в таблице 2.

Таблица 2.

Коэффициенты ускорения программы

Соотношение эффективности выполнения программы на 2 и 4 процессах по сравнению с параллельным выполнением представлено в таблице 3.

Таблица 3.

Эффективность программы по сравнению с последовательным выполнением

Как видно из таблиц 2 и 3 с увеличением объема вычислений увеличивается ускорение вычислений, а также эффективность. Это обусловлено тем, что на создание процессов и обмен сообщениями между ними необходимы некоторые издержки. С увеличением объемов данных эти издержки становятся не такими существенными, как на небольших объемах.

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

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

1. Букатов А.А., Дацюк В.Н., Жегуло А.И. Программирование многопроцессорных вычислительных систем. – Ростов-на-Дону: ООО «ЦВВР», 2003. – 208 с. – ISBN 5-94153-062-5.
2. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. – М.: Мир, 1982. – 416 с.
3. Эра многоядерных энергоэффективных процессоров – [Электронный ресурс] – режим доступа – http://compress.ru/article.aspx?id=16962 (Дата обращения: 03.06.2016).