Description

Project 1 requires developing and submitting an OpenMP program and a written report. Project 1 is worth
Assessment Tasks
1) Research parallel methods for the following problem: determine the minimum of the maximum flows between all pairs of vertices in a directed graph with weighted edges, where each weight is a real value greater than 0.
1.1) For clarity, let removal of weight w from the graph mean removing any set of edges whose total weight equals w. Then, the maximum flow from a vertex u to a vertex v in such a graph is the minimum amount of weight required to be removed from the graph in order to eliminate all paths in the graph from u to v. The problem is to find the minimum of these maximum flows over all pairs of vertices in the graph.
2) Choose/devise a parallel method, either that you have found in the literature, in part or in full, or that you have devised yourself, in part or in full, and implement it using OpenMP in the C/C++ language such that it will compile and run on a 4 socket cluster node provided via the Spartan HPC at Unimelb.
4) Write a minor report (2000 words not including figures, tables, diagrams or references) with the following sections and details:
4.1) Introduction (250 words): define the problem as above in your own words and discuss the parallel technique that you have implemented. Present the technique using parallel pseudo-code, assuming a PRAM style parallel algorithm syntax as shown in lecture slides. Cite any relevant literature that you have made use of.
4.2) Methodology (350 words): discuss the experiments that you will use to measure the performance of your program, with mathematical definitions of the performanc e measures and/or explanations using diagrams, etc.
4.3) Experiments (350 words): show the results of your experiments, using appropriate charts, tables and diagrams that are captioned with numbers and referred to from the text. The text should be only enough to explain the presented results so it clear what is being presented, not to analyse result.
4.5) References: cite literature that you have cited in preparing your report.
Use the latest ACM Conference Style guide for all aspects of formatting your report, i.e. for font size, layout, margins, title, authorship, etc.
Assessment Criteria
The assessment of software component and written report is weighted 40/60, i.e. 40% of the project marks are focussed on the software component and 60% of the project marks are focussed on the written report.
Assessing a written report requires significant qualitative assessment. The guidelines applied for qualitative assessment of the written report are provided below.
Quality Assessment Guidelines
Quality expectations:
• >=80% – H1. A very good, excellent or outstanding discussion, with at most only minor improvements to conceptual expression or wording that can be identified. A grade in this range is generally considered to reflect the possibility of continuing with research higher degree study in the future and usually about 10% to 20% of students would be awarded this grade.
• 65%-69% – H3. A reasonable discussion that addresses the question but with one aspect of the discussion that is significantly poor in writing style, understanding or missing all together. Usually 75% of students would receive a grade of H3 or above.
• 50%-64% – P. The discussion does not entirely address the question – it is considered to be off topic in some ways, and there is more than one aspect that is significantly poor in writing style, understanding or missing all together.
• 0%-49% – F. The discussion shows a clear lack of understanding/effort, or clearly misunderstood or underestimated what was expected and/or has significant writing style issues. Usually less than 5% of students would receive this grade.
When considering writing style, The “Five C’s of Writing” is adapted here as a guideline for writing/assessing a discussion:
• Clarity – is the discussion clear in what it is trying to communicate? When sentences are vague or their meaning is left open to interpretation then they are not clear and the discussion is therefore not clear.
• Consistency – does the discussion use consistent terminology and language? If different terms/language are/is used to talk about the same thing throughout the discussion then it is not consistent.
• Correctness – is the discussion (arguably) correct? If the claims in the discussion are not logically sound/reasonable or are not backed up by supporting evidence (citations), or otherwise are not commonly accepted, then they are not assumed to be correct.
• Conciseness – is the discussion expressed in the most concise way possible? If the content/meaning/understanding of the discussion can be effectively communicated with less words, then the discussion is not as concise as it could be. Each sentence in the discussion should be concisely expressed.
• Completeness – is the discussion completely covering what is required? If something is missing from the discussion that would have significant impact on the content/meaning/understanding of what it conveys, then the discussion is incomplete.
Submission
• solution.cc: Ensure that your solution is a single file, and include comments at the top of your program that show how to compile and run your program, including examples how to test the correctness and performance of your program, using additional test case input files if you require.
• Report.pdf: The only acceptable format is PDF
• test case inputs: Any additional files, providing test case inputs, that are needed to follow the instructions you provide in your solution’s comments section.