Intro Caches Theory

Question 1

What is it the main goal of a cash memory?

Answer 1

To increase the performance of a computer through the memory system in order to:

• Provide the user the illusion to use a memory that is simultaneously large and fast
• Provide the data to the processor at high frequency

Question 2

Why does memory hierarchy design becomes more crucial with multicore processors?

Answer 2

Due to the aggregate peak bandwidth growth related to the increasing in the number of cores

Question 3

What is temporal locality?

Answer 3

When there is a reference to one memory element, the trend is to refer again to the same memory element soon

Question 4

What is spatial locality?

Answer 4

When there is a reference to one memory element, the trend is to refer soon at other memory elements, whose addresses are close by

Question 5

How do caches exploit both types of locality?

Answer 5

Exploits temporality by keeping the contents of recently access memory locations

And spatial locality by fetching blocks of data around recently accessed memory locations

Question 6

What is the minimum of data that can be copied into the cash?

Answer 6

The block or cash line

Question 7

What is the relationship between the block size in the cash memory and in the main memory and what is the rationale behind it?

Answer 7

The block sizing the cash memory must be multiple of the word size in main memory. The reason behind it is to better exploit the spatial locality.

Question 8

How do we calculate the number of blocks in a cash?

Answer 8

We divide the cash size by the Block size

Question 9

Define a cash hit

Answer 9

It is when the requested data is found in one of the cash blocks

Question 10

Define a cash miss and how it is handled

Answer 10

It is when a requested data is not find in one of the cash blocks. In case of a miss we stall the CPU, then we require the block from the main memory, copy the block in cash and repeat the cash access

Question 11

What is the hit rate and how do we calculate it?

Answer 11

It is the number of memory access that find the data in the upper level with respect to the number of memory accesses.

It is calculated by the amount of hit accesses divided by the amount of memory accesses

Question 12

What is the hit time?

Answer 12

It is the time to access the data in the upper level of the memory hierarchy

Question 13

Define a miss rate

Answer 13

It is the number of memory accesses not finding the data in the upper level with respect to the total number of memory accesses. It is therefor calculated as the division between the misses and the total memory accesses

Question 14

Define and explain, how is the miss time calculated?

Answer 14

The miss time is the sum of the hit time and the miss penalty, where the penalty is the time needed to access the lower level and to replace the block in the upper level

Question 15

What is the average memory access time and how it is calculated?

Answer 15

It is the sum of the hit rate and miss rate by its respective hit and miss time. It can be calculated ass the hit time plus the miss rate times the miss penalty (Hit Time + Miss Rate * Miss Penalty)

Question 16

Based on how the average memory access time is calculated, how can we improve cash performance?

Answer 16

We can improve cash performance by reducing either the hit time, the miss rate or even the miss penalty

Question 17

What is the rational behind the division of the cash into instruction and data cash

Answer 17

Since there is a higher spatial locality in instructions, the miss rate of an instruction cache would be much lower than the miss rate of a data cash

Question 18

Define a validity bit (and it’s relation with the bootstrap process)

Answer 18

Validity be it is used to indicate if the content of the cash block or line is valid or not. At the bootstrap, all the entries in the cash are marked as invalid.

Question 19

Define the cash tag

Answer 19

It contains the value that univocally identifies the memory address corresponding to the stored data

Question 20

Where can a block be placed in the upper level? Given the address of the block in the main memory, where the block can be placed in the cash.

Answer 20

The correspondence between the memory address and the cash address depends on the cash structure, which can be direct mapped, fully associative, and N-way set-associative

Question 21

Describe the direct mapped cash and its functionalities. Describe how the memory address in the cash is composed.

Answer 21

In the direct mapped cache, each memory location correspondence to one and only one cash location.

The block address is composed by a tag and index. The full memory address also contains a block offset to control this specific data that was requested.

Question 22

This describe how is it done the verification of a given address with respect to a direct mapped cash structure

Answer 22

