CS152 Computer Architecture and Engineering Lecture 17 Dynamic Scheduling (Cont), SpeculationThe Big Picture: Where are We Now?Review: Scoreboard Architecture(CDC 6600)Review: Four Stages of Scoreboard ControlReview: Tomasulo OrganizationRecall: Reservation Station ComponentsRecall: Three Stages of Tomasulo AlgorithmRecall: Tomasulo Example Cycle 1Recall: Tomasulo Example Cycle 2Recall: Tomasulo Example Cycle 3Recall: Tomasulo Example Cycle 4Recall: Tomasulo Example Cycle 5Recall: Tomasulo Example Cycle 6Recall: Compare to Scoreboard Cycle 62Tomasulo v. Scoreboard (IBM 360/91 v. CDC 6600)Tomasulo Loop ExampleLoop ExampleLoop Example Cycle 1Loop Example Cycle 2Loop Example Cycle 3What does this mean physically?Loop Example Cycle 4Loop Example Cycle 5Loop Example Cycle 6Loop Example Cycle 7Loop Example Cycle 8Slide 27Loop Example Cycle 9Loop Example Cycle 10Loop Example Cycle 11Loop Example Cycle 12Loop Example Cycle 13Loop Example Cycle 14Loop Example Cycle 15Loop Example Cycle 16Loop Example Cycle 17Loop Example Cycle 18Loop Example Cycle 19Loop Example Cycle 20Why can Tomasulo overlap iterations of loops?Recall: Unrolled Loop That Minimizes StallsAdministriviaComputers in the NewsWhy issue in-order?Now what about exceptions???HW support for precise interruptsFour Steps of Speculative Tomasulo AlgorithmTomasulo With Reorder buffer:Slide 49Slide 50Slide 51Slide 52Slide 53Slide 54Slide 55Memory Disambiguation: Handling RAW Hazards in memoryHardware Support for Memory DisambiguationMemory Disambiguation:What about FETCH? Independent “Fetch” unitBranches must be resolved quickly for loop overlap!Prediction: Branches, Dependencies, DataDynamic Branch PredictionSimple dynamic prediction: Branch Target Buffer (BTB)Branch History Table (BHT)Dynamic Branch Prediction: Usual DivisionDynamic Branch Prediction: 2-bit predictorBHT AccuracyCorrelating BranchesSlide 69Accuracy of Different SchemesSummary #1/2Summary #2/24/07/03 ©UCB Spring 2003CS152 / Kubiatowicz Lec17.1CS152Computer Architecture and EngineeringLecture 17Dynamic Scheduling (Cont), SpeculationApril 7, 2003John Kubiatowicz (www.cs.berkeley.edu/~kubitron)lecture slides: http://inst.eecs.berkeley.edu/~cs152/4/07/03 ©UCB Spring 2003CS152 / Kubiatowicz Lec17.2°The Five Classic Components of a Computer°Today’s Topics: •Recap last lecture•Hardware loop unrolling with Tomasulo algorithm•Administrivia•Speculation, branch prediction•Reorder buffersThe Big Picture: Where are We Now? ControlDatapathMemoryProcessorInputOutput4/07/03 ©UCB Spring 2003CS152 / Kubiatowicz Lec17.3Review: Scoreboard Architecture(CDC 6600)Functional UnitsRegistersFP MultFP MultFP MultFP MultFP DivideFP DivideFP AddFP AddIntegerIntegerMemorySCOREBOARDSCOREBOARD4/07/03 ©UCB Spring 2003CS152 / Kubiatowicz Lec17.4Review: Four Stages of Scoreboard Control°Issue—decode instructions & check for structural hazards •Instructions issued in program order (for hazard checking)•Don’t issue if structural hazard•Don’t issue if instruction is output dependent on any previously issued but uncompleted instruction (no WAW hazards) °Read operands—wait until no data hazards, then read operands •All real dependencies (RAW hazards) resolved in this stage•No forwarding of data in this model!°Execution—operate on operands (EX)•The functional unit begins execution upon receiving operands. When the result is ready, it notifies the scoreboard that it has completed execution. °Write result—finish execution (WB)•Stall until no WAR hazards with previous instructions:Example: DIVD F0,F2,F4 ADDD F10,F0,F8 SUBD F8,F8,F14CDC 6600 scoreboard would stall SUBD until ADDD reads operands4/07/03 ©UCB Spring 2003CS152 / Kubiatowicz Lec17.5Review: Tomasulo OrganizationFP addersFP addersAdd1Add2Add3FP multipliersFP multipliersMult1Mult2From MemFP RegistersReservation StationsCommon Data Bus (CDB)To MemFP OpQueueLoad BuffersStore BuffersLoad1Load2Load3Load4Load5Load64/07/03 ©UCB Spring 2003CS152 / Kubiatowicz Lec17.6Recall: Reservation Station ComponentsOp: Operation to perform in the unit (e.g., + or –)Vj, Vk: Value of Source operands•Store buffers has V field, result to be storedQj, Qk: Reservation stations producing source registers (value to be written)•Note: No ready flags as in Scoreboard; Qj,Qk=0 => ready•Store buffers only have Qi for RS producing result Busy: Indicates reservation station or FU is busyRegister result status (Or “Rename Table”)—•Mapping from user-visible registers to reservation stations or value4/07/03 ©UCB Spring 2003CS152 / Kubiatowicz Lec17.7Recall: Three Stages of Tomasulo Algorithm1. Issue—get instruction from FP Op Queue If reservation station free (no structural hazard), control issues instr & sends operands (renames registers).2. Execution—operate on operands (EX) When both operands ready then execute; if not ready, watch Common Data Bus for result3. Write result—finish execution (WB) Write on Common Data Bus to all awaiting units; mark reservation station available°Normal data bus: data + destination (“go to” bus)°Common data bus: data + source (“come from” bus)•64 bits of data + 4 bits of Functional Unit source address•Write if matches expected Functional Unit (produces result)•Does the broadcast4/07/03 ©UCB Spring 2003CS152 / Kubiatowicz Lec17.8Recall: Tomasulo Example Cycle 1Instruction status:Exec WriteInstruction j kIssue Comp Result Busy AddressLD F6 34+ R2 1 Load1 Yes 34+R2LD F2 45+ R3 Load2 NoMULTD F0 F2 F4 Load3 NoSUBD F8 F6 F2DIVD F10 F0 F6ADDD F6 F8 F2Reservation Stations:S1 S2 RS RSTime NameBusyOp Vj Vk Qj QkAdd1 NoAdd2 NoAdd3 NoMult1 NoMult2 NoRegister result status:ClockF0 F2 F4 F6 F8 F10 F12 ... F301 FU Load14/07/03 ©UCB Spring 2003CS152 / Kubiatowicz Lec17.9Instruction status:Exec WriteInstruction j kIssue Comp Result Busy AddressLD F6 34+ R2 1 Load1 Yes 34+R2LD F2 45+ R3 2 Load2 Yes 45+R3MULTD F0 F2 F4 Load3 NoSUBD F8 F6 F2DIVD F10 F0 F6ADDD F6 F8 F2Reservation Stations:S1 S2 RS RSTime NameBusyOp Vj Vk Qj QkAdd1 NoAdd2 NoAdd3 NoMult1 NoMult2 NoRegister result status:ClockF0 F2 F4 F6 F8 F10 F12 ... F302 FU Load2 Load1Note: Unlike 6600, can have multiple loads outstandingRecall: Tomasulo Example Cycle 24/07/03 ©UCB Spring 2003CS152 / Kubiatowicz Lec17.10Instruction status:Exec WriteInstruction j kIssue Comp Result Busy AddressLD F6 34+ R2 1 3 Load1 Yes 34+R2LD F2 45+ R3 2 Load2 Yes 45+R3MULTD F0 F2 F4 3 Load3
View Full Document
Unlocking...