Associativity usually improves the miss ratio, but not always. Give a short seri

Question

Associativity usually improves the miss ratio, but not always. Give a short series of address references for which a two-way set-associative cache with LRU replacement would experience more misses than a direct-mapped cache of the same size. Suppose a computer's address size is k bits (using byte-addressing), the cache size is S bytes, the block size is B bytes, and the cache is A-way set-associative. Assume that B is a power of 2, so B=2_b. Figure out what the following quantities are in terms of S, B, A, b, and k. the number of sets in the cache, the number of index bits in the address, and the number of bits needed to implement the cache.

Explanation / Answer

Let us assume a cache with 8 four byte blocks. Now consider the following access request

0, 2, 4, 0, 2, 4, 0, 2, 4,......

All addresses map to set 0 in the 2-way set-associative cache with LRU replacement policy and will evict each other.
There will be no hits and all miss in the 2-way set-associative cache.

In direct-mapped cache, addresses 0 and 4 map to set 0 and will evict each other, however, address 2 maps to set 2 and after the initial miss will remain in the cache. Hence the direct-mapped cache will observe 1 hit every three accesses. Thus it will perform better than 2-way set associative cache.

e) Capacity of cache = S

Number of blocks = Capacity / block size = S / 2b

Number of sets = Number of blocks / number of ways = S / (2b * A)

Number of index bit = log2 S - b - log2 A

Width of tag field = (k - log2(S-A) + b - b) = k - log2(S-A)

Number of bits to store tag field = (k - log2(S-A) ) * (S / 2b)

Bits for valid and dirty bits = 2* (S / 2b)

Total number of bits needed = (S / 2b) * (k - log2(S-A) + 2)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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