First, the cash verifies the index in the requested data in the memory location, which will correspondence to one and only cash line. Then he verifies the tag in order to check for the correspondence off the stored data. Then it check the validity of the data, and finally using the block offset it extract the specific requested data in the memory block.

Question 23

Describe a fully associative cash and its memory composition

Answer 23

In a fully associative cash The memory block can be placed in any position of the cash, therefore, all the cash blocks must be checked during the search of the block.

The cash memory is composed by the block address, which contains the tag for memory correspondence verification, and block offset

Question 24

This describe how is it done the verification of a given address with respect to a fully associative cash structure

Answer 24

The associative cash checks first for the tag correspondence between the cash lines and the requested data memory address, then it checks the validity of the data in the cash, and finally uses the offset to extract the specific data requested

Question 25

Describe the N-way set associative and its memory address composition

Answer 25

Cash is composed of set, each set composed of N blocks, which is related to the cash and block size. Memory block can be placed in any block of the set, and therefore the search must be done on all the blocks of the set.

Question 26

This describe how is it done the verification of a given address with respect to a n-way set associative cash structure

Answer 26

The cash uses the index in the block address memory requested to identify the correct set in which that memory address could be stored. Then inside this set it compares every cash line with the requested tag, then check the validity of the line, and finally it uses the offsets to extract the specific data requested

Question 27

How does the incremental of associativity impact the cash performance? What are the advantages and these advantages?

Answer 27

Advantages: reduction of miss rate

Disadvantages : higher implementation cost, increment of hit time

Question 28

How is a block found if it is in the upper level

Answer 28

To address the problem of block identification, we need to compare tag beats.

In a direct map cash, we identify the block position by index (once every memory address corresponds to a specific cash address) then we compare to tag off the block and verify the validity

Set-associative mapping, we identify the set in which the memory address could be placed then we compare the tag of the blocks in the set and then check the validity bit

In fully associative mapping, we compare the tags for every block in the cash memory and verify the validity bit

Question 29

Which block should be replaced on a miss, describe the differences in the rational between the different structures of possible caches

Answer 29

In case of a miss in a fully associative cash, we need to decide which block to replace, any block is a potential candidate for the replacement

If the cash is set associative, we need to select among the blocks in the given set

For a direct mapped cash There is only one candidate to be replaced, therefore, there is no need of any block replacement strategy.

Question 30

Are the main strategies for block replacement

Answer 30

Random, least recently used, and IIFO

Question 31

What happens on a write?

Answer 31

There are two possibilities

Right – through, in which the information is written to both the block in the cash and to the block in the lower level memory

Right – back, the information is written only in the block in cash. The modified cash block is written to the lower level memory only when it is replaced due to a miss.

Question 32

The question “is a block clean or dirty?” adequate to which right policy and what does it means?

Answer 32

It is adequate to the write – back policy, and it is related to the fact that at the end of the write in cash, the cash block becomes dirty (modified) and the main memory will contain a different with respect to the value in cash, main memory cash are not coherent

Question 33

Compare the two right policies

Answer 33

Write – through is simpler to implement, but to be effective, it requires a right buffer, to not wait for the lower level of the memory hierarchy. The read misses are cheaper because they do not require any write to the lower level of the memory hierarchy and the memory is always up-to-date.

A write-back policy, otherwise, the block can be written by the processor at the frequency at which the cash, and not the main memory, can accept it . Other positive aspect is: multiple writes to the same block require only a single write to main memory

Question 34

To what right policy would be right but for being necessary and how would it work?

Answer 34

Write buffer would be necessary in case of a write through policy

The basic idea is to insert a buffer to not wait for lower level memory access. This way, the processor writes data to the cash and to the right buffer and the memory controller writes the contents of the buffer to the memory.

Question 35

What is a problem of a write buffer

Answer 35

Write buffer saturation

Question 36

What are the possible options a buffer can take on the right miss

Answer 36

