EEE230 Online
Cache Basics Practice Problems
1. The following block numbers are accessed. These are decimal block numbers. The
word and byte offsets are not included (This is the same as the example in the lecture and
the book).
17, 19, 12, 13, 15, 14, 17, 11, 19, 15
a. A direct mapped cache holds 4 blocks. For the block numbers above, give the
i. index into the cache (in binary)
ii. the tag (in binary)
b. Draw the cache as it would appear at the end of the sequence. Include the valid
bit in your answer.
c. What is the hit ratio?
2. Repeat the above question, this time with a direct mapped cache of 8 blocks.
3. Given the 32 bit address for MIPS, determine the number of bits needed for the byte
offset, block offset, cache index and tag for each of the following caches. See the
Intrinsity FastMATH cache as an example.
a. Direct mapped cache of 256 8-word blocks
b. Direct mapped cache of 1024 4-word blocks
c. Direct mapped cache of 512 16-word blocks.
Sample answers
1. 4 block cache
a.
Block Index Tag
17 01 100
19 11 100
12 00 011
13 01 011
15 11 011
14 10 011
17 01 100
11 11 010
19 11 100
15 11 011
b.
Index Valid Tag Data
00 1 011 M[01100]
01 1 100 M[10001]
10 1 011 M[01110]
11 1 011 M[01111]
c. 0%
2. 8 block cache
a.
Block Index Tag
17 001 10
19 011 10
12 100 01
13 101 01
15 111 01
14 110 01
17 001 10
11 011 01
19 011 10
15 111 01
b.
Index Valid Tag Data
000 0
001 1 10 M[10001]
010 0
011 1 01 M[10011]
100 1 01 M[01100]
101 1 01 M[01101]
110 1 01 M[01110]
111 1 01 M[01111]
c. 20%
3. .
a. Byte offset 2 bits, block offset 3 bits, cache index 8 bits, tag 19 bits
b. Byte offset 2 bits, block offset 2 bits, cache index 10 bits, tag 18 bits
c. Byte offset 2 bits, block offset 4 bits, cache index 9 bits, tag 17 bits