Digital Design & Computer Arch.

Lecture 14: Precise Exceptions

Prof. Onur Mutlu

ETH Zürich
Spring 2023
20 April 2023
Agenda for Today & Next Few Lectures
n Prior to last week: Microarchitecture Fundamentals
q Single-cycle Microarchitectures
q Multi-cycle Microarchitectures
Problem
Algorithm
n Last week & today: Pipelining
Program/Language
q Pipelining System Software
q Pipelined Processor Design SW/HW Interface
n Control & Data Dependence Handling Micro-architecture
n Precise Exceptions: State Maintenance & Recovery Logic
Devices
n Tomorrow: Out-of-Order Execution Electrons

q Out-of-Order Execution
q Issues in OoO Execution: Load-Store Handling, …
2
Readings
n Past weeks & today
q Pipelining
n H&H, Chapter 7.5
q Pipelining Issues
n H&H, Chapter 7.7, 7.8.1-7.8.3

n This week & next week

q Out-of-order execution
q H&H, Chapter 7.8-7.9
q Smith & Sohi, “The Microarchitecture of Superscalar Processors,”
Proceedings of the IEEE, 1995
n More advanced pipelining
n Interrupt and exception handling
n Out-of-order and superscalar execution concepts
3
Pipelining and Precise Exceptions:
Preserving Sequential Semantics
Multi-Cycle Execution
n Not all instructions take the same amount of time in the
“execute stage” of the pipeline

n Idea: Have multiple different functional units that take

different number of cycles
q Can be pipelined or not pipelined
q Can let independent instructions start execution on a different
functional unit before a previous long-latency instruction
finishes execution
Integer add
E
Integer mul
E E E E
FP mul
?
F D
E E E E E E E E

E E E E E E E E ...
Load/store
5
Issues in Pipelining: Multi-Cycle Execute
n Instructions can take different number of cycles in EXECUTE
stage
q Integer ADD versus Integer DIVide
Exception-causing
DIV R4 ß R1, R2 F D E E E E E E E E W instruction
ADD R3 ß R1, R2 F D E W
F D E W
F D E W
DIV R2 ß R5, R6 F D E E E E E E E E W
ADD R7 ß R5, R6 F D E W
F D E W

q What is wrong with this picture in a Von Neumann architecture?

n Sequential semantics of the ISA NOT preserved!
n What if DIV incurs an exception? (e.g., DIV by zero)
6
An Example Exception

Delayed “instruction”
due to exception

Exception-causing “instruction”

Time: 12:55 7
An Example Exception

Exception-causing
“instruction”

Time: 12:57 8
An Example Exception

Time: 12:58 9
An Example Exception

Time: 13:00 10
Another View

11
Exception Handled & Resolved…

Exception-causing
“instruction”

Time: 13:06 12
Exceptions and Interrupts
n “Unplanned” changes or interruptions in program execution

n Due to internal problems in execution of the program

à Exceptions

n Due to external events that need to be handled by the

processor
à Interrupts

n Both exceptions and interrupts require

q stopping of the current program
q saving the architectural state
q handling the exception/interrupt à switch to handler
q (if possible and makes sense) returning back to program execution
13
Exceptions and Interrupts: Examples
n Exception examples
q Divide by zero
q Overflow
q Undefined opcode
q General protection (or access protection)
q Page fault
q …

n Interrupt examples
q I/O device needing service (e.g., keyboard input, video input)
q (Periodic) system timer expiration
q Power failure
q Machine check
q …
14
Exceptions vs. Interrupts
n Cause
q Exceptions: internal to the running thread
q Interrupts: external to the running thread

n When to Handle
q Exceptions: when detected (and known to be non-speculative)
q Interrupts: when convenient
n Except for very high priority ones
q Power failure
q Machine check (error)

n Priority: process (exception), depends (interrupt)

n Handling Context: process (exception), system (interrupt)

15
Precise Exceptions/Interrupts
n The architectural state should be consistent (precise)
when the exception/interrupt is ready to be handled

1. All previous instructions should be completely retired

2. No later instruction should be retired

Retire = commit = finish execution and update arch. state

DIV R4 ß R1, R2
Precise state
ADD R3 ß R1, R2
(clean separation of
DIV R2 ß R5, R6 sequential instructions)
ADD R7 ß R5, R6

16
Checking for and Handling Exceptions in Pipelining

n When the oldest instruction ready-to-be-retired is detected

to have caused an exception, the control logic

q Ensures architectural state is precise (register file, PC, memory)

