CsabaAndrasMoritz

1、 Copyright 2001 UCB & Morgan Kaufmann ECE668 .1Adapted from Patterson, Katz and Kubiatowicz UCBCsaba Andras MoritzUNIVERSITY OF MASSACHUSETTSDept. of Electrical & Computer EngineeringComputer Architecture ECE 668Exceptions, Reorder Buffer (ROB), Speculative Tomasulo Copyright 2001 UCB &

2、Morgan Kaufmann ECE668 .2Adapted from Patterson, Katz and Kubiatowicz UCBExceptions - BasicsException = unprogrammed control transfersystem takes action to handle the exception must record the address of the offending instruction record any other information necessary to return afterwardsreturns con

3、trol to usermust save & restore user statenormal control flow: sequential, jumps, branches, calls, returnsuser programSystemExceptionHandlerException:return fromexception Copyright 2001 UCB & Morgan Kaufmann ECE668 .3Adapted from Patterson, Katz and Kubiatowicz UCBTwo Types of ExceptionsInte

4、rruptscaused by external events: Network, Keyboard, Disk I/O, Timerasynchronous to program execution Most interrupts can be disabled for brief periods of timemay be handled between instructionssimply suspend and resume user programTraps caused by internal events exceptional conditions (overflow) err

5、ors (parity) page faults (non-resident page)synchronous to program executioncondition must be remedied by the handlerinstruction may be retried and program continued or program may be aborted Copyright 2001 UCB & Morgan Kaufmann ECE668 .4Adapted from Patterson, Katz and Kubiatowicz UCBExceptions

6、 - Examples Copyright 2001 UCB & Morgan Kaufmann ECE668 .5Adapted from Patterson, Katz and Kubiatowicz UCBStagePossible exceptionsIFPage fault on instruction fetch; misaligned memory access; memory-protection violationID Undefined or illegal opcodeEX Arithmetic exceptionMEM Page fault on data fe

7、tch; misaligned memory access; memory-protection violation; memory errorHow do we stop the pipeline? How do we restart it?Do we interrupt immediately or wait?5 instructions, executing in 5 different pipeline stages!Who caused the interrupt?Exceptions in MIPS pipeline Copyright 2001 UCB & Morgan

8、Kaufmann ECE668 .6Adapted from Patterson, Katz and Kubiatowicz UCBMultiple exceptionsTime (clock cycles)Load AddRegALUDMemIfetchRegRegALUDMemIfetchRegCycle 1 Cycle 2 Cycle 3 Cycle 4 Cycle 5Data page faultArithmetic exceptionTime (clock cycles)Load AddRegALUDMemIfetchRegRegALUDMemIfetchRegCycle 1 Cyc

9、le 2 Cycle 3 Cycle 4 Cycle 5Data page faultInstruction page fault Copyright 2001 UCB & Morgan Kaufmann ECE668 .7Adapted from Patterson, Katz and Kubiatowicz UCBPrecise Interrupts/ExceptionsExceptions should be Precise or clean, i.e., the outcome should be exactly the same as in a non-pipelined m

10、achinePrecise state of the machine is preserved as if program executed up to the offending instructionAll previous instructions completedOffending instruction and all following instructions act as if they have not even startedSame code will work on different processor implementations Difficult in th

11、e presence of pipelining, out-of-order execution, .Imprecise system software has to figure out what is where and put it all back togetherModern techniques for out-of-order execution and branch prediction help implement precise interrupts Copyright 2001 UCB & Morgan Kaufmann ECE668 .8Adapted from

12、 Patterson, Katz and Kubiatowicz UCBRelationship between precise interrupts and speculationSpeculation: guess and checkImportant for branch prediction:Need to “take our best shot” at predicting branch directionIf we speculate and are wrong, need to back up and restart execution to point at which we

13、predicted incorrectly:This is exactly the same as precise exceptions!Technique for both precise interrupts/exceptions and speculation: in-order completion or commit Copyright 2001 UCB & Morgan Kaufmann ECE668 .9Adapted from Patterson, Katz and Kubiatowicz UCBHandling Exceptions Exceptions are ha

14、ndled by not recognizing the exception until instruction that caused it is ready to commit in ROBIf a speculated instruction raises an exception, the exception is recorded in the ROBThis is why reorder buffers in all new processors Copyright 2001 UCB & Morgan Kaufmann ECE668 .10Adapted from Patt

15、erson, Katz and Kubiatowicz UCBReorder Buffer(HW support for precise interrupts)ROB=Buffer for results of uncommitted instructionsAn instruction commits when it completes its execution and all its predecessors have already committed Once instruction commits, result is put into register Therefore, ea

16、sy to undo speculated instructions on mispredicted branches or exceptionsSupplies operands between execution complete & commitReorderBufferFPOpQueueFP AdderFP MpierRes StationsRes StationsFP Regs Copyright 2001 UCB & Morgan Kaufmann ECE668 .11Adapted from Patterson, Katz and Kubiatowicz UCBM

