Subversion Repositories programming

Rev

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

Rev 300 Rev 303
Line 1... Line 1...
1 
/*******************************************************************************
 1 
/*******************************************************************************
2 
 * proj1.c - implement a simple program that will find the minimum and maximum
 2 
 * proj1-parallel.c - implement a simple program that will find the minimum
3 
 *           numbers out of a randomly generated list of integers, using MPI
 3 
 *                    and maximum numbers out of a randomly generated list of
4 
 *           to parallelize the operation.
 4 
 *                    integers, using MPI to parallelize the operation.
5 
 *
 5 
 *
6 
 * Copyright (c) 2006, Ira W. Snyder (devel@irasnyder.com)
 6 
 * Copyright (c) 2006, Ira W. Snyder (devel@irasnyder.com)
7 
 * All rights reserved.
 7 
 * All rights reserved.
8 
 *
 8 
 *
9 
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 9 
 * Permission is hereby granted, free of charge, to any person obtaining a copy
Line 23... Line 23...
23 
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 23 
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
24 
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
 24 
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
25 
 * IN THE SOFTWARE.
 25 
 * IN THE SOFTWARE.
26 
 ******************************************************************************/
 26 
 ******************************************************************************/
27 
 
 27 
 
- 
 
 28 
#include <limits.h>
28 
#include <stdio.h>
 29 
#include <stdio.h>
29 
#include <stdlib.h>
 30 
#include <stdlib.h>
30 
#include <limits.h>
 - 
 
31 
#include <unistd.h>
 31 
#include <unistd.h>
- 
 
 32 
 
32 
//#include <mpi.h>
 33 
#include <mpi.h>
- 
 
 34 
 
- 
 
 35 
#define ROOT_NODE 0
- 
 
 36 
#define TAG_MAX  0x1010
- 
 
 37 
#define TAG_MIN  0x0101
- 
 
 38 
#define TAG_SIZE 0x0808
- 
 
 39 
#define TAG_DATA 0x0c0c
- 
 
 40 
 
- 
 
 41 
void find_max_and_min (const int *numbers, const int size, int *max, int *min)
- 
 
 42 
{
- 
 
 43 
    int i;
- 
 
 44 
    *max = INT_MIN;
- 
 
 45 
    *min = INT_MAX;
- 
 
 46 
 
- 
 
 47 
    for (i=0; i<size; i++)
- 
 
 48 
    {
- 
 
 49 
        if (numbers[i] > *max)
- 
 
 50 
            *max = numbers[i];
- 
 
 51 
 
- 
 
 52 
        if (numbers[i] < *min)
- 
 
 53 
            *min = numbers[i];
- 
 
 54 
    }
- 
 
 55 
}
33 
 
 56 
 
34 
int main (int argc, char *argv[])
 57 
