About Me

Welcome to my blog! This is where I collect my observations and notes on programming and technology. The main subjects range from implementation details to broader ideas about programming.

Main Topics

• Engineering Projects: Exploring implementation details and how technical systems work.
• C/C++: Notes on language features and programming techniques.
• The Programmer’s Perspective: Ideas about developing a career and a way of thinking as a programmer.

For more, visit the categories page.

Contact

If you have questions or would like to discuss something, please get in touch through the About page.

Thank you for reading and for your support. I hope these notes help you on your own technical journey!

Locality and memory hierarchies

Temporal and spatial locality motivate hierarchical storage. Data is transferred from a lower level into a faster upper level. The original notes describe an inclusive hierarchy in which upper-level contents are a subset of lower-level contents; actual cache hierarchies need not all use an inclusive policy.

SRAM and DRAM

A major cost difference comes from implementation area. SRAM cells commonly use several transistors, often six, whereas DRAM combines a transistor with a storage capacitor. DRAM therefore offers greater density. SRAM does not require periodic refresh and supports fast access, but must remain powered to retain data. DRAM’s capacitor charge must be refreshed, which accounts for the word dynamic.

Historically SRAM chips supplied fast caches; semiconductor scaling enabled processor-integrated caches. The details of both technologies remain important research topics because memory behavior strongly affects processor performance.

Finding data in a cache

A cache must quickly answer two questions: is the addressed data present, and where would it be stored? An address-derived mapping makes that lookup practical.

For a direct-mapped cache, first divide the byte address by the block size to obtain a block address. A modulo operation selects the cache line. The entry contains data, a tag, and a valid bit so that the implementation can distinguish the requested memory block from another block mapping to the same location.

The block-size tradeoff

Larger blocks exploit spatial locality, but with a fixed total cache capacity they reduce the number of independently resident blocks. That can increase replacement pressure and evict useful data before it is accessed. A larger transfer can also increase the miss penalty. The useful balance depends on locality, transfer bandwidth, and the working set. Improving bulk-transfer support can change that balance.

Early restart and critical-word-first

On a miss, the processor may resume as soon as the requested word arrives, without waiting for the whole block. This is early restart.

1

Early restart can benefit instruction fetch because sequential instructions often occupy nearby addresses. The effect on data accesses depends more strongly on the access pattern: another required value may belong to a different block before the current refill finishes.

The benefit concerns the current miss: it reduces the time before the requested value becomes usable, even if the next access concerns a different block. If the ongoing refill prevents another required cache access, the pipeline can still stall.

Critical-word-first, also called requested-word-first, fetches the requested word before the rest of the block and then completes the remaining transfer. It uses the same idea of making needed data available earlier, with a more deliberate transfer order.

Alignment and address fields

A conventional power-of-two cache divides an address into tag, index, and block-offset fields. A word-oriented explanation can further divide the offset into a byte-within-word part and a word-within-block part. Natural alignment simplifies access and can prevent an object from spanning blocks.

The original notes generalized this to all RISC-V instructions and data being four-byte aligned. More precisely, alignment depends on the instruction set and access width: a word is four bytes, but byte, halfword, doubleword, and compressed-instruction cases differ.

Removing offset bits produces the block address. Integer division by a power of two rounds a nonnegative address down to the containing block; this is why it identifies the block even for an unaligned byte address.

Capacity, hit time, miss rate, and miss penalty

A larger cache can retain more data and reduce misses, but can also take longer to access. Technology and circuit organization matter, so the relationship is not simply that every capacity increase lengthens the clock. In a design where cache access lies on the critical path, however, hit time and cycle time can constrain capacity.

cache capacity = block size × number of blocks

Once capacity is fixed, larger blocks mean fewer entries. Spatial locality may improve while replacement pressure and refill time worsen. A lower miss rate can justify a greater penalty per miss, but neither number alone establishes performance. The relevant tradeoff includes both.

Bandwidth matters too

Splitting instruction and data caches allows instruction fetch and data access in the same cycle. This can benefit a pipeline even when the combined miss behavior differs from that of a unified cache. Cache performance therefore includes bandwidth and structural contention, not just miss rate.

Set associativity

At the other extreme from direct mapping, a fully associative cache permits a block in any entry. All relevant tags must be searched, often with parallel comparison. The hardware cost becomes substantial for large caches.

Set associativity is a compromise. Divide the cache into m sets of n ways. The address selects one set, and a block may occupy any way in that set. Parallel tag comparisons search the selected set.

Increasing associativity can reduce conflict misses, but adds comparator and selection work. Capacity and associativity must be evaluated together. Higher associativity is not unconditionally better, and whether it increases hit time depends on the implementation.

Selecting a way

A four-way set-associative design uses four tag comparators. Each match is qualified by a valid bit. The resulting signals select data through a four-to-one multiplexer and combine into the hit indication. Parallel comparison avoids a sequential search, although selection and wiring still have delay.

Replacement and lower-level caches

LRU attempts to retain recently used blocks and exploit temporal locality. Adding lower-level caches can reduce the penalty of a first-level miss. Both techniques need to be considered together with access latency and hardware cost.

Traditional algorithm analysis often abstracts away the memory hierarchy. Understanding that hierarchy is essential to explaining performance on modern processors.

• ← Previous Post
• Next Post →