В этом цикле статей речь пойдет о параллельном программировании.
- Часть 1. MPI — Введение и первая программа.
- Часть 2. MPI — Учимся следить за процессами.
- Часть 3. MPI — Как процессы общаются? Сообщения типа точка-точка.
В бой. Введение
Довольно часто самые сложные алгоритмы требуют огромного количества вычислительных ресурсов в реальных задачах, когда программист пишет код в стандартном его понимании процедурного или Объектно Ориентированного Программирования(ООП), то для особо требовательных алгоритмических задач, которые работают с большим количеством данных и требуют минимизировать время выполнения задачи, необходимо производить оптимизацию.
В основном используют 2 типа оптимизации, либо их смесь: векторизация и распараллеливание
вычислений. Чем же они отличаются?
Вычисления производятся на процессоре, процессор пользуется специальными «хранилищами» данных называемыми регистрами. Регистры процессора напрямую подключены к логическим элементам и требуют гораздо меньшее время для выполнения операций над данными, чем данные из оперативной памяти, а тем более на жестком диске, так как для последних довольно большую часть времени занимает пересылка данных. Так же в процессорах существует область памяти называемая Кэшем, в нем хранятся те значения, которые в данный момент участвуют в вычислениях или будут участвовать в них в ближайшее время, то есть самые важные данные.
Параллельные процессы MPI
Задача оптимизации алгоритма сводится к тому, чтобы правильно выстроить последовательность операций и оптимально разместить данные в Кэше, минимизировав количество возможных пересылок данных из памяти.
Так а чем отличаются векторизация и параллельные вычисления? Векторизация — позволяет выполнять операции над данными целыми векторами. Например для С++: если мы используем AVX инструкции, то у нас есть вектора размером 256 бит, куда мы можем поместить float32 элементы. Получится, что мы можем собрать 2 вектора по (256 / 32) = 8 float32 значений.
После чего выполнить над ними одну операцию за такт, хотя если бы мы этого не сделали, то вполне возможно, что аналогичные вычисления прошли бы за 8 операций, а то и больше если брать в учет вычисления индексов конкретных элементов. Однако есть одна проблема: компиляторы нынче довольно умны и довольно хорошо справляются с подобной оптимизацией и сами, поэтому большая часть сил уходит на то чтобы правильно организовать данные.
Параллелизация же позволяет пользоваться не только вычислительными возможностями одного процессора, а множеством процессоров, в том числе и в системах с распределенной памятью, и т.п. В подобных системах как правило намного больше вычислительных мощностей, но этим всем нужно уметь управлять и правильно организовывать параллельную работу на конкретных потоках.
Основная часть
В настоящее время существует много технологий которые позволяют наиболее легко организовать параллельные вычисления, одна из самых популярных на текущий момент это MPI.
Лекция 2. Основные функции библиотеки 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С++ int MPI_Finalize(void);
Первая процедура предназначения для инициализации параллельной части программы, все другие процедуры, кроме некоторых особых, могут быть вызваны только после вызова процедуры MPI_Init, принимает эта функция аргументы командной строки, через которые система может передавать процессу некоторые параметры запуска. Вторая процедура же предназначена для завершения параллельной части программы.
Для того чтобы проверить работу программы реализуем самую примитивную программку на С++ с применением MPI.
#include #include «mpi.h» int main(int argc, char **argv)
Чтобы запустить эту программу сохраним нашу запись в файле с любым названием и расширением *.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 и с чем его едят. В дальнейших туториалах мы рассмотрим уже более полезные программы и наконец перейдем ко коммуникации между процессами.
- mpi
- c++
- оптимизация
- параллельное программирование
- многопоточные приложения
Источник: habr.com
Примеры из учебника «Технологии параллельного программирования MPI и OpenMP»
Глава 1 Технология параллельного программирования MPI
1.1. Введение
1.2. Основные понятия
1.3. Общие процедуры MPI
Пример 1a. Простейшая программа на языке Си
Пример 1b. Простейшая программа на языке Фортран
Пример 2a. Определение числа процессов и номера процесса на языке Си
Пример 2b. Определение числа процессов и номера процесса на языке Фортран
Пример 3a. Распараллеливание на языке Си
Пример 3b. Распараллеливание на языке Фортран
Пример 4a. Определение характеристик системного таймера на языке Си
Пример 4b. Определение характеристик системного таймера на языке Фортран
1.4. Передача и прием сообщений между отдельными процессами
1.4.1. Операции типа точка-точка
1.4.2. Передача и прием сообщений с блокировкой
Пример 5a. Обмен сообщениями двух процессов на языке Си
Пример 5b. Обмен сообщениями двух процессов на языке Фортран
Пример 6a. Обмен сообщениями четных и нечетных процессов на языке Си
Пример 6b. Обмен сообщениями четных и нечетных процессов на языке Фортран
Пример 7a. Пересылка несуществующему процессу на языке Си
Пример 7b. Пересылка несуществующему процессу на языке Фортран
Пример 8a. Буферизованная посылка данных на языке Си
Пример 8b. Буферизованная посылка данных на языке Фортран
Пример 9a. Получение информации об атрибутах сообщения на языке Си
Пример 9b. Получение информации об атрибутах сообщения на языке Фортран
Пример 10a. Определение латентности и пропускной способности на языке Си
Пример 10b. Определение латентности и пропускной способности на языке Фортран
1.4.3. Передача и прием сообщений без блокировки
Пример 11a. Обмен по кольцевой топологии при помощи неблокирующих операций на языке Си
Пример 11b. Обмен по кольцевой топологии при помощи неблокирующих операций на языке Фортран
Пример 12a. Коммуникационная схема «мастер – рабочие» на языке Си
Пример 12b. Коммуникационная схема «мастер – рабочие» на языке Фортран
Пример 13a. Транспонирование матрицы на языке Си
Пример 13b. Транспонирование матрицы на языке Фортран
1.4.4. Отложенные запросы на взаимодействие
Пример 14a. Схема итерационного метода с обменом по кольцевой топологии при помощи отложенных запросов на языке Си
Пример 14b. Схема итерационного метода с обменом по кольцевой топологии при помощи отложенных запросов на языке Фортран
1.4.5. Тупиковые ситуации (deadlock)
Пример 15a. Обмен по кольцевой топологии при помощи процедуры MPI_Sendrecv на языке Си
Пример 15b. Обмен по кольцевой топологии при помощи процедуры MPI_SENDRECV на языке Фортран
1.5. Коллективные взаимодействия процессов
1.5.1. Общие положения
1.5.2. Барьер
Пример 16a. Моделирование барьерной синхронизации на языке Си
Пример 16b. Моделирование барьерной синхронизации на языке Фортран
1.5.3. Коллективные операции пересылки данных
1.5.4. Глобальные операции
Пример 17a. Моделирование глобального суммирования при помощи схемы сдваивания и коллективной операции MPI_Reduce на языке Си
Пример 17b. Моделирование глобального суммирования при помощи схемы сдваивания и коллективной операции MPI_Reduce на языке Фортран
1.5.5. Пользовательские глобальные операции
Пример 18a. Пользовательская глобальная функция на языке Си
Пример 18b. Пользовательская глобальная функция на языке Фортран
1.6. Группы и коммуникаторы
1.6.1. Общие положения
1.6.2. Операции с группами процессов
Пример 19a. Работа с группами на языке Си
Пример 19b. Работа с группами на языке Фортран
1.6.3. Операции с коммуникаторами
Пример 20a. Разбиение коммуникатора на языке Си
Пример 20b. Разбиение коммуникатора на языке Фортран
Пример 21a. Перенумерация процессов на языке Си
Пример 21b. Перенумерация процессов на языке Фортран
1.6.4. Интеркоммуникаторы
Пример 22a. Cхема «мастер – рабочие» с использованием интеркоммуникатора на языке Си
Пример 22b. Схема «мастер – рабочие» с использованием интеркоммуникатора на языке Фортран
1.6.5. Атрибуты
1.7. Виртуальные топологии
1.7.1. Общие положения
1.7.2. Декартова топология
1.7.3. Топология графа
Пример 23a. Cхема «мастер – рабочие» с использованием графовой топологии на языке Си
Пример 23b. Схема «мастер – рабочие» с использованием графовой топологии на языке Фортран
1.8. Пересылка разнотипных данных
1.8.1. Общие положения
1.8.2. Производные типы данных
Пример 24a. Перестановка столбцов матрицы в обратном порядке на языке Си
Пример 24b. Перестановка столбцов матрицы в обратном порядке на языке Фортран
1.8.3. Упаковка данных
Пример 25a. Пересылка упакованных данных на языке Си
Пример 25b. Пересылка упакованных данных на языке Фортран
1.9. Объект info
1.9.1. Общие положения
1.9.2. Работа с объектом info
1.10. Динамическое управление процессами
1.10.1. Общие положения
1.10.2.Порождение процессов
master.c
slave.c
Пример 26a. Схема «мастер – рабочие» с использованием порождения процессов на языке Си
master.f
slave.f
Пример 26b. Схема «мастер – рабочие» с использованием порождения процессов на языке Фортран
1.10.3. Клиент-серверная связь
server.c
client.c
Пример 27a. Обмен данными между сервером и клиентом посредством публичного имени на языке Си
server.f
client.f
Пример 27b. Обмен данными между сервером и клиентом посредством публичного имени на языке Фортран
1.10.4. Удаление связи процессов
1.10.5. Связь через сокеты
1.11. Односторонние коммуникации
1.11.1. Общие положения
1.11.2. Работа с окном
1.11.3. Передача данных
1.11.4. Синхронизация
Пример 28a. Обмен по кольцевой топологии при помощи односторонних коммуникаций на языке Си
Пример 28b. Обмен по кольцевой топологии при помощи односторонних коммуникаций на языке Фортран
Пример 29a. Обмен по кольцевой топологии при помощи односторонних коммуникаций на языке Си
Пример 29b. Обмен по кольцевой топологии при помощи односторонних коммуникаций на языке Фортран
Пример 30a. Обмен по кольцевой топологии при помощи односторонних коммуникаций на языке Си
Пример 30b. Обмен по кольцевой топологии при помощи односторонних коммуникаций на языке Фортран
1.12. Внешние интерфейсы
1.12.1. Обобщенные запросы
1.12.2. Информация из статуса
1.12.3. Нити
1.13. Параллельный ввод/вывод
1.13.1. Определения
1.13.2. Работа с файлами
1.13.3. Доступ к данным
Пример 31a. Буферизованное чтение из файла на языке Си
Пример 31b. Буферизованное чтение из файла на языке Фортран
Пример 32a. Коллективное чтение из файла на языке Си
Пример 32b. Коллективное чтение из файла на языке Фортран
1.14. Обработка ошибок
1.14.1. Общие положения
1.14.2. Обработчики ошибок, связанные с коммуникаторами
1.14.3. Обработчики ошибок, связанные с окнами
1.14.4. Обработчики ошибок, связанные с файлами
1.14.5. Дополнительные процедуры
1.14.6. Коды и классы ошибок
1.14.7. Вызов обработчиков ошибок
Пример 33a. Обработка ошибок на языке Си
Пример 33b. Обработка ошибок на языке Фортран
Глава 2 Технология параллельного программирования OpenMP
2.1. Введение
2.2. Основные понятия
2.2.1. Компиляция программы
Пример 34a. Условная компиляция на языке Си
Пример 34b. Условная компиляция на языке Фортран
Пример 34c. Условная компиляция на языке Фортран
2.2.2. Модель параллельной программы
2.2.3. Директивы и процедуры
2.2.4. Выполнение программы
2.2.5. Замер времени
Пример 35a. Работа с системными таймерами на языке Си
Пример 35b. Работа с системными таймерами на языке Фортран
2.3. Параллельные и последовательные области
2.3.1. Директива parallel
Пример 36a. Параллельная область на языке Си
Пример 36b. Параллельная область на языке Фортран
Пример 37a. Опция reduction на языке Си
Пример 37b. Опция reduction на языке Фортран
2.3.2. Сокращенная запись
2.3.3. Переменные среды и вспомогательные процедуры
Пример 38a. Процедура omp_set_num_threads и опция num_threads на языке Си
Пример 38b. Процедура omp_set_num_threads и опция num_threads на языке Фортран
Пример 39a. Процедуры omp_set_dynamic и omp_get_dynamic на языке Си
Пример 39b. Процедуры omp_set_dynamic и omp_get_dynamic на языке Фортран
Пример 40a. Вложенные параллельные области на языке Си
Пример 40b. Вложенные параллельные области на языке Фортран
Пример 41a. Функция omp_in_parallel на языке Си
Пример 41b. Функция omp_in_parallel на языке Фортран
2.3.4. Директива single
Пример 42a. Директива single и опция nowait на языке Си
Пример 42b. Директива single и опция nowait на языке Фортран
Пример 43a. Опция copyprivate на языке Си
Пример 43b. Опция copyprivate на языке Фортран
2.3.5. Директива master
Пример 44a. Директива master на языке Си
Пример 44b. Директива master на языке Фортран
2.4. Модель данных
Пример 45a. Опция private на языке Си
Пример 45b. Опция private на языке Фортран
Пример 46a. Опция shared на языке Си
Пример 46b. Опция shared на языке Фортран
Пример 47a. Опция firstprivate на языке Си
Пример 47b. Опция firstprivate на языке Фортран
Пример 48a. Директива threadprivate на языке Си
Пример 48b. Директива threadprivate на языке Фортран
Пример 49a. Опция copyin на языке Си
Пример 49b. Опция copyin на языке Фортран
2.5. Распределение работы
2.5.1. Низкоуровневое распараллеливание
Пример 50a. Процедуры omp_get_num_threads и omp_get_thread_num на языке Си
Пример 50b. Процедуры omp_get_num_threads и omp_get_thread_num на языке Фортран
2.5.2. Параллельные циклы
Пример 51a. Директива for на языке Си
Пример 51b. Директива do на языке Фортран
Пример 52a. Опция schedule на языке Си
Пример 52b. Опция schedule на языке Фортран
Пример 53a. Опция schedule на языке Си
Пример 53b. Опция schedule на языке Фортран
2.5.3. Параллельные секции
Пример 54a. Директива sections на языке Си
Пример 54b. Директива sections на языке Фортран
Пример 55a. Опция lastprivate на языке Си
Пример 55b. Опция lastprivate на языке Фортран
2.5.4. Директива workshare
2.5.5. Задачи (tasks)
Пример 57a. Директива taskyield на языке Си
Пример 57b. Директива taskyield на языке Фортран
2.6. Синхронизация
2.6.1. Барьер
Пример 58a. Директива barrier на языке Си
Пример 58b. Директива barrier на языке Фортран
2.6.2. Директива ordered
Пример 59a. Директива ordered и опция ordered на языке Си
Пример 59b. Директива ordered и опция ordered на языке Фортран
2.6.3. Критические секции
Пример 60a. Директива critical на языке Си
Пример 60b. Директива critical на языке Фортран
2.6.4. Директива atomic
Пример 61a. Директива atomic на языке Си
Пример 61b. Директива atomic на языке Фортран
2.6.5. Замки́̀
Пример 62a. Использование замков на языке Си
Пример 62b. Использование замков на языке Фортран
Пример 63a. Функция omp_test_lock на языке Си
Пример 63b. Функция omp_test_lock на языке Фортран
2.6.6. Директива flush
2.7. Дополнительные переменные среды и процедуры
2.8. Использование OpenMP
Глава 3 Реализация параллельных алгоритмов
3.1. Введение
3.2. Простейшая вычислительная программа
3.2.1. Реализация на OpenMP
Пример 64a. Вычисление числа Пи на языке Си с использованием технологии OpenMP
Пример 64b. Вычисление числа Пи на языке Фортран с использованием технологии OpenMP
3.2.2. Реализация на MPI
Пример 65a. Вычисление числа Пи на языке Си с использованием технологии MPI
Пример 65b. Вычисление числа Пи на языке Фортран с использованием технологии MPI
3.3. Параллельная реализация вычислительно сложных задач на примере решения задачи перемножения плотных матриц
3.3.1. Постановка задачи
3.3.2. Последовательная реализация
Пример 66a. Последовательный вариант перемножения матриц на языке Си
Пример 66b. Последовательный вариант перемножения матриц на языке Фортран
3.3.3. Параллельная реализация
3.3.4. Реализация на OpenMP
Пример 67a. Перемножение матриц на языке Си с использованием технологии OpenMP
Пример 67b. Перемножение матриц на языке Фортран с использованием технологии OpenMP
3.3.5. Реализация на MPI
3.3.5.1. Распределение на одномерную решетку процессов (строчное или столбцовое)
Пример 68a. Перемножение матриц на языке Си с использованием технологии MPI (одномерная решетка процессов)
Пример 68b. Перемножение матриц на языке Фортран с использованием технологии MPI (одномерная решетка процессов)
3.3.5.2. Распределение на двумерную решетку процессов (строчно-столбцовое)
Пример 69a. Перемножение матриц на языке Си с использованием технологии MPI (двумерная решетка процессов)
Пример 69b. Перемножение матриц на языке Фортран с использованием технологии MPI (двумерная решетка процессов)
Источник: parallel.ru
Основы технологии MPI на примерах
Параллельное программирование — очень актуальное направление, т.к. большинство современных вычислительных устройств (включая телефоны) являются многоядерными или многопроцессорными. В предыдущей записи я публиковал учебник по OpenMP, однако OpenMP позволяет программировать только системы с общей памятью — в большей части, многоядерные компьютеры. Основной проблемой таких систем является плохая масштабируемость — не так легко и дешево увеличить число ядер в компьютере.
Другой класс параллельных ЭВМ — системы с распределенной памятью, к которым, в частности, относятся кластеры. Они представляют собой набор соединенных сетью компьютеров. Такая система гораздо лучше мастабируется — не составит особого труда купить и подключить в сеть дополнительную сотню компьютеров. Число вычислительных узлов в кластерах измеряется тысячами.
Взаимодействуют узлы кластера с помощью передачи сообщений по сети, поэтому стандартом программирования таких систем является MPI (Message Passing Interface). Библиотека MPI предоставляет программисту огромный выбор способов передать сообщение между узлами, в этой статье я постараюсь описать основные способы на простых примерах.
Ключевые особенности MPI
Допустим, есть у нас кластер. Чтобы программа начала на нем выполняться, ее необходимо скопировать на каждый узел, запустить и установить связь между процессами. Эту работу берет на себя утилита mpirun (под Linux) или mpiexec (под Windows), так например, чтобы запустить 5 процессов достаточно написать:
mpirun -np 5 path/your_mpi_program
Однако программа должна быть написана определенным образом. Вообще, технология MPI позволяет как использовать модель SPMD (Single Process, Multiple Data), так и MPMD [1], в этой статье я рассматривают только первый вариант. Далее по тексту узел и процесс будут означать одно и тоже, хотя на одном узле может быть создано несколько процессов (именно так я делаю при запуске примеров статьи, т.к. отлаживаю их на персональном компьютере). Это вводная статья, поэтому тут не пойдет речь о коммуникаторах, в которые могут группироваться процессы.
Суть SPMD заключается в том, что для решения задачи запускается множество одинаковых процессов. На приведенном выше рисунке видно, что пользователь (который вводит данные и хочет получить результат) взаимодействует только с одним узлом кластера. Такой узел называется root и логика его работы должна отличаться, ведь он должен не только взаимодействовать с пользователем, но и, получив исходные данные, выполнить их рассылку остальным процессам. Каждый процесс имеет свой номер (в MPI принят термин «ранг«) в рамках каждого коммуникатора, при этом у root ранг обычно равен нулю.
Процессы обмениваются сообщениями, каждое из которых помимо номеров процесса отправителя и получателя имеет тег, а также тип и количество передаваемых элементов. Тег представляет собой целое число, с помощью которого программа может отличать одни сообщения от других. В силу того, что сегодня мы рассмотрим очень простые примеры, тег нам не особо пригодится (можно было бы везде использовать, скажем, «ноль» вместо тега). Все поступающие процессу сообщения помещаются в очередь, из которой могут быть извлечены в соответствии с запрашиваемыми параметрами (тегом, отправителем и т.п.).
В связи с тем, что MPI-программа обладает множеством особенностей, компилироваться она должна специальным компилятором. Под Linux для этого используется mpic++, а под Windows можно применять расширение для Microsoft Visual Studio. Для сборки примеров статьи под Linux я использовал примерно следующую команду:
mpic++ main.cpp -o main
Разобравшись с особенностями технологии, перейдем к примерам. В этой статье мы будем пытаться посчитать сумму элементов массива — несмотря на простоту, эта задача позволяет продемонстрировать самые различные способы передачи данных между узлами.
Операции точка-точка MPI
Блокирующие операции — MPI_Send, MPI_Recv, MPI_Probe
Операции точка-точка позволяют передавать данные между парой узлов. Самые простые функции этого вида — MPI_Send и MPI_Recv, выполняющие передачу и прием сообщения, соответственно:
MPI_Send(void* buf, int count, MPI_Datatype datatype, int dest, int tag, MPI_Comm comm) MPI_Recv(void* message, int count, MPI_Datatype datatype, int source, int tag, MPI_Comm comm, MPI_Status* status)
Функция MPI_Send выполняет передачу count элементов типа datatype, начиная с адреса определенного buf, процессу с номером dest в коммуникаторе comm. При этом сообщению присваивается некоторый тег.
Функция MPI_Recv выполняет прием, при этом она ожидает появления во входном буфере сообщения с заданными параметрами (выполнение программы не продолжится до того, как такое сообщение поступит). Функция также возвращает статус, который может содержать код ошибки.
Рассмотрим первый пример:
#include «mpi.h» #include using namespace std; const int Tag = 0; const int root = 0; double sum_array(double *array, int n) < double sum = 0; for (int i = 0; i < n; ++i) < sum += array[i]; >return sum; > int main() < int rank, commSize; MPI_Init(NULL, NULL); MPI_Comm_rank(MPI_COMM_WORLD, MPI_Comm_size(MPI_COMM_WORLD, double *arr, sum = 0, buffer; int n; MPI_Status status; if (root == rank) < cout > n; arr = new double[n]; for (int i = 0; i < n; ++i) cin >> arr[i]; int partSize = n/commSize; int shift = n%commSize; for (int i = root+1; i < commSize; ++i) < MPI_Send(arr + shift + partSize*i, partSize, MPI_DOUBLE, i, Tag, MPI_COMM_WORLD); >sum = sum_array(arr, shift + partSize); for (int i = root+1; i < commSize; ++i) < MPI_Recv(status); sum += buffer; >> else < MPI_Probe(root, Tag, MPI_COMM_WORLD, MPI_Get_count(n); arr = new double[n]; MPI_Recv(arr, n, MPI_DOUBLE, root, Tag, MPI_COMM_WORLD, sum = sum_array(arr, n); MPI_Send( >delete[] arr; cout
Все обращения к функциям MPI должны размещаться между MPI_Init и MPI_Finalize. В качестве коммуникатора в этом примере используется MPI_COMM_WORLD, который включает в себя все процессы, запущенные для текущей задачи с помощью mpirun. Каждый процесс получает свой ранг с помощью вызова MPI_Comm_rank, количество процессов в коммуникаторе возвращает функция MPI_Comm_size.
В теле программы явно выделяется два блока кода — один выполняется главным процессом, а другой — остальными. Главный процесс занимается вводом/выводом данных, и их распределением между остальными узлами. Все остальные процессы ожидают от главного часть массива, вычисляют сумму элементов и передают результат назад. Чтобы принять массив, дочерние процессы должны сначала выделить память, но для этого необходимо знать сколько именно элементов им будет передано — сделать это можно с помощью функции MPI_Probe, которая работает также как MPI_Send (блокирует процесс до поступления в очередь сообщения с заданными параметрами), но не удаляет сообщение из очереди, а лишь возвращает его статус. Структура типа MPI_Status содержит тип элементов и их количество.
Операции MPI_Send, MPI_Probe и MPI_Recv являются синхронными (блокирующими), т.к. останавливают выполнение основного потока процесса до тех пор, пока не выполнится какое-либо действие (данные не будут записаны в сокет или не поступит сообщение с требуемыми параметрами).
Асинхронные операции — MPI_Isend
Приведенный выше пример работает прекрасно, но бутылочным горлышком является нулевой процесс, т.к. перед тем как приступить к обработке своей части массива root должен передать данные всем остальным процессами. Немного улучшить картину можно с помощью неблокирующих (асинхронных) операций — одной из них является MPI_Isend.
Функции неблокирующего обмена имеют такие же аргументы как и их блокирующие аналоги, но в качестве дополнительного параметра принимают параметр типа MPI_Request. Чтобы нулевой процесс в приведенном выше примере работал асинхронно достаточно изменить лишь этот фрагмент кода:
for (int i = root+1; i
Теперь функция передачи возвращает управление немедленно, сама же передача происходит параллельно с выполнением других команд процесса. Узнать о ходе выполнения асинхронной операции мы сможем с помощью специальных функций:
int MPI_Wait(MPI_Request *request, MPI_Status *status); int MPI_Test(MPI_Request *request, int *flag, MPI_Status *status);
Функция MPI_Wait является блокирующей — она останавливает выполнение процесса до тех пор, пока передача, связанная с request не будет завершена. Функция MPI_Test является неблокирующей (не дожидается окончания выполнения операции) — о том была завершена операция или нет, она сигнализирует с помощью флага (true — завершена).
В нашем примере в использовании функций MPI_Wait и MPI_Test нет необходимости, т.к. синхронно выполняется сбор результатов вычислений процессов. Главный процесс инициирует передачу данных и приступает к обработке своей части массива, после этого синхронно ожидает поступления данных от каждого по очереди процесса. Кстати, асинхронной может быть не только передача, но и прием данных — функция MPI_Irecv.
Чтобы избежать ошибок, необходимо представлять как именно может быть реализована работа неблокирующих функций. Например, MPI_Isend инициирует передачу данных, которая выполняется в отдельном потоке параллельно. По окончанию передачи этот поток должен изменить переменную request. Это значит, что такой код вполне может привести к ошибкам:
for (int i = root+1; i
Тут на каждой итерации цикла создается экземпляр переменной типа MPI_Request, инициируется передача и объект разрушается (память освобождается). Это значит, что поток, выполняющий передачу обратится к памяти, которая будет освобождена (и возможно уже повторно распределена для других целей), а значит — программа будет вести себя непредсказуемо. Вывод — объект request должен существовать до завершения асинхронной передачи.
Вызов функции MPI_Request_free необходим в случаях если не требуется ждать окончания асинхронной передачи и при этом хочется использовать один экземпляр MPI_Request — в нашем случае один и тот же объект используется для передачи данных всем дочерним процессам. За более детальной информацией о работе асинхронных операций MPI предлагаю обратиться к стандарту (раздел 3.7 Nonblocking Communication) [3].
Буферизованная передача — MPI_Bsend
В стандарте MPI сказано, что функция MPI_Send вернет управление после того, как сообщение будет записано в выходной буфер, я же выше писал что это сокет (пусть это не совсем точно) — стандарт в этом месте дает некоторую свободу, возможны различные реализации. Однако, «выходной буфер» в стандарте — это однозначно не область в оперативной памяти, т.к. для работы с буфером в ОЗУ предусмотрена другая функция — MPI_Bsend.
Функция MPI_Send записывает данные в сокет и только после этого возвращает управление. Функция MPI_Isend вернет управление сразу, но нам все равно нельзя будет изменять передаваемые данные, пока они не будут записаны в сокет.
При этом, работа с сокетом выполняется медленнее, чем с оперативной памятью — поэтому ускорить работу программы в ряде случаев можно путем копирования данных в некоторый буфер в оперативной памяти и передачей данных из этого буфера. Изменять отправляемые данные мы сможем сразу после того, как они будут скопированы. Примерно так и работает функция MPI_Bsend. Сложность реализации такой операции вручную заключается также в том, что после отправки данных память из под буфера нужно освободить.
Чтобы выделенная область памяти использовалась в качестве буфера при передачи в буферизованном режиме — необходимо использовать функцию MPI_Buffer_attach. Буфер может состоять из нескольких «присоединенных» областей. В разделе 3.6.1 стандарта [3] говорится о том, что буфер может быть устроен как циклическая очередь сообщений, отправленные сообщения из буфера удаляются, позже на их место могут быть записаны другие сообщения.
При использовании буферизованного режима исходный код будет не сильно отличаться от приведенного выше, ниже приведен только фрагмент, которого коснулись изменения:
int message_buffer_size = n*sizeof(double) + MPI_BSEND_OVERHEAD; double* message_buffer = (double*)malloc(message_buffer_size); MPI_Buffer_attach(message_buffer, message_buffer_size); int shift = n%commSize; for (int i = root+1; i < commSize; ++i) < MPI_Bsend(arr + shift + partSize*i, partSize, MPI_DOUBLE, i, Tag, MPI_COMM_WORLD); >sum = sum_array(arr, shift + partSize); for (int i = root+1; i < commSize; ++i) < MPI_Recv(status); sum += buffer; >MPI_Buffer_detach(message_buffer, free(message_buffer);
Перед использованием функции выделяется память под буфер, т.к. в этой памяти размещается очередь — следовательно есть некоторые издержки (размер которых зависит от конкретной реализации стандарта), поэтому необходимо выделять чуть больше памяти (MPI_BSEND_OVERHEAD). Выделенная область прикрепляется к буферу, затем используется MPI_Bsend (аргументы функции полностью совпадают с MPI_Send, буфер в качестве аргумента не передается, т.к. он является глобальным для процесса). После того, как все сообщения будут переданы — буфер можно отсоединить, а память освободить.
Коллективные операции. Пример использования MPI_Reduce
Коллективные операции выполняются всеми процессами указанного коммуникатора. Ниже приведена картинка из стандарта [3], на которой показана суть некоторых операций:
Верхняя часть схемы иллюстрирует операцию MPI_Bcast, которая позволяет передать некоторые данные с одного узла кластера на все остальные. Нижняя — соответствует операциям MPI_Scatter и MPI_Gather. Если у нас на узле U есть массив из N элементов и его части необходимо передать на P узлов кластера — можно использовать функцию MPI_Scatter. Проблем не возникнет если N делится нацело на P, т.к. при выполнении MPI_Scatter все узлы получат одинаковое количество элементов. Обратную операцию выполняет MPI_Gather, т.е. собирает данные со всех P узлов на узел U.
Эти операции являются синхронными и используют MPI_Send (это закреплено стандартом), однако существуют асинхронные аналоги — MPI_Ibcast, MPI_Igather и MPI_Iscatter.
Операция MPI_Bcast теоретически (зависит от реализации библиотеки) может работать более эффективно и выполняться за (O(log(n))) операций вместо (O(n)).
На приведенной схеме цветом выделен узел, на котором находятся передаваемые данные. В начале работы такой узел один. После первой передачи данные есть уже на двух узлах, оба они могут участвовать в передачи. При реализации такой схемы для передачи данных на 1000 узлов будет достаточно 10 операций. Таким же образом может работать операция MPI_Reduce:
A more efficient implementation is achieved by taking advantage of associativity and using a logarithmic tree reduction. [3]
Операция MPI_Reduce не просто передает данные, но и выполняет над ними заданную операцию. В нашем примере применить ее можно вместо сбора результатов вычисления сумм:
if (root == rank) < cout > n; arr = new double[n]; for (int i = 0; i < n; ++i) cin >> arr[i]; int partSize = n/commSize; int shift = n%commSize; for (int i = root+1; i < commSize; ++i) < MPI_Send(arr + shift + partSize*i, partSize, MPI_DOUBLE, i, Tag, MPI_COMM_WORLD); >sum = sum_array(arr, shift + partSize); > else < MPI_Probe(root, Tag, MPI_COMM_WORLD, MPI_Get_count(n); arr = new double[n]; MPI_Recv(arr, n, MPI_DOUBLE, root, Tag, MPI_COMM_WORLD, sum = sum_array(arr, n); >double global_sum = 0; MPI_Reduce(global_sum, 1, MPI_DOUBLE, MPI_SUM, root, MPI_COMM_WORLD); if (rank == root)
Операция MPI_Reduce может выполняться не только над числами, но и над массивами (при этом будет применена к каждому его элементу отдельно).
Заключение
Целью статьи было продемонстрировать ряд функций библиотеки MPI и показать, что реализовать их вручную не так легко — этим привлечь внимание к библиотеке.
Пример с функцией MPI_Isend наглядно демонстрирует насколько сложно реализовать аналогичное поведение вручную. Дело не только в том, что передача выполняется в отдельном потоке. Сложно придумать механизм лучший, чем работа с MPI_Request, однако к объекту request может параллельно обращаться несколько потоков, поэтому все эти операции защищаются семафорами.
Еще более наглядным является пример с MPI_Bsend, т.к. вручную реализовать циклический буфер сообщений (который, кстати, тоже защищается семафорами) — не простая задача. Однако, в библиотеке MPI гораздо больше функций типа точка-точка. Различие между ними заключается в преставлении о «завершенной передаче», т.е. моменте когда блокирующая операция вернет управление или для асинхронной операции завершится MPI_Wait.
Примеры статьи являются полностью искусственными — именно по этой причине я не стал приводить таблицу с временем выполнения программы для различных вариантов реализации. Дело в том, что кластерная архитектура (а следовательно и MPI) подходит не всех типов задач — необходимо учитывать затраты на передачу данных. Так, для вычисления на кластере суммы элементов массива необходимо выполнить, порядка (O(n)) операций передачи, но (O(frac
)) операций сложения может быть выполнено параллельно. Трудоемкость вычислений будет оцениваться (O(n)) при любом количестве узлов кластера. Подробнее об оценке трудоемкости параллельных алгоритмов советую прочитать в книге Миллера [4].
Вспомогательная литература
Источник: pro-prof.com