CS274: Computer Architecture - The Memory Hierarchy: Cache Design

Activity Goals

The goals of this activity are:
  1. To design a memory architecture that does not starve the CPU despite the memory hierarchy
  2. To exploit cache design using the principles of locality

Supplemental Reading

Feel free to visit these resources for supplemental background reading material.

The Activity

Directions

Consider the activity models and answer the questions provided. First reflect on these questions on your own briefly, before discussing and comparing your thoughts with your group. Appoint one member of your group to discuss your findings with the class, and the rest of the group should help that member prepare their response. Answer each question individually from the activity, and compare with your group to prepare for our whole-class discussion. After class, think about the questions in the reflective prompt and respond to those individually in your notebook. Report out on areas of disagreement or items for which you and your group identified alternative approaches. Write down and report out questions you encountered along the way for group discussion.

Model 1: The Principle of Locality

Questions

  1. There are two principles of locality: Temporal Locality (referring to a variable or instruction repeatedly in a short period of time) and Spatial Locality (referring to nearby memory addresses following a particular access). Identify all the examples of each in the code example above.
  2. What would happen to our locality if we switched the two for loop lines? This is called switching from a row-major order to a column-major order.
  3. What would happen to our locality if N and M became very large?

Model 2: The Memory Hierarchy

The Memory Mountain from CS:APP by Bryant and O'Hallaron

Questions

  1. What do you think processor registers are made of? Why might computer memory and disk be made of a different material?
  2. Since cache (and, for that matter, processor registers) is so much smaller than primary memory, how can we make efficient use of the space given the principle of locality? For example, should we randomly store data in cache, or take a more strategic approach?
  3. What do you think stride refers to?

Model 3: Exploiting Temporal Locality with the Direct Mapped Cache

A Direct Mapped Single Word Block Cache
Direct Mapped Cache Design with Address Bits

Questions

  1. Which address bits are used to determine which block a word maps to?
  2. Given a cache with 1024 entries, how many bits would determine the block number (a.k.a. row, or index)?
  3. What is the purpose of the tag bits? Why is it necessary to store them?
  4. Why do you think the last two bits of the address are ignored?

Model 4: Direct Mapped Cache Example

Index Valid Tag Data
000
001
010
011
100
101
110
111
Address Binary Cache Block Hit/Miss?
22 10110 110
26 11010 010
22 10110 110
26 11010 010
16 10000 000
3 00011 011
16 10000 000
18 10010 010

Questions

  1. Fill in the table above, assuming an 8-word direct mapped cache.
  2. How many hits and misses were there?
  3. Why were these cache replacements particularly unfortunate?
  4. How could we increase the duration of temporal locality in this cache? That is, what could we do to enable these words to remain in cache longer?

Model 5: Write Policies to Avoid Stale Data

ComputerMemoryHierarchy

Questions

  1. What is the benefit and drawback of writing data to both cache and to main memory (and every layer in between) whenever a write occurs? This is known as a "write-through" strategy.
  2. What would need to change if a write-back strategy was used instead, in which data was only written to the top layer of cache. What would we need to do to ensure this data is not lost, and when would we need to copy it to the next lower layer?

Model 6: Adding Spatial Locality Multiword Blocks

Multi-word cache

Questions

  1. What is different about this design?
  2. How does this approach enable spatial locality?
  3. To what block and index does address 67 map?
  4. What other words would be loaded into this block?

Model 7: Mitigating Cache Conflicts with Associative Caches

A set associative cache

Questions

  1. Draw a 1 MB cache that is 4-way set associative, with 8 words per block.
  2. Map address 37 to this cache, and indicate which other addresses would be loaded.
  3. Show the tag and index for address 37.
  4. Does a fully associative cache need a block offset, an index, and/or a tag? Why or why not?

Model 8: Cache Replacement Strategies

Draw a direct mapped, two-way set associative, and fully associative cache with 4 words total.

Questions

  1. Map these addresses and count the number of hits and misses: 0, 8, 0, 6, 8.
  2. How does your hit rate change for 8 or 16 word caches?
  3. When you must replace a block, how can you decide which set to replace? What is your rationale for doing so?

