MODULE 5 �Pipelining

Overview

• Pipelining is widely used in modern processors.
• Pipelining improves system performance in terms of throughput.
• Pipelined organization requires sophisticated compilation techniques.

Basic Concepts

Making the Execution of Programs Faster

• Use faster circuit technology to build the processor and the main memory.
• Arrange the hardware so that more than one operation can be performed at the same time.
• In the latter way, the number of operations performed per second is increased even though the elapsed time needed to perform any one operation is not changed.

Traditional Pipeline Concept

• Laundry Example
• Ann, Brian, Cathy, Dave �each have one load of clothes �to wash, dry, and fold
• Washer takes 30 minutes

​

• Dryer takes 40 minutes

​

• “Folder” takes 20 minutes

Traditional Pipeline Concept

• Sequential laundry takes 6 hours for 4 loads
• If they learned pipelining, how long would laundry take?

30

40

20

30

40

20

30

40

20

30

40

20

6 PM

7

8

9

10

11

Midnight

Time

Traditional Pipeline Concept

• Pipelined laundry takes 3.5 hours for 4 loads

6 PM

7

8

9

10

11

Midnight

T

a

s

k

​

O

r

d

e

r

Time

Traditional Pipeline Concept

• Pipelining doesn’t help latency of single task, it helps throughput of entire workload
• Pipeline rate limited by slowest pipeline stage
• Multiple tasks operating simultaneously using different resources
• Potential speedup = Number pipe stages
• Unbalanced lengths of pipe stages reduces speedup
• Time to “fill” pipeline and time to “drain” it reduces speedup
• Stall for Dependences

6 PM

7

8

9

T

a

s

k

​

O

r

d

e

r

Time

Use the Idea of Pipelining in a Computer

F

1

E

1

F

2

E

2

F

3

E

3

I

1

I

2

I

3

(a) Sequential execution

Instruction

fetch

unit

Ex

ecution

unit

Interstage buffer

B1

(b) Hardware organization

T

ime

F

1

E

1

F

2

E

2

F

3

E

3

I

1

I

2

I

3

Instruction

(c) Pipelined execution

Figure 8.1. Basic idea of instruction pipelining.

Clock cycle

1

2

3

4

T

ime

Fetch + Execution

Use the Idea of Pipelining in a Computer

Fetch + Decode

+ Execution + Write

Textbook page: 457

Role of Cache Memory

• Each pipeline stage is expected to complete in one clock cycle.
• The clock period should be long enough to let the slowest pipeline stage to complete.
• Faster stages can only wait for the slowest one to complete.
• Since main memory is very slow compared to the execution, if each instruction needs to be fetched from main memory, pipeline is almost useless.
• Fortunately, we have cache.

Pipeline Performance

• The potential increase in performance resulting from pipelining is proportional to the number of pipeline stages.
• However, this increase would be achieved only if all pipeline stages require the same time to complete, and there is no interruption throughout program execution.
• Unfortunately, this is not true.

Data Hazards

Data Hazards

• We must ensure that the results obtained when instructions are executed in a pipelined processor are identical to those obtained when the same instructions are executed sequentially.
• Hazard occurs

A ← 3 + A

B ← 4 × A

• No hazard

A ← 5 × C

B ← 20 + C

• When two operations depend on each other, they must be executed sequentially in the correct order.
• Another example:

Mul R2, R3, R4

Add R5, R4, R6

Data Hazards

Operand Forwarding,� Instruction Hazards

Operand Forwarding

• Instead of from the register file, the second instruction can get data directly from the output of ALU after the previous instruction is completed.
• A special arrangement needs to be made to “forward” the output of ALU to the input of ALU.

Handling Data Hazards in Software

• Let the compiler detect and handle the hazard:

I1: Mul R2, R3, R4

NOP

NOP

I2: Add R5, R4, R6

• The compiler can reorder the instructions to perform some useful work during the NOP slots.

Side Effects

• The previous example is explicit and easily detected.
• Sometimes an instruction changes the contents of a register other than the one named as the destination.
• When a location other than one explicitly named in an instruction as a destination operand is affected, the instruction is said to have a side effect. (Example?)
• Example: conditional code flags:

Add R1, R3

AddWithCarry R2, R4

• Instructions designed for execution on pipelined hardware should have few side effects.

Instruction Hazards

Overview

• Whenever the stream of instructions supplied by the instruction fetch unit is interrupted, the pipeline stalls.
• Cache miss
• Branch