q Flushes all younger instructions in the pipeline

q Saves PC and registers (as specified by the ISA)

q Redirects the fetch engine to the appropriate exception

handling routine

17
Aside: From the x86-64 ISA Manual

https://www.intel.com/content/www/us/en/developer/articles/technical/intel-sdm.html 18
Why Do We Want Precise Exceptions?
n Semantics of the von Neumann model ISA specifies it
q Remember von Neumann vs. Dataflow

n Aids software debugging

n Enables (easy) recovery from exceptions

n Enables (easily) restartable processes

n Enables traps into software (e.g., software implemented

opcodes)

19
Ensuring Precise Exceptions
n Easy to do in single-cycle and multi-cycle machines

n Single-cycle
q Instruction boundary == Cycle boundary
q An instruction is guaranteed to be finished in one cycle
à no possibility of violating sequential execution semantics

n Multi-cycle
q Add special states in the control FSM that lead to the
exception or interrupt handlers
q Switch to the handler only at a precise state
à before fetching the next instruction

See H&H Section 7.7 for a treatment of exceptions in multi-cycle microarchitecture 20

Precise Exceptions in Multi-Cycle Datapath
EPC register: Holds the exception causing PC
Cause register: Holds the cause of the exception
Exception Handler starts at address 0x80000180

See H&H Section 7.7 for a treatment of exceptions in multi-cycle microarchitecture 21

Precise Exceptions in Multi-Cycle FSM
n Supports
q Overflow
q Undefined
instruction

n mfc0 instruction
is used to copy
the exception
cause into a
general-purpose
register

See H&H Section 7.7 for a treatment of exceptions in multi-cycle microarchitecture 22

Precise Exceptions in Multi-Cycle Datapath

23
Multi-Cycle Execute: More Complications
n Instructions can take different number of cycles in EXECUTE
stage à This complicates exception/interrupt handling

Exception-causing
DIV R4 ß R1, R2 F D E E E E E E E E W instruction
ADD R3 ß R1, R2 F D E W
F D E W
F D E W
DIV R2 ß R5, R6 F D E E E E E E E E W
ADD R7 ß R5, R6 F D E W
F D E W

q What is wrong with this picture in a Von Neumann architecture?

n Sequential semantics of the ISA NOT preserved!
n What if DIV incurs an exception? (e.g., DIV by zero)
24
Ensuring Precise Exceptions in Pipelining
n Idea: Make each operation take the same amount of time

DIV R3 ß R1, R2 F D E E E E E E E E W
ADD R4 ß R1, R2 F D E E E E E E E E W
F D E E E E E E E E W
F D E E E E E E E E W
F D E E E E E E E E W
F D E E E E E E E E W
F D E E E E E E E E W

n Downside
q Worst-case instruction latency determines all instructions’ latency
n What about memory operations?
n Each functional unit takes worst-case number of cycles?

25
Solutions: Supporting Precise Exceptions
n How do we support precise exceptions in the presence of
instructions completing out of program order?

n Reorder buffer

n History buffer

We will not cover these

n Future register file See suggested lecture video from Spring 2015
Also see backup slides

n Checkpointing

n Smith and Plezskun, “Implementing Precise Interrupts in Pipelined

Processors,” IEEE Trans on Computers 1988 and ISCA 1985.
26
Solution I: Reorder Buffer (ROB)
n Idea: Complete instructions out-of-order, but reorder them
before making results visible to architectural state
n When instruction is decoded, it reserves the next-sequential
entry in a special buffer called the Reorder Buffer (ROB)
n When instruction completes, it writes result into ROB entry
n When instruction oldest in ROB and it has completed
without exceptions, its result moved to reg. file or memory

Func Unit
Instruction Register Reorder
Cache File Func Unit Buffer
(ROB)
Func Unit

ROB is implemented as a circular queue in hardware 27

Reorder Buffer
n A hardware structure that keeps information about all
instructions that are decoded but not yet retired/committed

Entry 0 Oldest instruction

Entry 1 (pointer to ROB entry
Entry 2
that contains information
about oldest instruction

Dest reg written?

in the machine)

Dest reg value

Entry Valid?
Dest reg ID

Entry 8 Youngest instruction

Entry 13
Entry 14
Entry 15

ROB is implemented as a circular queue in hardware 28

What’s in a ROB Entry?
Valid bits for reg/data
V DestRegID DestRegVal StoreAddr StoreData PC Exception?
+ control bits

n Everything required to:

