Computer architectureLesson 3 of 3 in the course Memory hierarchy

Cache Replacement Policies: Recency, Frequency, and Prediction

5 flashcards · 5 quiz questions · 5 match pairs · 5 fill-in sentences · English

Save course
Lesson progress
0 / 5

Your progress is kept in this browser only.Sign up to save it

Summary

This lesson introduces cache replacement and the performance trade-offs that shape replacement policies. Understanding these fundamentals makes it easier to compare the algorithms in later lessons.

A cache keeps copies of data in storage that is faster or cheaper to access than the normal backing store. By retaining recently or frequently used items, a cache can reduce the time and work required to serve requests.

All flashcards

What is Bélády's optimal replacement rule?
Evict the item whose next use is farthest in the future; it requires knowledge of future requests.
How does FIFO replacement choose a victim?
It evicts the item that has been in the cache longest, typically the earliest inserted.
How does SLRU protect items with demonstrated reuse?
It promotes a hit item from probationary to protected storage and replaces from probationary storage first.
What does an RRPV represent in RRIP?
A prediction of how soon a cache line will be referenced again; higher values indicate later predicted reuse.
What are the three queues in S3-FIFO?
A small queue, a main queue, and a ghost queue that stores metadata.

Quiz questions

  1. When a cache needs space, how does random replacement select an item to evict?Answer: It selects a cached item at random without using access history.
  2. In SIEVE, what does an object's request bit indicate?Answer: Whether the object has been requested since it entered the cache.
  3. What information does TLRU use in addition to recency?Answer: Content lifetime or usability time, represented using TTU.
  4. How does DRRIP choose between SRRIP and BRRIP for most cache sets?Answer: It uses set dueling and a policy counter to select between them.
  5. How does ARC adapt its allocation between replacement behaviors?Answer: It uses information about recently evicted items to adjust the sizes of its cache portions.

Based on the Wikipedia article Cache replacement policies, licensed CC BY-SA 4.0. Adapted into a summary, flashcards and quizzes.

More in Computer architecture

All Computer architecture lessons
Computer architectureInstruction Pipelining: Stages, Hazards, and Performance Trade-offs5 flashcards · 5 quiz questions · 4 gamesPlay free →Computer architectureCPU Cache Organization, Policies, Addressing, and Hierarchies5 flashcards · 5 quiz questions · 4 gamesPlay free →Computer architectureOut-of-Order Execution: Scheduling, Renaming, and Retirement5 flashcards · 5 quiz questions · 4 gamesPlay free →Computer architectureMemory Hierarchy: Storage Levels, Locality, and Tiering5 flashcards · 5 quiz questions · 4 gamesPlay free →Computer architectureData and Control-Flow Addressing Modes in Processor Architectures5 flashcards · 5 quiz questions · 4 gamesPlay free →Computer architectureBranch Prediction: Strategies, History, and Speculative Execution5 flashcards · 5 quiz questions · 4 gamesPlay free →