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

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

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

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

Метод решения

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

1. массив разбивается на две половины;

2. каждая половинка сортируется;

3. упорядоченные половины сливаются.

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

Параллельная схема

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

Анализ эффективности

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

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

Демонстрация

Оранжевый — неотсортированная часть.
Голубой — две отсортированные, но не слитые подчасти.
Зелёний — отсортированная часть.
Серый — часть переданная для сортировки другому процессу.

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

Тестирование реализованных последовательной и параллельной версий алгоритма проводилось на следующей машине: AMD Athlon 64 X2 Dual Core Processor 4200+ 2,21 ГГц; 2,0 ГБ ОЗУ

Время работы

	последовательный	2 процесса	4 процесса
10^5	0,040	0,029	0,033
10^6	0,422	0,316	0,351
10^7	4,734	3,536	3,949

Ускорение

	2 процесса	2 процесса (теоритически)	4 процесса	4 процесса (теоритически)
10^5	1,33	1,36	1,19	1,60
10^6	1,35	1,40	1,20	1,75
10^7	1,39	1,42	1,24	1,10

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

Об авторе

Виктор Рамин (группа 8409)