Question

2. (15 points total, 3 pts each) Let’s say that we have a 4-way set associative cache. The cache has 16 sets in total. Main memory consists of 16K blocks of 16 words each, and word addressing is used. a. Show the address format that is used to map main memory address to the cache. Include the appropriate fields and their sizes. For the remaining questions, assume that we have the following situation: We have a program that loops 6 times from location 1209810 in memory to location 1238610. In other words, think of this as an assembly language program that runs from the opcode at location 12098 to the opcode at location 12386, then loops back to location 12098. It does 6 such iterations in total (the original pass, plus 5 more loops). You can assume that the cache is initially empty. b. At the end of the first iteration, how many blocks of memory are stored in the cache? c. At the end of the first iteration, how many of these blocks are stored in (i) Set 2 (ii) Set 5 d. At the end of the first iteration, what is the hit ratio for the cache? The hit ratio should be expressed as a percentage (e.g., 85.67% or 96.35%) e. At the end of all 6 iterations, what is the hit ratio for the cache?

Answer 1

Given

• 4-way set associative cache
• cache has 16 sets
• Main memory consists of 16K blocks
• 16 words per block

a) Show the address format that is used to map main memory address to the cache.

Main memory consists of 16K blocks each block with 16 words => 2^18 words

=>  address has 18 bits

cache has 16 sets in total and it is 4-way set associative cache

Number of bits to represent set = 2^4/2^2

= 2^2

=> 2 bits

16 words per block  

Number of bits to represent block = 2^4

=> 4 bits

Number of bits to represent tag = 18 - 2 - 4

= 12 bits

address format => (0-3) bits represent word in block

(4-5) bits represent set in cache

(6-17) bits represent tag   

Now, there is a program that runs from the opcode at location 12098 to the opcode at location 12386, then loops back to location 12098 six times.

cache is initially empty and on a request, the entire block is brought into the cache

12098 - (000010111101000000)₂ placed @set 0, line 0 => words from 12099 to 12113 are also brought inside ( referring these will always be a cache hit => for one block there is 13 cache hits)

12114 - (000010111101010010)₂   placed @set 1, line 0 => words from 12115 to 12129 are also brought inside

12130 - (000010111101100010)₂   placed @set 0, line 1 => words from 12131 to 12145 are also brought inside

12146 - (000010111101110010)₂   placed @set 3, line 0 => words from 12146 to 12161 are also brought inside

12162 - (000010111110000010)₂   placed @set 0, line 2 => words from 121463 to 12177 are also brought inside

12178 - (000010111110010010)₂   placed @set 1, line 1 => words from 121479 to 12193 are also brought inside

12194 - (000010111110100010)₂   placed @set 1, line 2 => words from 12195 to 12209 are also brought inside

12210 - (000010111110110010)₂   placed @set 3, line 1 => words from 12211 to 12225 are also brought inside

12226 - (000010111111000010)₂   placed @set 0, line 3 => words from 12227 to 12241 are also brought inside

12242 - (000010111111010010)₂   placed @set 1, line 3 => words from 12243 to 12257 are also brought inside

12258 - (000010111111100010)₂   placed @set 2, line 0 => words from 12259 to 12273 are also brought inside

12274 - (000010111111110010)₂   placed @set 3, line 2 => words from 12275 to 12289 are also brought inside

12290 - (000011000000000010)₂   placed @set 0, line 0 => words from 12291 to 12305 are also brought inside

12306 - (000011000000010010)₂   placed @set 1, line 0 => words from 12307 to 12321 are also brought inside

12322 - (000011000000100010)₂   placed @set 2, line 1 => words from 12323 to 12337 are also brought inside

12338 - (000011000000110010)₂   placed @set 3, line 3 => words from 12339 to 12353 are also brought inside

12354 - (000011000001000010)₂   placed @set 0, line 1 => words from 12355 to 12369 are also brought inside

12370 - (000011000001010010)₂   placed @set 2, line 2 => words from 12371 to 12385 are also brought inside

12386 - (000011000001100010)₂   placed @set 2, line 3 => words from 12387 to 12401 are also brought inside

b) At the end of the first iteration, how many blocks of memory are stored in the cache?

Set 0 - holds 4 blocks

Set 1 - holds 4 blocks

Set 2 - holds 4 blocks

Set 3 - holds 4 blocks

all sets are full => cache contains 16 blocks of memory

c) At the end of the first iteration, how many of these blocks are stored in

(i) Set 2 - 4 blocks

(ii) Set 5 - 4 blocks

d) At the end of the first iteration, what is the hit ratio for the cache?

18 + 1 complusory misses

Whenever there is a miss, a block is placed inside cache => 15 other words can be referenced directly

=> 15 hits/block

Number of reference = 18*16 + 1 = 289

Number of hits = 18*15 = 270

Hit ratio = 270/289 = 0.9342

= 93.42%