OpenMP - Project 1 - Solved

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.

This problem has particular importance in the design of future high performance interconnection networks for supercomputer architectures, because it represents a quantity that is similar to the more fundamental network bi-section width: the minimum number of edges required to be cut in order to separate the network roughly into two halves. We may cover some of these concepts in more detail later in the subject.

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.

2.1)   Make sure to think about achieving as much performance as you can on a 4 socket cluster node on Spartan; that may require you to consider its NUMA characteristics, and other OpenMP techniques as discussed in the lectures.

3)    Design and apply an appropriate methodology for testing the performance of your parallel implemention on a 4 socket cluster node. Your experiments should at the very least, i.e. to pass, show measurements of speedup versus number of threads/cores. You may also show more detailed measurements that demonstrate that the techniques you have implemented are indeed contributing to the performance of your approach; in order to achieve a higher grade in the project.

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.4)   Discussion and Conclusion (1050 words): analyze your experimental results, and discuss how they provide evidence either that your parallel techniques were successful or otherwise how they were not successful or, as may be the case, how the results are inclusive. Provide and justify, using theoretical reasoning and/or experimental evidence, a prediction on the performance you would expect using your parallel technique as the number of sockets in the single node were to increase, i.e. as the number of cores of such a single node were to increase to a much larger number; taking architectural aspects and technology design trends into account as best as you can - this may require some speculation.

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.