It could use the write allocate policy where it would allocate a new cash line in cash then write (double write to cash).

Or it could use a no write allocate policy, this way you simply send write data to lower level memory, do not allocate new cash line

Question 37

What are the most common combinations between right policies?

Answer 37

Write-back cash uses the write allocate option, hoping next writes to the block will be done again in cash

Write-through cash uses the no write allocate option, hoping next writes to the block will be done again in memory

Question 38

How can we reduce the miss penalty?

Answer 38

Adding a second level cash

This way we would have a L1 cash, small enough to match the Fast CPU cycle time

And another L2 cash large enough to capture many accesses that would go to main memory reducing the effective miss penalty

Question 39

How would we calculate the average memory access time for a memory hierarchy with two level cashes

Answer 39

It would be calculated as the hit time of L1, plus the miss rate of L1 times the miss penalty of L1

But the penalty of L1 is equal to the hit time of L2, plus the miss rate of L2 times the miss penalty of L2

So our final result would be:

Hit Time L1 + Miss Rate L1 * Hit Time L2 + Miss Rate L1L2 * Miss Penalty L2

Question 40

What is the difference between a local and global miss rate?

Answer 40

In local miss rate, we would have the number of misses in the cash divided by the total number of memory accesses to the cash

In Global miss rate, otherwise, is the misses in the cash divided by the total number of memory accesses generated by the CPU.

For the upper level cash, for example, we would have the global miss rate equal to local, in the lower levels otherwise we would have the Global Miss rate as the multiplication of the local miss rate of the upper level and the current level.

In other words, it indicates what fraction of memory accesses from CPU go all the way to main memory.

Question 41

Direct Mapped Cache Example

• Memory address composed of N = 32 bit

• Cache Size 64 K Byte

• Block Size 128 bit = 16 Byte

Calculate the Structure of the Memory Address

Answer 41

Block Size 128 bit = 16 Byte => 4 bit Block Offset

Numberofblocks=CacheSize/BlockSize=64KByte/16Byte= 4 K blocks => 212 blocks => 12 bit Index

Structure of the memory address:
• Byte Offset: BO = 2 bit
• Word Offset: WO = 2 bit
• Index: 12 bit
• Tag:(32–12-4)=16bit

Question 42

Fully Associative Cache Example

• Memory address composed of N = 32 bit

• Cache size 256 Byte

• Block size 128 bit = 16 Byte

Calculate the Structure of the Memory Address

Answer 42

Block size 128 bit = 16 Byte => 4 bit Block Offset

Number of blocks = Cache Size / Block Size =
= 256 Byte / 16 Byte = 16 Blocks

Structure of the memory address:
• Byte Offset: BO = 2 bit
• Word Offset: KO = 2 bit
• Tag:(32bit–4bit)=28bit

Question 43

4-way Set Associative Cache Example

• Memory address: N = 32 bit

• Cache Size 4KByte

• Block size 32 bit = 4 Byte

Calculate the Structure of the Memory Address

Answer 43

Block size 32 bit = 4 Byte => 2 bit Block Offset

Numberofblocks=CacheSize/BlockSize=4KByte/4Byte=1Kblocks

Numberofsets=CacheSize/(Blocksizexn)=4KByte/(4Bytex4)= =256 sets=28 sets=>8bitIndex

Structure of the memory address:
• Byte Offset: BO = 2 bit
• Word Offset: WO = 0 bit
• Index: 8 bit
• Tag:(32–8–2)bit=22bit

Question 44

What are the categories of cache misses

Answer 44

Compulsory misses, capacity misses, and conflict misses

Question 45

What are compulsory misses

Answer 45

Cold start misses or first reference misses

Question 46

What are capacity misses

Answer 46

If the cache cannot contain all the blocks needed during the execution of a program, capacity misses will occur due to blocks being replaced and later retrieved

Can be reduced by increasing the cache size

Question 47

What are conflict misses

Answer 47

