Subversion Repositories programming

Rev

Go to most recent revision | Details | Last modification | View Log | RSS feed

Rev Author Line No. Line
322 ira 1 
#include <stdio.h>
2 
#include <limits.h>
3 
#include <mpi.h>
4 
 
5 
const int ROOT_NODE = 0;
325 ira 6 
int numprocs;
7 
int myid;
322 ira 8 
 
9 
/**
10 
 * NOTE: Accessing "matrices" in this program is a little strange.
11 
 * I decided to implement matrices using an array. To get to a[row][col],
12 
 * you would use a[row*a_size+col]. Pretty simple actually.
13 
 */
14 
 
15 
int* allocate (int rows, int cols)
16 
{
17 
    int *temp = NULL;
18 
 
19 
    if ((temp = (int*) malloc (rows * cols * sizeof(int))) == NULL)
20 
        printf ("Could not allocate memory for array of size: %d x %d\n", rows, cols);
21 
 
22 
    return temp;
23 
}
24 
 
325 ira 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 
 
322 ira 102 
int main (int argc, char *argv[])
103 
{
324 ira 104 
    const int n = 4;
325 ira 105 
    int *b, *c;
106 
    int i, j, k, temp, t;
107 
    MPI_Status status;
322 ira 108 
 
109 
    /* Get all of the necessary info for each process */
110 
    MPI_Init (&argc, &argv);
111 
    MPI_Comm_rank (MPI_COMM_WORLD, &myid);
112 
    MPI_Comm_size (MPI_COMM_WORLD, &numprocs);
113 
 
114 
    /* Allocate all of b for each process, since we'll need it */
115 
    b = allocate (n, n);
116 
 
117 
    if (myid == ROOT_NODE)
118 
    {
325 ira 119 
        /* Allocate the full c, since we need to initialize it */
322 ira 120 
        c = allocate (n, n);
121 
 
122 
        /* Initialize values */
123 
        for (i=0; i<n; i++)
124 
            for (j=0; j<n; j++)
324 ira 125 
                b[i*n+j] = INT_MAX;
126 
 
323 ira 127 
        b[0] = 0;
324 ira 128 
        b[1] = 2;
323 ira 129 
        b[2] = INT_MAX;
324 ira 130 
        b[3] = 10;
323 ira 131 
 
324 ira 132 
        b[4] = 2;
133 
        b[5] = 0;
134 
        b[6] = 2;
135 
        b[7] = INT_MAX;
136 
 
137 
        b[8]  = INT_MAX;
138 
        b[9]  = 2;
139 
        b[10] = 0;
140 
        b[11] = 3;
141 
 
142 
        b[12] = 10;
143 
        b[13] = INT_MAX;
144 
        b[14] = 3;
145 
        b[15] = 0;
146 
 
325 ira 147 
        if (n<=100)
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 
 
322 ira 155 
    }
156 
    else
157 
    {
325 ira 158 
        /* Allocate our slice of c, since that's all we need */
322 ira 159 
        c = allocate (n/numprocs, n);
160 
    }
161 
 
325 ira 162 
    /* Send all of b to each process, since they need all of it */
322 ira 163 
    MPI_Bcast (b, n*n, MPI_INT, ROOT_NODE, MPI_COMM_WORLD);
164 
 
325 ira 165 
    /* Run our piece of the calculation.
166 
     * Synchronize data with all other processes at the end of each step. */
167 
    for (t=0; t<ceil(log(n-1)); t++)
322 ira 168 
    {
325 ira 169 
        matrix_mult (b, c, n);
170 
        MPI_Allgather (c, n*n/numprocs, MPI_INT, b, n*n/numprocs, MPI_INT, MPI_COMM_WORLD);
322 ira 171 
    }
172 
 
325 ira 173 
    /* Print out the result matrix. */
322 ira 174 
    if (myid == ROOT_NODE)
175 
    {
325 ira 176 
        if (n<=100)
177 
            print_matrix (b, n, "Result Matrix:");
178 
        else
323 ira 179 
        {
325 ira 180 
            printf ("Finished calculation for all shortest paths\n");
181 
            printf ("for a graph with %d nodes\n", n);
323 ira 182 
        }
322 ira 183 
    }
184 
 
185 
    /* Free all of the memory we allocated earlier */
186 
    free (b);
187 
    free (c);
188 
 
189 
    MPI_Finalize ();
190 
    return 0;
191 
}
192