next up previous
Next: 8.4 Bounding the congestion Up: 8 Sorting on butterflies Previous: 8.2 Analysis

8.3 Bounding the load

The first step in the analysis is to show that, with high probability, the number of splitter candidates chosen by each butterfly is within a constant factor of the expectation. We say that an M-input butterfly is well-partitioned if the number of splitter candidates chosen is between tex2html_wrap_inline3943 and tex2html_wrap_inline3945 . The tex2html_wrap_inline3947 upper bound ensures that the candidates can be sorted deterministically by the butterfly in tex2html_wrap_inline3949 time and the tex2html_wrap_inline3951 lower bound implies that the subbutterflies at the next level of recursion will have at most tex2html_wrap_inline3953 inputs. If all of the butterflies are well-partitioned, then the algorithm terminates after tex2html_wrap_inline3955 levels of recursion. (The choice of tex2html_wrap_inline3957 and tex2html_wrap_inline3959 as the coefficients of tex2html_wrap_inline3961 are not particularly important. Other constants would serve equally well.)

  lemma901

Proof: We begin by considering a single M-input butterfly that is to sort n packets. Since each packet chooses independently to be a candidate, the number of candidates has a binomial distribution. Let S be the number of successes in r independent Bernoulli trials where each trial has probability p of success. Then we have tex2html_wrap_inline3981 . We estimate the area under the tails of this binomial distribution using a Chernoff-type bound [8]. Following Angluin and Valiant [3] we have

eqnarray909

for tex2html_wrap_inline3983 and tex2html_wrap_inline3985 . In our application r = n, tex2html_wrap_inline3989 , tex2html_wrap_inline3991 , and tex2html_wrap_inline3993 . For any fixed constant tex2html_wrap_inline3995 , there is a constant tex2html_wrap_inline3997 such that the right-hand sides of the two inequalities sum to at most tex2html_wrap_inline3999 for tex2html_wrap_inline4001 .

To bound the probability that any butterfly is not well-partitioned, we sum the probabilities for all of the individual butterflies. Over the course of the algorithm, the algorithm is invoked on at most tex2html_wrap_inline4003 individual butterflies. Thus, the sum is at most tex2html_wrap_inline4005 . For any tex2html_wrap_inline4007 , there is a tex2html_wrap_inline4009 such that this sum is at most tex2html_wrap_inline4011 .


to .667emto .667em

The next lemma shows that, with high probability, the number of packets in each interval is at most a constant factor times its expectation. We say that an M-input butterfly that is assigned n packets to sort is tex2html_wrap_inline4017 -split if every interval has size at most tex2html_wrap_inline4019 . As we shall see, if every butterfly is tex2html_wrap_inline4021 -split and there are tex2html_wrap_inline4023 levels of recursion, then by lightly loading the butterfly we can ensure that no butterfly is assigned too many packets to sort.

  lemma919

Proof: We begin by examining a single packet in a single M-input butterfly that is to sort n-packets. To show that a packet lies in an interval of size at most tex2html_wrap_inline4037 it is sufficient to show that both following and preceding it in the sorted order at least tex2html_wrap_inline4039 of the next tex2html_wrap_inline4041 packets are candidates.

First we consider the packets that follow in the sorted order. The number of candidates in a sequence of tex2html_wrap_inline4043 packets has a binomial distribution. For tex2html_wrap_inline4045 , tex2html_wrap_inline4047 , tex2html_wrap_inline4049 , tex2html_wrap_inline4051 , and tex2html_wrap_inline4053 , we have tex2html_wrap_inline4055 . For any tex2html_wrap_inline4057 we can make the right-hand side smaller than tex2html_wrap_inline4059 by choosing tex2html_wrap_inline4061 large enough.

The calculation for the packets that precede in the sorted order are identical. The probability that fewer tex2html_wrap_inline4063 of the preceding tex2html_wrap_inline4065 packets are candidates is at most tex2html_wrap_inline4067 . Thus, the probability that an individual packet lies in an interval of size greater than tex2html_wrap_inline4069 is at most tex2html_wrap_inline4071 .

To bound the probability that any interval in the butterfly is too large we sum the probabilities that each individual packet lies in an interval that is too large. Since there are at most tex2html_wrap_inline4073 packets, this sum is at most tex2html_wrap_inline4075 .

To bound the probability that any butterfly is not tex2html_wrap_inline4077 -split, we sum the probabilities that each individual butterfly is not. Over the course of the algorithm, the algorithm is invoked on at most tex2html_wrap_inline4079 butterflies. The sum of the probabilities is at most tex2html_wrap_inline4081 . For any constant tex2html_wrap_inline4083 , we can make this sum at most tex2html_wrap_inline4085 by making tex2html_wrap_inline4087 large enough.


to .667emto .667em

The remainder of the analysis is conditioned on the event that every subbutterfly is well-partitioned and tex2html_wrap_inline4089 -split, which occurs with high probability. Two technical points bear mentioning. First, Lemma 8.1 requires that the number of inputs to every subbutterfly be at least tex2html_wrap_inline4091 , where tex2html_wrap_inline4093 is some constant. Since the recursion terminates when the number of inputs is tex2html_wrap_inline4095 , N must be large enough that tex2html_wrap_inline4099 . Second, both Lemmas 8.1 and 8.2 hold independent of the number of packets to be sorted by each subbutterfly. Thus, as the following lemmas show, we can adjust the load on the butterfly in order to ensure that each M-input subbutterfly receives at most M packets to sort.

lemma942

Proof: At each level of recursion the number of inputs drops from M to at most tex2html_wrap_inline4109 , until the number of inputs reaches tex2html_wrap_inline4111 .


to .667emto .667em

  lemma946

Proof: Since the ratio of packets to inputs is tex2html_wrap_inline4123 at the top level of the recursion, and increases by at most a constant factor at each of tex2html_wrap_inline4125 levels, it is possible to choose tex2html_wrap_inline4127 such that at the bottom level it will be at most one.


to .667emto .667em



next up previous
Next: 8.4 Bounding the congestion Up: 8 Sorting on butterflies Previous: 8.2 Analysis



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