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;

}