next up previous
Next: 11 Remarks Up: Randomized Routing and Sorting Previous: 9 Sorting on shuffle-exchange

10 Sorting on multidimensional arrays


In this section we describe an algorithm for sorting kN packets on an N-node k-dimensional array with maximum side length M in tex2html_wrap_inline4497 steps. The algorithm closely follows the algorithm of Section 8 for sorting on the butterfly network. For the sake of brevity, we omit many of the details.


Sketch of proof: The algorithm is essentially the same as the algorithm for sorting on the butterfly. For simplicity, we assume that tex2html_wrap_inline4509 .

As before, there is a recursive subroutine for sorting tex2html_wrap_inline4511 packets. We describe the action of the subroutine on a tex2html_wrap_inline4513 -dimensional subcube. (A tex2html_wrap_inline4515 -dimensional subcube of an array is a subgraph of the array consisting of tex2html_wrap_inline4517 nodes whose labels tex2html_wrap_inline4519 share the same value in some set of tex2html_wrap_inline4521 coordinates. For example, given a set tex2html_wrap_inline4523 coordinates and a set tex2html_wrap_inline4525 of values, there is a subcube consisting of those nodes tex2html_wrap_inline4527 such that tex2html_wrap_inline4529 for tex2html_wrap_inline4531 .) The array is lightly loaded by the factor of tex2html_wrap_inline4533 to ensure that at each level of the recursion, the number of packets entering any tex2html_wrap_inline4535 -dimensional subcube is at most tex2html_wrap_inline4537 .

The first step is to choose a set of splitters. A set of tex2html_wrap_inline4539 packets are randomly chosen to be splitter candidates and then sorted by comparing every candidate with every other candidate, which can be done in tex2html_wrap_inline4541 steps. Next, every tex2html_wrap_inline4543 th candidate is selected to be a splitter.

The subcube routes packets on a leveled logical routing network as described in Section 6. The splitters are placed on the plateaus of the logical network, tex2html_wrap_inline4545 of them on plateau i. Since there are only tex2html_wrap_inline4549 splitters, only the first tex2html_wrap_inline4551 plateaus get any, where tex2html_wrap_inline4553 is some fixed constant less than one. On plateau 1, the jth splitter is assigned to all of the nodes labeled tex2html_wrap_inline4559 , where tex2html_wrap_inline4561 for tex2html_wrap_inline4563 . A packet routes across dimension 1 edges on plateau 1 until until it reaches a splitter that is larger than itself. It then routes across dimension 2 edges to plateau 2. Because dimension 1 edges do not appear in any later plateaus, each of the M intervals is routed to a disjoint k-1 dimensional subgraph of the logical network. On each of these subgraphs, M splitters are positioned on plateau 2, and so on.

The subroutine calls itself recursively on subcubes with tex2html_wrap_inline4583 dimensions. The recursion terminates when the number of packets entering a subcube is less than kM, in which case they are sorted sequentially in tex2html_wrap_inline4587 time. There are tex2html_wrap_inline4589 levels to the recursion. As before, we can estimate the time required by the algorithm by assuming that the time spent on a tex2html_wrap_inline4591 -dimensional subcube is equal to the expectation, tex2html_wrap_inline4593 . The time is given by the recurrence


which has solution tex2html_wrap_inline4595 . To rigorously bound the time we would have to argue that delay does accumulate across the levels of the recursion.

The algorithm for sorting kN packets calls the subroutine once. First, tex2html_wrap_inline4599 packets are randomly chosen to be candidates and sorted using the subroutine. Next, every tex2html_wrap_inline4601 th candidate is selected to be a splitter. The splitters partition the packets into intervals of size tex2html_wrap_inline4603 . Since tex2html_wrap_inline4605 , each interval has at most tex2html_wrap_inline4607 packets. Since the 1-dimensional subcubes can each sort kM packets in tex2html_wrap_inline4613 steps using bubblesort, and tex2html_wrap_inline4615 , Columnsort can be applied to sort all of the packets in tex2html_wrap_inline4617 steps.

to .667emto .667em

next up previous
Next: 11 Remarks Up: Randomized Routing and Sorting Previous: 9 Sorting on shuffle-exchange

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