Project 2

Prime Number Census with MPI

The question

How many prime numbers are there from 1 through \(N\)? In this project, you will split that search across MPI processes, bring back both a total count and enough detail to see which numbers are prime, and check that the two answers agree.

This brings together the communication patterns from Modules 2–4: broadcast a shared setting, scatter the work, reduce local counts, and gather individual results. You do not need MPI_Sendrecv for this project.

Start with a correct serial test

A prime number is an integer greater than 1 with no divisors other than 1 and itself. Write a C function is_prime(int x) that returns 1 for a prime and 0 otherwise. Return 0 for 1. To test a possible divisor d, you only need to continue while d <= x / d; if no divisor has worked by then, none will. This avoids a math-library call and avoids calculating d * d for very large integers.

Check your function on the numbers 1 through 12. The primes are 2, 3, 5, 7, and 11. Get this part right before adding MPI calls.

Put the pieces together

Write prime_census.c. If command-line arguments are new to you, revisit the Module 5 example. Rank 0 should read \(N\) from the command line; the other ranks should not read it themselves. Use these four MPI operations for distinct jobs:

Operation Job in your program
MPI_Bcast Tell every rank the value of \(N\).
MPI_Scatter Divide the integers 1 through \(N\) into consecutive, equal-sized blocks.
MPI_Reduce Add the local prime counts into one total on rank 0.
MPI_Gather Collect each rank’s 0/1 primality flags in number order on rank 0.

Each process tests only the numbers in its own block. For each number, put a 1 in the matching position of its local flags array if it is prime, or 0 otherwise. Also count the primes in that block. For example, with \(N=12\) and three processes, rank 0 gets 1–4, rank 1 gets 5–8, and rank 2 gets 9–12. Their local counts should be 2, 2, and 1.

After the reduction and gather, rank 0 should count the gathered flags independently and check that this count matches the reduced total. The two operations answer different questions: reduction gives one count without collecting all flags, while gathering lets rank 0 identify each prime. Using both gives you a useful correctness check.

You may use fixed-size arrays as in Module 4. Set a maximum \(N\) of at least 120,000 and keep the large arrays outside main so they do not fill the stack. If you prefer dynamically allocated arrays, that is fine too. Check that \(N\) is between 2 and your chosen maximum and that the process count divides \(N\) before scattering. Have rank 0 print a clear message for unsupported input; all ranks should take the same clean exit path. Unequal blocks with MPI_Scatterv are not required.

TipA useful order for building this

Get is_prime and the serial answer right first. Then add broadcast and scatter; print each rank’s block once to check ownership. Next add the local flags and reduction. Gather flags last, and use them to check the total.

Run and check it

Compile and try several process counts:

mpicc -g -Wall -O2 -o prime_census prime_census.c
mpirun -n 1 ./prime_census 120
mpirun -n 2 ./prime_census 120
mpirun -n 3 ./prime_census 120
mpirun -n 4 ./prime_census 120

All four runs should report 30 primes from 1 through 120 and should pass your reduction-versus-gather check. For this small input, have rank 0 also print the prime numbers, in increasing order. You can compare its beginning with 2 3 5 7 11 13 and its end with 101 103 107 109 113.

Then try \(N=1200\) with one and four processes; the count should be 196. Try \(N=120000\) with one and four processes to see how the program behaves on more work. For the larger runs, print the total and the agreement check, but do not print thousands of prime numbers. Finally, try an invalid combination such as seven processes with \(N=120\); the program should explain why it cannot use that count and exit without hanging.

If a multi-node PicoCluster run prints its complete answer and then hangs in finalization, use the single-node fallback described in Module 5. Keep MPI_Finalize in your source.

Explain your design and results

Write a short explanation (about one page is enough) that includes:

  1. A table showing which numbers ranks 0–3 each own for \(N=120\), and their local prime counts. Do the counts add to 30?
  2. Your results for 1, 2, 3, and 4 processes at \(N=120\), plus 1 and 4 processes at \(N=1200\) and \(N=120000\). Did changing the process count change the mathematical answer?
  3. What information does MPI_Reduce return here, and what extra information does MPI_Gather return? Why is comparing their counts useful?
  4. Would you expect the tiny \(N=120\) case to run faster with four processes? Explain your prediction in terms of computation and communication. You do not need to collect timings.

If a result disagrees with the expected count, show it and describe what you checked. Do not present a mismatched answer as correct.

What to submit

Submit through Moodle:

  • prime_census.c, which compiles without warnings using the command above.
  • Your short explanation and clearly labeled output from the required runs. Include the commands you used and the hostname(s) if you used the PicoCluster single-node fallback.

Do not submit the executable. Leave the program set up to accept \(N\) from the command line; it should not require source edits between the required runs.

Optional challenge

Collect several wall-clock timings for \(N=120000\) with one and four processes. Do you see a consistent speedup? If not, what costs or variation might explain it? Keep this separate from the required correctness checks.

Back to top