EECE 321 Exam 3 with Solution, Fall 2012

H. AKKARY DEPT. OF ELECTRICAL AND COMPUTER ENGINEERING AMERICAN UNIVERSITY OF BEIRUT EECE321 – COMPUTER ORGANIZATION QUIZ 3 – Fall 2012 NAME: ________________________ ID: ___________________________ INSTRUCTIONS: Page 1 of 3  THE EXAM IS CLOSED BOOK/CLOSED NOTES, EXCEPT FOR MIPS ISA SHEET  THE DURATION IS 90 MINUTES.  THE PROBLEMS ARE WEIGHTED EQUALLY.  NO QUESTIONS ARE ALLOWED.  YOU ARE NOT ALLOWED TO LEAVE THE EXAM ROOM UNTIL YOU TURN IN YOUR EXAM.  MAKE SURE YOU HAVE 3 PAGES IN THIS QUIZ  WRITE YOUR NAME AND ID NUMBER IN THE SPACE PROVIDED ABOVE.  PROVIDE YOUR ANSWERS IN THE SPACE PROVIDED ON THE QUESTION SHEET.  USE THE BACK OF THE PAGES FOR SCRATCH  BE AS NEAT AND CLEAR AS POSSIBLE. 1. Structural, data and control hazards typically require a processor pipeline to stall. Listed below are a series of optimization techniques implemented in a processor pipeline designed to reduce or eliminate stalls due to these hazards. For each of the following optimization techniques, state which pipeline hazard it addresses and how it addresses it. a. Register operands comparator in the decode stage. Control hazard. b. Separate instruction and data cache Structural hazard. c. Adder for computing next PC Structural hazard. d. Data cache Data hazard. e. Bypassing Data hazard. 2. Ideally, a pipeline achieves n speedup over a single cycle pipeline, where n is the number of stages. Give 4 reasons why actual pipelines may not achieve the ideal speedup. 1) Unbalanced pipeline stage delays, 2) control hazards, 3) data hazards, 4) structural hazards, 5) branch mispredictions, 6) exceptions. 3. A pipelined MIPS processor has the following pipe stage latencies. The latency for each stage includes the delay through the pipeline register preceding it. IF ID EX MEM WB 350ps 200ps 200ps 450ps 150ps a. What is the processor cycle time? 450ps b. Assuming that the pipeline register delay is 40ps. What is the cycle time of a single cycle implementation of this MIPS processor? 1150ps. c. What is the speedup of this pipeline? Page 2 of 3 1150/450 = 2.56. 4. Consider the following assembly language code: I0: LDW R4 = MEM[R5 + 100]; I1: SUB R9 = R3 - R4; I2: LDW R2 = MEM[R3 + 0]; I3: BEQ R2, R9, LABEL; Consider a pipeline with forwarding and hazard detection. The pipeline is the typical 5-stage IF, ID, EX, MEM, WB MIPS design and computes the branch address and condition in the decode stage. For the above code, complete the pipeline diagram below (instructions on the left, cycles on top). Insert the characters IF, ID, EX, MEM, WB for each instruction in the boxes. Assume that there are two levels of bypassing, that the second half of the decode stage performs a read of source registers, and that the first half of the write back stage writes to the register file. Label all data stalls (Draw an X in the box). Label all data forwards that the forwarding unit detects (arrow between the stages handing off the data and the stages receiving the data). T1 T2 T3 T4 T5 T6 T7 T8 T9 T10 T11 T12 T13 T14 T15 I0 IF ID EX MEM WB I1 IF ID X EX MEM WB I2 IF X ID EX MEM WB I3 IF ID X X EX MEM WB 5. Repeat the above problem for the case when instruction I0 causes a page fault exception that is detected in the MEM stage of the pipeline. T1 T2 T3 T4 T5 T6 T7 T8 T9 T10 T11 T12 T13 T14 T15 I0 IF ID EX MEM WB I1 IF ID EX NOP NOP I2 IF ID NOP NOP NOP I3 IF NOP NOP NOP NOP Page 3 of 3