Only Part B, answered but need further explanation about the answer. Question on

Question

Only Part B, answered but need further explanation about the answer.

Question on the Answer: How does someone get 5*7 + 3 hits? And how does someone iterate times 2 and 3 for 5*8+4 hits? Also how do we know which are hits and misses, such as how do we know there are 6 misses?

Answer:

First iteration of the loop:

Address 8 is a miss, then entire block brought into set 1. 9-15 are then hits. 16 is a miss, entire block brought into set 2, 17-23 are hits. 24 is a miss, entire block brought into set 3, 25-31 are hits. 32 is a miss, entire block brought into set 0, 33-39 are hits. 40 is a miss, entire block brought into set 1. (we do not have to throw out the block with address 8 as this is 2-way set associative) 41-47 are hits. 48 is a miss, entire block brought into set 2, 49-51 are hits. For the first iteration of the loop we have 6 misses and 5*7+3 hits or 38 hits. On the remaining iterations we have 5*8+4 hits or 44 hits each, for 88 more hits. Therefore we have 6 misses and 126 hits for a hit ratio of 126/132 or 95.45%

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.

Explanation / Answer

b. In part a of the question, you have got 9 tag bits,2 index bits and 3 offset bits. So these bits are

tag bits| index bits| offset bits

I.e. The lower bits are offset bits followed by index bits and then tag bits.

Our memory access starts at address 8 with 3 offset bits. This cache line reference will be address 8 to address 15(1000-1111) in binary.

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, it's 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 sure 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 shoul 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 association).

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,

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

=126/132

Related Questions

Navigate

• Browse (All)
• Browse O
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.