CsabaAndrasMoritz

《CsabaAndrasMoritz》由会员分享，可在线阅读，更多相关《CsabaAndrasMoritz（27页珍藏版）》请在装配图网上搜索。

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&Morgan Kaufmann ECE668.2

2、Adapted from Patterson,Katz and Kubiatowicz UCBExceptions-BasicsException=unprogrammed control transfersystem takes action to handle the exceptionmust record the address of the offending instructionrecord any other information necessary to return afterwardsreturns control to usermust save&restore us

3、er 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 ExceptionsInterruptscaused by external events:Network,Keyboard,Di

4、sk I/O,Timerasynchronous to program executionMost interrupts can be disabled for brief periods of timemay be handled between instructionssimply suspend and resume user programTraps caused by internal eventsexceptional conditions(overflow)errors(parity)page faults(non-resident page)synchronous to pro

5、gram 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-Examples Copyright 2001 UCB&Morgan Kaufmann ECE668.5Adapted from Patt

6、erson,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 fetch;misaligned memory access;memory-protection violation;memory errorHow do we sto

7、p 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 Kaufmann ECE668.6Adapted from Patterson,Katz and Kubiatowicz UCBMultiple exceptionsTime(clock

8、 cycles)Load AddRegALUDMemIfetchRegRegALUDMemIfetchRegCycle 1 Cycle 2 Cycle 3 Cycle 4 Cycle 5Data page faultArithmetic exceptionTime(clock cycles)Load AddRegALUDMemIfetchRegRegALUDMemIfetchRegCycle 1 Cycle 2 Cycle 3 Cycle 4 Cycle 5Data page faultInstruction page fault Copyright 2001 UCB&Morgan Kaufm

9、ann 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 machinePrecise state of the machine is preserved as if program executed up to the offending instructionAll p

10、revious instructions completedOffending instruction and all following instructions act as if they have not even startedSame code will work on different processor implementations Difficult in the presence of pipelining,out-of-order execution,.Imprecise system software has to figure out what is where

11、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 Patterson,Katz and Kubiatowicz UCBRelationship between precise interrupts and speculationSpeculation:guess and chec

12、kImportant 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 predicted incorrectly:This is exactly the same as precise exceptions!Technique for both precise interrupts/exceptions and

13、 speculation:in-order completion or commit Copyright 2001 UCB&Morgan Kaufmann ECE668.9Adapted from Patterson,Katz and Kubiatowicz UCBHandling Exceptions Exceptions are handled by not recognizing the exception until instruction that caused it is ready to commit in ROBIf a speculated instruction raise

14、s 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 Patterson,Katz and Kubiatowicz UCBReorder Buffer(HW support for precise interrupts)ROB=Buffer for results of uncommitted instructionsAn instru

15、ction commits when it completes its execution and all its predecessors have already committed Once instruction commits,result is put into registerTherefore,easy to undo speculated instructions on mispredicted branches or exceptionsSupplies operands between execution complete&commitReorderBufferFPOpQ

16、ueueFP AdderFP MpierRes StationsRes StationsFP Regs Copyright 2001 UCB&Morgan Kaufmann ECE668.11Adapted from Patterson,Katz and Kubiatowicz UCBMore on Reorder Buffer operationHolds instructions in FIFO order,exactly as issuedWhen instructions complete,results placed into ROBSupplies operands to othe

17、r instruction between execution complete&commit Tag results with ROB buffer number instead of reservation stationInstructions commit values at head of ROB placed in registersReorderBufferFPOpQueueFP AdderFP AdderRes StationsRes StationsFP RegsCommit path Copyright 2001 UCB&Morgan Kaufmann ECE668.12A

18、dapted from Patterson,Katz and Kubiatowicz UCBAnother Perspective on Reorder BufferIf instructions write results in program order,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

19、write reg/memory immediately after execution,so ROB also buffer the resultsNo such a place in original Tomasulo ReorderBufferDecodeFU1FU2ReStReStFetch UnitRenameL-bufS-bufDMRegfileIM Copyright 2001 UCB&Morgan Kaufmann ECE668.13Adapted from Patterson,Katz and Kubiatowicz UCBROB:Circular Buffer with H

20、ead/Tail PointersheadtailheadtailheadtailFreed ROB entryAllocated ROB Entry when instr issuedEntries between head and tail are valid Copyright 2001 UCB&Morgan Kaufmann ECE668.14Adapted from Patterson,Katz and Kubiatowicz UCBReorder Buffer Entry DetailsReorder BufferDest regResultExceptions?Program C

21、ounterBranch or L/W?Ready?Copyright 2001 UCB&Morgan Kaufmann ECE668.15Adapted from Patterson,Katz 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,IEE

22、ETC,May 1988 REGISTERFILEResult Shift RegisterREORDERBUFFERControlSource Data to functional 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

23、next clock The issuing instr places control information into RSR Each clock moves 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(

24、see Smith et al)PC Instruction Ex_Time(in FU)6 ADDF F10,F1,F3 6 7 ADD R9,R2,R5 2Stage FunctionalValidTagunit sourceinstr.102Integer ADD1530405Flt.Pt.ADD14N0Direction of movementReorder(circular)BufferResult Shift RegisterHeadTail State in RSR(control info plus ROB tag)after the ADD issues(for exampl

25、e below)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 result shift r

26、egister 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 register file;(6)dispatch the decoded

