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