Winter 2003 Exam 2 Solutions
----------------------------
1 a. F
1 b. F
1 c. T
1 d. F
1 e. F

2. e
3. d
4. d
5. c (32 byte line size => set size = 32 => block size = 32/4 = 8 bytes.
      #sets = 1 MB/32 = 215. therefore, 3 bits for block offset, 15
       bits for set index => 32 - (3 + 15) = 14 bits for tag.
6. d
7. b
8. b (assuming that clock time does not change)
9. d
10. a
  For A, CPI = 1 + 0.25*3 = 1.75, Time per insn = 1.75(T) = 1.75T
  For B, CPI = 1 + 0.25*2 = 1.50, Time per insn = 1.5(1.5T) = 2.25T
  For C, CPI = 1 + 0.25*1 = 1.25, Time per insn = 1.25(1.75T) = 2.19T

For questions 11, 12, 13, assume that the branch is taken. (it is
unclear if the question intends this. but this is the only way to get
one of the provided answer options.

11. e

lw r1, 0(r2)    WB in cycle 5
addi r1, r1, 1  WB in cycle 8
sw 0(r2), r1    WB in cycle 11
addi r2, r2, 4  WB in cycle 12
sub r4, r3, r2  WB in cycle 15
beqz r4, L1     WB in cycle 18
add r1, r2, r3
L1:

NOTE: if branch was NOT taken, then it would require 22 cycles

12. d

lw r1, 0(r2)    WB in cycle 5
addi r1, r1, 1  WB in cycle 7
sw 0(r2), r1    WB in cycle 8
addi r2, r2, 4  WB in cycle 9
sub r4, r3, r2  WB in cycle 10
beqz r4, L1     WB in cycle 11
add r1, r2, r3
L1:

NOTE: if branch was NOT taken, then it would require 12 cycles

13. c

NOTE: if branch was NOT taken, then it would require 11 cycles

14. tag = 5, set index = 77, block offset = 39

block size = 128 bytes = 128 bytes / 2 bytes per word = 64 words
=> block offset = 6 bits
set size = 4 x block size = 4 x 128 = 512 bytes
#sets = cache size/set size = 64 KB / 512 = 216/29 = 27
=> set index = 7 bits
Note: 1 KB = 1024 (= 210) bytes

tag = 16 - (6 + 7) = 3 bits

15. 128 lines

# cache lines = # sets in cache (by definition)

set size = 4 blocks per set x 16 bytes per block = 64 bytes
# sets = cache size/set size = 8KB/64 = 213/26 = 27 = 128

16. Olivia (lw 1 3 X, sw 2 3 Y)

17. Tricia (program where LRU causes miss every time)