Understanding the speedup equation with Pipelining

Question

I'm having a lot of trouble understanding calculating the speedup of Pipelining. This is the slide that was provided for this in my Computer Organization class.

I don't really understand the formula.

Why is it 2n? Why is it 0.5n + 1.5?

My professor started to explain the 1.5 comes from 1.5 hours between when A starts and B starts...and thats easy to see with a picture like that but a problem like...

Suppose you have a pipelined machine with a 10 stage pipeline and a program with 1000 instructions whose dependencies are such that the pipeline does not stall. If each stage of the pipe takes 1 cycle, what is the speedup gained by pipelining compared to execution of the program on the same machine without exploiting the pipeline?

I don't think I could just draw a picture...plus I know there has to be some better way than drawing a picture.

Can anyone explain speedup with pipeling and/or provide some good material online to understand this?

Answer 1

The classic example for pipeline that I have encountered is an assembly line! So say if you had A-B-C-D-E as the five stages to completion, and each of them involving different resources; When E is being worked upon the resources that can do A-D are idle and that's what pipelining exploits in order to get some form of concurrency.

So your timeline would look something like - and say you had 1000 work items each of which did the above 1. Without pipelining you would basically repeat A-B-C-D-E a 1000 times, leading to time slot of 5000! 2. With pipeline you would get A-B-C-D-E for the first round, and then every other time tick, you are going to get an output i.e

A-B-C-D-E       // ends at t=5
__A-B-C-D-E     // ends at t=6!
____A-B-C-D-E   // ends at t=7!
.....
...... 
............
A-B-C-D-E // 1000th process ends at t=1005 (starts at t=1000)

I guess you could extend that for the 10 stage pipelining case as well.