Model 9: Reducing the Miss Penalty with Multi-Level Caches

Suppose you have a base CPI of 1 (assuming L1 cache hits) and a 5 GHz CPU clock (0.2 ns per CPU cycle), 100 ns main memory access time, a 2% miss rate at L1, a 0.5% miss rate at L2.

Questions

  1. What is your CPI with and without your secondary cache?

Model 10: Key Formulas and Concepts Recap

A quick-reference recap of the key rules from this activity. Try to reproduce each one from memory before peeking!

Key Rules and Formulas
  • Address bit-splitting: offset bits = log2(block size); index bits = log2(number of sets); tag bits = the rest of the address. For byte addresses with word-sized data, the lowest log2(4) = 2 bits are the byte-within-word offset.
  • Number of sets: sets = cache size / (block size * associativity). A direct mapped cache has associativity 1 (sets = number of blocks); a fully associative cache has one set (0 index bits - only tag and offset).
  • Micro-example (direct mapped): 1024 one-word blocks, 32-bit byte address: (1) offset = 2 bits (bytes in a word); (2) index = log2(1024) = 10 bits; (3) tag = 32 - 10 - 2 = 20 bits.
  • Micro-example (set associative): 4-way, 8-word (32-byte) blocks, 1 MB total: (1) block offset = log2(32) = 5 bits; (2) sets = 2^20 / (32 * 4) = 8192, so index = 13 bits; (3) tag = 32 - 13 - 5 = 14 bits.
  • Which block? block address = address / block size; set number = block address mod number of sets. Micro-example: address 22 = 10110, 8 one-word blocks: index = low 3 block bits = 110, tag = 10.
  • AMAT (average memory access time) = hit time + miss rate * miss penalty. Micro-example: 0.2 ns hit, 2% miss rate, 100 ns penalty: (1) 0.02 * 100 = 2 ns; (2) AMAT = 0.2 + 2 = 2.2 ns. A second-level cache replaces most of that 100 ns penalty with a much shorter L2 hit time.
  • Locality: temporal (reuse the same address soon) is exploited by keeping recently used blocks; spatial (use neighboring addresses) is exploited by multiword blocks that load neighbors in with each miss.
  • Write policies: write-through updates cache and memory on every write (simple, but slow writes); write-back writes only the cache, marks the block dirty, and copies it down when the block is evicted (fast writes, must track dirty blocks).

32-bit address, direct mapped, 1024 one-word blocks:

|        tag (20 bits)        | index (10) | byte offset (2) |
 31 ........................ 12 11 ...... 2  1 ............ 0

tag    --> compared against the tag stored in the indexed row
index  --> selects the cache row (set)
offset --> selects the byte/word within the block

Glossary
TermMeaning
Hit / MissThe requested word is / is not present in the cache
Block (line)The unit of transfer between cache and memory (one or more words)
IndexAddress bits selecting which set (row) a block maps to
TagThe remaining upper address bits, stored to verify which block occupies a row
Valid bitMarks whether a row actually holds data yet
AssociativityHow many places (ways) a block may live within its set
Miss penaltyExtra time to fetch a block from the next lower level on a miss
LRU replacementEvicting the least recently used block in a set, betting on temporal locality
Write-through / write-backWriting to memory on every store vs. only when a dirty block is evicted
StrideThe distance between successive memory accesses (stride 1 maximizes spatial locality)

Questions

  1. Without looking, split a 32-bit address for a direct mapped cache with 256 four-word (16-byte) blocks: how many offset, index, and tag bits?
  2. Compute the AMAT for a 1 ns hit time, 5% miss rate, and 80 ns miss penalty.

Submission

I encourage you to submit your answers to the questions (and ask your own questions!) using the Class Activity Questions discussion board. You may also respond to questions or comments made by others, or ask follow-up questions there. Answer any reflective prompt questions in the Reflective Journal section of your OneNote Classroom personal section. You can find the link to the class notebook on the syllabus.