Consider the following program:

Analyse the above code and answer following questions:

· Consider whether all statements are atomic and transform the program to load/store architecture if needed.

· Identify the conflicting pairs of atomic instructions.

· State an upper bound on the possible number of outcomes for this program based on the number of processes and atomic instructions in this program.

· State an upper 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 ‘k’? Justify your answer.

 Question 2: Process Interleaving with Control Flow [10 marks]

Consider the following program:

Answer following questions:

(i) Consider whether all statements are atomic and transform the program to load/store architecture if needed.

(ii) Identify all conflicting pairs of atomic instructions.

(iii) 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 all ways to interleave instructions assuming a fair scheduler? Does the program also terminate for execution scenarios that are unique to an unfair scheduler? Justify your answers. (Reminder: with a fair scheduler no process is deferred forever).

 Question 3: Graph Processing - Introduction [15 marks]

This question lays the foundation for the remaining assessments on the implementation of concurrent graph processing operations. In this assignment you will complete the implementation of a graph processing program. A skeleton program is available in a git repository. 1 You will extend the code by completing the implementation of key data structures to represent graphs.

The code models graph analytics applications as a repeated graph traversal. Each traversal operates like a higher-order map method: all edges of the graph are visited and a user-supplied method is called for each edge. This method performs a function specific to the graph analytics. For instance, in PageRank it consists of a floating-point addition, while the label propagation algorithm performs a ‘minimum’ operation on integers. The actual operation performed is not of immediate interest to us. We will focus our attention on completing the graph data structures. An accompanying document, available on canvas, gives additional information on the PageRank problem. It is useful to familiarise yourself with the PageRank problem for debugging and validation purposes.

The code may operate using one of three graph data structures (CSR, CSC or COO, defined in the slides). Implement the omitted code for calculating out- degrees (an auxiliary method required by PageRank) and for the edgemap method for each of the COO, CSR, and CSC sparse matrix formats. You only need to modify the files SparseMatrix{COO|CSR|CSC}.java. Keep the

command-line interface of the Driver.java program as is and keep the damping factor at 0.85. Test your code thoroughly as you will extend it in the next question. Confirm that all three versions calculate the same PageRank values, up to an error tolerance of 10-7.

Perform following experiments using your implementation and the orkut_undir2

graph and briefly answer these questions:

(i) Record the residual error (printed to the console by the PageRank operation) at the end of each iteration of the power method for each of the three matrix formats. Plot these values in a chart (consider log-scale). Summarise your observations.