Многопоточная сортировка слиянием — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(initial)
 
 
(не показано 11 промежуточных версий 3 участников)
Строка 1: Строка 1:
 
== Многопоточная сортировка слиянием ==
 
== Многопоточная сортировка слиянием ==
Благодаря тому, что сортировка слиянием построена на принципе "Разделяй и властвуй", выполнение данного алгоритма можно весьма эффективно распараллелить. При оценке асимптотики допускается, что возможен запуск неограниченного количества независимых процессов, т.е. процессов с вычислительными ресурсами, не зависящими от других процессов, что на практике не достижимо. Более того, при реализации имеет смысл ограничить количество параллельных потоков.
+
Благодаря тому, что [[Сортировка слиянием | сортировка слиянием]] построена на принципе "Разделяй и властвуй", выполнение данного алгоритма можно весьма эффективно распараллелить. При оценке асимптотики допускается, что возможен запуск неограниченного количества независимых процессов, т.е. процессов с вычислительными ресурсами, не зависящими от других процессов, что на практике не достижимо. Более того, при реализации имеет смысл ограничить количество параллельных потоков.
 +
 
 
==Сортировка с однопоточным слиянием==
 
==Сортировка с однопоточным слиянием==
 
Внесем в алгоритм сортировки слиянием следующую модификацию: будем сортировать левую и правую части массива параллельно.
 
Внесем в алгоритм сортировки слиянием следующую модификацию: будем сортировать левую и правую части массива параллельно.
     function mergeSortMT(array, left, right):
+
     '''function''' mergeSortMT(array, left, right):
 
         mid = (left + right) / 2
 
         mid = (left + right) / 2
 
      
 
      
Строка 12: Строка 13:
 
         merge(array, left, mid, right)
 
         merge(array, left, mid, right)
  
