Fall 2003 Exam 2 Solutions -------------------------- 1. a) TRUE b) FALSE c) TRUE d) TRUE e) FALSE f) FALSE g) FALSE h) TRUE 2. a) D b) N c) F d) N e) N f) D 3. a) M, M, H, M, M, M, H, M, M, H, H, H b) 42 % c) 5.67 cycles 4. a) 16 bits tag * 1024 blocks + 1 dirty bit * 1024 blocks + 1 valid bit * 1024 blocks --------------------------- 18432 bits b) 17 bits tag * 1024 blocks + 1 dirty bit * 1024 blocks + 1 valid bit * 1024 blocks + 1 LRU bit * 512 sets --------------------------- 19968 bits 5. a) start nand 1 1 2 -none- beq 1 2 target EXMEM lw 2 5 data MEMWB add 2 5 6 MEMWB target sw 0 6 data EXMEM nand 1 2 3 -none- nand 6 5 4 WBEND nand 4 3 7 EXMEM, MEMWB nand 3 4 1 MEMWB, WBEND nand 2 4 2 WBEND halt -none- b) Yes, "add 2 5 6" 6. a) 1.58 (CPI = 1 + (0.5)(0.25)1 + (0.15)3 = 1.58) b) 1.17 (CPI = 1 + (0.4)(0.25)1 + (0.25)1 = 1.35, Speedup = 1.58/1.35 = 1.17) 7. a) | 1| 2| 3| 4| 5| 6| 7| 8| 9|10|11|12|13|14|15|16| ------------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ add 1 2 3 |IF|RR|AG|EM|WB| | | | | | | | | | | | add 4 5 6 |IF|RR|AG|EM|WB| | | | | | | | | | | | lw 3 5 -1 | |IF|RR|AG|AG|EM|WB| | | | | | | | | | add 5 2 4 | |IF|RR|AG|AG|AG|EM|WB| | | | | | | | | sw 1 4 -1 | | |IF|RR|RR|RR|AG|EM|WB| | | | | | | | nand 4 1 7 | | |IF|RR|RR|RR|AG|EM|WB| | | | | | | | add 7 3 4 | | | |IF|IF|IF|RR|AG|EM|WB| | | | | | | sw 4 7 -2 | | | |IF|IF|IF|RR|AG|AG|AG|EM|WB| | | | | lw 5 3 14 | | | | | | |IF|RR|RR|RR|AG|EM|WB| | | | beq 3 4 3 | | | | | | |IF|RR|RR|RR|AG|AG|EM|WB| | | add 1 2 3 | | | | | | | |IF|IF|IF|RR|RR|AG|EM|WB| | nand 3 4 5 | | | | | | | |IF|IF|IF|RR|RR|AG|AG|EM|WB| b) 16 cycles 8. a) 1 noop must be entered before or after "add 7 7 7", but not both. b) No, one possible reordering: lw 0 7 n1 lw 0 1 n3 lw 0 2 n4 lw 0 6 n2 noop loop add 1 7 1 add 2 6 2 sw 0 7 tmp add 7 7 7 beq 1 2 end beq 0 0 loop end halt 9. a) Standard interpretation: compare WBEND destination with IDEX.readRegA compare WBEND destination with IDEX.readRegB compare MEMWB destination with IDEX.readRegA compare MEMWB destination with IDEX.readRegB compare EXMEM destination with IDEX.readRegA compare EXMEM destination with IDEX.readRegB Total: 6 comparators The fact that LW has it destination specified in different instruction bits from ADD and NAND adds another complication. To do it in 6 comparators, the destination register input for the comparators for WBEND and MEMWB must be supplied by a MUX that picks out the right field. Smart hardware designers would probably do this during ID and pass the proper destination down the pipe, probably along with tags as to whether it is actually used for this particular instruction, but we've never gotten that detailed in 370. To parallelize the checks for LW and not wait for the MUX we can add four more comparators: compare WBEND LW destination with IDEX.readRegA compare WBEND LW destination with IDEX.readRegB compare MEMWB LW destination with IDEX.readRegA compare MEMWB LW destination with IDEX.readRegB If we bring opcodes checking into the picture, compare WBEND opcode with ADD compare WBEND opcode with NAND compare WBEND opcode with LW compare MEMWB opcode with ADD compare MEMWB opcode with NAND compare MEMWB opcode with LW compare EXMEM opcode with ADD compare EXMEM opcode with NAND 8 more comparators Thus, it seems that 6, 10, 14, or 18 are all plausible correct answers, depending on the underlying assumptions, (common or separate LW handling, with or without opcode handling) b) 3 bits is the only reasonable answer c) 2 for the register compares: compare IFID field 0 with IDEX field1 compare IFID field 1 with IDEX field1 If we bring in opcode checks, 1 to check that IDEX is LW 5 to check for ADD, NAND, LW, SW, BEQ in IFID some not entirely trivial random logic to compute the stall, Thus, plausible correct answers are 2 or 8