Unconditional Branches

Branch Timing

- Branch penalty

​

- Reducing the penalty

Instruction Queue and Prefetching

F : Fetch

instruction

E : Ex

ecute

instruction

W : Write

results

D : Dispatch/

Decode

Instruction queue

Instruction fetch unit

Figure 8.10. Use of an instruction queue in the hardware organization of Figure 8.2b.

unit

Conditional Braches

• A conditional branch instruction introduces the added hazard caused by the dependency of the branch condition on the result of a preceding instruction.
• The decision to branch cannot be made until the execution of that instruction has been completed.
• Branch instructions represent about 20% of the dynamic instruction count of most programs.

Delayed Branch

• The instructions in the delay slots are always fetched. Therefore, we would like to arrange for them to be fully executed whether or not the branch is taken.
• The objective is to place useful instructions in these slots.
• The effectiveness of the delayed branch approach depends on how often it is possible to reorder instructions.

Delayed Branch

Add

LOOP

Shift_left

R1

Decrement

Branch=0

R2

LOOP

NEXT

(a) Original program loop

LOOP

Decrement

R2

Branch=0

Shift_left

LOOP

R1

NEXT

(b) Reordered instructions

​

Figure 8.12. Reordering of instructions for a delayed branch.

Add

R1,R3

R1,R3

Delayed Branch

F

E

F

E

F

E

F

E

F

E

F

E

F

E

Instruction

Decrement

Branch

Shift (delay slot)

Figure 8.13. Execution timing showing the delay slot being filled

during the last two passes through the loop in Figure 8.12.

​

Decrement (Branch tak

en)

Branch

Shift (delay slot)

Add (Branch not tak

en)

1

2

3

4

5

6

7

8

Clock c

ycle

T

ime

Branch Prediction

• To predict whether or not a particular branch will be taken.
• Simplest form: assume branch will not take place and continue to fetch instructions in sequential address order.
• Until the branch is evaluated, instruction execution along the predicted path must be done on a speculative basis.
• Speculative execution: instructions are executed before the processor is certain that they are in the correct execution sequence.
• Need to be careful so that no processor registers or memory locations are updated until it is confirmed that these instructions should indeed be executed.

Incorrectly Predicted Branch

F

1

F

2

I

1

(Compare)

I

2

(Branch>0)

I

3

D

1

E

1

W

1

F

3

F

4

F

k

D

k

D

3

X

X

I

4

I

k

Instruction

Figure 8.14. Timing when a branch decision has been incorrectly predicted

as not taken.

E

2

Clock cycle

1

2

3

4

5

6

D

2

/P

2

T

ime

Branch Prediction

• Better performance can be achieved if we arrange for some branch instructions to be predicted as taken and others as not taken.
• Use hardware to observe whether the target address is lower or higher than that of the branch instruction.
• Let compiler include a branch prediction bit.
• So far the branch prediction decision is always the same every time a given instruction is executed – static branch prediction.

Influence on Instruction Sets

Overview

• Some instructions are much better suited to pipeline execution than others.
• Addressing modes
• Conditional code flags

Addressing Modes

• Addressing modes include simple ones and complex ones.
• In choosing the addressing modes to be implemented in a pipelined processor, we must consider the effect of each addressing mode on instruction flow in the pipeline:
• Side effects
• The extent to which complex addressing modes cause the pipeline to stall
• Whether a given mode is likely to be used by compilers

Recall

Load X(R1), R2

Load (R1), R2

Complex Addressing Mode

F

F

D

D

E

X

+

[R1]

[X

+

[R1]]

[[X

+

[R1]]]

Load

Ne

xt instruction

(a) Complex addressing mode

W

1

2

3

4

5

6

7

Clock c

ycle

T

ime

W

F

orw

ard

Load (X(R1)), R2

Simple Addressing Mode

X

+

[R1]

F

D

F

F

F

D

D

D

E

[X

+

[R1]]

[[X

+

[R1]]]

Add

Load

Load

Ne

xt instruction

(b) Simple addressing mode

W

W

W

W

Add #X, R1, R2

Load (R2), R2

Load (R2), R2

Addressing Modes

• In a pipelined processor, complex addressing modes do not necessarily lead to faster execution.
• Advantage: reducing the number of instructions / program space
• Disadvantage: cause pipeline to stall / more hardware to decode / not convenient for compiler to work with
• Conclusion: complex addressing modes are not suitable for pipelined execution.

Addressing Modes

