# CS 211 - Lecture 25

## Computer Architecture

### DLD and Review

Bernhard Firner

2026-04-29

---

## Review

* Computers use two types of digital logic
  * combinational: stateless
  * sequential: has state
* Unless you printed this out, you are using digital logic right now!

---

## Combinational Logic

* We've looked at the adder quite a bit
* Circuits begin by finding each line in the truth table with output = 1
  * $Sum = (C_{in} \land \bar{B} \land \bar{A}) \lor  (B \land \overline{C_{in}} \land \bar{A}) ...$
  * Or $Sum = C_{in}\overline{AB} + B\overline{AC_{in}} + A\overline{BC_{in}} + ABC_{in}$
* Simpler with XOR
  * $Sum = (C_{in} \oplus A \oplus B)$

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

<div class="container">
<table>
<tr> <th>Input A</th><th>Input B</th><th>Carry In</th><th>Sum</th><th>Carry Out</th></tr>
<tr> <td>0      </td><td>0      </td><td>0       </td><td>0  </td><td>0    </td></tr>
<tr> <td>0      </td><td>0      </td><td>1       </td><td>1  </td><td>0    </td></tr>
<tr> <td>0      </td><td>1      </td><td>0       </td><td>1  </td><td>0    </td></tr>
<tr> <td>0      </td><td>1      </td><td>1       </td><td>0  </td><td>1    </td></tr>
<tr> <td>1      </td><td>0      </td><td>0       </td><td>1  </td><td>0    </td></tr>
<tr> <td>1      </td><td>0      </td><td>1       </td><td>0  </td><td>1    </td></tr>
<tr> <td>1      </td><td>1      </td><td>0       </td><td>0  </td><td>1    </td></tr>
<tr> <td>1      </td><td>1      </td><td>1       </td><td>1  </td><td>1    </td></tr>
</table>
</div>

</div>
</div>

---

## Adder with Carry

* The carry out has multiple solutions
  * $C_{out} = \bar{A}BC_{in}  + AC_{in}\bar{B} + AB\overline{C_{in}} + ABC_{in}$
* This simplifies multiple ways
  * $C_{out} = AB + C_{in}(A \oplus B)$
  * $C_{out} = BC_{in} + A(B \oplus C_{in})$
  * $C_{out} = AC_{in} + B(A \oplus C_{in})$

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

</div>
</div>

---

## Many Building Blocks

* Adders, muxes, decoders, etc are all used to build up complex logic
* They don't seem exciting, but we can do clever things with them

</div>
<div class="col">
<img style="width: 50%" class="r-stretch" src="./figures/24_2to4_decoder.svg" />
<br/>
<small>A decoder</small>
<img style="width: 50%" class="r-stretch" src="./figures/24_bit_mux.svg" />
<br/>
<small>A multiplexer</small>

</div>
</div>

---

## Decoding

* Consider a decoder
* $n$ input bits are converted into $2^n$ outputs
* This seems boring, but we can actually implement any arbitrary circuit with this and some OR gates

</div>
<div class="col">
<img style="width: 50%" class="r-stretch" src="./figures/24_2to4_decoder.svg" />
<br/>
<small>A 2 to 4 decoder</small>

</div>
</div>

---

## Decoding

* Recall that the circuit from any truth table can be written as a sum or products
  * The inputs of each row are ANDed together
  * Then the rows are ORed together
* Let us begin by giving a number to each row

<div class="container">
<table>
<tr> <th>Input A</th><th>Input B</th><th>Carry In</th><th>Sum</th><th>Carry Out</th><th>Row #</th></tr>
<tr> <td>0      </td><td>0      </td><td>0       </td><td>0  </td><td>0    </td><td>0 </td></tr>
<tr> <td>0      </td><td>0      </td><td>1       </td><td>1  </td><td>0    </td><td>1 </td></tr>
<tr> <td>0      </td><td>1      </td><td>0       </td><td>1  </td><td>0    </td><td>2 </td></tr>
<tr> <td>0      </td><td>1      </td><td>1       </td><td>0  </td><td>1    </td><td>3 </td></tr>
<tr> <td>1      </td><td>0      </td><td>0       </td><td>1  </td><td>0    </td><td>4 </td></tr>
<tr> <td>1      </td><td>0      </td><td>1       </td><td>0  </td><td>1    </td><td>5 </td></tr>
<tr> <td>1      </td><td>1      </td><td>0       </td><td>0  </td><td>1    </td><td>6 </td></tr>
<tr> <td>1      </td><td>1      </td><td>1       </td><td>1  </td><td>1    </td><td>7 </td></tr>
</table>
</div>

