# CS 211 - Lecture 18

## Computer Architecture

###  Types of Memory

Bernhard Firner

2025-10-29

---

## Notes

* Realized that I misordered the syllabus, SIMD and parallelism is lecture 22
  * Comes before the parallel and GPU architecture
* We're still talking about the cache

---

## Review

---

## Exploiting Locality

* Each part of the system assumes:
  * The next higher part is faster, but will exhibit locality in data usage
  * The next lower part is slower, but has the bandwidth required to meet the faster speed of the higher part

---

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

---

## Locality By Design

* Good design is on *you*, the programmer

---

## Future Hardware Can't Trivialize

* Some problems are solved with future hardware
  * Not this one!
* RAM has grown in density by many orders of magnitude, but latency hasn't kept up
* To compensate, we have more levels of cache now, in a desperate race to keep up with modern processing speed

---

## Reading

* CS:App Chapters 6.2-6.6
* Outside reading:
  * [https://gameprogrammingpatterns.com/data-locality.html](https://gameprogrammingpatterns.com/data-locality.html)

---

## Other Resources

* Good, practical talks from game developers
  * [https://youtu.be/SZOr0m-K5PQ?si=JAG3Lx88y8yjkSaZ](https://youtu.be/SZOr0m-K5PQ?si=JAG3Lx88y8yjkSaZ)
    * Lots of register talk, so fun!
  * Because they *can* share, and performance matters to them
* A good proxy for other industries since games are so varied

---

## Cacheing

* Let's talk about how we cache
  * When is data placed into a cache?
  * When is data evicted?
  * What is the cost?

---

## Abstract Cache

* A cache is a mirror of data from a lower cache

<div class="container">
<table>
<tr> <b><th colspan="4"> Higher Cache </th></b></tr>
<tr> <td>Block 12 </td><td> Block 300 </td><td> Block 5 </td><td> Block 8 </td></tr>
</table>

* Data goes back and forth between these two.

<table>
<tr> <th colspan="4"> Lower Cache  </th></tr>
<tr> <td>Block 1 </td><td> Block 2</td><td> Block 3 </td><td> Block 4</td></tr>
<tr> <td>Block 5 </td><td> Block 6</td><td> Block 7 </td><td> Block 8</td></tr>
<tr> <td>Block 9 </td><td> Block 10</td><td> Block 11</td><td> Block 12</td></tr>
<tr> <td colspan="4" rowspan="4">Block ........................................................</td></tr>
</table>
</div>

---

## Describing Cache

* Obviously some cache memory is larger than other memory
* But how do we describe a cache?
* For CPU cache, meaning L1, L2, l3:
  * Data is fetched into `cache lines`
  * Each line is arranged into a `set`

---

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

---

## Hit or Miss?

* When the desired data is missing, there is a *cache miss*
* When the desired data is present, there is a *cache hit*

---

## Cold Cache

* When a device is turned on, all cache is empty
* The valid bits are set to false, 
* Every request for memory is a *miss*
  * We call these *cold misses*

---

## Fetching Data

* Whenever there is a cache miss, we must fetch some data
* Let's go through an example of how this looks

---

## Direct Cache Example

* In a direct cache, there is one line per set
* Let's say we have 16 bytes of memory
  * That's 4 bits of addresses
* Cache
  * 4 sets
  * 2 bytes/block
  * 1 line/set

---

## Direct Cache Example

* Starting state

<table>
<tr> <td></td><th> valid  </th> <th>Tag</th> <th colspan="2"> Block </th></tr>
<tr> <td><b>Set 0</b></td><td> 0</td><td> </td><td> </td><td> </td></tr>
<tr> <td><b>Set 1</b></td><td> 0</td><td> </td><td> </td><td> </td></tr>
<tr> <td><b>Set 2</b></td><td> 0</td><td> </td><td> </td><td> </td></tr>
<tr> <td><b>Set 3</b></td><td> 0</td><td> </td><td> </td><td> </td></tr>
</table>

---

## Direct Cache Example

* Request address 0000
  * The last bit addresses the 2 bytes in the block
  * The middle two bits address the set
  * The highest bit is the tag

---

## Direct Cache Example

* Request address 0000
  * The valid bit on set 0 isn't set, so this is a *cold miss*
  * We have to go to the next memory  down to fill the cache

<table>
<tr> <td></td><th> valid  </th> <th>Tag</th> <th colspan="2"> Block </th></tr>
<tr> <td><b>Set 0</b></td><td> 1</td><td>0</td><td>m[0]</td><td>m[1]</td></tr>
<tr> <td><b>Set 1</b></td><td> 0</td><td> </td><td> </td><td> </td></tr>
<tr> <td><b>Set 2</b></td><td> 0</td><td> </td><td> </td><td> </td></tr>
<tr> <td><b>Set 3</b></td><td> 0</td><td> </td><td> </td><td> </td></tr>
</table>

---

## Direct Cache Example

* Request address 0001
  * The tag is 0 and the set is 0
  * That's a **hit**, and we can fetch the byte from the block

---

## Direct Cache Example

* Request address 0111
  * The tag is 0 and the set is 3
  * The valid bit isn't set, so this is a *cold miss*

---

## Direct Cache Example

* Request address 1000
  * The tag is 1 and the set is 0
  * The valid bit is set, but the tag doesn't match
  * So we "evict" that data and replace it

<table>
<tr> <td></td><th> valid  </th> <th>Tag</th> <th colspan="2"> Block </th></tr>
<tr> <td><b>Set 0</b></td><td> 1</td><td>1</td><td>m[8]</td><td>m[9]</td></tr>
<tr> <td><b>Set 1</b></td><td> 0</td><td> </td><td> </td><td> </td></tr>
<tr> <td><b>Set 2</b></td><td> 0</td><td> </td><td> </td><td> </td></tr>
<tr> <td><b>Set 3</b></td><td> 1</td><td>0</td><td>m[6]</td><td>m[7]</td></tr>
</table>

---

## Direct Cache Example

* Request address 0000
  * The tag is 0 and the set is 0
  * This is the memory we just evicted! Oh no!
  * This type of miss is called a *conflict miss*
    * There is enough capacity, but we are mapping to the same location

---

## Reducing Conflict Misses

* Conflict misses are common in a direct cache
  * any memory with an offset equal to the cache size will cause them
  * this is *thrashing*, going from one memory to the other and back
    * Happens in disks, happens in cache, happens everywhere
* An obvious solution is to provide multiple lines per set

---

## Set Associative Caches

* Two-way associative (E = 2)

---

## Associative Cache Example

* Starting state
  * Blocks still hold 2 bytes
  * There are two sets, each with two lines
    * So the size is the same
  * 2 bits of tag

<table>
<tr> <td></td><th> valid  </th> <th>Tag</th> <th colspan="2"> Block </th><th> valid  </th> <th>Tag</th> <th colspan="2"> Block </th></tr>
<tr> <td><b>Set 0</b></td><td> 0</td><td> </td><td> </td><td> </td><td> 0</td><td> </td><td> </td><td> </td></tr>
<tr> <td><b>Set 1</b></td><td> 0</td><td> </td><td> </td><td> </td><td> 0</td><td> </td><td> </td><td> </td></tr>
</table>

---

## Associative Cache Example

* Request address 0000
  * tag=00, s=0
  * cold miss

<table>
<tr> <td></td><th> valid  </th> <th>Tag</th> <th colspan="2"> Block </th><th> valid  </th> <th>Tag</th> <th colspan="2"> Block </th></tr>
<tr> <td><b>Set 0</b></td><td> 1</td><td> </td>00<td>m[0]</td><td>m[1]</td><td> 0</td><td> </td><td> </td><td> </td></tr>
<tr> <td><b>Set 1</b></td><td> 0</td><td> </td><td> </td><td> </td><td> 0</td><td> </td><td> </td><td> </td></tr>
</table>

---

## Associative Cache Example

* Request address 0001
  * hit

<table>
<tr> <td></td><th> valid  </th> <th>Tag</th> <th colspan="2"> Block </th><th> valid  </th> <th>Tag</th> <th colspan="2"> Block </th></tr>
<tr> <td><b>Set 0</b></td><td> 1</td><td> </td>00<td>m[0]</td><td>m[1]</td><td> 0</td><td> </td><td> </td><td> </td></tr>
<tr> <td><b>Set 1</b></td><td> 0</td><td> </td><td> </td><td> </td><td> 0</td><td> </td><td> </td><td> </td></tr>
</table>

---

## Associative Cache Example

* Request address 0111
  * tag=01, set=1
  * cold miss

<table>
<tr> <td></td><th> valid  </th> <th>Tag</th> <th colspan="2"> Block </th><th> valid  </th> <th>Tag</th> <th colspan="2"> Block </th></tr>
<tr> <td><b>Set 0</b></td><td> 1</td><td> </td>00<td>m[0]</td><td>m[1]</td><td> 0</td><td> </td><td> </td><td> </td></tr>
<tr> <td><b>Set 1</b></td><td> 1</td><td> </td>01<td>m[6]</td><td>m[7]</td><td> 0</td><td> </td><td> </td><td> </td></tr>
</table>

---

## Associative Cache Example

* Request address 1000
  * tag=10, set=0
  * cold miss

<table>
<tr> <td></td><th> valid  </th> <th>Tag</th> <th colspan="2"> Block </th><th> valid  </th> <th>Tag</th> <th colspan="2"> Block </th></tr>
<tr> <td><b>Set 0</b></td><td> 1</td><td> </td>00<td>m[0]</td><td>m[1]</td><td> 1</td><td>10</td><td>m[8]</td><td>m[9]</td></tr>
<tr> <td><b>Set 1</b></td><td> 1</td><td> </td>01<td>m[6]</td><td>m[7]</td><td> 0</td><td> </td><td> </td><td> </td></tr>
</table>

---

## Associative Cache Example

* Request address 0000
  * Hit!

<table>
<tr> <td></td><th> valid  </th> <th>Tag</th> <th colspan="2"> Block </th><th> valid  </th> <th>Tag</th> <th colspan="2"> Block </th></tr>
<tr> <td><b>Set 0</b></td><td> 1</td><td> </td>00<td>m[0]</td><td>m[1]</td><td> 1</td><td>10</td><td>m[8]</td><td>m[9]</td></tr>
<tr> <td><b>Set 1</b></td><td> 1</td><td> </td>01<td>m[6]</td><td>m[7]</td><td> 0</td><td> </td><td> </td><td> </td></tr>
</table>

---

## Fully Associative Cache

* We could go even farther
* Just 1 set
  * Now conflict misses will only happen when capacity is filled
    * *capacity misses*
* Look things up by their tag

---

## Fully Associative Drawbacks?

* The tag bits need to be compared to every single line
  * This is hardware exensive
    * Easy to get either large or fast, not both
* A fully associative cache is only used in special, small cache applications
  * Like the translation lookaside buffer

---

## Eviction in an Associative Cache

* Obviously associativity doesn't solve all conflict and capacity misses
  * Occur when a set is fully utilitized and new memory needs to be cached
  * We have to choose which memory to evict
    * Different algorithms: least recently used, least frequently used, random

---

## Writing

* We've only handled fetching
* What about writing?
  * Remember, writing is slow too!
* There are different strategies

---

## Write Strategies

* *Write-through*
  * Write immediately to the underlying memory
* *Write-back*
  * Defer writing until the block is evicted
  * This means that we need to add a dirty bit to mark modifications

---

## Write-misses

* What if we write to memory without reading it?
  * We could have a miss!
* More strategies
  * *Write-allocate*
    * Load into cache and update there
  * *No-write-allocate*
    * Same as write through, go directly to memory

---

## Typical Settings

* Write-through + no-write-allocate
* Write-back + Write-allocate
  * These can make better use of locality

---

## Real-World Example

Core i7 Cache

---

## Performance Impacts

<table>
<tr> <hr><td>Cache</td><td>Access Time (cycles)</td><td>Cache Size (C)</td><td> Assoc. (E)</td><td>Block size (B)</td><td>Sets (S)</td></hr></tr>
<tr> <td> L1 i-cache</td><td> 4   </td><td> 32 KB    </td><td> 8 </td><td> 64 B  </td><td> 64 </td></tr>
<tr> <td> L1 d-cache</td><td> 4   </td><td> 32 KB    </td><td> 8 </td><td> 64 B  </td><td> 64 </td></tr>
<tr> <td> L2 unified cache</td><td> 10   </td><td> 256 KB    </td><td> 8 </td><td> 64 B  </td><td> 512 </td></tr>
<tr> <td> L3 unified cache</td><td> 40-75   </td><td> 8 MB    </td><td> 16 </td><td> 64 B  </td><td> 8192 </td></tr>
<tr> <td> Main memory</td><td> 200   </td><td>     </td><td>  </td><td>       </td><td>      </td></tr>
</table>

<p style='font-size:13pt'>$^*$ According to CS:App, Core i7 cache</p>

---

## Cache Types

* A *d-cache* holds data
* An *i-cache* holds instructions
* A *unified cache* holds both
* It makes sense to handle instructions and data differently at the CPU, but less sense farther away

---

## Performance of Block Size

* A small cache is faster, but has a higher miss rate
* Large blocks increase hit rate is spatial locality is true
  * But decrease the number of cache lines
  * This increases misses if data isn't used in that block size
  * Take longer to travel too

---

## Performance of Associativity

* Low associativity can lead to thrashing from conflict misses
* High associativitty is exensive and slow
  * Longer to search the memory
  * More difficult decisions about which memory to evict
* Generally lower associativity closer to the CPU, higher associativity farther away
  * In i7, L1 and L2 are 8-way associative, L3 is 16-way

---

## Write Strategy

* Write-through is simpler
  * Writing can also be shifted to another system, called a write buffer
  * Since the memory is already written, an eviction from a read won't also cause a write, slowing it down farther
* Write-back saves on bandwidth, though
  * Becomes more likely as we move down the hierarchy

---

## Practical Concerns

* A i7 program has a hit rate of 97%
  * Hit time is 4 cycles for L1
  * 10 cycles for L2
  * 200 cycles from main memory
* Average access time with 97% hit: $4 cycles  + 0.03*200cycles = 10 cycles$
* Average access time with 99% hit: $4 cycles  + 0.01*200cycles = 6 cycles$
* So it is better to talk about "miss rate" rather than "hit rate"

---

## Next Time

* More cache details
* Examples of cache friendly code
* Fun topics, but we'll save them for next lecture!

<!--

Pick up from page 650

Cache hit and cache miss

Kinds of cache miss
  * cold misses/compulsory misses
  * conflict miss
  * capacity miss
Cache line, cache set

Replacement policies: random replacement, least recently used

Cache associativity
# lines (of size), # ways, # sets (lines = ways * sets)