《现代计算机体系结构》课程教学课件（英文讲稿）Lecture 06 Scoreboarding and Tomasulo

高级计算机体系结构设计及其在数据中心和云计算的应用Lecture 6Scoreboarding

高级计算机体系结构设计及其在数据中心和云计算的应用 Lecture 6 Scoreboarding

高级计算机体系结构设计及其在数据中心和云计算的应用OverviewTechniquefor implementing an instruction queuethat supports dynamic reordering.Developed on CDC 6600 (decades ago)Reordering must check WAR/WAW hazards:← Long-runningF0,F2,F4DIVD←ADDD1F10_F0.F8Depends on DIV< Anti-depends on ADDSUBD F8,F8,F14Goal:Begin execution of instructions as early aspossible2

高级计算机体系结构设计及其在数据中心和云计算的应用 Overview • Technique for implementing an instruction queue that supports dynamic reordering. • Developed on CDC 6600 (decades ago). • Reordering must check WAR/WAW hazards: DIVD F0,F2,F4  Long-running 2 DIVD F0,F2,F4  Long-running ADDD F10,F0,F8  Depends on DIV SUBD F8,F8,F14  Anti-depends on ADD • Goal: Begin execution of instructions as early as possible

高级计算机体系结构设计及其在数据中心和云计算的应用SimpleScoreboardedDatapathRegistersData busesFP multFPmultFPdivideFPaddIntegerunitScoreboardControl/Control/statusstatus

高级计算机体系结构设计及其在数据中心和云计算的应用 Simple Scoreboarded Datapath 3

高级计算机体系结构设计及其在数据中心和云计算的应用Pipeline with Scoreboarding(F)Fetchinstructionfromcacheorprefetchbuffer(0)Issueinst.toanexecutionpath (whenno structural/WAWhazards)(R)Readoperands (whennoRAWhazardsremain)(E)Executeinstruction(possiblymulti-cycle)(W)Writeresults (whennoWARhazardsremain)Scoreboard/Pre-executionPost-executionbuffersbuffersControl UnitReadExecutionunit 1operandsInstructionInstructionWriteFetchIssueresultsReadExecutionunit 2operandsPre-issuebufferInstructionDecode

高级计算机体系结构设计及其在数据中心和云计算的应用 Pipeline with Scoreboarding • (F) Fetch instruction from cache or prefetch buffer • (I) Issue inst. to an execution path (when no structural/WAW hazards) • (R) Read operands (when no RAW hazards remain) • (E) Execute instruction (possibly multi-cycle) • (W) Write results (when no WAR hazards remain) Scoreboard / Pre-execution Post-execution 4 Instruction Fetch Instruction Issue Pre-issue buffer Execution unit 1 Execution . unit 2 Write results Pre-execution buffers Post-execution buffers Read operands Read operands Scoreboard / Control Unit Instruction Decode

高级计算机体系结构设计及其在数据中心和云计算的应用Instruction Issue (is) StageReplaces first halfReceivenewly-fetchedinstructionofID stageDecode binary instruction format Check for structural hazards:-Instructionneedsexecution unitcurrentlyin use,whoseinitiationinterval hasn't passed?CheckforWAWhazards:Instruction wants to write to a register that an active instruction(issued, but notyetfinished)wantsto writeto?Badiftheyfinishout-of-order!Stall all current (& future) instruction issuing, until none ofthese hazards remainIssue instructions (in-order) to the appropriate execution units& track status on scoreboard5

高级计算机体系结构设计及其在数据中心和云计算的应用 Instruction Issue (IS) Stage • Receive newly-fetched instruction • Decode binary instruction format • Check for structural hazards: – Instruction needs execution unit currently in use, whose initiation interval hasn’t passed? • Check for WAW hazards: Replaces first half of ID stage 5 • Check for WAW hazards: – Instruction wants to write to a register that an active instruction (issued, but not yet finished) wants to write to? • Bad if they finish out-of-order! • Stall all current (& future) instruction issuing, until none of these hazards remain. • Issue instructions (in-order) to the appropriate execution units & track status on scoreboard

高级计算机体系结构设计及其在数据中心和云计算的应用Read Operands (RO) StageReceiveinstructionissuedtofunctional unit Check for RAw hazards: Are all source operands availableyet?- If no: Hold instruction in a pre-execution buffer.. If buffer has only 1 entry, this and all not-yet-issuedinstructions using this functional unit must waitIf yes:Read operandsfromregisterfile, &startinstruction down the execution unit's pipelineReplaces secondhalfofIDstage6

