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

ВВЕДЕНИЕ

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

В данной курсовой работе необходимо изучить работу параллельных вычислений с помощью таких технологий, как 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