ILP Theory

Question 1

What is the goal of instruction level parallelism?

Answer 1

Is to maximize performance in terms of throughput. In other words, to increase the instructions per clock and decrease the clocks per instruction

Question 2

What is the relationship between dependencies in the code, hazards and instruction level parallelism?

Answer 2

If two instructions are dependent on each other, they cannot be executed in parallel, they must be executed in order or partially overlapped.

Also, call dependencies might become hazards

Dependencies are a property of the code, while hazards are a property of the pipeline architecture

Question 3

What are the three possible dependencies in a code?

Answer 3

Data, name, and control dependencies

Question 4

What are the data dependencies?

Answer 4

A data dependencie occurs when an instruction depends on the data produced by the previous instruction

Question 5

What are the control dependencies?

Answer 5

They are the ones related to branching. They impose the ordering of instructions.

Question 6

What are the name dependencies?

Answer 6

The name dependencies occur when two instructions use the same register or memory location

Question 7

What are the two types of name dependencies?

Answer 7

Anti-dependencie and output dependencies

Question 8

What are the anti-dependencies?

Answer 8

The anti-dependencies occurs when a preceding instruction is reading a register or memory location later written by an older instruction. This generate a write after read Hazard where the preceding instruction reads the wrong value from the register or memory location

Question 9

What are the output dependencies?

Answer 9

When to instructions right at the same register or memory location. It could generate a write after write hazard. The order must be preserved in order to make the value of the old instruction the one that is written later.

Question 10

What is the cause of name dependencies?

Answer 10

The cause of name dependencies is register reuse

Question 11

What is a possible solution for name dependencies

Answer 11

Register renaming. If the register used could be changed the conflict would not exist anymore

Question 12

What are the two possibilities to perform register renaming?

Answer 12

Register renaming could be performed either statically by the compiler or dynamically by the hardware

Question 13

What are the hazards a pipeline can face?

Answer 13

The reads after writes hazards, which corresponds to true data dependencies

The write after reads Hazard, which correspondence to anti-dependencies

And finally, the write after write Hazzard, which corresponds to output dependencies

Question 14

What are the properties that need to be preserved in order to preserve program correctness?

Answer 14

Data flow, and exception behavior (changes in the ordering of instructions must not change how the exceptions are raised in the program)

Question 15

What are the main characteristics of a multi cycle in order pipeline?

Answer 15

In order issue of instructions

Multiple functional unit is with different latencies

Delayed write back, in order to force in order to commit of instructions

One instruction in and one instruction out at every cycle

Question 16

What are the consequences of in order issue and in order commit in multi cycle in order pipelines

Answer 16

The consequences are, you maintain the data flow and the exception behavior of the program, and also avoid write after write hazards and write after read hazards

Question 17

What are the main characteristics of a multi cycle out of order pipeline

Answer 17

The ID stage is divided into two stages the instruction decode and the register read

Multiple functional unities with different latencies

Out of order commit

Question 18

What are the consequences of the in order issue, out of order commit and out of order execution in multi cycle out of order pipelines

Answer 18

It implies in the necessity to verify the write of the write, write after read hazards, and imprecise exceptions

Question 19

What is the problem a dynamic scheduling pipeline tries to solve

Answer 19

It tries to solve true data dependencies that might cause read after write hazards. Once these kind of hazards cannot be solved by forwarding, the stalls are unavailable, therefore the dynamically scheduling issues data independent instructions in order to feel these stalls

Question 20

DIVD F0,F2,F4 # exec. takes many cycles
ADDD F10,F0,F8 # RAW F0
SUBD F12,F8,F14

How would a dynamically scheduler proceed?

Answer 20

BASIC IDEA: to enable SUBD to proceed => this generates out-of-order execution

Question 21

When does an exception becomes imprecise?

Answer 21

Exception is imprecise if the processor state when an exception is raised does not look exactly as if the instructions were executed in order

Question 22

What are the reasons imprecise exceptions occur?

Answer 22

Imprecise exceptions can occur in out of order pipelines because the pipeline may have already completed instructions that are later in program order than the instruction causing the exception, or also the pipeline may have not yet completed some instructions that are earlier in the program order than the instruction causing the exception

Question 23

How does a multiple issue pipeline increases the performance of a processor?

Answer 23

By introducing more parallelism Through fetching and executing more than one instruction per clock

Question 24

What are the ideals CPI both in multiple pipelines and dual issue pipelines

Answer 24

The ideal CPI in a multiple pipeline is equal to one while in a dual issue pipeline corresponds to .5

Question 25

What are the steps towards exploiting more instruction level parallelism?

Answer 25

From a sequential non-pipelined execution of the program with an CPI greater than one we could implement a in order scalar pipeline increasing the CPI to one

Moreover, by using multi cycling instructions based on different functional unit, we could reduce the possible stalls in the program still keeping the Ideal CPI equal to one. In these step, we could also have an out of order execution and commit.

to further reduce the stall cycles we could also implement in the multi issue pipelines the dynamic scheduling. Finally by combine the dynamic scheduling with multiple issues we arrive at the super scaler pipelines where the ideal CPI is lower than one.

We could also follow these logics by using static scheduling

Question 26

What is static scheduling?

Answer 26

Static scheduling is done by the compiler, in which instructions are re-ordered into dependency free, parallel instructions otherwise NOPs are introduced in the code.

Question 27

What are the main limits of static scheduling?

Answer 27

Unpredictable branch behavior

Unpredictable cash behavior

Complexity of compiler technology

Called size explosion due to insertion of NOPs operations

Question 28

What are the differences between super scalar processors and VLIW processors regarding the time and place where Instruction order is conceived

Answer 28

For a super scalar processor, it is decided at runtime, by the hardware logic meanwhile for a VLIW processor is decided at compiler time, by the compiler