Due: April 15th, 2024 @ 23:59

Weight: 50%

Maximum Marks: 100 (70 group marks + 30 individual marks)

Learning Outcome

This assessment tests your ability to:

A.     Demonstrate understanding of the concepts used in modern processors for increasing the performance.

B.     Demonstrate optimization techniques for serial code.

C.     Understand and apply parallel computing paradigms.

D.    Write optimized programs designed for high-performance computing systems.

Overview

The Sieve of Eratosthenes is an ancient algorithm attributed to the Greek mathematician

Eratosthenes. It efficiently identifies prime numbers by iteratively marking the multiples of each prime number as composite. This process eliminates the need to repeatedly test every number  for primality, making it a practical and efficient method for finding primes within a given range.

The algorithm's effectiveness and simplicity have led to its widespread application in computer science and number theory, providing a valuable tool for identifying prime numbers and studying their distribution characteristics.

Our objective is to develop a parallel version of this algorithm based on mpi4py. It should support prime number search within the range of 100 million and be capable of handling parallel computation with at most 8 processes.

Team policy

You are free to team up from minimum of 4 to maximum of 5 team members, and you must choose your team on LMO before 15th March, 23:59. Students who fail to do so will be randomly assigned. Changes will not be allowed once settled.

Avoid Plagiarism

. Do not submit work from other teams.

. Do not share code/work to students other than your own team members.

. Do not read code/work from other teams, discussions between teams should remain high level.

. Do not use code from the Internet, Generative AI, or published textbooks.

1.  Group Tasks (70 marks)

Tasks

1)   The pseudocode for the serial version of this algorithm is:

For example, when n=10, the program will output 4. This is exactly the number of prime  numbers between 2 and 10 (2, 3, 5, 7). Please give the design of a parallel version of this program based on Foster’s Methodology. (25 Marks)

2)   Implement your design plan. Make sure your code is consistent with the design and has the necessary comments. Record its running time and results in the table below. Note: You can run the program once to allow the system to "warm up." Then run it a few more times and  record the relatively stable running time.

Total number of primes between 2 and 100,000,000 is :                               (20 Marks)

3)   Please explain what methods  (no more than two) you used (you cannot call third-party

algorithm libraries) to: 1) shorten the average running time of the program; 2) improve its acceleration ratio.  (10 Marks)

4)   Do you think your program achieves linear speedup? Please draw the plot, and design a statistical hypothesis test to verify your conclusion.  (15 Marks) Note：An example of the speedup graph is shown below. The horizontal axis is the number of processes, and the vertical axis is the speedup ratio.

2.  Peer Review (30 individual marks)

Review your peers based on the project contribution. This will be done on LMO anonymously, each of the group members should log in to their LMO account and submit the marks individually. Marks should be submitted within 7 days after the group work submission is done. Peer review rubrics are attached in the Appendix.

3.  Submission

One of the group members must submit the following files to LMO:

1)  A report named as Your_Student_ID.pdf.

2)  A directory containing all your source code, named as Your_Student_ID_code.

NOTE: The report shall be in A4 size, size 11 font, and shall not exceed 3 pages in length. You can include only key code snippets in your reports. The complete source code can be placed in  the attachment.