Задания по курсу "Параллельное программирование", МФТИ ФРКТ, 2024

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

Введение

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

Рассмотрим некоторый последовательный алгоритм решения какой-либо задачи. В нем есть как операции, которые не могут выполняться параллельно (например, ввод/вывод), так и операции, которые можно выполнять на нескольких исполнителях одновременно. Пусть доля последовательных операций в алгоритме равна $\alpha$.

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

$$T_{p}=\alpha*T_{1} + \frac{(1-\alpha)*T_{1}}{p}$$

Ускорением параллельного алгоритма называют отношение времени выполнения лучшего последовательного алгоритмам к времени выполнения параллельного алгоритма:

$$S=\frac{T_{1}}{T_{p}}$$

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

$$E=\frac{S}{p}$$

Теоретическую оценку максимального ускорения, достижимого для параллельного алгоритма с долей последовательных операций равной α определяется законом Амдала:

$$S<=\frac{1}{\alpha}$$

MPI

Для решения задач используется MPI ( Message Passing Interface ). MPI это стандартизованный механизм для построения параллельных программ в модели обмена сообщениями. Стандарт разрабатывается объединением MPI Forum.

MPI предоставляет следующие возможности:

• Обеспечение удобной абстракции над протоколами сетевого взаимодействия
• Логическая организация кластера, а именно организация виртуальной топологичсекой сети поверх физических протоколов
• Функции синхронизации и коммуникации для параллельных операций
• Кроссплатформенная реализация стандарта
• Биндинги в разные языки программирования
• Ориентированность на слабосвязанный MIMD, однако MPI пригоден для сильносвязанного MIM при организации многопроцессности
• Новые версии стандарта поддерживают гибридные архитектуры с общей памятью

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

Перед запуском проектов для сборки необходимо установить toolchain MPI.

Библиотека поддержки параллелизма (начиная с C++11)

C++ включает встроенную поддержку потоков, атомарных операций, взаимного исключения, условных переменных и фьючерсов

• Потоки: позволяют программам выполняться на нескольких ядрах процессора.
• Алгоритмы взаимного исключения: предотвращают одновременный доступ нескольких потоков к общим ресурсам. Это предотвращает гонки данных и обеспечивает поддержку синхронизации между потоками.
• Семафоры: упрощенныe примитивы синхронизации, используемыe для ограничения одновременного доступа к общему ресурсу.

OpenMP

OpenMP (Open Multi-Processing) — это стандарт, определяющий набор директив компилятора, библиотечных процедур и переменных среды окружения для создания многопоточных программ использующих общую память. Стандарт предусматривает использование OpenMP для алгоритмических языков C/C++ и Fortran.

Проекты

1. Метод глобального стека для параллельного вычисления интеграла с использованием std::thread.
2. Поиск всех подпалиндромов в заданной строке с использование OpenMP.
3. Распараллеливание циклов с зависимостями с использованием OpenMP и MPI.
4. Численное решение уравнения переноса с помощью технологии MPI.
5. Ускорение подсчёта числа Pi с помощью технологии MPI.
6. Измерение задержки передачи сообщений между двумя узлами сети с помощью технологии MPI.
7. Базовый пример использования MPI.