# CS 211 - Lecture 13

## Pipelined Architectures

Bernhard Firner

2026-03-09

---

## Review

* We've gone through sections 4.1 to 4.3
  * Sequential instructions
* Now we'll delve into the rest of chapter 4
  * Pipelining

---

## Review Concepts

* CPU only does computation on values from registers and immediate instructions
* That's why we need to load things into registers before using them
* Even instructions must be loaded from memory locations
  * Instructions are just numbers
  * The bits in these numbers select behavior of parts of the CPU
    * Going through ALU, multiplexors, memory retrieval, etc

---

## Idyllic Architecture

---

## CISC Vs Risc

* x86-64 is a complex instruction set computer (`CISC`)
  * Supports array access and writing in single instructions
  * Manual for instructions starting with letters A-L is 600 pages
    * M-U another 700, W-Z just 70
* The alternative is `RISC` (reduced instruction set computer)

---

## Assembly to Machine Code

* Assembly instructions are human-readable
* Machine instructions are just numbers
  * CISC instructions are also variable length
* The numbers are translated directly into action in the CPU hardware

---

## CPU in Action

* Each instruction only uses a subset of the CPU
  * `movq $5, %rdx` moves 5 into rdx and doesn't touch the memory or ALU
  * `movq %rax, %rdi` copies the value in rax to rdi and doesn't touch the memory or ALU

</div>
<div class="col">

</div>
</div>

---

## Memory Read and Write

* Memory instructions obviously access memory
  * `movq (%rax), %rax` loads the data at rax into the rax register
  * `addl $1, -20(%rbp)` adds the value 1 to the `memory[rbp-20]`
    * That last one is going to increase complexity, as we'll see

</div>
<div class="col">

</div>
</div>

---

## Example

* `pushq %rbp` puts rbp's value into stack memory
  * It also updates `%rsp`, decrementing the register, which isn't shown

<pre>
sequence:
	pushq	%rbp
	movq	%rsp, %rbp
	subq	$16, %rsp
	movq	%rdi, -8(%rbp)
	cmpq	$1, -8(%rbp)
	ja	.L2
	movl	$1, %eax
	jmp	.L3
.L2:
	movq	-8(%rbp), %rax
	subq	$1, %rax
	movq	%rax, %rdi
	call	sequence
	movq	-8(%rbp), %rdx
	addq	%rdx, %rax
.L3:
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
</pre>

</div>
<div class="col">
<img style="width: 80%" class="r-stretch" src="./figures/idylic_execution_6-1.png" />

</div>
</div>

---

## Example

* `movq %rsp, %rbp` loads one register and writes back into another

</div>
<div class="col">
<img style="width: 80%" class="r-stretch" src="./figures/idylic_execution_6-2.png" />

</div>
</div>

---

## Example

* `subq $16, %rsp` subtracts an immediate from a register and writes back to a register

</div>
<div class="col">
<img style="width: 80%" class="r-stretch" src="./figures/idylic_execution_6-3.png" />

</div>
</div>

---

## Example

* `movq %rdi, -8(%rbp)` inserts rdi's value into `memory[rbp-8]`

</div>
<div class="col">
<img style="width: 80%" class="r-stretch" src="./figures/idylic_execution_6-4.png" />

</div>
</div>

---

## Example

* `cmpq $1, -8(%rbp)` first calculates a memory address. Then what?
  * First we calculate the memory address and access memory

</div>
<div class="col">
<img style="width: 80%" class="r-stretch" src="./figures/idylic_execution_6-5.png" />

</div>
</div>

---

## Example

* `cmpq $1, -8(%rbp)` (in modern CPUs) is usually split into a mov and sub

</div>
<div class="col">
<img style="width: 80%" class="r-stretch" src="./figures/idylic_execution_6-3.png" />

</div>
</div>

---

## Status Register

