| |
|
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
HW |
| 0 |
1 1 8 14 21 28 34 41 48 54 61
1 2 8 53 98 143 188 233 278 323 368
1 3 4 7 10 12 13
2 1 8 29 54 76 95 113 128 140 150
2 2 1 8
2 3 4 7 11 14 16
3 1 16 32 59 85 110 134 159 182 205 228 250 271 293 314 334 355 375
3 2 8 33 60 87 114 141 167 193 219
4 1 6 39 76 111 150 186 220
5 1 11 52 99 147 191 239 286 332 383 427 474 521
6 1 8 100 192 274 357 456 513 586 657
7 1 9 78 152 220 294 362 421 497 563 627
8 1 13 30 52 77 96 121 142 162 182 205 221 235 257 275
8 2 8 24 43 63 81 99 117 134 151
9 1 10 13 22 31 40 49 57 65 74 82 89
9 2 7 9 16 22 28 33 40 45
9 3 3 6 10 13
10 1 7 18 28 38 48 58 69 78
10 2 8 13 21 29 36 44 52 59 67
10 3 8 6 8 10 12 14 17 17 19
|
|
Costs of the computation nodes. |
|
|
|
|
|
|
|
|
|
|
|
| 0 |
31 107 20
|
|
Time for processing a packet by the
hardware accelerator, and the time for trying to receive incoming
packets. |
|
|
|
|
|
|
|
|
|
|
|
| 0 |
11
|
|
Number of packets in this testcase. |
|
|
|
|
|
|
|
|
|
|
|
| 0 |
|
R 4
|
Receive packets until time t=4. |
|
|
|
|
|
|
|
|
|
|
|
| 23 |
0
|
|
No new packets till t=4 received. Current
time \(= (4+ c_r - 1) = 23\). Next
action possible at t=24. |
|
|
|
|
|
|
|
|
|
|
|
| 24 |
|
R 24
|
Receive packets until time t=24. |
|
|
|
|
|
|
|
|
|
|
|
| 43 |
5
1 3 6
2 3 7
3 1 7
4 3 9
5 1 10
|
|
5 packets till t=24 received: 3 packets of
type=3 (id=1, 2, 4) at time 6, 7, 9. 2 packets of type=1 (id=3, 5) at
time 7, 10. |
type=1: 3 5 type=3: 1 2 4 |
|
|
|
|
|
|
|
|
|
|
| 44 |
|
E 44 1 3 1 2 4
|
Execute a task at t=44 on node 1. Execute
a batch of 3 packets with IDs 1, 2 and 4. All packets are of the same
type (3). According to the line 3 of the input (1 3 4 7 10 12 13) Node 1
will process a batch of 3 packets of type 3 for 12 seconds. |
type=1: 3 5 type=3: 1 2
4 |
|
|
|
|
|
|
|
|
|
|
| 55 |
0
|
|
Processing the packet took 12 seconds.
They are ready at t=t+cijs-1=44+12-1=55. Next action possible at
t=56. |
type=1: 3 5 |
type=3: 1 2 4 |
|
|
|
|
|
|
|
|
|
| 56 |
|
E 56 1 2 3 5
|
Execute a task at t=56 on node 1. Execute
a batch of 2 packets with IDs 3, 5. Time for execution = 21 |
type=1: 3 5 |
type=3: 1 2 4 |
|
|
|
|
|
|
|
|
|
| 76 |
0
|
|
|
|
type=1: 3 5 type=3: 1 2 4 |
|
|
|
|
|
|
|
|
|
| 77 |
|
E 77 2 3 1 2 4
|
Execute a task at t=77 on node 2. Execute
a batch of 3 packets with IDs 1, 2, 4. Time for execution = 14 |
|
type=1: 3 5 type=3: 1 2
4 |
|
|
|
|
|
|
|
|
|
| 90 |
0
|
|
Packets of type 3 go to node 9 after
execution on node 2. |
|
type=1: 3 5 |
|
|
|
|
|
|
type=3: 1 2 4 |
|
|
| 91 |
|
R 91
|
|
|
type=1: 3 5 |
|
|
|
|
|
|
type=3: 1 2 4 |
|
|
| 110 |
6
6 1 24
7 1 28
8 1 37
9 1 45
10 1 56
11 1 59
|
|
|
type=1: 6 7 8 9 10 11 |
type=1: 3 5 |
|
|
|
|
|
|
type=3: 1 2 4 |
|
|
| 111 |
|
E 111 9 3 1 2 4
|
Execute a task at t=111 on node 9. Execute
a batch of 3 packets with IDs 1, 2, 4. Time for execution = 13 |
type=1: 6 7 8 9 10 11 |
type=1: 3 5 |
|
|
|
|
|
|
type=3: 1 2 4 |
|
|
| 123 |
0
|
|
|
type=1: 6 7 8 9 10 11 |
type=1: 3 5 |
|
|
|
|
|
|
|
type=3: 1 2 4 |
|
| 124 |
|
E 124 10 3 1 2 4
|
Execute a task at t=124 on node 10.
Execute a batch of 3 packets with IDs 1, 2, 4. Time for execution =
10 |
type=1: 6 7 8 9 10 11 |
type=1: 3 5 |
|
|
|
|
|
|
|
type=3: 1 2 4 |
|
| 133 |
0
|
|
Packets 1, 2, and 4 were processed
durint this step. They are considered ready since the next step, so we
are considering 134 (not 133) at their processed time. Packet processing
delays for those packets are: ID = 1, delay = 134 - 6 = 128. ID = 2,
delay = 134 - 7 = 127. ID = 4, delay = 134 - 9 = 125. |
type=1: 6 7 8 9 10 11 |
type=1: 3 5 |
|
|
|
|
|
|
|
|
|
| 134 |
|
E 134 1 6 6 7 8 9 10 11
|
Execute a task at t=134 on node 1. Execute
a batch of 6 packets with IDs 6, 7, 8, 9, 10, 11. Time for execution =
48. |
type=1: 6 7 8 9 10 11 |
type=1: 3 5 |
|
|
|
|
|
|
|
|
|
| 181 |
0
|
|
|
|
type=1: 3 5 6 7 8 9 10 11 |
|
|
|
|
|
|
|
|
|
| 182 |
|
E 182 2 8 3 5 6 7 8 9 10 11
|
Execute a task at t=182 on node 2. Time
for execution = 150. |
|
type=1: 3 5 6 7 8 9 10
11 |
|
|
|
|
|
|
|
|
|
| 331 |
0
|
|
|
|
|
type=1: 3 5 6 7 8 9 10 11 |
|
|
|
|
|
|
|
|
| 332 |
|
E 332 3 8 3 5 6 7 8 9 10 11
|
Execute a task at t=332 on node 3. Time
for execution = 205. |
|
|
type=1: 3 5 6 7 8 9 10
11 |
|
|
|
|
|
|
|
|
| 536 |
0
|
|
|
|
|
|
3 5 6 7 8 9 10 11 |
|
|
|
|
|
|
|
| 537 |
|
E 537 4 2 10 11
|
Process packets 10 and 11 on node 4. Time
for execution =76. |
|
|
|
3 5 6 7 8 9 10 11 |
|
|
|
|
|
|
|
| 612 |
0
|
|
Packets 10 and 11 were processed by Node
4. HW will start processing at t=613. |
|
|
|
3 5 6 7 8 9 |
|
|
|
|
|
|
10(4) 11(4) |
| 613 |
|
|
Packets 10 and 11 added to the HW queue.
Packets are processed one by one. Execution after the Node 4 takes t=31.
Execution after the Node 6 takes t=107. |
|
|
|
3 5 6 7 8 9 |
|
|
|
|
|
|
10(4):643 11(4) |
| 613 |
|
E 613 4 3 5 6 3
|
Process packets 5, 6, and 3 on node 4.
Time for execution =111. |
|
|
|
3 5 6 7 8 9 |
|
|
|
|
|
|
10(4):643 11(4) |
| 643 |
|
|
Packet 10 processed on HW |
|
|
|
3 5 6 7 8 9 |
10 |
|
|
|
|
|
11(4) |
| 644 |
|
|
HW started processing packet 11. |
|
|
|
3 5 6 7 8 9 |
|
|
|
|
|
|
11(4):674 |
| 674 |
|
|
Packet 11 processed on HW |
|
|
|
3 5 6 7 8 9 |
10 11 |
|
|
|
|
|
|
| 723 |
0
|
|
Packets 5, 6, and 3 processed on Node 4.
They are added to the HW queue in the same order as in the execution
request. |
|
|
|
7 8 9 |
10 11 |
|
|
|
|
|
5(4) 6(4) 3(4) |
| 724 |
|
|
Packet 5 started execution on HW |
|
|
|
7 8 9 |
10 11 |
|
|
|
|
|
5(4):754 6(4) 3(4) |
| 724 |
|
E 724 5 2 10 11
|
Process packets 10 and 11 on node 5. Time
for execution =99. |
|
|
|
7 8 9 |
10 11 |
|
|
|
|
|
5(4):754 6(4) 3(4) |
| 754 |
|
|
Packet 5 processed on HW |
|
|
|
7 8 9 |
10 11 5 |
|
|
|
|
|
6(4) 3(4) |
| 755 |
|
|
HW started processing packet 6. |
|
|
|
7 8 9 |
10 11 5 |
|
|
|
|
|
6(4):785 3(4) |
| 785 |
|
|
Packet 6 processed on HW |
|
|
|
7 8 9 |
10 11 5 6 |
|
|
|
|
|
3(4) |
| 786 |
|
|
HW started processing packet 3. |
|
|
|
7 8 9 |
10 11 5 6 |
|
|
|
|
|
3(4):816 |
| 816 |
|
|
Packet 3 processed on HW |
|
|
|
7 8 9 |
10 11 5 6 3 |
|
|
|
|
|
|
| 822 |
0
|
|
Packets 10 and 11 processed on node
5. |
|
|
|
7 8 9 |
5 6 3 |
10 11 |
|
|
|
|
|
| 823 |
|
E 823 4 3 7 8 9
|
Process packets 7, 8, and 9 on node 4.
Time for execution =111. |
|
|
|
7 8 9 |
5 6 3 |
10 11 |
|
|
|
|
|
| 933 |
0
|
|
|
|
|
|
|
5 6 3 |
10 11 |
|
|
|
|
7(4) 8(4) 9(4) |
| 934 |
|
|
HW started processing packet 7. |
|
|
|
|
5 6 3 |
10 11 |
|
|
|
|
7(4):964 8(4) 9(4) |
| 934 |
|
E 934 6 2 10 11
|
Process packets 10 and 11 on node 6. Time
for execution =192. |
|
|
|
|
5 6 3 |
10 11 |
|
|
|
|
7(4):964 8(4) 9(4) |
| 964 |
|
|
Packet 7 processed on HW |
|
|
|
|
5 6 3 7 |
10 11 |
|
|
|
|
8(4) 9(4) |
| 965 |
|
|
HW started processing packet 8. |
|
|
|
|
5 6 3 7 |
10 11 |
|
|
|
|
8(4):995 9(4) |
| 995 |
|
|
Packet 8 processed on HW |
|
|
|
|
5 6 3 7 8 |
10 11 |
|
|
|
|
9(4) |
| 996 |
|
|
HW started processing packet 9. |
|
|
|
|
5 6 3 7 8 |
10 11 |
|
|
|
|
9(4):1026 |
| 1026 |
|
|
Packet 9 processed on HW |
|
|
|
|
5 6 3 7 8 9 |
10 11 |
|
|
|
|
|
| 1125 |
0
|
|
|
|
|
|
|
5 6 3 7 8 9 |
|
|
|
|
|
10(6) 11(6) |
| 1126 |
|
|
HW started processing packet 10. Time for
execution = 107 and not 31, as this packet came from node 6. |
|
|
|
|
5 6 3 7 8 9 |
|
|
|
|
|
10(6):1232 11(6) |
| 1126 |
|
E 1126 5 6 3 5 6 7 8 9
|
Process packets 3, 5, 6, 7, 8, 9 on node
5. Time for execution =286. |
|
|
|
|
5 6 3 7 8 9 |
|
|
|
|
|
10(6):1232 11(6) |
| 1232 |
|
|
Packet 10 processed on HW |
|
|
|
|
5 6 3 7 8 9 |
|
10 |
|
|
|
11(6) |
| 1233 |
|
|
HW started processing packet 11. |
|
|
|
|
5 6 3 7 8 9 |
|
10 |
|
|
|
11(6):1339 |
| 1339 |
|
|
Packet 11 processed on HW |
|
|
|
|
5 6 3 7 8 9 |
|
10 11 |
|
|
|
|
| 1411 |
0
|
|
|
|
|
|
|
|
3 5 6 7 8 9 |
10 11 |
|
|
|
|
| 1412 |
|
E 1412 6 6 3 5 6 7 8 9
|
Process packets 3, 5, 6, 7, 8, 9 on node
6. Time for execution =513. |
|
|
|
|
|
3 5 6 7 8 9 |
10 11 |
|
|
|
|
| 1924 |
0
|
|
|
|
|
|
|
|
|
10 11 |
|
|
|
3(6) 5(6) 6(6) 7(6) 8(6) 9(6) |
| 1925 |
|
|
Start executing process 3 on HW. |
|
|
|
|
|
|
10 11 |
|
|
|
3(6):2031 5(6) 6(6) 7(6)
8(6) 9(6) |
| 2031 |
|
|
Packet 3 processed on HW |
|
|
|
|
|
|
10 11 3 |
|
|
|
5(6) 6(6) 7(6) 8(6) 9(6) |
| 2032 |
|
|
Start executing process 5 on HW. |
|
|
|
|
|
|
10 11 3 |
|
|
|
5(6):2138 6(6) 7(6) 8(6)
9(6) |
| 2138 |
|
|
Packet 5 processed on HW |
|
|
|
|
|
|
10 11 3 5 |
|
|
|
6(6) 7(6) 8(6) 9(6) |
| 2139 |
|
|
Start executing process 6 on HW. |
|
|
|
|
|
|
10 11 3 5 |
|
|
|
6(6):2245 7(6) 8(6)
9(6) |
| 2245 |
|
|
Packet 6 processed on HW |
|
|
|
|
|
|
10 11 3 5 6 |
|
|
|
7(6) 8(6) 9(6) |
| 2246 |
|
|
Start executing process 7 on HW. |
|
|
|
|
|
|
10 11 3 5 6 |
|
|
|
7(6):2352 8(6) 9(6) |
| 2352 |
|
|
Packet 7 processed on HW |
|
|
|
|
|
|
10 11 3 5 6 7 |
|
|
|
8(6) 9(6) |
| 2353 |
|
|
Start executing process 8 on HW. |
|
|
|
|
|
|
10 11 3 5 6 7 |
|
|
|
8(6):2459 9(6) |
| 2459 |
|
|
Packet 8 processed on HW |
|
|
|
|
|
|
10 11 3 5 6 7 8 |
|
|
|
9(6) |
| 2460 |
|
|
Start executing process 9 on HW. |
|
|
|
|
|
|
10 11 3 5 6 7 8 |
|
|
|
9(6):2566 |
| 2566 |
|
|
Packet 9 processed on HW |
|
|
|
|
|
|
10 11 3 5 6 7 8 9 |
|
|
|
|
| 2567 |
|
E 2567 7 8 3 5 6 7 8 9 10 11
|
Process packets on node 7. Execution time
= 563. |
|
|
|
|
|
|
3 5 6 7 8 9 10 11 |
|
|
|
|
| 3129 |
0
|
|
|
|
|
|
|
|
|
|
3 5 6 7 8 9 10 11 |
|
|
|
| 3130 |
|
E 3130 8 8 3 5 6 7 8 9 10 11
|
Process packets on node 8. Execution time
=182. |
|
|
|
|
|
|
|
3 5 6 7 8 9 10 11 |
|
|
|
| 3311 |
0
|
|
|
|
|
|
|
|
|
|
|
3 5 6 7 8 9 10 11 |
|
|
| 3312 |
|
E 3312 9 8 3 5 6 7 8 9 10 11
|
Process packets on node 9. Execution time
=74. |
|
|
|
|
|
|
|
|
3 5 6 7 8 9 10 11 |
|
|
| 3385 |
0
|
|
|
|
|
|
|
|
|
|
|
|
3 5 6 7 8 9 10 11 |
|
| 3386 |
|
E 3386 10 7 3 5 6 7 8 9 10
|
Process packets on node 10. Processing 7
packets in a batch because it’s the maximum batch size allowed on this
node for type=1. Execution time = 78. |
|
|
|
|
|
|
|
|
|
3 5 6 7 8 9 10 11 |
|
| 3463 |
0
|
|
Packets 3, 5, 6, 7, 8, 9, 10 were
processed. Packet processing delays for those packets are: ID = 3, delay
= 3464 - 7 = 3457. ID = 5, delay = 3464 - 10 = 3454. ID = 6, delay =
3464 - 24 = 3440. ID = 7, delay = 3464 - 28 = 3436. ID = 8, delay = 3464
- 37 = 3427. ID = 9, delay = 3464 - 45 = 3419. ID = 10, delay = 3464 -
56 = 3408. |
|
|
|
|
|
|
|
|
|
11 |
|
| 3464 |
|
E 3464 10 1 11
|
Process packet on node 10. Execution time
= 18. |
|
|
|
|
|
|
|
|
|
11 |
|
| 3481 |
0
|
|
Packet 11 was processed.
Processing delay: ID = 11, delay = 3482 - 59 = 3423. |
|
|
|
|
|
|
|
|
|
|
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
|
|
\(d_{ave} =
(128+127+3457+125+3454+3440+3436+3427+3419+3408+3423) / 11 =
2531.27273.\) |
|
|
|
|
|
|
|
|
|
|
|
| |
|
|
\(score =
\lfloor(10^4-2531.27273)*10^3\rfloor = 7 468 727.\) |
|
|
|
|
|
|
|
|
|
|
|
