Question

32 bytes of memory. 16 bytes of 2-way setassociative cache, where blocks can go anywhere within the set. Block is 4 bytes, set in cache is two blocks. Populate memory starting with 0-9, then upper case letters. Hint- with full associativity in the set: each block has its own set of Tag bits in the cache. Memory is not organized by sets, though blocks get assigned to sets, and load in the cache per set. A) Complete: Bits in Address = # bytes in cache = # bytes in set = # of sets in cache = # of blocks in memory = B) Addressing: Tag | Set |block offset ____ | ____ | ____ C) Draw the diagrams of cache and memory, with appropriate labels as per example. D) Load cache with 1st 2nd 5th 8th blocks. E) CPU generates address 10011. If this is a hit, what character is stored at that location?

Answer 1

Given Memory Size is = 32 bytes and

a 16 bytes of 4-way set-associative cache.

Block Size is = 2 bytes implies

Number of blocks in Main Memory is = N = 32 bytes / 2 bytes = 16.

Number of blocks in Cache Memory is = M = 16 bytes / 2 bytes = 8.

Number of sets in Cache Memory is = S = 8 / 4 = 2.

Here kth block of Main Memory will be placed in k mod S set of cache implies

k mod 2 set of the cache.

Main Memory will be as below,

Given addresses 00001 00010 01000 01011 01100 11011 11100 11111,

00001 address is in block 0 of main memory and it will be placed in 0 mod 2 = 0 (Set 0).

00010 address is in block 1 of main memory and it will be placed in 1 mod 2 = 1 (Set 1).

01000 address is in block 4 of main memory and it will be placed in 4 mod 2 = 0 (Set 0).

01011 address is in block 5 of main memory and it will be placed in 5 mod 2 = 1 (Set 1).

01100 address is in block 6 of main memory and it will be placed in 6 mod 2 = 0 (Set 0).

11011 address is in block 13 of main memory and it will be placed in 13 mod 2 = 1 (Set 1).

11100 address is in block 14 of main memory and it will be placed in 14 mod 2 = 0 (Set 0).

11111 address is in block 15 of main memory and it will be placed in 15 mod 2 = 1 (Set 1).

Hence cache Memory will be as below,

Given CPU generates the address 11010, this address is there in

Block 6 of the cache and Hence this is a HIT.

Character at this address is Q