* The EFLAGS register holds results of comparisons
* `cmpq a b` is just `subq a b`
  * subtracts a from b
  * Sets the OF, CF, and ZF (overflow, carry, and zero) flags in the same manner

---

## More Complications

* `cmpq $1, -8(%rbp)` needs to get the value from memory into the ALU
  * But I haven't drawn a line from memory into the ALU!
  * Some old CPU's may have done that, but modern CPUs simply rewrite the instruction into two simpler ones
* Let's start introducing some modern complexity

</div>
<div class="col">

</div>
</div>

---

## Pipelines

* Let's break every operation into several components
* Each gray bar is a buffer, called a `pipeline register`
* This is a pipeline
  * Increases throughput roughly 5x

</div>
<div class="col">

</div>
</div>

---

## Pipeline Stages$^*$

1. Instruction fetch (IF)
2. Instruction decode/register fetch (ID)
3. Execute (math or address calculation) (EX)
4. Memory access (MA)
5. Write back (WB)

<p style='font-size:25pt'>$^*$ For our super-simplified example pipeline</p>

---

## Note on the pipeline

* This is going to be an idealized version
  * Useful to understand a CPU
  * Gross simplification of a modern system
* Sufficient to understand challenges in modern CPUs

---

## Y86

* The book goes into more details, but simplifies to the idyllic Y86 instruction set
  * Still, some of the diagrams get quite complicated
* Look at both
  * More examples will help get the major points across

---

## Execution in a pipeline

* Now it takes 5 clock cycles to complete one instruction
  * The instruction begins at time 0 and completes at the end of cycle 4
* But these clock cycles are faster than the unpipelined version
  * Only needs to be as slow as the slowest block

</div>
<div class="col">

</div>
</div>

---

## Sequential Execution

---

## Parallel Execution

---

## Parallel Execution Notes

* More throughput
  * Six 5-stage instructions finished by clock tick 10!
  * Roughly 5x the throughput!
* Each stage must be fully isolated from the other
  * This is why we have a register in between pipeline stages

</div>
<div class="col">

</div>
</div>

---

## Buffering

* Each register stores the output from a stage of the pipeline
* When the clock ticks, it emits those values as if they were being output directly from the previous stage
* This mostly cleans up problems
  * Only mostly

---

## Buffering Delay

* Those buffers are called pipeline registers, and like other memory they take time
* Let's say we cut up a pipeline that took 500ps (2GHz)
* Each unit may only take 100ps (10GHz)
  * But each pipeline register costs 20ps, reducing throughput to 8.3GHz

---

## Unrealistic

* First, different steps may take different times
  * If ID is 80ps and EX is 120ps, then the clock will run at 120ps
    * We always have to wait for the EX stage anyway
* Second, the pipeline register delays increase as we add pipeline stages
* Third, we've assumed that the pipeline is always full, which may not be the case

---

## Memory Writeback

* If instruction 1 loads memory into a register and instruction 2 uses it, we have a problem
* And this will be common!
  * Why load memory if we aren't going to use it?

</div>
<div class="col">

</div>
</div>

---

## Memory Writeback Delay

* The data is loaded from memory in stage 4, memory access
  * And then written back to the registers in stage 5
* Too late!
  * Should be loaded in stage 2 of the next instruction (instruction decode and register fetch)
  * Used in stage 3 (execution)
* This is called a "read-after-write" dependency

</div>
<div class="col">

</div>
</div>

---

## Data Dependency

* A `data dependency` is a type of `pipeline hazard`
* In ID, we assume that register values are ready
* When the second instruction goes to read the register, the wrong value is present

</div>
<div class="col">

</div>
</div>

---

## More RAW Examples

* Read after write doesn't only happen with memory

* We need the immediate value, 50, to finish being loaded into %rax before the add

---

## Instruction Dependency - Stalling

* If we reach ID and we need a future value, we could wait
  * Insert "no ops" into the pipeline
* This is called a **bubble** or **stalling**

</div>
<div class="col">

