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?
-
Show this thread
-
Replying to @cmuratori
max(t_i) * (n-1) + sum(t_i) is a lower bound and tight in case max(t_i) = t_0. Upper bound is sum(t_i)*n which is tight in case there's only one stage. Neither *has* to be tight though. Don't think a general formula exists.
1 reply 0 retweets 0 likes -
Replying to @IsntTrivial
Where are you getting those bounds from, though? Why would it matter if max(t_i) is on t_0 or anywhere else?
1 reply 0 retweets 0 likes -
Replying to @cmuratori
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.
2 replies 0 retweets 0 likes -
Replying to @IsntTrivial
But I'm pretty sure the equation I proposed already accounts for that. Can you show an example where it fails?
1 reply 0 retweets 0 likes -
Replying to @cmuratori
t = [1, 3, 1, 3], n=2. The formula gives 7 + 3 = 10. However, this will take 12 steps. Diagram in a pastebinhttps://pastebin.com/N0JfzxP6
1 reply 0 retweets 0 likes -
Replying to @IsntTrivial
You cheated by counting two different ways :) Here is the same diagram you drew, but for a single input. Using your counting, the "t single" is clearly 9, not 7. So in your example, the formula gives 9 + 3 = 12, which is exactly what your diagram showed.https://pastebin.com/2RicjZqX
1 reply 0 retweets 0 likes -
Replying to @cmuratori
Oof, caught red-handed! I think t_single is 8 though, since the dot is already out at time 9 ;)
1 reply 0 retweets 0 likes -
Replying to @IsntTrivial
It doesn't matter how you count, you just have to count the same. So if you want t_single to be 8, your example has to be 11. Either way, my formula works correctly for your example as far as I can tell, so it is not a case where the formula fails?
1 reply 0 retweets 0 likes -
Replying to @cmuratori
I think you are right and I am wrong. I also tried with 3 items and various combinations of stage lengths, but I'm not able to make it last any longer or shorter. Seems like it doesn't matter that there could be various "other bottlenecks". Far from a proof though. :/
1 reply 0 retweets 0 likes
I think a proof is not too hard. We may try it and see. But it still doesn't change the fact that I feel like this should have been proved before, and it should probably have a name, like "Milton's Conjecture" or "Bonham's Law" or something.
-
-
Replying to @cmuratori
Pinedo's "Scheduling Theory, Algorithms, and Systems" has your formula (Theorem 6.1.8, proof as exercise), but it's for when each task takes a fixed amount of time for any stage, rather than each stage taking a fixed amount of time for any task.
1 reply 0 retweets 0 likes -
Replying to @IsntTrivial @cmuratori
I should get to work. If you want to look for yourself (it's probably easier to just find a proof), the problem is mathematically described as a permutation flow shop, you're optimizing the makespan. In notation Fm|prmu|C_max.
0 replies 0 retweets 0 likes
End of conversation
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.