Memory Hierarchy and Caches

A cache works because the next memory access is often related to a recent one. During a short interval, most programs use only a small part of their address space. This pattern is locality. A cache keeps that active part close to the processor, where it can serve accesses quickly.

Reuse in time and space

Temporal locality means reusing an item soon after accessing it. A loop repeatedly fetches its body instructions. A running total is read and updated many times. Keeping those items available avoids fetching them again from a slower level.

Spatial locality means accessing items at nearby addresses. An array scan reads adjacent elements, and straight-line code fetches successive instructions. A cache exploits this by fetching an entire block, also called a cache line, on a miss. Nearby bytes arrive before the program asks for them.

These patterns can occur together. A loop's instructions are adjacent and run repeatedly, so the instruction stream has both spatial and temporal locality. An array element read exactly once has no temporal reuse, even though the surrounding array scan has spatial locality.

Count blocks in an array scan

Consider this C loop with 4-byte integers and 64-byte cache blocks:

for (int i = 0; i < 1000; i++) {
    sum += a[i];
}

A block holds $64\mathrm{/}4=16$ integers. The array occupies $1000\times 4=4000$ bytes. If its first element is block aligned, the scan touches $\lceil 4000\mathrm{/}64\rceil =63$ blocks: 62 full blocks and one partial block.

In a cold cache without prefetching or interference, the first access to each block misses. The remaining elements in that block hit. Thus the array causes 63 misses in 1000 accesses, or about 6.3%. Counting one miss per element would overlook all the useful neighboring data fetched with each miss.

The source variables sum and i are reused frequently. A compiler usually keeps them in registers, however, so their source-level reuse need not produce data-cache accesses. Analyze the memory accesses executed by the compiled program when estimating cache traffic.

The working set must fit and coexist

The working set is the collection of blocks used during a chosen time window. If they fit in the cache and the placement rules allow them to coexist, repeated accesses mostly hit after the initial loads. The time window matters: a whole program can be huge while one active loop uses only a few blocks.

Capacity alone is insufficient. Two busy blocks can map to one direct-mapped entry and evict each other while other entries remain empty. A working set can therefore fit by byte count yet fail to stay cached.

Scattered linked-list nodes and random probes of a large hash table often have poor spatial locality. A column walk through a row-major array also skips over many nearby elements. These patterns bring in bytes that may go unused before eviction. Hardware exploits the locality supplied by the access pattern; changing the program's layout or traversal can make more of each fetched block useful.

Memory technologies trade speed against density, cost, and persistence. The processor needs quick access to a small amount of data and affordable space for much more. SRAM, DRAM, and flash meet different parts of that need.

Compare the cells

An SRAM cell is fast but occupies substantial area, making SRAM relatively expensive per bit. DRAM cells are smaller, so DRAM provides more capacity at a lower cost per bit. Their charge leaks away. Refresh reads and restores rows within a fixed window; normal-temperature DDR4 uses a 64 ms window. “Static” in SRAM means no refresh, not persistence after power loss.

Why DRAM access time varies

DRAM is organized into banks, with rows and columns in each bank. Activating a row copies it into a row buffer. Reads and writes then select columns from that open row. To open a different row in the same bank, the bank must first be precharged. An access to an already open row avoids that row-switching work.

Consecutive columns can be transferred in a burst, which suits fetching a cache block. Distributing requests across banks and channels lets transfers overlap. DDR memory transfers on both clock edges. These features increase the rate of data delivery without eliminating the wait for the first data.

Separate latency from bandwidth

Latency is the delay until the first data arrives. Bandwidth is the amount transferred per unit time. A high-bandwidth interface can still have a long initial delay.

For example, a DDR5-4800 channel with an aggregate 64-bit data path carries 8 bytes per transfer. Its peak rate is $4800\times {10}^6\times 8=38.4\times {10}^9$ bytes/s, or 38.4 GB/s. Sustained application bandwidth can be lower because commands, row changes, and other work consume time.

If a request waits 60 ns and then receives a 64-byte block at 16 GB/s, the transfer rate is 16 bytes/ns. Transfer takes $64\mathrm{/}16=4$ ns, giving about 64 ns altogether. Improving only bandwidth reduces the 4 ns part, not the initial 60 ns.

Flash keeps data but handles writes differently

NAND flash reads and programs pages of several KiB. Reusing a programmed page requires erasing its larger erase block, which contains many pages. Page reads typically take tens of microseconds, programming hundreds of microseconds to a few milliseconds, and erasing milliseconds.

