std :: sort намного быстрее, чем пользовательский алгоритм параллельной сортировки OpenMP - PullRequest
Новая
       7

std :: sort намного быстрее, чем пользовательский алгоритм параллельной сортировки OpenMP

0 голосов
/ 10 мая 2019

Я тестировал параллельную сортировку с использованием OpenMP. Я реализовал алгоритм сортировки по четным и четным в 3 раза быстрее, чем без OpenMP. Однако std :: sort по-прежнему работает намного быстрее: seq - 100 с, параллельное - 20 с, std :: sort - 0,05 с

Я пытался переместить #pragma omp параллельно для i-цикла, но это работало еще хуже и не сортировало вектор 

for (int i = 0; i < 100000; i++) {
        #pragma omp parallel for
        for (int j = (i % 2) ? 0 : 1; j < 100000 - 1; j += 2) {
            if (vec_[j] > vec_[j + 1]) {
                std::swap(vec_[j], vec_[j + 1]);
            }
        }
    }

Tbh, я ожидал, что параллельная нечетно-четная сортировка будет самой быстрой, но теперь я задаюсь вопросом - я делаю что-то не так, или это просто std :: sort настолько эффективен?

1 Ответ

5 голосов
/ 10 мая 2019

Ваш алгоритм O (n ^ 2) в общей выполненной работе. Используя k потоков, это самое большее делает это O (n ^ 2 / k).

std::sort - это O (n lg n). Если k не равно O (n / lg n), добавление новых потоков не будет продолжаться.

И даже если у вас есть куча нитей. NUMA в большинстве мегапоточных систем означает, что ваша память станет серьезной болью. Потоки не обращаются к одной и той же памяти в каждом цикле и фактически постоянно передают данные туда и обратно.

Примером того, как может ускорить вашу работу по сравнению с простым std :: sort, было бы разделение данных на K частей, std::sort каждый из K частей, а затем выполнение параллельное слияние этих частей. 

int data_count = 100000;
auto get_block_edge = [data_count](int i, int n) {
  return data_count * n / i;
};
int blocks = 0;
#pragma omp parallel
{
  blocks = omp_get_num_threads();
  int block = omp_get_thread_num();
  int start = get_block_edge( block, blocks );
  int finish = get_block_edge( block+1, blocks );
  std::sort( std::begin(vec_)+start, std::begin(vec_)+finish );
}

теперь у нас есть куча отсортированных блоков. Вам просто нужно объединить их. 

for (int merge_step = 1; merge_step < blocks; merge_step *= 2 )
{
  #pragma omp parallel for
  for (int i = 0; i < (blocks/2/merge_step); ++i) {
    int start = get_block_edge(i*2*merge_step, blocks);
    int mid = get_block_edge(i*2*merge_step+merge_step, blocks);
    int finish = get_block_edge(i*2*merge_step+2*merge_step, blocks);
    finish = std::min(finish, data_count);
    auto b = std::begin(vec_);
    std::inplace_merge( b+start, b+mid, b+finish );
  }
}

Я думаю, что это должно быть сильно параллельное слияние. Или, более вероятно, segfault, потому что у меня ошибка off-by-1.

Теперь, это все еще O (n) с бесконечным числом потоков, так как самое последнее слияние должно быть однопоточным. Обойти это, мягко говоря, сложно.

...