q correctly reorder instructions back into the program order
q update the architectural state with the instruction’s result(s), if
instruction can retire without any issues
q handle an exception/interrupt precisely, if an
exception/interrupt needs to be handled before retiring the
instruction

n Need valid bits to keep track of readiness of the result(s)

and find out if the instruction has completed execution

29
Reorder Buffer: Independent Operations
n Result first written to ROB on instruction completion
n Result written to register file at commit time

F D E E E E E E E E R W
F D E R W
F D E R W
F D E R W
F D E E E E E E E E R W
F D E R W
F D E R W

n What if a later instruction needs a value in the reorder buffer?

q One option: stall the operation à stall the pipeline
q Better: Read the value from the reorder buffer. How?

30
Reorder Buffer: How to Access?
n A register value can be in the register file, reorder buffer,
(or bypass/forwarding paths)

Random Access Memory

(indexed with Register ID,
Instruction Register which is the address of an entry)
Cache File
Func Unit

Func Unit

Reorder Func Unit

Content Buffer
Addressable
Memory bypass paths
(searched with
register ID,
which is part of the content of an entry)
31
Reorder Buffer Example
Register File (RF) Reorder Buffer (ROB)
R0 Entry 0 Oldest
R1 Entry 1 instruction
R2 Entry 2
R3
R4
R5
R6
R7
Entry 8 Youngest
Value Valid?

Value
instruction

Initially: all registers

are valid in RF Entry 13
& ROB is empty Entry 14
Entry 15 Entry Valid?

Dest reg written?

Dest reg value
Dest reg ID
Simulate:
MUL R1, R2 à R3
MUL R3, R4 à R11
ADD R5, R6 à R3
ADD R3, R8 à R12
32
Simplifying Reorder Buffer Access
n Idea: Use indirection

n Access register file first (check if the register is valid)

q If register not valid, register file stores the ID of the reorder
buffer entry that contains (or will contain) the value of the
register
q Mapping of the register to a ROB entry: Register file maps the
register to a reorder buffer entry if there is an in-flight
instruction writing to the register

n Access reorder buffer next

n Now, reorder buffer does not need to be content addressable

33
Reorder Buffer Example
Register File (RF) Reorder Buffer (ROB)
R0 Entry 0 Oldest
R1 Entry 1 instruction
R2 Entry 2
R3
R4
R5
R6
R7
Tag Entry 8 Youngest
Value Valid?

Value
(pointer to instruction
ROB entry)

Initially: all registers Entry 13

are valid in RF Entry 14
& ROB is empty Entry 15 Entry Valid?

Dest reg written?

Dest reg value
Dest reg ID
Simulate:
MUL R1, R2 à R3
MUL R3, R4 à R11
ADD R5, R6 à R3
ADD R3, R8 à R12
34
Reorder Buffer in Intel Pentium III/Pro

Boggs et al., “The

Microarchitecture of the
Pentium 4 Processor,” Intel
Technology Journal, 2001.

A Register Alias Table (RAT) points to where each register’s current value is (or will be)
Intel Pentium Pro (1995)

Processor chip Level 2 cache chip

Multi-chip module package

By Moshen - http://en.wikipedia.org/wiki/Image:Pentiumpro_moshen.jpg, CC BY-SA 2.5, https://commons.wikimedia.org/w/index.php?curid=2262471

36
Important: Register Renaming with a Reorder Buffer
n Output and anti dependences are not true dependences
q WHY? The same register refers to values that have nothing to
do with each other
q They exist due to lack of register ID’s (i.e. names) in
the ISA

n The register ID is renamed to the reorder buffer entry that

will hold the register’s value
q Register ID à ROB entry ID
q Architectural register ID à Physical register ID
q After renaming, ROB entry ID used to refer to the register

n This eliminates anti and output dependences

q Gives the illusion that there are a large number of registers
37
Recall: Data Dependence Types
Flow dependence
r3 ¬ r1 op r2 Read-after-Write
r5 ¬ r3 op r4 (RAW)
Anti dependence
r3 ¬ r1 op r2 Write-after-Read
r1 ¬ r4 op r5 (WAR)

Output dependence
r3 ¬ r1 op r2 Write-after-Write
r5 ¬ r3 op r4 (WAW)
r3 ¬ r6 op r7
38
Register Renaming Example (On Your Own)
n Assume
q Register file has a pointer to the reorder buffer entry that
contains or will contain the value, if the register is not valid
q Reorder buffer works as described before

n Where is the latest definition of R3 for each instruction

