Suppose we have a computer that uses a memory address word size of 8 bits. This
ID: 3824355 • Letter: S
Question
Suppose we have a computer that uses a memory address word size of 8 bits. This computer has a 16-byte cache with 4 bytes per block. The computer accesses a number of memory locations throughout the course of running a program. Suppose this computer uses direct-mapped cache. The format of a memory address as seen by the cache is shown here: The system accesses memory addresses (in hex) in this exact order: 6E, B9, 17, E0, 4E, 4F, 50, 91, A8, A9, AD, 93, and 94. The memory addresses of the first four accesses have been loaded into the cache blocks as shown below. (The contents of the tag are shown in binary and the cache "contents" are simply the address stored at that cache location.) a) What is the hit ratio for the entire memory reference sequence given above? b) What memory blocks will be in the cache after the last address has been accessed?Explanation / Answer
Given
Format of memory address:
Tag
4 bits
Block
2 bits
Word
2 bits
Memory address to access:
6E, B9, 17, E0, 4E, 4F, 50, 91, A8, A9, AB, AD, 93, and 94
First four access of address:
Tag Cache Contents
Contents (represented by address)
Block 0
1110
E0
E1
E2
E3
Block 1
0001
14
15
16
17
Block 2
1011
B8
B9
BA
BB
Block 3
0110
6C
6D
6E
6F
a)
How we determine hit or miss is
First we check for block id if it exist in cache we check for address if it exist in block we consider it as Hit else we consider it as miss.
In our case for first address the address is divided as follows 6E => 01101110 è where first four bits represent tag bits and next 2 block bits and next 2 offset bits
So for 6E => 0110 => tag id
11 => block 3
10 => position in block i.e., 3 rd position
In this way we check for all addresses if they already exist in cache we consider as hit else we consider as miss.
if we get miss we load that address into cache as follows:
we load that address into that consecutive location into block as calculated above and their consecutive address loaded into cache as address of pairs of 4 as shown above
Address
Hit or Miss
6E
Miss, brought into Block 3 with tag 0110 (as shown)
B9
Miss, brought into Block 2 with tag 1011 (as shown)
17
Miss. brought into Block 1 with tag 0001 (as shown)
E0
Miss, brought into Block 0 with tag 1110 (as shown)
4E
Miss, brought into Block 3 with tag 0100
4F
Hit
50
Miss, brought into Block 0 with tag 0101
91
Miss, brought into Block 0 with tag 1001
A8
Miss, brought into Block 2 with tag 1010
A9
Hit
AB
Hit
AD
Miss, brought into Block 3 with tag 1010
93
Hit
94
Hit
Hit Ratio: 4 hits out of 14 accesses so hit ration is (4/14)*100 = 28.6%
b)
Cache blocks after last address has been accessed
Tag Cache Contents
Contents (represented by address)
Block 0
1001
90
91
92
93
Block 1
1001
94
95
96
97
Block 2
1010
A8
A9
AA
AB
Block 3
1010
AC
AD
AE
AF
Tag
4 bits
Block
2 bits
Word
2 bits