Sortowanie bąbelkowe z OpenMP

Witam. Chciałbym zrealizować sortowanie bąbelkowe dla ciągu liczb rzeczywistych z wykorzystaniem OpenMP. Jednak mam problem ze zrównolegleniem. Ponieważ nie zawsze zadziała poprawnie. Czy trzeba tutaj zrównoleglać drugiego fora też?

Mój kod:

 #include <stdio.h>
#include "omp.h"

int main()
{
int n=10;
double X[10] = {0.4, -1.7, 2.2, 3.4, 2.2, -8.1, 9.2, -100, 99.01, 9};
int i, j;
double tmp;
int a=0;
omp_set_num_threads(4);

//for(a =0; a<n; a++)
//printf("%.2f ,", X[a]);
//printf("\n");

#pragma omp parallel for default(none) private(i,j,tmp) shared(n, X)
		for(i = 0; i< n; i++)
			for(j=0; j< (n-1-i); j++)
			{
				#pragma omp flush(X)
				if(X[j]>X[j+1])
				{
					tmp = X[j+1];
					X[j+1] = X[j];
					X[j] = tmp;
				}
			}


for (j = 0; j<n; j++)
printf("%.2f, ", X[j]);
printf("\n");


return 0;
}

W tym kodzie wenętrzny for jest urachamiany równolegle - co znaczy, ze w kilku wątkach próbujesz zamieniać elementy dzielonej tablicy. To oczywiście prowadzi do błędów.
Po co w ogóle chcesz zrównoleglac bubble sorta? To typowo sekwencyjny algorytm. Jeżeli chcesz sobie poćwiczyć OpenMP to już lepiej spróbuj zrównoleglić sortowanie przez scalanie.

                                #pragma omp flush(X)

Wiem że się czepiam, i że kompilatory to łykają, ale zgodnie ze standardem języka, powinno się pisać

#                                pragma omp flush(X)

czyli # w pierwszej kolumnie, a dopiero potem może być odstęp.

0x200x20 napisał(a):

W tym kodzie wenętrzny for jest urachamiany równolegle - co znaczy, ze w kilku wątkach próbujesz zamieniać elementy dzielonej tablicy. To oczywiście prowadzi do błędów.
Po co w ogóle chcesz zrównoleglac bubble sorta? To typowo sekwencyjny algorytm. Jeżeli chcesz sobie poćwiczyć OpenMP to już lepiej spróbuj zrównoleglić sortowanie przez scalanie.

Próbuję się przed tym właśnie w jakiś sposób zabezpieczyć. Na przykład:

#include <stdio.h>
#include "omp.h"

int main()
{
int n=10;
double X[10] = {0.4, -1.7, 2.2, 3.4, 2.2, -8.1, 9.2, -100, 99.01, 9};
int i, j;
double tmp;
int a=0;
omp_set_num_threads(4);

//for(a =0; a<n; a++)
//printf("%.2f ,", X[a]);
//printf("\n");

#pragma omp parallel for default(none) private(i,j,tmp) shared(n, X)
	for(i = 0; i< n; i++)
		for(j=0; j< (n-1-i); j++)
		{
			#pragma omp flush(X)
			if(X[j]>X[j+1])
			{
				#pragma omp critical
				{
					if(X[j]>X[j+1])
					{
						tmp = X[j+1];
						X[j+1] = X[j];
						X[j] = tmp;
					}
				}
			}
		}

for (j = 0; j<n; j++)
printf("%.2f, ", X[j]);
printf("\n");


return 0;
}

Jednak critical nie pomaga. Gdzieś widziałem rozwiązanie, że ten drugi for też jest "#pragma omp parallel for". Niemniej to również nie daje poprawnego wyniku.

Co do potrzeby zrównoleglania bubblesorta, to powiedzmy, że mam postawione takie zadanie, które muszę zrealizować. Na pewno można zaoszczędzić na złożoności dzięki OpenMP.

Z góry dziękuję pomocnym

Jeżeli chcesz to mozesz sobie zrobic cos takiego:

#pragma omp parallel for private(i, j, tmp) shared(n, X)
for(i = 0; i< n; i++)
{
	#pragma omp critical
    for(j=0; j< n-1; j++)
    {
        if(X[j]>X[j+1])
        {
                tmp = X[j+1];
                X[j+1] = X[j];
                X[j] = tmp;
        }
    }
}

Tyle ze jest to calkowicie bezsensu bo tak na prawde prawde kod nie jest zrownoleglony (wewnetrzne petle wykonuja sie po kolei). Nie da sie zrownoleglic bubble sorta bez modyfikacji samego algorytmu - bubble sort jest po prostu sekwencyjny. Tu jest jakas zrownoleglona wersja: http://alecu.ase.ro/conferences/nat_conf_2005_ro_am.pdf - na twoim miejscu przepisal bym na C++ z OpenMP.