</div>
</div>

---

## Value Forwarding

* Stalling is bad, it wastes clock cycles
* Another solution is to forward the memory value as soon as it's ready
  * At the end of the memory access stage
* We only lose one clock cycle this way

</div>
<div class="col">

</div>
</div>

---

## Forwarding

* We could have a dependency from the EX stage as well
  * `addq %rax %rbx`
  * `addq %rbx %rcx`
* If we forward from the EX stage back to the beginning of the EX stage, consecutive ALU operations are okay

</div>
<div class="col">

</div>
</div>

---

## Other Hazards

* Dependencies in adjacent steps are resolved
  * But some hazards are not fixed with forwarding
* What happens if we load something from memory and use it immediately?

</div>
<div class="col">

</div>
</div>

---

## Load/Use Hazard

* Example: mov instruction loads from memory into a register
* The next instruction wants to use that value in EX, but cannot
* We will have to stall here to fix the problem

</div>
<div class="col">

</div>
</div>

---

## Out of Order Execution

* Stalling is bad though
* Solution: find another instruction that doesn't have a dependency
  * Maybe we have a second memory access into a different register
  * Just run that one first instead of stalling
* Sounds simple, will be horribly complicated

---

## Aside: Instruction Memory

* Why don't we worry about modifying instruction memory?
  * This is called "self-modifying code"
  * It is generally not allowed
  * If not explicitly detected and blocked, can lead to strange outcomes
* So we won't worry about a modification to memory affecting the currently loaded instruction
* We do worry about the instruction pointer, though

---

## Control Hazards

* The `data dependencies` from before lead to data hazards
* `Control hazards` are also possible
  * When a previous instruction may update the instruction pointer
  * A jump statement, for example
* We may know *where* we could jump, but not know whether or not to do it

---

## Control Hazard Delays

* For direct `jmp` we read the value from the register in ID
* For conditional jumps, Need the ALU result from a comparison
  * `ja`, jump if above, looks for the result in the EFLAGS register
* That's fine for `ja`, the result can be forwarded back from EX
  * But then what?

</div>
<div class="col">

</div>
</div>

---

## Control Hazard Delays

* `ja` needs to update the instruction pointer at the beginning of the IF stage for the next instruction

</div>
<div class="col">

</div>
</div>

---

## Control Hazard Delays

* But `ja` works by specifying an offset to the current instruction pointer
  * So we also need to do some ALU operation in the EX stage
* Now we have a two clock cycle hazard
  * The third instruction needs to be pushed from cycle 2 to 4

</div>
<div class="col">

</div>
</div>

---

## Instruction Pointer Updates

* If we encounter a conditional jump, should we keep executing instructions?
  * Of course!
  * This is called `speculative execution`
* It's possible that we do take the jump
  * In that case, we throw out the results and flush the pipeline buffers

---

## Branch Prediction

* To decrease the frequency of pipeline flushes, we can try to predict which branch will be taken
* The simplest version of this is to guess that we branch the same as last time
  * Makes sense; most jumps are in loops

---

## Simple Branch Prediction Logic

```C
bool last_taken;

bool predictBranch() {
    return last_taken;
}

void updateBranch(bool taken) {
    last_taken = taken;
}

```

---

## Instruction Fetch

* These problem are all detected in the IF stage
  * Let's spend a moment talking about what happens here
* The instruction pointer goes into the instruction memory, fetching the instruction
* In x86-64 the value is stored in the EIP/RIP for the 32 or 64-bit register
* Showed the instruction being incremented by 1, but it is incremented by the size of instructions

---

## Instruction Fetch Reality

* Modern CPUs fetch multiple instructions at a time
* Some instructions are combined, rewritten, or expanded
* For example, `cmpq $1, -8(%rbp)` is broken into smaller operations
  * Called micro-operations
* load and then compare, in this case

---

## Ramifications

