Pipelining

Question 1

Define

Parallelism and Concurrency

Answer 1

Parallelism: Use extra resources to solve a problem faster
Concurrency: Correctly and efficiently manage access to shared resources

Question 2

How can we make computation faster on hardware level?

Name 3 approaches

Answer 2

Vectorization
Instruction Level parallelism
Pipelining

Question 3

How does vectorization work?

Answer 3

Vectorization (simplified) is the process of rewriting a loop so that instead of processing a single element of an array N times, it processes (say) 4 elements of the array simultaneously N/4 times.

Same operation applied to many cases at the same time

Question 4

How does Instruction Level Parallelism work? ILP

Answer 4

Independent operations are performed parallel.

Question 5

How can we increase oppurtunities for ILP? Name 3

Answer 5

Speculative Execution: Predict results to continue execution
Our-of-Order execution: Potentially change execution order of instructions
Pipelining

Question 6

What is a balanced pipeline?

Answer 6

all steps require same time

Question 7

How is the throughput of a pipeline defined?

Answer 7

Amount of work that can be done by a system in a given period of time

Question 8

How is Latency in a pipeline defined?

Answer 8

Time needed to perform a given computation (e.g. a CPU instruction)

Question 9

What is the throughput in CPU’s?

Answer 9

Number of instructions completed per second

Question 10

What is the throughput bound of a pipeline?

Answer 10

Throughput bound = 1 / max(computationtime(stages))

Question 11

What is the latency bound?

Answer 11

Latency bound = number of stages * max(computationtime(stages))

Question 12

See picture
What is the bound on latency?
What is the throughput?
What is the total time?

Answer 12

The bound on latency for each load is now: 6 * 6 = 36 seconds.
The throughput is approximately: 1 load / 6 seconds = ~ 10 loads / minute.

The total time for all 5 loads is 60 seconds.

Question 13

Define Pipelining.

Answer 13

Pipelining is a technique where multiple independent instructions are overlapped in execution through
the use of several execution units, provided they are available for use.

Question 14

Informal definition of throughput put in words. Also give formula.

Answer 14

Throughput is the number of instructions that exit the pipeline per a given time unit. Throughput can be calculated as follows:

Throughput:= 1 / max(computationtime(stages))

Question 15

What is the goal designing a pipeline. Use Latency and Throughput.

Answer 15

When designing a pipeline, it’s always our aim to increase throughput and decrease latency as much as possible

Question 16

See picture
What is the latency?
What is the throughput?

Answer 16

Latency = 30 min
Throughput = 1 load per 15 minutes

In a balanced pipeline just look at how many operations are left in the last load. in the picture thats 3. these 3 operations each take 5 minutes so 15 minutes.

Question 17

See picture
This is an unbalanced pipeline
What is the throughput?
What is happening to the latency?

Answer 17

throughput = 1 load per 10 minutes

Latency is increasing in every load hence the pipeline is unbalanced.

Question 18

Given a pipeling how do calculate how long for example 100 processes take to terminate? IMPORTANT

example this pipeline with these time how long does it take to execute 100 processes?

1) 40 ns 2) 50 ns 3) 30 ns 4) 40 ns

Answer 18

Add up all the times except for the longest time than add (the longest time * the amount of processes here 100) to the sum

40+30+40 + (50*100) 5110ms

Question 19

Easy way to find Latency if pipeline is balanced? And when is the pipeline balanced?

Answer 19

• Latency if pipeline is balanced: sum of all steps

- Pipeline is balanced if first step >= other steps

Question 20

Easy way to find Throughput?

Answer 20

1 / longest step

Question 21

Balance / Unbalanced Pipeline how to see quickly?

Answer 21

Pipeline is balanced if first step >= other steps