The logic of a program naturally introduces dependences among instructions, including data dependence (true dependence), name dependence (anti-dependence, output dependence), and control dependence (when the decision of whether to execute an instruction is determined by the outcome of a branch). In some pipelines a specific dependence may result in a hazard that prevents the dependent instruction from moving forward in the pipeline without stalls. In some other pipelines, the same dependence may not result in a hazard. That is related to hardware optimization. One can also try compiler optimization to reduce the penalty of stalls for the same microarchitecture. Consider the following C code: = a [2] a [5] a [0] + a[1]; a [3] + a[4]; It is compiled to the following MIPS assembly code (assume Rl=&a, i.e. the address of a[0]): = 1 2 3 4 5 6 7 8 LW LW ADD SW LW LW ADD SW R2, O (R1) R3, 1 (R1) R4, R2, R3 R4, 2 (R1) R5, 3(R1) R6, 4 (R1) R7, R5, R6 R7, 5(R1) # R2 = a [0] # R3 a [1] # R4 = a[0] + a [1] # a [2] = R4 # R5 = a (3) # R6 = a[4] # R7 = a [3] + a[4] # a [5] = R7 a) [5 marks] Identify all dependences in the above assembly code segment; list the two instructions involved; identify which instruction is dependent; and, if there is one, name the storage location involved. The first row is shown in the table as an example. Independent instruction 1 (LW) Dependent instruction 3 (ADD) Storage location R2 1 2 3 4 5 6 7 8 9 10 b) [4 marks] We run the above assembly code in a pipeline with five stages: Fetch (one clock cycle) Decode (one clock cycle) Execute (one block cycle). Memory operand fetch (one block cycle). Write-back (one clock cycle) The logic of a program naturally introduces dependences among instructions, including data dependence (true dependence), name dependence (anti-dependence, output dependence), and control dependence (when the decision of whether to execute an instruction is determined by the outcome of a branch). In some pipelines a specific dependence may result in a hazard that prevents the dependent instruction from moving forward in the pipeline without stalls. In some other pipelines, the same dependence may not result in a hazard. That is related to hardware optimization. One can also try compiler optimization to reduce the penalty of stalls for the same microarchitecture. Consider the following C code: = a [2] a [5] a [0] + a[1]; a [3] + a[4]; It is compiled to the following MIPS assembly code (assume Rl=&a, i.e. the address of a[0]): = 1 2 3 4 5 6 7 8 LW LW ADD SW LW LW ADD SW R2, O (R1) R3, 1 (R1) R4, R2, R3 R4, 2 (R1) R5, 3(R1) R6, 4 (R1) R7, R5, R6 R7, 5(R1) # R2 = a [0] # R3 a [1] # R4 = a[0] + a [1] # a [2] = R4 # R5 = a (3) # R6 = a[4] # R7 = a [3] + a[4] # a [5] = R7 a) [5 marks] Identify all dependences in the above assembly code segment; list the two instructions involved; identify which instruction is dependent; and, if there is one, name the storage location involved. The first row is shown in the table as an example. Independent instruction 1 (LW) Dependent instruction 3 (ADD) Storage location R2 1 2 3 4 5 6 7 8 9 10 b) [4 marks] We run the above assembly code in a pipeline with five stages: Fetch (one clock cycle) Decode (one clock cycle) Execute (one block cycle). Memory operand fetch (one block cycle). Write-back (one clock cycle)