---

## Decoding an Adder

* Sum is rows 1, 2, 4, 7
* Carry out is rows 3, 5, 6, 7
* One decoder output is active at a time

</div>
<div class="col">
<img style="width: 80%" class="r-stretch" src="./figures/24_decoder_full_adder.svg" />
<br/>
<small>A full adder from a decoder</small>

</div>
</div>

---

## Remember Opcodes?

* Our C programs are turned into assembly
  * Which is just a bunch of numbers
* Those numbers are decoded into signals to control the hardware

<img style="width: 50%" class="r-stretch" src="./figures/IntelFigure_ADD.png" />
<br/>
<small>Intel® 64 and IA-32 Architectures Software Developer’s Manual, June 2025</small>
</div>
</div>

---

## What is ADD?

* Look at the three additions from the objdump in lecture 11

* 48 is 0b01001000, indicating that 64 bit values should be used
  * See [https://wiki.osdev.org/X86-64_Instruction_Encoding#REX_prefix](https://wiki.osdev.org/X86-64_Instruction_Encoding#REX_prefix)
* REX.W + 83 is the opcode for addition with 64 bit register, 8 bit immediate
* The immediate values (0x8 and 0x10) are in the instructions themselves
* The address of the ax register is 0

---

## What is ADD?

* Look at the three additions from the objdump in lecture 11

* The last addition uses opcode 01, for adding 2 (non 64-bit) registers
* The d0 contains the addresses of the two registers, dx and ax

---

## How About SUB?

* The subtraction instruction is very close to the addition instruction
  * In fact, 48 83 is the beginning of both

<img style="width: 70%" class="r-stretch" src="./figures/IntelFigure_SUB.png" />
<br/>
<small>Intel® 64 and IA-32 Architectures Software Developer’s Manual, June 2025</small>
</div>
</div>

---

## How About SUB?

* Let look at some subtractions from the sieve

---

## Why So Similar?

* Recall that the has controls going into it, as well as the operands
* We only need 1 bit to turn an addition into a subtraction
* Let's look at the circuit, and how it differs from addition

---

## 4-bit Adder/Subtracter

* A single bit does 2's complement
* This turns addition into subtraction
* Isn't this clever? The same hardware does two things!
  * Do you appreciate 2's complement more now?

---

## 4-bit Adder/Subtracter

* The bit that turns addition into subtraction comes from the instruction itself

---

## DLD in Use

* When the CPU decodes an instruction, it is really flipping bits in its logic circuit
* In the pipelined CPU, we need to keep these instruction separate, so we use memory and clocks

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

</div>
</div>

---

## Memory

* Memory means sequential logic
* How is memory stored by logic gates?
  * We simply feed the output back into the input
* The latch is the simplest form of register memory, storing a single bit

---

## SR-Latch

| R      |     S | $Q$   | $\overline{Q}$   |
| :----: | :---: | :---: | :---:            |
| 0      | 0     | $Q$   | $\overline{Q}$   |
| 0      | 1     | 1     | 0                |
| 1      | 0     | 0     | 1                |
| 1      | 1     | 0     | 0 (don't do this)|

</div>

</div>
</div>

---

## Stability

* Latches are not stable
  * They have a bad state when both set and reset are 1
* They also change as soon as an input changes
  * This is not desirable if we want to align on clock changes

---

## Clock Edges

* So we build circuits that will only change on the rising or falling edge of the clock
 * Remember, there are only 2 states in digital logic, high and low (1 and 0)
* We want to make a circuit that only updates its value when the clock changes
  * So make a latch that only changes when the clock is in one state or the other
  * Then put two in a row that change on the opposite state

---

## Flip Flop

* This is an edge triggered D Flip-Flop
  * There are variations, but this should be enough to grasp the concept

---

## Zooming Out

* CPU registers and buffers are made of flip flops
* All non-memory circuits are combinational
* The critical path of the circuits in a CPU instruction stage determine the fastest possible clock rate

---

## Clocks and Reliability

* Imagine that we estimate that our ALU operations take 50ps
  * Due to inconsistency in manufacturing, that could be 5% slower
  * So we need to allow for 52.5ps, just in case
* We also have a crystal oscillator that is correct to 20ppm (parts per million)
  * If we try to measure 52.5 we would get $52.5 \times (1.0 \pm 20\times10^{-6})$
  * As fast as 52.49895ps, so leave a tiny bit more delay for the circuit

---

## Limited Space, Real Delays

* Adding too much logic to the same circuit degrades some electrical properties
  * Increasing voltage is required, driving up power consumption
* This constraint led to multi-core systems
* Pipeline delays, from registers and logic, pushed CPU designers to find more opportunities for parallelism

---

## Drawbacks of Size

* Logic circuits grows larger nonlinearly
  * Decoders are 2 wide for 1 input, 4 wide for 2, 8 wide for 3...
  * A multiplexer will grow deeper
  * Lookahead adders need more propagate and generate circuits with more bits
* So silicon costs and delays grow too fast to ignore, even as transistor density improves

---

## Where is the memory?

* Notice that there are multiple pipeline stages with memory
  * Instruction cache in the IF stage
  * Registers in ID
  * L1 cache in MA (and L2, L3, etc)
* Branch prediction also has memory and the reorder buffer stores order details
  * Modern CPUs have a lot of state not captured in our simple 5 stage illustration

---

## Cache

* The cache is a CPU's largest chunk of memory
  * It is also subject to constraints from DLD
  * Fully associative would require more comparisons in parallel to find matching tags
  * The circuit itself would have a longer critical path
* So we settle for "big enough"
  * 8-way associate in the L1 cache that we have looked at

---

## Describing a Cache

* For any cache
  * Data is fetched into **cache lines** which each hold a single **block**
  * Lines are grouped into **sets**
  * *n-way* associative means that there are *n* lines per set
* For CPUs and GPUs there are different cache levels
* They all make different trade-offs 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
* You now know that these are all flip-flops
  * With mazes of wires for data transfer
  * Small towns of logic for tag and valid bit comparisons

---

## Querying the Cache

* Memory, as we know from pointers and decoders, is described by a number
  * The address will be split into pieces
* Each line stores a single block of data
  * This is the smallest unit of data that can be loaded into a cache

<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

---

## Dealing with Cache Misses

* A cache miss means falling back to the previous memory in the hierarchy
  * The hierarchy exists for every architecture: CPU, GPU, embedded MCU, etc
* The best way to deal with misses is by avoiding them with prefetching

<div class="col">
<img style="width: 50%" class="r-stretch" src="./figures/nvidia-a100-memory-hierarchy.webp" />
<br/>
<small><a href="https://developer.nvidia.com/blog/cuda-refresher-cuda-programming-model/">https://developer.nvidia.com/blog/cuda-refresher-cuda-programming-model/</a></small>
</div>

---

## Prefetching

* It takes time to load data into a cache
  * Whether the instruction cache, or the data cache
* If the hardware can predict what memory you want, it can load it before your program uses it

---

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

* In a way, a large block size is like more prefetching
  * As long as you actually use memory in large chunks
* This can be true for data
  * Less true for code, which is broken into different functions of limited size

---

## Block Sizes

* Large blocks generally increase the hit rate, up to a point
  * But decrease the number of cache lines since the total cache size is still limited
* If data is used in smaller chunks, memory is wasted
    * This could increase contention misses
* Larger blocks also incur higher latencies to fetch

---

## Optimization

* Some optimizations are done by your compiler
* But broad, software architectural choices can have huge impacts
  * Changing data usage can drastically change prefetching success
* The more you understand architecture, the more effectively you can work with your hardware

---

## 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
  * Even worse; you won't realize when you are using them poorly

---

## Final Preparations

* The final is on Friday, May 8th, from 4PM to 7PM
* Last semester's final and answers are on canvas
* I will spend Monday reviewing example and past questions