OpenMP, zrównoleglenie quicksort

0

Cześć, chciałbym zrównoleglić sortowanie quicksort bazując na bibliotece OpenMP. Czytałem o bibliotece, zapoznałem się z klauzalami, dyrektywami czy konstrukcjami, ale nadal nie wiem od czego zacząć.

Próbowałem różnych metody użycia OpenMP i za każdym razem występował jakiś błąd lub czas sortowania równoległego nie różnił się od czasu sortowania szeregowo. Mógłby mi ktoś doradzić od czego powinienem zacząć? Na pewno od zrównoleglenia instrukcji for, ale jednak.... to nic nie daje:

Mam następującą funkcję:

void zamiana(int &x, int &y)

{
	int pom;
	pom = x;
	x = y;
	y = pom;
}

 void szybkieszeregowo(int a[], int pocz, int kon)
{
	//Sortowanie tablicy qsort
	int klucz, s;
	if (pocz < kon)
	{
		klucz = a[pocz]; //klucz osiowy
		s = pocz;
		int i;

		for (i = pocz + 1; i <= kon; i++)
			if (a[i] < klucz)
			{
				s++;
				zamiana(a[i], a[s]);
			}

		zamiana(a[pocz], a[s]);	

		#pragma omp parallel sections
		{
			#pragma omp section
			{
				szybkieszeregowo(a, pocz, s - 1);
			}

			#pragma omp section
			{
				szybkieszeregowo(a, s + 1, kon);
			}
		}
	}
}
0
  1. Sprawdź czy na pewno kompilujesz z openmp i czy twój kompilator go wspiera.
  2. Dziwne że w tym przypadku openMP nie jest gorsze od wywołania liniowego, zrównoleglasz każde wywołani rekurencyjne, za duży narzut na wątki. Dochodzi do tego jeszcze fakt że sortowanie nie jest zbyt dobrym przypadkiem na użycie wielu watków, dużo operacji po pamięci mało obliczeń. Lepiej spróbuj jakiś algorytm z dużym narzutem na CPU, efekty będą bardziej widoczne.
0

To Ci się nie wykona zrównoleglone bo masz części wspólne w danych i rekurencyjne wołanie funkcji. Chyba najrozsądniejszym rozwiązaniem jest to (oczywiście nie przez MPI a OpenMP) https://github.com/danielpetroianu/COSP_MPI/wiki/Hyperquicksort

1 użytkowników online, w tym zalogowanych: 0, gości: 1