内部选定排序循环的并行性跳过了几个数字

Question

我正在尝试制作一个程序，在那里你可以设置你想要的线程数量，它将用给定的数据和线程数量并行化选择排序算法。我知道在这种情况下我应该使用另一种算法，但这只是出于教育目的。因此，在选择排序算法中并行内部循环时，我遇到了一个问题——一些封闭的数字没有排序，但整个数组都被里面的几对数字分开了，我不知道为什么。

int* selectionSort(int arr[], int size, int numberOfThreads)
{
int i, j;
int me, n, min_idx;
bool canSwap = false;
#pragma omp parallel num_threads(numberOfThreads) private(i,j,me,n)
{
me = omp_get_thread_num();
n = omp_get_num_threads();
printf("Hello from %d/%dn", me, n);

for (i = 0; i < size - 1; i++) {
min_idx = i;
canSwap = true;
#pragma omp barrier
#pragma omp for
for (j = i + 1; j < size; j++) {
if (arr[j] < arr[min_idx])
min_idx = j;
//printf("I am %d processing %d,%dn", me, i, j);
}
printf("Min value %d ---- %d n", arr[min_idx], min_idx);
#pragma omp critical(swap)
if(canSwap)
{
swap(&arr[min_idx], &arr[i]);
canSwap = false;
}
#pragma omp barrier
}
}
return arr;
}

Answer 1

我发现问题是你不能真正并行化这个算法(好吧，至少在我这样做的时候(，因为我正在比较arr[j]和arr[min_idx]，min_idx的值有时会在这样一个特定的时间内被改变，使得其他线程将完成if (arr[j] < arr[min_idx])行，并且紧接着另一个线程将改变min_idx的值，这有时会使刚刚完成的if语句不再是true。