27、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.Write result finish execution(WB)Action:Write on Commo

28、n 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 memory)and remove instr from ROB.Mispredicted branch flushes reorder buffer

29、.(sometimes called“graduation”)Copyright 2001 UCB&Morgan Kaufmann ECE668.18Adapted from Patterson,Katz and Kubiatowicz UCBTomasulo With Reorder buffer:ToMemoryFP addersFP multipliersReservation StationsFP OpQueueROB7ROB6ROB5ROB4ROB3ROB2ROB1F0LD F0,10(R2)NDone?DestDestOldestNewestfrom Memory1 10+R2De

30、stReorder BufferRegisters Copyright 2001 UCB&Morgan Kaufmann ECE668.19Adapted from Patterson,Katz and Kubiatowicz UCB2 ADDD R(F4),ROB1Tomasulo With Reorder buffer:ToMemoryFP addersFP multipliersReservation StationsFP OpQueueROB7ROB6ROB5ROB4ROB3ROB2ROB1F10F0ADDD F10,F4,F0LD F0,10(R2)NNDone?DestDestOl

31、destNewestfrom 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 Reorder buffer:ToMemoryFP addersFP multipliersReservation StationsFP OpQueueROB7ROB6ROB5ROB4ROB3ROB2ROB1F

32、2F10F0DIVD F2,F10,F6ADDD F10,F4,F0LD F0,10(R2)NNNDone?DestDestOldestNewestfrom Memory1 10+R2DestReorder BufferRegisters Copyright 2001 UCB&Morgan Kaufmann ECE668.21Adapted from Patterson,Katz and Kubiatowicz UCB3 DIVD ROB2,R(F6)2 ADDD R(F4),ROB16 ADDD ROB5,R(F6)Tomasulo With Reorder buffer:ToMemoryF

33、P addersFP multipliersReservation StationsFP OpQueueROB7ROB6ROB5ROB4ROB3ROB2ROB1F0ADDD F0,F4,F6NF4LD F4,0(R3)N-BNE F2,NF2F10F0DIVD F2,F10,F6ADDD F10,F4,F0LD F0,10(R2)NNNDone?DestDestOldestNewestfrom Memory1 10+R2DestReorder BufferRegisters5 0+R3 Copyright 2001 UCB&Morgan Kaufmann ECE668.22Adapted fr

34、om 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 OpQueueROB7ROB6ROB5ROB4ROB3ROB2ROB1-F0ROB5ST 0(R3),F4ADDD F0,F4,F6NNF4LD F4,0(R3)N-BNE F2,NF2F10F0DIVD F2,F10,F6ADDD F10,F4,F0LD

35、F0,10(R2)NNNDone?DestDestOldestNewestfrom MemoryDestReorder BufferRegisters1 10+R25 0+R3 Copyright 2001 UCB&Morgan Kaufmann ECE668.23Adapted from Patterson,Katz and Kubiatowicz UCB3 DIVD ROB2,R(F6)Tomasulo With Reorder buffer:ToMemoryFP addersFP multipliersReservation StationsFP OpQueueROB7ROB6ROB5R

36、OB4ROB3ROB2ROB1-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+R2DestReorder BufferRegisters2 ADDD R(F4),ROB16 ADDD M10,R(F6)Copyright 2001 UCB&Morgan Kaufmann ECE668.24Adapted from Patterson,Katz an

37、d Kubiatowicz UCB3 DIVD ROB2,R(F6)2 ADDD R(F4),ROB1Tomasulo With Reorder buffer:ToMemoryFP addersFP multipliersReservation StationsFP OpQueueROB7ROB6ROB5ROB4ROB3ROB2ROB1-F0M10ST 0(R3),F4ADDD F0,F4,F6YExF4M10LD F4,0(R3)Y-BNE F2,NF2F10F0DIVD F2,F10,F6ADDD F10,F4,F0LD F0,10(R2)NNNDone?DestDestOldestNew

38、estfrom Memory1 10+R2DestReorder BufferRegisters Copyright 2001 UCB&Morgan Kaufmann ECE668.25Adapted from Patterson,Katz and Kubiatowicz UCB-F0M10ST 0(R3),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 multipliersReserva

39、tion 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 Memo

40、ry HazardsWAW and WAR hazards through memory are eliminated with speculation because actual updating of memory occurs in order,when a store is at head of the ROB,and hence,no earlier loads or stores can still be pending RAW hazards through memory are maintained by two restrictions:1.not allowing a l

41、oad to initiate the second step of its execution if any active ROB entry occupied by a store has a Destination field that matches the value of the A field of the load,and 2.maintaining the program order for the computation of an effective address of a load with respect to all earlier stores.these re

42、strictions ensure that any load that accesses a memory location written to by an earlier store cannot perform the memory access until the store has written the data Copyright 2001 UCB&Morgan Kaufmann ECE668.27Adapted from Patterson,Katz and Kubiatowicz UCBGetting CPI below 1CPI 1 if issue only 1 ins

43、truction every clock cycle Multiple-issue processors come in many flavors,e.g.,:1.dynamically-scheduled superscalar processors,and 1.(out-of-order execution)2.VLIW(very long instruction word)processorsVLIW processors,in contrast,issue a fixed number of instructions formatted either as one large instruction or as a fixed instruction packet with the parallelism among instructions explicitly indicated by the instruction(Intel/HP Itanium)