next up previous
Next: 8.6 Putting it all Up: 8 Sorting on butterflies Previous: 8.4 Bounding the congestion

8.5 Bounding the cumulative delay

Since a subbutterfly does not begin to execute its algorithm until the larger butterfly at the previous level of recursion is finished, delay in excess of the time allotted to each butterfly accumulates over the course of the algorithm. An M-input butterfly is allotted tex2html_wrap_inline4189 time to perform its steps. However, Steps 6, 7, and 8 are not guaranteed to terminate in time tex2html_wrap_inline4191 . It is tempting to try to prove that these steps terminate quickly with high probability. This approach fails because at the lower levels of the recursion the problem size is so small that nothing can be ascertained with high probability. Instead we must argue that although delay may occur at any particular step, it is unlikely that a lot of delay will accumulate over a sequence of steps.

The delay from Step 8 is relatively easy to analyze. This step requires tex2html_wrap_inline4193 time; the delay depends only on the congestion. Lemma 8.5 bounds the probability that the congestion is large.

There are two possible causes of delay in Steps 6 and 7. A poor set of random rows for the packets can cause congestion at some node, which guarantees that some packet will arrive at its destination late. On the other hand, even if the congestion is small, a poor choice for the random ranks used by the scheduling algorithm may delay a packet. The following pair of lemmas bounds the probability that the delay from these steps is large. The first is a restatement of the Theorem 2.9 in a slightly different form. It bounds the probability that a packet will be delayed when the congestion is small. The second puts this bound together with the bound that the congestion is large from Lemma 8.5.


Proof: The proof of Theorem 2.9 shows that the probability that any packet arrives at its destination after step tex2html_wrap_inline4211 is at most


where tex2html_wrap_inline4215 and tex2html_wrap_inline4217 are constants. Suppose that tex2html_wrap_inline4219 . Then this probability is at most tex2html_wrap_inline4221 which is less than tex2html_wrap_inline4223 . Now let tex2html_wrap_inline4225 . Then the probability that any packet arrives at its destination after step tex2html_wrap_inline4227 (for some tex2html_wrap_inline4229 ) is at most tex2html_wrap_inline4231 , where tex2html_wrap_inline4233 .

to .667emto .667em


Proof: For the sake of brevity, we examine Step 7 only. A similar analysis holds for Step 6.

We break the analysis into two cases according to whether the congestion is small or large. Let T be the time at which the last packet arrives. Then


We use Lemma 8.6 to bound the first term on the right. Plugging in tex2html_wrap_inline4245 for c yields tex2html_wrap_inline4249 . We use Lemma 8.5 to bound the second term on the right. Plugging in tex2html_wrap_inline4251 for c yields tex2html_wrap_inline4255 . Since tex2html_wrap_inline4257 , and tex2html_wrap_inline4259 , tex2html_wrap_inline4261 , and tex2html_wrap_inline4263 are constants, tex2html_wrap_inline4265 , for sufficiently large N.

to .667emto .667em

The following lemma bounds the combined delay of Steps 6, 7, 8.


Proof: Step 8 can be performed deterministically in time tex2html_wrap_inline4279 . From Lemma 8.5 we have tex2html_wrap_inline4281 , for s > L. For our purposes, a weaker bound on this probability suffices. Since tex2html_wrap_inline4285 is a constant, there is a constant tex2html_wrap_inline4287 such that tex2html_wrap_inline4289 for sufficiently large L. Combining this bound with that of Lemma 8.7 yields the desired result.

to .667emto .667em

To complete our analysis of the algorithm, we need to bound the probability that more than tex2html_wrap_inline4293 delay accrues during the sort.


Proof: The cumulative delay at the bottom level of the recursion is the sum of the delay at each of the butterflies on the branch of the recursion tree from the top level to the leaf. Let tex2html_wrap_inline4303 be the delay beyond tex2html_wrap_inline4305 at the ith level of the recursion. Then tex2html_wrap_inline4309 by Lemma 8.8. Notice that there is no dependence on i in this expression. Let D be the cumulative delay on a branch of the recursion from the top level to a leaf. Then tex2html_wrap_inline4315 . Generating functions help us here. The generating function for tex2html_wrap_inline4317 is


where tex2html_wrap_inline4321 can be thought of as a place holder. Since the delay at each level of the recusion is independent of the delays at other levels, we can sum the delay by multiplying the generating functions. Thus, the generating function for the cumulative delay is tex2html_wrap_inline4323 . The coefficient of tex2html_wrap_inline4325 in tex2html_wrap_inline4327 is at most tex2html_wrap_inline4329 . For tex2html_wrap_inline4331 , this coefficient is at most tex2html_wrap_inline4333 . For any tex2html_wrap_inline4335 , there is a tex2html_wrap_inline4337 such that tex2html_wrap_inline4339 is at most tex2html_wrap_inline4341 .

To bound the probability that the cumulative delay exceeds tex2html_wrap_inline4343 on any branch of the recursion, we sum the individual probabilities for all of the branches. There are at most N branches. Thus, the sum is at most tex2html_wrap_inline4347 . For any tex2html_wrap_inline4349 , there is a tex2html_wrap_inline4351 such that this sum is at most tex2html_wrap_inline4353 .

to .667emto .667em

next up previous
Next: 8.6 Putting it all Up: 8 Sorting on butterflies Previous: 8.4 Bounding the congestion

Bruce Maggs
Mon Jul 22 22:57:44 EDT 1996