17、ore on Reorder Buffer operationHolds instructions in FIFO order, exactly as issuedWhen instructions complete, results placed into ROBSupplies operands to other instruction between execution complete & commit Tag results with ROB buffer number instead of reservation stationInstructions commit val

18、ues at head of ROB placed in registersReorderBufferFPOpQueueFP AdderFP AdderRes StationsRes StationsFP RegsCommit path Copyright 2001 UCB & Morgan Kaufmann ECE668 .12Adapted from Patterson, Katz and Kubiatowicz UCBAnother Perspective on Reorder BufferIf instructions write results in program orde

19、r, reg/memory always get the correct valuesRole of ROB: to reorder out-of-order instruction to program order at the time of writing register/memory (commit)Instruction cannot write reg/memory immediately after execution, so ROB also buffer the resultsNo such a place in original Tomasulo ReorderBuffe

20、rDecodeFU1FU2ReStReStFetch UnitRenameL-bufS-bufDMRegfileIM Copyright 2001 UCB & Morgan Kaufmann ECE668 .13Adapted from Patterson, Katz and Kubiatowicz UCBROB: Circular Buffer with Head/Tail PointersheadtailheadtailheadtailFreed ROB entryAllocated ROB Entry when instr issuedEntries between head a

21、nd tail are valid Copyright 2001 UCB & Morgan Kaufmann ECE668 .14Adapted from Patterson, Katz and Kubiatowicz UCBReorder Buffer Entry DetailsReorder BufferDest regResultExceptions?Program CounterBranch or L/W?Ready? Copyright 2001 UCB & Morgan Kaufmann ECE668 .15Adapted from Patterson, Katz

22、and Kubiatowicz UCBOrganization with ROB and Associated Result Shift Register (from Smith et al. 1988)Common Result BusData (upon Commit)Bypass Logic/ ComparatorsFor more details read: J. Smith & A. Pleszkun, IEEETC, May 1988 REGISTERFILEResult Shift RegisterREORDERBUFFERControlSource Data to fu

23、nctional units Result Shift Register controls Result Bus Stages labeled 1through n, n length longest FU pipeline An instruction taking i clocks reserves stage i in RSR when issues If valid instr already it waits until next clock The issuing instr places control information into RSR Each clock moves

24、to stage towards 1 and next cycle uses controlThe ROB Tag guides the results to end up in correct ROB entry Copyright 2001 UCB & Morgan Kaufmann ECE668 .16Adapted from Patterson, Katz and Kubiatowicz UCBExample of RSR use (see Smith et al )PC Instruction Ex_Time (in FU) 6 ADDF F10,F1,F3 6 7 ADD

25、R9,R2,R5 2Stage FunctionalValidTagunit sourceinstr.102Integer ADD1530405Flt. Pt. ADD14N0Direction of movementEntry # Dest. Reg. Result Exceptions Valid RsltPC34100659076Reorder (circular) BufferResult Shift RegisterHeadTail State in RSR (control info plus ROB tag) after the ADD issues (for example b

26、elow) ROB entry at Tail is given to issuing instruction;Tail + Copyright 2001 UCB & Morgan Kaufmann ECE668 .17Adapted from Patterson, Katz and Kubiatowicz UCBFour Steps of Speculative Tomasulo Algorithm1. Issue get instruction from FP Op Queue If reservation station, reorder buffer slot, and res

27、ult shift register slot free, issue instr & send operands & reorder buffer no. for destination. (this stage sometimes called “dispatch”)Actions summary: (1) decode the instruction; (2) allocate a RS, RSR and ROB entry; (3) do source register renaming; (4) do dest register renaming; (5) read

28、register file; (6) dispatch the decoded and renamed instruction to the RS and ROB2. Execution operate on operands (EX) Action: when both operands ready then execute; if not ready, watch CDB for result; when both in reservation station, execute; this takes care of RAW. (sometimes called “issue”)3. Wr

29、ite result finish execution (WB) Action: Write on Common Data Bus to all awaiting FUs & reorder buffer; mark reservation station available4. Commit update register with result from reorder buffer Action: When instr. at head of ROB & result present, update register with result (or store to me

30、mory) and remove instr from ROB. Mispredicted branch flushes reorder buffer. (sometimes called “graduation”) Copyright 2001 UCB & Morgan Kaufmann ECE668 .18Adapted from Patterson, Katz and Kubiatowicz UCBTomasulo With Reorder buffer:ToMemoryFP addersFP multipliersReservation StationsFP OpQueueRO

31、B7ROB6ROB5ROB4ROB3ROB2ROB1F0LD F0,10(R2)NDone?DestDestOldestNewestfrom Memory1 10+R2DestReorder BufferRegisters Copyright 2001 UCB & Morgan Kaufmann ECE668 .19Adapted from Patterson, Katz and Kubiatowicz UCB2 ADDD R(F4),ROB1Tomasulo With Reorder buffer:ToMemoryFP addersFP multipliersReservation

