Параллельный qsort using openMP

Question

Я пытаюсь распараллелить функцию qsort() в C++ с помощью openMP, но у меня есть некоторые проблемы. Для всех, для большого количества элементов для сортировки (ex: V = 1000) qsort вообще не работает, я никогда не выхожу из этой функции (бесконечный цикл). Затем я замечаю, что моя параллельная версия qsort намного медленнее, чем серийная. Кто-нибудь может мне помочь? Здесь код: https://dpaste.de/EaH0.

здесь среднее время, прошедшее, где kruscalP является параллельная версия: благодаря

Answer 1

У вас есть несколько условий гонки в коде, когда вы пишете в A, exch0 и exch1, которые все совместно. Мало того, что это может ухудшить производительность, скорее всего, даст неправильный результат. К сожалению, вы должны использовать критический раздел, чтобы исправить это, что также может повредить производительность, но, по крайней мере, это даст правильный результат.

#pragma omp for  
for (i = 0; i < N-1; i += 2) { 
    #pragma critical 
    { 
     if (A[i].weight > A[i+1].weight) { 
      temp = A[i]; 
      A[i] = A[i+1]; 
      A[i+1] = temp; 
      exch0 = 1; 
     } 
    } 
} 

То же самое касается следующего цикла цикла. Если вы хотите сделать это эффективно, вам придется изменить свой алгоритм. Возможно, рассмотрим сортировку слияния.