# COMP90025 Project 1A – Diameter of Graph solution

\$30.00

Category:

## Description

Summary
The rst project is group work (size at most 2) and is divided into two
parts (so that you can get feedback earlier). This is Part A.
A sequential algorithm for computing the diameter of a graph has
been provided on LMS. The program reads a graph from standard
input (stdin) and outputs the diameter.
The diameter of a graph is dened as the maximum of the shortest
path lengths between all pairs of nodes.
The graph is assumed to be directed and connected, and edge weights
are always greater than 0.
Aaron Harwood and Lachlan Andrew (School of Computing and Information Systems The University of Melbourne) COMP90025 Parallel and Multicore Computing 2019 Semester II 2 / 8
Input format
The rst line of input is a single integer giving the number of vertices
in the graph, N.
The second line is a single integer giving the number of edges, M.
Each subsequent line of the input le provides a tuple of positive
integers:
fromVertex toVertex weight
Vertices are numbered 0 to N − 1.
Aaron Harwood and Lachlan Andrew (School of Computing and Information Systems The University of Melbourne) COMP90025 Parallel and Multicore Computing 2019 Semester II 3 / 8
Example Input
5
10
0 1 5
0 2 2
0 4 15
1 2 6
1 3 1
3 1 4
3 0 9
3 4 2
4 1 6
2 4 1
Aaron Harwood and Lachlan Andrew (School of Computing and Information Systems The University of Melbourne) COMP90025 Parallel and Multicore Computing 2019 Semester II 4 / 8
Example Graph
1
2
5
3
2
5
15 6
4
1
1
6
9
4
2
Figure: Example Graph
Diameter 17, given by the shortest path from vertex 3 to vertex 1.
(In this gure nodes are numbered from 1, unlike in the data le.)
Aaron Harwood and Lachlan Andrew (School of Computing and Information Systems The University of Melbourne) COMP90025 Parallel and Multicore Computing 2019 Semester II 5 / 8
Write an OpenMP program that computes and outputs, in the same
way, the diameter of a given graph as done by the sequential program.
Aim to have your program run as fast as possible. In doing so, you
may alter the calculations of the program, so long as the nal output
is correct.
Use the sequential code as a base. Do not change the le before the
end of main(). If you need to include additional headers, they can be
included after main(). In particular, do not alter the timing
Write at most 550 words that outlines how you achieved
parallelism/high performance. Include tables and/or charts of your
own measurements that support your discussion.
Write at most 200 additional words that discuss Illiac. Describe the
important features of the architecture in the terms introduced in this
course. Discuss whether the algorithm you used in this project would
be suitable for running on any of the Illiac computers.
Aaron Harwood and Lachlan Andrew (School of Computing and Information Systems The University of Melbourne) COMP90025 Parallel and Multicore Computing 2019 Semester II 6 / 8
Assessment
Project 1 A is worth 7% of your total assessment. It is group work in
size of 2 at most.
Assessment of the report (3/7) is based on the level of details and
presentation.
Assessment of the program (4/7) is based on correctness and
performance. Incorrect programs (i.e. that give incorrect outputs or
that fail to compile/run) will attract few if any marks. The top 5
fastest running programs, when given a mystery work load (you will
not be told the work load in advance), will be given a bonus mark; i.e.
the maximum mark for this project part is 8/7.
At most ve people will get the bonus mark. If a sixth person is tied
with anyone in the top ve, then anyone tied with that sixth person
will not receive a bonus mark.
Aaron Harwood and Lachlan Andrew (School of Computing and Information Systems The University of Melbourne) COMP90025 Parallel and Multicore Computing 2019 Semester II 7 / 8
Submission
Submit a PDF of your report (use PDF only, no other format will be
assessed) via LMS on or before Saturday 31st August. As well you
will need to submit your program (either via LMS or directly on
Spartan). Instructions for doing this will be given closer to the