## parallelize a double recursion(mergesort)

General OpenMP discussion

### parallelize a double recursion(mergesort)

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

### Re: parallelize a double recursion(mergesort)

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: 746
Joined: Thu Jan 08, 2009 10:12 am
Location: EPCC, University of Edinburgh