below in sequential order?
LD R0(0) à R3
LD R3, R1 à R10
MUL R1, R2 à R3
MUL R3, R4 à R11
ADD R5, R6 à R3
ADD R3, R8 à R12

39
Reorder Buffer Example
Register File (RF) Reorder Buffer (ROB)
R0 Entry 0 Oldest
R1 Entry 1 instruction
R2 Entry 2
R3
R4
R5
R6
R7
Tag Entry 8 Youngest
Value Valid?

Value
(pointer to instruction
ROB entry)
Initially: all registers Entry 13
are valid in RF Entry 14
& ROB is empty Entry 15 Entry Valid?

Dest reg written?

Dest reg value
Simulate: Dest reg ID
LD R0(0) à R3
LD R3, R1 à R10
MUL R1, R2 à R3
MUL R3, R4 à R11
ADD R5, R6 à R3
40
ADD R3, R8 à R12
In-Order Pipeline with Reorder Buffer
n Decode (D): Access regfile/ROB, allocate entry in ROB, check if
instruction can execute, if so dispatch instruction
n Execute (E): Instructions can complete out-of-order
n Completion (R): Write result to reorder buffer
n Retirement/Commit (W): Check oldest instruction for exceptions; if none,
write result to architectural register file or memory; else, flush pipeline
and start from exception handler
n In-order dispatch/execution, out-of-order completion, in-order retirement
Integer add
E
Integer mul
E E E E
FP mul
R W
F D
E E E E E E E E
R
E E E E E E E E ...
Load/store

ROB is implemented as a circular queue in hardware 41

Reorder Buffer Tradeoffs
n Advantages
q Conceptually simple for supporting precise exceptions
q Can eliminate false dependences

n Disadvantages
q Reorder buffer needs to be accessed to get the results that
are yet to be written to the register file
n CAM or indirection à increased latency and complexity

n Other solutions aim to eliminate the disadvantages

q History buffer
We will not cover these
q Future file See suggested lecture video from Spring 2015
q Checkpointing Also see backup slides

42
More on State Maintenance & Precise Exceptions

https://www.youtube.com/watch?v=nMfbtzWizDA&list=PL5PHm2jkkXmi5CxxI7b3JCL1TWybTDtKq&index=13
More on State Maintenance & Precise Exceptions

https://www.youtube.com/watch?v=upJPVXEuqIQ&list=PL5Q2soXY2Zi-iBn_sw_B63HtdbTNmphLc&index=18
More on State Maintenance & Precise Exceptions

https://www.youtube.com/watch?v=9yo3yhUijQs&list=PL5Q2soXY2Zi8J58xLKBNFQFHRO3GrXxA9&index=17
Lectures on State Maintenance & Recovery
n Computer Architecture, Spring 2015, Lecture 11
q Precise Exceptions, State Maintenance/Recovery (CMU, Spring 2015)
q https://www.youtube.com/watch?v=nMfbtzWizDA&list=PL5PHm2jkkXmi5CxxI7b3J
CL1TWybTDtKq&index=13

n Digital Design & Computer Architecture, Spring 2019, Lecture 15a

q Reorder Buffer (ETH Zurich, Spring 2019)
q https://www.youtube.com/watch?v=9yo3yhUijQs&list=PL5Q2soXY2Zi8J58xLKBNFQ
FHRO3GrXxA9&index=17

n Digital Design & Computer Architecture, Spring 2021, Lecture 15a

q Precise Exceptions (ETH Zurich, Spring 2021)
q https://www.youtube.com/watch?v=upJPVXEuqIQ&list=PL5Q2soXY2Zi-
iBn_sw_B63HtdbTNmphLc&index=18

https://www.youtube.com/onurmutlulectures 46
Suggested Readings for the Interested
n Smith and Plezskun, “Implementing Precise Interrupts in
Pipelined Processors,” IEEE Trans on Computers 1988 and
ISCA 1985.

n Smith and Sohi, “The Microarchitecture of Superscalar

Processors,” Proceedings of the IEEE, 1995

n Hwu and Patt, “Checkpoint Repair for Out-of-order

Execution Machines,” ISCA 1987.

n Backup Slides

47
Digital Design & Computer Arch.
Lecture 14: Precise Exceptions

Prof. Onur Mutlu

ETH Zürich
Spring 2023
20 April 2023
Backup Slides
on Precise Exceptions

49
Reorder Buffer Tradeoffs
n Advantages
q Conceptually simple for supporting precise exceptions
q Can eliminate false dependences

