Обсуждение:PSRS-сортировка

Материал из Викиконспекты
Перейти к: навигация, поиск

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

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

В алгоритме быстрой сортировки, исходный массив разбивается на 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]\mathrm {spawn}[/math] запускает новый поток, а оператор [math]\mathrm {sync}[/math] ожидает завершения этого потока.

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

Каждую итерацию массив делится случайно. На первой итерации при делении на [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] - время перестановки.