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

Модель параллельного программирования MPI (Message Passing Interface) основана на том, что взаимодействие между процессами происходит посредством передачи сообщений. Кратко стандарт MPI 1.2. можно охарактеризовать следующими возможностями:

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

– Возможность асинхронной передачи типа точка-точка, при которой посылающей сообщение процесс не ждет начала приема, что позволяет эффективно передавать короткие сообщения;

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

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

Технология параллельного программирования позволяет перемножать строки матрицы A и столбцы матрицы B одновременно. Для этого необходимо программно разделить строки между процессорами.

Разработка будет полезна в космической отрасли. При проектировании и испытании новых высокоскоростных летательных аппаратов, а также гиперзвуковых прямоточных воздушно-реактивных двигателей (ГПВРД) требуются математические исследования аэродинамических полей течений их геометрических моделей. Для решения подобных задач и будет создана разработка, которая является объектом моего исследования.

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

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

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

В схеме «Линейное соединение» каждый процессор взаимодействует с двумя соседними. Первый процессор взаимодействует только со вторым, а N-процессор только с N-1 процессором.

Рисунок 1. Линейное соединение

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

Рисунок 2. Кольцевое соединение

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

Рисунок 3. Звездообразное соединение

Кроме того также существуют организация работы процессоров по принципу сетки, «дерева» и «каждый-с-каждым». Такие способы используются реже. Они предназначены для сложных алгоритмов задач. Например, построение процессоров деревом упрощает решение задач, которые используют алгоритмы рекурсии для вычислений.

Для решения поставленной задачи распараллеливания матриц удобнее всего использовать звездообразное соединение. Оно удобно подстраивается под любое количество процессоров.

Перед нами стоит задача распараллелить процесс перемножения матриц. Пусть даны матрицы A и B размером 1000x1000 ячеек. Технология параллельного программирования позволяет перемножать строки матрицы A и столбцы матрицы B одновременно. Для этого необходимо программно разделить строки между процессорами.

Границы строк и столбцов в перемножаемых параллельно матрицах, которые обрабатывает процессор, будут определяться следующими правилами. Количество разбиений строк и столбцов зависит от количества процессоров, используемых в процессе перемножения. Если размер матрицы делится на количество процессоров без остатка, то в перемножении матриц используются формулы (1), (2).

 ,                                       (1)

                                           (2) 

Если размер матрицы не делится на количество процессоров без остатка, последние строки и столбцы обрабатываются по правилу, описанному в формулах (3), (4).

 ,                                (3)

                                        (4)

В приведенных формулах  – ряд, с которого начинается обработка;  – ряд, на котором заканчивается обработка;  – номер процессора, которые перемножает строки матрицы A и столбцы матрицы B;  – количество используемых процессоров.

Таблица 1.

Время расчета матрицы 1000*1000

Результаты таблицы наглядно представляют рисунки 11, 12 и 13. Время расчета уменьшается по экспоненциальному закону как показано на рисунке 11. Отношение времени выполнения на одном процессоре относительно n количества процессоров имеет линейную зависимость. Коэффициент увеличивается прямо пропорционально.

Рисунок 1. Время расчета в зависимости от количества процессоров

Рисунок 2. Отношение времени выполнения

Рисунок 3. Эффективность параллелизации

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

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

1. Антонов, А.С. Технологии параллельного программирования MPI и OpenMP: Учебное пособие / А.С. Антонов. - М.: МГУ, 2012. - 344 c.
2. Гергель, В.П. Современные языки и технологии паралелльного программирования: Учебник / В.П. Гергель. - М.: МГУ, 2012. - 408 c.
3. Лупин, С.А. Технологии параллельного программирования / С.А. Лупин, М.А. Посыпкин. - М.: ИД ФОРУМ, ИНФРА-М, 2013. - 208 c.