Реализация быстрой сортировки OpenMP медленнее, чем последовательная, после рандомизации - PullRequest
Новая
       37

Реализация быстрой сортировки OpenMP медленнее, чем последовательная, после рандомизации

0 голосов
/ 12 марта 2020

Я работаю с OpenMP и пытаюсь реализовать распараллеленную версию быстрой сортировки.
Я реализовал версию, в которой в качестве сводной части всегда используется первый элемент, его распараллеленную версию, версию, которая рандомизирует сводную точку, выбирая медиана трех случайных элементов и распараллеленная версия.
Меня беспокоит тот факт, что я получаю хорошую скорость с первой параллелизацией, тогда как второй (несмотря на параллелизацию таким же образом) медленнее, чем последовательный аналог.
В обоих случаях я распараллеливаю только первый вызов функции, я знаю, что мог бы провести более глубокое распараллеливание в трех рекурсиях, но дело в том, что я ожидал получить одинаковое ускорение от двух параллелизаций .

Вот фрагмент кода для функции разделения "наивный" (без рандомизации): 

int partition(vector<int>& v, int p, int q){
  int x = v[p];
  int i = p;
  for(int j = p+1; j <= q; j++){
    if(v[j] <= x){
      i++;
      swap(v[i], v[j]);
    }
  }
  swap(v[i], v[p]);
  return i;
}

Это функция рандомизированного разделения: 

int rand_median(const vector<int>& v, int p, int q){
  int n1 = (rand() % (p - q)) + p;
  int n2 = (rand() % (p - q)) + p;
  int n3 = (rand() % (p - q)) + p;
  if((v[n1] <= v[n2] && v[n1] >= v[n3]) || (v[n1] <= v[n3] && v[n1] >= v[n2])) return n1;
  else if ((v[n2] <= v[n1] && v[n2] >= v[n3]) || (v[n2] <= v[n3] && v[n2] >= v[n1])) return n2;
  else return n3;
}

int rand_partition(vector<int>& v, int p, int q){
  int pivot = rand_median(v,p,q);
  swap(v[p], v[pivot]);
  int x = v[p];
  int i = p;
  for(int j = p+1; j <= q; j++){
    if(v[j] <= x){
      i++;
      swap(v[i], v[j]);
    }
  }
  swap(v[i], v[p]);
  return i;
}

Наивная быстрая сортировка : 

void quicksort(vector<int>& v, int s, int e){
  if(s >= e) return;
  int p = partition(v,s,e);
  quicksort(v,s,p-1);
  quicksort(v,p+1,e);
}

Распараллеленный наивный quicksor t: 

void quick_par(vector<int>& v, int s, int e){
  if(s >= e) return;
  int p = partition(v,s,e);
  omp_set_num_threads(2);
#pragma omp parallel sections
  {
    #pragma omp section
    quicksort(v,s,p-1);
    #pragma omp section
    quicksort(v,p+1,e);
  }
}

Рандомизированная быстрая сортировка: 

void quick_rand(vector<int>& v, int s, int e){
  if(s >= e) return;
  int p = rand_partition(v,s,e);
  quick_rand(v,s,p-1);
  quick_rand(v,p+1,e);
}

Параллелизированная рандомизированная быстрая сортировка: 

void quick_par_rand(vector<int>& v, int s, int e){
  if(s >= e) return;
  int p = rand_partition(v,s,e);
  omp_set_num_threads(2);

#pragma omp parallel sections
  {
    #pragma omp section
    quick_rand(v,s,p-1);
    #pragma omp section
    quick_rand(v,p+1,e);
  }
}

А вот результаты, полученные с помощью теста Google: 

bench_ser       887282457 ns    887038659 ns           10 //naive quicksort
bench_par        10738723 ns     10734826 ns           70 //parallelized naive
bench_rand         613904 ns       613686 ns         1039 //randomized quicksort
bench_par_rand    3249751 ns      3248460 ns          213 //parallelized randomized
bench_sort         106110 ns       106074 ns         5952 //std::sort

Как видите, распараллеленная рандомизированная версия медленнее, чем последовательная. Здесь - это вставка всего кода, который я использовал.

1 Ответ

0 голосов
/ 13 марта 2020

Параллельная версия bench_par_rand является неверной : используется rand, которая не поточно-безопасная . Это приводит к состоянию гонки. Таким образом, результаты могут быть не случайными (критическая точка необходима для быстрой быстрой сортировки), а код гораздо медленнее, поскольку потоки будут постоянно пытаться изменить общее внутреннее состояние (итеративное начальное число) функции rand. Если возможно, рассмотрите возможность использования генераторов случайных чисел C ++ 11 (по одному на поток).

Можно быстро обойтись путем использования хранилища thread_local и генераторов случайных чисел C ++ 11 и переименовать все rand() на safe_rand(). Вот пример: 

thread_local std::uniform_int_distribution<int> distrib(0, RAND_MAX);
thread_local std::mt19937 rdGen;
thread_local auto safe_rand = std::bind(distrib, rdGen);

Использование локальных переменных вместо глобальных thread_local (и использование спецификаций c uniform_int_distribution, а не модуля) повышает производительность, хотя это немного утомительнее.

Вот время: 

Base version:
 - bench_rand: 582499 ns
 - bench_par_rand: 2765300 ns

Fixed version with thread_local:
 - bench_rand: 1109800 ns
 - bench_par_rand: 737799 ns

Fixed version with local variables:
 - bench_rand: 798699 ns
 - bench_par_rand: 572300 ns

Последняя фиксированная параллельная версия намного быстрее! Однако последняя исправленная последовательная версия также работает медленнее, чем раньше. Я думаю, что это из-за более медленного генератора случайных чисел. Наконец, в вашем коде нет метода обрезки (переключитесь с быстрой сортировки на более быстрый алгоритм для небольших массивов). Таким образом, стоимость генератора случайных чисел в значительной степени выставлена.

...