Subversion Repositories programming

/*******************************************************************************
 * prob3.c - implement a parallel (pipelined approach) system for the
 *           Sieve of Eratosthenes problem.
 *
 * Copyright (c) 2006, Ira W. Snyder (devel@irasnyder.com)
 ******************************************************************************/

#include <mpi.h>
#include <stdio.h>
#include <stdlib.h>

#define TAG_DATA   0x1010
#define TERMINATOR 0xffff
#define BAD_NUM    -1

#define FALSE 0
#define TRUE  1

/* Check if we should pass num on, based on mynumber */
int should_pass (int num, int mynumber)
{
    if (num % mynumber == 0)
        return FALSE; /* evenly divisible, DO NOT PASS */

    return TRUE; /* not evenly divisible, GO AHEAD */
}

/* Print out this processes number nicely.
 * Ignore processes that don't have a number. */
void print_num (int myrank, int mynumber)
{
    if (mynumber == BAD_NUM)
        return;

    if (myrank < 10)
        printf ("Proc 0%d's Prime: %d\n", myrank, mynumber);
    else
        printf ("Proc %d's Prime: %d\n", myrank, mynumber);
}

/* Send the terminator to to_proc */
void send_term (int to_proc)
{
    int temp = TERMINATOR;
    MPI_Send (&temp, 1, MPI_INT, to_proc, TAG_DATA, MPI_COMM_WORLD);
}

int main (int argc, char *argv[])
{
    int myrank, numprocs;
    int mynumber = BAD_NUM;
    int temp_recv;

    MPI_Status status;

    MPI_Init (&argc, &argv);
    MPI_Comm_rank (MPI_COMM_WORLD, &myrank);
    MPI_Comm_size (MPI_COMM_WORLD, &numprocs);

    if (myrank == 0) /* root */
    {
        int i;
        mynumber = 2;
     
        /* Send numbers [3,100] through the pipe, in order */   
        for (i=3; i<=100; i++)
            /* p0 is part of the pipe, so check numbers here, too */
            if (should_pass (i, mynumber))
                MPI_Send (&i, 1, MPI_INT, myrank+1, TAG_DATA, MPI_COMM_WORLD);

        /* Done with all the numbers, so send the terminator through the pipe */
        send_term (myrank+1);
    }
    else if (myrank < (numprocs - 1)) /* middle of pipeline */
    {
        while (TRUE)
        {
            /* Recieve a number */
            MPI_Recv (&temp_recv, 1, MPI_INT, myrank-1, TAG_DATA, MPI_COMM_WORLD, &status);

            /* If what we recieved was the terminator, send the terminator on,
             * then leave the loop. */
            if (temp_recv == TERMINATOR)
            {
                send_term (myrank+1);
                break;
            }

            /* If this was not a terminator, and we don't have a number already,
             * then the number that came through must be prime, so store it. */
            if (mynumber == BAD_NUM)
                mynumber = temp_recv;

            /* Check any number that comes in to see if it's prime, and forward
             * it through the pipe if it is a prime number */
            if (should_pass (temp_recv, mynumber))
                MPI_Send (&temp_recv, 1, MPI_INT, myrank+1, TAG_DATA, MPI_COMM_WORLD);
        }
    }
    else /* end of pipeline */
    {
        while (TRUE)
        {
            /* Recieve a number */
            MPI_Recv (&temp_recv, 1, MPI_INT, myrank-1, TAG_DATA, MPI_COMM_WORLD, &status);

            /* If what we recieved was the terminator, leave the loop now.
             * No need to forward it, since we are the end of the pipeline. */
            if (temp_recv == TERMINATOR)
                break;

            /* If this was not a terminator, and we don't have a number already,
             * then the number that came through must be prime, so store it. */
            if (mynumber == BAD_NUM)
                mynumber = temp_recv;

            /* Check any number that comes in to see if it's prime, and print an
             * error if we should pass it on, since we don't have anywhere to
             * forward it to. */
            if (should_pass (temp_recv, mynumber))
                printf ("ERROR: not enough processes. Number = %d\n", temp_recv);
        }
    }

    /* Every process should print it's prime number */
    print_num (myrank, mynumber);

    MPI_Finalize ();

    return 0;
}