Program/erase cycles wear cells out. Dense multi-bit flash often supports a few thousand cycles, while single-bit cells can support around 100,000. Controllers use wear leveling to spread writes across blocks.

For scale, SRAM access is roughly 1 ns, DRAM roughly 50–100 ns, NAND reads roughly 25–100 µs, and disk access roughly 5–10 ms. Actual devices vary. The hierarchy combines these technologies because a single one cannot provide their speed, capacity, and price advantages together.

The memory hierarchy places small, fast storage near the processor and progressively larger storage farther away. Locality lets the small levels serve a large fraction of requests, while the lower levels supply capacity.

Levels and transfer units

A typical path is registers, L1, L2, L3, main memory, and storage. L1 commonly has separate instruction and data caches of around 32–64 KiB each per core. L2 is often hundreds of KiB to a few MiB per core, while L3 is often shared and holds several to tens of MiB. Main memory holds many GiB, and storage holds hundreds of GB or more. Designs differ in size and sharing.

On a processor near 3 GHz, representative load latencies are about 4–5 cycles for L1, 12–15 for L2, 30–50 for L3, and 200–300 for DRAM. An L1 may accept a new request each cycle even when one request needs several cycles to complete: throughput and latency describe different properties.

Data travels through caches in blocks, commonly 64 bytes. Virtual memory uses pages, commonly 4 KiB, when moving page contents between memory and storage. A cache line and a page serve similar grouping purposes at different scales; they are not the same transfer unit.

Hits, misses, and timing

A hit means a level contains the requested data. A miss means it must obtain the data from below. Both words refer to the level being checked: an L1 miss can still be an L2 hit.

The hit rate is hits divided by accesses, and the miss rate is one minus the hit rate. Hit time includes checking the level and deciding whether the request hits. The miss penalty is the additional time needed on a miss to obtain and deliver the block.

Suppose a simplified cache has a 1-cycle hit time, a 97% hit rate, and a 100-cycle extra miss penalty. Every access pays 1 cycle, while 3% pay another 100:

A miss takes 101 cycles in this example. Using 100 as the complete miss time would charge the hit lookup inconsistently. Even a high hit rate leaves expensive misses visible in the average.

Who manages each level?

The compiler assigns suitable values to registers. Cache hardware moves blocks automatically as loads, stores, and instruction fetches run. Programs name addresses; they do not select cache entries. The operating system manages virtual-memory mappings with hardware support and handles pages that must be brought into main memory.

Splitting L1 instructions from data allows a pipeline to fetch an instruction and access data together without competing for one cache port. Lower caches are usually unified, storing both instruction and data blocks.

Some hierarchies are inclusive: a block present above also has a copy below. Others are exclusive or non-inclusive, so a copy in every lower cache is not guaranteed. Draw a hierarchy as a search and transfer path, not a promise that all levels contain identical subsets.

Making L1 larger can reduce misses but increase access delay and energy. Adding larger lower caches allows the design to keep L1 fast while rescuing many of its misses before DRAM. Evaluate that trade-off with access time, not capacity alone.

A byte address identifies one byte in memory. A cache fetches a whole block, so lookup first identifies that block and then selects the requested bytes within it. In a direct-mapped cache, each block has exactly one possible entry.

Divide the address by purpose

For a block size of $2^b$ bytes, the low $b$ address bits form the offset. Dividing the byte address by the block size and discarding the remainder gives the block address. The remainder is the offset.

If the cache has $E$ entries, the entry index is

With a power-of-two entry count, the index is the group of address bits immediately above the offset. The remaining high bits form the tag, which tells the cache which of the many blocks sharing an index is present.

The field order from high bits to low bits is tag | index | offset. For an address width of $A$ bits:

Use the number of entries for the index calculation. Taking the logarithm of capacity in bytes would count the offset bits a second time.

Work a 16 KiB example

A 16 KiB direct-mapped cache with 64-byte blocks has $16384\mathrm{/}64=256$ entries. The offset takes 6 bits, the index 8 bits, and the tag $32-8-6=18$ bits for 32-bit addresses.

For byte address 0x1234ABCD, the low 6 bits give offset 13, or 0x0D. Removing those bits gives block address 0x48D2AF. Its low 8 bits are 0xAF, so the index is 175. The remaining bits give tag 0x48D2.

The byte address can be reconstructed from these fields: concatenate the tag, the 8-bit index, and the 6-bit offset. Field widths matter because a hexadecimal digit represents 4 bits; the boundaries need not fall between hex digits.

