Superscalar, VLIW, OoO

Question 1

What are the 3 types of multiple-issue processors?

Answer 1

Statically-scheduled
dynamically-scheduled
VLIW

Question 2

What is the goal of Multipe-issue processors?

Answer 2

Achieve a CPI < 1

Question 3

What is a statically-scheduled superscalar processor?

Answer 3

In-order execution
Multiple issues of instructions

Question 4

What is a dynamically-scheduled superscalar processor?

Answer 4

OoO-execution
Multiple number of instructions scheduled

Question 5

What is a Very long instruction word processor?

Answer 5

In-order execution
Fixed number of instructions issued.

Question 6

What is a superscalar architecture

Answer 6

Several instructions issued simultaneously and executed independently.

Pipelining enables parallel execution across different stages.
Superscalar enables parallel execution within the same stage.

Question 7

What components do we need to add to enable multiple issuing of instructions?

Answer 7

One way is to duplicate the pipeline, in essens this gives a multi-core system.

Both pipelines must fetch from the same instruction cache, and write to the same data-caches.

PC must be synchronised across cores (PC, PC + 1).

Share register file.

Implement forwarding across cores.

More complex hazard detection across pipelines.

Question 8

What is the downside of duplicating the pipeline to achieve multi-issuing of instructions?

Answer 8

Much added complexity in the implementation

Question 9

What does a 3-issue superscalar processor consist of?

Answer 9

Multiple fetch-, and decode units.

Instructions share the functional units (EX stage). There are multiple FUs with different purposes (INT, FP, BRANCH, etc.)

Multiple MEM- and WB-stage. Might not want to duplicate MEM stage to all instructions, to avoid many ports to the caches.

CPU decides what instructions can be executed in parallel. Because of this, needs extra logic to see if an instruction actually can be executed in parallel.

Question 10

What does a VLIW consist of?

Answer 10

Only one instruction is fetched at a time, however this instruction has an an explicit encoding for allowing multiple instructions.

A VLIW instruction format defines the different types of instructions that can be executed in parallel.
The instruction format consist of a field for:
FP ADD instruction, FP MUL instruction, INT ALU, Branch and ld/sw.

Compiler takes care of detecting independent instructions.

The goal is to have as many instructions within the format of a VLIW. However, the trade off here is that the compiler must be able to identify the independent instructions that are able to fill it.

If no instructions are found for e.g. the FP MUL and Branch field, these must be inserted with NOP instructions. This results in space being taken up by instructions that are not being executed.

Trade offs: Instruction format width
- Wider allows for more instructions being executed in parallel
- However it is harder for the compiler to find instructions to fill all the fields

Question 11

What is an advantage of VLIWs?

Answer 11

Avoids needing to add additional logic in hardware to detect if instructions are independent or not.
This is done by the compiler.

Question 12

How can we avoid empty instruction slots in a VLIW?

Answer 12

Loop unrolling: Gives more loop bodies, more likely to find independent instructions

Local scheduling: Re-organise instructions within one body of execution

Global scheduling: Scheduling across branches

Question 13

What are some issues with VLIW?

Answer 13

Increased code size: loop enrolling, potential empty slots

VLIWs operate in lock-step: There are no hazards between instruction - this is taken care of by the compiler. However, if one instruction has a delay, the whole pipeline must stall.

Reduced binary code compatibility: The VLIWs instruction format varies across architectures. More performant CPUs might want more instructions in parallel. Smaller CPUs might only need a few instructions in parallel. These would require different formats of instruction-encoding.

Question 14

What is static scheduling?

Answer 14

Processor executes instructions in program order.

Any prior reordering is done by the compiler. No re-ordering in hardware.

Question 15

What is dynamic scheduling?

Answer 15

OoO-execution

CPU itself reorders instructions by looking for instructions that can execute in parallel, and instructions that are dependent of each other.

These CPUs must preserve the original order of operations, as defined by the program to achieve correct execution.
Reordering and renaming is defined in tomasulo’s algorithm.

Question 16

How are anti-dependences taken care of in OoO-processors?

Answer 16

Register renaming

Question 17

What are the stages of an OoO pipeline?

Answer 17

IF, ID, renaming and dispatch is done in order

On dispatch, the instructions are inserted in the ROB, and into the issue buffers of the relevant execution unit.

In the issue buffers, the instructions access the register files to get their operands.

When all operands are ready, the instructions are issued on the different FUs.

Question 18

What are 3 components necessary for OoO execution?

Answer 18

Tomasulo’s algorithm

Register renaming

Reorder buffer

Question 19

How do we decide what reservation station to place an instruction?

Answer 19

Look at what type of instruction it is.

Load instruction -> load unit

Question 20

How is the ROB structured?

Answer 20

Newest on top of buffer, oldest on bottom

Question 21

What does ROB entries consist of?

Answer 21

Instruction itself
Flag saying if instruction is computed or not
Destination register
Value - when execution has completed.

Question 22

What does the reservation station entries consist of?

Answer 22

Operation to execute

