next up previous
Next: 10 Sorting on multidimensional Up: Randomized Routing and Sorting Previous: 8.6 Putting it all

9 Sorting on shuffle-exchange graphs


The butterfly sorting result from Section 8 does not directly extend to the shuffle-exchange graph because the shuffle-exchange graph does not have the nice recursive structure possessed by the butterfly. However we can use the following theorem to sort on the shuffle-exchange graph. A similar theorem was proven independently by Raghunathan and Saran [28].


Proof: We assume that tex2html_wrap_inline4401 . Thus each row of each butterfly can be represented by a k-bit string, and each node of the shuffle-exchange can be represented by a 2k-bit string.

To map tex2html_wrap_inline4407 butterflies to the shuffle-exchange graph, we use the following lemma [15, Lemma 1-1,].


For each of these subsets we pick the lexicographically minimum string to represent the subset. We associate the tex2html_wrap_inline4417 butterflies in a two to one fashion with the tex2html_wrap_inline4419 representative strings. Suppose butterfly i is associated with string tex2html_wrap_inline4423 . We map a node tex2html_wrap_inline4425 in butterfly i to a shuffle-exchange node by shuffling the bits of tex2html_wrap_inline4429 with the bits of r's representation, and choosing the current bit to be tex2html_wrap_inline4433 . That is, node tex2html_wrap_inline4435 in butterfly i is mapped to shuffle-exchange node tex2html_wrap_inline4439 .

From a shuffle-exchange node we can recover the representative string tex2html_wrap_inline4441 by picking out every other bit and shifting to the lexicographically minimum string. We find the row string by picking out the other bits and shifting by the same amount. The position in the row is clearly the number of shifts we used to get to tex2html_wrap_inline4443 and the row number.

To finish, we observe that each edge in any of the butterflies is mapped to a path of length at most three in the shuffle-exchange graph since we either shift twice to reach tex2html_wrap_inline4445 's image, or we exchange the current bit and shift twice to reach tex2html_wrap_inline4447 's image.

Thus we can embed tex2html_wrap_inline4449 ( tex2html_wrap_inline4451 )-node butterflies in an N-node shuffle-exchange with load 2, congestion tex2html_wrap_inline4455 , and dilation 3.

to .667emto .667em

This technique can be extended to prove that for any constant tex2html_wrap_inline4457 , tex2html_wrap_inline4459 distinct tex2html_wrap_inline4461 -node butterfly graphs can be embedded in an N-node shuffle-exchange with constant load, congestion, and dilation.

The following theorem shows that we can use Theorem 9.1 to sort on the shuffle-exhange graph in tex2html_wrap_inline4465 steps.


Proof: The N packets can be sorted using the Columnsort algorithm of [16]. Using Theorem 9.1, tex2html_wrap_inline4475 tex2html_wrap_inline4477 -node butterflies are embedded in the shuffle-exchange graph with constant load, congestion, and dilation, where tex2html_wrap_inline4479 . Each of the butterflies can sort tex2html_wrap_inline4481 packets in tex2html_wrap_inline4483 time using the butterfly sorting algorithm of Section 8. Columnsort sorts all N packets using a constant number of butterfly sorting steps and global permutation routing steps on the shuffle-exchange graph, each of which takes tex2html_wrap_inline4487 time, with high probability.

to .667emto .667em

next up previous
Next: 10 Sorting on multidimensional Up: Randomized Routing and Sorting Previous: 8.6 Putting it all

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