THINK FIRST·CODE LATER

← All labs

Ranks and the critical path

Problem

Compute the ranks used by list-scheduling algorithms.

Input format (used by all Chapter 6 labs):

n p                      (tasks, processors)
n lines: w(i,1) ... w(i,p)   (computation cost of task i on each processor)
m                        (number of edges)
m lines: i j c           (edge i -> j with communication cost c)

Tasks are numbered 1…n. Compute:

  • average cost w̄ᵢ (mean over processors);
  • rank_u(i) = w̄ᵢ + max over successors j of (c(i, j) + rank_u(j)); for exit tasks rank_u = w̄ᵢ;
  • rank_d(i) = max over predecessors j of (rank_d(j) + w̄ⱼ + c(j, i)); for entry tasks rank_d = 0.

Print for each task Ti: avg w A, rank_u U, rank_d D, sum S (two decimals), then Critical path (CPOP): T1 -> T2 -> ... | length L, listing in increasing task number every task whose rank_u + rank_d equals the maximum sum (within 10⁻⁶).

Input:

5 2
4 6
5 3
6 8
3 5
4 2
5
1 2 2
1 3 3
2 5 4
3 4 1
4 5 2

Output:

T1: avg w 5.00, rank_u 25.00, rank_d 0.00, sum 25.00
T2: avg w 4.00, rank_u 11.00, rank_d 7.00, sum 18.00
T3: avg w 7.00, rank_u 17.00, rank_d 8.00, sum 25.00
T4: avg w 4.00, rank_u 9.00, rank_d 16.00, sum 25.00
T5: avg w 3.00, rank_u 3.00, rank_d 22.00, sum 25.00
Critical path (CPOP): T1 -> T3 -> T4 -> T5 | length 25.00

Data for this lab

Your program reads its data from standard input. Download the file, then give it to your program as shown below. Start with data set 1: its expected output is given.

os6-1-data-1.txt

5 2
4 6
5 3
6 8
3 5
4 2
5
1 2 2
1 3 3
2 5 4
3 4 1
4 5 2
What your program must print for os6-1-data-1.txt
T1: avg w 5.00, rank_u 25.00, rank_d 0.00, sum 25.00
T2: avg w 4.00, rank_u 11.00, rank_d 7.00, sum 18.00
T3: avg w 7.00, rank_u 17.00, rank_d 8.00, sum 25.00
T4: avg w 4.00, rank_u 9.00, rank_d 16.00, sum 25.00
T5: avg w 3.00, rank_u 3.00, rank_d 22.00, sum 25.00
Critical path (CPOP): T1 -> T3 -> T4 -> T5 | length 25.00

Run your program first, then open this and compare line by line: your output must contain these lines exactly.

How to give the file to my program

Terminal (macOS, Linux, or Windows Command Prompt), after compiling:

java Main < os6-1-data-1.txt

Windows PowerShell does not understand <:

Get-Content os6-1-data-1.txt | java Main

IntelliJ IDEA: Run → Edit Configurations → Redirect input from. Or simply paste the content of the file into the console when the program waits for input.

Write it here or in your IDE, then paste it. Compile and test it yourself before comparing. Your code stays in your browser — it is never sent to or stored on the server.