高级计算机体系结构设计及其在数据中心和云计算的应用 Read Operands (RO) Stage • Receive instruction issued to functional unit. • Check for RAW hazards: Are all source operands available yet? – If no: Hold instruction in a pre-execution buffer. • If buffer has only 1 entry, this and all not-yet-issued 6 • If buffer has only 1 entry, this and all not-yet-issued instructions using this functional unit must wait. – If yes: Read operands from register file, & start instruction down the execution unit’s pipeline. Replaces second half of ID stage

高级计算机体系结构设计及其在数据中心和云计算的应用Execution (Ex) Stage. Once operands are received, begin executionof the instruction in the execution unit. Execution may take multiple cycles.When result is ready, notify scoreboard ofinstruction completionReplacesoldEXstage

高级计算机体系结构设计及其在数据中心和云计算的应用 Execution (EX) Stage • Once operands are received, begin execution of the instruction in the execution unit. • Execution may take multiple cycles. • When result is ready, notify scoreboard of 7 instruction completion. Replaces old EX stage

高级计算机体系结构设计及其在数据中心和云计算的应用Write Result (WR) stageReceive completed instruction & its result fromexecution unit.CheckforWARhazards:- Does any previously-issued instruction that has not yetread its operands depend on the old value we are about tooverwrite? (Does it anti-depend on us?).While yes:Stall instruction in a post-execution buffer..When no:Write instruction result to register fileReplaces WB stage8

高级计算机体系结构设计及其在数据中心和云计算的应用 Write Result (WR) stage • Receive completed instruction & its result from execution unit. • Check for WAR hazards: – Does any previously-issued instruction that has not yet read its operands depend on the old value we are about to 8 overwrite? (Does it anti-depend on us?) • While yes: Stall instruction in a post-execution buffer. • When no: Write instruction result to register file. Replaces WB stage

高级计算机体系结构设计及其在数据中心和云计算的应用Scoreboard Implementation: One typical implementation uses three tables:-Instruction status,foreachinstructiononthescoreboard. Which stage of execution is the instruction currently in?-FunctionalUnit(FU)status,foreachFU:: What instruction (if any) is being processed?.Ifinst.isinROstage,thenforeachoperand:- What registeris the operand comingfrom?-Istheoperandready?Ifnot,whichFUwill producetheoperand?-Registerresultstatus,foreachreg.intheISA:.Whichcurrently-runningFU(ifany)isscheduledtooverwritethegiven register?

高级计算机体系结构设计及其在数据中心和云计算的应用 Scoreboard Implementation • One typical implementation uses three tables: – Instruction status, for each instruction on the scoreboard • Which stage of execution is the instruction currently in? – Functional Unit (FU) status, for each FU: • What instruction (if any) is being processed? 9 • If inst. is in RO stage, then for each operand: – What register is the operand coming from? – Is the operand ready? – If not, which FU will produce the operand? – Register result status, for each reg. in the ISA: • Which currently-running FU (if any) is scheduled to overwrite the given register?

高级计算机体系结构设计及其在数据中心和云计算的应用Functional Unit Status TableFor each functional unit, the following fields:- Busy - ls the unit busy (Yes/No)?-Op-WhichexactopcodetoperformintheFU?-F,-Destinationregisterof instruction intheFU F,Fk- Source registers of instruction These fields are only needed during RO stage:: Q,Qk- FUs to write new values of source registers, or 0· R,Rk- Are operands Fj,Fk ready? (Yes/No)Register result status table has only 1 field:-Result-Whichcurrently-executingFUwill write itsresultto this register?10

高级计算机体系结构设计及其在数据中心和云计算的应用 Functional Unit Status Table • For each functional unit, the following fields: – Busy – Is the unit busy (Yes/No)? – Op – Which exact opcode to perform in the FU? – Fi – Destination register of instruction in the FU – Fj ,Fk – Source registers of instruction 10 – Fj ,Fk – Source registers of instruction – These fields are only needed during RO stage: • Qj ,Qk – FUs to write new values of source registers, or 0 • Rj ,Rk – Are operands Fj,Fk ready? (Yes/No) • Register result status table has only 1 field: – Result – Which currently-executing FU will write its result to this register?