Consider a VEX executing VLIW machine with the following characteristics:

The machine supports 4 slots (4 wide machine) with the following resources:

2 memory units each with a load latency of 3 cycles

2 integer-add/sub functional units with latency of 2 cycle

1 integer-multiply functional unit with latency of 4 cycles

Each functional unit in the machine is pipelined and can be issued a new operation at each cycle. However, results of an operation are only available after the latency of the

operation has passed.

Given the following Sequential VEX Code (a total of 16 instructions)

1. ldw $r1 = 4[$r10]

2. add $r2 = $r1, $r10

3. ldw $r3 = 8[$r10]

4. ldw $r5 = 12[$r20]

5. sub $r4 = $r3, $r2

6. ldw $r6 = 0[$r21]

7. add $r8 = $r20, 4

8. sub $r7 = $r23, $r22

9. mpy $r9 = $r8, $r5

10. ldw $r13 = 12[$r27]

11. ldw $r14 = 4[$r27]

12. mpy $r14 = $r13, $r14

13. add $r11 = $r7, $r6

14. ldw $r12 = $r11[$r9]

15. sub $r15 = $r14, 4

16. add $r16 = $r12, 10

Note: An instruction cannot be scheduled in a given slot unless all of its operands are available from other instructions on which it is dependent.

I. Draw the data dependence graph for the above code:

A. Each node in the graph is an instruction and an arrow from node A to node B signifies that the instruction in B is dependent on the instruction in A.

II. Using the dependence graph and latencies given, find the smallest (in terms of execution time) possible valid instruction schedule. Make your schedule follow

A. Attempt to place the instructions in the earliest slots possible where the dependencies are satisfied.

1. Hint: When having to decide between multiple possible instruction thathave their dependencies satisfied, try picking the instructions that are on the critical path of the code.

B. Make sure to ensure that the number of instructions assigned to the appropriate function does not exceed the memory memory or functional units does not exceed the availability.

C. Dont forget the latencies of the respective operations.

D. It is ok if operations that schedule to the same VLIW instruction read from the same register, as long as no other operation in the VLIW instruction is writing to that register. For example, it is valid to schedule instruction 1 and 3 to the same slot, even though both read from register $r10. However, this would not apply to instructions 12 and 15, since even though they both read register $r14,instruction 12 also writes to $r15.

III. Calculate the number of cycles it takes to execute the VLIW code.

IV. How many slots remain empty where no instruction could be scheduled? Provide a ratio of empty slots to the total number of slots present in the instruction schedule.