Fixing Data Hazards at the Compiler/Programmer Level
Notes
- Consider the following code:
const int MAX = 10; int A[MAX], B[MAX], C[MAX]; ... for(int i =0; i < MAX; ++i) { A[i] = B[i] + C[i]; } - This is fairly tight code.
- In assembly it might be
; x1 is the LCV (i) ; x2 is the index (i*4) ; x3 is a ; x4 is b ; x5 is c ; x6 is the max
- mov x1, 0
- mov x6, MAX
- mov x2, 0 top:
- cmp x1, x6
- bge done
- ldur x4, [x2, B]
- ldur x5, [x2, C]
- add x3, x4, x5 ; mem to alu1, mem to alu2
- stur x3, [x2, A] ; alu to mem
- addi x2, x2, 8
- addi x1, x1, 1
- b top done:
- What are the dependencies?
-
ldur x4, [x2, B] ldur x5, [x2, C] add x3, x4, x5 ; mem to alu1, mem to alu2
-
add x3, x4, x5 ; mem to alu1, mem to alu2 stur x3, [x2, A] ; alu to mem
addi x1, x1, 1 b top cmp x1, x6
-
- An easy fix to some of this is the answer to the question, where do lines 10 and 11 really need to be in the code?
- By moving line 11 up, anywhere, we could eliminate the last problem.
- We could also free up line 10, by adding
mov x7, x2
- A second approach is to unroll the loop
const int MAX = 10; int A[MAX], B[MAX], C[MAX]; ... for(int i =0; i < MAX; ++i) { A[i] = B[i] + C[i]; ++i; A[i] = B[i] + C[i]; } - We would :
- have to maintain two sets of i and i*8
- have twice as many loads and stores
- A compiler could easily perform code reordering to accomplish this
- This is a moderately successful technique.