Рассмотрим подробнее алгоритм сортировки слиянием. Его основная идея состоит в том, что массив разбивается на части, они сортируются отдельно, а затем, упорядоченные части сливаются. Эта сортировка — хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи. И так основные этапы алгоритма:

• массив разбивается на две части;
• каждая часть сортируется;
• упорядоченные части сливаются.

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

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

Попробуем добиться уменьшения времени сортировки за счет параллельности вычислений. За основу возьмем последовательный алгоритм слияния.

Итак, необходимо упорядочить массив чисел из n элементов (например в порядке возрастания), используя алгоритм сортировки слиянием. Затем, для увеличения производительности программы и уменьшения времени её работы требуется на основе последовательного алгоритма разработать параллельный.

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

Алгоритм сортировки с использованием регулярного набора образцов.

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

• на первом этапе сортировки производится упорядочивание имеющихся на процессорах блоков. Данная операция может быть выполнена каждым процессором независимо друг от друга при помощи обычного алгоритма быстрой сортировки ; далее каждый процессор формирует набор из элементов своих блоков с индексами
• на втором этапе выполнения алгоритма все сформированные на процессорах наборы данных собираются на одном из процессоров системы и объединяются в ходе последовательного слияния в одно упорядоченное множество. Далее из полученного множества значений из элементов с индексами
  

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

• на третьем этапе сортировки каждый процессор осуществляет рассылку выделенных ранее частей своего блока всем остальным процессорам системы; рассылка выполняется в соответствии с порядком нумерации – часть j, 0 ≤ j < p , каждого блока пересылается процессору с номером j ;
• на четвертом этапе выполнения алгоритма каждый процессор выполняет слияние p полученных частей в один отсортированный блок.

По завершении четвертого этапа исходный набор данных становится отсортированным.

Как известно сложность последовательной реализации слияния:

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

Оценим трудоемкость рассмотренного параллельного метода. Пусть, как и ранее, n есть количество сортируемых данных, p, p

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

где τ есть время выполнения базовой операции сортировки.

На втором этапе алгоритма один из процессоров собирает наборы из p элементов со всех остальных процессоров, выполняет слияние всех полученных данных (общее количество элементов составляет p2 ), формирует набор из p-1 ведущих элементов и рассылает полученный набор всем остальным процессорам. С учетом всех перечисленных действий общая длительность второго этапа составляет

(в приведенном соотношении выделенные подвыражения соответствуют четырем перечисленным действиям алгоритма); здесь, как и ранее, α – латентность, β – пропускная способность сети передачи данных, а w есть размер элемента упорядочиваемых данных в байтах.

В ходе выполнения третьего этапа алгоритма каждый процессор разделяет свои элементы относительно ведущих элементов на p частей (общее количество операций для этого может быть ограничено величиной n/p). Выполнение такой операции может быть осуществлено за log2 p шагов, на каждом из которых каждый процессор передает и получает сообщение из (n/p)/2 элементов. Как результат, общая трудоемкость третьего этапа алгоритма может быть оценена как

На четвертом этапе алгоритма каждый процессор выполняет слияние p отсортированных частей в один объединенный блок. Оценка трудоемкости такой операции уже проводилась при рассмотрении второго этапа, и, тем самым, длительность выполнения процедуры слияния составляет

С учетом всех полученных соотношений общее время выполнения алгоритма сортировки с использованием регулярного набора образцов составляет

Тестирование реализованных последовательной и параллельной версий алгоритма проводилось на следующей машине: 1.7GHz dual-core Intel Core i5 processor, 4GB memory.

Результаты вычислительных экспериментов для параллельного алгоритма сортировки с использованием регулярного набора образцов

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

Работу выполнили студенты группы №8409 Александр Петровичев и Гарнов Руслан