Reorder Buffer Flashcards
What problem does the Reorder Buffer solve?
When we execute instructions out of order, we might overwrite the inputs to an instruction that later throws an exception. This can be a major problem with division, which is both prone to exceptions (divide by zero) and takes longer than most.
What actions can we and can we not perform out of order?
- We can execute instructions out of order
- We can broadcast results out of order
- But we CAN’T deposit values to registers out of order! This is why we need the Reorder Buffer, to make sure this happens in order.
Big picture, what does the Reorder Buffer do?
- Remembers program order
- Holds results until it’s safe to write them to registers
What does a Reorder Buffer look like?
It’s a table with three columns: one for the register to be written to, one for the value, and one bit to indicate whether we’re ready to write this value to its register.
The table also has two pointers: one points to the where the next issued instruction goes, and one points to the next instruction to be “committed”, or saved to register. The issue pointer is obviously ahead of the commit pointer.
How is the Reorder Buffer used?
When an instruction is issued, it gets the next free RS entry and the next ROB entry after the issue pointer. The RAT points to the ROB entry now instead of the RS.
When the instruction is dispatched for execution, we can immediately free the RS entry because it doesn’t serve as the “name” for this value. Instead, that’s the ROB entry.
When we broadcast the instruction result, we tag it with the ROB entry instead of the RS. Instead of writing the result directly to register, we write to its ROB entry.
We only write the result to register when the commit pointer reaches the ROB entry.
How does the ROB help us recover from a branch midprediction?
Once the misprediction has been marked in the ROB and the commit pointer reaches that entry, we simply move that issue pointer back to the place as the commit! The registers, at this point, only contain values from before the branch, so they’re correct. Future instructions will just write over top of the incorrect ones.
How does the ROB help us recover from exceptions?
For regular exceptions (like divide by zero), we move the issue pointer to the same location as the commit point once we detect the exception. This gives us a nice resume point after exception handling.
For “phantom” exceptions (ones that occur along a branch that never should have been taken), we move the issue pointer like before and we cleanly skip over the exception. Essentially, we treat exceptions like any other result and delay handling until commit gets there.
How do we update registers and RAT on commit?
First, we check whether our ROB entry is still the name stored in our result’s corresponding RAT entry. If it’s not, we will still update the register (because that’s what a commit is all about!), but we will leave the RAT entry alone.
However, if our ROB entry IS the name stored in the corresponding RAT entry, then we will update the register, then point that RAT entry to the register.
Once an instruction captures its final value (while sitting in the RS), when does it dispatch and when does it execute?
It dispatches in the same cycle that it captures, and it executes in the next cycle.
What are the pros and cons of using a unified Reservation Station?
Pro: We can always issue the next instruction as long as there is an RS slot available, we don’t have to wait for the right kind of RS slot.
Con: Dispatching becomes more complicated. Every cycle we need to pick one instruction for each ALU unit to dispatch (say, one ADD and one MUL)
On net, this is a benefit and modern processors tend to use a unified RS.
What do we need to achieve superscalar processing?
We need every stage to be able to handle more than one instruction per cycle. This includes:
- Fetch
- Decode
- Issue
- Dispatch
- Broadcast
- Commit
The “weakest link”, or narrowest part of the pipeline, determines the flow.
Which stages of the pipeline are in- and out-of-order?
The first three stages, Fetch, Decode, and Issue, are all in program order.
The next two stages, Dispatch and Broadcast, are out-of-order. They instead occur in the order determined by their data dependencies.
The final stage, Commit, is obviously in order. The whole point of this stage is maintain program order when we write to registers.
