PRIME is a version of the prime summing program that we have seen earlier. Your task is to make an MPI version of it. If you become interested in this problem, then your secondary task can be to make an efficient MPI version of it.
The original program sums the primes from 2 to 100,000. The program you are to start with still has this behavior. However, to help you make an MPI version, the program has broken up the computation into P subloops.
The program should be reasonably easy to convert to MPI. Each process can figure out its subinterval just based on its ID number. The only communication comes at the end, when each process must send its sum back to process 0 to be totaled. This can be done with an MPI_REDUCE call.
As a correctness check, note that, with N equal to 100,000, the prime sum should come out to be 454,396,537.
If you get the program working, and are interested in its behavior, you can consider the following second task:
This program is interesting because it is clear that the amount of work for each loop iteration increases with I. Thus, if the work is to be divided among "equally" among processors, some care should be taken. Since we're dividing the loop work evenly, the last process has significantly more work to do, and slows down the program.
A good estimate for the amount of work required to determine if the integer I is prime is simply I, which is about the number of values we might have to check as possible factors. Thus, the amount of work to check all the integers from I1 to I2 is the sum of all the integers from I1 to I2, which is a quadratic. To divide the work evenly between the processors, we have to break up the interval from 2 to 100,000 into subintervals so that the quadratic expression for work comes out roughly the same.
Here are "completed" versions of the programs.
You can go up one level to the MPI page.
Last revised on 17 September 2008.