A matching tag needs a valid entry

Each entry stores data, a tag, and a valid bit. The index selects the entry. A hit requires both a set valid bit and equality between its stored tag and the requested tag. At startup, an entry can contain arbitrary bits; the valid bit prevents those bits from being mistaken for a loaded block.

Once the block is present, accesses to other bytes in that block hit too. A hit does not require the identical byte address used to fetch the block.

Count metadata separately

Quoted cache capacity normally counts data only. Here each entry contains 512 data bits, 18 tag bits, and 1 valid bit, or 531 bits. Total storage is

The data alone uses 131072 bits. Tags and validity add 4864 bits, about 3.7% of data storage. A write-back design also needs dirty bits; more complex designs need further control state.

The index uses low block-address bits so successive blocks spread across successive entries. A wider address leaves offset and index widths unchanged when capacity and block size stay fixed; the extra bits extend the tag.

A cache trace records how each access changes the stored blocks. Keep a separate state for each entry, and update that state immediately after every miss. The next request uses the updated cache, not the cache as it looked at the beginning.

Set up the trace

Take a 64-byte direct-mapped cache with four 16-byte entries. It starts empty. For each byte address, divide by 16 to find the block, then compute block modulo 4 for the index. The tag is the block number divided by 4, with its fractional part discarded. There are 4 offset bits and 2 index bits.

On a read, inspect the selected entry. If it is valid and the tag matches, record a hit. Otherwise record a miss, replace that entry's block and tag, and set its valid bit. No replacement choice is available in a direct-mapped cache.

Follow all eight accesses

The first access fills entry 0 with block 0. The next address, 0x04, is still inside that 16-byte block, so it hits despite naming a different byte. 0x40 belongs to block 4. It has the same index as block 0 but a different tag, so it replaces block 0.

The second 0x00 therefore misses. Earlier use alone cannot guarantee a hit: the block must still be present. The request to 0x14 loads block 1 into entry 1, leaving entry 0 unchanged.

Next, 0x44 loads block 4 into entry 0 again. 0x08 needs block 0 and evicts block 4. Finally, 0x84 loads block 8 into that same entry. At the end, entry 0 holds block 8 and entry 1 holds block 1; entries 2 and 3 remain invalid.

Interpret the behavior

There is one hit and seven misses, so the hit rate is $1\mathrm{/}8=12.5\mathrm{\%}$. Blocks 0, 4, and 8 compete for entry 0. The cache has four entries, yet this access pattern uses only two of them. The repeated evictions are caused by mapping conflicts, not a shortage of total storage for the four distinct blocks.

A block fill makes all of that block's bytes available. In a sequential scan, one miss can therefore serve many following elements. Here the conflicting accesses repeatedly remove that benefit before the next nearby byte is requested.

For reliable tracing, label byte addresses and block numbers explicitly. Applying modulo 4 directly to the byte address skips the division by block size and sends requests to the wrong entries. Record the replacement even when the new block has been loaded before: every miss installs the requested block and its tag in the selected entry.

A set-associative cache gives a block several possible entries without searching the entire cache. The index selects a set, and the block can occupy any way in that set. This reduces conflicts between blocks that share an index.

Compute sets and fields

For data capacity $C$, block size $B$, and associativity $n$:

The set index is block address modulo the number of sets. The offset still depends only on block size. The tag contains the remaining high bits.

A 32 KiB, 8-way cache with 64-byte blocks has 512 blocks and 64 sets. With 32-bit addresses, its offset, index, and tag widths are 6, 6, and 20 bits. Address 0x1234ABCD has offset 13, set 47, and tag 0x1234A.

At fixed capacity and block size, doubling associativity halves the number of sets. One index bit becomes a tag bit; no data capacity is added.

Lookup compares the tag with all valid tags in the chosen set in parallel. A matching way supplies the data through a selector. More ways require more comparisons and selection hardware, which can increase hit time and energy.

Replace a block only when the set is full

Use an invalid way first. When every way is occupied, LRU, or least recently used, evicts the block whose most recent access is oldest. Update recency on hits as well as fills. A 2-way set needs only one bit to track its LRU way; larger sets often use pseudo-LRU approximations.

FIFO evicts the block loaded earliest, even if it was recently accessed. Random replacement chooses a victim without maintaining full recency information. It is simple and can perform close to LRU in large caches.

Revisit the small trace with two ways