If the block placement strategy is set, associative or direct mapping, conflict misses will occur because a block can be replaced and later retrieved when other blocks map to the same location in the cash

Conflict misses decrease as associativity increases

Question 48

What are the ways to reduce the miss rate and its consequences

Answer 48

Increase cash capacity. Which return increases heat time, area, power consumption, and cost.

Increase block size. Reduces the miss rate up to a point when the block size is too large with respect to the cash size. Reduces compulsory misses due to spatial locality.

Higher associativity. Which comes at the price of complexicity

By introducing multibanked caches

By introducing victim caches

Via pseudo-associativity and way prediction

By hardware prefetching of instructions and data

By software prefetching data

By compiler optimizations

Question 49

How can we reduce miss rate via larger block size and are the drawbacks of this technique

Answer 49

Increasing the block size reduces the miss rate up to a point when the block size is too large with respect to the cache size

Larger block size will reduce compulsory misses taking advantage of spatial locality

Main drawbacks:
 Larger blocks increase miss penalty
 Larger blocks reduce the number of blocks so increase conflict misses (and even capacity misses) if the cache is small.

Question 50

How can we reduce miss rate via higher associativity

Answer 50

Higher associativity decreases the conflict misses

Main drawbacks:
 The complexity increases hit time, area, power consumption and cost.

Question 51

How can we reduce miss rate using multibanked caches

Answer 51

Multibanked caches introduce a sort of associativity

 Organize cache as independent banks to support simultaneous access to increase the cache bandwidth

 Interleave banks according to block address to access each bank in turn (sequential interleaving)

Question 52

How can we reduce miss rate using victim caches

Answer 52

Victim cache is a small fully associative cache used as a buffer to place data discarded from cache to better exploit temporal locality

 Victim cache placed between cache and its refilling path towards the next lower-level in the hierarchy

 Victim cache is checked on a miss to see if it has the required data before going to lower-level memory

 If the block is found in Victim cache the victim block and the cache block are swapped

Question 53

How can we reduce miss rate using hardware prefetching

Answer 53

Basic idea: To exploit locality, pre-fetch next instructions (or data) before they are requested by the processor
 Pre-fetching can be done in cache or in an external stream buffer

Question 54

Give an example on how hardware prefetching works

Answer 54

Instruction pre-fetch in Alpha AXP 21064
 Fetch two blocks on a miss; the requested block (i) and the next consecutive block (i+1)
 Requested block placed in cache, while next block in instruction stream buffer
 If miss in cache, but hit in stream buffer, move stream buffer block into cache and pre-fetch next block (i+2)

Question 55

How can we reduce miss rate using software prefetching

Answer 55

Compiler-controlled pre-fetching (the compiler can help in reducing useless pre-fetching): Compiler inserts pre- fetch LOAD instructions to load data in registers/cache before they are needed

Question 56

How can we reduce miss rate by compiler optimizations

Answer 56

Basic idea: Apply profiling on SW applications, then use profiling info to apply code transformations

Managing instructions:
 Reorder instructions in memory so as to reduce conflict misses
 Profiling to look at instruction conflicts

Question 57

How can we reduce miss rate by applying way prediction

Answer 57

Way prediction is a technique used in cache memory systems to reduce the miss rate and improve access times. It helps in predicting the “way” in which a particular piece of data might be found, thus enhancing the efficiency of cache lookups. Here’s how way prediction can reduce the miss rate:

Way Prediction: Modern caches are often set-associative, meaning each set in the cache can have multiple ways (slots) where data can be stored. Way prediction involves guessing which way within the set will hold the requested data, aiming to reduce the time and energy needed to search through all possible ways.

Faster Access Times: By predicting the correct way:
- If the prediction is correct, the cache can quickly access the data, reducing the time spent on cache lookups.
- Faster access times can reduce the penalty of cache misses, indirectly contributing to performance improvement.