32、StationsFP OpQueueROB7ROB6ROB5ROB4ROB3ROB2ROB1F10F0ADDD F10,F4,F0LD F0,10(R2)NNDone?DestDestOldestNewestfrom Memory1 10+R2DestReorder BufferRegisters Copyright 2001 UCB & Morgan Kaufmann ECE668 .20Adapted from Patterson, Katz and Kubiatowicz UCB3 DIVD ROB2,R(F6)2 ADDD R(F4),ROB1Tomasulo With Reo

33、rder buffer:ToMemoryFP addersFP multipliersReservation StationsFP OpQueueROB7ROB6ROB5ROB4ROB3ROB2ROB1F2F10F0DIVD F2,F10,F6ADDD F10,F4,F0LD F0,10(R2)NNNDone?DestDestOldestNewestfrom Memory1 10+R2DestReorder BufferRegisters Copyright 2001 UCB & Morgan Kaufmann ECE668 .21Adapted from Patterson, Kat

34、z and Kubiatowicz UCB3 DIVD ROB2,R(F6)2 ADDD R(F4),ROB16 ADDD ROB5, R(F6)Tomasulo With Reorder buffer:ToMemoryFP addersFP multipliersReservation StationsFP OpQueueROB7ROB6ROB5ROB4ROB3ROB2ROB1F0ADDD F0,F4,F6NF4LD F4,0(R3)N-BNE F2,NF2F10F0DIVD F2,F10,F6ADDD F10,F4,F0LD F0,10(R2)NNNDone?DestDestOldestN

35、ewestfrom Memory1 10+R2DestReorder BufferRegisters5 0+R3 Copyright 2001 UCB & Morgan Kaufmann ECE668 .22Adapted from Patterson, Katz and Kubiatowicz UCB3 DIVD ROB2,R(F6)2 ADDD R(F4),ROB16 ADDD ROB5, R(F6)Tomasulo With Reorder buffer:ToMemoryFP addersFP multipliersReservation StationsFP OpQueueRO

36、B7ROB6ROB5ROB4ROB3ROB2ROB1-F0ROB5ST 0(R3),F4ADDD F0,F4,F6NNF4LD F4,0(R3)N-BNE F2,NF2F10F0DIVD F2,F10,F6ADDD F10,F4,F0LD F0,10(R2)NNNDone?DestDestOldestNewestfrom MemoryDestReorder BufferRegisters1 10+R25 0+R3 Copyright 2001 UCB & Morgan Kaufmann ECE668 .23Adapted from Patterson, Katz and Kubiato

37、wicz UCB3 DIVD ROB2,R(F6)Tomasulo With Reorder buffer:ToMemoryFP addersFP multipliersReservation StationsFP OpQueueROB7ROB6ROB5ROB4ROB3ROB2ROB1-F0M10ST 0(R3),F4ADDD F0,F4,F6YNF4M10LD F4,0(R3)Y-BNE F2,NF2F10F0DIVD F2,F10,F6ADDD F10,F4,F0LD F0,10(R2)NNNDone?DestDestOldestNewestfrom Memory1 10+R2DestRe

38、order BufferRegisters2 ADDD R(F4),ROB16 ADDD M10,R(F6) Copyright 2001 UCB & Morgan Kaufmann ECE668 .24Adapted from Patterson, Katz and Kubiatowicz UCB3 DIVD ROB2,R(F6)2 ADDD R(F4),ROB1Tomasulo With Reorder buffer:ToMemoryFP addersFP multipliersReservation StationsFP OpQueueROB7ROB6ROB5ROB4ROB3RO

39、B2ROB1-F0M10ST 0(R3),F4ADDD F0,F4,F6YExF4M10LD F4,0(R3)Y-BNE F2,NF2F10F0DIVD F2,F10,F6ADDD F10,F4,F0LD F0,10(R2)NNNDone?DestDestOldestNewestfrom Memory1 10+R2DestReorder BufferRegisters Copyright 2001 UCB & Morgan Kaufmann ECE668 .25Adapted from Patterson, Katz and Kubiatowicz UCB-F0M10ST 0(R3),

40、F4ADDD F0,F4,F6YExF4M10LD F4,0(R3)Y-BNE F2,N3 DIVD ROB2,R(F6)2 ADDD R(F4),ROB1Tomasulo With Reorder buffer:ToMemoryFP addersFP multipliersReservation StationsFP OpQueueROB7ROB6ROB5ROB4ROB3ROB2ROB1F2F10F0DIVD F2,F10,F6ADDD F10,F4,F0LD F0,10(R2)NNNDone?DestDestOldestNewestfrom Memory1 10+R2DestReorder BufferRegistersWhat about memoryhazards? Copyright 2001 UCB & Morgan Kaufmann ECE668 .26Adapted from Patterson, Katz and Kubiatowicz UCBAvoiding Memory Ha