HW3

1.

Given the program:

1:  addi  x5,  x0, 1       # i = 1  
2:  slli  x21, x5, 3       # n = i · 2³ = 8  
3:  Loop: bge   x5, x21, Exit  # if i ≥ n, exit  
4:         slli  x6,  x5, 2   # x6 = i · 4  
5:         add   x7,  x22, x6 # x7 = &B[i]  
6:         lw    x9,  0(x7)   # x9 = B[i]  
7:         slli  x10, x9, 2   # x10 = 4·B[i]  
8:         sw    x10, 0(x7)   # B[i] = x10  
9:         addi  x5,  x5, 1   # i++  
10:        beq   x0,  x0, Loop  # unconditional back  
11: Exit:

1. Iterations
   • a) The loop body (lines 4–9) runs for $i=1$ through $7$, so 7 iterations.
2. Conditional‑branch executions
   • b) Line 3 executes once per iteration plus once more at exit, so 8 times.
3. Body instructions
   • c) Lines 4–9 are 6 instructions/iteration ⇒ $6\times 7=42$.
4. Unconditional branch
   • d) Line 10 runs once per iteration ⇒ 7 times.
5. Total dynamic instructions
   • e) $1+1+8+42+7=59$ instructions.

---

2.

• CPI = 1, cycle‑time = $5\text{ ns}$
• Total instructions = 59
• Time = $59\times 5\text{ ns}=295\text{ ns}$

---

3.

a) Data & Control Hazards

Between	Hazard Type	Register
1 & 2	RAW	x5
1 & 3	RAW	x5
2 & 3	RAW	x21
3 & 4	none	—
4 & 5	RAW	x6
5 & 6	RAW	x7
6 & 7	Load–Use RAW	x9
7 & 8	RAW	x10
9 & 3 (next)	RAW	x5
10 & 3 (next)	Control hazard	—

b) Pipeline Diagram

Instruction	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
I1 (L1)	F	D	E	M	W
I2 (L2)		F	D	E	M	W
I3 (L3: bge)			F	D	E	M	W
B1 (flush)				F	D	E	M	W
B2 (flush)					F	D	E	M	W
I4 (L4)						F	D	E	M	W
I5 (L5)							F	D	E	M	W
I6 (L6)								F	D	E	M	W
B3 (stall)									F	D	E	M	W
I7 (L7)										F	D	E	M	W
I8 (L8)											F	D	E	M	W
I9 (L9)												F	D	E	M	W
I10 (L10)													F	D	E	M	W
B4 (flush)														F	D	E	M	W
B5 (flush)															F	D	E	M	W
I11 (exit)																F	D	E	M	W

• F = IF
• D = ID
• E = EX
• M = MEM
• W = WB
• N = pipeline bubble

c) Calculations

1. CPI

   • Instructions = 8 (lines 3–10)
   • Bubbles = 2 (cond‑branch) + 1 (load‑use) + 2 (uncond‑branch) = 5
   • ${\text{CPI}}_{\text{iter}}=8+5=13$

2. Total cycles

   • Pipeline fill = 5 stages − 1 = 4 cycles
   • Iterations = 7
   • $\text{Total}=4+7\times 13=95\text{ cycles}$

3. Execution time

   • $95\text{ cycles}\times 1\text{ ns}=95\text{ ns}.$

4. Speedup

   • $\frac{295\text{ ns}}{95\text{ ns}}\approx 3.11\times .$

---

d)

i. Reordered loop:

Loop:
    bge   x5, x21, Exit     # line 3
    slli  x6, x5, 2         # line 4
    add   x7, x22, x6       # line 5
    lw    x9, 0(x7)         # line 6
    addi  x5, x5, 1         # line 9 (moved up)
    beq   x0, x0, Loop      # line 10 (moved up)
    slli  x10, x9, 2        # line 7
    sw    x10, 0(x7)        # line 8
Exit:

• By moving the addi and beq into the load‑use slot, we eliminate that 1‑cycle stall.
  ii. performance
• Instrs∕iter = 8
• Bubbles∕iter = 2 (cond) + 2 (uncond) = 4
• CPI∕iter = 8 + 4 = 12
• Total = 4 + 7×12 = 88 cycles ⇒ 88 ns
• Speedup = $295\text{ ns}/88\text{ ns}\approx 3.35\times$