Pipelining Flashcards
Define
Parallelism and Concurrency
Parallelism: Use extra resources to solve a problem faster
Concurrency: Correctly and efficiently manage access to shared resources
How can we make computation faster on hardware level?
Name 3 approaches
Vectorization
Instruction Level parallelism
Pipelining
How does vectorization work?
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
How does Instruction Level Parallelism work? ILP
Independent operations are performed parallel.
How can we increase oppurtunities for ILP? Name 3
Speculative Execution: Predict results to continue execution
Our-of-Order execution: Potentially change execution order of instructions
Pipelining
What is a balanced pipeline?
all steps require same time
How is the throughput of a pipeline defined?
Amount of work that can be done by a system in a given period of time
How is Latency in a pipeline defined?
Time needed to perform a given computation (e.g. a CPU instruction)
What is the throughput in CPU’s?
Number of instructions completed per second
What is the throughput bound of a pipeline?
Throughput bound = 1 / max(computationtime(stages))
What is the latency bound?
Latency bound = number of stages * max(computationtime(stages))
See picture
What is the bound on latency?
What is the throughput?
What is the total time?
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.
Define Pipelining.
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.
Informal definition of throughput put in words. Also give formula.
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))
What is the goal designing a pipeline. Use Latency and Throughput.
When designing a pipeline, it’s always our aim to increase throughput and decrease latency as much as possible
See picture
What is the latency?
What is the throughput?
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.
See picture
This is an unbalanced pipeline
What is the throughput?
What is happening to the latency?
throughput = 1 load per 10 minutes
Latency is increasing in every load hence the pipeline is unbalanced.
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
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
Easy way to find Latency if pipeline is balanced? And when is the pipeline balanced?
- Latency if pipeline is balanced: sum of all steps
- Pipeline is balanced if first step >= other steps
Easy way to find Throughput?
1 / longest step
Balance / Unbalanced Pipeline how to see quickly?
Pipeline is balanced if first step >= other steps