The 64-byte cache with 16-byte blocks now has two sets of two ways. Blocks 0, 4, and 8 map to set 0, while block 1 maps to set 1. For 0x00, 0x04, 0x40, 0x00, 0x14, 0x44, 0x08, 0x84, the results are miss, hit, miss, hit, miss, hit, hit, miss.

Blocks 0 and 4 can coexist, so their repeated accesses hit. Just before the last access, block 0 was used more recently than block 4. Loading block 8 evicts block 4 under LRU. Four of eight accesses hit, compared with one in the direct-mapped version.

Associativity cannot remove compulsory misses or make a working set larger than capacity fit. It also cannot prevent conflicts when more than n busy blocks compete for one n-way set. A repeating cycle of n+1 such blocks can make LRU miss every time. Padding arrays can change their set mappings; choosing more ways is only one possible response to a conflict problem.

A cache miss is an event with both a mechanism and a cause. The mechanism describes how the request is served. The cause explains why the needed block was absent and which design change might help.

Handle a read miss

In a simple in-order pipeline, the cache detects an invalid entry or a tag mismatch, and the processor stalls. The cache requests the block from the next level. If the chosen victim is dirty, its changed data must be preserved by writing it back. The arriving block is installed with its tag and valid bit, and the waiting access completes. An instruction-cache miss similarly waits for the instruction's block and then fetches the instruction again.

Critical word first requests the needed word first in the returning block. Early restart lets execution resume as soon as that word arrives. A nonblocking cache can serve other hits and track outstanding misses while an out-of-order processor does independent work. These mechanisms reduce waiting; they do not make the original data dependency disappear.

Use the three Cs

Apply the first-access test first. A block's first access is compulsory even if its destination entry is already occupied. For later misses, compare the actual cache with a fully associative LRU cache of equal data capacity and block size, both receiving the same access history.

In the earlier four-entry trace, blocks 0, 4, 1, and 8 each cause one compulsory miss. The direct-mapped cache also misses on the repeated accesses to blocks 0 and 4. A four-entry fully associative cache can retain all four distinct blocks, so those three repeat misses are conflicts. There are no capacity misses.

Choose a change that addresses the cause

Increasing capacity can retain a larger working set. Increasing associativity can let conflicting blocks coexist. Increasing block size can exploit spatial locality by bringing in more useful neighbors with each fill.

Block size has competing effects. At fixed data capacity, larger blocks mean fewer resident blocks. Unused bytes consume cache space, unrelated useful blocks can be displaced, and each transfer can take longer. Miss rate often falls initially as block size grows, then rises when these costs outweigh useful spatial locality.

A larger cache can also have a longer lookup, and additional ways require more comparison hardware. Judge changes through average access time, including hit time and miss penalty, instead of assuming that a lower miss rate guarantees a faster design.

In multicore systems, invalidation after another core writes can cause coherence misses. Prefetching can bring a first-use block in before its demand access, hiding a demand miss that additional capacity alone cannot avoid.

A store changes a value, so the hierarchy needs a rule for passing that change downward. Two separate choices are involved: what to do when a store hits, and what to do when it misses.

Write-through and write-back

A dirty bit records that a write-back block contains changes not yet written to the next level. A clean victim needs no write-back. A dirty victim must have its changed data preserved before its entry can be reused. The processor's loads obtain the new value from the cache even while the lower copy is older.

For 100 stores to one cached 4-byte variable, unmerged write-through sends 100 writes, or 400 bytes of data payload. Write-back can combine those changes into one 64-byte block write on eviction. This comparison counts update payload, excluding the initial fill and protocol overhead.

The benefit depends on reuse. Repeated writes to one block give write-back a chance to combine updates; writes scattered across many blocks may lead to many dirty evictions. Lower caches commonly use write-back to limit traffic toward DRAM. L1 data caches can use either policy.

A write buffer hides waiting, not traffic

A write buffer queues pending lower-level writes. Under write-through, the processor can proceed once a store has entered the buffer instead of waiting for the lower memory to finish. The lower level catches up as buffered stores drain; it can temporarily lag behind the cached value.

The buffer has finite capacity. If stores arrive faster than the lower level accepts them for long enough, it fills and the processor stalls. A buffer changes when the processor waits, not the sustainable bandwidth of the destination.

Without buffering or overlap, if 10% of instructions store and every store adds 100 wait cycles, a base CPI of 1 becomes $1+0.1\times 100=11$. Buffering can hide much of this delay when the destination keeps up on average.

Treat a write miss separately

Write-allocate fetches the missing block into the cache and then applies the store. It pairs naturally with write-back because later accesses and writes can reuse that block. No-write-allocate, also called write-around, sends the store downward without filling this cache. It pairs naturally with write-through and can avoid displacing useful blocks during a one-time output stream.

