[mpich-discuss] Parallel Quick sort

[Irfan Gul]

>version :MPICH2 1.3.1
>uname -mo
            ia64 GNU/Linux
>Yah dear 100 is the output. which is the size of array I have I entered.
>Yah Friend it is working correctly with out profiling on single and
multiple      processes. and also after profiling when it run on a single
process.

#include <mpi.h>
#include <stdio.h>
#include <stdlib.h>
#define  TRUE 1
#include "math.h"
#include <time.h>
int compare(const void *e1, const void *e2 )
    {
          return (*((int *)e1) - *((int *)e2));
    }
DisplayError(char *str)
{
    printf("Error: %s \n",str);
}

int Partition(int *Array,int start,int end)
{
    int pivo;
    int i, j;
    int tmp;

    pivo=Array[end];
    i=start-1;

    for(j=start;j<end;j++)
        if(Array[j]<=pivo)
        {
            i++;
            tmp=Array[i];
            Array[i]=Array[j];
            Array[j]=tmp;
        }

    tmp=Array[i+1];
    Array[i+1]=Array[end];
    Array[end]=tmp;

    return i+1;
}

QuickSort(int *Array,int start,int end)
{
    int r;
    int i;

    if(start<end)
    {
        r=Partition(Array,start,end);
        QuickSort(Array,start,r-1);
        QuickSort(Array,r+1,end);
    }
}

int PowerOf2(int num)
{
    int i;

    i=1;

    while(num>0)
    {
        num--;
        i=i*2;
    }

    return i;
}


PQuickSort(int *Array,int start,int end,int m,int id,int MyRank)
{
    int i, j;
    int r;
    int LocalLength;
    int *tmp;
    //int newsize;
    MPI_Status status;
    LocalLength=-1;
    double t3,t4,t5;

    if(m==0)
    {
        if(MyRank==id)

        t3=MPI_Wtime();
        qsort(Array, end-start, sizeof(int), compare);
        t4=MPI_Wtime();
        t5=t4-t3;
        printf("Process with ID %d and time %6.3f  \n",MyRank,t5);

        return 0;
    }

    if(MyRank==id)
    {
        r=Partition(Array,start,end);
        LocalLength=end-r;

MPI_Send(&LocalLength,1,MPI_INT,id+PowerOf2(m-1),MyRank,MPI_COMM_WORLD);
        if(LocalLength!=0)

MPI_Send(Array+r+1,LocalLength,MPI_INT,id+PowerOf2(m-1),MyRank,MPI_COMM_WORLD);
    }

    if(MyRank==id+PowerOf2(m-1))
    {
        MPI_Recv(&LocalLength,1,MPI_INT,id,id,MPI_COMM_WORLD,&status);

       if(LocalLength!=0)
        {
            tmp=(int *)malloc(LocalLength*sizeof(int));
            if(tmp==0) DisplayError("Malloc memory error!");
            MPI_Recv(tmp,LocalLength,MPI_INT,id,id,MPI_COMM_WORLD,&status);
        }
    }



    if(id<=MyRank && MyRank<id+PowerOf2(m-1))
    {
        PQuickSort(Array,start,r-1,m-1,id,MyRank);
    }

    if(MyRank>=id+PowerOf2(m-1))
    {
        PQuickSort(tmp,0,LocalLength-1,m-1,id+PowerOf2(m-1),MyRank);
    }


    if((MyRank==id+PowerOf2(m-1)) && (LocalLength!=0))

MPI_Send(tmp,LocalLength,MPI_INT,id,id+PowerOf2(m-1),MPI_COMM_WORLD);

    if((MyRank==id) && (LocalLength!=0))

MPI_Recv(Array+r+1,LocalLength,MPI_INT,id+PowerOf2(m-1),id+PowerOf2(m-1),MPI_COMM_WORLD,&status);

}

int LogBase2(int num)
{
    int i, j;

    i=1;
    j=2;

    while(j<num)
    {
        j=j*2;
        i++;
    }

    if(j>num)
        i--;

    return i;
}


main(int argc,char *argv[])
{
    int ArraySize;
    int *Array;
    int    MyRank, npes;
    int i, j;
    int m, r;
    double t1,t2,t3;


    MPI_Status status;
    MPI_Init(&argc,&argv);

    MPI_Comm_rank(MPI_COMM_WORLD,&MyRank);

    MPI_Comm_size(MPI_COMM_WORLD,&npes);

    if(MyRank==0)
    {
        ArraySize=1000000;
        printf("%d\n",ArraySize);
        Array=(int *)malloc(ArraySize*sizeof(int));

        if(Array==0)
            printf("Malloc memory error!");

        srand(396);
        for(i=0;i<ArraySize;i++)
        {
            Array[i]=(int)rand()%1000;
            //printf("%10d",Array[i]);
            //    printf("\t");
        }
        printf("\n");
    }

    m=LogBase2(npes);

    MPI_Bcast(&ArraySize,1,MPI_INT,0,MPI_COMM_WORLD);
        t1=MPI_Wtime();
    PQuickSort(Array,0,ArraySize-1,m,0,MyRank);
        t2=MPI_Wtime();
        t3=t2-t1;

    if(MyRank==0)
    {
        //for(i=0;i<ArraySize;i++)
        //{
        //    printf("%10d",Array[i]);
        //        printf("\t");
        //}
        printf("\n");
    printf("MPI_time :%6.3f\n",t3);

    }

    MPI_Finalize();
    return 0;
}

> the above code is without profiling and work well
Thanks Friend :)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mcs.anl.gov/pipermail/mpich-discuss/attachments/20110520/6a121ffa/attachment-0001.htm>