Обсуждение:PSRS-сортировка — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
==Распараллеливание простых сортировок==
+
== Сортировка PSRS ==
===Быстрая параллельная сортировка===
+
=== Алгоритм ===
В алгоритме быстрой сортировки, исходный массив разбивается на <tex>2</tex> части, обработка которых ведется независимо (поэтому может выполняться параллельно). Задачи должны создаваться внутри параллельной области, однако если мы так сделаем, то у нас будут рекурсивно создаваться потоки (количество потоков при этом будет зависеть от размера обрабатываемого массива). Создание потока — очень сложная операция, требующая значительных вычислительных затрат, поэтому потоки мы создадим до вызова функции. Итак, поток, выполнившийся поток добавит в пул одну или две задачи и завершится. Но мы должны дождаться пока эти задачи будут выполнены. При этом, добавлять задачи в пул будет не только этот поток, но любой другой поток (ведь он может взять из пула задачу и обработать часть массива). Оптимизированный вариант сортировки отличается от обычного лишь тем, что при небольшом (с точным значением можно поиграть) размере массива сортировка выполняется последовательно.
+
Для начала надо разделить входные данные на n равных частей, где n - количество процессоров. Далее запустить алгоритм быстрой сортировки на каждом из процессоров. Далее  мы должны сформировать массив элементами которого будут элементы из каждого процессора с индексами 0, n/p^2, 2n/p^2,...,(p-1)n/p^2 и элементы стоящие в процессорах левее выбранных. Далее на нам потребуется отсортировать полученный массив и выбрать из него p разделителей с индексами p + [p / 2] - 1, 2p + [p / 2] - 1,...,(p-1)n + [p / 2] - 1. Теперь разделим данные в процессорах согласно полученному массиву разделителей и сольём данные соответствующие части в в массив.
  '''void''' quickSort('''int'''[] a, '''long''' n)
 
    '''long''' i = 0, j = n
 
    '''int'''  mid = a['''Random'''(n)]; // опорный элемент
 
 
    '''do'''
 
      '''while''' (a[i] < mid) i++
 
      '''while''' (a[j] > mid) j--
 
 
 
      '''if''' (i <tex>  \leqslant </tex> j)
 
        swap(a[i], a[j])
 
        i++ j--
 
    '''while''' (i <tex>  \leqslant </tex> j);
 
 
    '''if''' (n < 100)  // если размер массива меньше 100
 
                  // сортировка выполняется в текущем потоке
 
      '''if''' (j > 0) quickSort(a, j)
 
      '''if''' (n > i) quickSort(a + i, n - i)
 
      '''return'''
 
 
 
 
    '''spawn'''
 
      '''if''' (j > 0) quickSort(a, j)
 
    '''spawn'''
 
      '''if''' (n > i) quickSort(a + i, n - i)
 
    '''sync'''
 
В данном алгоритме оператор <tex>\mathrm {spawn}</tex> запускает новый поток, а оператор <tex>\mathrm {sync}</tex> ожидает завершения этого потока.
 
=== Анализ эффективности параллельного алгоритма ===
 
Каждую итерацию массив делится случайно. На первой итерации при делении на <tex>2</tex> части с меньшими и большими элеменами с разделяющим ведущем пусть длина меньшей части <tex>n1</tex>. Алгоритм отправляет её на другой процессор сортироваться параллельно, а так как она короче, то и досортируется быстрее, значит время её сортировки не учитывается. Длина большей части <tex>N-n1</tex>, с этой частью мы проделываем точно такую же итерацию с разделителем <tex>n2</tex>. И так далее до момента, когда число свободных процессоров закончится, то есть до разделителя <tex>nk</tex>. Где <tex>[p / 100]=2^k</tex>.
 
 
 
<tex>T=O(N+(N-n1)+(N-n1-n2)+...+(N-n1-...-nk))</tex>.
 

Версия 21:20, 10 июня 2014

Сортировка PSRS

Алгоритм

Для начала надо разделить входные данные на n равных частей, где n - количество процессоров. Далее запустить алгоритм быстрой сортировки на каждом из процессоров. Далее мы должны сформировать массив элементами которого будут элементы из каждого процессора с индексами 0, n/p^2, 2n/p^2,...,(p-1)n/p^2 и элементы стоящие в процессорах левее выбранных. Далее на нам потребуется отсортировать полученный массив и выбрать из него p разделителей с индексами p + [p / 2] - 1, 2p + [p / 2] - 1,...,(p-1)n + [p / 2] - 1. Теперь разделим данные в процессорах согласно полученному массиву разделителей и сольём данные соответствующие части в в массив.