Rekurencja + OpenMP (sortowanie przez scalanie)

W jaki sposób mogę zrównoleglić taką funkcję:

// Procedura sortująca
//--------------------

void MergeSort(int i_p, int i_k)
{
  int i_s,i1,i2,i;

  i_s = (i_p + i_k + 1) / 2;
  if(i_s - i_p > 1) MergeSort(i_p, i_s - 1);
  if(i_k - i_s > 0) MergeSort(i_s, i_k);
  i1 = i_p; i2 = i_s;
  for(i = i_p; i <= i_k; i++)
    p[i] = ((i1 == i_s) || ((i2 <= i_k) && (d[i1] > d[i2]))) ? d[i2++] : d[i1++];
  for(i = i_p; i <= i_k; i++) d[i] = p[i];
}

Poszukałem w samouczkach jednak zazwyczaj używa się OpenMP to pętli for itp.

ja bym zmienił rekurencję drzewiastą na bardziej liniową, tzn. najpierw posortować po 2 elementy, potem 4 (scalając posortowane pary), następnie 8 itd. Powinno to się dać ładnie zrównoleglić.

Edit: do tego nie umiesz używać google: http://www.google.pl/search?q=openmp+mergesort

A nie lepiej puścić równolegle kilka sortów (np. merge sort) na podzakresach a potem to scalić np. przy pomocy insertion sort?

Witam. Napisałem program jednak nie rozumiem czemu po wykonaniu:

		int nr_threads = omp_get_num_threads(); 
		printf("Dostepnych jest %d watki.\n", nr_threads); 

Wyświetla mi: Dostepnych jest 1 watki.
Procesor mam dwurdzeniowy.

Cały kod wygląda tak:

#include <Windows.h>
#include <stdio.h>
#include <cstdlib>
#include <stdlib.h>
#include <time.h>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <omp.h>


using namespace std;


void merge(int *src, int* dst, int l, int m, int r){
    int i = l, j = m;
    int d = l;

       for (d=l; d<r; d++) 
	   {
			if ( j < r && (i == m || src[i] > src[j]) )
			{
				dst[d] = src[j++];
			}
			else
			{
				dst[d] = src[i++];
			}
	}
}

void merge_ww(int *src, int* dst, int l, int m, int r){
    int i = l, j = m;
    int d = l;

	#pragma omp parallel for
       for (d=l; d<r; d++) 
	   {
			if ( j < r && (i == m || src[i] > src[j]) )
			{
				dst[d] = src[j++];
			}
			else
			{
				dst[d] = src[i++];
			}
	}
}
 
void sort(int *tab, int n){
    
	int gap = 1;
    int *tab0 = tab;
    int *tab2 = new int[n];
	int i;

		for (gap = 1; gap < n; gap *= 2)
		{
			for (i = 0; i < n; i += gap * 2)
			{
				merge(tab, tab2, i, i + gap, min(i + 2 * gap, n));
			}

			int *tmp = tab2; 
			tab2 = tab;
			tab = tmp;
		}

    if (tab != tab0)
    {
        memcpy(tab0, tab, n * sizeof(int));
        delete []tab;
    }else delete []tab2;

}
 
double GetTime()
{
  long long f,t;
  QueryPerformanceFrequency((PLARGE_INTEGER)&f);
  QueryPerformanceCounter((PLARGE_INTEGER)&t);
  return (double)t/(double)f;
}

int main()
{
	long int N=500000;
	int petle=100;
	int *d = new int[N];
	int *d1 = new int[N];
	int *d2 = new int[N];
	int *d_k = new int[N];
	double t1,t2;
	int *d_b = new int[N];
	double T_W=0, T_BW=0;
	double srednia=0;

	srand((unsigned)time(NULL));

		
		int nr_threads = omp_get_num_threads(); 
		printf("Dostepnych jest %d watki.\nLicze!\n", nr_threads);

	for(int a=0; a<petle; a++)
	{
	for(int i = 0; i < N; i++) d[i] = rand() % 100;

		for(int i = 0; i < N/2; i++) 
		{
			d1[i]=d[i];
		}
		for(int i = N/2; i < N; i++) 
		{
			d2[i-N/2]=d[i];
		}

	for(int i=0; i<N; i++)
	{
		d_b[i]=d[i];
	}


			t1=GetTime();

			#pragma omp parallel sections
			{
				#pragma omp section
					{sort(d1,N/2);}
				#pragma omp section
					{sort(d2,N/2);}
			}


			#pragma omp parallel sections
			{
				#pragma omp section
					{for (int i=0; i<N/2; i++) d[i]=d1[i];}
				#pragma omp section
					{for (int i=N/2; i<N; i++) d[i]=d2[i-N/2];}
			}

			merge(d, d_k, 0, N/2, N);

			t2=GetTime();

	T_W=t2-t1;
   // printf("Czas wykonania funkcji wielowatkowo %f. \n", t2-t1);

	/*cout << "Posortowana tablica: "<<endl;
	for(int i = 0; i < N; i++) cout << setw(4) << d_k[i];
	cout << endl <<endl <<endl;*/

//----------------------------------------------------------------

	t1=GetTime();
	sort(d_b,N);
	t2=GetTime();

	T_BW=t2-t1;
	srednia+=T_BW/T_W;
	//printf("Czas wykonania funkcji bez watkow %f. \n", t2-t1);
	}

	/*cout << "Posortowana tablica: "<<endl;
	for(int i = 0; i < N; i++) cout << setw(4) << d_b[i];
	cout << endl <<endl <<endl;*/

	printf("Program wielowatkowy wykonuje sie srednio: %f razy szybciej. \n", srednia/petle);

    system("pause");
	return 0;
}

Jednak czas wykonywania dwu wątkowej części nie jest mocno krótszy. Co myślicie, że mógłbym poradzić?
Zrównoleglić funkcje marge chyba też by się przydało ale nie wiem jak :(.

Po wykonaniu mojego programu wyświetla się:

Dostepnych jest 1 watki.
Licze!
Program wielowatkowy wykonuje sie srednio: 1.376767 razy szybciej.
Aby kontynuować, naciśnij dowolny klawisz . . .

Usuń kopiowanie:

                                #pragma omp section
                                        {for (int i=0; i<N/2; i++) d[i]=d1[i];}
                                #pragma omp section
                                        {for (int i=N/2; i<N; i++) d[i]=d2[i-N/2];}

To wzrośnie trochę wydajność. Zamiast tego niech merge() działa na dwóch strukturach wejściowych.

Program działa Ci na 2 rdzeniach / wątkach, tylko nie doczytałeś opisu funkcji:

The omp_get_num_threads function returns the number of threads currently in the team executing the parallel region from which it is called.