To find all prime numbers up to some limit value N, the sequential version of this algorithm works as follows:
This week's project is to create a hybrid version of this algorithm that uses MPI to distribute "the sieve" across different PEs, and uses OpenMP to speed up the processing on those PEs.
Download sieve.c and this Makefile. Make and run it to verify that it is working correctly.
Then rerun it, using a large limit value (e.g., 1,000,000,000 or more) and 1 process, and record the execution time in a spreadsheet.
Then run it again using 2 processes and verify that its execution time is faster than was the case with 1 process. Repeat this with 4, 8, 16, and 32 processes, to see how well it scales.
There are many ways in which the program can be improved.
Your task is to write sieve2.c: an improved version of Eratosthenes Sieve that uses MPI for the interprocess communication and uses OpenMP to multithread the computation a given process performs. You may either adapt sieve.c (i.e., add OpenMP to MPI), or start from scratch and build/design/implement sieve2.c from the ground up.
For this assignment, use 4 OpenMP threads per process. You should develop and test your sieve2.c program in the ulab, and then move both it and sieve.c to Dahl to compare their performance.
On Dahl, run the original sieve.c program using a large limit value (e.g., 1,000,000,000 or more) and 4, 8, 16, 32, 64, 128, and 256 processes. Record their execution times in a spreadsheet. Then repeat this using your sieve2.c hybrid version using 4, 8, 16, 32, 64, 128, and 256 threads to quantify your performance improvement.
This is a one week project.
CS > 374 > Exercises > 08 > Homework Project