Carl-Hamacher

Question

A computer system has a main memory consisting 1M 16 bit-words.It also has a 4K-word cache organized in the block-set-associative manner,with 4 blocks per set and 64 words per block.

a)assume that the cache is initially empty.Suppose that the processor fetches 4352 words from locations 0,1,2,...,4351,in that order.It then repeats this fetch sequence nine more times,If the cache is 10 times faster than the main memory,estimate the improvement factor resulting from the use of the cache.Assume that LRU algorithm is used for block replacement.

ans is: 2.15

Answer 1

cache  size=4K word=2¹² words

Block size=64 words=2⁶ words
So, number of blocks=2¹²/2⁶=2⁶=64

Processor fetches  4352 words contiguously

So, number of blocks required to access all word=4352/64=68

so,(68-64)=4 blocks need to be replaced in each 9 accesses using LRU policy.Now consider the 1st time when blocks are being fetched in cache from MM.As LRU is used,so in the particular set(in which the block will be placed),the oldest block will be replaced.This will be done for all the 4 sets.Now,when 2nd time the sequence will be accessed,then the oldest block for the all 4 sets will not be found.So this block will be fetched from MM and it will be kept in the set by replacing the 2nd oldest block.So,for 2nd oldest block,miss will occur.Then this will be fetched and will be placed by replacing 3rd oldest block.This process will continue until the 5th block for the set is placed.So for all 5 blocks there will be miss.So total miss in each of the 9 accesses=(5*4)=20

so total cache misses=68+(9*20)=248

so,total MM word accesses for this miss=248*64=15872

total cache accesses=(9*(68-20)*64)=27648

if cache was not present,then total MM word access would be=4352*9=40788

so improvement factor=(40788*10*cache access time) / ((15872*10*cache access time)+(27648*cache access time))=2.1

Comments

cache block(also called as cache line)  size will always be equal to MM block size.

---

No, Actually that's not the case.

---

If cache wasn’t there then the total MM accesses would become 4352*10 right? But why is it 4352*9 here? Can someone explain?

Answer 2

Block size 64 words=$2^{6}$ words

cache  size=$2^{12}$

So, number of blocks=$\frac{2^{12}}{2^{6}}=2^{6}$

Number of sets=$\frac{2^{6}}{2^{2}}=2^{4}$

Processor fetches =4352 words

So, number of blocks required to access all word in one time = $\frac{4352}{64}=68$

One tome cache can access 64 blocks

So, last 4 blocks we need to access using LRU.

So, 1st time miss all 68 blocks.

Now, 9 more time need to access.

2nd time miss $4\times 5=20$ using LRU replacement.

So, like that total miss $68+20\times 9=68+180=248$

Comments

How from the 2nd-time miss, 20 came. Can u please explain?

---

@srestha maam,

Can you please explain how 20 misses are possible after 2^nd time. I am not understanding this only.

@venkat_sirvisetti Sir have you got it?