Question

Consider a VEX-executing VLIW machine with the following characteristics:

• The machine supports 4 slots (4-wide machine) with the following resources:
  1. 2 memory units each with a load latency of 3 cycles
  2. 2 integer-add/sub functional units with a latency of 2 cycle
  3. 1 integer-multiply functional unit with a latency of 4 cycles
• Each functional unit in the machine is pipelined and can be issued a new operation at each cycle. However, the 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 = 4[$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.

1. Draw the data dependence graph for the above code.
   • Each node in the graph is an instruction. You can simply write the instruction number (1-16) on the node; you do not need to write the instruction itself.
   • An arrow from node A to node B signifies that the instruction in B is dependent on the instruction in A. Note: You are not required to include the latencies in your submission, but it may prove useful for you to draw the graph with latencies included in order to find the critical path.
2. Using the dependence graph and given latencies, find the smallest (in terms of execution time) possible valid instruction schedule. Make your schedule as follows:
   • Place the instructions in the earliest slots possible where the dependencies are satisfied.
     • Hint: When having to decide between multiple possible instructions that have their dependencies satisfied, pick the instructions that are on the critical path of the code.
   • Ensure that the number of instructions assigned to the appropriate function does not exceed the number of available memory or functional units.
   • Don’t forget the latencies of the respective operations.
   • 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 $r14.
3. Calculate the number of cycles it takes to execute the VLIW code.
4. How many slots remain empty where no operation could be scheduled? Provide a ratio of empty slots to the total number of slots present in the instruction schedule. (Do not simplify, we want to see you selected the right number of total slots and empty slots).

Answer 1