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

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


• Выполнить реализацию разработанного алгоритма и построить все необходимые теоретические оценки сложности метода.


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

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

• Последовательная версия сортировки слиянием
  
  

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

     Для решения задачи сортировки эти три этапа выглядят так:

  1. Сортируемый массив разбивается на две части примерно одинакового размера;
  2. Каждая из получившихся частей сортируется отдельно, например — тем же самым алгоритмом;
  3. Два упорядоченных массива половинного размера соединяются в один.
  
  

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




• Параллельная версия сортировки слиянием
  
  

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

  1. Исходный массив разбивается на блоки длины n/p, где p – количество процессов. Каждый процесс получает свой блок и сортирует его как описанным выше способом;
  2. Далее запускается метод чёт-нечётной перестановки, при котором соседние процессы обмениваются своими упорядоченными блоками и сливают их таким образом, что на процессе i содержатся меньшие элементы двух блоков, а на процессе i+1 - большие элементы
  3. Каждый из процессов передаёт свой подмассив нулевому процессу, на котором формируется выходной отсортированный массив.
  
  

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

  Определим трудоёмкость последовательного алгоритма. Количество сравнений при слиянии массива из n элементов равно n. Количество уровней рекурсии равно log₂n. Таким образом, время выполнения последовательной задачи:

T₁ = n*log₂n

  Определим сложность параллельного алгоритма. Каждый процесс производит сортировку слиянием блока размером n/p, где n - количество элементов массива, p - количество процессов. Получаем оценку:

t₁ = (n/p)*log₂(n/p)

Количество сравнений при одной итерации чёт-нечётной перестановки равно n, число таких итераций равно p. Трудоёмкость чёт-нечётной перестановки:

t₂ = p*(n/p)=n

  Общее время всех выполняемых в ходе сортировки операций передачи блоков можно оценить при помощи соотношения:

T_p(comm)=p(a+w(n/p)/b),

  где a - латентность, b - пропускная способность сети передачи данных, w - размер элемента упорядочиваемых данных в байтах.

  Время выполнения параллельного алгоритма сортировки слиянием определяется суммой

T_p = T_p(comm)+ t₁ + t₂,

T_p = p(a+w(n/p)/b)+t((n/p)*log₂(n/p) + n)

Общая оценка показателя ускорения равна:

S_p = n*log₂n  /  [p(a+w(n/p)/b)+t((n/p)*log₂(n/p) + n)]   

Оценка эффективности:

E_p = n*log₂n  /  p[p(a+w(n/p)/b)+t((n/p)*log₂(n/p) + n)]

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

Тестовая инфраструктура

Процессор - Intel Core 2 CPU 6320 1.86 GHz
Оперативная память - 1 GB
Операционная система - MS Windows XP
Компилятор - MS Visual Studio 2008
Размер элемента набора - 4 байта
Время выполнения базовой операции перестановки - 14 нс
Скорость обмена между процессами - 996103643 байт/c

Об авторе

Работу выполнила студентка группы 8409 Короткова Н.О.