Изменения

Перейти к: навигация, поиск

Обсуждение участника:AKhimulya

566 байт убрано, 01:01, 3 июня 2014
Нет описания правки
== Многопоточная сортировка слиянием ==
 Благодаря тому, что сортировка слиянием построена на принципе "Разделяй и властвуй", выполнение данного алгоритма можно весьма эффективно распараллелить. При оценке асимптотики допускается, что возможен запуск неограниченного количества независимых процессов, что на практике не достижимо. Более того, при реализации имеет смысл ограничить количество параллельных потоков.
===Сортировка с однопоточным слиянием===
Внесем в алгоритм сортировки слиянием следующую модификацию: будем сортировать левую и правую части массива параллельно.
В данном алгоритме оператор '''spawn''' запускает новый поток, а оператор '''sync''' ожидает завершения этого потока. Функция merge аналогична функции merge из раздела [http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D1%81%D0%BB%D0%B8%D1%8F%D0%BD%D0%B8%D0%B5%D0%BC#.D0.A1.D0.BB.D0.B8.D1.8F.D0.BD.D0.B8.D0.B5_.D0.B4.D0.B2.D1.83.D1.85_.D0.BC.D0.B0.D1.81.D1.81.D0.B8.D0.B2.D0.BE.D0.B2 слияние двух массивов].<br>
Несмотря на наличие двух рекурсивных вызовов, при оценке будем считать, что совершается один вызов, т.к. оба вызова выполняются параллельно с одинаковой асимптотикой. Оценим время работы данного алгоритма: <math>T(n) = T(n / 2) + \Theta(n) = \Theta(n)</math>. Данная асимптотика достигается при возможности запускать неограниченное количество потоков независимо друг от друга.<br>
На практике на однопроцессорных компьютерах имеет смысл запускать алгоритм, ограничив количество допустимое количество потоков. Изменим код в соответствии с этими требованиями:
 
mergeSortMTBounded(array, left, right):
mid = (left + right) / 2
if threadCount <math><</math> maxThreads:
threadCount++
'''spawn''' mergeSortMTBounded(array, left, mid)
else:
mergeSortMTBounded(array, left, mid)
mergeSortMTBounded(array, mid + 1, right)
if threadCount <math>\leqslant</math> maxThreads:
'''sync'''
threadCount--
merge(array, left, mid, right)
 
Где threadCount - глобальный счетчик, а maxThreads - ограничение по количеству потоков.
Данный алгоритм будет иметь асимптотику: <math>\Theta((n / maxThreads) * \log((n / maxThreads)))</math>.
===Многопоточное слияние===
Оценим данный алгоритм сверху при условии, что возможен запуск неограниченного количества независимых потоков. Из предыдущих пунктов <math>TmergeSort(n) = TmergeSort(n / 2) + Tmerge(n) = TmergeSort(n / 2) + \Theta(\log^2(n)) = \Theta(\log^3(n))</math>.
 
===Литература===
Cormen T.H., Leiserson C.E., Rivest R.L., Stein C. - Introduction to Algorithms, Third Edition
AKhimulya
97
правок
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/37517»

Навигация