Анализ моделей параллельного программирования

Введение
С момента появления вычислительных машин одной из основных их функций является выполнение трудоемких вычислений. При этом сложность поставленных задач растет быстрее, чем производительность отдельного процессора. Многие современные вычислительные задачи невозможно решить с помощью однопроцессорных ЭВМ, поскольку программа будет выполняться слишком долго либо затребует большой объем ресурсов таких, как, например, память. Поэтому для увеличения скорости вычислений применяется также и другой путь - создание многопроцессорных ЭВМ.Параллельным программированием будем называть процесс написания программы для многопроцессорной системы. Разумеется, параллельное программирование имеет ряд особенностей по сравнению с традиционным последовательным программированием. В данной работе мы акцентируем внимание на моделях параллельного программирования.Цель: выявить характеристики, присущие моделям параллельного программированияЗадачи:1. Предоставить краткий обзор существующих моделей2. Рассмотреть основные модели параллельного программирования 3. Выделить особенности параллельного программирования4. Предоставить информацию о технологии для создания параллельных программ и об интерфейсе MPI.Глава 1. Краткий обзор существующих моделейВ настоящее время в области научно-технических расчетов превалируют три модели параллельного программирования: модель передачи сообщений, модель с общей памятью и модель параллелизма по данным.* Модель передачи сообщений. В модели передачи сообщений каждый процесс имеет собственное локальное адресное пространство. Обработка общих данных и синхронизация осуществляется посредством передачи сообщений. Обобщение и стандартизация различных библиотек передачи сообщений привели к разработке стандарта MPI (Message Passing Interface).На сегодняшний день модель передачи сообщений является наиболее широко используемой моделью параллельного программирования. Программы этой модели создают множество процессов, с каждым из которых ассоциированы локальные данные. Каждый процесс идентифицируется уникальным именем. Процессы взаимодействуют, посылая и получая сообщения. Модель передачи сообщений не накладывает ограничений ни на динамическое создание процессов, ни на выполнение нескольких процессов одним процессором, ни на использование разных программ для разных процессов. Формальные описания систем обмена сообщениями не рассматривают вопросы, связанные с манипулированием процессами. Однако, при реализации таких систем приходится принимать какое-либо решение в этом отношении. На практике сложилось так, что большинство систем обмена сообщениями при запуске параллельной программы создает фиксированное число идентичных процессов и не позволяет создавать и разрушать процессы в течение работы программы. В таких системах каждый процесс выполняет одну и ту же программу (параметризованную относительно идентификатора либо процесса, либо процессора), но работает с разными данными, поэтому о таких системах говорят, что они реализуют SPMD (single program multiple data - одна программа много данных) модель программирования. SPMD модель приемлема и достаточно удобна для широкого диапазона приложений параллельного программирования, но она затрудняет разработку некоторых типов параллельных алгоритмов.* Модель с общей памятью. В модели с общей памятью процессы разделяют общее адресное пространство. Так как нет ограничений на использование общих данных, то программист должен явно специфицировать общие данные и упорядочивать доступ к ним с помощью средств синхронизации. В языках высокого уровня логически независимые нити (threads Нить — это легковесный процесс, имеющий с другими нитями общие ресурсы, в том числе общую оперативную память. С концептуальной точки зрения нить существует внутри процесса, являясь более мелкой единицей управления программой.) вычислений определяются на уровне функциональных задач или витков цикла. Обобщение и стандартизация моделей с общей памятью привели к созданию стандарта OpenMP. В OpenMP за основу берется последовательная программа, а для создания ее параллельной версии пользователю предоставляется набор директив, процедур и переменных окружения. Стандарт OpenMP разработан для языков Фортран, С и С++.В модели программирования с общей памятью, все процессы совместно используют общее адресное пространство, к которому они асинхронно обращаются с запросами на чтение и запись. В таких моделях для управления доступом к общей памяти используются всевозможные механизмы синхронизации типа семафоров и блокировок процессов. Преимущество этой модели с точки зрения программирования состоит в том, что понятие собственности данных (монопольного владения данными) отсутствует, следовательно, не нужно явно задавать обмен данными между производителями и потребителями. Эта модель, с одной стороны, упрощает разработку программы, но, с другой стороны, затрудняет понимание и управление локальностью данных, написание детерминированных программ. В основном эта модель используется при программировании для архитектур с общедоступной памятью.* Модель параллелизма по данным. В модели параллелизма по данным отсутствует понятие процесса и, как следствие, явная передача сообщений или явная синхронизация. В этой модели данные последовательной программы распределяются по узлам (процессорам) вычислительной системы. Последовательная программа преобразуется компилятором либо в модель передачи сообщений, либо в модель с общей памятью. При этом вычисления распределяются по правилу собственных вычислений Правило собственных вычислений - каждый процессор выполняет только вычисления собственных данных, т.е. данных, распределенных на этот процессор.Модель параллелизма по данным также является часто используемой моделью параллельного программирования. Название модели происходит оттого, что она эксплуатирует параллелизм, который заключается в применении одной и той же операции к множеству элементов структур данных. Например, "умножить все элементы массива M на значение x" или "снизить цену автомобилей со сроком эксплуатации более 5-ти лет". Программа с параллелизмом данных состоит из последовательностей подобных операций. Поскольку операции над каждым элементом данных можно рассматривать как независимые процессы, то степень детализации таких вычислений очень велика, а понятие "локальности" (распределения по процессам) данных отсутствует. Следовательно, компиляторы языков с параллелизмом данных часто требуют, чтобы программист предоставил информацию относительно того, как данные должны быть распределены между процессорами, другими словами, как программа должны быть разбита на процессы.Кроме описанных основных моделей существуют такие, как модель параллелизма по управлению, модель параллелизма по управлению с передачей сообщений и другие.Глава 2. Основные модели параллельного программированияПринято (условно) выделять следующие основные стили (модели решения, парадигмы) параллельного программирования:1. Итеративный параллелизм.2. Рекурсивный параллелизм.3. «Производители и потребители» (конвейеры).4. «Клиенты и серверы».5. «Взаимодействующие равные».Итеративный параллелизм: несколько процессов (часто одинаковых) выполняют циклические вычисления, решая одну задачу. Часто используется для выполнения разных итераций одного цикла параллельно.Рекурсивный параллелизм: рекурсивные вызовы процедуры, которые являются независимыми (работают над различными частями общих данных), могут выполняться параллельно. Используется для решения комбинаторных задач, реализации метода ветвей и границ и т. д.«Производители и потребители»: процессы, объединяемые в конвейер. Каждый процесс потребляет данные — возможно, результат вычислений предыдущего процесса, и передаёт результат вычислений следующему. Используется для выполнения однотипных многоэтапных вычислений над большими объёмами данных: каждое элементарное действие может выполняться над следующими данными, в то время как результат обработки предыдущих обрабатывается далее по конвейеру. Часто используется для аппаратной реализации вычислений: цифровые фильтры, обработка изображений, микроархитектура процессорного ядра и т. д.«Клиенты и серверы»: Процесс клиента отправляет запрос серверу на оказание услуги и затем ожидает от него результата (возможно, параллельно выполняя другие действия). Процесс сервера в цикле ожидает запроса от клиента и, получив его, обрабатывает. Сервер может быть реализован как однопоточное или многопоточное приложение. В зависимости от этого сервер способен одновременно обрабатывать запросы от нескольких клиентов, либо нет. Модель представляет собой обобщение концепции вызова процедуры.«Взаимодействующие равные»: несколько процессов, решая одну задачу, исполняют один и тот же код, обмениваясь сообщениями. Используется при итеративном параллелизме и децентрализованном принятии решений.Глава 3. Особенности параллельного программированияПараллельное программирование – это особый метод написания программ, при котором процесс решения целой задачи разделяется на несколько отдельных подзадач, которые будут выполняться одновременно на нескольких процессорах (ядрах) компьютера.Предполагается, что такой подход приводит к сокращению времени программного решения общей задачи. Тем не менее, на практике могут возникать ситуации, когда многоядерное программирование вовсе не ускоряет процесс поиска решения. Причинами такой низкой производительности параллельной программы, могут быть:сама задача недостаточно подходит для применения к ней параллельных методов решения;неправильное использование методов распараллеливания, что приводит к неэффективности данного подхода.Посмотрим теперь, какими свойствами должна обладать задача и как необходимо выстроить логику её решения, для того чтобы к ней было уместно применять технологии параллельного программирования. Перечислим эти основные моменты, позволяющие заметить эффект от приёмов параллельного программирования:В поставленной задаче нужно иметь достаточный объём работы для распараллеливания, чтобы покрыть издержки самого процесса распараллеливания.Необходимо грамотно определить размер отдельных подзадач и их общее количество. Так, если их будет слишком много, то образуются очереди к ядрам процессора, и решение оказывается неоптимальным. И наоборот, если количество подзадач будет очень малым, то некоторые ядра процессора будут просто без работы, что также снижает общую производительность системы.Должна быть правильно выстроена балансировка нагрузки между отдельными ядрами процессора, что зачастую автоматически реализуется в применяемых инструментах для параллельного программирования.Требуется хорошая организация по выделению памяти и сборке мусора. Поскольку области памяти компьютера, выделяемые для параллельных вычислений, не должны перекрывать друг друга, то здесь важны вопросы о синхронизации всех одновременно выполняемых программой процессов. При очищении памяти возникают достаточно серьёзные временные затраты, плюс затрудняется распараллеливание задачи во время такой постоянной очистки.Минимизация проблем, связанных с кэшированием. Например, бывает так, что одно из ядер записывает значение в определённую область памяти, расположенную в кэше другого ядра. Или же различные ядра записывают значения хотя и в разные области памяти, но, допустим, находящиеся в одной строке кэша. Всё это значительно снижает производительность программы. Для того, чтобы уменьшить вероятность появления таких ситуаций, нужно определённым образом проектировать структуры данных, сохраняя в алгоритме решения задачи локальность обрабатываемых данных относительно общего потока.Глава 4. Технологии для создания параллельных программ. Интерфейс MPIВ настоящее время существует достаточно большое количество инструментов, позволяющих организовать параллельные вычисления для решения объёмных задач, например, таких как проведение различных научно-инженерных расчётов на вычислительных кластерах и в сетях. Среди них есть такие технологии как MPI, OpenMP, CUDA, HPF, DVM и т. д.Любой язык, подходящий для параллельного программирования, должен предоставлять: средства для создания параллельных потоков; возможности по взаимодействию параллельных процессов между собой; конструкции для их синхронизации.Интерфейс MPI: MPI (от англ. Message Passing Interface – интерфейс передачи сообщений) – это одна из распространённых технологий для параллельного программировании, основанная на том, что параллельные процессы взаимодействуют друг с другом при помощи обмена сообщениями.Сообщение в MPI – это массив (набор) однотипных данных, расположенных в последовательных ячейках памяти. Каждое такое сообщение имеет несколько атрибутов, среди которых номер процесса-отправителя, номер процесса-получателя, идентификатор самого сообщения и другие.Технология MPI поддерживается такими языками программирования, как Fortran и Си. Сам интерфейс MPI включает в себя описание более 125 процедур и функций, причём их программная реализация особо сильно не зависит от выбранного языка программирования.Так как MPI представляет собой библиотеку, то для успешной компиляции программы необходимо подключить соответствующие библиотечные модули. В начале любой программы, использующей технологию MPI, должна быть выполнена команда include 'mpif.h' или include "mpi.h" (для языков Фортран и Си, соответственно). С помощью неё мы включаем в программу базовый файл с описанием интерфейса MPI.Затем исполняемый файл нужно будет запустить на требуемом количестве процессоров. Для этого обычно используется команда mpirun, задающая подключение MPI-приложения: mpirun –np N {программа с аргументами}, где N – число процессов, допустимое в данной системе для решения одной задачи.Теперь одна и та же запущенная программа будет выполняться сразу же всеми действующими на компьютере процессами.Отметим, что все объекты в MPI, такие как процедуры, константы и другие типы данных, в своих названиях имеют специальный префикс MPI_.Программа с использованием технологии MPI представляет собой множество параллельных, взаимодействующих между собой процессов. Каждый такой процесс порождается только один раз и образует составляющую часть целой программы. Причём во время выполнения всей параллельной программы недопустимо создание новых дополнительных процессов или же уничтожение уже существующих. Каждый процесс выполняется в своём выделенном пространстве, и никаких общих данных и переменных у них нет. Для дальнейшего обмена данными между ними будет осуществляться пересылка сообщений.Также у MPI предусмотрена возможность для локализации некоторых взаимодействующих параллельных процессов. Для этого можно создавать отдельные группы процессов, предоставляя им собственную среду для обмена сообщениями, называемую коммуникатором. При этом в зависимости от целей решаемых задач некоторые группы могут полностью совпадать или же, напротив, не иметь никаких общих процессов, а также либо включаться одна в другую, либо частично пересекаться.

Заключение

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

Список литературы
1. Модели взаимодействия процессов // URL: http://staff.mmcs.sfedu.ru/~dubrov/files/tut_parallel_02_model.pdf (дата обращения: 24.05.2022).2. Модели параллельного программирования // URL: https://vuzlit.com/1041823/modeli_parallelnogo_programmirovaniya (дата обращения: 24.05.2022).3. Модели параллельного программирования // URL: https://pandia.ru/text/78/413/26219.php (дата обращения: 24.05.2022).4. Основы параллельного программирования // URL: http://hpc-education.ru/files/lectures/gergel/ch_4.pdf (дата обращения: 24.05.2022).5. Параллельное программирование // URL: https://spravochnick.ru/programmirovanie/parallelnoe_programmirovanie/ (дата обращения: 24.05.2022).