Итак, здесь есть ряд проблем.
Итак, во-первых, как уже указывалось, i и j (и temp) должны быть частными;м и нужно делиться.Полезно сделать с openmp использование default (none), чтобы вы были вынуждены продумать, что делает каждая переменная, которую вы используете в параллельном разделе, и какой она должна быть.Так что
#pragma omp parallel for private (i,j,temp) shared(a,m) default(none)
- хорошее начало.В частности, создание m private - это беда, потому что это означает, что m не определено внутри параллельной области.Между прочим, цикл должен начинаться с m = n / 2, а не с m = 2.
Кроме того, вам не нужна критическая область - или вы не должны это делать для сортировки оболочки,Проблема, которую мы увидим через секунду, заключается не в том, что несколько потоков работают над одними и теми же элементами.Поэтому, если вы избавитесь от этих вещей, вы получите что-то, что почти работает, но не всегда.И это подводит нас к более фундаментальной проблеме.
Способ работы сортировки оболочки заключается в том, что вы разбиваете массив на множество (здесь, m) подмассивов и вставляете-сортировать их (очень быстро для небольших массивов), а затем собрать заново;затем продолжайте, разбивая их на все меньшее и меньшее количество подмассивов и сортировку вставок (очень быстро, потому что они частично отсортированы).Сортировка этих множества подмассивов - это нечто, что можно сделать параллельно.(На практике проблема с памятью будет проблемой при таком простом подходе, но все же).
Теперь код, который вы получили, делает это в последовательном режиме, но на него нельзя рассчитывать, если вы просто обернете цикл j в omp parallel for.Причина в том, что каждая итерация в цикле j делает один шаг одного из видов вставки.Итерация цикла j + m делает следующий шаг.Но нет никакой гарантии, что они сделаны одним и тем же потоком или по порядку!Если другой поток уже выполнил j + m-ю итерацию до того, как первая выполнила j-ю, тогда сортировка вставки испорчена, и сортировка не удалась.
Таким образом, способ заставить эту работу переписатьсортировка оболочки, чтобы сделать параллелизм более явным - чтобы не разбивать сортировку вставкой на несколько последовательных шагов.
#include <stdlib.h>
#include <stdio.h>
#include <sys/time.h>
void insertionsort(int a[], int n, int stride) {
for (int j=stride; j<n; j+=stride) {
int key = a[j];
int i = j - stride;
while (i >= 0 && a[i] > key) {
a[i+stride] = a[i];
i-=stride;
}
a[i+stride] = key;
}
}
void shellsort(int a[], int n)
{
int i, m;
for(m = n/2; m > 0; m /= 2)
{
#pragma omp parallel for shared(a,m,n) private (i) default(none)
for(i = 0; i < m; i++)
insertionsort(&(a[i]), n-i, m);
}
}
void printlist(char *s, int a[], int n) {
printf("%s\n",s);
for (int i=0; i<n; i++) {
printf("%d ", a[i]);
}
printf("\n");
}
int checklist(int a[], int n) {
int result = 0;
for (int i=0; i<n; i++) {
if (a[i] != i) {
result++;
}
}
return result;
}
void seedprng() {
struct timeval t;
/* seed prng */
gettimeofday(&t, NULL);
srand((unsigned int)(1000000*(t.tv_sec)+t.tv_usec));
}
int main(int argc, char **argv) {
const int n=100;
int *data;
int missorted;
data = (int *)malloc(n*sizeof(int));
for (int i=0; i<n; i++)
data[i] = i;
seedprng();
/* shuffle */
for (int i=0; i<n; i++) {
int i1 = rand() % n;
int i2 = rand() % n;
int tmp = data[i1];
data[i1] = data[i2];
data[i2] = tmp;
}
printlist("Unsorted List:",data,n);
shellsort2(data,n);
printlist("Sorted List:",data,n);
missorted = checklist(data,n);
if (missorted != 0) printf("%d missorted nubmers\n",missorted);
return 0;
}