Subversion Repositories programming

Rev

Rev 324 | Rev 326 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 324 Rev 325
Line 1... Line 1...
1 
#include <stdio.h>
 1 
#include <stdio.h>
2 
#include <limits.h>
 2 
#include <limits.h>
3 
#include <mpi.h>
 3 
#include <mpi.h>
4 
 
 4 
 
5 
const int ROOT_NODE = 0;
 5 
const int ROOT_NODE = 0;
- 
 
 6 
int numprocs;
- 
 
 7 
int myid;
6 
 
 8 
 
7 
/**
 9 
/**
8 
 * NOTE: Accessing "matrices" in this program is a little strange.
 10 
 * NOTE: Accessing "matrices" in this program is a little strange.
9 
 * I decided to implement matrices using an array. To get to a[row][col],
 11 
 * I decided to implement matrices using an array. To get to a[row][col],
10 
 * you would use a[row*a_size+col]. Pretty simple actually.
 12 
 * you would use a[row*a_size+col]. Pretty simple actually.
Line 18... Line 20...
18 
        printf ("Could not allocate memory for array of size: %d x %d\n", rows, cols);
 20 
        printf ("Could not allocate memory for array of size: %d x %d\n", rows, cols);
19 
 
 21 
 
20 
    return temp;
 22 
    return temp;
21 
}
 23 
}
22 
 
 24 
 
- 
 
 25 
void print_matrix (int *b, int n, const char *s)
- 
 
 26 
{
- 
 
 27 
    int i,j;
- 
 
 28 
 
- 
 
 29 
    if (n<=10) // n<=10
- 
 
 30 
    {
- 
 
 31 
        printf ("%s\n", s);
- 
 
 32 
 
- 
 
 33 
        for (i=0; i<n; i++)
- 
 
 34 
        {
- 
 
 35 
            for (j=0; j<n; j++)
- 
 
 36 
                printf ("%d\t", b[i*n+j]);
- 
 
 37 
 
- 
 
 38 
            printf ("\n");
- 
 
 39 
        }
- 
 
 40 
        printf ("\n");
- 
 
 41 
    }
- 
 
 42 
    else if (n<=100) // 10<n<=100
- 
 
 43 
    {
- 
 
 44 
        printf ("%s\n", s);
- 
 
 45 
 
- 
 
 46 
        // First 2 rows
- 
 
 47 
        for (i=0; i<2; i++)
- 
 
 48 
        {
- 
 
 49 
            for (j=0; j<n; j++)
- 
 
 50 
                printf ("%d\t", b[i*n+j]);
- 
 
 51 
 
- 
 
 52 
            printf ("\n");
- 
 
 53 
        }
- 
 
 54 
        printf ("\n");
- 
 
 55 
 
- 
 
 56 
        // First 2 cols
- 
 
 57 
        for (i=0; i<n; i++)
- 
 
 58 
        {
- 
 
 59 
            for (j=0; j<2; j++)
- 
 
 60 
                printf ("%d\t", b[i*n+j]);
- 
 
 61 
 
- 
 
 62 
            printf ("\n");
- 
 
 63 
        }
- 
 
 64 
    }
- 
 
 65 
}
- 
 
 66 
 
- 
 
 67 
void matrix_mult (int *b, int *c, int n)
- 
 
 68 
{
- 
 
 69 
    int i,j,k,ii,temp;
- 
 
 70 
 
- 
 
 71 
    /* Multiply our slice of the matrix, store it in c */
- 
 
 72 
    for (ii=0; ii<n/numprocs; ii++)
- 
 
 73 
    {
- 
 
 74 
        i = ii + myid * n/numprocs; // i is the offset into b
- 
 
 75 
 
- 
 
 76 
        for (j=0; j<n; j++)
- 
 
 77 
        {
- 
 
 78 
            // MATRIX_MULT
- 
 
 79 
            // c[i*n+j]=0;
- 
 
 80 
 
- 
 
 81 
            // SHORTEST PATH
- 
 
 82 
            c[ii*n+j] = INT_MAX;
- 
 
 83 
 
- 
 
 84 
            for (k=0; k<n; k++)
- 
 
 85 
            {
- 
 
 86 
                // MATRIX MULT
- 
 
 87 
                // c[i*n+j] += a[i*n+k] * b[k*n+j];
- 
 
 88 
 
- 
 
 89 
                // SHORTEST PATH
- 
 
 90 
                if (b[i*n+k] == INT_MAX || b[k*n+j] == INT_MAX)
- 
 
 91 
                    temp = INT_MAX;
- 
 
 92 
                else
- 
 
 93 
                    temp = b[i*n+k] + b[k*n+j];
- 
 
 94 
 
- 
 
 95 
                if (temp < c[ii*n+j])
- 
 
 96 
                    c[ii*n+j] = temp;
- 
 
 97 
            }
- 
 
 98 
        }
- 
 
 99 
    }
