MPI параллельное умножение матриц

Исходник параллельной программы умножения матриц

Программы для параллельных вычислений по стандарту MPI позволяют значительно сократить время сложных математических операций путем разбиения большого объема вычислений между несколькими процессорами (ядер процессора).

На странице можно получить доступ к скачиванию файла исходного кода программы MPI умножения матриц для операционной системы Windows. Для практического тестирования к странице дополнительно прикреплена бесплатная скомпилированная тестовая программа. При запуске программы перемножаются большие матрицы: А размерностью 4000x1000 и В=1000х2000. Для проверки правильности работы кода при запуске программы с аргументом test, с визуализированным результатом, создаются и перемножаются небольшие матрицы: А размерностью 3х4 и В=4х5.

Для функционирования интерфейса Message Passing Interface на операционной системе Windows необходима установка программных пакетов MS-MPI, прочитать о настройке и установке MPI можно на странице данного сайта MPI на Windows, пример программы.

Примечание. Запуск параллельной программы на одноядерном процессоре малоэффективен и практически не ускоряет вычисления.

Результаты тестирования умножения матриц

На измерение скорости вычисления может влиять степень загруженности процессора сторонними задачами и функционированием программ операционной системы.

Скорость умножения матриц А=4000x1000 и В=1000х2000 на компьютере с процессором Intel(R) Core(TM) i5-9400 CPU @ 2.90GHz 6 ядер, 6 логических процессоров:
- единственным процессом – 10,9 секунд;
- разбиение задачи на 2-процесса снижает время вычислений до 6,1 секунды;
- разбиение задачи на 4-процесса снижает время вычислений до 3,52 секунды;
- разбиение задачи на 6-процессов снижает время вычислений до 2,52 секунды;
- разбиение задачи на 10-процессов снижает время вычислений до 2,68 секунды;
- разбиение задачи на 20-процессов снижает время вычислений до 2,49 секунды;
- разбиение задачи на 100-процессов снижает время вычислений до 2,5 секунды.
Из измерений видно, что наивысшая скорость вычислений начинается при задействовании всех 6-ядер процессора. В дальнейшем разбиение задачи на большее количество процессов, практически не дает прирост скорости умножения матриц.

Скорость умножения матриц А=4000x1000 и В=1000х2000 на компьютере с процессором Intel(R) Core(TM) i3-7100 CPU @ 3.90GHz 3.90 GHz 2 ядра, 4 логических процессора:
- единственным процессом – 13,19 секунд;
- разбиение задачи на 2-процесса снижает время вычислений до 11,58 секунды;
- разбиение задачи на 3-процесса снижает время вычислений до 10,2 секунды;
- разбиение задачи на 4-процессов время вычислений до 12,1 секунды;
- разбиение задачи на 6-процессов время вычислений до 11,9 секунды;
- разбиение задачи на 10-процессов снижает время вычислений до 11,9 секунды;
Безусловно, на скорость вычислений влияет общая производительность процессора машины. Максимальная скорость вычислений достигается с количеством процессов равным или близким к количеству участвующих процессоров(ядер) компьютерного устройства.

MPI и параллельные вычисления

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

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

Умножение больших матриц

Умножение матриц — одна из основных операций над матрицами, при которой из двух матриц получается третья матрица. Условие, при котором возможно умножение: количество столбцов первой матрицы должно равняться количеству строк второй.

Умножение больших матриц может быть сложным из-за большого количества операций, которые необходимо выполнить. Когда мы умножаем матрицы размерности M x N и N x P, нам необходимо выполнить M * N * P скалярных умножений и сложений. Если размеры матриц очень большие, это может занять значительное количество времени и ресурсов.

Матрица A = M(кол-во строк) x N(кол-во столбцов)
матрица B  = N(кол-во строк) x P(кол-во столбцов)
Условие для умножения:
Количество столбцов матрицы A  = количество строк матрицы B
*(величины M и P могут быть любыми)

Количество операций умножения:
q = M * N * P
Результат:
Матрица C = M(кол-во строк) x P(кол-во столбцов)

Даны:
Матрица A = 2 x 3
Матрица B = 3 x 4

Количество операций умножений и сложений:
q = 2 * 3 * 4 = 24
Результат:
Матрица C = 2 x 4

Даны большие матрицы:
Матрица A = 2000x3000
Матрица B = 3000x4000

Количество операций умножений и сложений:
q = 2000 * 3000 * 4000 = 24 000 000 000
Результат:
Матрица C = 2000 x 4000

К сведению. Без применения параллельных вычислений умножение матрицы A = 2000x3000 на матрицу B = 3000x4000 на компьютере с процессором Intel(R) Core(TM) i5-9400 CPU @ 2.90GHz 6-ядерном занимает время около 123 секунды.

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

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

Работа программы на MPI

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

Параллельные процессы запускаются, находясь в папке размещения файла программы, в окне командной строки командой:
mpiexec -n количество_процессов название_файла_программы
Например,
mpiexec -n 6 MPIMatricesMultiplication.exe

Проверить правильность умножения матриц можно командой с аргументом test:
mpiexec -n 3 MPIMatricesMultiplication.exe test
При таком запуске создаются небольшие матрицы, 3х4 и 4х5, перемножаются и результаты работы программы печатаются в окне командной строки. При каждом запуске тестового режима создаются новые матрицы со случайными числами.

Исходник параллельной программы на MPI

Исходный код программы умножения матриц написан на языке С++ в MS Visual Studio 2022, набор инструментов Visual Studio 2022 (v143), стандарт ISO C++ 14.

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

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

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

Скачать демо

💾MPIMatricesMultiplication-demo.zip

Скачать исходник