Caches and Caching

Question 1

What are the two concepts associated with caching?

Answer 1

Caching and Memory Cache

Question 2

What is caching?

Answer 2

It is an optimization technique
that speeds up access to slow storage by
storing frequently accessed items in fast
storage.

Question 3

What is memory cache?

Answer 3

It is a type of fast memory
storage between the CPU and RAM that
stores frequently accessed memory items and speeds up memory access.

Question 4

What are some instances where caching is used as an optimization technique?

Answer 4

Physical memory cache, Web cache. Disk buffers, VM, TLB

Question 5

Explain web cache

Answer 5

Speeds up access to web pages by
storing a copy of the frequently accessed pages locally in the computer.

Question 6

Explain disk buffers in the context of cache.

Answer 6

Store in RAM the disk blocks that are
frequently accessed in the computer.

Question 7

Explain Virtual Memory in the context of cache

Answer 7

Store in RAM the disk blocks that are
frequently accessed in the computer.

Question 8

Explain Translation Lookaside Buffer in the context of caching.

Answer 8

Store in RAM the disk blocks that are
frequently accessed in the computer.

Question 9

What is a Cache Hit?

Answer 9

● When a request is satisfied from cache,
● No need to access Large Data Storage

Question 10

What is a Cache miss?

Answer 10

● 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).

Question 11

What happens when the cache is full?

Answer 11

an item not used recently in the cacheis removed to make room for the new item (LRU-Least Recently Used).

Question 12

What is the hit ratio in context of cache?

Answer 12

● Percentage of requests satisfied from cache between 0 and 1.

Question 13

What is the miss ratio in the context of cache?

Answer 13

● Percentage of requests not satisfied from cache.
● Time = r * Thit + (1-r)*Tmiss Thit < Tmiss

Question 14

What are the worse and best cases of cache in terms of hit ratio?

Answer 14

● 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.

Question 15

What is Locality of Reference?

Answer 15

refers to repetitions of the same request.

Question 16

What does it mean to have a high locality of reference?

Answer 16

Many repetitions of same request

Question 17

What does it mean to have a low locality of reference?

Answer 17

Few repetitions of the same request

Question 18

What is better for cache, a high or low locality of reference?

Answer 18

high, more repetitions means the cache will be more effective.

Question 19

What is preloading (prefetch) in caches?

Answer 19

It is an optimization technique where items are stored in the cache before the request arrives.

Question 20

When does preloading work?

Answer 20

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.

Question 21

Where is memory cache located?

Answer 21

In between the cpu and ram

Question 22

What are two different types of memory cache?

Answer 22

Write-Through, and Write-Back

Question 23

What is Write-Through cache?

Answer 23

● Place a copy of the item in cache
● Write a copy to Physical Memory

Question 24

What is Write-Back cache?

Answer 24

● 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.

Question 25

What are the specifics of multi level cache?

Answer 25

● L1 Cache
● Built inside the CPU
● L2 Cache
● External to the CPU
● L3 Cache
● Built into RAM

Question 26

Where are instructions and data stored?

Answer 26

In RAM

Question 27

Do modern computers separate instructions and data in cache?

Answer 27

No

Question 28

Do instructions have a high or low locality of reference?

Answer 28

High, usually accessed sequentially and some functions are accessed more than others

Question 29

Does data have a high or low locality of reference?

Answer 29

Medium, there is some locality of reference for example some part of the stack are accessed more than the heap.

Question 30

What cache can store virtual memory?

Answer 30

L1

Question 31

What are cache lines?

Answer 31

The way RAM is divided.

Question 32

What is the typical size of a cache line/block?

Answer 32

64 bytes

Question 33

How much memory is fetched during a cache miss?

Answer 33

1 line, 64 bytes

Question 34

What are the types of cache technologies?

Answer 34

● Direct Memory Cache
● Associative Memory Cache

Question 35

What is Direct Memory Cache?

Answer 35

● The memory is divided into blocks (Cache Lines)
and each Block has a number.
● N blocks in memory are grouped into tags.

Question 36

What is Associative Memory Cache?

Answer 36

● Generalization of Direct Memory Cache.
● Uses parallel hardware.
● Maintains independent caches:

Question 37

What are the direct cache steps?

Answer 37

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.

Question 38

Does it matter what order you access elements in an array for speed?

Answer 38

Yes, accessing sequentially is faster for the cache.