- 
 
 100 
}
- 
 
 101 
 
23 
int main (int argc, char *argv[])
 102 
int main (int argc, char *argv[])
24 
{
 103 
{
25 
    const int n = 4;
 104 
    const int n = 4;
26 
    int myid, numprocs;
 - 
 
27 
    int *a, *b, *c;
 105 
    int *b, *c;
28 
    int i, j, k;
 106 
    int i, j, k, temp, t;
29 
    int temp;
 107 
    MPI_Status status;
30 
 
 108 
 
31 
    /* Get all of the necessary info for each process */
 109 
    /* Get all of the necessary info for each process */
32 
    MPI_Init (&argc, &argv);
 110 
    MPI_Init (&argc, &argv);
33 
    MPI_Comm_rank (MPI_COMM_WORLD, &myid);
 111 
    MPI_Comm_rank (MPI_COMM_WORLD, &myid);
34 
    MPI_Comm_size (MPI_COMM_WORLD, &numprocs);
 112 
    MPI_Comm_size (MPI_COMM_WORLD, &numprocs);
Line 36... Line 114...
36 
    /* Allocate all of b for each process, since we'll need it */
 114 
    /* Allocate all of b for each process, since we'll need it */
37 
    b = allocate (n, n);
 115 
    b = allocate (n, n);
38 
 
 116 
 
39 
    if (myid == ROOT_NODE)
 117 
    if (myid == ROOT_NODE)
40 
    {
 118 
    {
41 
        /* Allocate the full a and c, since we need to initialize it */
 119 
        /* Allocate the full c, since we need to initialize it */
42 
        a = allocate (n, n);
 - 
 
43 
        c = allocate (n, n);
 120 
        c = allocate (n, n);
44 
 
 121 
 
45 
        /* Initialize values */
 122 
        /* Initialize values */
46 
#if 0
 - 
 
47 
        for (i=0; i<n; i++)
 123 
        for (i=0; i<n; i++)
48 
            for (j=0; j<n; j++)
 124 
            for (j=0; j<n; j++)
49 
            {
 - 
 
50 
                a[i*n+j] = i*n+j+1;
 - 
 
51 
                b[i*n+j] = i*n+j+1;
 - 
 
52 
            }
 - 
 
53 
#endif
 - 
 
54 
 
 - 
 
55 
        for (i=0; i<n; i++)
 - 
 
56 
            for (j=0; j<n; j++)
 - 
 
57 
            {
 - 
 
58 
                a[i*n+j] = INT_MAX;
 - 
 
59 
                b[i*n+j] = INT_MAX;
 125 
                b[i*n+j] = INT_MAX;
60 
            }
 - 
 
61 
 
 126 
 
62 
        b[0] = 0;
 127 
        b[0] = 0;
63 
        b[1] = 2;
 128 
        b[1] = 2;
64 
        b[2] = INT_MAX;
 129 
        b[2] = INT_MAX;
65 
        b[3] = 10;
 130 
        b[3] = 10;
Line 77... Line 142...
77 
        b[12] = 10;
 142 
        b[12] = 10;
78 
        b[13] = INT_MAX;
 143 
        b[13] = INT_MAX;
79 
        b[14] = 3;
 144 
        b[14] = 3;
80 
        b[15] = 0;
 145 
        b[15] = 0;
81 
 
 146 
 
- 
 
 147 
        if (n<=100)
82 
        memcpy (a, b, n*n*sizeof(int));
 148 
            print_matrix (b, n, "Input Matrix:");
- 
 
 149 
        else
- 
 
 150 
        {
- 
 
 151 
            printf ("Beginning calculation for all shortest paths\n");
- 
 
 152 
            printf ("for a graph with %d nodes\n", n);
- 
 
 153 
        }
- 
 
 154 
 
83 
    }
 155 
    }
84 
    else
 156 
    else
85 
    {
 157 
    {
86 
        /* Allocate our slice of a and c, since that's all we need */
 158 
        /* Allocate our slice of c, since that's all we need */
87 
        a = allocate (n/numprocs, n);
 - 
 
88 
        c = allocate (n/numprocs, n);
 159 
        c = allocate (n/numprocs, n);
89 
    }
 160 
    }
90 
 
 161 
 
91 
    /* Send a slice of a to each process.
 - 
 
92 
     * Send all of b to each process, since they need all of it */
 162 
    /* Send all of b to each process, since they need all of it */
93 
    MPI_Scatter (a, n*n/numprocs, MPI_INT, a, n*n/numprocs, MPI_INT, ROOT_NODE, MPI_COMM_WORLD);
 - 
 
94 
    MPI_Bcast (b, n*n, MPI_INT, ROOT_NODE, MPI_COMM_WORLD);
 163 
    MPI_Bcast (b, n*n, MPI_INT, ROOT_NODE, MPI_COMM_WORLD);
95 
 
 164 
 
96 
    for (i=0; i<n/numprocs; i++)
 165 
    /* Run our piece of the calculation.
97 
        for (j=0; j<n; j++)
 - 
 
98 
            c[i*n+j] = INT_MAX;
 - 
 
99 
 
 - 
 
100 
    /* Multiply our slice of the matrix, store it in c */
 166 
     * Synchronize data with all other processes at the end of each step. */
101 
    for (i=0; i<n/numprocs; i++)
 167 
    for (t=0; t<ceil(log(n-1)); t++)
102 
    {
 168 
    {
103 
        for (j=0; j<n; j++)
 169 
        matrix_mult (b, c, n);
104 
        {
 - 
 
105 
            // MATRIX_MULT
 - 
 
106 
            // c[i*n+j]=0;
 - 
 
107 
 
 - 
 
108 
            // SHORTEST PATH
 - 
 
109 
            //c[i*n+j] = INT_MAX;
 - 
 
110 
 
 - 
 
111 
            for (k=0; k<n; k++)
 - 
 
112 
            {
 - 
 
113 
                // MATRIX MULT
 - 
 
114 
                // c[i*n+j] += a[i*n+k] * b[k*n+j];
 - 
 
115 
 
 - 
 
116 
                // SHORTEST PATH
 - 
 
117 
                if (a[i*n+k] == INT_MAX || b[k*n+j] == INT_MAX)
 170 
        MPI_Allgather (c, n*n/numprocs, MPI_INT, b, n*n/numprocs, MPI_INT, MPI_COMM_WORLD);
118 
                    temp = INT_MAX;
 - 
 
119 
                else
 - 
 
120 
                    temp = a[i*n+k] + b[k*n+j];
 - 
 
121 
 
 - 
 
122 
                //if (i*n+j == 3 || i*n+j == 12)
 - 
 
123 
                //    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);
 - 
 
124 
 
 - 
 
125 
                if (temp < c[i*n+j])
 - 
 
126 
                    c[i*n+j] = temp; //a[i*n+k] + b[k*n+j];
 - 
 
127 
            }
 - 
 
128 
        }
 - 
 
129 
    }
 171 
    }
130 
 
 172 
 
131 
    /* Recieve each slice from all processes, store the result in c */
 173 
    /* Print out the result matrix. */
132 
    MPI_Gather (c, n*n/numprocs, MPI_INT, c, n*n/numprocs, MPI_INT, ROOT_NODE, MPI_COMM_WORLD);
 - 
 
133 
 
 - 
 
134 
    if (myid == ROOT_NODE)
 174 
    if (myid == ROOT_NODE)
135 
    {
 175 
    {
136 
        for (i=0; i<n; i++)
 176 
        if (n<=100)
- 
 
 177 
            print_matrix (b, n, "Result Matrix:");
- 
 
 178 
        else
137 
        {
 179 
        {
138 
            for (j=0; j<n; j++)
 - 
 
139 
                printf ("%d\t", c[i*n+j]);
 180 
            printf ("Finished calculation for all shortest paths\n");
140 
 
 - 
 
141 
            printf ("\n");
 181 
            printf ("for a graph with %d nodes\n", n);
142 
        }
 182 
        }
143 
    }
 183 
    }
144 
 
 184 
 
145 
    /* Free all of the memory we allocated earlier */
 185 
    /* Free all of the memory we allocated earlier */
146 
    free (a);
 - 
 
147 
    free (b);
 186 
    free (b);
148 
    free (c);
 187 
    free (c);
149 
 
 188 
 
150 
    MPI_Finalize ();
 189 
    MPI_Finalize ();
151 
    return 0;
 190 
    return 0;