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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
==Распараллеливание простых сортировок==
 
==Распараллеливание простых сортировок==
===Параллельная сортировка пузырьком===
+
===Быстрая параллельная сортировка===
Сначала главный процессор разбивает исходный массив длиной <tex>z</tex> элементов на <tex>p</tex> равных частей блоков. Каждый блок содержит <tex>p=z/n</tex> элементов массива. Полученные блоки рассылаются по процессам. Далее идет предобработка. На этапе предобработки каждый процесс сортирует свой массив методом пузырьковой сортировки. Далее происходит чередование чет-нечетных перестановок на p итерациях. На нечетной итерации пары процессов с номерами <tex>(0,1)(2,3)(4,5)</tex> обмениваются друг с другом массивами, при этом выполняется слияние блоков, после чего на процессе с меньшим номером остается <tex>n/p</tex> первых упорядоченных элементов объединенного массива, а на процессе с большим номером остается <tex>n/p</tex> последних упорядоченных элементов объединенного массива. На четной итерации происходит все точно так же, но обмен производится между процессами с номерами <tex>(1,2)(3,4)(5,6)(7,8)…</tex> . Если в течении двух последовательных четной и нечетной итерации не производится никаких изменений, то алгоритм может прекратить свою работу заранее. После этого части массивов отсылаются на главный процесс и там объединяются, после чего получается отсортированный массив. Предобработка занимет <tex>p^2</tex> тактов после чего происходит максимум <tex>n</tex> слияний. Осознать, что максимально количество слияний можно, представив частный случай. Пусть минимальный элемент оказался в последнем блоке тогда за за каждое слияние он будет перемещаться на один блок влево. После <tex>n</tex> слияний он окажется в первом блоке. В итоге время сортировки сократится с <tex> z^2 </tex> до <tex> p^2+2pn\log (2*p)</tex> .
+
В алгоритме быстрой сортировки, исходный массив разбивается на 2 части, обработка которых ведется не зависимо (поэтому может выполняться параллельно). Задачи должны создаваться внутри параллельной области, однако если мы поместим директиву omp parallel внутрь функции, то у нас будут рекурсивно создаваться потоки (количество потоков при этом будет зависеть от размера обрабатываемого массива). Создание потока — очень сложная операция, требующая значительных вычислительных затрат, поэтому потоки мы создадим до вызова функции. И так, поток, выполнивший область omp single добавит в пул одну или две задачи и завершится. Но мы должны дождаться пока эти задачи будут выполнены. При этом, добавлять задачи в пул будет не только этот поток, но любой другой поток (ведь он может взять из пула задачу и обработать часть массива). Оптимизированный вариант сортировки отличается от обычного лишь тем, что при небольшом (с точным значением можно поиграть) размере массива сортировка выполняется последовательно.
 +
  '''void''' quickSort('''double'''[] a, '''long''' n)
 +
    '''long''' i = 0, j = n
 +
    '''float'''  mid = a[n / 2]; // опорный элемент
 +
 +
    '''do'''
 +
      '''while''' (a[i] < mid) i++
 +
      '''while''' (a[j] > mid) j--
 +
 
 +
      '''if''' (i <= j)
 +
        swap(a[i], a[j])
 +
        i++ j--
 +
      '''while''' (i <= 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>2</tex> части с меньшими и большими элеменами с разделяющим ведущем пусть длина меньшей части <tex>n1</tex>. Алгоритм отправляет её на другой процессор сортироваться параллельно, а так как она короче, то и досортируется быстрее, значит время её сортировки не учитывается. Длина большей части <tex>N-n1</tex>, с этой частью мы проделываем точно такую же итерацию с разделителем <tex>n2</tex>. И так далее до момента, когда число свободных процессоров закончится, то есть до разделителя <tex>nk</tex>. Где <tex>[p / 100]=2^k</tex>.
 +
 
 +
<tex>T=(N+(N-n1)+(N-n1-n2)+...+(N-n1-...-nk))*t</tex>, где <tex>t</tex> - время перестановки.

Версия 21:59, 9 июня 2014

Распараллеливание простых сортировок

Быстрая параллельная сортировка

В алгоритме быстрой сортировки, исходный массив разбивается на 2 части, обработка которых ведется не зависимо (поэтому может выполняться параллельно). Задачи должны создаваться внутри параллельной области, однако если мы поместим директиву omp parallel внутрь функции, то у нас будут рекурсивно создаваться потоки (количество потоков при этом будет зависеть от размера обрабатываемого массива). Создание потока — очень сложная операция, требующая значительных вычислительных затрат, поэтому потоки мы создадим до вызова функции. И так, поток, выполнивший область omp single добавит в пул одну или две задачи и завершится. Но мы должны дождаться пока эти задачи будут выполнены. При этом, добавлять задачи в пул будет не только этот поток, но любой другой поток (ведь он может взять из пула задачу и обработать часть массива). Оптимизированный вариант сортировки отличается от обычного лишь тем, что при небольшом (с точным значением можно поиграть) размере массива сортировка выполняется последовательно.

 void quickSort(double[] a, long n) 
   long i = 0, j = n
   float  mid = a[n / 2]; // опорный элемент

   do 
     while (a[i] < mid) i++
     while (a[j] > mid) j--
  
     if (i <= j)
       swap(a[i], a[j])
       i++ j--
     while (i <= 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

Анализ эффективности параллельного алгоритма

Каждую итерацию массив делится случайно. На первой итерации при делении на [math]2[/math] части с меньшими и большими элеменами с разделяющим ведущем пусть длина меньшей части [math]n1[/math]. Алгоритм отправляет её на другой процессор сортироваться параллельно, а так как она короче, то и досортируется быстрее, значит время её сортировки не учитывается. Длина большей части [math]N-n1[/math], с этой частью мы проделываем точно такую же итерацию с разделителем [math]n2[/math]. И так далее до момента, когда число свободных процессоров закончится, то есть до разделителя [math]nk[/math]. Где [math][p / 100]=2^k[/math].

[math]T=(N+(N-n1)+(N-n1-n2)+...+(N-n1-...-nk))*t[/math], где [math]t[/math] - время перестановки.