Lec 04-22-2025 & 04-29-2025: Intro to Cache; Direct-Mapped Cache Design & Size Calculations | CSCI 343

Cache

Cache is a small amount of memory that is faster than main memory. It sits between normal main memory and the CPU, and may be located on the CPU chip itself or on a separate module.

Cache Operations: Overview

• CPU requests the contents of a memory location
• The cache is checked for this data
• If present, the data is retrieved from cache (fast)
• If not present, the required block is read from main memory into cache
• The data is then delivered from cache to the CPU

Cache includes tags to identify which block of main memory is currently stored in each cache slot.

Why Cache Exists: The Principle of Locality

Main memory is slow compared to the CPU. Cache is a small, fast memory that sits between them and holds copies of recently accessed or likely-to-be-needed data. The idea behind cache is that programs tend to access the same memory locations repeatedly, or locations that are close together. This observation breaks down into two principles:

Temporal Locality: When an instruction is executed or data is accessed, it is stored in the cache because there is a high probability it will be accessed again.

eg. (loop variables)

while (condition) {
    i++; // access variable
} // for 100 iterations, the variable would be referenced again and again

Spatial Locality: When an instruction is executed or data is accessed, nearby items are also loaded into the cache because there’s a high probability they’ll be accessed soon.

eg. Arrays and vectors — if you access arr[0], you’re likely going to access arr[1], arr[2], etc. soon after. Cache takes advantage of this by loading a whole block of consecutive memory (not just the one requested word) on a cache miss.

How Does Hardware Decide What to Cache?

Taking advantage of temporal locality:

• Bring data into cache whenever it’s referenced
• Kick out something that hasn’t been used recently

Taking advantage of spatial locality:

• Bring in a block of contiguous data (a cacheline), not just the requested data

Cache Hits, Misses, and Hit Ratio

