# CS 211 - Lecture 26

## Computer Architecture

### Review

Bernhard Firner

2025-12-09

---

## Computer Architecture

* Why did you have to take this course?
  * Theoretical computer science is done on paper and white boards
  * Everything else is done on computers
* If you don't understand computers, you won't be able to use them well

---

## Architecture Stack

* C
* Assembly
* Digital Logic
  * Synchronous
  * Combinational

---

## Abstraction Light

* C is only a light abstraction over assembly
  * Compiler optimizations probably the most confusing part
* Knowing about assembly and hardware, C should make even more sense now

---

## Static and Dynamic Memory

* The C memory model should make sense now
* Here are some questions that should feel intuitive
  * Why can't we return variable length arrays from a function?
  * Does dynamic memory allocation occur on the stack or the heap?
  * Which direction does stack memory grow? And heap memory?

---

## Stack and Heap Memory

* Stack memory generally grows by *subtracting* from %rsp
  * So the stack grows down
* The heap is global, and grows upwards

---

## Memory Example

```C
/*
 * Stack Vs Heap example
 */

#include <stdio.h>
#include <stdlib.h>

void a() {
    unsigned char stack_memory[16];
    unsigned char *heap_memory = calloc(16, sizeof(unsigned char));

printf("a stack memory is %p\n", stack_memory);
    printf("a heap memory is %p\n", heap_memory);
    free(heap_memory);

return;
}

void b() {
    unsigned char stack_memory[16];
    unsigned char *heap_memory = calloc(16, sizeof(unsigned char));

printf("b stack memory is %p\n", stack_memory);
    printf("b heap memory is %p\n", heap_memory);

a();

free(heap_memory);

return;
}

void c() {
    unsigned char stack_memory[16];
    unsigned char *heap_memory = calloc(16, sizeof(unsigned char));

printf("c stack memory is %p\n", stack_memory);
    printf("c heap memory is %p\n", heap_memory);

b();

free(heap_memory);

return;
}

void d() {
    unsigned char stack_memory[16];
    unsigned char *heap_memory = calloc(16, sizeof(unsigned char));

printf("d stack memory is %p\n", stack_memory);
    printf("d heap memory is %p\n", heap_memory);

c();

free(heap_memory);

return;
}

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

---

## Example Output

* Example values not guaranteed, direction is consistent

<pre>
$ ./a.out
d stack memory is 0x7ffc2eceb250
d heap memory is 0x55d2ddab12a0
c stack memory is 0x7ffc2eceb210
c heap memory is 0x55d2ddab16d0
b stack memory is 0x7ffc2eceb1d0
b heap memory is 0x55d2ddab16f0
a stack memory is 0x7ffc2eceb190
a heap memory is 0x55d2ddab1710
</pre>

---

## The Operating System

* Memory allocated on the stack is easy to understand
  * Adjust %rsp and that's it
  * %rsp is set back to %rbp and memory is returned
* Memory with longer lifetimes is more complicated
  * This memory is managed by your operating sytem
  * Or, on an embedded device, you set aside a memory pool

---

## More OS Stuff

* This isn't an OS course, but the OS is another major component
  * Take CS 214 and CS 416 to dive more into systems programming
* In addition to memory, the OS also handles exceptions and I/O
  * That includes networking I/O which is pretty important
    * See CS 352

---

## Primitive Types

* Primitive types exist in hardware
  * int, float, double, long, short, char
  * You should recognize that these are things we can put into a register

---

## Ints

* Integers are either unsigned or signed
  * If signed, stored in 2's complement
* The negative of an 8-bit number is
  * (n ^ 11111111) + 1
  * So adding the negative and positive together yields 0

---

## 2's complement

* Remember that a number added to its negative will yield 0
  * With a carry out from the MSB
  * Not an overflow, which occurs when the carry in to the MSB != the carry out

* Q: What are the bits of the most negative 16-bit number?

---

## Casting

* What happens when we cast?

```c
#include <stdio.h>

