Caches and Caching Flashcards
What are the two concepts associated with caching?
Caching and Memory Cache
What is caching?
It is an optimization technique
that speeds up access to slow storage by
storing frequently accessed items in fast
storage.
What is memory cache?
It is a type of fast memory
storage between the CPU and RAM that
stores frequently accessed memory items and speeds up memory access.
What are some instances where caching is used as an optimization technique?
Physical memory cache, Web cache. Disk buffers, VM, TLB
Explain web cache
Speeds up access to web pages by
storing a copy of the frequently accessed pages locally in the computer.
Explain disk buffers in the context of cache.
Store in RAM the disk blocks that are
frequently accessed in the computer.
Explain Virtual Memory in the context of cache
Store in RAM the disk blocks that are
frequently accessed in the computer.
Explain Translation Lookaside Buffer in the context of caching.
Store in RAM the disk blocks that are
frequently accessed in the computer.
What is a Cache Hit?
● When a request is satisfied from cache,
● No need to access Large Data Storage
What is a Cache miss?
● Request cannot be satisfied from cache,
● Item is retrieved from Large Data Storage,
● A copy is placed in cache.
● If cache is full, an item not used recently in the cacheis removed to make room for the new item (LRU-Least Recently Used).
What happens when the cache is full?
an item not used recently in the cacheis removed to make room for the new item (LRU-Least Recently Used).
What is the hit ratio in context of cache?
● Percentage of requests satisfied from cache between 0 and 1.
What is the miss ratio in the context of cache?
● Percentage of requests not satisfied from cache.
● Time = r * Thit + (1-r)*Tmiss Thit < Tmiss
What are the worse and best cases of cache in terms of hit ratio?
● In the worst case (r=0) the cost will be the same as not having cache at all.
● In the best case (r=1), all accesses will be in the cache.
What is Locality of Reference?
refers to repetitions of the same request.
What does it mean to have a high locality of reference?
Many repetitions of same request
What does it mean to have a low locality of reference?
Few repetitions of the same request
What is better for cache, a high or low locality of reference?
high, more repetitions means the cache will be more effective.
What is preloading (prefetch) in caches?
It is an optimization technique where items are stored in the cache before the request arrives.
When does preloading work?
When items are grouped. ex:
● When loading a web page, load also the images in the web page.
● When accessing an item in a struct, also fetch the other items in the struct.
● When reading a program instruction, also read the instructions that follow.
Where is memory cache located?
In between the cpu and ram
What are two different types of memory cache?
Write-Through, and Write-Back
What is Write-Through cache?
● Place a copy of the item in cache
● Write a copy to Physical Memory
What is Write-Back cache?
● Place a copy of item in cache
● Write the copy to RAM only when necessary
● Since multiple processors may have different
caches, a Cache Coherence mechanism is
needed to make sure the cache is consistently updated.
What are the specifics of multi level cache?
● L1 Cache
● Built inside the CPU
● L2 Cache
● External to the CPU
● L3 Cache
● Built into RAM
Where are instructions and data stored?
In RAM
Do modern computers separate instructions and data in cache?
No
Do instructions have a high or low locality of reference?
High, usually accessed sequentially and some functions are accessed more than others
Does data have a high or low locality of reference?
Medium, there is some locality of reference for example some part of the stack are accessed more than the heap.
What cache can store virtual memory?
L1
What are cache lines?
The way RAM is divided.
What is the typical size of a cache line/block?
64 bytes
How much memory is fetched during a cache miss?
1 line, 64 bytes
What are the types of cache technologies?
● Direct Memory Cache
● Associative Memory Cache
What is Direct Memory Cache?
● The memory is divided into blocks (Cache Lines)
and each Block has a number.
● N blocks in memory are grouped into tags.
What is Associative Memory Cache?
● Generalization of Direct Memory Cache.
● Uses parallel hardware.
● Maintains independent caches:
What are the direct cache steps?
Input: Memory Address
Output: Data in that address
Algorithm:
● Obtain tag t, block number b, and offset
● Examine Tag b in slot b in cache. If tag
matches, extract the value from slot b in cache.
● If tag does not match, read the item in memory
and copy data in slot b and replace the tag with
t.
● Problem: Two items with the same block
number cannot be in cache at the same time.
Does it matter what order you access elements in an array for speed?
Yes, accessing sequentially is faster for the cache.
