4.0 Out-of-order execution

Question 1

What are some limitations with pipelines

Answer 1

1: treat all instructions the same (same execution time for the different stages)

2: maximum IPC: 1

3: Limits to in-order execution

Question 2

What determines the clock frequency?

Answer 2

The slowest pipeline stage.
All the stages will execute at this frequency

Question 3

What is a solution to unification happening during pipelining?

Answer 3

Diversification

Question 4

What is diversification?

Answer 4

Update the pipeline by allowing the Execution phase to take different amount of cycles depending on operation to be done.
For example iteger operations take 1 cycle and memory operations take multiple.

Question 5

What are a benefit with using diversification

Answer 5

Shorter clock cycles

Question 6

What are some problems with diversification?

Answer 6

1: Might get out-of-order completion

2: Multiple write operations to the register file in the same clock cycle

3: Exceptions

Question 7

How can out-of-order completion happen when using diversification?

Answer 7

If the first instruction uses 3 cycles during the execute phase and the next uses 1, the second instruction will complete before the first.

If both instruction write to the same register, we have a write after write hazard

Question 8

What do we need to do to fix a write-after-write hazard caused by out-of-order execution?

Answer 8

Stall

Question 9

What are some hazards that can happen as a result of out-of-order execution?

Answer 9

Write-after-write

Multiple writes per cycle

Question 10

How can we fix the problem of having multiple writes per cycle as a result of out-of-order execution?

Answer 10

Multiple write ports, if different registers are being used

Consider write port as structural hazard. When detected, the pipeline can delay until the first write has finished

Question 11

What are precise exceptions and how can out-of-order execution affect these?

Answer 11

Precise exceptions are when all instructions prior to the exception, has executed to their completion. And non instructions after the exception has completed at all.

Out-of-order instructions may allow for later instructions to complete write back before the excpetion happens.

Question 12

What are interrupts?

Answer 12

Due to external factors

Asynchronous to program execution

Independent of program running

Of-of-order execution is not a problem for interrupts, as these don’t need to be handled immediately

Question 13

How are interrupts handled?

Answer 13

Stop fetching new instruction

Drain pipeline (execute instructions in the pipeline)

Store state (registers, PC)

Handle interrupt

restore program state and resume execution

Question 14

What are exceptions and how are these handled?

Answer 14

Synchronous: result of program execution

Precise exeption flow:
- Store architecture state from just before the instruction that caused exception
- handle exception
- restore state and resume execution from instruction that caused exception

Can guarantee precise exceptions by stalling pipeline

Question 15

How can parallelism be exploited in pipelines?

Answer 15

Superscalar pipelines are pipelines where multiple instructions can complete each cycle.

Parallelism in time(pipelining)

Parallelism in space (superscalar execution)

Superscalar pipeline use both

Question 16

How does superscalar pipelines handle hazards?

Answer 16

Handle hazard before sending instruction to a functioning unit

Question 17

Whatcan cause performance loss when using in-order issue?

Answer 17

Even though some instructions are completely independent on the previous ones, if previous instructions are stalling, these also need to stall to ensure in-order execution.

Question 18

What are a key-idea behind out-of-order execution (2)?

Answer 18

Register renaming: Remove all anti dependences

Data flow execution: instruction execute as soon as their inputs are evailable.

Question 19

What is data flow limit

Answer 19

The only thing preventing execution is that input data is not ready yet

Can illustrate by setting instructions as nodes in a graph, and real (RAW) data dependences as edges

Height of graph show minimum number of cycles needed

Question 20

Describe the out-of-order pipeline

Answer 20

Two new stages:
- register renaming
- dispatch

New structures:
- issue buffer
- reorder buffer
- store buffer and queue

writeback stage divided into two stages: complete and retire

Question 21

What does the register renaming stage do?

Answer 21

Remove all WAW and WAR hazards

These dependences are caused by the lack of names

Question 22

What does the dispatch stage do?

