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 . 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 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 butterflies in a two to one fashion with the representative strings. Suppose butterfly i is associated with string . We map a node in butterfly i to a shuffle-exchange node by shuffling the bits of with the bits of r's representation, and choosing the current bit to be . That is, node in butterfly i is mapped to shuffle-exchange node .

From a shuffle-exchange node we can recover the representative string 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 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 's image, or we exchange the current bit and shift twice to reach 's image.

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

to .667emto .667em

This technique can be extended to prove that for any constant , distinct -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 steps.

Proof: The N packets can be sorted using the Columnsort algorithm of [16]. Using Theorem 9.1, -node butterflies are embedded in the shuffle-exchange graph with constant load, congestion, and dilation, where . Each of the butterflies can sort packets in 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 time, with high probability.

to .667emto .667em

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