COMP 206: Computer Architecture and ImplementationReadingWhat is a Scoreboard?MIPS with a ScoreboardDynamic Scheduling with a ScoreboardScoreboard ImplicationsFour Stages of Scoreboard ControlFour Stages of Scoreboard Control (cont.)Three Parts of the ScoreboardScoreboard Example Cycle 0Scoreboard Example Cycle 1Scoreboard Example Cycle 2Scoreboard Example Cycle 3Scoreboard Example Cycle 4Scoreboard Example Cycle 5Scoreboard Example Cycle 6Scoreboard Example Cycle 7Scoreboard Example Cycle 8aScoreboard Example Cycle 8bScoreboard Example Cycle 9Scoreboard Example Cycle 10Scoreboard Example Cycle 11Scoreboard Example Cycle 12Scoreboard Example Cycle 13Scoreboard Example Cycle 14Scoreboard Example Cycle 15Scoreboard Example Cycle 16Scoreboard Example Cycle 17Scoreboard Example Cycle 18Scoreboard Example Cycle 19Scoreboard Example Cycle 20Scoreboard Example Cycle 21Scoreboard Example Cycle 22Scoreboard Example Cycle 61Scoreboard SummaryScoreboard: Bookkeeping Actions1COMP 206:COMP 206:Computer Architecture and Computer Architecture and ImplementationImplementationMontek SinghMontek SinghWed, Oct 5, 2005Wed, Oct 5, 2005Topic: Topic: Instruction-Level ParallelismInstruction-Level Parallelism(Dynamic Scheduling: Scoreboarding)(Dynamic Scheduling: Scoreboarding)2ReadingReadingAppendix A (Crosscutting Issues)Appendix A (Crosscutting Issues)3What is a Scoreboard?What is a Scoreboard?A Scoreboard is a table maintained by the A Scoreboard is a table maintained by the hardware:hardware:keeps track of instructions being fetched, issued, keeps track of instructions being fetched, issued, executed etc.executed etc.keeps track of the resources (functional units and keeps track of the resources (functional units and operands) they use/needoperands) they use/needkeeps track of which instructions modify which keeps track of which instructions modify which registersregistersuses this information to dynamically schedule uses this information to dynamically schedule instructionsinstructionsvery similar to a pen and paper calculationvery similar to a pen and paper calculationsimple step-by-step procedure easily implemented in simple step-by-step procedure easily implemented in hardwarehardware4MIPS with a ScoreboardMIPS with a Scoreboard5Dynamic Scheduling with a Dynamic Scheduling with a ScoreboardScoreboardOriginal development in CDC 6600Original development in CDC 6600Simplified example in HP3 for MIPS FP operations Simplified example in HP3 for MIPS FP operations (Read Section A.8)(Read Section A.8)Using neither Using neither renamingrenaming nor nor forwardingforwardingValues always move from registers to function units, and from Values always move from registers to function units, and from function units back to registersfunction units back to registersHowever, write-back of results happen as soon as However, write-back of results happen as soon as possible, not in a statically scheduled slotpossible, not in a statically scheduled slotOut-of-order completion can give rise to WAR and WAW Out-of-order completion can give rise to WAR and WAW hazards hazards Remember: machine “knows” original program order (needed Remember: machine “knows” original program order (needed for hazard detection)for hazard detection)Machine modelMachine model2 FP multipliers (10 cycles), 1 FP adder (2 cycles), 1 FP divider 2 FP multipliers (10 cycles), 1 FP adder (2 cycles), 1 FP divider (40 cycles), all non-pipelined(40 cycles), all non-pipelined1 integer unit for everything else (incl. memory references)1 integer unit for everything else (incl. memory references)6Scoreboard ImplicationsScoreboard ImplicationsOut-of-order completion Out-of-order completion  WAW, WAR hazards? WAW, WAR hazards?for WAW: for WAW: stall in Issuestall in Issue until previous write completes until previous write completesfor WAR: for WAR: stall in Write Resultstall in Write Result until previous read until previous read completes completes Need to have multiple instructions in execution Need to have multiple instructions in execution phasephase multiple execution units or pipelined execution unitsmultiple execution units or pipelined execution unitsScoreboard keeps track of dependences, state Scoreboard keeps track of dependences, state of operationsof operationsScoreboard replaces ID, EX, WB with 4 stagesScoreboard replaces ID, EX, WB with 4 stages7Four Stages of Scoreboard ControlFour Stages of Scoreboard Control1.1.Issue:Issue: decode instr. & check for structural hazards (ID1)decode instr. & check for structural hazards (ID1)If functional unit is free and no WAW hazard with other active If functional unit is free and no WAW hazard with other active instruction …instruction …… … scoreboard issues the instruction to the functional unit and updates scoreboard issues the instruction to the functional unit and updates its internal data structure.its internal data structure.If a structural or WAW hazard exists …If a structural or WAW hazard exists …… … instruction issue stallsinstruction issue stalls–unless there is buffering between fetch and issue, no further instructions unless there is buffering between fetch and issue, no further instructions can issue until these hazards are cleared.can issue until these hazards are cleared.2.2.Read operands:Read operands: wait until no data hazards, then read (ID2)wait until no data hazards, then read (ID2)A source operand is available if no earlier issued active A source operand is available if no earlier issued active instruction is going to write it.instruction is going to write it.When all source operands are available …When all source operands are available …… … scoreboard tells the functional unit to proceed to read the operands scoreboard tells the functional unit to proceed to read the operands from registers and begin execution.from registers and begin execution.Thus, scoreboard resolves RAW hazards dynamically in this stepThus, scoreboard resolves RAW hazards dynamically in this stepinstructions may be sent into execution out of orderinstructions may be sent into execution out of order8Four Stages of Scoreboard Control Four Stages of Scoreboard Control (cont.)(cont.)3.3.Execution:Execution: operate on operandsoperate on operandsThe functional unit begins execution upon receiving The functional unit begins execution upon receiving