Do problem 5.3.1 from the book.
The list of addresses given in the problem are word addresses and
in are decimal (not hexadecimal). They are not
byte addresses. For example, for problem 5.3.1a
the first address given is 3. This corresponds to byte address
12ten or 1100 (note the two final zeros).
So you don't need to chop off the two zeroes on the least
significant bits because the book has already done it for you.
To get you started:
Answer to part A. The first thing to notice is that since we have one word blocks and no address is repeated then there are zero cache hits. The other way to say this is that this address sequence exhibits no temporal locality.
Addressten Binarytwo Tagten Blockten Hit/Miss
3 00000011 0000 3 Miss
180 10110100 1011 4 Miss
43 00101011 0010 11 Miss
2 00000010 0000 2 Miss
191 10111111 1011 15 Miss
88 01011000 0101 8 Miss
190 10111110 1011 14 Miss
14 00001110 0000 14 Miss
181 10110101 1011 5 Miss
44 00101100 0010 12 Miss
186 10111010 1011 10 Miss
253 11111101 1111 13 Miss
Answer to part B. By scanning the address sequence we do see that some addresses are repeated - but it doesn't mean that they will be cache hits because they may have been kicked out of the cache before the address is used again. So we have to trace the addresses.
Addressten Binarytwo Tagten Blockten Hit/Miss
21 00010101 0001 5 Miss
166 10100110 1010 6 Miss
201 11001001 1100 9 Miss
143 10001111 1000 15 Miss
61 00111101 0011 13 Miss
166 10100110 1010 6 Hit
62 00111110 0011 14 Miss
133 10000101 1000 5 Miss
111 01101111 0110 15 Miss (darn, kicks out address 143)
143 10001111 1000 15 Miss (because of the above reference)
144 10010000 1001 0 Miss
61 00111101 0011 13 Hit
Generating the above tables was tedious. While it is beneficial for you to grunge through this by hand, I wrote a Python program to generate the tables above. Most of the code is for getting it to format and print nicely.
Do problem 5.3.2a the same exercise as above but for a direct mapped cache with two-word blocks and a total of 8 blocks.
Answer to 5.3.2a. Hint: How did I modify my Python program above to generate the data below?
Addressten Binarytwo Tagten Blockten Offset Hit/Miss
3 00000011 0000 1 1 Miss
180 10110100 1011 2 0 Miss
43 00101011 0010 5 1 Miss
2 00000010 0000 1 0 Hit (brought in from address 3 reference)
191 10111111 1011 7 1 Miss
88 01011000 0101 4 0 Miss
190 10111110 1011 7 0 Hit (brought in from address 191 references)
14 00001110 0000 7 0 Miss (kicks out 190 and 191)
181 10110101 1011 2 1 Hit (brought in from address 180 reference)
44 00101100 0010 6 0 Miss
186 10111010 1011 5 0 Miss
253 11111101 1111 6 1 Miss
Answer to 5.3.2b.
Addressten Binarytwo Tagten Blockten Offset Hit/Miss
21 00010101 0001 2 1 Miss
166 10100110 1010 3 0 Miss
201 11001001 1100 4 1 Miss
143 10001111 1000 7 1 Miss
61 00111101 0011 6 1 Miss
166 10100110 1010 3 0 Hit (previous reference to address 166)
62 00111110 0011 7 0 Miss (kicks out addresses 142 and 143)
133 10000101 1000 2 1 Miss (kicks out addresses 20 and 21)
111 01101111 0110 7 1 Miss (kicks out addresses 62 and 63)
143 10001111 1000 7 1 Miss (got kicked out way back)
144 10010000 1001 0 0 Miss
61 00111101 0011 6 1 Hit (still in cache)
Using the same set of addresses from the above exercises identify whether the access is a hit or miss for an 8 block (one word per block) fully associative cache. Assume LRU replacement policy.
For part A (the address sequence 3, 180, .etc.) there are no hits because there is no temporal locality and the cache is made up of single word blocks.
For part B there is some temporal locality so we need to trace it.
21 miss 166 miss 201 miss 143 miss 61 miss 166 hit 62 miss 133 miss 111 miss 143 hit 144 miss (kicks out address 21 because that is the oldest) 61 hit
Using the same set of addresses from the above exercises identify the set and whether the access is a hit or miss for a 2-way set associative cache that has 16 one word blocks (hence 8 sets). Assume LRU replacement policy.
Answer to Part A. There are no hits because there is no temporal locality.
Address Set Hit/Miss 21 5 Miss 166 6 Miss 201 1 Miss 143 7 Miss 61 5 Miss 166 6 Hit 62 6 Miss 133 5 Miss 111 7 Miss 143 7 Hit 144 0 Miss 61 5 Hit
Do problems 5.4.1 - 5.4.3 part a only.
Oops. I put the answers for part B in here as well.
Answer 5.4.1 part A: This problem is worded poorly in the book. Bits 0 through 4 are the offset in a line but remember that bit 0 and bit 1 are always 0, so bits 2-4 contain the offset. So that means there are $2^3 = 8$ words in a line. We also need to store the tag on a line which is 22 bits and also the valid bit, which is then $(22 + 1)/32 = .71875$ words. But I think the book was just looking for the answer 8, not 8.71875.
Answer 5.4.1 part B: Same argument as above. There are 4 offset bits so 16 words on a line. Adding the tag and valid bit it is $16 + (20+1)/32 = 16.65625$ words/line.
Answer 5.4.2 part A: There are 5 index bits so there are $2^5=32$ blocks times 8 entries/block, or 256 entries.
Answer 5.4.2 part B: There are 6 index bits so there are $2^6=64$ blocks times 16 entries/block, or 1K entries.
Answer 5.4.3 part A: For each line the tag and valid bits are overhead, so we have for one cache block $8(32) = 256$ data bits and $23$ overhead bits. So $(256 + 23)/256 = 1.09$.
Answer 5.4.3 part B: For each line the tag and valid bits are overhead, so we have for one cache block $16(32) = 512$ data bits and $21$ overhead bits. So $(512 + 21)/512 = 1.04$.