These are independent policy choices. Knowing that a cache is write-through does not by itself tell you whether a write miss allocates a line; a trace must specify both policies.

A write-back miss that selects a dirty victim involves outgoing data as well as the incoming fill, raising the penalty unless buffers or overlap hide part of the work. Other cores and I/O devices also need a consistent view when lower memory is stale. Coherence and system mechanisms coordinate that visibility; a dirty bit alone only records pending changes.

A high hit rate is useful, but it is not a complete performance measure. A small number of expensive misses can dominate the average, and a design that avoids more misses can still lose if its lookup becomes too slow.

Start with rates and timing definitions

The two fractions sum to one. Convert percentages to fractions before multiplying: 5% is 0.05.

Average memory access time, or AMAT, is

Every request checks the cache, including requests that miss. The penalty is the extra delay after that lookup. Equivalently, weight hit time by the hit fraction and total miss time by the miss fraction; expanding gives the same formula.

With a 1-cycle hit time, 5% misses, and a 100-cycle additional penalty, AMAT is $1+0.05\times 100=6$ cycles. At 2 GHz, each cycle lasts 0.5 ns, so this is 3 ns. Do all arithmetic in cycles or all in time, then convert the final result if needed.

Compare complete designs

Cache A has a 1.0 ns lookup and 5% misses. Cache B has a 1.2 ns lookup and 3.5% misses. With a 50 ns penalty:

B wins because avoiding expensive misses more than repays its slower lookup. If the penalty falls to 10 ns, A takes 1.5 ns and B takes 1.55 ns. Now A wins. A miss-rate improvement has value in proportion to the penalty it avoids.

Weight instruction and data accesses correctly

Suppose each instruction produces one instruction fetch and 0.3 data accesses on average. The instruction miss rate is 2%, and the data miss rate is 4%. In 100 instructions, there are 100 fetches and 30 data accesses. Expected misses are $100\times 0.02+30\times 0.04=3.2$ out of 130 accesses.

The combined miss fraction is therefore $\frac{0.02+0.3\times 0.04}{1.3}\mathrm{.}$ With equal 1-cycle hit times and 100-cycle penalties, AMAT is about 3.46 cycles per memory access. Averaging 2% and 4% directly would wrongly give the two access types equal weight.

Estimate a transfer penalty

A block request can include initial latency followed by transfer time. With 60 ns latency, a 64-byte line, and 16 GB/s bandwidth, transfer takes 4 ns, making the additional penalty about 64 ns. At 3 GHz, there are 3 cycles/ns, so that is 192 cycles.

Check what a problem's timing includes. If it gives a complete miss access time, subtract the hit lookup before treating that number as an additional miss penalty. Charging the lookup twice overstates AMAT.

AMAT measures time per memory access. CPI measures cycles per executed instruction. To connect them, count how many instruction and data requests each instruction produces and how many stall cycles those requests add.

Add the stall terms

For a simple in-order processor whose cache hits are included in the base CPI, a nonoverlapped miss adds its extra penalty. With instruction miss rate $m_I$, data accesses per instruction $f_D$, data miss rate $m_D$, and penalty $P$ in cycles:

Every instruction has one instruction-fetch request in this model. Only loads and stores make data requests, so multiply their miss rate by their frequency. If their penalties differ, use a separate penalty in each term.

Work from requests to stalls

Let base CPI be 1.0, instruction miss rate 2%, load/store frequency 30%, data miss rate 4%, and miss penalty 100 cycles. Instruction stalls are $0.02\times 100=2.0$ cycles per instruction. Data stalls are $0.3\times 0.04\times 100=1.2$. Total CPI is 4.2.

With a perfect cache, CPI would return to 1.0. At the same clock and instruction count, that would be a 4.2-fold speedup. The data miss rate is twice the instruction miss rate, yet instruction misses cost more total time because every instruction is fetched and only 30% access data.

Do not insert AMAT directly as CPI. AMAT is per access, and it includes the hit service time. The CPI calculation here adds only stalls beyond the base execution already counted.

A faster clock makes each memory wait cost more cycles

DRAM latency in nanoseconds does not shrink when the processor clock increases. Doubling the clock converts the same 100-cycle memory wait into 200 cycles at the new clock. The example's CPI becomes

Each new cycle is half as long, so relative execution time changes from 4.2 old cycles per instruction to the equivalent of 3.7 old cycles. Speedup is $4.2\mathrm{/}3.7\approx 1.14$, far below two.