В данном алгоритме оператор <tex>\mathrm {\bf {spawn}}</tex> запускает новый поток, а оператор <tex>\mathrm {\bf {sync}}</tex> ожидает завершения этого потока. Функция <tex>\mathrm {merge}</tex> аналогична одноименной функции из раздела [[Сортировка слиянием#.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>
+
В данном алгоритме оператор <tex>\mathrm {spawn}</tex> запускает новый поток, а оператор <tex>\mathrm {sync}</tex> ожидает завершения этого потока. Функция <tex>\mathrm {merge}</tex> аналогична одноименной функции из раздела [[Сортировка слиянием#Слияние двух массивов|слияние двух массивов]].<br>
Несмотря на наличие двух рекурсивных вызовов, при оценке будем считать, что совершается один вызов, т.к. оба вызова выполняются параллельно с одинаковой асимптотикой. Оценим время работы данного алгоритма:  <tex dpi="120">T(n) = T(\frac {n}{2}) + \Theta(n) = \Theta(n)</tex>. Данная асимптотика достигается при возможности запускать неограниченное количество потоков независимо друг от друга.<br>
+
Несмотря на наличие двух рекурсивных вызовов, при оценке будем считать, что совершается один вызов, т.к. оба вызова выполняются параллельно с одинаковой асимптотикой. Оценим время работы данного алгоритма:  <tex>T(n) = T(\dfrac {n}{2}) + \Theta(n) = \Theta(n)</tex>. Данная асимптотика достигается при возможности запускать неограниченное количество потоков независимо друг от друга.<br>
  
 
==Многопоточное слияние==
 
==Многопоточное слияние==
 
Как видно из оценки первого алгоритма, слияние является его узким местом. Попытаемся распараллелить слияние, для чего рассмотрим алгоритм рекурсивного слияния массивов <tex dpi="120">T[left_{1} \dots right_{1}]</tex> и <tex dpi="120">T[left_{2} \dots right_{2}]</tex> в массив <tex dpi="120">A[left_{3} \dots right_{3}]</tex>:
 
Как видно из оценки первого алгоритма, слияние является его узким местом. Попытаемся распараллелить слияние, для чего рассмотрим алгоритм рекурсивного слияния массивов <tex dpi="120">T[left_{1} \dots right_{1}]</tex> и <tex dpi="120">T[left_{2} \dots right_{2}]</tex> в массив <tex dpi="120">A[left_{3} \dots right_{3}]</tex>:
[[Файл:MergeMT.png‎|430px|thumb|Слияние массивов]]
+
 
 
# Убедимся, что размер <tex dpi="120">T[left_{1} \dots right_{1}]</tex> больше либо равен размеру <tex dpi="120">T[left_{2} \dots right_{2}]</tex>
 
# Убедимся, что размер <tex dpi="120">T[left_{1} \dots right_{1}]</tex> больше либо равен размеру <tex dpi="120">T[left_{2} \dots right_{2}]</tex>
# Возьмем <tex dpi="120">x = T[mid_{1}]</tex> - середину первого массива (<tex dpi="120">x</tex> также является и медианой этого массива)
+
# Возьмем <tex dpi="120">x = T[mid_{1}]</tex> середину первого массива (<tex dpi="120">x</tex> также является и медианой этого массива)
 
# При помощи [[Целочисленный двоичный поиск|бинарного поиска]] найдем <tex dpi="120">mid_{2}</tex> такое, что <tex dpi="120">\forall y \in T[left_{2} \dots mid_{2} - 1]: y < x</tex>
 
# При помощи [[Целочисленный двоичный поиск|бинарного поиска]] найдем <tex dpi="120">mid_{2}</tex> такое, что <tex dpi="120">\forall y \in T[left_{2} \dots mid_{2} - 1]: y < x</tex>
 
# <tex dpi="120">mid_{3} = left_{3} + (mid_{1} - left_{1}) + (mid_{2} - left_{2})</tex>
 
# <tex dpi="120">mid_{3} = left_{3} + (mid_{1} - left_{1}) + (mid_{2} - left_{2})</tex>
Строка 25: Строка 26:
 
# Сольем <tex dpi="120">T[right_{1} \dots mid_{1} - 1]</tex> и <tex dpi="120">T[right_{2} \dots mid_{2}]</tex> в <tex dpi="120">A[right_{3} \dots mid_{3} - 1]</tex>
 
# Сольем <tex dpi="120">T[right_{1} \dots mid_{1} - 1]</tex> и <tex dpi="120">T[right_{2} \dots mid_{2}]</tex> в <tex dpi="120">A[right_{3} \dots mid_{3} - 1]</tex>
 
# Сольем <tex dpi="120">T[mid_{1} + 1 \dots right_{1}]</tex> и <tex dpi="120">T[mid_{2} \dots right_{2}]</tex> в <tex dpi="120">A[mid_{3} + 1 \dots right_{3}]</tex>
 
# Сольем <tex dpi="120">T[mid_{1} + 1 \dots right_{1}]</tex> и <tex dpi="120">T[mid_{2} \dots right_{2}]</tex> в <tex dpi="120">A[mid_{3} + 1 \dots right_{3}]</tex>
 +
 +
Алгоритм показан на рисунке:
 +
 +
[[Файл:MergeMT.png‎|Слияние массивов]]
  
 
===Реализация===
 
===Реализация===
     // если <tex dpi="120">right \leqslant left</tex> возвращает <tex dpi="120">left</tex>
+
     <font color=green>// если <tex dpi="120" color=green>right \leqslant left</tex> возвращает <tex dpi="120">left</tex>
 
     // если <tex dpi="120">x \leqslant T[left]</tex>, возвращает <tex dpi="120">left</tex>
 
     // если <tex dpi="120">x \leqslant T[left]</tex>, возвращает <tex dpi="120">left</tex>
     // иначе возвращает наибольший индекс <tex dpi="120">i</tex> из отрезка <tex dpi="120">[left, right]</tex> такой, что <tex dpi="120">array[i - 1] < x</tex>
+
     // иначе возвращает наибольший индекс <tex dpi="120">i</tex> из отрезка <tex dpi="120">[left, right]</tex> такой, что <tex dpi="120">array[i - 1] < x</tex></font>
     integer binarySearch(x, array, left, right)
+
     '''integer''' binarySearch(x, array, left, right)
 
      
 
      
     // слияние <tex dpi="120">T[left_{1} \dots right_{1}]</tex> и <tex dpi="120">T[left_{2} \dots right_{2}]</tex> в <tex dpi="120">A[left_{3} \dots right_{1} - left_{1} + right_{2} - left_{2}]</tex>
+
     <font color=green>// слияние <tex dpi="120">T[left_{1} \dots right_{1}]</tex> и <tex dpi="120">T[left_{2} \dots right_{2}]</tex> в <tex dpi="120">A[left_{3} \dots right_{1} - left_{1} + right_{2} - left_{2}]</tex></font>
     function mergeMT(T, left<tex dpi="120">_{1}</tex>, right<tex dpi="120">_{1}</tex>, left<tex dpi="120">_{2}</tex>, right<tex dpi="120">_{2}</tex>, A, left<tex dpi="120">_{3}</tex>):
+
     '''function''' mergeMT(T, left<tex dpi="120">_{1}</tex>, right<tex dpi="120">_{1}</tex>, left<tex dpi="120">_{2}</tex>, right<tex dpi="120">_{2}</tex>, A, left<tex dpi="120">_{3}</tex>):
 
         n<tex dpi="120">_{1}</tex> = right<tex dpi="120">_{1}</tex> - left<tex dpi="120">_{1}</tex> + 1
 
         n<tex dpi="120">_{1}</tex> = right<tex dpi="120">_{1}</tex> - left<tex dpi="120">_{1}</tex> + 1
 
         n<tex dpi="120">_{2}</tex> = right<tex dpi="120">_{2}</tex> - left<tex dpi="120">_{2}</tex> + 1
 
         n<tex dpi="120">_{2}</tex> = right<tex dpi="120">_{2}</tex> - left<tex dpi="120">_{2}</tex> + 1
Строка 53: Строка 58:
  
 
Оба массива содержат <tex dpi="120">n_{1} + n_{2} = n</tex> элементов. К моменту рекурсивных вызовов <tex dpi="120">n_{2} \leqslant n_{1}</tex>, значит,<br>
 
Оба массива содержат <tex dpi="120">n_{1} + n_{2} = n</tex> элементов. К моменту рекурсивных вызовов <tex dpi="120">n_{2} \leqslant n_{1}</tex>, значит,<br>
<tex dpi="135">n_{2} = 2 \cdot \frac{n_{2}}{2} \leqslant \frac{(n_{1} + n_{2})}{2} = \frac{n}{2}</tex>.<br>
+
<tex>n_{2} = 2 \cdot \dfrac{n_{2}}{2} \leqslant \dfrac{(n_{1} + n_{2})}{2} = \dfrac{n}{2}</tex>.<br>
В худшем случае один из двух рекурсивных вызовов сольет <tex dpi="135">\frac{n_{1}}{2}</tex> элементов <tex dpi="120">T[left_{1} \dots right_{1}]</tex> с <tex dpi="120">n_{2}</tex> элементами <tex dpi="120">T[left_{2} \dots right_{2}]</tex> и тогда количество элементов первых двух массивов в рекурсивном вызове будет равно<br>
+
В худшем случае один из двух рекурсивных вызовов сольет <tex>\dfrac{n_{1}}{2}</tex> элементов <tex dpi="120">T[left_{1} \dots right_{1}]</tex> с <tex dpi="120">n_{2}</tex> элементами <tex dpi="120">T[left_{2} \dots right_{2}]</tex> и тогда количество элементов первых двух массивов в рекурсивном вызове будет равно<br>
<tex dpi="135">\frac{n_{1}}{2} + n_{2} \leqslant \frac{n_{1}}{2} + \frac{n_{2}}{2} + \frac{n_{2}}{2} = \frac{(n_{1} + n_{2})}{2} + \frac{n_{2}}{2} \leqslant \frac{n}{2} + \frac{n}{4} = \frac{3}{4}n</tex>.<br>Асимптотика каждого вызова функции - <tex dpi="120">\Theta(\log n)</tex>, т.е. время, затрачиваемое на бинарный поиск. Так как рекурсивные вызовы функции выполняются параллельно, а потоки при оценке независимы, время их выполнения будет равно времени выполнения самого долгого вызова. В худшем случае это <tex dpi="120">T(\frac{3}{4}n)</tex>. Тогда получим оценку сверху<br><tex dpi="130">T_{\mathrm {merge}}(n) = T_{\mathrm {merge}}(\frac{3}{4}n) + \Theta(\log n) = \Theta(\log^2 n)</tex>
+
<tex>\dfrac{n_{1}}{2} + n_{2} \leqslant \dfrac{n_{1}}{2} + \dfrac{n_{2}}{2} + \dfrac{n_{2}}{2} = \dfrac{(n_{1} + n_{2})}{2} + \dfrac{n_{2}}{2} \leqslant \dfrac{n}{2} + \dfrac{n}{4} = \dfrac{3}{4}n</tex>.<br>Асимптотика каждого вызова функции <tex dpi="120">\Theta(\log n)</tex>, т.е. время, затрачиваемое на бинарный поиск. Так как рекурсивные вызовы функции выполняются параллельно, а потоки при оценке независимы, время их выполнения будет равно времени выполнения самого долгого вызова. В худшем случае это <tex>T(\dfrac{3}{4}n)</tex>. Тогда получим оценку сверху<br><tex>T_{\mathrm {merge}}(n) = T_{\mathrm {merge}}(\dfrac{3}{4}n) + \Theta(\log n) = \Theta(\log^2 n)</tex>
  
 
==Сортировка с многопоточным слиянием==
 
==Сортировка с многопоточным слиянием==
 
Приведем псевдокод алгоритма, использующего слияние из предыдущего раздела, сортирующего элементы <tex dpi="120">A[leftA \dots rightA]</tex> и помещающего отсортированный массив в <tex dpi="120">B[leftB \dots leftB + rightA - leftA]</tex>
 
Приведем псевдокод алгоритма, использующего слияние из предыдущего раздела, сортирующего элементы <tex dpi="120">A[leftA \dots rightA]</tex> и помещающего отсортированный массив в <tex dpi="120">B[leftB \dots leftB + rightA - leftA]</tex>
  
     function mergeSortMT2(A, leftA, rightA, B, leftB):
+
     '''function''' mergeSortMT2(A, leftA, rightA, B, leftB):
 
         n = r - p + 1
 
         n = r - p + 1
 
         '''if''' n == 1
 
         '''if''' n == 1
Строка 73: Строка 78:
 
             mergeMT(T, 1, newMid, newMid + 1, n, B, leftB)
 
             mergeMT(T, 1, newMid, newMid + 1, n, B, leftB)
  
Оценим данный алгоритм сверху при условии, что возможен запуск неограниченного количества независимых потоков. Из предыдущих пунктов <tex dpi="130">T_{\mathrm {mergeSort}}(n) = T_{\mathrm {mergeSort}}(\frac{n}{2}) + T_{\mathrm {merge}}(n) = T_{\mathrm {mergeSort}}(\frac{n}{2}) + \Theta(\log^2 n) = \Theta(\log^3 n)</tex>.
+
Оценим данный алгоритм сверху при условии, что возможен запуск неограниченного количества независимых потоков. Из предыдущих пунктов <tex>T_{\mathrm {mergeSort}}(n) = T_{\mathrm {mergeSort}}(\dfrac{n}{2}) + T_{\mathrm {merge}}(n) = T_{\mathrm {mergeSort}}(\dfrac{n}{2}) + \Theta(\log^2 n) = \Theta(\log^3 n)</tex>.
  
 
==Оценка при фиксированном числе потоков==
 
==Оценка при фиксированном числе потоков==
Очевидно, что при отсутствии возможности запуска неограниченного количества независимых потоков, вычислительная сложность многопоточного алгоритма зависит от максимально возможного количества независимых потоков. Обозначим такое количество как <tex dpi="120">N_{ind}</tex>. Допустим, <tex dpi="120">n</tex> много больше <tex dpi="120">N_{ind}</tex>, что в общем случае верно для ПК и достаточно больших объемов данных. Оценим приведенные выше алгоритмы с учетом наложенных ограничений и допущений:<br>
+
Понятно, что при отсутствии возможности запуска неограниченного количества независимых потоков, вычислительная сложность многопоточного алгоритма зависит от максимально возможного количества независимых потоков. Обозначим такое количество как <tex dpi="120">N_{ind}</tex>. Допустим, <tex dpi="120">n</tex> много больше <tex dpi="120">N_{ind}</tex>, что в общем случае верно для ПК и достаточно больших объемов данных. Оценим приведенные выше алгоритмы с учетом наложенных ограничений и допущений:<br>
::[[#.D0.A1.D0.BE.D1.80.D1.82.D0.B8.D1.80.D0.BE.D0.B2.D0.BA.D0.B0_.D1.81_.D0.BE.D0.B4.D0.BD.D0.BE.D0.BF.D0.BE.D1.82.D0.BE.D1.87.D0.BD.D1.8B.D0.BC_.D1.81.D0.BB.D0.B8.D1.8F.D0.BD.D0.B8.D0.B5.D0.BC|Сортировка с однопоточным слиянием]] будет иметь асимптотику <tex dpi="135">\Theta(\frac{n}{N_{ind}}\log \frac{n}{N_{ind}} + n) = \Theta(\frac{n}{N_{ind}}\log \frac{n}{N_{ind}})</tex>:
+
::[[#Сортировка с однопоточным слиянием|Сортировка с однопоточным слиянием]] будет иметь асимптотику <tex>\Theta(\dfrac{n}{N_{ind}}\log \dfrac{n}{N_{ind}} + n) = \Theta(\dfrac{n}{N_{ind}}\log \dfrac{n}{N_{ind}})</tex>:
::::<tex dpi="135">\Theta(\frac{n}{N_{ind}}\log \frac{n}{N_{ind}})</tex> операций нужно на последовательную сортировку массива длиной <tex dpi="135">\frac{n}{N_{ind}}</tex>.
+
::::<tex>\Theta(\dfrac{n}{N_{ind}}\log \dfrac{n}{N_{ind}})</tex> операций нужно на последовательную сортировку массива длиной <tex>\dfrac{n}{N_{ind}}</tex>.
 
::::<tex dpi="135">\Theta(n)</tex> необходимо на последовательное слияние.
 
::::<tex dpi="135">\Theta(n)</tex> необходимо на последовательное слияние.
::[[#.D0.9C.D0.BD.D0.BE.D0.B3.D0.BE.D0.BF.D0.BE.D1.82.D0.BE.D1.87.D0.BD.D0.BE.D0.B5_.D1.81.D0.BB.D0.B8.D1.8F.D0.BD.D0.B8.D0.B5|Многопоточное слияние]] будет работать за <tex dpi="135">\Theta((\frac{n}{N_{ind}})^{\log_{\frac{4}{3}}2} + \log n \cdot min(N_{ind}, \log n)=\Theta((\frac{n}{N_{ind}})^{\log_{\frac{4}{3}}2})</tex>:
+
::[[#Многопоточное слияние|Многопоточное слияние]] будет работать за <tex>\Theta((\dfrac{n}{N_{ind}})^{\log_{\frac{4}{3}}2} + \log n \cdot min(N_{ind}, \log n)=\Theta((\dfrac{n}{N_{ind}})^{\log_{\frac{4}{3}}2})</tex>:
 
::::Прежде чем достигнуть ограничения на создание нового потока, алгоритм углубится на <tex dpi="110">min(N_{ind}, \log n)</tex> уровней вглубь дерева рекурсии, где на каждом уровне выполняется бинпоиск за <tex dpi="135">\Theta(\log n)</tex>
 
::::Прежде чем достигнуть ограничения на создание нового потока, алгоритм углубится на <tex dpi="110">min(N_{ind}, \log n)</tex> уровней вглубь дерева рекурсии, где на каждом уровне выполняется бинпоиск за <tex dpi="135">\Theta(\log n)</tex>
 
::::Асимптотика многопоточного слияния при работе в одном потоке по основной теореме рекуррентных соотношений равна  
 
::::Асимптотика многопоточного слияния при работе в одном потоке по основной теореме рекуррентных соотношений равна  
::::<tex dpi="135">T_{\mathrm {merge}}'(n) = 2T_{\mathrm {merge}}'(\frac {3}{4}n) + \Theta(\log n) = \Theta(n^{\log_{\frac{4}{3}}2})</tex>
+
::::<tex>T_{\mathrm {merge}}'(n) = 2T_{\mathrm {merge}}'(\frac {3}{4}n) + \Theta(\log n) = \Theta(n^{\log_{\frac{4}{3}}2})</tex>
::Оценим [[#.D0.A1.D0.BE.D1.80.D1.82.D0.B8.D1.80.D0.BE.D0.B2.D0.BA.D0.B0_.D1.81_.D0.BC.D0.BD.D0.BE.D0.B3.D0.BE.D0.BF.D0.BE.D1.82.D0.BE.D1.87.D0.BD.D1.8B.D0.BC_.D1.81.D0.BB.D0.B8.D1.8F.D0.BD.D0.B8.D0.B5.D0.BC|сортировку с многопоточным слиянием]] снизу:
+
::Оценим [[#Сортировка с многопоточным слиянием|сортировку с многопоточным слиянием]] снизу:
::::Части массива длиной <tex dpi="135">\frac{n}{N_{ind}}</tex> гарантированно будут сортироваться последовательно, т.к. только алгоритм сортировки запустит к моменту вызова <tex>\mathrm {mergeSortMT2} </tex> от массива длиной <tex dpi="135">\frac{n}{N_{ind}}</tex> число потоков, равное <tex dpi="135">N_{ind}</tex>. Тогда по основной теореме рекуррентных соотношений:
+
::::Части массива длиной <tex>\dfrac{n}{N_{ind}}</tex> гарантированно будут сортироваться последовательно, т.к. только алгоритм сортировки запустит к моменту вызова <tex>\mathrm {mergeSortMT2} </tex> от массива длиной <tex>\dfrac{n}{N_{ind}}</tex> число потоков, равное <tex dpi="135">N_{ind}</tex>. Тогда по основной теореме рекуррентных соотношений:
::::<tex dpi="135">T_{\mathrm {mergeSort}}'(\frac{n}{N_{ind}}) = 2T_{\mathrm {mergeSort}}'(\frac{n}{2N_{ind}}) + \Theta(\frac{n}{N_{ind}})^{\log_{\frac{4}{3}}2} = \Theta(\frac{n}{N_{ind}})^{\log_{\frac{4}{3}}2}</tex>
+
::::<tex>T_{\mathrm {mergeSort}}'(\dfrac{n}{N_{ind}}) = 2T_{\mathrm {mergeSort}}'(\dfrac{n}{2N_{ind}}) + \Theta(\dfrac{n}{N_{ind}})^{\log_{\frac{4}{3}}2} = \Theta(\dfrac{n}{N_{ind}})^{\log_{\frac{4}{3}}2}</tex>
Очевидно, что нижняя оценка алгоритма сортировки с многопоточным слиянием выше. Таким образом, при приведенных выше допущениях алгоритм сортировки с однопоточным слиянием эффективнее и его асимптотика составляет <tex dpi="120">\Theta(\frac{n}{N_{ind}}\log \frac{n}{N_{ind}})</tex>.
+
Очевидно, что нижняя оценка алгоритма сортировки с многопоточным слиянием выше. Таким образом, при приведенных выше допущениях алгоритм сортировки с однопоточным слиянием эффективнее и его асимптотика составляет <tex>\Theta(\dfrac{n}{N_{ind}}\log \dfrac{n}{N_{ind}})</tex>.
 +
 
 +
==См. также==
 +
*[[Сортировка слиянием]]
 +
*[[PSRS-сортировка]]
 
==Источники информации==
 
==Источники информации==
#Cormen T.H., Leiserson C.E., Rivest R.L., Stein C. {{---}} Introduction to Algorithms, Third Edition
+
*Cormen T.H., Leiserson C.E., Rivest R.L., Stein C. {{---}} Introduction to Algorithms, Third Edition
 +
 
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Сортировки]]
 +
[[Категория: Многопоточные сортировки]]

Текущая версия на 14:17, 4 июня 2015

Многопоточная сортировка слиянием[править]

Благодаря тому, что сортировка слиянием построена на принципе "Разделяй и властвуй", выполнение данного алгоритма можно весьма эффективно распараллелить. При оценке асимптотики допускается, что возможен запуск неограниченного количества независимых процессов, т.е. процессов с вычислительными ресурсами, не зависящими от других процессов, что на практике не достижимо. Более того, при реализации имеет смысл ограничить количество параллельных потоков.

Сортировка с однопоточным слиянием[править]

Внесем в алгоритм сортировки слиянием следующую модификацию: будем сортировать левую и правую части массива параллельно.

   function mergeSortMT(array, left, right):
       mid = (left + right) / 2
   
       spawn mergeSortMT(array, left, mid)
       mergeSortMT(array, mid + 1, right)
       sync
   
       merge(array, left, mid, right)

В данном алгоритме оператор [math]\mathrm {spawn}[/math] запускает новый поток, а оператор [math]\mathrm {sync}[/math] ожидает завершения этого потока. Функция [math]\mathrm {merge}[/math] аналогична одноименной функции из раздела слияние двух массивов.
Несмотря на наличие двух рекурсивных вызовов, при оценке будем считать, что совершается один вызов, т.к. оба вызова выполняются параллельно с одинаковой асимптотикой. Оценим время работы данного алгоритма: [math]T(n) = T(\dfrac {n}{2}) + \Theta(n) = \Theta(n)[/math]. Данная асимптотика достигается при возможности запускать неограниченное количество потоков независимо друг от друга.

Многопоточное слияние[править]

Как видно из оценки первого алгоритма, слияние является его узким местом. Попытаемся распараллелить слияние, для чего рассмотрим алгоритм рекурсивного слияния массивов [math]T[left_{1} \dots right_{1}][/math] и [math]T[left_{2} \dots right_{2}][/math] в массив [math]A[left_{3} \dots right_{3}][/math]:

  1. Убедимся, что размер [math]T[left_{1} \dots right_{1}][/math] больше либо равен размеру [math]T[left_{2} \dots right_{2}][/math]
  2. Возьмем [math]x = T[mid_{1}][/math] — середину первого массива ([math]x[/math] также является и медианой этого массива)
  3. При помощи бинарного поиска найдем [math]mid_{2}[/math] такое, что [math]\forall y \in T[left_{2} \dots mid_{2} - 1]: y \lt x[/math]
  4. [math]mid_{3} = left_{3} + (mid_{1} - left_{1}) + (mid_{2} - left_{2})[/math]
  5. [math]A[mid_{3}] = x[/math]
  6. Сольем [math]T[right_{1} \dots mid_{1} - 1][/math] и [math]T[right_{2} \dots mid_{2}][/math] в [math]A[right_{3} \dots mid_{3} - 1][/math]
  7. Сольем [math]T[mid_{1} + 1 \dots right_{1}][/math] и [math]T[mid_{2} \dots right_{2}][/math] в [math]A[mid_{3} + 1 \dots right_{3}][/math]

Алгоритм показан на рисунке:

Слияние массивов

Реализация[править]

   // если [math]right \leqslant left[/math] возвращает [math]left[/math]
   // если [math]x \leqslant T[left][/math], возвращает [math]left[/math]
   // иначе возвращает наибольший индекс [math]i[/math] из отрезка [math][left, right][/math] такой, что [math]array[i - 1] \lt  x[/math]
   integer binarySearch(x, array, left, right)
   
   // слияние [math]T[left_{1} \dots right_{1}][/math] и [math]T[left_{2} \dots right_{2}][/math] в [math]A[left_{3} \dots right_{1} - left_{1} + right_{2} - left_{2}][/math]
   function mergeMT(T, left[math]_{1}[/math], right[math]_{1}[/math], left[math]_{2}[/math], right[math]_{2}[/math], A, left[math]_{3}[/math]):
       n[math]_{1}[/math] = right[math]_{1}[/math] - left[math]_{1}[/math] + 1
       n[math]_{2}[/math] = right[math]_{2}[/math] - left[math]_{2}[/math] + 1
       if n[math]_{1}[/math] < n[math]_{2}[/math]
           swap(left[math]_{1}[/math], left[math]_{2}[/math])
           swap(right[math]_{1}[/math], right[math]_{2}[/math])
           swap(n[math]_{1}[/math], n[math]_{2}[/math])
   
       if n[math]_{1}[/math] == 0
           return
       else
           mid[math]_{1}[/math] = (left[math]_{1}[/math] + right[math]_{1}[/math]) / 2
           mid[math]_{2}[/math] = binarySearch(T[mid[math]_{1}[/math]], T, left[math]_{2}[/math], right[math]_{2}[/math])
           mid[math]_{3}[/math] = left[math]_{3}[/math] + (mid[math]_{1}[/math] - left[math]_{1}[/math]) + (mid[math]_{2}[/math] - left[math]_{2}[/math])
           A[mid[math]_{3}[/math]] = T[mid[math]_{1}[/math]]
           spawn mergeMT(T, left[math]_{1}[/math], mid[math]_{1}[/math] - 1, left[math]_{2}[/math], mid[math]_{2}[/math] - 1, A, left[math]_{3}[/math])
           mergeMT(T, mid[math]_{1}[/math] + 1, right[math]_{1}[/math], mid[math]_{2}[/math], right[math]_{2}[/math], A, mid[math]_{3}[/math] + 1)
           sync

Оба массива содержат [math]n_{1} + n_{2} = n[/math] элементов. К моменту рекурсивных вызовов [math]n_{2} \leqslant n_{1}[/math], значит,
[math]n_{2} = 2 \cdot \dfrac{n_{2}}{2} \leqslant \dfrac{(n_{1} + n_{2})}{2} = \dfrac{n}{2}[/math].
В худшем случае один из двух рекурсивных вызовов сольет [math]\dfrac{n_{1}}{2}[/math] элементов [math]T[left_{1} \dots right_{1}][/math] с [math]n_{2}[/math] элементами [math]T[left_{2} \dots right_{2}][/math] и тогда количество элементов первых двух массивов в рекурсивном вызове будет равно
[math]\dfrac{n_{1}}{2} + n_{2} \leqslant \dfrac{n_{1}}{2} + \dfrac{n_{2}}{2} + \dfrac{n_{2}}{2} = \dfrac{(n_{1} + n_{2})}{2} + \dfrac{n_{2}}{2} \leqslant \dfrac{n}{2} + \dfrac{n}{4} = \dfrac{3}{4}n[/math].
Асимптотика каждого вызова функции — [math]\Theta(\log n)[/math], т.е. время, затрачиваемое на бинарный поиск. Так как рекурсивные вызовы функции выполняются параллельно, а потоки при оценке независимы, время их выполнения будет равно времени выполнения самого долгого вызова. В худшем случае это [math]T(\dfrac{3}{4}n)[/math]. Тогда получим оценку сверху
[math]T_{\mathrm {merge}}(n) = T_{\mathrm {merge}}(\dfrac{3}{4}n) + \Theta(\log n) = \Theta(\log^2 n)[/math]

Сортировка с многопоточным слиянием[править]

Приведем псевдокод алгоритма, использующего слияние из предыдущего раздела, сортирующего элементы [math]A[leftA \dots rightA][/math] и помещающего отсортированный массив в [math]B[leftB \dots leftB + rightA - leftA][/math]

   function mergeSortMT2(A, leftA, rightA, B, leftB):
       n = r - p + 1
       if n == 1
           B[leftB] = A[leftA]
       else
           создадим новый массив T[1 [math]\dots[/math] n]
           mid = (leftA + rightA) / 2
           newMid = mid - leftA + 1
           spawn mergeSortMT2(A, leftA, mid, T, 1)
           mergeSortMT2(A, mid + 1, rightA, T, newMid + 1)
           sync
           mergeMT(T, 1, newMid, newMid + 1, n, B, leftB)

Оценим данный алгоритм сверху при условии, что возможен запуск неограниченного количества независимых потоков. Из предыдущих пунктов [math]T_{\mathrm {mergeSort}}(n) = T_{\mathrm {mergeSort}}(\dfrac{n}{2}) + T_{\mathrm {merge}}(n) = T_{\mathrm {mergeSort}}(\dfrac{n}{2}) + \Theta(\log^2 n) = \Theta(\log^3 n)[/math].

Оценка при фиксированном числе потоков[править]

Понятно, что при отсутствии возможности запуска неограниченного количества независимых потоков, вычислительная сложность многопоточного алгоритма зависит от максимально возможного количества независимых потоков. Обозначим такое количество как [math]N_{ind}[/math]. Допустим, [math]n[/math] много больше [math]N_{ind}[/math], что в общем случае верно для ПК и достаточно больших объемов данных. Оценим приведенные выше алгоритмы с учетом наложенных ограничений и допущений:

Сортировка с однопоточным слиянием будет иметь асимптотику [math]\Theta(\dfrac{n}{N_{ind}}\log \dfrac{n}{N_{ind}} + n) = \Theta(\dfrac{n}{N_{ind}}\log \dfrac{n}{N_{ind}})[/math]:
[math]\Theta(\dfrac{n}{N_{ind}}\log \dfrac{n}{N_{ind}})[/math] операций нужно на последовательную сортировку массива длиной [math]\dfrac{n}{N_{ind}}[/math].
[math]\Theta(n)[/math] необходимо на последовательное слияние.
Многопоточное слияние будет работать за [math]\Theta((\dfrac{n}{N_{ind}})^{\log_{\frac{4}{3}}2} + \log n \cdot min(N_{ind}, \log n)=\Theta((\dfrac{n}{N_{ind}})^{\log_{\frac{4}{3}}2})[/math]:
Прежде чем достигнуть ограничения на создание нового потока, алгоритм углубится на [math]min(N_{ind}, \log n)[/math] уровней вглубь дерева рекурсии, где на каждом уровне выполняется бинпоиск за [math]\Theta(\log n)[/math]
Асимптотика многопоточного слияния при работе в одном потоке по основной теореме рекуррентных соотношений равна
[math]T_{\mathrm {merge}}'(n) = 2T_{\mathrm {merge}}'(\frac {3}{4}n) + \Theta(\log n) = \Theta(n^{\log_{\frac{4}{3}}2})[/math]
Оценим сортировку с многопоточным слиянием снизу:
Части массива длиной [math]\dfrac{n}{N_{ind}}[/math] гарантированно будут сортироваться последовательно, т.к. только алгоритм сортировки запустит к моменту вызова [math]\mathrm {mergeSortMT2} [/math] от массива длиной [math]\dfrac{n}{N_{ind}}[/math] число потоков, равное [math]N_{ind}[/math]. Тогда по основной теореме рекуррентных соотношений:
[math]T_{\mathrm {mergeSort}}'(\dfrac{n}{N_{ind}}) = 2T_{\mathrm {mergeSort}}'(\dfrac{n}{2N_{ind}}) + \Theta(\dfrac{n}{N_{ind}})^{\log_{\frac{4}{3}}2} = \Theta(\dfrac{n}{N_{ind}})^{\log_{\frac{4}{3}}2}[/math]

Очевидно, что нижняя оценка алгоритма сортировки с многопоточным слиянием выше. Таким образом, при приведенных выше допущениях алгоритм сортировки с однопоточным слиянием эффективнее и его асимптотика составляет [math]\Theta(\dfrac{n}{N_{ind}}\log \dfrac{n}{N_{ind}})[/math].

См. также[править]

Источники информации[править]

  • Cormen T.H., Leiserson C.E., Rivest R.L., Stein C. — Introduction to Algorithms, Third Edition