Answer 22

Dispatches the instructions that now only have data dependences to the issue buffers

Instructions stay in the issue buffer until all their inputs have become available, then they continue execution

Question 23

What does the reorder buffer do?

Answer 23

Instructions are also dispatched to the reorder-buffer as well as he issue buffers. This to pretend the instructions are ordered to get precise exceptions

Question 24

What does the completion stage do?

Answer 24

Architecture state is updated
To software, the instruction appears to be fully completed

Question 25

What does the retirement stage do?

Answer 25

Applies to stores only.

Data is written to memory hierarchy

Question 26

How does the completion and retirement phase appear to different type of instructions?

Answer 26

For non-store instructions the completion phase is the same as the retirement.

For store instruction, completion moves from store queue to store buffer and retirement writes to memory and leave the store buffer.
In the store queue we have the stores that has not yet happend. Store buffer is the stores that hascompleted architecturaly, but not written back to memory.

Question 27

What does the issue buffer do?

Answer 27

Keeps track of instructions that has not executed yet

Inserted in buffer in program order

Execute on the functional unit when ready, and possibly leaves buffer out of program order

Question 28

What does the reorder buffer do?

Answer 28

Keeps track of window of instructions currently being execution

Main job is to maintain program order

insert in program order, and leaves reorder buffer in program order

Software gets illusion of sequentiality, precise exceptions

Question 29

What does register renaming accomplish and how

Answer 29

Remove anti and output dependences, only real data dependences

achieve data-flow-limit

Architectural registers are renamed to physical/rename registers

Need more physical registers then architectural

Key observation: a physical register is written at most once by an instruction in execution

Done completely in hard ware

Question 30

How are registers renamed?

Answer 30

Real data dependences will get the same name as the registers they’re dependent on (One instruction uses R3 and another is real dependent on R3, Renamed to F3 at both instructions)

anti dependency registers get new names (R3 used by two instruction, named F3 at one of them and F4 at the other)

Data flow show no reused name

Question 31

How is the architectural to physical register mapping done?

Answer 31

Need two tables.
- mapping table
- physical register file

In the frontend of the pipeline, the renaming stage, we need a mapping table. Provide the architectural register and retrieve a pointer to physical register. Size of mapping table: arch-registers times log_2(physical_reg)

In the backend pipeline we access the physical register file.

Question 32

What does a physical register consist of?

Answer 32

Have a state:
- starts as ‘available’

• then physical register gets allocated and becomes a rename register (value not computed)
• When instruction with this register is executed, the register becomes a rename register, value is computed
• when instruction leaves the reorder buffer it is time to make the value of the register appear in program state - update the state of the architectural register.
• architectural register is then overwritten and released

Question 33

How is register renaming implemented?

Answer 33

Initialization:
- All physical registers that map to architectural registers are in the ‘architectural register’ state
- all other registers are ‘availeble’

Renaming register:
- Read the physical register that corresponds with the architectural from the mapping table

Decide what to do with the output:
- Select an ‘available’ physical register and change the state to ‘rename register, value not computed’. update mapping table
- if no more ‘available’, stall pipeline until physical register becomes available

Instruction finish:
- State change to ‘rename register, value computed’

Instruction leaves reorder buffer (complete):
- change state of physical to architectural AND
- physical reg previously associated with same arch register changes to ‘available’

Question 34

What is the final stage of the frontend pipeline?

Answer 34

Dispatch stage

Question 35

What happens during the dispatch stage?

Answer 35

Allocates space in- and dispatches instructions to the issue buffers of their respective functional unit and the reorder buffer.

If the issue buffers OR the register buffer are full, the pipeline must stall.

Question 36

What is Tomasulos algorithm?

Answer 36

The out-of-order execution

Question 37

What does the reservation station/issue buffers do?

Answer 37

Issue buffer decouples the frontend from the backend of the pipeline.

Buffering of instructions until all their operands are available.