Reduced Conflict Misses: Way prediction can help mitigate conflict misses:
- Conflict misses occur when multiple pieces of data compete for the same cache line or set.
- By predicting and distributing data across different ways more effectively, way prediction can reduce the chances of such conflicts, thereby lowering the miss rate.

Question 58

How can we reduce the miss rate using pseudo-associativity

Answer 58

Pseudo-associativity in direct mapped caches: Divide the cache in two banks in a sort of associativity.
 If the bank prediction is correct  Hit time
 If misprediction on the first bank, check the other bank to see if there, if so have a pseudo hit (slow hit) and change the bank predictor
 Otherwise go to the lower level of hierarchy (Miss penalty)

Question 59

What are some of the instruction and data managing compilers optimizations do

Answer 59

Managing Data
a) Merging Arrays: improve spatial locality by single array of compound elements vs. 2 arrays (to operate on data in the same cache block)

b) Loop Interchange: improve spatial locality by changing loops nesting to access data in the order stored in memory (re-ordering maximizes re-use of data in a cache block)

c) Loop Fusion: improve spatial locality by combining 2 independent loops that have same looping and some variables overlap

d) Loop Blocking: Improve temporal locality by accessing “sub-blocks” of data repeatedly vs. accessing by entire columns or rows

Question 60

How can we reduce the miss penalty?

Answer 60

Give priority to reads over writes

Sub-Block placement

Early restart in critical word first

Non-blocking cashes (hit under Miss, miss under miss)

Introducing Second level cache

Merging write buffer (victim cache)

Question 61

How can we give priority to read misses over write misses and what are the drawbacks of this technique

Answer 61

Basic idea: Giving higher priority to read misses over writes to reduce the miss penalty. This is done by introducing a write buffer between CPU and the main memory

Drawback: This approach can complicate the memory access because the write buffer might hold the updated value of a memory location needed on a read miss => RAW hazard through memory.

Question 62

How does sub-blocking works and what are the drawbacks of this technique

Answer 62

Don’t have to load full block on a miss: move sub- blocks

We need valid bits per sub-block to indicate validity

Drawback: no exploiting enough the spatial locality

Question 63

How does the early restart and the critical word first techniques work

Answer 63

Usually the CPU needs just one word of the block on a miss.

Basic idea: Don’t wait for full block to be loaded before restarting CPU (by sending the requested missed word)

Early restart: Request the words in normal order from memory, but as soon as the requested word of the block arrives, send it to the CPU to let the CPU continue execution, while filling in the rest of the words in the cache block;

Critical Word First: Request the missed word first from memory and send it to the CPU as soon as it arrives to let the CPU continue execution, while filling the rest of the words in the cache block. This approach is also called requested word first.

Question 64

How does the non-blocking techniques work and what are the types of it

Answer 64

Non-blocking cache (or lockup-free cache) allows data cache to continue to supply cache hits during a previous miss (Hit under Miss);

“Hit under Miss” reduces the effective miss penalty by working during a miss instead of stalling CPUs on misses
 Requires out-of-order execution CPU: the CPU needs to do not stall on a cache miss: For example, the CPU can continue fetching instructions from I-cache while waiting for D-cache to return the missing data.
 This approach is a sort of “out-of-order” pipelined memory access

“Miss under Miss” may further lower the effective miss penalty by overlapping multiple misses
 Requires multiple memory banks (otherwise cannot support) to serve multiple misses
 Significantly increases the complexity of the cache controller as there can be multiple simultaneous memory accesses
 Pentium Pro allows 4 outstanding memory misses

Question 65

How do we improve hit time

Answer 65

Via small and simple L1 cash

By avoiding address translation. If index is physical part of address, can start tag access in parallel with address translation so that can compare to physical tag

Fast Hit Times Via Pipelined Writes
Basic idea: To pipeline Tag Check and Update Cache Data as separate stages: current write tag check & previous write cache update
The “Delayed Write Buffer”; must be checked on reads; either complete write or read from write buffer

Via Small Sub-blocks for Write Through