int main(int argc, char** argv) {
    int a = 260;
    char b = (char)a;

printf("a and b are %i and %i\n", a, b);

return 0;
}
```

* What prints out?

---

## ASM

* Can you read this code?

```asm
	.file	"check.c"
	.text
	.section	.rodata
.LC0:
	.string	"a and b are %i and %i\n"
	.text
	.globl	main
	.type	main, @function
main:
.LFB0:
	.cfi_startproc
	endbr64
	pushq	%rbp
	movq	%rsp, %rbp
	subq	$32, %rsp
	movl	%edi, -20(%rbp)
	movq	%rsi, -32(%rbp)
	movl	$260, -4(%rbp)
	movl	-4(%rbp), %eax
	movb	%al, -5(%rbp)
	movsbl	-5(%rbp), %edx
	movl	-4(%rbp), %eax
	movl	%eax, %esi
	leaq	.LC0(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	printf@PLT
	movl	$0, %eax
	leave
	ret
.LFE0:
	.size	main, .-main
	.ident	"GCC: (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0"
	.section	.note.GNU-stack,"",@progbits
	.section	.note.gnu.property,"a"
	.align 8
	.long	1f - 0f
	.long	4f - 1f
	.long	5
0:
	.string	"GNU"
1:
	.align 8
	.long	0xc0000002
	.long	3f - 2f
2:
	.long	0x3
3:
	.align 8
4:
```

---

## Addressing Types

* You remember these, right?
  * Immediate
  * Register
  * Direct
  * Indirect

---

## Immediate Addressing

* We can use constant values with registers
  * e.g. `$5` refers to the constant value 5
* This sets the destination to 5
  * `movq $5 dst`

---

## Register Addressing

* More common to work with register values
* `movq %rax, %rdi`
  * Moves the value in %rax into %rdi

---

## Direct and Indirect

* These are pointer equivalents
* Direct uses a hard-coded address
  * `movq 0x40abcd, dst`
  * Would move `memory[0x40abcd]` to destination
* `moveq (%rax), dst`
  * Would move `memory[%rax]` to destination
* The first is `direct`, the second is `indirect`

---

## Displacement and Scaling

* Arrays are very common, so syntax supports them
  * `8(%rax)` is `memory[%rax + 8]`
  * like `char_ptr[8]`
* But most displacement has a scaling factor
  * E.g. ints have a scale of 4 bytes
  * `8(%rax, %rcx, 4)` is `memory[%rax + 8 + 4*%rcx]`
* Can skip the displacement for familiar array access
  * `(%rax, %rcx, 4)` is `memory[%rax + 4*%rcx]`

---

## Why have displacement?

* Because we could have a struct with an array in it!
* Let's talk about structs!

---

## Structs

* Sometimes we need data that doesn't exist in hardware
  * C provides *structs*, which allow us to group data into a new type
* Structs can hold other structs, but at some point the basic types will still be primitives

---

## Memory Alignment

```C
typedef struct Aligned Aligned;
struct Aligned {
    int a : 10;
    int b : 10;
    int c : 10;
    long long int d : 64;
};
```

* `sizeof(Aligned)` will have a size of 16
* This makes sense, if you remember that we load memory in blocks, so we should align to block boundaries
  * We could pack that into 12 bytes, but that doesn't align

---

## Float Union

```C
#include <stdio.h>
#include <stdlib.h>

typedef struct FloatBits FloatBits;
struct FloatBits {
    unsigned int significand : 23;
    unsigned int exponent : 8;
    unsigned int sign : 1;
};

typedef union FloatIntBits FloatIntBits;
union FloatIntBits {
    float the_float;
    int the_int;
    FloatBits the_bits;
};

int main(int argc, char** argv) {
    if (argc < 2) {
        printf("Give me a float!");
        return 0;
    }

FloatIntBits fib = {.the_float = atof(argv[1])};

printf("The size of fib is %lu\n", sizeof(fib));
    printf("The size of FloatBits is %lu\n", sizeof(FloatBits));
    printf("The sign is %u, the exponent is %u, and the significand is %u\n", fib.the_bits.sign, fib.the_bits.exponent, fib.the_bits.significand);

printf("%f as an int is %i\n", fib.the_float, fib.the_int);
    return 0;
}
```

---

## Floating Point Numbers

* Let's talk about floating point numbers
* Why do we need them?
  * int doesn't have enough range
  * Both large and small scale
* We could represent fractions with fixed point numbers
  * But this doesn't solve the range issue

---

## Parts of a Float

* [IEEE 754 Standard](https://en.wikipedia.org/wiki/IEEE_754)
* Three sections
  * Sign: 0 or 1
  * Exponent
  * Significand (also called mantissa)

<table>
<tr><td>Sign</td><td colspan="8">Exponent</td><td colspan="23">Significand</td></tr>
<tr><td>31</td><td>30</td><td colspan="6">...</td><td>23</td><td colspan="21">22</td><td>...</td><td>0</td></tr>
</table>

---

## Float Values

* Special patterns for inf and NaN
  * Generally with all exponent bits set
* For fp32
  * value = $(-1)^{sign} \times 2^{exponent - bias} \times (1+\frac{Significand}{2^{23}})$
* If exponent bits all 0
  * value = $(-1)^{sign} \times 2^{1-bias} \times (\frac{Significand}{2^{23}})$
  * These are subnormal numbers

---

## Why Care About Floats?

* First, we've only got integers and floats
* Second, scientific computing, ML, rendering, etc

---

## More On Floats

* Let's say we have an fp4 value
  * 1 bit sign
  * 2 bits exponent
  * 1 bit significand
  * bias = 1
* It has no NaN or inf
  * What values can it take on?

---

## Rounding

* How do floats round?
  * What if we always chose up or down?
    * Then we get biased results
* So we could round up half the time and down the other half
  * For example, round towards even

---

## Stochastic Rounding

* For machine learning, that isn't good enough
* Rounding to nearest even has bias with some distributions
* Instead, round with probability proportional to the distance
  * e.g. 0.1 has to round to 0 or 0.5
    * it rounds to 0 with p = 0.2,
    * it rounds to 0.5 with p = 0.8

---

## Digital Math

* All math happens in the CPU
  * Integer math in ALUs
    * Arithmetic logic units
  * Floating point math in FPUs
    * Floating Point Units

---

## AMD Zen 4

---

## Arm Cortex A510

---

## Idyllic Architecture

* Real hardware is complex, so we made up a simple system

---

## Pipelines

* Here's our idyllic version of a 5-stage CPU pipeline
* Each gray bar is a buffer, called a `pipeline register`
* The pipeline stages increase 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>

---

## Where is the Cache?

* Notice that there are multiple pieces with memory
  * Instruction cache in the IF stage
  * Registers in ID
  * L1 cache in MA
* So our idyllic version of the pipeline is hiding many details

---

## Dependencies

* Our idyllic pipeline is most useful for revealing dependencies
  * If we need to load data into a register for some math, that is a data dependency
* Q: If a load instruction issued on cycle 0 completes at the end of cycle 6, how large a bubble is required?
  * Assume that we can forward directly from the MA stage to the EX stage

---

## Dealing with Dependencies

* Data hazards
  * Data forwarding
  * Instruction reordering
* Control Hazards
  * Use speculative execution with branch prediction
  * And, as we now know, prefetch instructions!

---

## Prefetching

* It takes time to load data into a cache
  * Whether the instruction cache, or the data cache
* So modern CPUs predict what data you want
* They do this by guessing the data access pattern
  * We call this locality
  * Good locality leads to better prefetching and fewer misses, and more efficient data usage

---

## Locality

* Programs use data near what they are currently using
* `Temporal locality`: programs keep using the data they've got
* `Spatial locality`: when programs read new data, it is near what they recently addressed

---

## Locality

```c
float mean(float* data, size_t size) {
    float sum = 0;
    for (size_t i = 0; i < size; ++i) {
        sum += data[i];
    }
    return sum/size;
}
```

* Data:
  * Spatial locality in the array access
  * Temporal locality in the sum variable

---

## Locality continued

```c
float mean(float* data, size_t size) {
    float sum = 0;
    for (size_t i = 0; i < size; ++i) {
        sum += data[i];
    }
    return sum/size;
}
```

* Instructions:
  * Spatial locality: the instructions could have been prefetched before the function was called
  * Temporal locality: repeatedly use the loop instructions

---

## Modern Prefetching

* Sequential access (data stream)
  * Most code, data in arrays
* Strided access
  * Modern CPUs predict strided patterns in data access
* Region
  * Access within blocks
* Up/Down
  * Predict adjacent memory access

---

## Prefetching and Block Size

* A small block is fetched faster, but has a higher miss rate
  * Since it may not grab the entire region that will be used
* Large blocks increase hit rate if spatial locality is true
  * But decrease the number of cache lines
  * This increases misses if data isn't used in groups of that block size
    * And contention misses, if there are multiple programs/threads
  * Higher latency to load too

---

## Describing a Cache

* For any cache
  * Data is fetched into `cache lines` which each hold a single `block`
  * Lines are grouped into `sets`
* For CPUs and GPUs there are different cache levels
* They all make different tradeoffs with number of sets and block sizes

---

## Visualization

---

## Cache Lines

* Cache lines hold three fields
  * Valid bit
  * Tag
  * Data
    * $2^b$ bytes, usually 64-bytes in L1/L2/L3 cache

---

## Querying the Cache

* Memory, as we know from pointers, is described by a number
  * The address will be split into pieces
* Remember *aliasing* from C structs?
  * Each line is a particular size, called the block size

<table>
<tr> <td colspan="12">Full address</td></tr>
<tr> <td colspan="4">tag bits</td><td colspan="4">set bits</td><td colspan="4">block bits</td></tr>
</table>

---

## Sizes

* The sizes of the bit fields indicate the amount of memory being addressed
  * Sets: $S = 2^s$
  * Lines per set: $E$
  * Block size: $B = 2^b$
  * Cache size: $C = B \times E \times S$
    * Not including overhead for valid and tag bits

---

## Querying the Cache

---

## Cache Misses

* `cold miss`: When the valid bit is unset (also called *compulsory miss*)
* `capacity miss`: When our cache is full and the miss couldn't be avoided
  * For example, you are looping repeatedly through a 1MB array on a 64KB cache
  * In a non-transposed matrix multiplication, this caused many misses
* `conflict miss`: When the program has used the cache poorly
  * There is available space, but locality has not been exploited to use it

---

## Limitations

* Why haven't our cache sizes grown?
* Let's talk about DLD
  * Each cache query is done in hardware
  * This can increase latency as circuit grow
  * Also increases space require by a nonlinear amount

---

## Stacked Decoders

* We stack multiple decoders together to convert an address to a select signal
* Notice that only one output is active at a time
  * We could use this to select a single cache line given an input address

</div>
</div>

---

## Delays

* A Mux converts N inputs to 1 output, selecting one of them
* $log_2(n)$ control inputs are required
* Q: Using a sum of products formula and gates with 2 inputs, and assume that each gate has a delay of 1ps, what is the delay of a 4 to 1 Mux?

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

</div>
</div>

---

## Drawback

* Logic circuits grows larger nonlinearly
  * Decoders are 2 wide for 1 input, 4 wide for 2, 8 wide for 3...
  * And a multiplexor will grow deeper
* So silicon costs and delays grow too fast to ignore, even as transistor density improves

---

## Meaning?

* If performance is a concern, you will always need to know architecture
  * Otherwise, it won't be clear how to fix bad code

---

## The Final

* Uploaded a version of quiz1 and the midterm with marked answers to the files section of canvas
  * Mostly so you stop bothering me, I don't believe that studying answers is a good idea
* Will hold office hours next week at the usual time
  * Unless people tell me that some other time is better
* Post public questions on piazza

---

## How not to Open-Ended

Q: Why does transposing a matrix make matrix multiplication faster on our CPUs? Only partial credit will be given for vague answers.

A: Because transposed matrix gets multiplied faster.