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];
}