辅导PageRank、讲解Java程序语言、辅导single-threaded、Java辅导

日期：2018-10-15 11:09

(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? 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 will

implement a sequential (single-threaded) program that solves the PageRank

problem. In the second assignment, you will convert the sequential program

into a concurrent program. To that it, you will need 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 COO 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 will extend it in the

next assignment. 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_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?

(iii) Calculate the total execution time over all iterations for the CSR, CSC and

COO matrix formats. Comment on the relative speed when using the

CSR, CSC or COO 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 School of EEECS and is accessible using your EEECS

credentials (student number and the same password as in the CSB labs). You can

clone this repository and work off it. Check the README.md file for instructions.

3

precision floating-point numbers. Report these numbers using charts. Can

you explain this result?

InputFiles

You can find three graph data sets in CSR, CSC and COO format at

http://www.eeecs.qub.ac.uk/~H.Vandierendonck/CSC3021/graphs

These graphs have varying sizes and will 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: COO, CSC,

CSR or CSC-CSR. The latter applies 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 COO format contains one line per edge, each containing two

integers: the ID of the source vertex followed 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 need to insert the edges in the data structures that you designed.

Submission

Your submission will consist of three parts: a program implementing the

PageRank problem submitted to a EEECS gitlab repository, the same

program submitted to an online test server, and a write-up.

Develop your code through a private git repository hosted on

gitlab.eeecs.qub.ac.uk to which you will provide read access to the

user csc3021@qub.ac.uk. Provide at least reporter access.

Submission of the code will occur by specifying the repository and the

branch or commit ID that corresponds to your submitted code by email

to csc3021@qub.ac.uk.

Make sure to make frequent commits to the repository as the commit

history will be taken into account should cases of plagiarism or

collusion need to be dealt with.

The double precision version of your code will be submitted through an

online testing and evaluation system available at

http://hvan.eeecs.qub.ac.uk/domjudge using the contest ‘1819_prseq’.

This system will test the correctness of your code on a few sample

graphs. The relative ranking of your code compared to others is

irrelevant. You will 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