DM818 Mandatory Assignment 4

Overview

The purpose of this assignment is apply methods and techniques you learned to a project of your own choice. You choose an algorithm to be parallelized and to be analyzed yourself. The following requirements have to be fulfilled:

You are required to submit an implementation that can be executed on the Franklin Cluster.
You have to use the message-passing paradigm for your implementation.
It should be possible to use a large number of processors to solve the problem of your choice with your implementation (at least hundreds).
Communication overhead, scalability, and efficiency have to be analyzed empirically. If an isoefficiency analysis is easily possible, then it has to be done. You should consider simplifications that may make an analytical isoefficiency analysis possible.
You should try to choose a problem that is not too similar to a problem for which the isoefficiency analysis is aleady discussed in the course book. Very easy problems for which a scalability analysis is trivial are not acceptable.

Project suggestions will be given in week 46, however you are very welcome to not follow the project suggestions. Note that the course book is also a source for finding projects proposals (especially the exercise part of Chapters 8-13).

The last mandatory assignment is solved in two phases:

Phase 1

In phase 1 of this assignment you have to submit a short problem specification. This document should have a length of approx. 0.5 - 1 page. Within this document you should give the following information:

The names of the people in your group.
What problem are you going to solve?
How are you going to investigate scalability? (Are you planning to do an isoefficiency analysis? Are you planning to use other scalability measures? Are you planning to investigate the communication overhead analytically?)
Literature that you are going to use and that you already know of.
Contact e-mail address(es) that we should use for sending you our response.

For submitting the required problem specification, proceed as follows: Use this template to create the file specification.pdf and put the final pdf-document in a directory with the name mandatory4-phase1. Then change to the directory mandatory4-phase1 and type aflever DM818.

The strict deadline for submission (electronically and the print-out in the secretaries office) is Friday, November, 20th, 10:00am. However, you are welcome to hand in the problem specification earlier. We will try to review your specification as fast as possible. You will either get the information that no changes are required, or we might request for a re-submission.

Phase 2

In phase 2 you follow the plan we agreed upon (justified changes during phase 2 are of course possible, however you have to inform me in the case of significant changes). As usual, you have to hand in a written report, the source code of your implementation, and the results. In addition to that you will have to make a short presentation of what you did. This presentation has to be done in week 51 and should have a length of approx. 10-15 minutes. The deadline for submission of the final report will be after the presentation (see submission deadline below).

Report / Submission

The assignment can be done in groups of two or three people (preferably groups of two or three, in exceptional cases you can also work alone). The submission of the source code has to be supplemented by a write-up (max. 15 pages), one write-up for the whole group. The write-up should contain in any case:

The names of the people in your group.
A statement of who contributed with what.
An introduction and a specification of the problem.
A discussion of related work that you used or that you found related enough to be mentioned (note that you are requested to search for related literature).
A description of the design choices that you tried and how they affected the performance.
A discussion and a description of the tests that you performed and what the outcome was.
An analytical and/or and empirical analysis of scalability and/or isoefficiency.
A conclusion.
A list of references.

For submitting the report and the sources proceed as follows: Create the following directory structure on one of IMADAs pool machines:

mandatory4-phase2/
mandatory4-phase2/report/
mandatory4-phase2/sources/
mandatory4-phase2/results/

Put your report, sources, and results in the corresponding directory. The sources directory should include all files that are necessary to produce an executable code on the Franklin Cluster. The sources directory and the results directory should also contain a README file that describes details. It basically has to be possible to copy the complete sources to the file system of the system of your choice, and to produce executable files via a simple make command. The report directory, the sources directory, and the results directory should not contain more than 10MB of data each.

After putting all the data to the correct location, change to the directory mandatory4 and type aflever DM818.

Additionally, you shall hand in a printout of your report and of your source code (15 pages limit applies only to the report, not to the source code). (Department secretaries office).

The strict deadline for submission (electronically and printouts) is Friday, December, 18 th, 10:00am.

Frequently Asked Questions (FAQ)

Are we allowed to work in groups?

Yes, we actually recommend to do so. You should clearly state who contributed with what in the report.

Parallel Computing