Is there any standard equation for the cost to process n items through a pipeline of fixed cost stages? Maybe from queuing theory? Like t_total(n) = t_single + t_worst*(n - 1) where t_single is the sum of the stage costs and t_worst is cost of the most expensive stage?
Where are you getting those bounds from, though? Why would it matter if max(t_i) is on t_0 or anywhere else?
-
-
The upper bound is simply the total amount of work if the pipeline is executed on a single processor. The lower bound is (I realize now) incorrect, but the idea is that all tasks have to get to the bottleneck and be processed there, before you can process the final task fully.
-
But I'm pretty sure the equation I proposed already accounts for that. Can you show an example where it fails?
- Show replies
New conversation -
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.