Reducing CPU cycles | CSCE-533 | Computer Architecture

Let me try a different approach with a simpler example.

Imagine counting down from 5 to 0:

for (i=5; i>=0; i=i-1) {
    // do something
}

The loop needs to:

1. Start at 5
2. Keep going until we hit 0
3. Subtract 1 each time

In assembly, we need a way to:

1. Keep track of our current number (x1)
2. Know when to stop (x2)
3. Check if we should continue or stop

So when we see:

assembly
bne x1,x2,Loop    // Branch if x1 ≠ x2

It's basically asking:

Is my current position (x1) different from where I want to stop (x2)?

• If different: Keep going (jump back to Loop)
• If same: We're done (continue to next instruction)

It's like a game:

• You start at 5
• You want to stop at 0
• Each time you ask "Am I at 0 yet?"
• If no: Keep counting down
• If yes: Stop

Let me break this down - it's showing how a processor pipeline executes our loop instructions and how we can make it more efficient:

Pipeline Stages:

1. IF: Instruction Fetch
2. ID: Instruction Decode
3. EX: Execute
4. ME: Memory
5. WB: Write Back

Original Code (Top) - Takes 9 cycles:

assembly


Loop: fld    f0,0(x1)    # Load number
      fadd.d f4,f0,f2    # Add
      fsd    f4,0(x1)    # Store
      addi   x1,x1,-8    # Update pointer
      bne    x1,x2,Loop  # Branch check

The diagram shows lots of stalls" (waiting periods) because instructions are dependent on each other.

1. Improved Code (Bottom) - Takes 7 cycles:

• Reordered instructions to reduce stalls
• Moved addi earlier to prevent stalling after fld
• Still has two necessary stalls after fadd.d

Think of it like an assembly line where we're trying to minimize workers standing around waiting. We reorder the tasks so there's less waiting time.

What causes these stalls or how the reordering helps reduce them?

First, let's understand what a pipeline is. Imagine making a sandwich in an assembly line:

1. Get bread (IF - Fetch)
2. Add meat (ID - Decode)
3. Add veggies (EX - Execute)
4. Add sauce (ME - Memory)
5. Close sandwich (WB - Write Back)

1. Get bun from shelf (fld)
  [WAIT for bun to arrive]

2. Add patty (fadd.d)
  [WAIT for patty to cook]
  [WAIT more for patty]

3. Put burger in bag (fsd)
4. Move to next order (addi)
5. Check if more orders (bne)

Optimized (7 cycles):

Loop: fld    f0,0(x1)      # Load
      addi   x1,x1,-8      # Integer Add moved up
      fadd.d f4,f0,f2      # FP Add
      stall
      stall
      fsd    f4,8(x1)      # Store (offset adjusted)
      bne    x1,x2,Loop    # Branch

But sometimes we have to wait:

• Can't add veggies until meat is done
• Can't close sandwich until sauce is added

The key optimizations were:

1. Moving the addi instruction earlier, right after the load. This eliminates the stall after fld because addi can execute while waiting for the load to complete.
2. Adjusting the store offset to compensate for the earlier addi execution (using 8(x1) instead of 0(x1))
3. Removing redundant stalls by better pipelining of instructions

These changes maintain the same functionality while reducing pipeline stalls, allowing the sequence to complete in 7 cycles instead of 9 cycles. The reordering takes advantage of instruction-level parallelism by executing the integer addition during what would otherwise be stall cycles.

In our computer code:

assembly
fld    f0,0(x1)     # Load number from memory
fadd.d f4,f0,f2     # Add 5 to it

We can't add (fadd.d) until we've loaded the number (fld) - this causes a STALL (waiting).

The diagram shows these waits with stall. Each column (i+1, i+2, etc.) is one clock cycle time passing.

Does this help explain what's happening? Would you like me to explain more about why we have to wait in certain cases?

Let me explain why we have to wait in this example!

Looking at the original code at the top of the image:

assembly


Copy
fld    f0,0(x1)     # Load number
fadd.d f4,f0,f2     # Add to it
fsd    f4,0(x1)     # Store result

The STALLS happen because:

1. After fld (Load):
2. We need to WAIT for the number to be loaded from memory
3. Can't start adding (fadd.d) until we have the number
4. Just like you can't put toppings on a sandwich before you have the bread!
5. After fadd.d (Add):
6. Long operation - takes multiple cycles to add floating point numbers
7. Need to wait for addition to finish
8. Like waiting for cheese to melt before you can close the sandwich
9. After fsd (Store):
10. Need to wait for the addition to complete
11. Can't store a result we don't have yet
12. Like can't box the sandwich before it's made

That's why we see all those "stall" markers in the pipeline diagram - they're forced waiting periods because one instruction depends on the result of another.

we were able to reduce cycle from 9 to 7, but did anything code change on the for loop?

or this kinda optimization can only be done in assembly?

The original loop in high-level code remains the same:

for (i=5; i>=0; i=i-1) {
    x[i] = x[i] + 1;  // The operation stays exactly the same
}

The optimization happened at two levels:

1. Assembly Level (What we saw in the diagram):

assembly

Cop# Original (9 cycles)
Loop: fld    f0,0(x1)      # Load
      fadd.d f4,f0,f2      # Add
      fsd    f4,0(x1)      # Store
      addi   x1,x1,-8      # Decrement
      bne    x1,x2,Loop    # Branch

# Optimized (7 cycles)
Loop: fld    f0,0(x1)      # Load
      addi   x1,x1,-8      # Moved up here!
      fadd.d f4,f0,f2      # Add
      fsd    f4,8(x1)      # Store
      bne    x1,x2,Loop    # Branch

1. Who Does the Optimization:

• Modern compilers are smart enough to do this kind of optimization automatically
• When you compile your C/C++/Java code, the compiler tries to arrange the assembly instructions in the most efficient way
• You don't need to write assembly code yourself

This is why when programmers say "premature optimization is the root of all evil" - let the compiler do these low-level optimizations! Focus on writing clear, maintainable high-level code.

The only time you might need to write optimized assembly is when:

1. Working on embedded systems
2. Writing performance-critical system code
3. Developing compilers
4. Working on very specialized hardware

For 99% of programming, you write the normal loop and let the compiler handle these optimizations!