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