Question

1. A direct-mapped cache consists of 8 blocks. Byte-addressable main memory contains 4K blocks of 8 bytes each. Access time for the cache is 22ns, and the time required to fill a cache slot from main memory is 300ns. (This time allows us to determine the block is missing and bring it into cache.) Assume a request is always started in parallel to both cache and to main memory(so if it is not found in cache, we do not have to add this cache search time to the memory access). If a block is missing from cache, the entire block is brought into the cache and the access is restarted. Initially, the cache is empty.  You MUST show your work for all parts of this problem to receive full credit!
   1. 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.
   2. Compute the hit rate for a program that loops 4 times from locations 0x0 to 0x43 (address 0 hex to address 43 hex).
   3. Compute the effective access time for this program.

Redo the previous problem, assuming a 2-way set associative cache. If a cache set is full and a block has to be removed to make room for another, remove the block that has been in cache the longest (FIFO).

Answer 1

2-Way Set Associative Cache

Number of blocks in cache = 8 = 2³.

Number of blocks in Main memory = 4K = 2¹²

Block size = 8 bytes = 2³.

Cache access time =  22 ns

Page fault time = 300 ns.

a)

Main memory size = 2¹² * 2³ = 2¹⁵ so address = 15 bits

Number of sets in cache = 2³ / 2 = 2²

Byte offset = 3 bits (required to access each byte in the block)

Set offset = 2 bits (required to access each set in cache)

Tag = 15-2-3= 10 bits

Main Memory Address = Tag(10 bits) Set Offset (2 bits) Byte Offset(3 bits)

b)

Loop runs from 0x0 to 0x43 (67 in decimal)

Each block of memory contains 8 bytes. So first time miss will happen for starting address of block but subsequent 7 addresses will be hit. Please note that number of cache blocks are 8 divided into 4 sets. Each set will have two blocks.

If particular set is full then we remove the block in FIFO order.

Pass 1 of Loop

Main Memory Block	Addresses	Cache (Set, Block)	Number of Misses	Number of Hits
0	0x0 - 0x7	0, 0	1	7
1	0x8 - 0xF	1, 0	1	7
2	0x10 - 0x17	2, 0	1	7
3	0x18 - 0x1F	3, 0	1	7
4	0x20 - 0x27	0, 1	1	7
5	0x28 - 0x2F	1, 1	1	7
6	0x30 - 0x37	2, 1	1	7
7	0x38 - 0x3F	3, 1	1	7
8	0x40 - 0x43	0, 0	1	3

Pass 2 of Loop

Main Memory Block	Addresses	Cache (Set, Block)	Number of Misses	Number of Hits
0	0x0 - 0x7	0, 1	1	7
1	0x8 - 0xF	1, 0	0	8
2	0x10 - 0x17	2, 0	0	8
3	0x18 - 0x1F	3, 0	0	8
4	0x20 - 0x27	0, 0	1	7
5	0x28 - 0x2F	1, 1	0	8
6	0x30 - 0x37	2, 1	0	8
7	0x38 - 0x3F	3, 1	0	8
8	0x40 - 0x43	0, 1	1	3

Pass 3 of Loop

Main Memory Block	Addresses	Cache (Set, Block)	Number of Misses	Number of Hits
0	0x0 - 0x7	0, 0	1	7
1	0x8 - 0xF	1, 0	0	8
2	0x10 - 0x17	2, 0	0	8
3	0x18 - 0x1F	3, 0	0	8
4	0x20 - 0x27	0, 1	1	7
5	0x28 - 0x2F	1, 1	0	8
6	0x30 - 0x37	2, 1	0	8
7	0x38 - 0x3F	3, 1	0	8
8	0x40 - 0x43	0, 0	1	3

Pass 4 of Loop

Main Memory Block	Addresses	Cache (Set, Block)	Number of Misses	Number of Hits
0	0x0 - 0x7	0, 1	1	7
1	0x8 - 0xF	1, 0	0	8
2	0x10 - 0x17	2, 0	0	8
3	0x18 - 0x1F	3, 0	0	8
4	0x20 - 0x27	0, 0	1	7
5	0x28 - 0x2F	1, 1	0	8
6	0x30 - 0x37	2, 1	0	8
7	0x38 - 0x3F	3, 1	0	8
8	0x40 - 0x43	0, 1	1	3

So Hit ratio = Number of hits / total access (hit+miss)

= 254/272

= 0.94485 = 93.38%

c)

Effective access time = Hit rate * cache access time + miss rate * page fault time

= (254/272) * 22 + (18/272)*300

= 40.39 ns