97
правок
Изменения
Многопоточная сортировка слиянием
== Многопоточная сортировка слиянием ==
Благодаря тому, что сортировка слиянием построена на принципе "Разделяй и властвуй", выполнение данного алгоритма можно весьма эффективно распараллелить. Теоретически можно достичь много лучшей асимптотики, однако на практике из-за огранечений по количеству потоков, которые могут выполняться независимо друг от друга, вычислительная сложность уменьшается на константу.
===Алгоритм со слиянием за <math>\Omega(n)</math>===
Внесем в алгоритм сортировки слиянием следующую модификацию: будем сортировать левую и правую части массива параллельно.
mergeSortMT(array, left, right):
mid = (left + right) / 2
'''spawn''' mergeSortMT(array, left, mid)
mergeSortMT(array, mid + 1, right)
'''sync'''
merge(array, left, mid, right)
В данном алгоритме оператор '''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 слияние двух массивов].
Несмотря на наличие двух рекурсивных вызовов, при оценке будем считать, что совершается один вызов, т.к. оба вызова выполняются параллельно с одинаковой асимптотикой. Оценим время работы данного алгоритма: <math>T(n) = T(n / 2) + \Omega(n) = \Omega(n)</math>. Данная асимптотика достигается при возможности запускать неограниченное количество потоков независимо друг от друга.
На практике на однопроцессорных компьютерах имеет смысл запускать алгоритм, ограничив количество допустимое количество потоков. Изменим код в соответствии с этими требованиями:
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>\Omega((n / maxThreads) * \log((n / maxThreads)))</math>.
===Алгоритм с многопоточным слиянием===
Как видно из оценки первого алгоритма, слияние выполняется слишком долго при том, что существует возможность его ускорить. Рассмотрим алгоритм рекурсивного слияния массивов <math>T[left1 \dots right1]</math> и <math>T[left2 \dots right2]</math> в массив <math>A[left3 \dots right3]</math>:
# Убедимся, что размер <math>T[left1 \dots right1]</math> больше либо равен размеру <math>T[left2 \dots right2]</math>
# Найдем <math>x = T[mid1]</math> - середину первого массива (<math>x</math> также является и медианой этого массива)
# При помощи бинарного поиска найдем <math>mid2</math> такое, что <math>\forall y \in T[left2 \dots mid2 - 1]: y < x</math>
# <math>mid3 = left3 + (mid1 - left1) + (mid2 - left2)</math>
# <math>A[mid3] = x</math>
# Сольем <math>T[right1 \dots mid1 - 1]</math> и <math>T[rigth2 \dots mid2]</math> в <math>A[right3 \dots mid3 - 1]</math>
# Сольем <math>T[mid1 + 1 \dots right1]</math> и <math>T[mid2 \dots right2]</math> в <math>A[mid3 + 1 \dots right3]</math>
Приведем псевдокод данного алгоритма:
// если <math>right <= left</math> возвращает <math>left</math>
// если <math>x <= T[left]</math>, возвращает <math>left</math>
// иначе возвращает наибольший индекс <math>i</math> из отрезка <math>[left; right]</math> такой, что <math>array[i - 1] < x</math>
binarySearch(x, array, left, right)
// слияние <math>T[left1 \dots right1]</math> и <math>T[left2 \dots right2]</math> в <math>A[left3 \dots right1 - left1 + right2 - left2]</math>
mergeMT(T, left1, right1, left2, right2, A, left3):
n1 = right1 - left1 + 1
n2 = right2 - left2 + 1
if n1 < n2:
swap(left1, left2)
swap(right1, right2)
swap(n1, n2)
if n1 == 0:
return
else
mid1 = (left1 + right1) / 2
mid2 = binarySearch(T[mid1], T, left2, right2)
mid3 = left3 + (mid1 - left1) + (mid2 - left2)
A[mid3] = T[mid1]
'''spawn''' mergeMT(T, left1, mid1 - 1, left2, mid2 - 1, A, left3)
mergeMT(T, mid1 + 1, right1, mid2, right2, A, mid3 + 1)
'''sync'''
Благодаря тому, что сортировка слиянием построена на принципе "Разделяй и властвуй", выполнение данного алгоритма можно весьма эффективно распараллелить. Теоретически можно достичь много лучшей асимптотики, однако на практике из-за огранечений по количеству потоков, которые могут выполняться независимо друг от друга, вычислительная сложность уменьшается на константу.
===Алгоритм со слиянием за <math>\Omega(n)</math>===
Внесем в алгоритм сортировки слиянием следующую модификацию: будем сортировать левую и правую части массива параллельно.
mergeSortMT(array, left, right):
mid = (left + right) / 2
'''spawn''' mergeSortMT(array, left, mid)
mergeSortMT(array, mid + 1, right)
'''sync'''
merge(array, left, mid, right)
В данном алгоритме оператор '''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 слияние двух массивов].
Несмотря на наличие двух рекурсивных вызовов, при оценке будем считать, что совершается один вызов, т.к. оба вызова выполняются параллельно с одинаковой асимптотикой. Оценим время работы данного алгоритма: <math>T(n) = T(n / 2) + \Omega(n) = \Omega(n)</math>. Данная асимптотика достигается при возможности запускать неограниченное количество потоков независимо друг от друга.
На практике на однопроцессорных компьютерах имеет смысл запускать алгоритм, ограничив количество допустимое количество потоков. Изменим код в соответствии с этими требованиями:
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>\Omega((n / maxThreads) * \log((n / maxThreads)))</math>.
===Алгоритм с многопоточным слиянием===
Как видно из оценки первого алгоритма, слияние выполняется слишком долго при том, что существует возможность его ускорить. Рассмотрим алгоритм рекурсивного слияния массивов <math>T[left1 \dots right1]</math> и <math>T[left2 \dots right2]</math> в массив <math>A[left3 \dots right3]</math>:
# Убедимся, что размер <math>T[left1 \dots right1]</math> больше либо равен размеру <math>T[left2 \dots right2]</math>
# Найдем <math>x = T[mid1]</math> - середину первого массива (<math>x</math> также является и медианой этого массива)
# При помощи бинарного поиска найдем <math>mid2</math> такое, что <math>\forall y \in T[left2 \dots mid2 - 1]: y < x</math>
# <math>mid3 = left3 + (mid1 - left1) + (mid2 - left2)</math>
# <math>A[mid3] = x</math>
# Сольем <math>T[right1 \dots mid1 - 1]</math> и <math>T[rigth2 \dots mid2]</math> в <math>A[right3 \dots mid3 - 1]</math>
# Сольем <math>T[mid1 + 1 \dots right1]</math> и <math>T[mid2 \dots right2]</math> в <math>A[mid3 + 1 \dots right3]</math>
Приведем псевдокод данного алгоритма:
// если <math>right <= left</math> возвращает <math>left</math>
// если <math>x <= T[left]</math>, возвращает <math>left</math>
// иначе возвращает наибольший индекс <math>i</math> из отрезка <math>[left; right]</math> такой, что <math>array[i - 1] < x</math>
binarySearch(x, array, left, right)
// слияние <math>T[left1 \dots right1]</math> и <math>T[left2 \dots right2]</math> в <math>A[left3 \dots right1 - left1 + right2 - left2]</math>
mergeMT(T, left1, right1, left2, right2, A, left3):
n1 = right1 - left1 + 1
n2 = right2 - left2 + 1
if n1 < n2:
swap(left1, left2)
swap(right1, right2)
swap(n1, n2)
if n1 == 0:
return
else
mid1 = (left1 + right1) / 2
mid2 = binarySearch(T[mid1], T, left2, right2)
mid3 = left3 + (mid1 - left1) + (mid2 - left2)
A[mid3] = T[mid1]
'''spawn''' mergeMT(T, left1, mid1 - 1, left2, mid2 - 1, A, left3)
mergeMT(T, mid1 + 1, right1, mid2, right2, A, mid3 + 1)
'''sync'''
