Исследование эффективности параллельных вычислений

ВВЕДЕНИЕ

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

В данной курсовой работе необходимо изучить работу параллельных вычислений с помощью таких технологий, как std::thread, TBB, MPI.

Библиотека std::thread предоставляет стандартный способ управления потоками. Данная технология впервые была добавлена в стандарт С++11. std::thread представляют собой объекты в процессе С++, которые действуют как дескрипторы для лежащих в их основе программных потоков. Некоторые объекты std::thread представляют "нулевые" дескрипторы, т.е. не соответствуют программным потокам, поскольку находятся в состоянии, сконструированном по умолчанию (следовательно, без выполняемой функции); потоки, из которых выполнено перемещение (после перемещения объект std::thread, в который оно произошло, действует как дескриптор для соответствующего программного потока); потоки, у которых выполняемая ими функция завершена; а также потоки, у которых разорвана связь между ними и обслуживающими их программными потоками. API std::thrеаd не предлагает способа непосредственного получения возвращаемых значений из асинхронно выполняемых функций, и, если такие функции генерируют исключения, программа завершается.

Intel Threading Building Blocks (также известная как TBB) — кроссплатформенная библиотека шаблонов C++, разработанная компанией Intel для параллельного программирования. Библиотека содержит алгоритмы и структуры данных, позволяющие программисту избежать многих сложностей, возникающих при использовании традиционных реализаций потоков, таких как POSIX Threads, Windows threads или Boost Threads, в которых создаются отдельные потоки исполнения, синхронизируемые и останавливаемые вручную. Библиотека TBB абстрагирует доступ к отдельным потокам. Все операции трактуются как «задачи», которые динамически распределяются между ядрами процессора. Кроме того, достигается эффективное использование кэша. Программа, написанная с использованием TBB, создаёт, синхронизирует и разрешает графы зависимостей задач в соответствии с алгоритмом. Затем задачи исполняются в соответствии с зависимостями. Этот подход позволяет программировать параллельные алгоритмы на высоком уровне, абстрагируясь от деталей архитектуры конкретной машины.

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

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

1 Постановка задачи

Дана перестановка чисел от 1 до n. Определите, существуют ли такие два целых числа a и b (1 ≤ a, b ≤ n; a ≠ b), что число (a+b)/2 находится между a и b в заданной перестановке. Вывести все такие пары чисел.

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

Целью курсовой работы является приобретение навыков работы с системами параллельных вычислений. 

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ 4

1 Постановка задачи 6

2 Анализ и описание последовательного метода 7

3 Общее описание архитектуры параллельной вычислительной системы 8

4 Общее описание параллельной программы 9

5 Результаты теоретического анализа эффективности 10

6 Описание последовательной и параллельных программ 12

7 Описание выполненных вычислительных экспериментов 20

ЗАКЛЮЧЕНИЕ 24

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 25

ПРИЛОЖЕНИЕ А 26

ПРИЛОЖЕНИЕ Б 27

ПРИЛОЖЕНИЕ В 28

ПРИЛОЖЕНИЕ Г 29

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

1. Борзунов С. В., Практикум по параллельному программированию: учеб. пособие / С. В. Борзунов, С. Д. Кургалин, А. В. Флегель. — СПб.: БХВ, 2017. — 236 с.

2. Жалнин Р. В., Панюшкина Е. Н., Пескова Е. Е., Шаманаев П. А., Основы параллельного программирования с использованием технологий MPI и OpenMP: учебное пособие / Р.В. Жалнин, Е.Н. Панюшкина, Е. Е. Пескова, П.А. Шаманаев. – Саранск: Изд-во СВМО, 2013. – 78 с.

3. Богачёв К. Ю., Основы параллельного программирования: учебное пособие / К. Ю. Богачёв. 2-е изд. (эл.). М. : БИНОМ. Лаборатория знаний, 2013. 342 с.

4. Мичаев Вос. «Pro TBB»: Учебное пособие. – М.: Изд-во Apress Беркли, Калифорния, 2019. – 807 с.

5. Волосова А.В., Параллельные методы и алгоритмы: учебное пособие/ А.В.Волосова. ‒ М.: МАДИ, Электронные текстовые и графические данные (5,35 Мбайт). 2020. – 176 с.

6. Шпаковский Г.И. Реализация параллельных вычислений: кластеры, многоядерные процесры, грид, квантовые компьютеры. – Минск, БГУ, 2010 г., 155 с.

7. [Электронный ресурс] Т.Ю. Лымарь, Оценка эффективности параллельных алгоритмов URL: https://foreva.susu.ru/courses/fpk_parallel/lectures/pp8.pdf