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

.Now,when 2nd time the sequence will be accessed,then the oldest block for the all 4 sets will not be found

what does the above line mean?

1st time 64 blocks are present aand from that 4 are replaced considering the oldest ones

lets assume block 1,2,3,4 is replaced

now second time among the blocks present the least used can be replaced...assuming block 5,6,7,8 right?

what is brought from memory to cache again?

it is not that only blocks that were replaced for the first time are oldest

among the blocks present in cache the oldest can be usd right?

i dont know if i have confused myself

u have explained it very beautifully but still somewhere am getting choked up

---

keep in mind that it is set associative cache.

you said that " lets assume block 1,2,3,4 is replaced ".it is not possible.because a set in cache contains 4 blocks.so block numbers that will be replaced in 1st fetch sequence will be 0,4,8,12.so when 2nd fetch sequence will occur,then these blocks can't be found in cache.so they will be fetched from MM and will be placed by replacing block numbers 1,5,9,13 respectively.

---

y not replace blocks 16,20,24,28 ?

and this will be present in cache right?

---

because word number 0 will be resided in block number 0 and it will map set number 0 in cache memory.as it is oldest block so it will be replaced first.

---

during access at second time , 4 sets wont be found therefore bring from memory and will cause a  miss

it will cause 4 misses right? how 5?

if possible please can u take a small example with small numbers and a representation of the block with the replacement as a diagram and explain?

would be grateful

thanku in advance

---

4 blocks,which were there in the set previously,for all of them no hit will be occurred in second access.so totally 4 miss and one extra miss will occur because each of the (68-64)=4 blocks will be placed in each of the 4 sets.

---

thank you :)

---

@Sambit Kumar , everything is perfect in your answer,But one thing as here BLOCK SIZE Of main memory is not given, so by default we are taking the cache block size =MM block size,correct?

---

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?