Введение. Зачем все это?

В этом цикле статей речь пойдет о параллельном программировании.

• Часть 1. MPI - Введение и первая программа.

• Часть 2. MPI - Учимся следить за процессами.

• Часть 3. MPI - Как процессы общаются? Сообщения типа точка-точка.

В бой. Введение

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

В основном используют 2 типа оптимизации, либо их смесь: векторизация и распараллеливание
вычислений. Чем же они отличаются?

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

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

Так а чем отличаются векторизация и параллельные вычисления? Векторизация - позволяет выполнять операции над данными целыми векторами. Например для С++: если мы используем AVX инструкции, то у нас есть вектора размером 256 бит, куда мы можем поместить float32 элементы. Получится, что мы можем собрать 2 вектора по (256 / 32) = 8 float32 значений. После чего выполнить над ними одну операцию за такт, хотя если бы мы этого не сделали, то вполне возможно, что аналогичные вычисления прошли бы за 8 операций, а то и больше если брать в учет вычисления индексов конкретных элементов. Однако есть одна проблема: компиляторы нынче довольно умны и довольно хорошо справляются с подобной оптимизацией и сами, поэтому большая часть сил уходит на то чтобы правильно организовать данные.

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

Основная часть

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

Существует два основных стиля создания параллельных программ: MIMD(Multiple Instruction Multiple Data - Множественный поток Инструкций, Множественный поток Данных) и SPMD(Single Program Multiple Data - Одна Программа, Множественный поток Данных).

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

Установка

Поскольку MPI - библиотека, то необходимо ее прилинковать к компилятору. В каждой среде это делается по своему и в зависимости от компилятора. Лично я работал на Ubuntu Budgie 20.04 LTS и расскажу инструкцию по установке именно для нее.

В командной строке вводим следующие команды:

[user-name]$ sudo apt-get update
[user-name]$ sudo apt-get install gcc
[user-name]$ sudo apt-get install mpich

Первая команда обновляет менеджер пакетов, вторая устанавливает компилятор GCC, если его нет в системе, третья программа устанавливает компилятор через который мы собственно и будем работать с C\С++&MPI кодом.

Первые шаги.

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

Для понимания того что происходит дальше нужно определиться с несколькими терминами:

Коммуникатор - объект через который общается определенная группа порожденных процессов. В С++/С это тип данных MPI_Comm. Коммуникатор может объединять несколько процессов путем передачи сообщений между ними, при этом коммуникаторов может быть несколько, группы которые они образуют могут как не пересекаться, так пересекаться частично. При старте программы все процессы работают под единым коммуникатором с именем MPI_COMM_WORLD. Кроме него существуют еще коммуникаторы MPI_COMM_SELF, MPI_COMM_NULL, которые содержат только текущий процесс и ни одного процесса соответственно.

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

Тег сообщения - целое не отрицательное число от 0 до 32767(В зависимости от реализации. Максимально возможная величина тега хранится в константе MPI_TAG_UB).

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

int MPI_Init(int *argc, char ***argv);
int MPI_Finalize(void);

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

Для того чтобы проверить работу программы реализуем самую примитивную программку на С++ с применением MPI.

#include <stdio.h>
#include "mpi.h"

int main(int argc, char **argv)
{
  printf("Before MPI_INIT\n");
  MPI_Init(&argc, &argv);
  printf("Parallel sect\n");
  MPI_Finalize();
  printf("After MPI_FINALIZE\n");
  return 0;
}

Чтобы запустить эту программу сохраним нашу запись в файле с любым названием и расширением *.cpp, после чего выполним следующие действия в консоли (В моем случае код лежит в файле main.cpp):

[user-name]$ mpic++ main.cpp -o main
[user-name]$ mpiexec -n 2 ./main 

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

Программа просто напечатает несколько строк в зависимости от количества процессов которое вы укажете. Не стоит пугаться если строки "Before ..." и "After ..." будут отображаться не по одному разу, в зависимости от реализации MPI программа может работать параллельно и вне процедур Init-Finalize.

Итог

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