Question

Computer archieture

1. Assume that the cache size is 512kB, and each cache line is 128 Bytes.

1. If it’s a 4-way associative cache, how many sets are there? If it’s a 2-way associative cache, how many sets are there?
2. Let’s assume the cache is initially empty, and LRU policy is used for cache line replacement. If the following memory blocks are accessed:

Mem-block # 7, 1031, 2055, 4103, 1031, 7, 2055, 3079, 1031, 3079

What is the cache hit/miss rate if the cache is 4-way associative? Put “Hit” or “Miss” in the blanks in the table below. (5%)

7	1031	2055	4103	1031	7	2055	3079	1031	3079

3. Given the same conditions as the question above, what is the cache hit/miss rate if the cache is 2-way associative? Put “Hit” or “Miss” in the blanks in the table below. (5%)

7	1031	2055	4103	1031	7	2055	3079	1031	3079

Answer 1

Cache size : 512 kB= 2^19 bytes

Size of cache line : 128Bytes=2^7bytes

Number of cache lines= 2^19/2^7=2^12

With 4-way associative cache, i.e. 4 cache lines per set, number of sets= 2^12/2^2=2^10 = 1024 sets

With following memory blocks 7, 1031, 2055, 4103, 1031, 7, 2055, 3079, 1031, 3079:

To place a block in a particular set following formula is used

Set j= (memory block number) mod ( number of sets)

For memory block 7, it will be placed in set:

7 mod 1024= 7,

Memory block 7 will be allocated in one of the 4 lines of set 7 which are empty.

1031 mod 1024=7,

Memory block 1031 will be allocated in one of the 3 lines of set 7 which are empty.

2055,4103 memory blocks are also allocated to the set 7 in the rest of two lines that are empty.

1031,7,2055 are next following blocks that are refered which are present cache resulting in hit.

3079 mod 1024 =7, as the set is full, one of the block has to be replaced using LRU policy to place 3079. As 4103 is the leat recently used block, it selected for replacement.

1031,3079 are the blocks next refered which are already present in cache resulting in hit.

7	1031	2055	4103	1031	7	2055	3079	1031	3079
M	M	M	M	H	H	H	M	H	H

Therefore miss rate = 5/10=0.5

Hit rate=1-0.5=0.5

B. With 2-way set associative:

All the calculations till number of cache lines are same.

But as it is 2-way set, there will be only 2 lines per set. Therefore number of sets will be: 2^12/2=2^11 sets= 2048 sets.

The formula for finding the set for a memory block will become:

i mod 2048, where i is memory block number

7 mod 2048=7, placed in set 7,

1031 mod 2048=1031, placed in set 1031

2055 mod 2048=7, placed in set 7

4103 mod 2048=7, has to be placed in set 7. But all the 2 lines of set 7 are occupied. Hence using LRU block 7 which is least recently used is replaced with block 4103.

1031 is already present in set 1031,

7 is a miss, by using LRU, block 2055 is replaced by 7.

Again 2055 is a miss, by using LRU, block 4103 is replaced by 2055.

3079 mod 2048=1031, placed in set 1031.

Next blocks refered are 1031, 3079 which are already present in set 1031.

7	1031	2055	4103	1031	7	2055	3079	1031	3079
M	M	M	M	H	M	M	M	H	H

Miss rate= 7/10=0.7

Hit rate=1-0.7=0.3