Subversion Repositories programming

#include <stdio.h>

#include <limits.h>

#include <mpi.h>

const int ROOT_NODE = 0;

/**

 * NOTE: Accessing "matrices" in this program is a little strange.

 * I decided to implement matrices using an array. To get to a[row][col],

 * you would use a[row*a_size+col]. Pretty simple actually.

 */

int* allocate (int rows, int cols)

{

    int *temp = NULL;

    if ((temp = (int*) malloc (rows * cols * sizeof(int))) == NULL)

        printf ("Could not allocate memory for array of size: %d x %d\n", rows, cols);

    return temp;

}

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

{

    const int n = 4;

    int myid, numprocs;

    int *a, *b, *c;

    int i, j, k;

    int temp;

    /* Get all of the necessary info for each process */

    MPI_Init (&argc, &argv);

    MPI_Comm_rank (MPI_COMM_WORLD, &myid);

    MPI_Comm_size (MPI_COMM_WORLD, &numprocs);

    /* Allocate all of b for each process, since we'll need it */

    b = allocate (n, n);

    if (myid == ROOT_NODE)

    {

        /* Allocate the full a and c, since we need to initialize it */

        a = allocate (n, n);

        c = allocate (n, n);

        /* Initialize values */

#if 0

        for (i=0; i<n; i++)

            for (j=0; j<n; j++)

            {

                a[i*n+j] = i*n+j+1;

                b[i*n+j] = i*n+j+1;

            }

#endif

        for (i=0; i<n; i++)

            for (j=0; j<n; j++)

            {

                a[i*n+j] = INT_MAX;

                b[i*n+j] = INT_MAX;

            }

        b[0] = 0;

        b[1] = 2;

        b[2] = INT_MAX;

        b[3] = 10;

        b[4] = 2;

        b[5] = 0;

        b[6] = 2;

        b[7] = INT_MAX;

        b[8]  = INT_MAX;

        b[9]  = 2;

        b[10] = 0;

        b[11] = 3;

        b[12] = 10;

        b[13] = INT_MAX;

        b[14] = 3;

        b[15] = 0;

        memcpy (a, b, n*n*sizeof(int));

    }

    else

    {

        /* Allocate our slice of a and c, since that's all we need */

        a = allocate (n/numprocs, n);

        c = allocate (n/numprocs, n);

    }

    /* Send a slice of a to each process.

     * Send all of b to each process, since they need all of it */

    MPI_Scatter (a, n*n/numprocs, MPI_INT, a, n*n/numprocs, MPI_INT, ROOT_NODE, MPI_COMM_WORLD);

    MPI_Bcast (b, n*n, MPI_INT, ROOT_NODE, MPI_COMM_WORLD);

    for (i=0; i<n/numprocs; i++)

        for (j=0; j<n; j++)

            c[i*n+j] = INT_MAX;

    /* Multiply our slice of the matrix, store it in c */

    for (i=0; i<n/numprocs; i++)

    {

        for (j=0; j<n; j++)

        {

            // MATRIX_MULT

            // c[i*n+j]=0;

            // SHORTEST PATH

            //c[i*n+j] = INT_MAX;

            for (k=0; k<n; k++)

            {

                // MATRIX MULT

                // c[i*n+j] += a[i*n+k] * b[k*n+j];

                // SHORTEST PATH

                if (a[i*n+k] == INT_MAX || b[k*n+j] == INT_MAX)

                    temp = INT_MAX;

                else

                    temp = a[i*n+k] + b[k*n+j];

                //if (i*n+j == 3 || i*n+j == 12)

                //    printf ("i=%d, j=%d, k=%d, a[%d]=%d, b[%d]=%d, temp=%d\n", i,j,k, i*n+k,a[i*n+k], k*n+j,b[k*n+j], temp);

                if (temp < c[i*n+j])

                    c[i*n+j] = temp; //a[i*n+k] + b[k*n+j];

            }

        }

    }

    /* Recieve each slice from all processes, store the result in c */

    MPI_Gather (c, n*n/numprocs, MPI_INT, c, n*n/numprocs, MPI_INT, ROOT_NODE, MPI_COMM_WORLD);

    if (myid == ROOT_NODE)

    {

        for (i=0; i<n; i++)

        {

            for (j=0; j<n; j++)

                printf ("%d\t", c[i*n+j]);

            printf ("\n");

        }

    }

    /* Free all of the memory we allocated earlier */

    free (a);

    free (b);

    free (c);

    MPI_Finalize ();

    return 0;

}