Файл: Курсовая Выполнить быструю сортировку (quicksort) массива, используя парадигмы программирования OpenMP и MPI..docx

Выполните быструю сортировку (quicksort) массива, содержащего N (Nmin=105) сгенерированных случайным образом элементов (от -1000 до 1000), используя парадигмы программирования OpenMP и MPI. Для визуализации процесса используйте библиотеку G2. Изобразите график зависимости времени сортировки массива от числа потоков. Вычислите ускорение и эффективность параллельного алгоритма по сравнению с последовательным в зависимости от длины массива и количества потоков.

Теоретическая часть

Дан массив, содержащий N (Nmin=105) сгенерированных случайным образом элементов (от -1000 до 1000). Требуется выполнить быструю сортировку(quicksort) массива.

Рассмотрим алгоритм быстрой сортировки (quicksort)

Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем обменов при упорядочении n элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками.

Быстрая сортировка использует стратегию «разделяй и властвуй». Шаги алгоритма таковы:

Выбираем в массиве некоторый элемент, который будем называть опорным элементом. Для корректности алгоритма значение этого элемента должно быть между максимальным и минимальным значениями в массиве (включительно). С точки зрения повышения эффективности алгоритма выгоднее всего выбирать медиану; но без дополнительных сведений о сортируемых данных её обычно невозможно получить. Известные стратегии: выбирать постоянно один и тот же элемент, например, средний или последний по положению; выбирать элемент со случайно выбранным индексом. Часто хороший результат даёт выбор в качестве опорного элемента среднего арифметического между минимальным и максимальным элементами массива, особенно для целых чисел (в этом случае опорный элемент не обязан быть элементом сортируемого массива).
Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы со значением меньшим или равным опорному элементу, оказались слева от него, а все элементы, превышающие по значению опорный — справа от него. Обычный алгоритм операции:

Два индекса — l и r, приравниваются к минимальному и максимальному индексу разделяемого массива, соответственно.
Вычисляется значение опорного элемента m по одной из стратегий.
Индекс l последовательно увеличивается до тех пор, пока l-й элемент не окажется больше или равен опорному.
Индекс r последовательно уменьшается до тех пор, пока r-й элемент не окажется меньше или равен опорному.
Если r = l — найдена середина массива — операция разделения закончена, оба индекса указывают на опорный элемент.
Если l < r — найденную пару элементов нужно обменять местами и продолжить операцию разделения с тех значений l и r, которые были достигнуты. Следует учесть, что если какая-либо граница (l или r) дошла до опорного элемента, то при обмене значение m изменяется на r-й или l-й элемент соответственно, так же изменяется индекс опорного элемента и алгоритм продолжает своё выполнение.

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

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

Базовая схема

Кратко говоря, алгоритм выполнения поставленной задачи будет следующим:

В начале создаем в каждом процессе исходный массив из n/p частей и инициализируем их. Сортируем его алгоритмом быстрой сортировки.
Выбираем опорный элемент. В нашей реализации алгоритма мы выбираем в качестве опорного средний элемент ведущего процесса. Рассылаем этот элемент по всем остальным процессам. Выбираемый подобным образом, ведущий элемент в отдельных случаях может оказаться более близким к реальному среднему значению всего сортируемого набора, чем какое-либо другое произвольно выбранное значение.
Производим разделение данных каждого процесса на элементы, меньшие, либо равные значению опорного элемента и большие значения опорного.
Образуем пары процессов, для которых битовое представление номера отличается только в старшем бите (позиции N) и производим взаимообмен между этими процессами:

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

Таким образом на каждой итерации набор данных каждого процесса остаётся упорядоченным.

Парадигма программирования OpenMP

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

OpenMP реализует параллельные вычисления с помощью многопоточности, в которой «главный» (master) поток создает набор подчиненных (slave) потоков и задача распределяется между ними. Предполагается, что потоки выполняются параллельно на машине с несколькими процессорами (количество процессоров не обязательно должно быть больше или равно количеству потоков).

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

Ключевыми элементами OpenMP являются

 конструкции для создания потоков (директива parallel),

 конструкции распределения работы между потоками (директивы DO/for и section ),

 конструкции для управления работой с данными (выражения shared и private для определения класса памяти переменных),

 конструкции для синхронизации потоков (директивы critical, atomic и barrier),

 процедуры библиотеки поддержки времени выполнения (например, omp_get_thread_num),

 переменные окружения (например, OMP_NUM_THREADS).

Трансляция и выполнение OpenMP-программ

Трансляция OpenMP- программы выполняется со специальным ключом. В дистрибутиве PelicanHPC использует ключ -fopenmp, например:

mpicc –fopenmp source.c -o program

где program – желаемое имя исполняемого файла программы, source.c – имя файла с исходным кодом программы.

Программа запускается командой: ./program [ключи и аргументы программы] где program – имя исполняемого файла программы..

Парадигма программирования MPI

MPI – программный интерфейс для передачи сообщений между процессами. Стандартизацией MPI занимается организация MPI Forum. Реализации интерфейса MPI существуют для множества различных платформ. В рамках технологии MPI на каждом вычислительном узле запускается копия параллельной программы. Каждая копия получает ранг – уникальный идентификатор, использующийся для адресации сообщений. Обмен сообщениями в рамках MPI происходит между процессами, которые относятся к одному коммуникатору. Коммуникатор – это способ группировки процессов. По умолчанию все запущенные процессы попадают в коммуникатор MPI_COMM_WORLD.

MPI предусматривает несколько вариантов обмена сообщениями. Сообщения бывают типа «точка-точка» – между двумя процессами, и «коллективные» – между несколькими процессами одновременно.

Трансляция и выполнение MPI-программ

Для трансляции и компоновки программ на языке C++ используется команда mpiCC, для трансляции программ на языке C – команда mpicc. Пример применения команды:

mpicc –o program source.c

где program – желаемое имя исполняемого файла программы, source.c – имя файла с исходным кодом программы.

Для выполнения MPI-программ используется загрузчик приложений mpirun. Он запускает указанное количество копий программы. Команда запуска:

mpirun –np X [ключи MPI] program [ключи и аргументы программы]

где X – число запускаемых процессов, program – имя исполняемого файла программы.

Например, после развёртывания кластера PelicanHPC, строка запуска программы может выглядеть так:

mpirun –np 10 --hostfile /home/user/tmp/bhosts program

т.е. будет запущено 10 процессов программы program, IP-адреса вычислительных узлов кластера будут получены из файла bhosts, до которого указан полный путь.