Improvements shift the bottleneck

If the base CPI drops from 1.0 to 0.5 while memory stalls remain 3.2, total CPI becomes 3.7. Stalls now consume $3.2\mathrm{/}3.7\approx 86\mathrm{\%}$ of cycles. Improving the core makes the unchanged memory delay a larger share of runtime, an example of Amdahl's law.

The simple model counts all miss delays as stalls. Out-of-order execution and nonblocking caches can overlap misses with useful work or other misses. Hardware counters and runtime measurements are needed to assess that overlap on a real machine. When comparing designs with this model, keep the same instruction stream and state which delays are already included in the base CPI.

A lower cache reduces the penalty paid when L1 misses. It has its own lookup time and miss rate, so the hierarchy's expected cost must follow the fraction of requests that reaches each level.

Keep the denominator with the rate

A level's local miss rate is its misses divided by requests to that level. Its global miss rate is its misses divided by all processor memory requests.

If L1 misses 4% of the time and L2 misses on 25% of those requests, only $0.04\times 0.25=0.01$, or 1% of original requests, reach memory. A 25% local L2 miss rate says nothing by itself about the fraction of all requests reaching memory: L1 filtered the stream first.

For two sequentially checked levels:

Here $H_1$ and $H_2$ are lookup times, $m_1$ and $m_2$ are local miss fractions, and $P$ is the additional memory penalty. Only L1 misses pay the L2 lookup. Only misses in both levels pay the memory penalty.

Evaluate from the inside outward

Use L1 hit time 1 cycle, L1 miss rate 4%, L2 hit time 12 cycles, local L2 miss rate 25%, and memory penalty 200 cycles. A request that reaches L2 takes an average of $12+0.25\times 200=62$ extra cycles. Thus

Without L2, AMAT would be $1+0.04\times 200=9$ cycles. The L2 lookup adds work to each L1 miss but prevents most of those requests from paying the much larger memory delay.

Do not substitute the 1% global L2 miss rate for $m_2$ inside the parentheses. That would multiply by the L1 miss fraction twice. An equivalent expanded form uses the global rate directly:

Add L3 using the same logic

With L3 hit time 40 cycles and local miss rate 40%, the L3 service term is $40+0.4\times 200=120$ cycles. The L2 term becomes $12+0.25\times 120=42$ cycles. Overall AMAT is $1+0.04\times 42=2.68$ cycles.

The full expression is $H_1+m_1(H_2+m_2(H_3+m_{3}P))\mathrm{.}$ L3 is charged only to requests that miss both upper levels. A level with a very slow lookup or very few hits can add more delay than it saves.

Use rates per instruction for CPI

Suppose base CPI is 1, L1 produces 0.032 misses per instruction, and memory adds 100 cycles. With no L2, CPI is $1+0.032\times 100=4.2$. Add a 10-cycle L2 whose local miss rate is 25%:

At the same clock, speedup is $4.2\mathrm{/}2.12\approx 1.98$. The 0.032 figure is already misses per instruction, so another access-frequency multiplier would count that frequency twice.

Virtual memory separates the addresses a program uses from the locations holding its data in main memory. Each process gets its own virtual address space. Hardware translates addresses using operating-system mappings and checks whether each requested access is permitted.

Replace the page number, preserve the offset

A page is a fixed-size region of virtual addresses. A page frame is a page-sized slot in physical memory. With 4 KiB pages, each page contains 4096 bytes, so the page offset needs 12 bits. The remaining high virtual-address bits form the virtual page number, or VPN.

A page table entry, or PTE, maps a VPN to a physical page number, or PPN. Translation replaces the page number but preserves the offset: the same byte position is selected inside the physical frame.

For virtual address 0x00403A7C, the low 12 bits give offset 0xA7C, and the VPN is 0x00403. If that VPN maps to PPN 0x02F1C, the physical address is 0x02F1CA7C. Appending a 12-bit offset is equivalent to multiplying the PPN by 4096 and adding the offset; adding the unshifted PPN would give the wrong address.

A mapping includes permissions

A PTE records validity, a physical page number, and permissions such as read, write, execute, and user access. Accessed and dirty bits record use and modification. A privileged processor register identifies the page table; RISC-V uses satp. User programs cannot freely rewrite these mappings.

Separate page tables let the same virtual address refer to different physical data in different processes. They also allow selected sharing: two processes can map virtual pages to the same physical frame, for example to share read-only library code. Isolation and sharing are both consequences of controlled mappings.

