Description A versatile scholar, Eratosthenes of Cyrene (today Libya) lived approximately 275195 BC. He was the first to estimate accurately the diameter of the earth. For several decades, he served as the director of the famous library in Alexandria. He was highly regarded in the ancient world, but unfortunately only fragments of his writing have survived. Eratosthenes died at an advanced age from voluntary starvation, induced by despair at his blindness. Eratosthenes also conceived the Sieve of Eratosthenes, a method for identifying prime numbers. Therefore, in a first step the set of natural numbers P = 2, , N from 2 to an upper limit N (in arbitrary ordering) is formed. Then, after searching for the minimum element p of set P the first prime number all multiples of p are deleted from P. Successively repeating this step until p > there are only prime numbers left. Example: N = 15, i.e. termination for p = 3 (= ) 1. step: 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 p = 2 delete multiples: 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 2. step: 3 , 5 , 7 , 9 , 11 , 13 , 15 p = 3 delete multiples: 3 , 5 , 7 , 9 , 11 , 13 , 15 termination (only prime numbers left), i.e. PRIME = 2, 3, 5, 7, 11, 13 2 Implementation 1. Implement a program sieve in C or C++ following the algorithm described above. Think about sufficient data structures for storing the elements in order not to process any element more than once that has already been discarded from the set. Run your program for different values of N, i.e. 1,000,000, 5,000,000, 10,000,000, 25,000,000, and 50,000,000 if your computer permit. What do you observe? For control, always print the largest prime number found! 2. For a faster processing, parallelisation is inevitable. In a first (and simple) approach, scan your code for prominent blocks of instructions that would benefit from multi- threading. Extend these blocks of instructions with valid OpenMP directives in order to allow a parallel processing. Run your code for different values of N (see above) and different amount of threads (2, 3, and 4). What do you observe now? For control, always print the largest prime number found! 3. For further parallelization, message passing is the name of the game. Think about a sufficient parallelization strategy and what code changes have to be made. Extend your program sieve from (1.) not the OpenMP version! with the necessary parallel functionality using MPI. Try to think and use the collective communication commands. Run your program for different values of N, i.e. 1,000,000, 5,000,000, 10,000,000, 25,000,000, and 50,000,000 if your computer permit, and different amount of processes (i.e. 2, 4, and 8). What do you observe now? For control, always print the largest prime number found! 3 Benchmark Sketch your results (i.e. execution times) of your OpenMP/MPI program for different N and different amount of processes in two diagrams showing speed-up or parallel efficiency. You can use any plotting tool (Excel, Python, etc.) of your choice. In order to benchmark your results, also make a theoretical approach to compute speed-up and efficiency according to Amdahl. Therefore, estimate the serial part of your program and compute the corresponding speed-up and efficiency values. Compare those with the ones measured and discuss your observation! Please refer to Chapter 3 in introduction to parallel programming textbook: section 3.6.3 and 3.6.4 when you writing up the analysis part of your report. 4 Report and presentations Write a final report (45 pages) including a brief description of your chosen parallelization strategy and the necessary MPI communication in your code (i.e. sketch the communication idea). The report should further highlight your achieved results for both parallelization approaches (i.e. OpenMP and MPI) including your diagrams and benchmark results from (3). Evaluate your results, i.e. discuss if in your opinion your results are good or bad and where you might have lost performance within your parallelization. The quality of the write-up is part of the grade. Moreover, please provide presentation along with the report.5 Project Due For successfully finishing the project students have to send their final report and presentation together with all programs (i.e. source code) not later than 5 February via blackboard. One submission per group is enough. Please ensure to have your group number (see below) on the first page of the report. Presentation showcase will be on Thursday 7 February 2023 Any submission after the deadline may be graded for correctness, but not credited! 6 Other The project is intended to be worked in groups of 3 students. Look for project partners and mail names to my email not later than 3 January 2023 for group number assignment. Once groups have been assigned they cannot be changed! Always use the assigned group numbers in any kind of correspondence. In case of problems or questions students can always seek help during office hours or via mail, and of course in consultations with one another.