* A modern x86 CPU hides a simpler, optimized instruction set behind the more complicated one
  * The compiler optimizes your code, sometimes making it hard to know what runs
  * So does the CPU
* CPUs also attempt to use instructions faster with forwarding
  * So what looks like a dependency could disappear

---

## Out of Order Execution

* Instruction don't *need* to be issued in order
* The CPU feels free to change things around to avoid hazards
  * For example, by inserting a useful operation from the future instead of a no op
  * Or, begin calculating the jump earlier in the instructions than specified
* In order to support that, future instructions are prefetched

---

## Who Optimizes?

* The order of execution could also be rewritten by the compiler
* In fact, both the compiler and the CPU will attempt to optimize code
  * The compiler has more global information about the program
  * The CPU has more information about the CPU state

---

## Loop Unrolling

* One optimization that the compiler is able to do is `loop unrolling`
  * If it can tell that a loop body will happen multiple times
  * Just copy and paste the code and get rid of (or shorten) the loop

---

## Loop Unrolling Example

```C
int sum = 0;
for (int i = 0; i < 10; ++i) {
    sum += i;
}
```

---

## Partial Loop Unrolling

```C
int sum = 0;
for (int i = 0; i < 10; i+=5) {
    sum += i;
    sum += i+1;
    sum += i+2;
    sum += i+3;
    sum += i+4;
}
```

---

## Full Loop Unrolling

```C
int sum = 0;
sum += 1;
sum += 2;
sum += 3;
sum += 4;
sum += 5;
sum += 6;
sum += 7;
sum += 8;
sum += 9;
sum += 10;
```

---

## Intel's Description

* Section 2.2.2.1 for Software Developer's Manual
  * prefetch instruction that are likely to be executed
  * fetch instructions that have not been fetched
  * decode instructions into micro-operations
  * generate microcode for complex instructions
  * delivers decoded instructions from the execution trace cache
  * predicts branches

---

## Continued

* Fixes these two problems
  * time to decode instructions after fetching them
  * wasted decode bandwidth due to branches or branch targets in the middle of cache lines
* Basically, a large cache of decoded instructions are always waiting for execution
  * This includes instructions from multiple different branches

---

## Reordering

* After out of order execution, results are put back into order
  * By a piece of hardware called the Reorder Buffer (ROB)
* If you draw a circle around the CPU, it looks like instructions go in and out in order

---

## Super scalar

* Modern CPUs are also wide, meaning that they can run multiple instructions at once
  * As long as they don't require the same hardware
* The Intel Core architecture
  * Has a 14 stage pipeline
  * three ALUs, two new ALU ops per cycle
  * many floating-point instructions can be issues once every two cycles
    * Implies that the FPUs take 2 cycles for computation

---

## Int and Float Timing

* Remember how we compared int and float timing?
  * They didn't seem so different. Why?
* More time was spent loading the values into registers from the memory
  * Recall that we used more values than registers
* We'll discuss it more, but loading data is generally our slowest operation

---

## What's Important?

* Hazards affect program performance
  * But a modern CPU will generally hide problems
* Unavoidable hazards stall, resulting in a bubble of no-ops in the pipeline
* Mispredicted branches are generally the most costly hazard

---

## Pipelines and hazards

* Hazards are basically race conditions brought about by pipelines
* An n-stage pipeline allows for n-simultaneous instructions
  * And n times the throughput
* Longer pipes have drawbacks and practical limits
  * More hazards, with stalls have larger effects
  * Greater overhead from the pipeline buffer delays

---

## Next Time

* More review of hazards
* Parallelism
  * Threaded: 12.3, 12.6 in the book
  * Instruction level: SIMD section in 5.9
* After the break
  * Architecture aware code

<!--
Show some examples of assembly instructions that cause hazards
  * These are great to ask about during a test!

Talk about loop unrolling as an optimization

Spend more time talking about branch prediction

Exhuastively list possible hazards, including in control and status registers. Most issues are solved with forwarding
-->