Subversion Repositories programming

Rev

Rev 314 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
314 ira 1 
/*******************************************************************************
2 
 * prob3.c - implement a parallel (pipelined approach) system for the
3 
 *           Sieve of Eratosthenes problem.
4 
 *
5 
 * Copyright (c) 2006, Ira W. Snyder (devel@irasnyder.com)
6 
 ******************************************************************************/
7 
 
8 
#include <mpi.h>
9 
#include <stdio.h>
10 
#include <stdlib.h>
11 
 
12 
#define TAG_DATA   0x1010
13 
#define TERMINATOR 0xffff
14 
#define BAD_NUM    -1
15 
 
16 
#define FALSE 0
17 
#define TRUE  1
18 
 
315 ira 19 
/* Check if we should pass num on, based on mynumber */
314 ira 20 
int should_pass (int num, int mynumber)
21 
{
22 
    if (num % mynumber == 0)
315 ira 23 
        return FALSE; /* evenly divisible, DO NOT PASS */
314 ira 24 
 
315 ira 25 
    return TRUE; /* not evenly divisible, GO AHEAD */
314 ira 26 
}
27 
 
315 ira 28 
/* Print out this processes number nicely.
29 
 * Ignore processes that don't have a number. */
314 ira 30 
void print_num (int myrank, int mynumber)
31 
{
32 
    if (mynumber == BAD_NUM)
33 
        return;
34 
 
35 
    if (myrank < 10)
36 
        printf ("Proc 0%d's Prime: %d\n", myrank, mynumber);
37 
    else
38 
        printf ("Proc %d's Prime: %d\n", myrank, mynumber);
39 
}
40 
 
315 ira 41 
/* Send the terminator to to_proc */
314 ira 42 
void send_term (int to_proc)
43 
{
44 
    int temp = TERMINATOR;
45 
    MPI_Send (&temp, 1, MPI_INT, to_proc, TAG_DATA, MPI_COMM_WORLD);
46 
}
47 
 
48 
int main (int argc, char *argv[])
49 
{
50 
    int myrank, numprocs;
51 
    int mynumber = BAD_NUM;
52 
    int temp_recv;
53 
 
54 
    MPI_Status status;
55 
 
56 
    MPI_Init (&argc, &argv);
57 
    MPI_Comm_rank (MPI_COMM_WORLD, &myrank);
58 
    MPI_Comm_size (MPI_COMM_WORLD, &numprocs);
59 
 
315 ira 60 
    if (myrank == 0) /* root */
314 ira 61 
    {
62 
        int i;
63 
        mynumber = 2;
315 ira 64 
 
65 
        /* Send numbers [3,100] through the pipe, in order */
314 ira 66 
        for (i=3; i<=100; i++)
315 ira 67 
            /* p0 is part of the pipe, so check numbers here, too */
314 ira 68 
            if (should_pass (i, mynumber))
69 
                MPI_Send (&i, 1, MPI_INT, myrank+1, TAG_DATA, MPI_COMM_WORLD);
70 
 
315 ira 71 
        /* Done with all the numbers, so send the terminator through the pipe */
314 ira 72 
        send_term (myrank+1);
73 
    }
315 ira 74 
    else if (myrank < (numprocs - 1)) /* middle of pipeline */
314 ira 75 
    {
76 
        while (TRUE)
77 
        {
315 ira 78 
            /* Recieve a number */
314 ira 79 
            MPI_Recv (&temp_recv, 1, MPI_INT, myrank-1, TAG_DATA, MPI_COMM_WORLD, &status);
80 
 
315 ira 81 
            /* If what we recieved was the terminator, send the terminator on,
82 
             * then leave the loop. */
314 ira 83 
            if (temp_recv == TERMINATOR)
84 
            {
85 
                send_term (myrank+1);
86 
                break;
87 
            }
315 ira 88 
 
89 
            /* If this was not a terminator, and we don't have a number already,
90 
             * then the number that came through must be prime, so store it. */
91 
            if (mynumber == BAD_NUM)
92 
                mynumber = temp_recv;
93 
 
94 
            /* Check any number that comes in to see if it's prime, and forward
95 
             * it through the pipe if it is a prime number */
96 
            if (should_pass (temp_recv, mynumber))
97 
                MPI_Send (&temp_recv, 1, MPI_INT, myrank+1, TAG_DATA, MPI_COMM_WORLD);
314 ira 98 
        }
99 
    }
315 ira 100 
    else /* end of pipeline */
314 ira 101 
    {
102 
        while (TRUE)
103 
        {
315 ira 104 
            /* Recieve a number */
314 ira 105 
            MPI_Recv (&temp_recv, 1, MPI_INT, myrank-1, TAG_DATA, MPI_COMM_WORLD, &status);
106 
 
315 ira 107 
            /* If what we recieved was the terminator, leave the loop now.
108 
             * No need to forward it, since we are the end of the pipeline. */
314 ira 109 
            if (temp_recv == TERMINATOR)
110 
                break;
315 ira 111 
 
112 
            /* If this was not a terminator, and we don't have a number already,
113 
             * then the number that came through must be prime, so store it. */
114 
            if (mynumber == BAD_NUM)
115 
                mynumber = temp_recv;
116 
 
117 
            /* Check any number that comes in to see if it's prime, and print an
118 
             * error if we should pass it on, since we don't have anywhere to
119 
             * forward it to. */
120 
            if (should_pass (temp_recv, mynumber))
121 
                printf ("ERROR: not enough processes. Number = %d\n", temp_recv);
314 ira 122 
        }
123 
    }
124 
 
315 ira 125 
    /* Every process should print it's prime number */
314 ira 126 
    print_num (myrank, mynumber);
127 
 
128 
    MPI_Finalize ();
129 
 
130 
    return 0;
131 
}
315 ira 132