0x200x20 napisał(a):

Jeżeli chcesz to mozesz sobie zrobic cos takiego:

#pragma omp parallel for private(i, j, tmp) shared(n, X)
for(i = 0; i< n; i++)
{
	#pragma omp critical
    for(j=0; j< n-1; j++)
    {
        if(X[j]>X[j+1])
        {
                tmp = X[j+1];
                X[j+1] = X[j];
                X[j] = tmp;
        }
    }
}

Tyle ze jest to calkowicie bezsensu bo tak na prawde prawde kod nie jest zrownoleglony (wewnetrzne petle wykonuja sie po kolei). Nie da sie zrownoleglic bubble sorta bez modyfikacji samego algorytmu - bubble sort jest po prostu sekwencyjny. Tu jest jakas zrownoleglona wersja: http://alecu.ase.ro/conferences/nat_conf_2005_ro_am.pdf - na twoim miejscu przepisal bym na C++ z OpenMP.

Dziękuję za ten materiał. Powoli zaczynam rozumieć.
A czy takie rozwiązanie, gdzie parami dzielę między wątki dwa elementy ciągu ma sens? nie ma chyba możliwości brudnego zapisu, a powinno to przyspieszyć działanie programu?

#include<stdio.h>
#include<omp.h>

#define N 13

int main()
{
	int i, j;
	double temp, tab[] = {1.1, 2.3, -1.2, 9.2, 8.1, 7.8, 6.4, 5.0, 4.1, -33.2, 2.7, 1.1, 0};
	for(i = 0; i < N; i++)
	{
		#pragma omp parallel for num_threads(4) private(temp)
		for (j = 0; j < N - 1; j += 2)
			if (tab[j] > tab[j+1])
			{
				temp = tab[j];
				tab[j] = tab[j+1];
				tab[j+1] = temp;
			}
		#pragma omp parallel for num_threads(4) private(temp)
		for (j = 1; j < N - 1; j += 2)
			if (tab[j] > tab[j+1])
			{
				temp = tab[j];
				tab[j] = tab[j+1];
				tab[j+1] = temp;
			}
	}
	for(i = 0; i < N; i++)
		printf("%.2f ", tab[i]);
	printf("\n");
}

Ogolnie nie ma sensu - nie otrzymasz w ten sposob posortowanego ciagu... chyba ze zastosujesz scalanie dwoch posortowanych ciagow w jeden posortowany ciag. A to jest zaczątek sortowania przez scalanie, ktore dobrze sie zrownolegla, ale ktore juz nie jest sortowaniem babelkowym.
Przeklepany algorytm z wczesniej wymienionego linku:

#include <cstdio>
#include <omp.h>
#include <utility>
 
int main()
{
	static const int N = 10;
	double X[N] = {0.4, -1.7, 2.2, 3.4, 2.2, -8.1, 9.2, -100, 99.01, 9};


	for(int k = 0; k < N-1; k++)
	{
		if(k % 2 == 0)
		{
			for(int i = 0; i <= N/2-1; i++)
			{
				if(X[2*i] > X[2*i+1]) 
					std::swap(X[2*i], X[2*i+1]);
			}
		}
		else
		{
			for(int i = 0; i <= N/2-2; i++)
			{
				if(X[2*i+1] > X[2*i+2]) 
					std::swap(X[2*i+1], X[2*i+2]);
			}
		}
	}
 
	for (int j = 0; j<N; j++)
		std::printf("%.2f, ", X[j]);
 
	return 0;
}

Jedyne co musisz zrobić to zrownoleglic 2 wewnetrzne petle przy uzyciu OpenMP (banał). Działa to tak, że w parzystej iteracji sortujesz parzyste elementy i sąsiadów parzystych elementów, a w nieparzystej - nieparzyste elementy i ich sąsiadów.

Moim zdaniem kod z 20:08 ma szansę działać. Przynajmniej dla danych przykładowych działa: http://ideone.com/gpE5Mr
Jak ktoś ma kontrprzykład to niech zarzuci :P

Wibowit napisał(a):

Moim zdaniem kod z 20:08 ma szansę działać. Przynajmniej dla danych przykładowych działa: http://ideone.com/gpE5Mr
Jak ktoś ma kontrprzykład to niech zarzuci :P

Działa. Testowałem 1000 razy dla 1000000 liczb. Niemniej działa wolniej od sekwencyjnego :) Poprawiłem według wskazówek kolegi i wszystko śmiga z lepszą złożonością.