Упорядочевание - один из важнейших и ключевых моментов при работе с информацией.
Известные алгоритмы сортировки данных, расположенных в оперативной памяти, чрезвычайно разнообразны.
По словам Н. Вирта, "создается впечатление, что можно построить целый курс программирования, выбирая примеры только из задач сортировки". Интересен этот класс алгоритмов еще и тем, что на нем наглядно демонстрируются богатейшие возможности программирования: насколько разными путями можно прийти к одной цели - получению упорядоченной таблицы! На множестве алгоритмов сортировки становится понятной необходимость оценки качества алгоритма, критериями которого являются экономия памяти и увеличение быстродействия.
Постановка задачи.
Требуется разработать алгоритм параллельной сортировки слиянием, а так же разработать программный комплекс реализующий этот алгоритм средствами MPI, и произвести необходимые теоретические оценки сложности алгоритма. Провести ряд экспириментов, получить оценки производительности по сравнению с последовательным алгоритмом.
Метод решения
Последовательный алгоритм:
|
1)Сортируемый массив разбивается на несколько частей примерно одинакового размера;
2)Каждая из получившихся частей сортируется отдельно, например — тем же самым алгоритмом;
3)Два упорядоченных массива половинного размера соединяются в один.
|
Параллельная версия:
Для удобства будем рассматривать топологию типа гиперкуб.
1) Исходные данные (предполагаем массив) разбиваем на части равные по размеру n/p, где n - кол-во элементов, p - кол-во процессов. И рассылаются процессам.
2) На каждом процессе полученные даннные сортируются, например последовательным методом сортировки слиянием.
3) На каждой итерации (log2(p) раз) процесс с номером id - (1 ≪ i) (где id номер текущего процесса, i-номер итерации) получает от процесса с номером id + (1 ≪ i) данные, и сливает их со своими
После завершения алгоритма, процесс с номером p-1, будет содержать весь отсортированные массив.
Теоретическая оценка сложности
В многих источниках рассматривается теоретическая сложность алгоритма сортировкии (например [1]) она равна:
О(n*log2(n)).
Соответственно на каждом процессе сложность будет:
t1 = (n/p)*log2(n/p)
Определим трудоёмкость метода при слиянии массивов из процессов. Число итераций равно 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 Atom N550@1.55 GHz, 2Gb RAM@1066MHz под управлением Windows 7 Professional N 32-bit.
В таблице представлены результаты экспериментов, где T - время выполнения, S* - теоретическая оценка ускорения, S - экспериментальное ускорение.
Размер массива |
Последоваетльный алгоритм / Параллельный алгоритм в один
процесс, мс |
Параллельный алгоритм |
2 процесса |
4 процесса |
T |
S* |
S |
T |
S* |
S |
80000 | 100/94 | 38 | 2,141 | 2,631 |
53 | 2,032 | 1,886 |
160000 | 204/111 | 74 | 2,183 | 2,128 |
65 | 2,082 | 2,423 |
320000 | 394/231 | 138 | 2,217 | 2,266 |
165 | 2,184 | 1,893 |
640000 | 751/453 | 293 | 2,294 | 2,054 |
270 | 2,190 | 2,229 |
Как видно из таблицы, результаты практических испытаний незначительно отличаются от теоретических оценок.
Литература
1) Дональд Э. Кнут
Искусство программирования. Том 3. Сортировка и поиск
2)http://ru.wikipedia.org
3)http://www.ipkro.isu.ru/informat/methods/findsort/sort.htm