n Disadvantages
q Reorder buffer needs to be accessed to get the results that
are yet to be written to the register file
n CAM or indirection à increased latency and complexity

n Other solutions aim to eliminate the disadvantages

q History buffer
q Future file
q Checkpointing

50
Solution II: History Buffer (HB)
n Idea: Update the register file when instruction completes,
but UNDO UPDATES when an exception occurs

n When instruction is decoded, it reserves an HB entry

n When the instruction completes, it stores the old value of
its destination in the HB
n When instruction is oldest and no exceptions/interrupts, the
HB entry discarded
n When instruction is oldest and an exception needs to be
handled, old values in the HB are written back into the
architectural state from tail to head

51
History Buffer

Func Unit
Instruction Register History
Cache File Func Unit Buffer

Func Unit

Used only on exceptions

n Advantage:
q Register file contains up-to-date values for incoming instructions
à History buffer access not on critical path
n Disadvantage:
q Need to read the old value of the destination register
q Need to unwind the history buffer upon an exception à
increased exception/interrupt handling latency
52
Comparison of Two Approaches
n Reorder buffer
q Pessimistic register file update
q Update only with non-speculative values (in program order)
q Leads to complexity/delay in accessing the new values

n History buffer
q Optimistic register file update
q Update immediately, but log the old value for recovery
q Leads to complexity/delay in logging old values

n Can we get the best of both worlds?

q Principle: Heterogeneity
q Idea: Have both types of register files
53
Solution III: Future File (FF) + ROB
n Idea: Keep two register files (speculative and architectural)
q Arch reg file: Updated in program order for precise exceptions
n Use a reorder buffer to ensure in-order updates
q Future reg file: Updated as soon as an instruction completes
(if the instruction is the youngest one to write to a register)

n Future file is used for fast access to latest register values

(speculative state)
q Frontend register file

n Architectural file is used for state recovery on exceptions

(architectural state)
q Backend register file
54
Future File

Func Unit
Instruction Future Arch.
Func Unit ROB File
Cache File

Data and Tag V Func Unit

Used only on exceptions

n Advantage
q No need to read the new values from the ROB (no CAM or
indirection) or the old value of destination register

n Disadvantage
q Multiple register files
q Need to copy arch. reg. file to future file on an exception
55
In-Order Pipeline with Future File and Reorder Buffer
n Decode (D): Access future file, allocate entry in ROB, check if instruction
can execute, if so dispatch instruction
n Execute (E): Instructions can complete out-of-order
n Completion (R): Write result to reorder buffer and future file
n Retirement/Commit (W): Check for exceptions; if none, write result to
architectural register file or memory; else, flush pipeline, copy
architectural file to future file, and start from exception handler
n In-order dispatch/execution, out-of-order completion, in-order retirement
Integer add
E
Integer mul
E E E E
FP mul
R W
F D
E E E E E E E E

E E E E E E E E ...
Load/store

56
Can We Reduce the Overhead of Two Register Files?
n Idea: Use indirection, i.e., pointers to data in frontend and
retirement
q Have a single storage that stores register data values
q Keep two register maps (speculative and architectural); also
called register alias tables (RATs)

n Future map used for fast access to latest register values

(speculative state)
q Frontend register map

n Architectural map is used for state recovery on exceptions

(architectural state)
q Backend register map

57
Future Map in Intel Pentium 4

Boggs et al., “The

Microarchitecture of
the Pentium 4
Processor,” Intel
Technology Journal,
2001.

Many modern
processors
are similar:
- MIPS R10K
- Alpha 21264

https://courses.cs.washington.edu/courses/cse378/10au/lectures/Pentium4Arch.pdf 58
Reorder Buffer vs. Future Map Comparison

https://courses.cs.washington.edu/courses/cse378/10au/lectures/Pentium4Arch.pdf 59
Before We Get to Checkpointing …
n Let’s cover what happens on exceptions
n And branch mispredictions

60
Checking for and Handling Exceptions in Pipelining

n When the oldest instruction ready-to-be-retired is detected

to have caused an exception, the control logic
q Recovers architectural state (register file, IP, and memory)
q Flushes all younger instructions in the pipeline
q Saves IP and registers (as specified by the ISA)
q Redirects the fetch engine to the exception handling routine
n Vectored exceptions

61
Pipelining Issues: Branch Mispredictions
n A branch misprediction resembles an “exception”
q Except it is not visible to software (i.e., it is microarchitectural)

n What about branch misprediction recovery?

q Similar to exception handling except can be initiated before
the branch is the oldest instruction (not architectural)
q All three state recovery methods can be used