A page fault needs operating-system attention

A page fault is an exception raised when translation or its permission checks cannot complete normally. A store to a read-only mapping can fault even if the page is already in memory.

When a needed page is absent from main memory, the operating system obtains a physical frame, reads the page from storage, updates the mapping, and restarts the instruction. A modified victim page may first need a write-back. Some faults are resolved without storage, such as setting up a mapping to an existing page or handling copy-on-write. An access the system cannot permit can instead end in a process error.

Storage-backed faults are expensive. At 3 GHz, a 50 µs delay costs 150000 cycles, and 1 ms costs 3000000. Large pages spread transfer costs across many bytes. A virtual page can occupy any suitable frame, and dirty pages use write-back because forwarding every store to storage would be too slow.

Page tables also consume memory

A flat table for 32-bit virtual addresses and 4 KiB pages needs $2^{32-12}=2^{20}$ entries. At 4 bytes per entry, that is 4 MiB per process. Real designs use multi-level tables to avoid allocating one huge flat table for sparse address spaces; RISC-V Sv39 uses three levels.

Virtual memory includes address translation, protection, and sharing even when every used page fits in DRAM. Storage-backed paging is one use of that machinery, not its whole purpose.

Address translation can require several page-table reads before a data access proceeds. Page-table entries can hit in ordinary caches, but those reads still add work. The translation lookaside buffer, or TLB, caches recently used translations so most accesses can avoid a page-table walk.

Follow an allowed access

The virtual page number is looked up in the TLB. A matching entry supplies the physical page number and permission information. After permission checks, the physical address identifies the data in the cache hierarchy.

On a TLB miss, a page-table walk obtains the translation. If the mapping is valid and permits the request, the translation is installed in the TLB and the access continues. RISC-V and x86-64 normally use hardware walkers; some architectures use software handlers. If the mapping cannot serve the request, the processor raises a page fault for the operating system.

A TLB miss can therefore accompany either a data-cache hit or a data-cache miss. It says that the translation was absent from the TLB, not that the page was absent from DRAM. Conversely, a TLB hit can accompany a cache miss, or a permission fault for a prohibited access. Translation and data residency answer different questions.

Count the memory covered by translations

TLB reach is entries multiplied by page size. A 64-entry TLB with 4 KiB pages covers 256 KiB at once. With 2 MiB pages, 64 entries cover 128 MiB. Accessing many different pages can exhaust translation capacity even when only a few bytes of each page are used.

First-level TLBs often contain tens of entries; lower TLB levels can contain hundreds or thousands. Their entries include page-number tags, physical mappings, permissions, and often address-space identifiers. Locality within pages and reuse across nearby accesses keep translation hit rates high.

For example, if 1% of accesses require a 30-cycle walk and TLB-hit time is otherwise hidden, walks add $0.01\times 30=0.3$ cycles per access on average. This example assumes the walks complete normally and excludes page-fault service.

Overlap indexing with translation

A physically indexed, physically tagged cache waits for a physical address before selecting its set. A virtually indexed, physically tagged cache, or VIPT cache, starts reading a set while the TLB translates, then compares physical tags.

The simple VIPT design takes all index and block-offset bits from the page offset, because translation preserves those bits. This requires

With 4 KiB pages, a 32 KiB 8-way cache has 4 KiB per way and fits. A 48 KiB 12-way cache also fits. A 64 KiB 8-way cache has 8 KiB per way and needs a page-number bit for indexing, so it requires more ways or additional handling.

Keep cached mappings current

Translations belong to address spaces. A context switch can flush old entries or distinguish them with address-space identifiers, or ASIDs. Changes to mappings require the corresponding translation-cache maintenance; RISC-V provides sfence.vma. When a page is evicted from memory, its old translation must not remain usable in the TLB. The TLB holds mappings and access rights, while ordinary caches hold the program's data and instructions.

Cache-aware code makes fetched bytes useful before their block is evicted. Start with the addresses generated by the inner loop. Then ask which data is reused, how far apart accesses are, and whether those blocks can coexist in the cache.

Traverse arrays in storage order

C and C++ store rectangular arrays in row-major order. Adjacent columns of one row are adjacent in memory. Fortran, MATLAB, and Julia use column-major order; NumPy arrays default to row-major order. The efficient inner traversal follows the actual layout.

A C array double a[1024][1024] occupies 8 MiB. Each row takes 8192 bytes. With 64-byte cache lines, each line holds eight doubles. A row walk can use all eight before moving on, giving roughly one cold miss per eight accesses in a simple demand-fetch model.

