Пусть
есть последовательность a0, a1... an и функция сравнения, которая на любых двух
элементах последовательности принимает одно из трех значений: меньше, больше
или равно. Задача сортировки состоит в перестановке членов последовательности
таким образом, чтобы выполнялось условие: ai <= ai+1, для всех i от 0 до n.
Постановка задачи
Требуется
упорядочить заданный массив чисел из N элементов в порядке возрастания, с
помощью сортировки слиянием. На основе
последовательного алгоритма требуется разработать параллельный вариант.. Время
выполнения параллельной программы сравнить со временем выполнения
последовательной программы и привести оценки сложности для алгоритмов.
Метод реализации
Сортировка
слиянием - пример использования принципа
«разделяй и властвуй». Сначала задача разбивается на несколько подзадач
меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или
непосредственно, если их размер достаточно мал. Наконец, их решения
комбинируются, и получается решение исходной задачи.
Для
решения задачи сортировки эти три этапа выглядят так:
1.
Сортируемый
массив разбивается на несколько частей примерно одинакового размера;
2.
Каждая
из получившихся частей сортируется отдельно, например — тем же самым
алгоритмом;
3.
Два
упорядоченных массива половинного размера соединяются в один.Рекурсивное
разбиение задачи на меньшие происходит до тех пор, пока размер массива не
достигнет единицы (любой массив длины 1 можно считать упорядоченным).
Нетривиальным
этапом является соединение двух упорядоченных массивов в один.
Основная
идея решения состоит в попарном сравнении очередных элементов каждого
фрагмента, выяснении, какой из элементов меньше, переносе его во
вспомогательный массив D (для простоты) и продвижении по тому фрагменту
массива, из которого взят элемент. При этом следует не забыть записать в D
оставшуюся часть того фрагмента, который не успел себя "исчерпать".
Пример
работы алгоритма на массиве 3 7 8 2 4 6 1 5
void merge (double* a, int n1, int n2)
{
int m = (n1
+ n2) / 2;
if (n1 ==
n2)
return;
else
{
merge
(a, n1, m);
merge
(a, m+1, n2);
bond (a, n1, m, n2);
}
}
Параллельная реализация
1.
Сначала выполняется передача, разбиение массива
элементов по всем процессам. Каждый процесс параллельно сортирует свой массив
последовательным алгоритмом.
2.
Теперь сливаем эти отсортированные массивы в
один результирующий. Слияние будет проводиться итерационно: на первом шаге
процессы делятся на пары, и правый массив передаёт свои данные левому. Тот
процесс сортирует их, используя функцию bond. На втором шаге также объединяем
процессы в пары, но только те, которые были левыми на первом шаге. Опять,
также, правый процесс передаёт свои данные левому, а тот их сортирует. Это
выполняется до тех пор, пока не останется один процесс. Его массив и будет
результатом параллельной сортировки.
Анализ эффективности
Определим трудоёмкость последовательного алгоритма. Количество сравнений
при слиянии массива из n элементов равно n. Количество уровней рекурсии равно
log2n. Таким образом, время выполнения последовательной задачи:
T1 = n*log2n
Определим трудоёмкость метода при слиянии
массивов из процессов. Число итераций равно p-1, а в каждой итерации число
перестановок равно отношению количества элементов в изначальном массиве n к
используемому количеству процессов на данной итерации.
На первом шаге их p, на втором p/2 и т.д.
То есть трудоёмкость t2 равна
t2 = n/p + 2*n/p + ... + n = n*(2p-1)/p
Общее время всех выполняемых в ходе
сортировки операций передачи блоков можно оценить при помощи соотношения:
Tp(comm)=p(a+w(n/p)/b), где a -
латентность, b - пропускная способность сети передачи данных, w - размер
элемента упорядочиваемых данных в байтах.
Окончательная оценка алгоритма Tp равна:
Tp=Tp(comm)+t1+t2=p(a+w(n/p)/b) + (n/p)*log2(n/p) +
n*(2p-1)/p
Общая оценка показателя ускорения равна:
Sp = n*log2n / [p(a+w(n/p)/b) + (n/p)*log2(n/p) +
n*(2p-1)/p]
Оценка эффективности:
Ep = n*log2n / p*[p(a+w(n/p)/b) + (n/p)*log2(n/p) +
n*(2p-1)/p]
Результаты вычислительных экспериментов
Вычислительные
эксперименты для оценки эффективности параллельного алгоритма сортировки
слиянием проводились при следующих условиях и оборудовании:Вычислительные
эксперименты для оценки эффективности параллельного алгоритма сортировки
слиянием проводились при следующих условиях и оборудовании:
Процессор
- Intel Core 2 Duo E6550, 2.33 ГГц
Оперативная
память - 4 GB
Операционная
система - Microsoft Windows 7 Enterprise
Компилятор
- MS Visual Studio 2008
Длительность
τ базовой скалярной операции - 14 нс
Параметры
передачи между процессами на одной машине: латентность α - 48,445 млс,
пропускная способность β - 985123443 байт/c
w = 4
байта
Tp*-практическое
время выполнения алгоритма в секундах
Tp-теоретическое
время выполнения алгоритма в секундах
Sp-практический
показатель ускорения
Результаты
практических испытаний незначительно отличаются от теоретических оценок.
