ASSIGNMENT 1
CSC3021 Concurrent Programming 2018-2019
Submit by 5:59 pm on Monday 15th October 2018
Question 1: Proces Interleaving: Straight-Line Code
Consider the following program:
Analyse the above code and answer folowing questions:
• Consider whether al statements are atomic and transform. the program
to load/store architecture if neded.
• Identify the conflicting pairs of atomic instructions.
• State an uper bound on the possible number of outcomes for this
program based on the number of processes and atomic instructions in
this program.
• State an uper bound on the possible number of outcomes for this
program based on the number of conflicting pairs found.
• What are the possible final values of ‘n’ and ‘m’? Motivate your
answer.
Question 2: Process Interleaving with Control Flow
Consider the folowing program:
Answer folowing questions:
(i) Consider whether al statements are atomic and transform. the program to
load/store architecture if neded.
(ii) Identify al conflicting pairs of atomic instructions.
Process P
P1: n := m + 1
end P;
Process Q
Q1: m := n + 1
end Q;
integer n := -1, m := 1
Process P
P1: while flag = false
P2: n := 1 - n
end P;
Process Q
Q1: while n = 0
; // nothing
Q2: flag := true
end Q;
integer n := 0
boolean flag := false
2
(ii) Construct an interleaving of instructions of the processes ‘P’ and ‘Q’ for
which the program terminates.
(iv) What are the possible values of ‘n’ when the program terminates? Can
you argue that other values than those you have listed for ‘n’ are
impossible?
(v) Does the program terminate for al ways to interleave instructions
assuming a fair scheduler? Does the program also terminate for execution
scenarios that are unique to an unfair scheduler? Motivate your answers.
(Reminder: with a fair scheduler no process is deferred forever).
Question 3: PageRank
This question lays the foundation for the second assessment: the
implementation of a concurrent PageRank. In this assignment you wil
implement a sequential (single-threaded) program that solves the PageRank
problem. In the second assignment, you wil convert the sequential program
into a concurrent program. To that it, you wil ned to thoroughly understand
the sequential program.
Read the accompanying document on the PageRank problem, available from
a GIT repository.
1
Implement the power iteration step for each of the CSR,
CSC and CO sparse matrix formats. You can base your code on the file
PageRankSkeleton.java. Keep the command-line interface as is and keep the
damping factor at 0.85. Test your code thoroughly as you wil extend it in the
next assignment. Confirm that al three versions calculate the same
PageRank values, up to an error tolerance of 10
-7
.
Perform. folowing experiments using your implementation and the orkut_undir
graph and briefly answer these questions:
(i) Record the residual error at the end of each iteration of the power method
for each of the three matrix formats. Plot these values in a chart.
Summarise your observations.
(ii) Report the execution time of each individual power iteration step for each
representation using a chart. What do you observe about the time taken
per iteration?
(ii) Calculate the total execution time over al iterations for the CSR, CSC and
CO matrix formats. Comment on the relative sped when using the
CSR, CSC or CO formats. Can you explain this result?
(iv) Modify your code to use single-precision floating-point numbers instead of
double-precision floating-point numbers for one of the three sparse matrix
formats. Record the residual error at the end of each power iteration step
and the average execution time when using single-precision vs. double-
1
https:/gitlab.eeecs.qub.ac.uk/csc3021/csc3021_assignments_1819/ This gitlab
server is run by the Schol of EECS and is accessible using your EECS
credentials (student number and the same password as in the CSB labs). You can
clone this repository and work of it. Check the README.md file for instructions.
3
precision floating-point numbers. Report these numbers using charts. Can
you explain this result?
Input Files
You can find three graph data sets in CSR, CSC and CO format at
htp:/ww.eecs.qub.ac.uk/~H.Vandierendonck/CSC3021/graphs
These graphs have varying sizes and wil result in varying processing times.
All of these can be comfortably processed in a few minutes on the lecturer’s
laptop, which has a 1.6 GHz Intel Core i5 processor and 8GB main memory.
Each file begins with a one-line header stating the graph format: CO, CSC,
CSR or CSC-CSR. The later aplies only to undirected graphs, which have
the property that the CSC and CSR representations are equal. The next two
lines then specify the number of vertices and number of edges. Then, the file
formats diverge:
• The CO format contains one line per edge, each containing two
integers: the ID of the source vertex folowed by the ID of the
destination vertex.
• The CSR format contains one line per vertex. The first integer on the
line is the ID of the source vertex. Every subsequent ID on the same
line specifies an edge from the first vertex to the listed vertex.
• The CSC format contains one line per vertex. The first integer on the
line is the ID of the destination vertex. Every subsequent ID on the
same line specifies an edge from the listed vertex pointing to the first
vertex listed on that line.
The skeleton program already contains the required code to parse the files,
you just ned to insert the edges in the data structures that you designed.
Submission
Your submission wil consist of three parts: a program implementing the
PageRank problem submited to a EEECS gitlab repository, the same
program submited to an online test server, and a write-up.
• Develop your code through a private git repository hosted on
gitlab.eecs.qub.ac.uk to which you wil provide read access to the
user . Provide at least reporter aces.
Submission of the code wil occur by specifying the repository and the
branch or commit ID that corresponds to your submited code by email
to .
Make sure to make frequent commits to the repository as the commit
history wil be taken into account should cases of plagiarism or
colusion ned to be dealt with.
• The double precision version of your code wil be submited through an
online testing and evaluation system available at
htp:/hvan.eecs.qub.ac.uk/domjudge using the contest ‘1819_prseq’.
This system wil test the correctness of your code on a few sample
graphs. The relative ranking of your code compared to others is
irrelevant. You wil be informed of your login credentials for this site in
due time.
• The write-up is a PDF document containing your answers to Questions
1-3. Submit it through TurnItIn. Do not put your name, student ID or
4
other identifying information in the write-up as it wil be reviewed
anonymously by other students.
As an indication of the level of detail expected for Question 3, it will be
at most 2 sides of an A4 page. The minimum font size should be 1
point and margins must be at least 2cm in al directions. Only a
standard ‘Arial’ or other ‘Sans Serif’ font should be used. Excess pages
may be ignored during marking. No page limit is enforced on Questions
1 and 2.
Guidance: Mark distribution:
Q1: 5 marks; Q2: 5 marks; Q3: 4 marks correctness of the code, 5 marks
report; Peer Review: 1 mark.
This assignment contributes to 20% of the marks for CSC3021.