PARALLEL BITONIC SORT IMPLEMENTED ON HYPERCUBE SOURCE CODE in C

The program implements Bitonic sort on a hypercube using 8 processors and input size array of 64.The unsorted array is initially statically assigned to each processor. Each of the processors sorts the local array in increasing order using built-in quick sort api of mpi-interface. Once the processors complete local sorting, they communicate and exchange data in a certain fashion to merge the local subsequences using compare-split operations instead of compare-exchange operations. The first (d^2 - d)/2=3 steps1 are for obtaining a full bitonic sequence and the last (d=3) steps are for sorting this Bitonic sequence.

#include
#include
#include
#include
#include
#include

int IncOrder(const void *e1,const void *e2)
{
return (*((int *)e1) - *((int *)e2));
}

CompareSplit(int nlocal,int elements[][8],int rank,int *relements,int *wspace,int keepsmall)
{
int i,j,k;
for(i=0;i wspace[i]=elements[rank][i];

if(keepsmall)
{
i=0;
j=0;
for(k=0;k {
if(j == nlocal || (i < nlocal && (wspace[i] < relements[j])) )
elements[rank][k] = wspace[i++];
else
elements[rank][k] = relements[j++];
}
}
else
{
i=nlocal-1;
j=nlocal-1;
for(k=nlocal-1;k>=0;k--)
{
if((i >=0 && (wspace[i] >= relements[j])) )
elements[rank][k] = wspace[i--];
else
elements[rank][k] = relements[j--];
}
}
}

main(int argc,char *argv[])
{
int i,j,nlocal,k;
int p,rank,n,partner,temp;
int *relements,*wspace;
int msb_i1,lsb_j,test_msb,test_lsb,keepsmall=0;
int elements[8][8]={
{55,26,51,60,43,64,54,33},
{22,7,13,18,2,17,1,14},
{56,49,29,39,37,35,53,48},
{20,6,10,24,15,9,21,3},
{28,44,63,34,62,38,58,40},
{16,19,23,4,11,12,5,8},
{36,50,41,47,57,25,32,31},
{45,42,30,46,61,27,52,59} };
MPI_Status status;

MPI_Init(&argc,&argv);
MPI_Comm_size(MPI_COMM_WORLD,&p);
MPI_Comm_rank(MPI_COMM_WORLD,&rank);

n = 64;

nlocal = n/p;

relements = (int *)malloc(nlocal*sizeof(int));
wspace = (int *)malloc(nlocal*sizeof(int));

/*Locally sort array of block of n/p elements at each process using built-in sort*/
qsort(elements[rank],nlocal,sizeof(int),IncOrder);

printf("Locally sorted array at Process %d\n",rank);
for(i=0;i printf("%d\t",elements[rank][i]);
printf("\n\n");

for(i=0;i<3;i++)
{
for(j=i;j>=0;j--)
{
temp = pow(2,j);
/*compute the Processor with which Communication will take place*/
partner = (rank ^ temp);

/*Extract the (i+1)th bit of Process-id (rank in our case)*/
test_msb = rank>>(i+1);
msb_i1=test_msb&1;

/*Extract the jth bit of Process-id (rank in our case)*/
test_lsb = rank>>j;
lsb_j=test_lsb&1;

if(msb_i1==lsb_j)
keepsmall = 1;
else
keepsmall = 0;

MPI_Send(elements[rank],nlocal,MPI_INT,partner,1,MPI_COMM_WORLD);
MPI_Recv(relements,nlocal,MPI_INT,partner,1,MPI_COMM_WORLD,&status);
CompareSplit(nlocal,elements,rank,relements,wspace,keepsmall);

}

}

printf("--------------Final Sorted array at Process %d--------------\n",rank);
for(i=0;i printf("%d\t",elements[rank][i]);
printf("\n");
printf("------------------------------------------------------------\n\n");

MPI_Finalize();
}//main