source: proiecte/pgraph/Code/Prim/papm.c @ 129

//Author Antonio-Gabriel Sturzu


#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<mpi.h>
#define inf 1001

int main(int argc,char *argv[])
{
        int rc,numtasks,rank,**m,n,*line,dim,next=0,strip,*key,*viz,*prev,minl=0,iminl,ming,iming,costl=0,prod,costg,sup;
        int i,j,temp;
        double time1,time2;
        FILE *f;
        MPI_Status status;

        //MPI Initialization
        rc = MPI_Init(&argc,&argv);
        if (rc != MPI_SUCCESS) 
        {
                printf ("Error starting MPI program. Terminating.\n");
                MPI_Abort(MPI_COMM_WORLD, rc);
        }
        MPI_Comm_size(MPI_COMM_WORLD,&numtasks);
        MPI_Comm_rank(MPI_COMM_WORLD,&rank);

        //Reading from file is done by process 0
        if(rank==0)
        {       
                f=fopen("apm2.in","r");
                fscanf(f,"%i",&n);
        }
        //Broadcast n's value to all processes
        MPI_Bcast(&n,1,MPI_INT,0,MPI_COMM_WORLD);
        dim=n/numtasks;
        strip=dim;
        if(rank==numtasks-1 && n%numtasks!=0)
                dim=n-dim*(numtasks-1);
        
        m=(int **) calloc(n*dim,sizeof(int *));
        for(i=0;i<n;i++)
                        m[i]=(int *) calloc(dim,sizeof(int));
        if(rank==0)
        {
                line=(int *) calloc(n,sizeof(int));
                for(i=0;i<n;i++)
                {
                        next=dim;
                        for(j=0;j<n;j++)
                                fscanf(f,"%i",line+j);
                        memmove(m[i],line,dim*sizeof(int));
                        for(j=1;j<numtasks-1;j++)
                        {
                                MPI_Send(&line[next],dim,MPI_INT,j,1,MPI_COMM_WORLD);
                                next+=dim;
                        }
                        if(numtasks>1)
                                MPI_Send(&line[next],n-next,MPI_INT,numtasks-1,1,MPI_COMM_WORLD);
                }
        }               
        else
                for(i=0;i<n;i++)
                        MPI_Recv(m[i],dim,MPI_INT,0,1,MPI_COMM_WORLD,&status);

        key=(int *) calloc(dim,sizeof(int));
        viz=(int *) calloc(dim,sizeof(int));
        prev=(int *) calloc(dim,sizeof(int));

        MPI_Barrier(MPI_COMM_WORLD);
        time1=MPI_Wtime();
        //Initialize the keys
        if(rank!=0)
        {
                for(i=0;i<dim;i++)
                        key[i]=inf;
        }
        else
        {
                for(i=1;i<dim;i++)
                        key[i]=inf;
                key[0]=0;
        }

        if(rank!=numtasks-1)
        {
                prod=rank*dim;
                sup=prod+dim;
        }
        else
        {
                prod=rank*strip;
                sup=n;
        }
        MPI_Barrier(MPI_COMM_WORLD);

        //Distributed Prim's algorithm
        for(;;)
        {
                minl=inf;
                for(i=0;i<dim;i++)
                {
                        if(viz[i]==0 && key[i]<minl)
                        {
                                minl=key[i];
                                iminl=i;
                        }
                }
                //Determine the global minimum value of a key
                MPI_Allreduce(&minl,&ming,1,MPI_INT,MPI_MIN,MPI_COMM_WORLD);
                if(ming==inf)
                        break;
        
                if(minl==ming)
                {
                        temp=iminl+prod;
                        MPI_Allreduce(&temp,&iming,1,MPI_INT,MPI_MIN,MPI_COMM_WORLD);
                }
                else
                        MPI_Allreduce(&n,&iming,1,MPI_INT,MPI_MIN,MPI_COMM_WORLD);
        
                //If the newest node that will be added to the tree is owned by this process
                //then marke it as out of the local queue
                
                if(iming>=prod && iming<sup)
                {
                        viz[iming-prod]=1;
                        costl+=minl;
                }
                for(i=0;i<dim;i++)
                {
                        if(m[iming][i]<key[i] && viz[i]==0)
                        {
                                key[i]=m[iming][i];
                                prev[i]=iming;
                        }
                }
                MPI_Barrier(MPI_COMM_WORLD);
        }

        MPI_Reduce(&costl,&costg,1,MPI_INT,MPI_SUM,0,MPI_COMM_WORLD);
        MPI_Barrier(MPI_COMM_WORLD);
        time2=MPI_Wtime();
        if(rank==0)
                printf("Au trecut %f secunde \n",time2-time1);

        if(rank==0)
        {
                printf("Costul minim este %i\n",costg);
                printf("Muchiile arborelui sunt: \n");
        }
        MPI_Barrier(MPI_COMM_WORLD);

        for(i=0;i<dim;i++)
                        if(i+prod!=0)
                                printf("%i %i\n",prev[i]+1,i+prod+1);
        for(i=0;i<n;i++)
                free(m[i]);
        free(m);
        free(key);
        free(prev);
        free(viz);
        if(rank==0)
                free(line);
        MPI_Finalize(); 
        return 0;
}