parallelize a double recursion(mergesort)

General OpenMP discussion

parallelize a double recursion(mergesort)

Postby omg » Sun Apr 22, 2012 5:24 am

why this code runs slower than serial one???????
#include<stdio.h>
#include<stdlib.h>
#include<omp.h>
static int m=0,e=0;
void swap(int *a,int *b)
{
int temp=*a;
*a=*b;
*b=temp;
}
int bin(int x,int t[],int p,int r)
{
int mid,low=p,
high=r+1;
while(low<high)
{
mid=(low+high)/2;
if(x<=t[mid])
high=mid;
else
low=mid+1;
}
return high;
}
void merge(int t[],int p1,int r1,int p2,int r2,int a[],int p3)
{
int q1,q2,q3,
n1=r1-p1+1,
n2=r2-p2+1;
if(n1<n2)
{
swap(&n1,&n2);
swap(&p1,&p2);
swap(&r2,&r1);
}
if(n1==0)
return;
q1=(p1+r1)/2;
q2=bin(t[q1],t,p2,r2);
q3=p3+q1-p1+q2-p2;
a[q3]=t[q1];




merge(t,p1,q1-1,p2,q2-1,a,p3);


merge(t,q1+1,r1,q2,r2,a,q3+1);


}
void ms(int a[],int p,int r,int b[],int s)
{
int q,q1,n=r-p+1;
int t[15000];
if(n==1)
{
b[s]=a[p];
return;
}
q=(p+r)/2;
q1=q-p+1;
#pragma omp parallel
{

#pragma omp sections nowait
{
ms(a,p,q,t,1);
}

#pragma omp sections nowait
{
ms(a,q+1,r,t,q1+1);
}
}
merge(t,1,q1,q1+1,n,b,s);
}
main()
{
int a[21000],b[15000];
int i,k=0,n,ch;

for(n=2;n<1000;n+=20)
{
for(i=0;i<n;i++)
a[i]=k+=10;
ms(a,0,n-1,b,0);
printf("%d\t%d\t",n);


for(i=0;i<n;i++)
a[i]=k-=10;
ms(a,0,n-1,b,0);
printf("%d\t");
for(i=0;i<n;i++)
{
srand(i);
a[i]=random();
}
ms(a,0,n-1,b,0);
printf("%d\n");


}
}
Don,t worry about merge....
omg
 
Posts: 1
Joined: Sun Apr 22, 2012 5:07 am

Re: parallelize a double recursion(mergesort)

Postby MarkB » Mon Apr 23, 2012 4:28 am

I see some modest speedup on two threads for the larger values of n. For smaller values of n the overhead of parallel regions is too large, and this dominates the overall execution time. You would likely be able to reduce overheads, and have better control over the number of threads being used, by using nested tasks instead of nested parallel regions.
MarkB
 
Posts: 408
Joined: Thu Jan 08, 2009 10:12 am


Return to Using OpenMP

Who is online

Users browsing this forum: Google [Bot] and 2 guests