algorithmpipelinepipelining

Proving that a k stage pipeline can be at most k times faster than that of a nonpipelined one

I roughly (abstractly) understand why pipeline is k times faster than non-pipelined one (like this way):

  1. K stage pipeline dividing the circuit into k parts.
  2. Each stage has the same transistor delay (Ideally)
  3. So it is K times faster.(like using conveyor belt system on car factory)

But I cannot understand this mathematical expression:

clock cycle time = t 
number of command = n  
speedup = (n*k*t)/((k-1)*t+n*t) = (n*k*t)/(k*t+(n-1)*t)

if n -> infinite: speedup is k

What I don't know is: What ((k-1)t+nt) means?

I can just understand (nkt) means non-pipelined time, so I believe ((k-1)*t+n*t) should be the pipedlined time.

But, why ((k-1)*t+n*t) is pipelined time?

Solution

  • You were correct - (k-1)*t+n*t is the time for executing n command in pipeline.

    You should think of it as follow:

    In the first (k-1) cycle (t) the pipe is filling up. After that time, 0 commends has been fully execute but all the pipe is filled.

    From now on, every cycle t you will have new command who finished to execute (because of the pipeline effect) -> therefor, the n*t.

    In total, after (k-1)*t + n*t is the time for execute n command in pipeline.

    Hope that make it more clear!