• Good addressing modes should have:
• Access to an operand does not require more than one access to the memory
• Only load and store instruction access memory operands
• The addressing modes used do not have side effects
• Register, register indirect, index

Conditional Codes

• If an optimizing compiler attempts to reorder instruction to avoid stalling the pipeline when branches or data dependencies between successive instructions occur, it must ensure that reordering does not cause a change in the outcome of a computation.
• The dependency introduced by the condition-code flags reduces the flexibility available for the compiler to reorder instructions.

Conditional Codes

Add

Compare

Branch=0

R1,R2

R3,R4

. . .

Compare

Add

Branch=0

R3,R4

R1,R2

. . .

(a) A program fragment

(b) Instructions reordered

Figure 8.17. Instruction reordering.

Conditional Codes

• Two conclusion:
• To provide flexibility in reordering instructions, the condition-code flags should be affected by as few instruction as possible.
• The compiler should be able to specify in which instructions of a program the condition codes are affected and in which they are not.

Datapath and Control Considerations

Original Design

Pipelined Design

- Separate instruction and data caches

- PC is connected to IMAR

- DMAR

- Separate MDR

- Buffers for ALU

- Instruction queue

- Instruction decoder output

- Reading an instruction from the instruction cache

- Incrementing the PC

- Decoding an instruction

- Reading from or writing into the data cache

- Reading the contents of up to two regs

- Writing into one register in the reg file

- Performing an ALU operation

Superscalar Operation

Overview

• The maximum throughput of a pipelined processor is one instruction per clock cycle.
• If we equip the processor with multiple processing units to handle several instructions in parallel in each processing stage, several instructions start execution in the same clock cycle – multiple-issue.
• Processors are capable of achieving an instruction execution throughput of more than one instruction per cycle – superscalar processors.
• Multiple-issue requires a wider path to the cache and multiple execution units.

Superscalar

Timing

I

1

(F

add)

D

1

D

2

D

3

D

4

E

1A

E

1B

E

1C

E

2

E

3

E

3

E

3

E

4

W

1

W

2

W

3

W

4

I

2

(Add)

I

3

(Fsub)

I

4

(Sub)

Figure 8.20. An example of instruction execution flow in the processor of Figure 8.19,

assuming no hazards are encountered.

1

2

3

4

5

6

Clock c

ycle

T

ime

F

1

F

2

F

3

F

4

7

Out-of-Order Execution

• Hazards
• Exceptions
• Imprecise exceptions
• Precise exceptions

I

1

(F

add)

D

1

D

2

D

3

D

4

E

1A

E

1B

E

1C

E

2

E

3A

E

3B

E

3C

E

4

W

1

W

2

W

3

W

4

I

2

(Add)

I

3

(Fsub)

I

4

(Sub)

1

2

3

4

5

6

Clock c

ycle

T

ime

(a) Delayed write

F

1

F

2

F

3

F

4

7

Execution Completion

• It is desirable to used out-of-order execution, so that an execution unit is freed to execute other instructions as soon as possible.
• At the same time, instructions must be completed in program order to allow precise exceptions.
• The use of temporary registers
• Commitment unit

I

1

(F

add)

D

1

D

2

D

3

D

4

E

1A

E

1B

E

1C

E

2

E

3A

E

3B

E

3C

E

4

W

1

W

2

W

3

W

4

I

2

(Add)

I

3

(Fsub)

I

4

(Sub)

1

2

3

4

5

6

Clock c

ycle

T

ime

(b) Using temporary registers

TW

2

TW

4

7

F

1

F

2

F

3

F

4

Performance Considerations

Overview

• The execution time T of a program that has a dynamic instruction count N is given by:

​

where S is the average number of clock cycles it takes to fetch and execute one instruction, and R is the clock rate.

• Instruction throughput is defined as the number of instructions executed per second.

​

Overview

• An n-stage pipeline has the potential to increase the throughput by n times.
• However, the only real measure of performance is the total execution time of a program.
• Higher instruction throughput will not necessarily lead to higher performance.
• Two questions regarding pipelining
• How much of this potential increase in instruction throughput can be realized in practice?
• What is good value of n?

Number of Pipeline Stages

• Since an n-stage pipeline has the potential to increase the throughput by n times, how about we use a 10,000-stage pipeline?
• As the number of stages increase, the probability of the pipeline being stalled increases.
• The inherent delay in the basic operations increases.
• Hardware considerations (area, power, complexity,…)