Mapping Strategies

Question

A 2-way set associative cache consists of four sets. Main memory contains 2K blocks of eight words each.

 a) Show the main memory address format that allows us to map addresses from main memory to cache. Be sure to include the fields as well as their sizes.

b) Compute the hit ratio for a program that loops 3 times from locations 8 to 51 in main memory. You may leave the hit ratio in terms of a fraction.

Hello Sir, I am write now solving sums from "The essentials of Computer architecture " I got this sum . and there is no solution provided i just wanna ask you to check this

Solution :

No of lines in a set=2
No of set in Cache = 4
Block size=8 words

So, Size of each cache= No of set* No of line in set * Block Size= 8*4*2=64 Words

Size of MM= no of block in main memory * size of each block=(2^11)*(2^3)= 2^14 words

Bits used to represent Physical address = 14 bits

Field of Cache address will be
1. word offset = 3 bits
2. index bits = 2 bits
3.Therefore no of bits used to represent Tag field =(14-(3+2)) = 9 bits.

 

Now the solution for part b

Since the size of both memory is expressed in words

We have a cache size/ capacity = 64 words and Size of Main Memory as( 2 ^ 14 words )

And since the loop says it starts from location 8 to 51 then . No of elements that will be encountered = (51-8+1)= 44 which is equivalent for running i from 0 to 43 times (for 44 words )

Since they have asked for 3 iteration,

we know that size of cache= 64 words

And the required data that we have is 44 words

Out of these 44 words there would be 22 words which would be mapped to set 0 and 22 words which would be mapped to Set 1

Now in each Set , we have 2 lines and Each block has a size of 8 words ,

So in 16 words we have would have 2 miss

And so in reamining in (22-16) words we  would have 6 words . to accomodate these 6 words again 1 block need to replaced

So total miss in 1 set in first iteration is 3 miss

Similarly total miss in second  set in first iteration = 3 miss

Total no of miss in first iteration = 6 miss

While in second iteration there would be again need of replacing 1 block to (first 8 words ) rest would be hit till and then again 1 miss for (last 6 words ) this is just for 1 set

so total no of miss in second iteration=4 (both sets )

And similarly Total no of miss in third set = 4

And miss ratio would be equal to = (6+4+4)/(44+44+44)= 14/132.

Is this correct ? Please help . i am sorry to write such a big content . But this question need and to show my way of approaching towards sums :)

Answer 1

Your first part is correct. But b part is not.

Actually in first part we got 9 tag bits, 2 index bits and 3 offset bits. So, these bits are like these:
tag bits | index bits | offset bits

That is, the lower bits are offset bits followed by index bits and then tag bits.

Our memory access starts from address 8. With 3 offset bits, this cache line reference will be from address 8 to address 15 (1000 - 1111 in binary).  Say this cache line goes to cache set A during the memory access for address 8. Next 7 accesses are cache hits. When address 16 is accessed, its cache line goes to set B and not set A because after offset comes the index/set bits so the set changes (this is made so that spacial locality won't reduce cache hits). Now, all accesses till 23 are hits and 24 will be a miss and cache line for 24 goes to set C. Similarly, cache line for 32 goes to set D. Now, for cache line of 40, it should go to set A. But it won't replace the cache line at set A, as each set has space for 2 cache lines (2-way associative). Similarly cache line of address 48 goes to set B. And that is the last cache miss in iteration 1. So, we have 6 cache misses and 38 cache misses in iteration 1. For iterations 2 and 3, all are cache hits. So,

hit ratio = (38 + 44 + 44) / (3 * 44)

= 126/132

Comments

oh Ya i got it . Thank you so much Sir :) I got your explanation.I did by making diagram . thank you so much :D .I didnt took into consider the offset bit only as a result i was mapping address from 16 to 23 on line 2 of set one only . I got my mistake :)

---

@arjun sir 1.it is 38 hit

                  2. why u hv not concidered the line2 of set 1 for address 16 to 23.this thing is not clear to me plz help