Project 1 Description A versatile scholar, Eratosthenes of Cyrene (today Libya) lived approximately 275-195 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>N there are only prime numbers left. Example: N=15, i.e. termination for p=3(=15) 1. step: 2,3,4,5,6,7,8,9,10,11,12,13,14,15p=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,15p=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 multithreading. Extend these blocks of instructions with valid OpenMP directives in order University of Jeddah, KSA College of Computer Science and Engineering 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! Project 1 Description A versatile scholar, Eratosthenes of Cyrene (today Libya) lived approximately 275-195 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>N there are only prime numbers left. Example: N=15, i.e. termination for p=3(=15) 1. step: 2,3,4,5,6,7,8,9,10,11,12,13,14,15p=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,15p=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 multithreading. Extend these blocks of instructions with valid OpenMP directives in order University of Jeddah, KSA College of Computer Science and Engineering 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