Subversion Repositories programming

/* proj3_10.c - implements the APSP algorithm for a matrix of size 10x10
 *              as provided in the project description.
 *
 * Copyright (c) 2006, Ira W. Snyder (devel@irasnyder.com)
 */


#include <stdio.h>
#include <limits.h>
#include <mpi.h>

const int ROOT_NODE = 0;
int numprocs;
int myid;

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

void print_matrix (int *b, int n, const char *s)
{
    int i,j;

    if (n<=10) // n<=10
    {
        printf ("%s\n", s);

        for (i=0; i<n; i++)
        {
            for (j=0; j<n; j++)
                printf ("%d\t", b[i*n+j]);

            printf ("\n");
        }
        printf ("\n");
    }
    else if (n<=100) // 10<n<=100
    {
        printf ("%s\n", s);

        // First 2 rows
        for (i=0; i<2; i++)
        {
            for (j=0; j<n; j++)
                printf ("%d\t", b[i*n+j]);

            printf ("\n");
        }
        printf ("\n");

        // First 2 cols
        for (i=0; i<n; i++)
        {
            for (j=0; j<2; j++)
                printf ("%d\t", b[i*n+j]);

            printf ("\n");
        }
    }
}

void matrix_mult (int *b, int *c, int n)
{
    int i,j,k,ii,temp;

    /* Multiply our slice of the matrix, store it in c */
    for (ii=0; ii<n/numprocs; ii++)
    {
        i = ii + myid * n/numprocs; // i is the offset into b

        for (j=0; j<n; j++)
        {
            // MATRIX_MULT
            // c[i*n+j]=0;

            // SHORTEST PATH
            c[ii*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 (b[i*n+k] == INT_MAX || b[k*n+j] == INT_MAX)
                    temp = INT_MAX;
                else
                    temp = b[i*n+k] + b[k*n+j];

                if (temp < c[ii*n+j])
                    c[ii*n+j] = temp;
            }
        }
    }
}

int main (int argc, char *argv[])
{
    const int n = 10;
    int *b, *c;
    int i, j, k, temp, t;
    MPI_Status status;

    /* 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);

    /* Do a quick sanity check for the correct number of processors */
    if (n % numprocs != 0)
    {
        if (myid == 0)
        {
            printf ("%d mod %d must be zero!\n", n, numprocs);
            printf ("You should probably change the -np parameter\n");
        }

        MPI_Finalize ();
        return 1;
    }

    /* Allocate all of b for each process, since we'll need it */
    b = allocate (n, n);

    if (myid == ROOT_NODE)
    {
        /* Allocate the full c, since we need to initialize it */
        c = allocate (n, n);

        /* Initialize values */
        for (i=0; i<n; i++)
            for (j=0; j<n; j++)
                b[i*n+j] = INT_MAX;

        b[1] = 3;
        b[2] = 2;
        b[5] = 5;
        b[6] = 4;
        b[7] = 9;
        b[8] = 1;
        b[9] = 15;

        b[10] = 3;
        b[12] = 4;
        b[13] = 7;
        b[14] = 28;
        b[16] = 2;
        b[17] = 9;
        b[19] = 1;

        b[20] = 2;
        b[21] = 4;
        b[24] = 3;
        b[25] = 12;
        b[26] = 5;
        b[28] = 10;
        b[29] = 4;

        b[31] = 7;
        b[34] = 15;
        b[35] = 6;
        b[36] = 2;
        b[37] = 5;

        b[41] = 28;
        b[42] = 3;
        b[43] = 15;
        b[45] = 1;
        b[46] = 3;
        b[48] = 2;
        b[49] = 9;

        b[50] = 5;
        b[52] = 12;
        b[53] = 6;
        b[54] = 1;
        b[56] = 3;
        b[58] = 2;
        b[59] = 9;

        b[60] = 4;
        b[61] = 2;
        b[62] = 5;
        b[63] = 2;
        b[64] = 3;
        b[65] = 3;
        b[67] = 1;
        b[69] = 4;

        b[70] = 9;
        b[71] = 9;
        b[73] = 5;
        b[76] = 1;
        b[78] = 7;
        b[79] = 2;

        b[80] = 1;
        b[82] = 10;
        b[84] = 4;
        b[85] = 2;
        b[87] = 7;
        b[89] = 4;

        b[90] = 15;
        b[91] = 1;
        b[92] = 4;
        b[94] = 7;
        b[95] = 9;
        b[96] = 4;
        b[97] = 2;
        b[98] = 4;

        /* Force b[i][i] = 0 */
        for (i=0; i<n; i++)
            b[i*n+i] = 0; 

        if (n<=100)
            print_matrix (b, n, "Input Matrix:");
        else
        {
            printf ("Beginning calculation for all shortest paths\n");
            printf ("for a graph with %d nodes\n", n);
        }

    }
    else
    {
        /* Allocate our slice of c, since that's all we need */
        c = allocate (n/numprocs, n);
    }

    /* Send all of b to each process, since they need all of it */
    MPI_Bcast (b, n*n, MPI_INT, ROOT_NODE, MPI_COMM_WORLD);

    /* Run our piece of the calculation.
     * Synchronize data with all other processes at the end of each step. */
    for (t=0; t<ceil(log(n-1)); t++)
    {
        matrix_mult (b, c, n);
        MPI_Allgather (c, n*n/numprocs, MPI_INT, b, n*n/numprocs, MPI_INT, MPI_COMM_WORLD);
    }

    /* Print out the result matrix. */
    if (myid == ROOT_NODE)
    {
        if (n<=100)
            print_matrix (b, n, "Result Matrix:");
        else
        {
            printf ("Finished calculation for all shortest paths\n");
            printf ("for a graph with %d nodes\n", n);
        }
    }

    /* Free all of the memory we allocated earlier */
    free (b);
    free (c);

    MPI_Finalize ();
    return 0;
}