# CS 211 - Lecture 12 - Computer Architectures

Bernhard Firner

2026-03-02

---

## Review

* Assembly!

---

## What is Assembly?

* Human-readable (and writeable) programming
  * Thin translation into machine code, which runs directly on the machine
* And what is machine code?
  * It is numbers that go into "the machine"

---

## Concepts

* No variables, just registers and memory
* Function arguments are just values stored in a register
* Return values are just values stored in another register
* Loops are just jumps to a previous memory location
* Functions are just instructions sitting in memory

---

## Allocating stack memory

* Just subtract what you want from the `stack pointer` (rsp)

<pre>
// Calculate the nth sequence number and return it.
unsigned long long sequence(unsigned long long n) {
    if (n < 2) {
        return 1;
    }
    // This function cannot clear its stack memory until the next call returns.
    return n + sequence(n-1);
}
</pre>

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

<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>

---

## Accessing Data

* Data is usually accessed through `registers`
* Three addressing types:
  * Immediate (constant values)
  * Register (value in a register)
  * Memory (value at a memory location)
    * Direct (address is a constant)
    * Indirect (address calculated from a register)

---

## Immediate and Register Addressing

* Immediate: use a constant
  * e.g. `$5` refers to the constant value 5
  * `movq $5, %rdx` moves 5 into rdx
* The source (in that example) is immediate, the destination is a register

---

## Memory Addressing

* These are pointers in C
  * `movq	%rdi, -8(%rbp)`
  * Moves the register value at rdi into the memory at (rbp - 8)
  * The stack grows down, so in C:
    * `*(rbp - 8) = rdi`
* If the memory location is hard-coded, we call it `direct`
* When the location is in a register, it is `indirect`

---

## Displacement and Scaling

* Address is: `displacement(base, index, scale)`
  * But you don't need to use both displacement and index
* Stack memory often uses only displacement
  * `-8(%rbp)` is `memory[%rbp - 8]`
* Array access often has a scaling factor
  * E.g. ints have a scale of 4 bytes
  * `(%rax, %rcx, 4)` is `memory[%rax + 4*%rcx]`

---

## Confused?

* The book uses a stripped down version of assembly called "y86"
  * There are a few javascript simulators
  * Here's one: [Y86-64 simulator](https://boginw.github.io/js-y86-64/)
* Let's use it to look at the stack

---

## Stack Documentation

* From Intel 64 and IA-32 Architecture Software Development Manual

---

## Stack Memory

* Decrease the stack `stack pointer` (in esp/rsp) to "allocate" stack memory
* The `push` functions do two things:
  * Sets the value at the stack pointer
  * Decrements the stack pointer, %rsp
* `pop` does the reverse, fetching a value and incrementing %rsp

---

## Functions and the Stack

* The initial stack value is stored in the `base pointer` (ebp/rbp) for reference
* When a function is called, the current **instruction pointer** is saved
  * The instruction pointer is stored in `eip` or `rip` and is pushed onto the stack
* When a function completes, it needs to return to the calling location
  * This means popping that value off of the stack

---

## Cleaning Up

* A function may have allocated stack memory
  * Cleaning up is handled by the `leave` instruction
  * Sets %esp to %ebp and then resets %ebp to its old value
* The `ret` function pops the old instruction value and jumps back

---

## Memory Example

* We'll convert this to Y86-64

```C
void use_stack() {
    long long bob[10];
    bob[3] = 5;
    bob[9] = 4;
    return;
}

int main(void) {
    return 0;
}
```

* To get an assembly file name test.s:
  * gcc -S test.c

---

## y86-64 Instructions