int main (int argc, char *argv[])
35 
{
 58 
{
- 
 
 59 
    int numprocs, myid;
- 
 
 60 
    int n = 6400;
36 
    int i;
 61 
    int i;
37 
    int c = -1;
 - 
 
38 
    int n = -1;
 - 
 
39 
    int min = INT_MAX;
 - 
 
40 
    int max = INT_MIN;
 - 
 
41 
 
 62 
 
- 
 
 63 
    int size;
42 
    int *numbers;
 64 
    int *numbers;
43 
 
 65 
 
- 
 
 66 
    int max = INT_MIN;
44 
    /* Parse the command line options */
 67 
    int min = INT_MAX;
- 
 
 68 
 
45 
    opterr = 0;
 69 
    int temp;
- 
 
 70 
 
- 
 
 71 
    MPI_Status status;
- 
 
 72 
 
- 
 
 73 
    MPI_Init (&argc, &argv);
- 
 
 74 
    MPI_Comm_size (MPI_COMM_WORLD, &numprocs);
- 
 
 75 
    MPI_Comm_rank (MPI_COMM_WORLD, &myid);
46 
 
 76 
 
47 
    while ((c = getopt (argc, argv, "n:")) != -1)
 77 
    if (myid == ROOT_NODE)
48 
    {
 78 
    {
49 
        switch (c)
 79 
        if ((numbers = (int*) malloc (n * sizeof(int))) == NULL)
50 
        {
 80 
        {
- 
 
 81 
            puts ("Out of memory");
- 
 
 82 
            return 1;
- 
 
 83 
        }
- 
 
 84 
 
- 
 
 85 
        for (i=0; i<n; i++)
- 
 
 86 
            numbers[i] = i;
- 
 
 87 
 
- 
 
 88 
        /* Calculate slice size */
- 
 
 89 
        size = n/numprocs;
- 
 
 90 
 
- 
 
 91 
        /* Send out n to everyone */
- 
 
 92 
        for (i=1; i<numprocs; i++)
- 
 
 93 
            MPI_Send (&size, 1, MPI_INT, i, TAG_SIZE, MPI_COMM_WORLD);
- 
 
 94 
 
- 
 
 95 
        /* Send out data to everyone */
- 
 
 96 
        for (i=1; i<numprocs; i++)
- 
 
 97 
            MPI_Send (numbers+(size*i), size, MPI_INT, i, TAG_DATA, MPI_COMM_WORLD);
- 
 
 98 
 
- 
 
 99 
        /* Calculate my part of the data */
- 
 
 100 
        find_max_and_min (numbers, size, &max, &min);
- 
 
 101 
 
- 
 
 102 
        /* Recieve data back */
- 
 
 103 
        for (i=1; i<numprocs; i++)
- 
 
 104 
        {
- 
 
 105 
            /* Find actual max */
- 
 
 106 
            MPI_Recv (&temp, 1, MPI_INT, i, TAG_MAX, MPI_COMM_WORLD, &status);
- 
 
 107 
 
- 
 
 108 
            if (temp > max)
- 
 
 109 
                max = temp;
- 
 
 110 
 
- 
 
 111 
            /* Find actual min */
- 
 
 112 
            MPI_Recv (&temp, 1, MPI_INT, i, TAG_MIN, MPI_COMM_WORLD, &status);
51 
 
 113 
 
52 
            /* Try to get n */
 - 
 
53 
            case 'n':
 - 
 
54 
                n = atoi (optarg);
 - 
 
55 
                break;
 - 
 
56 
 
 - 
 
57 
            /* Catch bad options */
 - 
 
58 
            case '?':
 - 
 
59 
                if (isprint (optopt))
 - 
 
60 
                    fprintf (stderr, "Unknown option '-%c'.\n", optopt);
 - 
 
61 
                else
 - 
 
62 
                    fprintf (stderr, "Unknown option character '\\x%x'.\n", optopt);
 - 
 
63 
 
 - 
 
64 
                return 1;
 114 
            if (temp < min)
65 
                break;
 - 
 
66 
            default:
 - 
 
67 
                abort ();
 115 
                min = temp;
68 
        }
 116 
        }
- 
 
 117 
 
- 
 
 118 
        printf ("final max: %d\n", max);
- 
 
 119 
        printf ("final min: %d\n", min);
69 
    }
 120 
    }
- 
 
 121 
    else
- 
 
 122 
    {
- 
 
 123 
        /* Recieve size of the data */
- 
 
 124 
        MPI_Recv (&size, 1, MPI_INT, ROOT_NODE, TAG_SIZE, MPI_COMM_WORLD, &status);
70 
 
 125 
 
71 
    /* Seed the random number generator */
 126 
        /* Allocate memory to store the data */
- 
 
 127 
        if ((numbers = (int*) malloc (size * sizeof(int))) == NULL)
- 
 
 128 
        {
- 
 
 129 
            puts ("Out of memory");
72 
    srand (time(NULL));
 130 
            return 1;
- 
 
 131 
        }
73 
 
 132 
 
74 
    /* Check if the n value is valid */
 133 
        /* Recieve the data */
75 
    if (n<=0)
 - 
 
76 
    {
 - 
 
77 
        fprintf (stderr, "Bad value for n, must be greater than 0\n");
 134 
        MPI_Recv (numbers, size, MPI_INT, ROOT_NODE, TAG_DATA, MPI_COMM_WORLD, &status);
78 
        fprintf (stderr, "Please specify the '-n NUMBER' option\n");
 - 
 
79 
        return 1;
 - 
 
80 
    }
 - 
 
81 
 
 135 
 
82 
    /* Allocate memory for the random number */
 136 
        /* Calculate the max and min of my part of the data */
83 
    if ((numbers = (int*) malloc (n * sizeof(int))) == NULL)
 - 
 
84 
    {
 - 
 
85 
        fprintf (stderr, "Memory allocation for array failed, exiting...\n");
 137 
        find_max_and_min (numbers, size, &max, &min);
86 
        return 2;
 - 
 
87 
    }
 - 
 
88 
 
 138 
 
89 
    /* Generate random numbers, staying in the range [1,10n] */
 139 
        /* Send the max and min back to the root node */
90 
    for (i=0; i<n; i++)
 140 
        MPI_Send (&max, 1, MPI_INT, ROOT_NODE, TAG_MAX, MPI_COMM_WORLD);
91 
        numbers[i] = (rand() % (n*10)) + 1;
 141 
        MPI_Send (&min, 1, MPI_INT, ROOT_NODE, TAG_MIN, MPI_COMM_WORLD);
92 
 
 142 
 
93 
    /* Find the max and min of them */
 - 
 
94 
    for (i=0; i<n; i++)
 - 
 
95 
    {
 - 
 
96 
        /* max */
 - 
 
97 
        if (numbers[i] > max)
 - 
 
98 
            max = numbers[i];
 - 
 
99
- 
 
100 
        if (numbers[i] < min)
 - 
 
101 
            min = numbers[i];
 143 
        free (numbers);
102 
    }
 144 
    }
103 
 
 145 
 
104 
    /* Print the results */
 - 
 
105 
    printf ("min: %d\n", min);
 - 
 
106 
    printf ("max: %d\n", max);
 - 
 
107 
 
 - 
 
108 
#ifdef DEBUG
 - 
 
109 
    for (i=0; i<n; i++)
 146 
    MPI_Finalize ();
110 
        printf ("numbers[%d] = %d\n", i, numbers[i]);
 - 
 
111 
#endif
 - 
 
112 
 
 147 
 
113 
    return 0;
 148 
    return 0;
114 
}
 149 
}
115 
 
 150