next up previous
Next: 2 Routing on a Up: Fast Algorithms for Bit-Serial Previous: Fast Algorithms for Bit-Serial

1 Introduction

Substantial effort has been devoted to the study of store-and-forward packet routing algorithms for hypercubic networks. The fastest algorithms are randomized, and can solve any one-to-one packet routing problem on an N-node hypercube in tex2html_wrap_inline797 packet steps with high probability [3, 14, 18, 19, 22, 23, 24, 26, 27]. Of the deterministic algorithms [5, 9, 10], the fastest requires tex2html_wrap_inline799 packet steps [9]. One drawback to these algorithms, however, is that they all require tex2html_wrap_inline801 bit steps when implemented on real parallel machines such as the Connection Machine. The reason is that most parallel machines operate in a bit-serial or byte-serial fashion because of pin limitations on switches. Since packets always contain at least tex2html_wrap_inline803 bits of addressing information, a typical packet step really consists of tex2html_wrap_inline805 bit steps.

In general, fast bit-serial algorithms are harder to design than store-and-forward algorithms. This is particularly true on a hypercube since the head of a tex2html_wrap_inline807 -bit packet should be close to its destination before the tail of the packet leaves the origingif. Moreover, while the packet is spread out and moving through the network, it prevents up to tex2html_wrap_inline813 wires from being used by other packets. This phenomenon raises issues such as deadlock and livelock [11] that do not arise in the simpler store-and-forward model.

In this paper, we describe an asymptotically optimal randomized algorithm for packet routing on the hypercube. The algorithm solves any permutation routing problem for packets that are M bits long (not including addressing information) in tex2html_wrap_inline817 bit steps with high probability. Moreover, the algorithm requires each node of the hypercube to deal with only tex2html_wrap_inline819 new packets at each step. The algorithm works in either the wormhole [11] or cut-through [16] models of routing.

The algorithm also solves the problem of on-line circuit switching in an tex2html_wrap_inline821 -dilated hypercube, where a b-dilated hypercube is one in which each edge is replaced by a bundle of b edges. Previously, it was known that for any one-to-one routing problem, edge-disjoint paths could be established from the inputs to the outputs of a Benes network [6]. The Benes network can be embedded in a 4-dilated hypercube. However, the only on-line algorithms previously known for finding the paths in a Benes network or hypercube require tex2html_wrap_inline829 steps [8, 21]. Our algorithm finds a set of edge-disjoint paths on the tex2html_wrap_inline831 -dilated hypercube, on-line, in tex2html_wrap_inline833 bit steps.

The algorithm has three essential features: (1) it uses Valiant's paradigm of routing to random intermediate destinations, (2) it uses a new embedding of a tex2html_wrap_inline835 -dilated butterfly into the hypercube that is based on 1-error correcting codes, and (3) it implements a bit-serial version of Ranade's algorithm [18, 19, 23] that eliminates the ghost packets and the need for packets to carry tex2html_wrap_inline839 -bit ranks.

Most hypercube routing algorithms [15, 18, 19, 23, 26, 27] are oblivious. A deterministic oblivious routing algorithm is one in which the path taken by a packet through the network is a function of the origin and destination of the packet. Deterministic oblivious algorithms have previously been called oblivious algorithms [7]. A randomized oblivious algorithm is one in which each packet independently chooses its path according to a probability distribution which is a function of its origin and destination.

The algorithms described in this paper are not oblivious. In fact, we show that any randomized oblivious algorithm on any N-node network with maximum node degree d requires tex2html_wrap_inline845 bit steps, with high probability, for almost all permutations, where M is the packet size (not including addressing information). For routing tex2html_wrap_inline849 -bit messages on the hypercube, the lower bound is tex2html_wrap_inline851 bit steps. This result extends the Borodin-Hopcroft tex2html_wrap_inline853 -packet-step lower bound for deterministic oblivious algorithms [7] to randomized oblivious algorithms. The lower bound for deterministic oblivious algorithms has recently been improved to tex2html_wrap_inline855 by Kaklamanis, Krizanc, and Tsantilas [15], who also provide a deterministic oblivious store-and-forward algorithm for routing on the hypercube in tex2html_wrap_inline857 steps. Further work on bounds for oblivious routing and trade-offs between time and randomness can be found in [17].

Although our algorithm is the first route permutations on the hypercube in tex2html_wrap_inline859 bit steps with high probability, Leighton and Plaxton [20] have subsequently achieved a stronger result. They show how to sort on bounded-degree hypercubic networks in tex2html_wrap_inline861 steps (with the caveat that with very small probability the output will not be in sorted order). Their algorithm can be pipelined and hence can achieve permutation routing as well as many-to-one and one-to-many routing on hypercubic networks in tex2html_wrap_inline863 bit steps with high probability, using standard reductions of routing to sorting (plus a minor fix to take care of the case when the output is not sorted). Nonetheless, techniques used in this paper have recently been extended by Aiello and Leighton [1] to construct improved embeddings of trees and other structures in a hypercube and to design more efficient and robust algorithms for reconfiguring a hypercube around random or worst-case faults.

A natural open problem is to find a deterministic algorithm for routing (or sorting) in tex2html_wrap_inline865 bit steps on a hypercubic network. The only known bounded-degree networks capable of deterministic tex2html_wrap_inline867 -bit-step routing are the AKS sorting circuit [2] and the multibutterfly [4, 25]. However, these sorting and routing algorithms rely on expansion properties that the hypercube and its derivatives do not possess.

The remainder of the paper is divided into sections as follows. We start by describing two tex2html_wrap_inline869 bit-step algorithms for routing on a tex2html_wrap_inline871 -dilated butterfly in Section 2. The first is quite simple, but needs a switch to handle up to tex2html_wrap_inline873 new packets at once. The second is more efficient, allowing a switch to handle at most 2 new packets at each step. In Section 3, we show how to implement the algorithms on a hypercube by embedding the tex2html_wrap_inline877 -dilated butterfly in the hypercube. The lower bound for randomized oblivious routing is described in Section 4.

next up previous
Next: 2 Routing on a Up: Fast Algorithms for Bit-Serial Previous: Fast Algorithms for Bit-Serial

Bruce Maggs
Mon Jul 22 17:37:10 EDT 1996