* The book uses a stripped down instruction set for simplicity
  * [https://github.com/boginw/js-y86-64/wiki/Instruction-set](https://github.com/boginw/js-y86-64/wiki/Instruction-set)
  * Note that this is a fork that supports 64-bit instructions

---

## Difference from x86-64

* Major change is to make instructions more clear
  * `rrmovq` moves from register to register
  * `irmovq` moves an immediate value into a register
  * `rmmovq` moves from register to memory
  * `mrmovq` moves from memory to register
* sub and add operators have the same changes to make addressing more clear

---

## y86-64 Version

```asm
# Execution begins at address 0 
    .pos 0
# The stack begins after the instruction memory. Look below for the tag "stack:"
# irmovq moves that memory address into the instruction pointer
    irmovq stack, %rsp      # Set up stack pointer
# Then we call main
    call main       # Execute main program
# When main returns, we halt the program
    halt            # Terminate program

# Here is our function that uses stack memory
use_stack:
# This is the reflexive stack setup at the start of every function
	pushq	%rbp
	rrmovq	%rsp, %rbp
# Allocate 88 bytes on the stack (80 for 10 long long ints, 8 for the address)
    isubq	$88, %rsp
# This puts the array pointer into %rax and then to the top 8 bytes of the stack.
	rmmovq	%rsp, -8(%rbp)
# In x86 this would be a movq $5, -36(%rbp), but y86 doesn't have immovq
	irmovq  $5, %rbx
# The array begins at -88(%rbp). -64 is -88+24, for index 3*8.
	rmmovq	%rbx, -64(%rbp)
    irmovq  $4, %rbx
# The array begins at -88(%rbp). -16 is -88+(9*8).
	rmmovq	%rbx, -16(%rbp)
	mrmovq	-8(%rbp), %rax
# This is a check for stack smashing from gcc.
# Verifies that we didn't mess with the array pointer.
    rrmovq  %rsp,   %rax
    rrmovq  %rsp,   %rbx
	subq	%rbx,   %rax
	je	.L3
	call	__stack_chk_fail@PLT
.L3:
# Clean up the stack. In x86 this is the `leave` instruction.
    rrmovq  %rbp,   %rsp
    popq    %rbp
# Pop the instruction pointer from the stack and jump back to the caller
	ret

# Our main function
main:
# This is the reflexive stack setup at the start of every function
	pushq	%rbp
	rrmovq	%rsp, %rbp
	call    use_stack
# Return 0.
	irmovq	$0, %rax
# Clean up the stack. We didn't allocate memory.
	popq	%rbp
	ret

# Stack starts here and grows to lower addresses
    .pos 0x120
stack:
```

---

</div>

---

</div>

---

</div>

---

</div>

---

</div>

---

</div>

---

</div>

---

</div>

---

## What is happening?

* What does all of this have to do with computer architecture?
* Content outline:
  * Walk through the life of an instruction
    * Begin with idyllic view
    * Introduce pipeline complexity
  * Zoom back out to C, showing performance ramifications on the way

---

## The Life of an Instruction

* You run a program. Now what?
* It is loaded into memory.
* Where does it start?
  * At main
* What does that mean?
  * The `instruction pointer`, %rip, is set to the address of main

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

</div>
</div>

---

## Instruction Loading (idyllic)

* Instructions are loaded one at a time and executed
* Each clock cycle, we increment the `instruction pointer` by one
  * (aside: some architectures call the `instruction pointer` the `program counter`)

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

</div>
</div>

---

## First Problem

* Some instructions change the instruction pointer
* Could jump to a specific address
* Could calculate it relative to something else

---

## Instruction Loading

* Okay, some math may find a new IP value
* Speaking of math
  * The opcode of the loaded instruction may be math
  * We'll have to load some register values

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

</div>
</div>

---

## Halfway There

* MUX stands for "multiplexor"
  * Selects an input with control lines (not shown)
  * Control comes from the opcodes of the fetched instruction

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

</div>
</div>

---

## Missing Pieces

* Remember all of the access types?
  * Immediate requires an opcode input to the ALU
  * Register inputs to both ALUs
  * But what about direct and indirect memory access?
* And what about calculated instruction pointers?

---

## Everything But Memory

* We select between the next instruction and a calculated instruction
  * But what about a fetched memory location?
  * And what about the memory in general?

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

</div>
</div>

---

## Memory Locations

* Instruction memory and data memory begin in the same place
* But they end up in different places in the CPU
  * This is because they are accessed differently
  * It makes sense to locate data memory "after" ALUs
    * And FPUs
* Instruction memory needs to be located earlier

---

## Register Memory

* And what about register memory?
* Registers are where all of the action takes place
  * So they actually use a different type of physical memory
* The three regions of memory---instruction, data, and register---are separate because they all have different **access patterns and usage**.

---

## What About movq?

* Now we can use direct and indirect memory access
* And we can set the instruction pointer several ways
  * Increment
  * Jump to an absolute address
  * Jump to a calculated address
* But how do we get values into registers?

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

</div>
</div>

---

## Complete?

* Math
  * Either immediate, from the instruction, or from registers
* Memory
  * Access from the instruction, register, or math
* Instruction Pointer
  * Incremented by 1, from math, or from memory

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

</div>
</div>

---

## Example

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

</div>
</div>

---

## Example

* pushq puts value in register rbp into memory

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

</div>
</div>

---

## Example

* movq 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 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 inserts a value into a calculated location

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

</div>
</div>

---

## Great!

* Now let's make it more complicated
* We don't want to wait for each instruction to finish before going on to the next
* So we'll add buffers at some steps to remember the current state of things
  * Clock ticks will cause values to leave the buffers and begin execution
  * That keeps things synchronized
* This is called `pipelined` execution

---

## Pipeline

* Each gray bar is a buffer
* This is a pipeline
  * Increases throughput roughly 5x

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

</div>
</div>

---

## Canonical Drawing (wikipedia)

---

## Named Steps

* Instruction Fetch
* Instruction Decode and Register Fetch
* Execute or Address Calculation
* Memory Access
* Write back

---

## Done? No!

* There are obviously depedencies between instructions
* And what if there is a conditional jump? 
  * How do we know which branch we should execute?
* Pipelining brings up a lot of issues, which we'll have to cover

---

## Realistic View - 1995

---

## Realistic View - 2000

---

## Realistic View - 2006
<img style="width: 100%" class="r-stretch" src="./figures/IntelFigure2-2_IntelCoreMicroarchitecturePipelineFunctionality2006.png" />

---

## Big field

* There are plenty of optimizations
  * Branch prediction
  * Speculative execution
  * Instruction reordering and rewriting
  * And more!
* We won't be able to go into everything
* Next time we'll go over a few pipelining problems and solutions

---

## Midterm Review!