n Difference between exceptions and branch mispredictions?

q Branch mispredictions are much more common
à need fast state recovery to minimize performance impact of
mispredictions

62
How Fast Is State Recovery?
n Latency of state recovery affects
q Exception service latency
q Interrupt service latency
q Latency to supply the correct data to instructions fetched after
a branch misprediction

n Which ones above need to be fast?

n How do the three state maintenance methods fare in terms

of recovery latency?
q Reorder buffer
q History buffer
q Future file
63
Branch State Recovery Actions and Latency
n Reorder Buffer
q Flush instructions in pipeline younger than the branch
q Finish all instructions in the reorder buffer

n History buffer
q Flush instructions in pipeline younger than the branch
q Undo all instructions after the branch by rewinding from the
tail of the history buffer until the branch & restoring old values
one by one into the register file

n Future file
q Wait until branch is the oldest instruction in the machine
q Copy arch. reg. file to future file
q Flush entire pipeline
64
Can We Do Better?
n Goal: Restore the frontend state (future file) such that the
correct next instruction after the branch can execute right
away after the branch misprediction is resolved

n Idea: Checkpoint the frontend register state/map at the

time a branch is decoded and keep the checkpointed state
updated with results of instructions older than the branch
q Upon branch misprediction, restore the checkpoint associated
with the branch

n Hwu and Patt, “Checkpoint Repair for Out-of-order

Execution Machines,” ISCA 1987.

65
Checkpointing
n When a branch is decoded
q Make a copy of the future file/map and associate it with the
branch

n When an instruction produces a register value

q All future file/map checkpoints that are younger than the
instruction are updated with the value

n When a branch misprediction is detected

q Restore the checkpointed future file/map for the mispredicted
branch when the branch misprediction is resolved
q Flush instructions in pipeline younger than the branch
q Deallocate checkpoints younger than the branch

66
Checkpointing
n Advantages
q Correct frontend register state available right after checkpoint
restoration à Low state recovery latency
q …

n Disadvantages
q Storage overhead
q Complexity in managing checkpoints
q …

67
Many Modern Processors Use Checkpointing
n MIPS R10000
n Alpha 21264
n Pentium 4
n …

n Yeager, “The MIPS R10000 Superscalar Microprocessor,”

IEEE Micro, April 1996

n Kessler, “The Alpha 21264 Microprocessor,” IEEE Micro,

March-April 1999.

n Boggs et al., “The Microarchitecture of the Pentium 4

Processor,” Intel Technology Journal, 2001.
68
Summary: Maintaining Precise State
n Reorder buffer

n History buffer

n Future register file

n Checkpointing

n Readings
q Smith and Plezskun, “Implementing Precise Interrupts in Pipelined
Processors,” IEEE Trans on Computers 1988 and ISCA 1985.
q Hwu and Patt, “Checkpoint Repair for Out-of-order Execution
Machines,” ISCA 1987.
69
Registers versus Memory
n So far, we considered mainly registers as part of state

n What about memory?

n What are the fundamental differences between registers

and memory?
q Register dependences known statically – memory
dependences determined dynamically
q Register state is small – memory state is large
q Register state is not visible to other threads/processors –
memory state is shared between threads/processors (in a
shared memory multiprocessor)

70
Maintaining Speculative Memory State: Stores
n Handling out-of-order completion of memory operations
q UNDOing a memory write more difficult than UNDOing a register
write. Why?
q One idea: Keep store address/data in reorder buffer
n How does a load instruction find its data?
q Store/write buffer: Similar to reorder buffer, but used only for
store instructions
n Program-order list of un-committed store operations
n When store is decoded: Allocate a store buffer entry
n When store address and data become available: Record in store
buffer entry
n When the store is the oldest instruction in the pipeline: Update the
memory address (i.e. cache) with store data

n We will get back to this when we discuss store-load handling

71
Reorder Buffer Example
Register File (RF) Reorder Buffer (ROB)
R0 Entry 0 Oldest
R1 Entry 1 instruction
R2 Entry 2
R3
R4
R5
R6
R7
Entry 8 Youngest
Value Valid?

Value or Tag
(i.e., pointer to ROB entry) instruction

Initially: all registers

Entry 13
are valid in RF
Entry 14
& ROB is empty Entry 15
Simulate:
Entry Valid?

Dest reg written?

Dest reg value
Dest reg ID
MUL R1, R2 à R3
MUL R3, R4 à R11
ADD R5, R6 à R3
ADD R3, R8 à R12
72