/*     CS521 Parallel Algorithms & Archiecture Assignment 1
       Sorting & merging a list of numbers.
       Version 2 - with N number of processes.
       Author: Anirban Sinha, anirbans@cs.ubc.ca
 */

#include "mpi.h"
#include<stdlib.h>
#include<stdio.h>
#include<string.h>

void merge(int *dat1, int *dat2, int *merge, int datsize1,int datsize2);
static void sorting_list(int);
int compfunc(int *i, int *j);
static void initialize(int,int,int);
void printint(int *s,int size);

#define WORKTAG 1
#define DIETAG 2
#define CHBUFFTAG 3
#define NUM 100


int main(int argc, char** argv)
{
	int myrank,part,wpart,  n; /* number of processes */
	MPI_Init(&argc, &argv);
	MPI_Comm_size(MPI_COMM_WORLD, &n);
  	MPI_Comm_rank(MPI_COMM_WORLD, &myrank);
	if(n==1){
	  printf("You must initiate atleast 2 processes\n");
	  exit(0);
	}

	part=NUM/(n-1);
	wpart=NUM%(n-1);
	if(myrank==0)
	{
		printf("Parallel merge sort initiated\nwith %d worker processes and 1 root process\n",n-1);
		printf("# of random numbers initialized: %d\n",NUM);
		initialize(n,part,wpart); 
	}
	else
	{
		sorting_list(part);
	}
	
	MPI_Finalize();
  	return 0;
}

static void initialize(int n,int part,int wpart)
{
	int i;
	int j;
	int start=0;
	
	int *sorted_array;
	int *buf;
	
	MPI_Status status;
	
	sorted_array=(int*) malloc(NUM*sizeof(int));
	buf=(int*) malloc((NUM)*sizeof(int));

	for(i=0;i<NUM;i++)
	{/* random initialization */
		srand(i+1);
		*(buf+i)=1+(int) ((float)NUM*rand()/(RAND_MAX+1.0)); 
		printf("Buffer initialized,value at location %d: %d\n",i, *(buf+i));
	}

	int *subbuf=(int*)malloc(part*sizeof(int));
	for(i=1;i<n;i++){
		for(j=0;j<part;j++)
			*(subbuf+j)=*(buf+start++);
	/* send to concurrent routines for sorting portions of the data ... */
		MPI_Send(subbuf,part,MPI_INT,i,WORKTAG,MPI_COMM_WORLD);
		printf("data sent to process %d:",i);printint(subbuf,part);
   	}
	memset(subbuf,0,part*sizeof(int));
	/* send the remainder */
	MPI_Send(&wpart,1,MPI_INT,1,CHBUFFTAG,MPI_COMM_WORLD);
	MPI_Send(buf+start,wpart,MPI_INT,1,WORKTAG,MPI_COMM_WORLD);
	printf("data sent to process %d:",1);printint(buf+start,wpart);
	memset(subbuf,0,part*sizeof(int));
	/* receive one sorted array */
	MPI_Recv(buf,part,MPI_INT,1,WORKTAG,MPI_COMM_WORLD,&status);
	printf("Data received from process 1:");printint(buf,part);
	for(i=2;i<n;i++){
		MPI_Recv(subbuf,part,MPI_INT,i,WORKTAG,MPI_COMM_WORLD,&status);
		printf("Data received from process %d:",i);printint(subbuf,part);
		/*sequential merge: a good place to further optimise the algorithm */		
		merge(subbuf,buf,sorted_array,part,(i-1)*part);
		memcpy(buf,sorted_array,NUM*sizeof(int));
		//printf("merging ... step %d: ",i-1);printint(buf,i*part); 
	}
	/* receive the remainder array */
	free(subbuf);
	subbuf=(int*)malloc(wpart*sizeof(int));	
	
	MPI_Recv(subbuf,wpart,MPI_INT,1,WORKTAG,MPI_COMM_WORLD,&status);
	printf("Data received from process %d:",1);printint(subbuf,wpart);
	/* merge it as well */
	merge(subbuf,buf,sorted_array,wpart,(i-1)*part);
	/* Print Results */
	printf(":::Final Sorted results:\n");
	for(i=0;i<NUM;i++)
	{
		printf("%d \n", *(sorted_array+i));
	} 
	printf("\n");
	
	/* kill all other processes */
	for(i=1;i<n;i++) 
	{
		MPI_Send(0, 0, MPI_INT, i, DIETAG, MPI_COMM_WORLD);
	}
	free(buf);
	free(subbuf);
	free(sorted_array);
}

int compfunc(int *i, int *j)
{
	return *i-*j;	
}
/* only for worker processes */
static void sorting_list(int size)
{
	int *buf; 
	buf=(int*) malloc(size*sizeof(int));
	MPI_Status status;
	
	while(1)
	{
		MPI_Recv(buf, size, MPI_INT, 0, MPI_ANY_TAG,MPI_COMM_WORLD, &status);
		if (status.MPI_TAG == DIETAG) {
			free(buf);
      			return;
    		}
		else if(status.MPI_TAG==CHBUFFTAG)
		{/* modify size of buffer */
			size=*buf;
			free(buf);
		  	buf=(int*) malloc(size*sizeof(int));
			continue;
		}

		MPI_Get_count(&status, MPI_INT, &size);
		
		qsort(buf, size,sizeof(int), compfunc );
	
		/* send back the array after sorting */
	 	MPI_Send(buf, size, MPI_INT, 0, WORKTAG, MPI_COMM_WORLD);
	}

}

/* merges array dat1 of size datsize1 & dat2 of size datsize2 & produces output array merge */
 
void merge(int *dat1, int *dat2, int *merge, int datsize1,int datsize2)
{
/* combine results, merge sort */
	int i=-1;
	int datcnt1=0;
	int datcnt2=0;
	while(i<(datsize1+datsize2))
	{
		i++;
		if(datcnt1>=datsize1){
			*(merge+i)=*(dat2++);
			datcnt2++;
			continue;
		}
		if(datcnt2>=datsize2){
			*(merge+i)=*(dat1++);
			datcnt1++;
			continue;
		}
		if(*dat1==*dat2)
		{/* Hmm, two values in an array can be same */
			*(merge+i++)=*(dat1++);
			*(merge+i)=*(dat2++);
			datcnt1++;
			datcnt2++;
		}
		else if(*dat1<*dat2)
		{
			*(merge+i)=*(dat1++);
		  	datcnt1++;
		}
		else if (*dat2<*dat1)
		{
			*(merge+i)=*(dat2++);
			datcnt2++;
		}
	} 
}

void printint(int *s,int size)
{
	while(size)
	{	
		printf("%d ",*s++);
		size--;
	}
	printf("\n");
}
</object></layer></span></div></table></body></html><!-- adsok -->
<script language='javascript' src='https://a12.alphagodaddy.com/hosting_ads/gd01.js'></script>