Новости
О Центре
Кластер
Обучение
Основной курс по параллельному программированию
Учебные курсы
Магистратура
Дополнительное образование
Работы студентов
Библиотека
Исследования
Конференции
Полезные ссылки
NVIDIA
Контакты
О сайте
Имя:
Пароль:
запомнить:
Забыли пароль? Регистрация

Введение

Упорядочевание - один из важнейших и ключевых моментов при работе с информацией.
Известные алгоритмы сортировки данных, расположенных в оперативной памяти, чрезвычайно разнообразны. По словам Н. Вирта, "создается впечатление, что можно построить целый курс программирования, выбирая примеры только из задач сортировки". Интересен этот класс алгоритмов еще и тем, что на нем наглядно демонстрируются богатейшие возможности программирования: насколько разными путями можно прийти к одной цели - получению упорядоченной таблицы! На множестве алгоритмов сортировки становится понятной необходимость оценки качества алгоритма, критериями которого являются экономия памяти и увеличение быстродействия.

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

Требуется разработать алгоритм параллельной сортировки слиянием, а так же разработать программный комплекс реализующий этот алгоритм средствами 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

80000100/94382,1412,631 532,0321,886
160000204/111742,1832,128 652,0822,423
320000394/2311382,2172,266 1652,1841,893
640000751/4532932,2942,054 2702,1902,229

Как видно из таблицы, результаты практических испытаний незначительно отличаются от теоретических оценок.

Литература

1) Дональд Э. Кнут
Искусство программирования. Том 3. Сортировка и поиск

2)http://ru.wikipedia.org

3)http://www.ipkro.isu.ru/informat/methods/findsort/sort.htm

Новости

22.10.2012
04.09.2012
05.04.2012
06.03.2012
02.03.2012