Caches (PPT 2 - 4)

Question 1

What are the four goals we wish to achieve?

Answer 1

• Fast processing
• Fast Memory
• Large Memory
• Cheap

Question 2

What is the Von Neumann Bottleneck?

Answer 2

It takes a much longer time to read data from memory than it does to actually process it

Question 3

What is a cache?

Answer 3

A small storage area located close to a processing unit, which stores recently used data taken from a larger, but more distant and slower, storage area.

Question 4

What is the payload of a cache?

Answer 4

The payload is the data and instructions fetched from memory

Question 5

What are the four traits of a computer cache?

Answer 5

• Physically very close to the processor for fast access
• Is very small
• Is accessed instead of main memory when doing a “main memory access”
• Functions automatically without software control

Question 6

What is locality of reference?

Answer 6

• When an item is used, it will probably be used again

- When an item is used, the items around it will likely be used

Question 7

How does a cache work?

Answer 7

It uses locality of reference, meaning it keeps a local copy of the original data and possibly the material around it to avoid going back to the original source

Question 8

Examples of Locality of Reference in Computing?

Answer 8

-ZIP Compression exploits repeated sequences in text
-Using the same applications regularly
Program loops use the same code repeatedly

Question 9

How small is the cache compared to main memory usually?

Answer 9

It is usually about 1% of main memory

Question 10

Why does a cache work?

Answer 10

A cache works because if the same data is needed again, it only takes 1 clock cycle to access rather than the full 8 it would take to fetch it from main memory

Question 11

How does the CPU use a cache?

Answer 11

When the CPU needs to fetch, it first checks the cache to see if the data is there. If it is, it gets a cache “hit”. If it isn’t, it gets a cache “miss” and has to read the data from main memory

Question 12

Is the processor aware a cache exists?

Answer 12

No, it treats the cache in the same way it treats main memory, meaning memory addressing is the same

Question 13

Name another type of caching

Answer 13

Disk Caching, from memory to hard disk

Question 14

What are the four possible issues with using a cache?

Answer 14

• Usage: Must function automatically
• Mapping: Cache is small so must be able to map main memory to it
• Coherence: Cache contains a copy of memory locations and integrity must be maintained during use
• Updating: Cache is normally full so needs to be able to handle new data

Question 15

What is Cache Overhead?

Answer 15

The cache needs additional space for housekeeping information and decoding information. This means storage is always more than the payload size but the quoted size is always the payload size only

Question 16

What are the three main cache mapping methods?

Answer 16

• Direct mapping
• Fully associative mapping
• N-way set associative mapping

Question 17

What is direct mapping?

Answer 17

Each main memory address maps to one specific cache address. This is found by calculation:
cache set no. = block no. mod cache size

Question 18

What are the advantages and disadvantages of using Direct Mapping?

Answer 18

Adv: Cache only stores the data and no other info so it is efficient in silicon use
Disadv: It can be inefficient. If referencing two blocks, blocks will be continually swapped and hit ratio will be low

Question 19

What is Fully-Associative Mapping?

Answer 19

An item can be placed anywhere in the cache and to find it we search every stored address

Question 20

What are the advantages and disadvantages of using Fully-Associative Mapping?

Answer 20

Adv: Does not require calculation to place payload
Disadv: -Must store the original address along with the data, meaning more space is taken up on the silicon.
-Must search every stored address to find data.

Question 21

What is Set Associative Mapping?

Answer 21

Combines the best features of Direct and Fully Associative Mapping. Cache is divided into sets(“rows”) and main memory is divided up in order to calculate the location. Some bits are used for the set, others for a partial address or tag

Question 22

What do “Ways” in a Set Associative map do?

Answer 22

They allow multiple addresses which map to the same location to be stored at the same time.

Question 23

How do you map an item using the Set Associative method?

Answer 23

We split the address into three sections:
(Tag Set Byte)
No. of byte bits is determined by way size = 2^byte bits
No. of set bits determined by sets = 2^set bits
The tag is what is left of the address bits

Question 24

If the bytes per cache line is 16 bytes and there are 256 sets, how many bits are needed for each part of the (Tag, Set, Byte) format?

Answer 24

2^4 = 16 so 4 bits for the Byte portion
2^8 = 256 so 8 bits for the Set portion
Tag is the remainder so 20 bits

Question 25

What is hexadecimal E in binary?

Answer 25

1110 (14)

Question 26

What are the three cache update strategies?

Answer 26

• Least Recently Used (LRU): Most Effective strategy
• First in First out (FIFO):Implemented by a circular buffer on each set
• Least Frequently Used (LFU): need a hit counter on each way of each set

Question 27

How do we determine which Set and Way will be used?

Answer 27

The set is determined by the address being accessed and is therefore fixed

The way to be used is determined at run time and therefore dynamic.

Question 28

Does the cache need any extra housekeeping bits to determine which way to overwrite?

Answer 28

Yes, it needs to keep track of some extra bits. These are updated dynamically during cache usage

Question 29

What is part of the physical size of the cache which is not stated in the quoted size?

Answer 29

Any housekeeping data, such as the address tag

Question 30

What are the four levels of cache?

Answer 30

Level 1 is the normal cache
Level 2 is a slightly larger but slower cache
Level 3 is for multi core CPUs and is shared between the cores
Level 4 is for multi CPU computers and can be shared between CPUs

Question 31

What are the two types of multi-level cache?

Answer 31

Inclusive: Level 2 holds all data from Level 1 and all the data it discards. Hit in L2, data copied into L1. Miss in both, data is fetched and copied into both.

Exclusive: L2 holds only discarded data from Level 1. Hit in L2, data is switched between L1 and L2. Miss in both, data is fetched into L1, L1 data moves to L2, L2 older data discarded

Question 32

What is cache coherence?

Answer 32

If one copy of the data the cache holds is updated, there may be two different versions of the same data.

Question 33

How can coherence be achieved?

Answer 33

-Ensure the cache and main memory are always coherent (contain the same data)
or
-Use appropriate dynamic techniques to ensure coherence differences don’t cause problems.

Question 34

What is a write-through?

Answer 34

In a write-through cache, a data write updates the cache and the main memory. It ensures the cache is always coherent but is slow as a memory write is needed for every write

Question 35

What is a write-back?

Answer 35

In a write-back cache, a data write only updates the cache. Cache and main memory are therefore not coherent. Main memory is updated only when the data is about to be overwritten in the cache which means there is only a main memory write cycle when necessary. Must keep track of which data has been changed.

Question 36

Do we need to do more for coherence if there are multiple processors?

Answer 36

Yes, we may want to use software and hardware protocols to monitor coherence. We also may want to allow the processors to eavesdrop on reads made by other processors to ensure each cache is up to date.

Question 37

What is the MESI Protocol?

Answer 37

Two bits are stored for each cache way, indicating one of four possible states:
Modified: Data in this way is newer than main memory. Must be written back if a processor tries to read that address
Exclusive: Data in this way matches main memory and is the only copy
Shared: Data in this way matches main memory but there are other copies
Invalid: Data is invalid or empty.

Question 38

How do you calculate Cache size?

Answer 38

Cache Size = Line size x no. of ways x no. of sets

Question 39

Calculate the size of a cache which is 2 way set associative with 128 sets, each with a way size of 32 bytes?

Answer 39

2x128x32 = 8192

Question 40

What does a cache speed up?

Answer 40

The cache increases the overall speed of the fetch execute cycle by automatically reducing the number of main memory reads/writes that are required