EECE 421 Exam 2, Fall 2009

EECE (2A Dec 14, 2009 PROF. MANSOUR DEPT. OF ELECTRICAL AND COMPUT REN GINEERTY AMERICAN UNIVERSITY OF/B EECE 421 - COMPUTER ARCHI eight EXAM 2 -FALL 2008 c (pe U NAME: ID: INSTRUCTIONS: " THE EXAM IS CLOSED-BOOK/CLOSED-NOTES. THE DURATION OF THE EXAM IS TWO HOURS AND 30 MINUTES. " CELL PHONES ARE NOT ALLOWED INTO THE EXAMINATION ROOM. = WRITE YOUR NAME AND ID-NUMBER IN THE SPACE PROVIDED ABOVE. “THE EXAM IS MULTIPLE CHOICE. = USE THE SCANTRON SHEET TO MARK THE APPROPRIATE ANSWER FOR EACH QUESTION. = MARK YOUR NAME, stuvedtin, AND THE VERSION OF YOUR EXAM ON THE SCANTRON CARD. «USE ONLY PENCIL TO MARK THE SCANTRON CARD. = CHOOSE THE BEST ANSWER FROM THE FIVE POSSIBLE ANSWERS LISTED IN EACH QUESTION. = IN SOME QUESTIONS, MORE THAN ONE CHOICE MAY BE A VALID ANSWER. SELECT THE BEST CHOICE YOU THINK IS THE MOST APPROPRIATE ANSWER TO THE QUESTION. = ALL QUESTIONS ARE EQUALLY WEIGHTED. = READ THE QUESTIONS CAREFULLY BEFORE ANSWERING. = BUDGET YOUR TIME APPROPRIATELY. « SUBMIT THE QUESTION SHEET TOGETHER WITH THE SCANTRON CARD AT THE END OF THE EXAM. = CHECK YOU HAVE A TOTAL OF 11 PAGES. Page 1 of 11 Problem 1: In-order Issue Scheduling using a Scoreboard (Answer questions Q1 to Q7) Consider a MIPS pipeline with a floating-point unit (FPU). The FPU contains one adder, one multiplier, and a load/store unit. The adder has a 3-cycle latency and is fully pipelined. The multiplier has a 5-cycle latency and is fully pipelined. Assume that loads and stores take 3 cycles to execute (plus 1 cycle for the write-back stage for loads). The floating-point registers are separate from the integer registers. There is a single write-back port to each register file. In case of a write-back conflict, the older instruction writes back first. FP instructions (and loads writing FP registers) must spend one cycle in the WB stage before their result can be used. Integer results are available for bypass the next cycle after issue. Issuing of instructions to function units is done using a scoreboard. Instructions issue in order. Remember in this scheme, an instruction is issued if it does not create a WAW hazard with any previous instruction that has not written back. Recall also that the WB stage is only relevant for FP instructions (integer instructions can forward results). Q1. How does the scoreboard eliminate WAR hazards? a) It does not. Instructions cannot issue if they create WAR hazards. b) WAR hazards cannot occur because instructions write back results in order. c), WAR hazards cannot occur because instructions issue in order. d) By applying register renaming e) None of the above choices is true, or more than one of the above choices is true. Q2. In the scoreboard scheduling technique (choose one) a) Instructions can execute and write back results out of order. b) Instructions can execute out of order but must write back results in order. c) Integer ALU instructions execute and write back results in order. d) Structural hazards cannot be eliminated. The programmer must ensure structural hazards do not occur. ©) None of the above choices is true, or more than one of the above choices is true. Now, refer to the code segment shown in Table 1. Schedule this code using the scoreboarding technique. Use the scoreboard shown in Table 2 to fill your intermediate steps. Then answer questions Q3 to Q7. The first two rows have been completed for you. Assume instruction I1 is issued on cycle 0. Q3. Which of the following is true about instruction 12? (a), Issues on cycle 4; writes back on cycle 9. b) Issues on cycle 3; writes back on cycle 8. c) Issues on cycle 5; writes back on cycle 9. d) Issues on cycle 1; writes back on cycle 6. e) None of the above choices is true, or more than one of the above choices is true. Q4. Which of the following is true about instruction 13? a) Issues on cycle 9; writes back on cycle 12. b) Issues on cycle 10; writes back on cycle 14. oO Issues on cycle 10; writes back on cycle 13. \a ‘d) Issues on cycle 5; writes back on cycle 8. . \ te * e) None of the above choices is true, or more than on Afek ices is true. 7.) D MS i Q5. Which of the following is true about instruction 14? - a) Issues on cycle 8. b) Issues on cycle 9. c) Issues on cycle 10; Registers F2 and R2 are reserved for writes on this cycle. d) Issues on cycle 11; Registers F3 and R2 are reserved for writes on this cycle. (e), None of the above choices is true, or more than one of the above choices is true. ‘ Q6. Which of the following is true about instruction 16? a) Issues on cycle 12; writes back on cycle 15. (oy Issues on cycle 16; writes back on cycle 21. c) Issues on cycle 11; writes back on cycle 14. d) Issues on cycle 15; writes back on cycle 20. e) None of the above choices is true, or more than one of the above choices is true. Page 2 of 11 Q7. Instruction 17 writes back its result on cycle: a) b) fc) d) e) Issues on cycle 12; writes back on cycle 24. Issues on cycle 16; writes back on cycle 21. Issues on cycle 22; writes back on cycle 25. Issues on cycle 15; writes back on cycle 26. None of the above choices is true, or more than one of the above choices is true. Table 1: Code segment for Problem 1. I1_ [up Fl, 7(R2) 2. | FMUL F2, Fl, FO 13 | FADD 4 | ADDI /| 15 [LD /|16 | FMUL 17. | FADD Table 2: Scoreboard for Problem 1. Functional Unit Status LOAD (3) FADD (3) FMUL (5) FP Registers Reserved for Writes Page 3 of 11 Problem 2: Out-of-Order Scheduling (Questions Q8 to Q31) In this problem, we examine the execution of the code segment in Table 3 on the following out-of-order processor. ALU MEM | AM! (2) IF | ID issue|/ | FADD a (1) (1) (4) J (3) \J Feo (5) Table 3: Code segment for problem 2. Il LD Fl, 7(R2) I2 FMUL F2, Fl, FO I3 FADD F3, F2, FO r4 ADDI R2, R2, 8 I5 LD Fl, 7(R2) I6 FMUL F2, Fl, Fl I7 FADD F2, F2, F3 Assumptions: e All functional units are pipelined e ALU operations take 1 cycle (1c) ¢ Memory operations take 3 cycles (3c) (1 cycle in ALU, followed by 2 cycles in MEM) e Floating- point add (FADD) instructions take 3 cycles (3c) e — Floating- point multiply (FMUL) instructions take 5 cycles (5c) e Floating-point registers are separate from the integer registers. ¢ There is a single write-back port to the FP register file and the INT register file (one port common to both). In the case ofa WB conflict, the older instruction writes back first. e Instructions are fetched and decoded in order e The issue stage is a buffer (issue buffer or ROB) of unlimited length that holds instructions waiting to start execution. ¢ Aninstruction will only enter the issue stage if it does not cause a WAR or WAW hazard © Only one instruction can be issued (to function units) at a time, and in case multiple instructions are ready, the oldest one will go first e There is no bypassing (for both integer and FP instructions). All instructions must spend one cycle in WB stage before their results can be used. This problem consists of three parts. e Part 1: Questions Q8 to Q13 e Part 2: Questions Q14 to Q19 e Part 3: Questions Q20 to Q31 Page 4 of 11 Part 1: You are asked to schedule the code shown in Table 3. In this scheduling method, remember that an instruction enters the issue stage if it does not cause a WAR or WAW hazard. There is no register renaming. Use Table 4 to schedule the code, and then answer questions Q8 to Q13. The first row has been completed for you. In Table 4, the column ‘Decode > Issue’ means that the instruction has entered issue stage (operands have been read, a slot in the issue buffer has been reser} he column “Issued” means the instruction has started to execute. Table 4: Scheduling table | Time (cycle) Decode > Issue Issued enter issue buffer start to execute Latencies: ALU Ic, MEM 3c, FADD 3c, FMUL Se, WB Ic. No forwarding. Q8. Instruction I2 enters issue stage on cycle___, starts to execute on cycle , enters WB stage on cycle a) 1, 4, 9 b) 1, 5, 11 (cy 1, 5, 10 4 i, 4, 10 e) None of the above choices is true, or more than one of the above choices is true. Q9. Instruction I3 enters issue stage on cycle__, starts to execute on cycle , enters WB stage on cycle a) 2, 10, 13 (op 2; dd, 14 ¢) «6, zy 10 d) 2, 141, 16 e) None of the above choices is true, or more than one of the above choices is true. Qio. Instruction 14 enters issue stage on cycle , starts to execute on cycle enters WB a) 15, 16, 17 —s insight b) 4, 6, 7 dices i$ true. c) 15, 16, 19 d)) 5, 6, 7 @ None of the above choices is true, or more than one of the above ch qil. Instruction I5 enters issue stage on cycle___, starts to execute on cycle enters WB stage on cycle fa} 11, 12, 15 Gi 8, 9, 12 c) 8, 9, 13 d) 18, 19, 22 e) None of the above choices is true, or more than one of the above choices is true. Qi2. Instruction 16 enters issue stage on cycle , starts to execute on cycle enters WB stage on cycle a) 14, 15, 20 b) 16, 17, 22 ( c} 625, 16, 21 A) 12; 16, 21 e) None of the above choices is true, or more than one of the above choices is true. qi3. Instruction I7 enters issue stage on cycle__, starts to execute on cycle enters WB stage on cycle a) 22, 23, 28 b) 21, 22, 25 c) 23, 24, 27 (dy 22, 23, 26 ~e) None of the above choices is true, or more than one of the above choices is true. Page 5 of 11 Part 2: Repeat Part 1 above now with register renaming (both integer and FP registers). Assume you are given an unlimited number of renaming resources (size of issue buffer/ROB is unlimited). The instructions are committed in order and only one instruction may be committed per cycle. The earliest time an instruction can be committed is one cycle after write back. First rename the appropriate registers in Table 3 then perform scheduling. Use the register names TO, T1, T2, etc. (in ascending order) when renaming the registers as they appear in program order. Since you have an unlimited number of register names, you should use a new register name each time a register is written. Use the table below to write your schedule. The column ‘committed’ refers to the cycle when the instruction actually commits. The first row has been completed for you. Answer questions Q14 to Q19. Time (cycle) Decode > Issue Issued , . OP dst | srcl | sre2 enter issue buffer start to execute WB) | Committed Il I2 13 I4 IS 16 17 Latencies: ALU 1c, MEM 3c, FADD 3c, FMUL 50, WB lc. No forwarding. Qi4. 12 enters issue stage on cycle __, starts to execute on cycle __, enters WB stage on cycle __, commits on cycle __| (a) 1, 5, 10, d1 bP 1, 6, 14, 12 od, 2 7, 8 d) 1, 4, 9, 10 e) None of the above choices is true, or more than one of the above choices is trye. .— Sy Qis. 13 enters issue stage on cycle __, starts to execute on cycle __, enters WB sta LL sicgfot ycle | Selle a) 12, 43, 16, i? e 2 a b) 2, 12, 15, 16 () 2, 14, 14, 15 d) 2, 10, 13, 14 e) None of the above choices is true, or more than one of the above choices is true. Qi6. 14 enters issue stage on cycle _, starts to execute on cycle __, enters WB stage on cycle __, commits on cycle __| a) 3, 16, Lif, 18 b) 3, 4, 15, 16 c) 16, 17, 18, 19 (d) 3, 4, 5, 16 e) None of the above choices is true, or more than one of the above choices is true. Qi7. I5 enters issue stage on cycle __, starts to exec teon cycle aint tage on cycle ___, commits on cycle __. a) 4, 17, 20, 21 . (b), 4, 6, 9, 17 \" sidhnt | c) 5, 6, 9, 17 O* 6 tu d) 4, 5 8, 17 es ) None of the above choices is true, or more than one of the above choices is true. 16 enters issue stage on cycle __, starts to execute on cycle __, enters WB stage on cycle __, commits on cycle __: 5, 10, 15; 18 5) hy 10, 18 5, 7, 10, 11 5, 12, 15, 18 None of the above choices is true, or more than one of the above choices is true. 7 enters issue stage on cycle __, starts to execute on cycle __, enters WB stage on cycle __, commits on cycle __ 15, 18, 19 16, 19) 20 11, 14, 15 19, 22, 23 e above choices is true, or more than one of the above choices is true. Page 6 of 11 Part 3: Repeat Part 2 above but now assuming that the ROB has only two entries. The first entry in the ROB has tag TO, while the second entry has tag T1. An instruction cannot enter the issue stage if there is no empty slot in the ROB. Otherwise, the instruction is reserved a slot its destination register is renamed with the appropriate tag. oss aS Use the table below to write your schedule. In the last column, record the renamed register wh orrespon ing instruction enters the ROB. The first row in the table has been completed for you. Answer questions Q20 t. Time (cycle) Decode > Issue Issued 7 F enter issue buffer start to execute WB: | Committed if FI renamed TO 12 F2 (econ) T! B EA cenanveh TO 14 K2 (Anam a if! 8 A named to 16 1) yerdovd TI 17 : 30 5112 @Wromwect TO Latencies: ALU lc, MEM 3c, FADD 3c, FMUL Sc, WB lc. No forwarding. Q20. When Instruction I2 enters the ROB, its registers are renamed as: ) FMUL TO, TO, FO. (6) FMUL T4, TO, FO. c) FMUL 11, F1, FO. d) FMUL TO, F1, FO. e) None of the above choices is true, or more than one of the above choices is true. Qa2i. 12 enters ROB on cycle _, starts to execute on cycle __, enters WB stage on cycle __, commits on cycle _: a) 1, 6, 11, 12 b) 5, 6, 11, 12 c) 6, 7, 12, 13 (d) 1, 5, to, od “| None of the above choices is true, or more than one of the above choices is true. Q22. When Instruction I3 enters the ROB, its registers are reng a) FADD TO, F2, FO. b) FADD 11, T1, FO. (©) FADD TO, T1, FO. _ d) FADD 71, TO, FO. e) None of the above choices is true, or more than one of the’a Q23. 13 enters ROB on cycle _, starts to execute on cycle __, enters WB stage on cycle__, commits on cycle _: a) 12, 13, 16, 17 (d) 6, 1, 014,15 ¢) 5, 11, 14, 15 d) 6, 12, 15, 16 e) None of the above choices is true, or more than one of the above choices is true. Q24. When Instruction I4 enters the ROB, its registers are renamed as: a) ADDI T1,71,8. (By) ADDI TO, R2, 8. cy) ADDI TO, TO, 8. d) ADDI T1, R2, 8. e) None of the above choices is true, or more than one of the above choices is true. Q2s5. 14 enters ROB on cycle _, starts to execute on cycle __, enters WB stage on cycle __, commits on cycle _: (a) 12, 13, 15, 16 b) 12, 13; 14, 16 c) 12, 13, 14, 15) d) 16, 17, 18, 19 e) None of the above choices is true, or more than one of the above choices is true. Page 7 of 11 Q26. When Instruction I5 enters the ROB, its registers are renamed as: a) LD T1, 5(TO). b) LD TO, 5(R2). —_—_— ( gq LD TO, S(T1). a “d) LD TA, 5(R2). | -) e) None of the above choices is true, or more than one of the abgv (@HE —! a pI Q27. 15 enters ROB on cycle _, starts to execute on cycle __, enters WB sta; a) 17, 18, 24. 22 (b) 16, 17, 20, 22 ‘13, 17, 20, 21 d) 13, 14, 17, 20 e) None of the above choices is true, or more than one of the above choices is true. cle __, commits on cycle _: Q28. When Instruction I6 enters the ROB, its registers are renamed as: @ FMUL 71, TO, TO. ) FMUL TO, 71, T1. c) FMUL T1, Fi, Fi. d) FMUL TO, F1, Fi. e) None of the above choices is true, or more than one of the above choices is true. Q29. 16 enters ROB on cycle _, starts to execute on cycle _, enters WB stage on cycle __, commits on cycle __: (a) 17, 21, 26, 27 b) 22, 23, 28, 29 c) 18, 19), 24, 25 d) 17, 18, 23, 24 e) None of the above choices is true, or more than one of the above choices is true. Q30. When Instruction !7 enters the ROB, its registers are renamed as: a) FADD 711, TO, F3. b) FADD T1, TO, TO. c) FADD TO, F2, F3. (dy FADD TO, 71, F3. e) None of the above choices is true, or more than one of the above choices} Q31. 17 enters ROB on cycle _, starts to execute on cycle __, enters WB stage o a) 22, 23, 26, 28 b) 22, 23, 26, 27 @ 22, 27, 30, 31 23; 27, 30, 31 e) None of the above choices is true, or more than one of the above choices is true. Page 8 of 11 Problem 3: Branch Prediction (Questions Q32 to Q38) In this problem, we study the performance of a 2-level branch prediction scheme when executing a loop (single branch). The prediction scheme is a 2-level predictor shown below. It employs 2-bit branch predictor state machines for local prediction as discussed in class. In state 1X, we predict ‘not taken’, while is state OX, we predict taken (see FSM below). However, instead of using a 2-bit shift register for global branch history (common for a es) to select the appropriate 2-bit predictor to use, a 2-bit shift register is maintained for every branch to act as a 2-bit local i branch are tracked in a two-bit shift register (1 for taken, 0 for ngt) lax ocal, his ry is usedXo select which 2-bit predictor to use. 00 Fetch PC an 2-bit branch predictors ¢ A—_____, k | l | | | an an | | | 1 1} Lu L 2-bit local i ! H branch history fl L fl 5 I | I | Taken / Not Taken Consider the loop shown below. Assume that every time this loop executes, it ends up taking two iterations, Column 1 in Table 5 below shows the values of register R1 to be used to evaluate the branch instruction on each iteration. The history register for B1 is initialized to ‘00’ (row1, column 2), while all local branch predictors are initialized to ‘10’ (columns 3 to.6 predicted value of the branch while the final column shows that actual outcome of the brar LOOP: LW R1, 4(R2) SUBI R2, R2, 8 Bl: BNEQZ R1, LOOP Table 5: Branch prediction table. (N: Not taken; T: Taken) System state Branch Predictor | Behavior . B1 bits History way 01 | way 10 COorntianer WN HE wes is) Page 9 of 11 Q32. Start by filling all rows in the History column (column 2) and the final column in Table 5 based on the values of R11 listed in column 1. In updating the History value, the contents of the shift register are shifted to the left, and the new branch outcome value is inserted from the right. Out of the 12 times the branch is executed, how manytimes. it is actually taken? The value of the History register after the branch executes 12 times is : (choose the correc answer) a) Taken4 times; value of History register is ‘11’. ° . ») b) Taken 8 times; value of History register is ‘11’. c) Taken 8 times; value of History register is ‘01’. d) Taken 8 times; value of History register is ‘10’. e) None of the above choices is true, or more than one of the above choices is true. Next, fill out columns 3 to 7 in Table 5. The first row has been completed for you. For row 1, the History register in column 2 is ‘00’, so way ‘00’ is selected. The stored prediction bits are ‘10’ (bold). The state machine predicts “not taken”, which is recorded in column 7, row 1. Since the branch is actually taken, the prediction bits for way ‘00’ are updated in row 2, column 3 (italic). Fill the remaining rows in the table in this fashion then answer questions Q33 to Q38. Q33. Refer to row 4 in the table. The stored prediction bits for way ‘01’ are__; The predicted value in column 7 is a) ‘11’; Taken. b) “21} Not Taken. ec) 10"; Taken. d) ‘10’; Not Taken. e) None of the above choices is true, or more than one of the above choices is true. Q34. Refer to row 7 in the table. The stored prediction bits for way ‘01’ are__; The predicted value in column 7 is a) ‘00’; Taken. b) ‘10’; Not Taken. c) ‘00’; Not Taken. d) ‘11’; Not Taken. e) None of the above choices is true, or more than one of the above choices is true. Q35. Refer to row 12 in the table. The stored prediction bits for w a) ‘00’; Taken. b) ‘10’; Not Taken. c) ‘11’; Not Taken. d) ‘00’; Not Taken. Q36. How many times does the predictor mispredict? a) 4times b) 5 times c) 6times d) 7 times e) None of the above choices is true, or more than one of the above choices is true. Q37. After training, does the predictor catch the behavior of the loop (i.e. that it runs only two iterations every time it executes)? a) Yes b) No c) Can’t tell d) It is a coincidence in this example. In other cases, the predictor will not be able to catch the 2-iterations pattern. e) None of the above choices is true, or more than one of the above choices is true. Q38. To achieve high accuracy on loops that run for 3 iterations instead of 2, how would you modify this prediction scheme? a) Make the local branch history 3 bits; Keep 4 two-bit local branch predictors. b) Keep the local branch history 2 bits; Include 8 three-bit local branch predictors. c) Make the local branch history 3 bits; Include 8 two-bit local branch predictors. d) Make the local branch history 3 bits; Include 4 three-bit local branch predictors. e) None of the above choices is true, or more than one of the above choices is true. Page 10 of 11