AE2OSC: Operating Systems & Concurrency
Coursework: Sieve of Eratosthenes
Spring 2015
Deadline: Monday, May 4th, 2015, 09:00 am
Cut-off Date: Tuesday, May 5th, 2015, 09:00 am Weight: 50% of the module mark
How to submit: Via Moodle
1 Sieve of Eratosthenes
We have already discussed a parallel implementation of the Sieve of Eratosthenes using MPI in the lectures. You can find out more in Chapter 5 of [Quinn, 2003], where a number of improvements to the parallel algorithm have been suggested but not implemented.
Your tasks for this coursework will be to implement those suggested improve- ments, benchmark your new programs, and finally compare the performance with the original version.
1.1 Original program
You will make the improvements over the original program that is fully explained in Chapter 5 of [Quinn, 2003]. You can also find the source of this program on Moodle in the file:
sieve_Original.c
2 Tasks
Your tasks for this coursework will be as follows:
Task 1 (20)
Modify the original parallel Sieve of Eratosthenes program to incorporate the fol- lowing improvements. You can find out more details about these in Section 5.9 of [Quinn, 2003]:
1
Deleting Even Integers: There is no need to set aside memory for even integers because we know that apart from 2, there is no other even prime. With this improvement, the need for memory allocation will be cut in half and as a result, the program should run faster accordingly.
Eliminating broadcast: Each process should use the sequential Sieve of Eratos- √
thenesalgorithmonaseparatearraytofindallprimesupto⌊ n⌋.Withthis information, the call to MPI Bcast can be eliminated.
This improvement should show its effect more strongly when the program is run on a higher number of processes.
After making these modifications, benchmark your program, comparing its per- formance with that of the original parallel sieve program. In particular, you should run both programs on different machines (e. g. your own machine, School’s Linux Server, etc) with different input arguments and different number of processes. You should make sound observations and present an informative account of your exper- iment in Task 3.
Task 2 (10)
For this task you should go back to one of the versions of this program that does have a broadcast step, i. e. either the original version or the one working only on odd numbers.
Lester [2006] suggests that the execution time of the program can be improved by replacing the broadcast step with a pipeline of sends and receives. In other words, instead of process 0 broadcasting the next prime to all the other processes, it sends the next prime to process 1, which receives the value and sends it to process 2, and so on. For each prime found, the maximum number of communication steps per process is reduced from ⌈log p⌉ to 2.
Implement a new parallel version of the Sieve of Eratosthenes program, re- placing the broadcast step with a receive/send step. Note that process 0 does not perform a receive, and the process of the highest rank does not perform a send.
Note: If you do not implement your send and receive instructions in the correct order, you may get deadlock.
As with the previous task, benchmark the original program and the new pro- gram and present your observations in Task 3.
Task 3 (20)
You should write a very short account of your experiments from Tasks 1 and 2. Remember that if parallelizing an algorithm does not result in better efficiency,
2
then it is pointless. Thus, benchmarking is of utmost importance.
3 Marking scheme
The marking scheme for Tasks 1 and 2 (i. e. the programming tasks) are as follows: Correctness: (70%) Your program should work correctly.
Style: (30%) You should follow the usual good practice such as:
• Choosing meaningful names for identifiers.
• Good use of blank lines and indentation to make code more readable. • Inclusion of succinct yet informative comments in the program.
The rule of thumb is, I should be able to read your program easily. If your code is badly written, depending on how bad it is, you may lose all the marks for style.
For Task 3, your report will be marked according to how informative and thor- ough it is. Note that you do not need to write any lengthy document. In fact, a couple of diagrams with a paragraph of clear explanation should do. So, one or two pages (including the figures) should be enough.
To see what kind of diagrams and figures are appropriate, take a look at the figures in [Quinn, 2003], such as Figures 5.7, 5.8, and 5.10.
4 Instructions regarding submission
Pay close attention to the following instructions regarding submission of your coursework:
MPI Sources to submit: You must submit two MPI source files called task1.c and task2.c. If you need to include any extra macros, then you must in- clude them all in the same file, i. e. do not submit header files or any other extra files.
Report on your experiments: You must submit one pdf file documenting your experiments. Again, use LATEX if you can, but pdf documents written origi- nally with LibreOffice or MS Word are also acceptable and you will not lose any marks as long as your pdf document is clearly written.
3
If you intend to scan a handwritten document, then you must write in clear and readable handwriting. If I cannot read any part of your answer, then I will not be able to give any marks to that part.
Late Submissions: For every one hour delay in your submission you will lose 4% of the mark. No submissions will be accepted after the cut-off time of Tuesday, May 5th, 2015, 09:00 am.
Your details on the answer sheet: Please do not forget to include your name and ID on the answer sheet.
References
Bruce P. Lester. The Art of Parallel Programming. 1st World Publishing, Inc., 2006.
Michael J. Quinn. Parallel Programming in C with MPI and OpenMP. McGraw- Hill Higher Education, 2003.
4