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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 2: Строка 2:
 
===Быстрая параллельная сортировка===
 
===Быстрая параллельная сортировка===
 
В алгоритме быстрой сортировки, исходный массив разбивается на 2 части, обработка которых ведется не зависимо (поэтому может выполняться параллельно). Задачи должны создаваться внутри параллельной области, однако если мы поместим директиву omp parallel внутрь функции, то у нас будут рекурсивно создаваться потоки (количество потоков при этом будет зависеть от размера обрабатываемого массива). Создание потока — очень сложная операция, требующая значительных вычислительных затрат, поэтому потоки мы создадим до вызова функции. И так, поток, выполнивший область omp single добавит в пул одну или две задачи и завершится. Но мы должны дождаться пока эти задачи будут выполнены. При этом, добавлять задачи в пул будет не только этот поток, но любой другой поток (ведь он может взять из пула задачу и обработать часть массива). Оптимизированный вариант сортировки отличается от обычного лишь тем, что при небольшом (с точным значением можно поиграть) размере массива сортировка выполняется последовательно.
 
В алгоритме быстрой сортировки, исходный массив разбивается на 2 части, обработка которых ведется не зависимо (поэтому может выполняться параллельно). Задачи должны создаваться внутри параллельной области, однако если мы поместим директиву omp parallel внутрь функции, то у нас будут рекурсивно создаваться потоки (количество потоков при этом будет зависеть от размера обрабатываемого массива). Создание потока — очень сложная операция, требующая значительных вычислительных затрат, поэтому потоки мы создадим до вызова функции. И так, поток, выполнивший область omp single добавит в пул одну или две задачи и завершится. Но мы должны дождаться пока эти задачи будут выполнены. При этом, добавлять задачи в пул будет не только этот поток, но любой другой поток (ведь он может взять из пула задачу и обработать часть массива). Оптимизированный вариант сортировки отличается от обычного лишь тем, что при небольшом (с точным значением можно поиграть) размере массива сортировка выполняется последовательно.
   '''void''' quickSort('''double'''[] a, '''long''' n)  
+
   '''void''' quickSort('''int'''[] a, '''long''' n)  
 
     '''long''' i = 0, j = n
 
     '''long''' i = 0, j = n
     '''float'''  mid = a[n / 2]; // опорный элемент
+
     '''int'''  mid = a['''Random'''(n)]; // опорный элемент
 
   
 
   
 
     '''do'''  
 
     '''do'''  
Строка 10: Строка 10:
 
       '''while''' (a[j] > mid) j--
 
       '''while''' (a[j] > mid) j--
 
    
 
    
       '''if''' (i <= j)
+
       '''if''' (i <tex>  \leqslant </tex> j)
 
         swap(a[i], a[j])
 
         swap(a[i], a[j])
 
         i++ j--
 
         i++ j--
       '''while''' (i <= j);
+
       '''while''' (i <tex>  \leqslant </tex> j);
 
   
 
   
 
     '''if''' (n < 100)  // если размер массива меньше 100
 
     '''if''' (n < 100)  // если размер массива меньше 100

Версия 22:13, 9 июня 2014

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

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

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

 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 [math]  \leqslant [/math] j)
       swap(a[i], a[j])
       i++ j--
     while (i [math]  \leqslant [/math] 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] - время перестановки.