Hi Guys,

I have an issue with my program. I am trying to implement bitonic sort parallel algorithm using MPI.

The issue is like i am able to sort upto 1000000 array elements.. but, if i increase it to 10000000 or 100000000 the processors are not able to handle it.

Please help me.

Cheers,

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

#define MAX_SIZE 524288
#define arrayElements 1000000

int temp[MAX_SIZE];
int array1[MAX_SIZE];

//extern time( double* );

int compare(const int *p, const int *q);
void  merge_even(int elements, int array[], int temp[]);
void  merge_odd(int elements, int array[], int temp[]);
int log_2(int x);


int main(int argc, char *argv[]){

	int i, j, k;
	int elements;
	int nproc, rank;
	int* array, *tmp, buf[MAX_SIZE];
	int mask, mask2, partner, dim, bl;

	struct timeval tim;
	MPI_Request request, request_array;
	MPI_Status status;
//Initializze the MPI
	

	MPI_Init(&argc, &argv);
	MPI_Comm_rank(MPI_COMM_WORLD, &rank);
	MPI_Comm_size(MPI_COMM_WORLD, &nproc);
/*
	if(rank == 0)
	{
		printf("Plesae enter the number of elements \n");
		scanf("%d", arrayElements);
		printf("debug\n");
	}
*/
//	MPI_Bcast(&arrayElements, 1, MPI_INT, 0, MPI_COMM_WORLD);

	elements = (arrayElements/nproc);

	array=(int*) malloc(elements * sizeof(int)); 

	srand((double) time(NULL));
	gettimeofday(&tim, NULL);
	double t1=tim.tv_sec+(tim.tv_usec/1000000.0);

	MPI_Buffer_attach(buf, MAX_SIZE);
	if(rank == 0)
	{
		tmp = (int*) malloc(elements * sizeof(int));
		
		for(i=0; i<elements; i++)
		{
			array[i] = rand()%arrayElements;
		}
			
		for(j=1; j<nproc; j++)
		{
			for(i=0; i<elements; i++)		
			{
				tmp[i] = rand()%arrayElements;
			}
		MPI_Send(tmp, elements,MPI_INT, j, 50, MPI_COMM_WORLD);
//		MPI_Wait(&request, &status);
		}
//		MPI_Wait(&request, &status);
		free(tmp);
	}
	else
	{
		MPI_Recv(array, elements, MPI_INT, 0, 50, MPI_COMM_WORLD, &status);
	}


	qsort(array, elements, sizeof(int), (int(*)(const void*, const void*))(compare)); 

	for (i = 2, mask = 2; i <= nproc; i *= 2, mask = mask << 1) {
	    dim = log_2(i);
	    mask2 = 1 << (dim - 1);

	if ((rank & mask) == 0) 
	{
		for (j = 0; j < dim; j++) 
		{
		        partner = rank ^ mask2;
		        if (rank < partner) 
			{
		          MPI_Sendrecv(array, elements, MPI_INT, partner, 100,
                	  temp, elements, MPI_INT, partner, 100, MPI_COMM_WORLD, &status);

		         merge_even(elements, array, temp);
        		}
		        else 
			{
		          MPI_Sendrecv(array, elements, MPI_INT, partner, 100,
                	  temp,elements, MPI_INT, partner, 100, MPI_COMM_WORLD, &status);

		          merge_odd(elements, array, temp);
        		}

		        mask2 = mask2 >> 1;
      		}
    	}

	else 
	{
		for (j = 0; j < dim; j++) 
		{
		        partner = rank ^ mask2;
		        if (rank > partner) 
			{
		          MPI_Sendrecv(array, elements, MPI_INT, partner, 100,
		          temp, elements, MPI_INT, partner, 100, MPI_COMM_WORLD, &status);

			  merge_even(elements, array, temp);
        		}
        
			else 
			{
		          MPI_Sendrecv(array, elements, MPI_INT, partner, 100,
                	  temp, elements, MPI_INT, partner, 100, MPI_COMM_WORLD, &status);

                          merge_odd(elements, array, temp);
       			}
			
		        mask2 = mask2 >> 1;
      		}
    	}
  	}


	if (rank == 0) 
	{
	    tmp = (int*) malloc( elements * sizeof(int) );
	    printf("The sorted sequence is\n");
	    for (i = 0; i < elements;  i++)
		      printf("%d ", array[i]);
	    for (j = 1; j < nproc; j++) 
		{
		      MPI_Recv(tmp, elements, MPI_INT, j, 50, MPI_COMM_WORLD, &status);
		      for (i = 0; i < elements; i++)
		      printf("%d ", tmp[i]);
    		}
//		MPI_Wait(&request, &status);
  	}
	
	else 
	{
	    MPI_Send(array, elements, MPI_INT, 0, 50, MPI_COMM_WORLD);
//            MPI_Wait(&request, &status);
  	}
gettimeofday(&tim, NULL);

double t2=tim.tv_sec+(tim.tv_usec/1000000.0);
if(rank == 0)
printf("\nTime taken %6f\n", t2-t1);
  //  free(local_a);

	MPI_Buffer_detach(&buf, &bl);

  MPI_Finalize();

  return 0;
}

int compare(const int* p, const int* q) {
  if (*p < *q)

    return -1;
  else if (*p == *q)
    return 0;
  else /* *p > *q */
    return 1;
}

int log_2(int x) {
  int i = 0;
  while (x > 1) {
    x = x / 2;
    i++;
  }
  return i;
}

void merge_even(int elements, int array[], int temp[]) 
{
  int i;
  int j = 0, k = 0;

  for (i = 0; i < elements; i++)
	if (array[j] <= temp[k]) 
	{
		array1[i] = array[j];
	        j++;
	} 
	else 
	{
		array1[i] = temp[k];
	        k++;
    	}
	
	for (i = 0; i < elements; i++)
		array[i] = array1[i];
}

void merge_odd(int elements, int array[], int temp[]) 
{
  int i;
  int j = elements - 1;
  int k = elements - 1;

  for (i = elements - 1; i >= 0; i--)
    if (array[j] >= temp[k]) {
      array1[i] = array[j];
      j--;
    }
    else {
      array1[i] = temp[k];
      k--;
    }
  for (i = 0; i < elements; i++)
    array[i] = array1[i];
}

http://www.daniweb.com/forums/thread203327.html
Last edited by Ancient Dragon : 16 Days Ago at 21:22. Reason: correct code tags -- use [code] instead of <code>

http://www.daniweb.com/forums/thread202126.html
Last edited by Ancient Dragon : 21 Days Ago at 04:39. Reason: correct code tags

http://www.daniweb.com/forums/thread201314.html
Last edited by Tekmaven : 25 Days Ago at 01:13. Reason: Code Tags

It doesn't matter how many times you reinvent your own code tags syntax, it just ain't gonna work.

This article has been dead for over six months. Start a new discussion instead.