Instructions leave the issue buffer when all operands are available and the functional unit is available. (Instruction ready signal = 1)

When execution has finished, the target ID and result is put on the forwarding bus.

Question 38

What does a reservation station entry contain?

Answer 38

Busy: Is entry in use

op1: if valid - contain reg value, if valid is 0 - contain reg ID
valid
op2
valid

ready: instruction is ready to be executed

Question 39

How is an instruction woken up in the reservation station?

Answer 39

The results come in from the FUs along side their reg-identifiers.

A comparator compares the incoming ID with the one stored in the operand X field in the issue-buffer entry.

The output of this comparison is used as control signal for a multiplexer using the FU-result as input, so that the result can be written to the operand field.

Then the valid bit is set.

Both valid bits are AND together and the result of this is stored in the ready-bit of the RS-entry

Question 40

What happens when more than one instruction are ready in the RS for the same functional unit?

Answer 40

Implement policies to choose what instruction to issue first.

For example schedule oldest-first

Question 41

What does the reorder buffer do?

Answer 41

Contain all in-flight instructions.

All instructions after dispatch and before completion.

Is a circular buffer - head/tail pointers

The number of new instructions that can be added each cycle is the dispatch width. Dispatch happens at the tail, in-order dispatch.

The number of instructions that can leave the ROB is limited by the completion width. completion happens at head, in-order completion

Question 42

What does the ROB-entry consist of (reorder-buffer entry)

Answer 42

busy: entry is in use

finished: instruction has finished execution and is ready to be committed

instruction address

previous reg mapping: used to deallocate the architectural register that this instruction writes to

speculative: is this instruction fetched beyond a predicted branch

store: if the instruction is a store

exception?: set if the instruction generated an exception

Question 43

What is the instruction window?

Answer 43

When ROB and issue buffer are combined into one structure.

Cons: large structure and HW complexity

Question 44

What are precise exceptions?

Answer 44

We save architectural state befor the exception occured, handle exception, and continue execution from the instruction that caused exception.

Question 45

How do we get precise instructions in out-of-order processors?

Answer 45

Set exception flag in ROB-entry

Let all instructions up until this complete

Handle instruction when the excpetion instruction is about to complete.

Then need to undo the register renaming that was done after the exception.

Question 46

How do we undo register renaming after an exception?

Answer 46

The exception instruction is at the ROB-head.

The register mapping is restored from the ROB tail to the ROB head

Question 47

How is mispredicted branches handled in out-of-order processors?

Answer 47

Register mapping must be restored to the state just after the branch

Can do this the same way as with exception, but this is more work as branches often gets mispredicted.

Use checkpointing instead: take a snapshot of the mapping table after each branch.
Restore table table from the snapshot after the mispredicted branch

Question 48

What is data captured scheduling?

Answer 48

Data and IDs are transfered from the FUs to the reservation station

Data is set as operands

Instructions are then issued to the FUs

A downside of doing this is that there is a fair share of data copying

Question 49

What is non-data captured scheduling?

Answer 49

Only the tags (IDs) are passed around, and the register file is between the reservation station and the FUs.

Question 50

What are the advantages of non-data captured organization?

Answer 50

Reservation station is less complex because it does not store the register values, only the tags.

Reduce wiringbetween FUs and the reservation station entries.

Question 51

How is RAW hazards handled in non-data captured scheduling

Answer 51

When a result is ready from the FUs it is forwarded to the FU inputs for the next instruction. This instruction needs it, but it is not yet written to the register file.

Question 52

What is Value prediction?

Answer 52

An attempt on approving the data flow limit.

Done at the beginning of the pipeline.

Predict outcome of loads/ALU ops

Don’t need to wait for the result to be computed and can therefor execute dependent instructions sooner

A speculative technique - prediction needs to be verified.

Can work because of locality

Is not implemented as much because of the power wall, and it being not efficient. If prediction is wrong we have done work that is useless, and we need to restore state.