Cache Hit: a memory access where the data is already in cache
Cache Miss: a memory access where data isn’t in the cache
Cache block size (or cache line size): the amount of data that gets transferred on a cache miss
Hit ratio: (# of cache hits) / (# of total accesses)
Hit time: the time needed to access the cache
Miss penalty: the time to replace a block from the upper level (cache) with a block from the lower level (main memory)

The hit ratio is a measure of how effectively the cache is being used. A higher hit ratio means fewer accesses of the slower main memory component.

Caches can also be divided by what kind of content they hold:

• Instruction cache (I-cache): a cache that can only hold instructions
• Data cache (D-cache): a cache that can only hold data
• Unified cache: a cache that holds both data and instructions

Consider this sequence of memory block accesses (consider each number as a block number):

$\color{red}{\times}$ indicates a miss.

$\color{blue}{\checkmark}$ indicates a hit.

$$\begin{array}{cccccccc} \color{red}{\times} & \color{red}{\times} & \color{blue}{\checkmark} & \color{blue}{\checkmark} & \color{blue}{\checkmark} & \color{red}{\times} & \color{blue}{\checkmark} & \color{blue}{\checkmark} \\ 5 & 5 & 5 & 5 & 6 & 7 & 6 & 5 \end{array} \;\longrightarrow\; \textbf{Hit ratio: } \frac{5}{8}$$

The first access to block 5 is always a miss (it’s not in cache yet). But the next three accesses to block 5 are hits — this is temporal locality at work. Block 6 is a miss when first accessed, then a hit afterwards. Block 7 is a miss (first time seen). The final access to block 5 is a hit because it was accessed recently enough to still be in cache.

Cache Design

Designing a cache means making decisions along several dimensions:

• Size
• Mapping function
• Replacement algorithm
• Write policy
• Block size
• Number of caches

Data Gets Into Cache via Reads Only

Data enters the cache through read operations only. When you write to memory, you are writing a result you have already computed in the CPU, so there’s no reason to fetch it from memory first. Cache stores data that was read from memory, not data being sent back to it.

This raises a question: when cached data is modified, how does main memory get updated? That’s handled by the write policies:

Write Policies:

• Write-through: Update RAM every time cache is updated. Simpler, but generates more memory traffic.
• Write-back: Delay RAM update until the block is evicted from cache. More efficient, but requires tracking which lines have been modified (using a “dirty bit”).

Cache/Memory Example: $C = A + B$ (read A, read B, write C)

A and B are read into cache so the CPU can operate on them. C is the write result — it goes back to memory (and may or may not update cache depending on the write policy).

What we bring into the cache is based on the principle of locality.

Replacement Policies:

• When cache is full, a line must be replaced
• Most common strategy: Least Recently Used (LRU)

Direct Mapping

For direct Mapping, each block of main memory maps to only one cache line, determined by:

$$\text{cache line index} = \text{(block \#)} \bmod \text{(\# of lines)}$$

This means multiple memory blocks compete for the same cache line. For example, with a 4-line cache (lines 0—3) and 32 memory blocks (0—31):

• Line 0 holds: block 0, 4, 8, 12, 16, 20, …
• Line 1 holds: block 1, 5, 9, 13, 17, 21, …

If block 4 is currently in line 0 and you access block 16, block 4 gets evicted — even if block 4 was still needed. This is a known limitation of direct mapping.

Cache: Direct Mapping Address Structure

Tag and Line Number: Address Breakdown

When a block is loaded into cache, we need to remember which memory block it came from — otherwise we can’t tell on a later access whether we have the right data or stale data from a different block that shares the same cache line.

The straightforward solution would be to store the full block number alongside the data, but that wastes space. Instead, we store only the bits we actually need:

With a 4-line cache, any block number that is a multiple of 4 maps to line 0, any block number that is a (multiple of 4) + 1 maps to line 1, and so on:

Line 0:

Mem block #	block # binary
block 0	$0\ 0\ 0\ {\color{#1f98bc}0\ 0}$
block 4	$0\ 0\ 1\ {\color{#1f98bc}0\ 0}$
block 8	$0\ 1\ 0\ {\color{#1f98bc}0\ 0}$
block 12	$0\ 1\ 1\ {\color{#1f98bc}0\ 0}$
$\vdots$

Line 1:

Mem block #	block # binary
block 1	$0\ 0\ 0\ {\color{#1f98bc}0\ 1}$
block 5	$0\ 0\ 1\ {\color{#1f98bc}0\ 1}$
block 9	$0\ 1\ 0\ {\color{#1f98bc}0\ 1}$
block 13	$0\ 1\ 1\ {\color{#1f98bc}0\ 1}$
$\vdots$

Notice that all blocks in line 0 end in 00, and all blocks in line 1 end in 01. That’s not a coincidence — the last 2 bits are the cache line index (since $\bmod 4$ is just the bottom 2 bits of the number). Because we already know which line we’re looking at, those bottom bits are redundant. We don’t need to store them.

What we do need to store is the remaining top bits — enough to distinguish which of the many blocks mapped to this line is currently stored here. This truncated block number is called the tag.

• Tag = top bits of the block number (unique identifier for which block occupies a line)
• Line number = lower bits (used to index into the cache; derived from the address, not stored)

General Formula

• Address size: $S$ bits (memory size $= 2^S$)
• Cache size: $2^R$ lines (line index size $= R$ bits)
• Tag size $= S - R$

Example:

• Memory has 32 blocks $\implies$ 5-bit address ($S = 5$)
• Cache has 4 lines $\implies$ 2-bit line # ($R = 2$)
• Tag $= 5 - 2 = 3$ bits

Cache Structure

Each cache line contains:

• Valid/Invalid bit (V/I): Indicates if the data is valid
• Tag: Used for identifying the block stored
• Data: The contents of the block

Cache Line Format

$$\underset{\text{1 bit}}{\boxed{\text{V/I}}} \underset{\text{? bits}}{\boxed{\phantom{00} \text{Tag} \phantom{0/}}} \underset{\text{? bits}}{\boxed{\phantom{00} \text{Data} \phantom{0/}}}$$

Tag and data bit width will depend on the system being described.

Adding Word and Byte Fields to the Address

So far we’ve been working with the simplest case: one word per block, word-addressed. In that case, the address breaks down cleanly into just a tag and a line index.

But in real systems, a cache block usually holds multiple words (to take advantage of spatial locality — you bring in a neighborhood of data, not just the one word you asked for). And processors often use byte addressing, meaning an address points to an individual byte rather than a whole word.

These situations can add up to two more fields to the address:

• Word index ($W$ bits): selects which word within a multi-word block you want. If there’s only 1 word per block, this field doesn’t exist.
• Byte offset ($B$ bits): selects which byte within a word. Only present if the system uses byte addressing.

This address is just the ordinary memory address the CPU generates for a memory reference (eg. from a load/store instruction, instruction fetch, etc). A system’s memory address partitioning scheme is influenced by the structure of the CPU’s cache.

For a direct-mapped cache, the full address partitioning is:

$$\overbrace{ \underset{S-R-W-B \text{ bits}}{\boxed{\phantom{0000}\text{Tag}\phantom{000/}}} \underset{R \text{ bits}}{\boxed{\phantom{00}\text{line index}\phantom{0/}}} \underset{W \text{ bits}}{\boxed{\phantom{00}\text{Word Index}\phantom{0/}}} \underset{B \text{ bits}}{\boxed{\phantom{00}\text{Byte Index}\phantom{0/}}} }^{\small\text{Address size } (S \text{ bits})}$$

• $S$ = Total address bits
• $R$ = Bits for line index
• $W$ = Bits for word index (if multiple words per block; if only 1 word per block, we don’t include a partition for the word index)
• $B$ = Bits for byte index (if the system uses byte addressing; otherwise we don’t include this partition for the byte index)

Address Decomposition Scenarios

• Word Addressing, 1 word per block

$$\boxed{\phantom{000}\text{Tag}\phantom{00/}} \boxed{\phantom{0}\text{line index}\phantom{/}}$$

• Word Addressing, multiple words per block

$$\boxed{\phantom{000}\text{Tag}\phantom{00/}} \boxed{\phantom{0}\text{line index}\phantom{/}} \boxed{\phantom{0}\text{word index}\phantom{/}}$$

• Byte Addressing, 1 word per block, word size $= 2^k$ bytes

$$\boxed{\phantom{000}\text{Tag}\phantom{00/}} \boxed{\phantom{0}\text{line index}\phantom{/}} \boxed{\phantom{0}\text{byte offset ($k$ bits)}\phantom{/}}$$

• Byte Addressing, multiple words per block

$$\boxed{\phantom{000}\text{Tag}\phantom{00/}} \boxed{\phantom{0}\text{line index}\phantom{/}} \boxed{\phantom{0}\text{word index}\phantom{/}} \boxed{\phantom{0}\text{byte offset}\phantom{/}}$$

Example of a cache with multiple words per block and byte addressing:

Cache Initialization and Context Switching

• On program startup: all cache lines are marked invalid
• On context switch:
  • Previous process’s cache data becomes irrelevant
  • All cache lines are again marked invalid
• Valid bit is set to 1 only when new block data is loaded

Total Cache Size Calculation

$$\text{Total cache size} = \text{\# of lines} \times (1 + \text{Tag bits} + \text{Block size as bits})$$

Example:

We wish to find the total # of bytes for a direct mapping cache to store 64 KB in 1-word blocks, assuming a word size of 32 bits and MIPS addressing.

Solution:

Break down the specifications:

• Word size $= 32$ bits
• Block size $= 1$ word
• Addressing mode: byte addressing (from what we know of MIPS)
• Data: 64 KB

Note

$b$ = bits
$B$ = bytes

Block size is only 1 word, so we don’t need to allocate any bits for word select.

MIPS uses byte addressing, so we need to allocate bits for addressing the byte # in a word.

The word size is 32 bits which implies a 32-bit address size.

So the address structure should be:

$$\overbrace{ \boxed{\phantom{000}\text{Tag}\phantom{00/}} \boxed{\phantom{0}\text{line \#}\phantom{/}} \boxed{\phantom{0}\text{byte \#}\phantom{/}} }^{\small 32 \text{ bits}}$$

Now we compute the bit width of each partition:

$$\begin{aligned} \text{Word size} & = 32 \text{ bits} \\ & = 4 \text{ B} \\ & = 2^2 \text{ B} \implies \text{Allocate } 2 \text{ bits for addressing byte \# (byte addressing)} \end{aligned}$$

 

$$\begin{aligned} \text{Data} &= 64 \text{ KB} \\ &= 2^6 \times 1 \text{ KB} \\ &= 2^6 \times 2^{10} \text{ B} \\ &= 2^{16} \text{ B} \end{aligned}$$

With direct mapping, there is exactly one cache line per block of data — each line holds exactly one block. So the number of lines equals the number of blocks that fit in the cache’s data capacity:

$$\begin{aligned} \text{\# of lines} &= \frac{\text{Data size}}{\text{block size}} \\[1em] &= \frac{2^{16} \text{ B}}{2^2 \text{ B}} \\[1em] &= 2^{14} \text{ lines} \implies \text{ Allocate } 14 \text{ bits for line \#} \end{aligned}$$

 

Since 2 bits for byte # and 14 bits for line # are already taking up part of the 32 bits of the address size:

$$\text{Tag} = 32 - (14 + 2) = 16 \text{ bits}$$

Address Structure:

$$\underset{16\ b}{\boxed{\phantom{000}\text{Tag}\phantom{000}}} \underset{14\ b}{\boxed{\phantom{0}\text{line \#}\phantom{0}}} \underset{2\ b}{\boxed{\phantom{0}\text{byte \#}\phantom{0}}}$$

Since we know generally that the cache line format looks like this:

$$\underset{\text{1 bit}}{\boxed{\text{V/I} }} \underset{\text{? bits}}{\boxed{\phantom{00} \text{Tag} \phantom{0/}}} \underset{\text{? bits}}{\boxed{\phantom{00} \text{Data} \phantom{0/}}}$$

Then the overall cache structure should follow, given that we now know the bit width for Tag and Data (which is the block size).

Cache Structure:

Each line is $1 + 16 + 32 = 49$ bits.

Total cache size:

$$\begin{aligned} 2^{14} \text{ lines} \ \times \ 49 \text{ bits/line} \ &= 49 \cdot 2^{14} \text{ b} \\ & = 49 \cdot 2^{11} \text{ B} \\ & = 49 \cdot 2 \text{ KB} \\ & = 98 \text{ KB} \end{aligned}$$