Operands: the operands can be identified using the ROB-entry identifier. If this ROB entry has not finished execution, the current operand is not yet available.
This is a way of register renaming. Instead of writing the source registers, write the ROB-entry which writes to this source register.

What ROB-entry is this instruction -> what ROB entry must be updated when computation finishes.

Question 23

How does renaming happen in the Tomasulo algorithm?

Answer 23

Looks at all the instructions in the ROB, and if these have written to any of the registers that a current instruction is using. This way, true dependencies are identified.

Question 24

What happens when an instruction finishes execution?

Answer 24

ROB entry updates its done-flag and insert the value computed.
Instructions dependent on this ROB-entry will then be able to use this value.

Question 25

What is branch prediction (BTP - branch target prediction?)

Answer 25

Predict if a branch is taken.
Hardware structure
Uses previous history

Question 26

What are some types of branch predictors?

Answer 26

2-bit counter
2-level adaptive predictor

Question 27

What is a 2-bit saturating counter?

Answer 27

Local branch predictor

Only considers current branch, for each branch have a 2-bit saturated counter.

2 bits - 4 states (strongly not taken - strongly taken)

Question 28

What are a two-level adaptive predictor

Answer 28

Looks at global history to find correlation between branches.

Keeps a n-bit branch history. For each branch that passes, register as either a 1 or a 0.
The length of the history is dependent on how many bits are used in the branch history register.

The value in the branch history register is used to index into a pattern history table.

Each entry in the pattern history table keeps a 2-bit saturated counter

Question 29

What is a Gshare predictor?

Answer 29

Combines local and two-level predictors.

Takes a hash of the current branch index, and a hash of the n-bit branch history. XOR these values, and use the result to index into a table keeping the saturated counter.

Local predictor: Used by using the branch address
Global predictor: Using the branch history

Question 30

What is a disadvantage of the Gshare predictor?

Answer 30

If we want to increase the number of bits in the branch history register, we need to increase the number of bits in the hash and therefor increasing the size of the pattern history table.

It also takes time to fill the bits of the branch history register.

Question 31

What is a tournament predictor?

Answer 31

Use more than one type of predictor, e.g. have one global- and one local-predictor.

Have a selector that over time learns if the local- or the global-predictor gives best predictions.

Index into the selector using the branch address. The selector provides a control signal to a mux that decides if the local- or the global prediction should be used.

Question 32

What is a problem with needing a predictor for each branch and history?

Answer 32

Implies huge tables

History takes a long time to learn

Question 33

What is the Tagged Hybrid Predictor?

Answer 33

Tries to solve the problem of having large tables.
Instead, uses a hash the tables, and use the history that is longest.

Have a local 3-bit saturated predictor.
Then we have additional history based predictors. For each of the history based tables, the history size is increasing.
Does not store all of the bits in these tables, or else these would be very large.

First, we take the prediction from the local predictor. Then we see if we have a hit in the smallest table. If so, we choose this prediction. Then we check in all the other tables, and chooses the prediction where we get a hit in the largest history table.

Question 34

What is a BTB?

Answer 34

In parallell to branch prediction, we need to predict the target of the branch.

The BTB contains addresses of predicted targets. The PC of the current branch is used to index into the BTB. Meaning, we check all the entries in the BTB to see if the first field in the BTB entry is the current target. The second entry will in case of a hit contain the predicted target address.

Functions as a cache for target addresses. The first time a branch address index into the table, there will be a miss. The target address will in this case be calculated in the pipeline, and then stored in the BTB. This way, next time the branch address is used as index, we can retrieve the target address without needing to do a calculation.

Question 35

What is a return address predictor, and why is it used (RAS)?

Answer 35

A function(branch target) can be called from multiple addresses in a program. This makes it difficult to predict where the program should return.

The RAS is a small cache that pushes the next instruction on the stack (PC + 4), and pop from the stack on return.

Question 36

What happens if we mispredict a branch, in the tomasulo pipeline?

Answer 36

Need to flush instructions on the wrong execution path - flush from ROB.

Question 37

What is a memory hazard?

Answer 37

If the same memory location is read/written to by different instructions.

This instructions can use different registers to calculate the target memory address, and still end up with the same memory address.

Question 38

How can we avoid memory hazards?

Answer 38

WAW and WAR are eliminated because tomasulo ensure memory update in order.

For loads, not allow load to happen, if any older ROB entry occupied by a store, has a destination field that matches the value of the address field in the load.

Maintain the program order for the computation of the effective address of a load, with respect to all earlier stores.

This ensures that loads cannot access a memory location written to by an earlier store, unless this writing has finished.

Question 39

In the tomasulo algorithm, what happens during the write result stage?

Answer 39

Execution has finished.
Data is written on the Common Data Bus (watched by instructions in the issue buffers to see if their operands are ready).
Mark reservation station as available

Question 40

In the tomasulo algorithm, what happens during the commit stage?

Answer 40

Update registers with reorder results.
This happenbs when the instruction is at the head (last) in the ROB.
Result can also be written back to memory.
Instruction is removed from the ROB.