A column walk steps 8192 bytes between consecutive accesses. It touches 1024 distinct lines before revisiting nearby data in the next column. Those lines occupy 64 KiB, exceeding a 32 KiB L1. They also conflict: in a 64-set cache, a stride of 128 lines preserves the set index. An 8-way set cannot hold 1024 competing lines.

Padding a row to 1032 doubles makes its stride 8256 bytes, or 129 lines. Successive rows then advance by one set modulo 64, spreading the requests. Padding addresses mapping conflicts; the amount of data still matters.

Interchange loops when the result is preserved

Loop interchange changes which loop runs inside another. For row-major matrix multiplication, the i, j, k order streams a row of A but a column of B. In a large streaming model with little reuse between passes, this costs about $1\mathrm{/}8+1=1.125$ misses per inner iteration.

With i, k, j, the inner loop streams rows of B and C, while one A element is reused. Counting a fresh stream for both rows gives about $1\mathrm{/}8+1\mathrm{/}8=0.25$ misses per iteration, 4.5 times fewer. If the repeatedly updated row of C stays resident, the count approaches 0.125. Cache capacity and conflicts decide which reuse survives.

Interchange must preserve required computation behavior. Dependencies, overlapping pointers, and floating-point evaluation order can constrain transformations; compilers need proof that a change is allowed.

Fetch the fields you use

An array of structures groups all fields of one object. A structure of arrays groups one field across objects. If a particle record holds eight doubles in one 64-byte line, summing only x across one million aligned records fetches about 64 MB. A separate contiguous x array fetches about 8 MB, using every double brought in. Code using every particle field together may favor the original structure layout.

Linked nodes can be scattered, and each next address may depend on a pointer just loaded. Contiguous arrays or node pools can improve locality. Compact hot fields also let more active data fit within each level.

Measure runtime and relevant hardware counters before and after a change. Cache misses can explain a slow loop, but computation, bandwidth, or branches may be the limiting factor. Keep the input and results comparable so a speed difference reflects the change being evaluated.

Loop interchange improves access order. Blocking, also called tiling, goes further by keeping a small region of data active until its useful reuse is complete. Prefetching moves a future transfer earlier so its delay overlaps useful work.

Keep a group of tiles resident

In blocked multiplication of square matrices, one tile of A and one tile of B contribute to one tile of C. A tile of side $b$ contains $b^2$ elements. Working repeatedly on these small tiles reuses data before moving to the next region.

For 8-byte doubles, three tiles require $3b^2\times 8=24b^2$ bytes. In a 32 KiB cache, the capacity limit is

Choosing a side of 32 uses 24576 bytes, or 24 KiB, leaving some space for other data. Choosing 36 merely because the arithmetic permits it leaves much less room and can expose conflicts. Capacity is a starting estimate; actual tile sizes are tuned by measurement.

A blocked traversal steps the outer loop by the tile size. Its inner bounds stop at the smaller of the tile end and matrix size. For example, if a dimension is 70 and tiles have side 32, the final tile has only six elements along that dimension. A full-size final tile would access beyond the array.

Estimate what reuse saves

In a simplified large-matrix model with 64-byte lines, the naive i, j, k order has about $1.125N^3$ misses when streamed rows are no longer cached on the next pass. A blocked version can reduce this to about $N^3\mathrm{/}(4b)$, assuming the three working tiles stay cached and ignoring conflicts.

For $N=1024$ and $b=32$, these estimates are about 1.2 billion and 8.4 million misses, a factor of 144. Both versions still perform about $2N^3$ floating-point operations. The saving is in repeated data movement, not in the multiplication's arithmetic count. The model describes ideal reuse; measured speedup also depends on bandwidth, execution, and other overhead.

Prefetch early enough to hide latency

Hardware prefetchers recognize streams such as sequential or constant-stride accesses. They request lines before demand accesses need them. Software can also request advance fetches, for example with GCC or Clang's __builtin_prefetch.

The timing matters. A request made too late leaves the demand waiting. A request made too early can bring a line in only to have it evicted before use. An inaccurate request consumes bandwidth and cache space without helping the program. Pointer chasing is harder to prefetch because the next address often becomes known only after the current node arrives.

Timely prefetching can turn later demand misses into hits, but the lines still travel through the hierarchy. It hides latency rather than reducing the required payload of a streaming pass. Blocking helps when values are reused; a one-time sweep has no repeated data to retain and may already be limited by memory bandwidth.