Subversion Repositories programming

/*******************************************************************************

 * proj2-normal.c - implement a simple program that will find the number of

 *                  occurrances of a random "seed" in a randomly generated

 *                  array of n numbers. This uses the regular synchronous

 *                  communication routines of MPI to transfer the data.

 *

 * Copyright (c) 2006, Ira W. Snyder (devel@irasnyder.com)

 * All rights reserved.

 *

 * Permission is hereby granted, free of charge, to any person obtaining a copy

 * of this software and associated documentation files (the "Software"), to

 * deal in the Software without restriction, including without limitation the

 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or

 * sell copies of the Software, and to permit persons to whom the Software is

 * furnished to do so, subject to the following conditions:

 *

 * The above copyright notice and this permission notice shall be included in

 * all copies or substantial portions of the Software.

 *

 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR

 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,

 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE

 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER

 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING

 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS

 * IN THE SOFTWARE.

 ******************************************************************************/

#include <stdio.h>

#include <stdlib.h>

#include <unistd.h>

#include <limits.h>

#include <sys/timeb.h>

#include <mpi.h>

#define ROOT_NODE 0

#define TAG_SIZE  0xaaaa

#define TAG_DATA  0xbbbb

#define TAG_SEED  0xcccc

#define TAG_TOTAL 0xdddd

#ifdef SOLARIS

    /* NOTE: Solaris is broken, and RAND_MAX is NOT the maximum size

     * number that random() outputs. Here is the correct value. */

    #define RAND_MAX LONG_MAX

#endif

int find_seed_occurrances (int *a, int asize, int seed)

{

    int i, count=0;

    for (i=0; i<asize; i++)

        if (a[i] == seed)

            count++;

    return count;

}

int main (int argc, char *argv[])

{

    int numprocs, myid, i;

    int n = -1;

    int c = -1;

    int size, seed, total, g_total;

    int *numbers;

    /* Declare timeb structs */

    struct timeb time1;

    struct timeb time2;

    MPI_Status status;

    MPI_Init (&argc, &argv);

    MPI_Comm_size (MPI_COMM_WORLD, &numprocs);

    MPI_Comm_rank (MPI_COMM_WORLD, &myid);

    if (myid == ROOT_NODE)

    {

        /* Parse the command line options */

        opterr = 0;

        while ((c = getopt (argc, argv, "n:")) != -1)

        {

            switch (c)

            {

                /* Try to get -n option */

                case 'n':

                    n = atoi (optarg);

                    break;

                /* Catch bad options */

                case '?':

                    if (isprint (optopt))

                        fprintf (stderr, "Unknown option '-%c'.\n", optopt);

                    else

                        fprintf (stderr, "Unknown option character '\\x%x'.\n", optopt);

                    return 1;

                    break;

                default:

                    abort ();

                    break;

            }

        }

        /* Check if the n value is valid */

        if (n<0)

        {

            fprintf (stderr, "Please specify the '-n NUMBER' option\n");

            return 1;

        }

        /* Make sure that we have the ability to calculate the answer */

        if (n % numprocs != 0)

        {

            fprintf (stderr, "n must be evenly divisble by numprocs\n");

            fprintf (stderr, "Please adjust -n and -np adequately\n");

            return 2;

        }

        /* Allocate memory for the random number array */

        if ((numbers = (int*) malloc (n * sizeof(int))) == NULL)

        {

            puts ("Out of memory");

            return 1;

        }

        /* Seed the random number generator */

        srandom (time(NULL));

        /* Generate random numbers, staying in the range [0,n) */

        for (i=0; i<n; i++)

            numbers[i] = (int) (n * (random() / (RAND_MAX + 1.0)));

        /* Generate the seed value */

        seed = (int) (n * (random() / (RAND_MAX + 1.0)));

        /* Calculate slice size */

        size = n/numprocs;

        /* Start the clock */

        ftime (&time1);

        /* Broadcast size to all nodes */

        for (i=1; i<numprocs; i++)

            MPI_Send (&size, 1, MPI_INT, i, TAG_SIZE, MPI_COMM_WORLD);

        /* Scatter the numbers array to all of the children */

        for (i=1; i<numprocs; i++)

            MPI_Send (numbers+(i*size), size, MPI_INT, i, TAG_DATA, MPI_COMM_WORLD);

        /* Broadcast x to all of the children */

        for (i=1; i<numprocs; i++)

            MPI_Send (&seed, 1, MPI_INT, i, TAG_SEED, MPI_COMM_WORLD);

        /* Calculate my part of the total */

        total = find_seed_occurrances (numbers, size, seed);

        /* Sum everyone's results */

        g_total = total;

        for (i=1; i<numprocs; i++)

        {

            MPI_Recv (&total, 1, MPI_INT, i, TAG_TOTAL, MPI_COMM_WORLD, &status);

            g_total += total;

        }

        /* Stop the clock */

        ftime (&time2);

        /* Print time taken */

        long time_taken = ((time2.time - time1.time) * 1000) + (time2.millitm - time1.millitm);

        printf ("Time taken: %d (milliseconds)\n", time_taken);

        /* Print the final status */

        printf ("Total occurrance of seed (%d) out of %d numbers: %d\n", seed, n, g_total);

    }

    else

    {

        /* Recieve the size broadcast */

        MPI_Recv (&size, 1, MPI_INT, ROOT_NODE, TAG_SIZE, MPI_COMM_WORLD, &status);

        /* Allocate memory for numbers, based on size */

        if ((numbers = (int*) malloc (size * sizeof(int))) == NULL)

        {

            puts ("Out of memory");

            return 1;

        }

        /* Recieve the numbers array */

        MPI_Recv (numbers, size, MPI_INT, ROOT_NODE, TAG_DATA, MPI_COMM_WORLD, &status);

        /* Recieve the seed */

        MPI_Recv (&seed, 1, MPI_INT, ROOT_NODE, TAG_SEED, MPI_COMM_WORLD, &status);

        /* Calculate my part of the total */

        total = find_seed_occurrances (numbers, size, seed);

        /* Send my part of the results back to the root */

        MPI_Send (&total, 1, MPI_INT, ROOT_NODE, TAG_TOTAL, MPI_COMM_WORLD);

    }

    free (numbers);

    MPI_Finalize ();

    return 0;

}