source: proiecte/pgraph/Code/Roy-Floyd/mpiroyfloyd.c @ 129

//Author Antonio-Gabriel Sturzu

#include<mpi.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define lim 100001

int main(int argc,char *argv[])
{
        int **m,n,i,j,k,rc,numtasks,rank,dim,next,strip,*line,root,rap;
        MPI_Status status;
        double time1,time2;
        
        //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)
        {       
                FILE *f=fopen("royfloyd.in","r");
                fscanf(f,"%i",&n);
                m=(int **) calloc(n*n,sizeof(int *));
                for(i=0;i<n;i++)
                        m[i]=(int *) calloc(n,sizeof(int));
                for(i=0;i<n;i++)
                        for(j=0;j<n;j++)
                        {
                                fscanf(f,"%i",&m[i][j]);
                                if(i!=j && m[i][j]==0)
                                        m[i][j]=lim;
                        }
                fclose(f);
        }               

        //Send n's value to all processes
        MPI_Bcast(&n,1,MPI_INT,0,MPI_COMM_WORLD);
        line=(int *) calloc(n,sizeof(int));
        dim=n/numtasks;
        if(rank==numtasks-1 && n%numtasks!=0)
                dim=n-dim*(numtasks-1);
        
        if(rank>0)
        {
                m=(int **) calloc(dim*n,sizeof(int *));
                for(i=0;i<dim;i++)
                        m[i]=(int *) calloc(n,sizeof(int));
        }       
        MPI_Barrier(MPI_COMM_WORLD);

        //Send matrix portions to all processes
        if(rank==0)
        {
                next = dim;
                for(k=1;k<numtasks-1;k++) 
                {
                        for (i=0;i<dim;i++) 
                                MPI_Send(m[next+i],n,MPI_INT,k,1,MPI_COMM_WORLD);
                        next+=dim;
                }
                if(numtasks>1)
                {
                        if(n%numtasks!=0)
                                strip=n-dim*(numtasks-1);
                        else
                                strip=dim;
                        for(i=0;i<strip;i++)
                                MPI_Send(m[next+i],n,MPI_INT,numtasks-1,1,MPI_COMM_WORLD);
                }       
        }

        //Receive lines
        else 
        {
                for(i=0;i<dim;i++) 
                        MPI_Recv(m[i],n,MPI_INT,0,1,MPI_COMM_WORLD,&status);
        }
        rap=n/numtasks;

        MPI_Barrier(MPI_COMM_WORLD);
        time1 = MPI_Wtime();
        
        //Distributed Floyd
        for(k=0;k<n;k++)
        {
                root=k/rap;
                if(root>numtasks-1)
                        root=numtasks-1;
                if(root==rank)
                {
                        MPI_Bcast(m[k-root*rap],n,MPI_INT,root,MPI_COMM_WORLD);
                        memmove(line,m[k-root*rap],n*sizeof(int));
                }
                else
                        MPI_Bcast(line,n,MPI_INT,root,MPI_COMM_WORLD);
                
                for(i=0;i<dim;i++)
                        for(j=0;j<n;j++)
                                if(m[i][k]+line[j]<m[i][j])
                                        m[i][j]=m[i][k]+line[j];
                MPI_Barrier(MPI_COMM_WORLD);
        }
        MPI_Barrier(MPI_COMM_WORLD);
        time2=MPI_Wtime();
        if(rank==0)
                printf("Time elapsed is %lf\n",time2-time1);
        
        //Matrix assembly
        if(rank!=0)
                for(i=0;i<dim;i++)
                        MPI_Send(m[i],n,MPI_INT,0,1,MPI_COMM_WORLD);
        else
        {
                if(numtasks>1)
                {
                        next=dim;
                        for(i=1;i<numtasks-1;i++)
                        {
                                for(j=0;j<dim;j++)
                                        MPI_Recv(m[next+j],n,MPI_INT,i,1,MPI_COMM_WORLD,&status);
                                next+=dim;
                        }
                        for(i=0;i<strip;i++)
                                MPI_Recv(m[next+i],n,MPI_INT,numtasks-1,1,MPI_COMM_WORLD,&status);
                }
        }
        
        if(rank==0)
        {
                FILE *f=fopen("royfloyd2.out","w");
                for(i=0;i<n;i++)
                {
                        for(j=0;j<n-1;j++)
                        {
                                if(m[i][j]==lim)
                                        m[i][j]=0;
                                fprintf(f,"%i ",m[i][j]);
                        }
                        if(m[i][n-1]==lim)
                                m[i][n-1]=0;
                        fprintf(f,"%i\n",m[i][n-1]);
                }
                fclose(f);
                for(i=0;i<n;i++)
                        free(m[i]);
        }
        else
                for(i=0;i<dim;i++)
                        free(m[i]);
        free(m);
        free(line);
        MPI_Finalize(); 
        return 0;
}