HPC Assignment #1 2013 - Spring NUCES FAST Karachi Pakistan Parallel Sorting Using MPI Note: Published after the deadline

parallelsort_mpi_asad

/*
Parallel Sorting using MPI
Author: Asad Memon
*/

#include <stdio.h>
#include <mpi.h>
#include <stdlib.h>
#include <math.h>
#include <iostream>
#include <time.h>

//#define N 200
#define MASTER 0  	/* taskid of first task */

int max(int x, int y);
void merge_helper(int *input, int left, int right, int *scratch);
int mergesort(int *input, int size);

void bubble_sort(int list[], int n);

int* GenerateRandomArr(int size,int max)
{
	int *temp = new int[size];//(int*) malloc (size+1);
	for (int i=0;i<size;i++)
	{
		temp[i] = rand()%max;
	}
	return temp;
}

void send(int* arr, int chunksize, int rank)
{
//char status[100];
MPI_Send(arr, chunksize, MPI_INT, rank, 1, MPI_COMM_WORLD); 
}
void recv(int* arr, int chunksize, int rank)
{
MPI_Status status;
MPI_Recv(arr, chunksize, MPI_INT, rank, 1, MPI_COMM_WORLD,&status);
}

int main(int argc, char** argv) {
    int myrank, nprocs;

    MPI_Init(&argc, &argv);
    MPI_Comm_size(MPI_COMM_WORLD, &nprocs);
    MPI_Comm_rank(MPI_COMM_WORLD, &myrank);

    for (int n=1;n<5;n++)
    {
    	int N = 5000*n;
    	int chunksize = N / (nprocs);
    	int* arr = new int[chunksize]; 
    	int* randarr=GenerateRandomArr(N,20000); 
    	double begin,end;

    	
    	//TIMING START FROM HERE
    	if (myrank==MASTER)	
    		{
    			printf("SORTING ARRAY OF SIZE: %d\n",N );
    			begin =  MPI_Wtime();
    		}

    	/*SEND DATA TO ALL NODES*/
    	// Scatter the random numbers to all processes
    	MPI_Scatter(randarr, chunksize, MPI_INT, arr,
    	            chunksize, MPI_INT, 0, MPI_COMM_WORLD);

    	/*SORT UR CHUNK NOW*/
    	bubble_sort(arr,chunksize); //bubble to slow down the processing to see the time differences much better
    	
    	//printf("gathering..\n");
    	/*NOW RETURN ALL DATA TO MASTER*/
    	int* result=0;// = new int[N];
    	if (myrank==MASTER) result = new int[N];
    	//result = {0};
    	MPI_Gather(arr, chunksize, MPI_INT, result, chunksize, MPI_INT, MASTER, MPI_COMM_WORLD); 

       //printf("gathered\n");

    	if (myrank==MASTER){
    		mergesort(result,N-1);
    		//TIMING ENDS HERE
    		end =  MPI_Wtime();
    		double dif = (end - begin);// / CLOCKS_PER_SEC;
    		printf ("Elasped time\t %f \t sec.\n", dif );
    		
    		//printf("FINAL RESULT AT MASTER NODE: \n");
    		//showVector(result,N,0);
    		
    		delete(result);
    	}

        delete(arr);
    	delete (randarr);
    }

    MPI_Finalize();

    return 0;
}


/*BUBBLE SORT
used to slow down the sorting a bit..to actually see the difference
*/
void bubble_sort(int list[], int n)
{
  long c, d, t;
 
  for (c = 0 ; c < ( n - 1 ); c++)
  {
    for (d = 0 ; d < n - c - 1; d++)
    {
      if (list[d] > list[d+1])
      {
        /* Swapping */
 
        t         = list[d];
        list[d]   = list[d+1];
        list[d+1] = t;
      }
    }
  }
}

/*MERGE SORT CODE
Implementation from http://www.cprogramming.com/tutorial/computersciencetheory/merge.html
*/

/* Helper function for finding the max of two numbers */
int max(int x, int y)
{
    if(x > y)
    {
        return x;
    }
    else
    {
        return y;
    }
}

/* left is the index of the leftmost element of the subarray; right is one
 * past the index of the rightmost element */
void merge_helper(int *input, int left, int right, int *scratch)
{
    /* base case: one element */
    if(right == left + 1)
    {
        return;
    }
    else
    {
        int i = 0;
        int length = right - left;
        int midpoint_distance = length/2;
        /* l and r are to the positions in the left and right subarrays */
        int l = left, r = left + midpoint_distance;

        /* sort each subarray */
        merge_helper(input, left, left + midpoint_distance, scratch);
        merge_helper(input, left + midpoint_distance, right, scratch);

        /* merge the arrays together using scratch for temporary storage */ 
        for(i = 0; i < length; i++)
        {
            /* Check to see if any elements remain in the left array; if so,
             * we check if there are any elements left in the right array; if
             * so, we compare them.  Otherwise, we know that the merge must
             * use take the element from the left array */
            if(l < left + midpoint_distance && 
                    (r == right || max(input[l], input[r]) == input[l]))
            {
                scratch[i] = input[l];
                l++;
            }
            else
            {
                scratch[i] = input[r];
                r++;
            }
        }
        /* Copy the sorted subarray back to the input */
        for(i = left; i < right; i++)
        {
            input[i] = scratch[i - left];
        }
    }
}

/* mergesort returns true on success.  Note that in C++, you could also
 * replace malloc with new and if memory allocation fails, an exception will
 * be thrown.  If we don't allocate a scratch array here, what happens? 
 *
 * Elements are sorted in reverse order -- greatest to least */

int mergesort(int *input, int size)
{
    int *scratch = (int *)malloc(size * sizeof(int));
    if(scratch != NULL)
    {
        merge_helper(input, 0, size, scratch);
        free(scratch);
        return 1;
    }
    else
    {
        return 0;
    }
}