PERMUTATION ROUTING VIA CAYLEY GRAPHS WITH AN EXAMPLE FOR BUS INTERCONNECTION NETWORKS

GENE COOPERMAN AND LARRY FINKELSTEIN

Abstract. Cayley graphs have been used extensively to design interconnection networks and provide a natural setting for studying point-to-point routing [1, 2, 3, 5, 6, 7, 12]. The extension of these techniques to the more important problem of permutation routing on interconnection networks presents fundamental problems. This is due to the potentially explosive growth in both the size of the graph and the number of generating permutations, referred to as one-step permutation routes, used to define the underlying graph. This paper describes a technique for moderating that growth so that the techniques in [8] can be applied for finding optimal permutation routes. In a particularly striking example, a bus interconnection architecture involving 1.0 × 10^{17} permutations (nodes of the Cayley graph) is reduced to a computation on a graph with only 3,950 nodes. Further, it is shown how many of the 58,624 generators (directed edges labelled by one-step permutation routes) at each node of the graph may be eliminated as locally redundant.

1. Introduction

There has been an extensive literature on the use of Cayley graphs to design interconnection networks [1, 2, 5, 6, 7, 12]. Cayley graphs have been used extensively to study point-to-point routing, and they have been particularly attractive for the degree-diameter problem [3, 5, 7]. Nevertheless, other patterns of routing, such as broadcast, permutation routing, and general many-to-one routing are at least as important for parallel computing. This paper describes the use of Cayley graphs to study permutation routing. There are also other approaches to permutation routing [1, 11] that concentrate more on heuristics and an overall framework.

A Cayley graph G is a directed labelled graph associated with a group, G, and generating set S. The nodes of G are elements of G and the edges are labelled by generators in S. Two nodes, g and h are connected by a directed edge, (g, h), and the edge is labelled by s ∈ S, if h = gs. In the case where S = S^{−1}, whenever g is connected to h by a directed edge labelled by s, h is simultaneously connected to g by a directed edge labelled by s^{−1}, and so G may be viewed as undirected. This is typically the case and will be assumed throughout this paper. Cayley graphs

1991 Mathematics Subject Classification. Primary 05C25, 68M10; Secondary 20-04, 68R10, 90B12.

Key words and phrases. permutation routing, Cayley graph, bus interconnection network. The authors were partially supported by NSF Grant CCR-9204469.

have the property that they are vertex-symmetric. This means that for any two nodes, there is a graph isomorphism of the graph into itself that maps the first node into the second. In the case of Cayley graphs, this graph isomorphism also preserves the labels of the edges. In fact, this property can be easily established by simply embedding G into Aut(G) through the left regular action so that the resulting image is transitive on the nodes of the graph and preserves edge labels.

A spanning tree T for G rooted at the identity e allows one to find shortest paths between arbitrary nodes. Given elements g and h of G, one uses T to find a shortest path from e to g^{−1}h. If w is the word in the edge labels along this path, then h = gw. Since G is vertex-symmetric, it follows that w also defines a shortest path in G from g to h as well. An important interpretation is that w is a minimal length word in the generating set S that represents the group element g^{−1}h. In particular, this allows for the solution of the minimal word problem for G relative to the generating set S.

In [8], an efficient method of encoding Cayley graphs was developed, using standard techniques from computational group theory [13]. This method required log_{2} 3 bits of storage per node of the graph to store a data structure for a spanning tree for the Cayley graph. The spanning tree was derived essentially through a method of breadth-first search. During computation of the data structure, log_{2} 5 bits per node were temporarily required. Since this is approximately 2 bits, it was called the 2-bit method. Furthermore, it was shown how to use this data structure to find shortest paths in G between any two nodes. Applications of this method are presented in [9].

We will now show how to apply these ideas to permutation routing in an arbitrary interconnection graph I. We first define a one-step permutation route π to be a permutation of the nodes Ω of I with the property that either π(x) is connected to x for each node x or π(x) = x. The idea is that any one-step permutation route can be executed in parallel without any conflicts. A k-step permutation route is one that is obtained from a sequence of at most k one-step permutation routes. If I is connected, then a transposition of the nodes of any edge is a one-step permutation route. This leads to the following observation.

Theorem 1. If I is connected, then the set S of one-step permutation routes generates Sym(Ω) and any permutation of the nodes of Ω is a \binom{|Ω|}{2} permutation route.

The basic problem we want to consider is given an arbitrary permutation π of I, express π as a sequence of k one-step permutation routes where k is minimal. This can then be viewed as finding a word of minimal length in the set S of one-step permutations that represents π. It is precisely this problem which must be solved.

2. Bus Interconnection Networks

We now apply the previous ideas to bus interconnection networks. From this, it will be clear how to generalize to other examples. Specifically, let C be a set of chips and let B be a set of bus lines. Let Ω = C ∪ B and let I be a graph on Ω such that (a, b) is an edge of I if and only if a ∈ C, b ∈ B, and chip a is connected to bus line b.

The following model corresponds to the case in which each chip has only one register. In each clock cycle, for each chip a, either the data in a is interchanged with the data on some unique bus line b or else the data on chip a remains fixed. Section 5 discusses how to generalizes this to multiple registers per chip. Essentially, one identifies C with the set of chip registers, rather than chips. The simpler model is analyzed in detail in section 3 to illustrate the concepts.

Let S be the set of all involutions g ∈ Sym(Ω) with the property that g is a product of disjoint transpositions of the form (a b) where a ∈ C and b ∈ B. The elements of S are precisely the one-step permutation routes of I. Let M = max(|C|, |B|) and let m = min(|C|, |B|). Then, the size of |S| is bounded above by (M + 1)^{m}.

This is a restricted version of an interconnection network in which distinct data is both read and written to the bus in one clock cycle, thus insuring that the communication is indeed a permutation. This may be the physical situation if the setup time to connect chips and bus lines dominates the actual transfer time. The bus line and/or the chip can hold dummy data, in which case the important transfer of data is in one direction only.

3. Experimental Model

For simplicity in computational experiments, we also assume that each chip is connected to each bus line. This allows us to find experimental data dependent only on parameters |C| and |B|. It is easy to see that if S is the set of one-step permutation routes for I defined in the previous section, then S generates G = Sym(C ∪ B). The technique can be easily applied to other interconnection patterns, and details of that generalization are contained in section 5.

The goal is to express each permutation route as a shortest possible sequence of one-step permutation routes. In the language of group theory, for each permutation g of Ω that setwise stabilizes B, we must find a shortest word in S that represents g. Given the Cayley graph G for G with generating set S, this is equivalent to finding a shortest path in G from the identity node 1 to the node g.

Rather than work with the Cayley graph G, we will work with a reduced labelled multigraph, defined below. This smaller graph greatly reduces the necessary computation. The reduced graph is constructed through two reductions. First, we construct a Cayley coset graph G_{H} from G, and second, we construct a reduced labelled multigraph G̃ from G_{H}.

The first reduction is obtained by noting that we are concerned only with permutations of data on the chips, and not with permutations of whatever data may initially be on the bus lines. This can be best expressed by right cosets Hg ∈ G/H, where g ∈ G and H ≅ Sym(B) is the subgroup of G that fixes C pointwise. Formally, the Cayley coset graph of G/H with generating set S is a directed labelled multigraph G_{H}, with nodes labelled by G/H. Two nodes Hg_{1} and Hg_{2} are connected by an edge with label s if Hg_{1}s = Hg_{2}. Thus, the image of g′ ∈ Hg on C depends only on g and not on the choice of g′. So, it suffices to find a shortest word w in S representing an element of Hg. Many routing problems can be formulated in terms of Cayley coset graphs (also referred to as group action graph in [2]). In general, Cayley coset graphs are not vertex-symmetric.

The second reduction is obtained from the symmetries of the chosen bus interconnection architecture. Recall that a group automorphism is a permutation σ of G such that σ(gh) = σ(g)σ(h) and σ(g^{−1}) = (σ(g))^{−1} for all g, h ∈ G. For G corresponding to the bus interconnection architecture I, we define a symmetry to be an automorphism, σ, of G such that σ(H) = H and σ(S) = S.

This definition insures that the symmetries of G act as graph automorphisms of the Cayley graph G (with generating set S), which map paths of minimal length in G to other paths of minimal length. If (g_{1}, g_{2}) is a directed edge of G with label s ∈ S, then σ maps (g_{1}, g_{2}) to the directed edge (σ(g_{1}), σ(g_{2})) with label σ(s) ∈ S. This and the invertibility of σ imply that σ preserves the paths of minimal length in G. Furthermore, as indicated above, we are actually interested in shortest words which represent a fixed coset Hg. But the symmetries of G also act as graph automorphisms of G_{H} in the same sense as for G. To see this, note that if (Hg_{1}, Hg_{2}) is an edge of G_{H} with edge label s ∈ S then σ(H) = H and σ(s) ∈ S implies that (σ(Hg_{1}), σ(Hg_{2})) = (Hσ(g_{1}), Hσ(g_{2})) is an edge of G_{H} with label σ(s). Thus σ preserves paths of minimal length in G_{H} as well.

Conjugation provides a natural means of constructing such symmetries. Define the conjugate of g by u to be g^{u} = u^{−1}gu, and extend the definition to sets H^{U} = {h^{u}: h ∈ H, u ∈ U}. The mapping σ_{u}: g ↦ g^{u} is an automorphism of G, and is known in group theory as an inner automorphism. In the case of our bus interconnection network, we let U ≅ Sym(C) × Sym(B), and choose as the set of symmetries {σ_{u}: u ∈ U}. We often refer to a symmetry σ_{u} simply as u. Note that H^{U} = H and S^{U} = S for this choice of U, and so the definition of symmetry is satisfied. Hence, conjugation by U preserves shortest words. From group theory, it is known that if |C ∪ B| ≠ 6, then the set U contains all possible symmetries.

With this motivation, we now introduce the reduced labelled multigraph G̃, derived from G, in which nodes of G̃ are identified with subsets [Hx] = (Hx)^{U} = Hx^{U} ⊆ G for x ∈ G. Thus, {[Hx]}_{x∈G} partitions G into disjoint subsets. In the language of group theory, [Hx] can also be viewed as the union of the cosets in the orbit of Hx under the conjugation action of U on G/H.

It remains to define the edges of G̃. For purposes of computation, the edge set of G̃ is defined to be only a subset of the naturally induced edge set from G_{H}. One would normally expect that for [Hx] ≠ [Hy], there is an edge between [Hx] and [Hy] if there is an edge in G between x′ and y′ for x′ ∈ [Hx] and y′ ∈ [Hy]. For purposes of computation, it is more convenient to first choose an arbitrary transversal T ⊆ G consisting of exactly one point from each distinct set [Hx] for x ∈ G. Denote by \overline{x} the unique element in [Hx]∩T. We define G̃ to have a directed edge between [Hx] and [Hy] labelled by s ∈ S if and only if [H\overline{x}s] = [Hy].

We next show that the edges in the two views of G̃ really do correspond. There is an edge in the unlabelled graph if and only if there is at least one directed, labelled edge in the directed, labelled multigraph. The backward implication is easy. For the forward implication, suppose there is an edge in the unlabelled graph. So, there are x′ ∈ [H\overline{x}], y′ ∈ [Hy] and s′ ∈ S such that x′s′ = y′. Then there is a u ∈ U, such that x′^{u} ∈ H\overline{x} and so x′^{u}s′^{u} = y′^{u} ∈ [Hy]. Note also that when S is closed under inverses, if there is a directed edge from [Hx] to [Hy], then there is at least one directed edge from [Hy] to [Hx].

Suppose now that g is an arbitrary element of G, and we want to construct a shortest word on S whose action on C is the same as the action of g on C. This is the same problem as finding a shortest sequence, g_{1}, …, g_{k} of elements of S such that g(g_{1} ⋯ g_{k})^{−1} ∈ H, or equivalently, that g ∈ Hg_{1} ⋯ g_{k}. The next result shows how to construct such a sequence from any path of length k from [H] to [Hg].

Theorem 2. Let g be an arbitrary element of G. There exists a path in G̃ from [H] to [Hg] of length k if and only if there exist g′_{1}, …, g′_{k} ∈ S such that g ∈ Hg′_{1} ⋯ g′_{k}.

Proof. Suppose first that there exists a path of length k from [H] to [Hg] in G̃. Then there exists g_{1}, …, g_{k} ∈ S and w_{0}, …, w_{k} ∈ T (hence w_{i} = \overline{w_{i}}) such that w_{0} = 1, w_{k} = \overline{g} and [Hw_{i−1}g_{i}] = [Hw_{i}]. Note that [Hw_{i−1}g_{i}] = [Hw_{i}] implies that there are h_{i} ∈ H and u_{i} ∈ U such that w_{i} = h_{i}w_{i−1}^{u_{i}}g_{i}^{u_{i}}. Iterating this, shows

that w_{k} = hg_{1}^{u′_{1}} ⋯ g_{k}^{u′_{k}} for h = h_{k}(h_{k−1}(h_{k−2} ⋯)^{u_{k−2}})^{u_{k−1}} ∈ H and u′_{i} = u_{i} ⋯ u_{k}. Letting g = h_{k+1}w_{k}^{u_{k+1}} and setting g′_{i} = g_{i}^{u′_{i}u_{k+1}} ∈ S proves the assertion in the forward direction.

Conversely, suppose g ∈ Hg′_{1} ⋯ g′_{k}. Define u′_{i} and h′_{i} so that w_{i} = h′_{i}(g′_{1} ⋯ g′_{i})^{u′_{i}} satisfies \overline{w_{i}} = w_{i}. Let w_{0} = 1. Note that w_{k} = \overline{g} and [Hw_{i}(g′_{i+1})^{u′_{i+1}}] = [Hw_{i+1}]. This then gives the required path of length k from [H] to [Hg] in G.

3.1. Encoding of nodes of reduced graph. Next, we consider how to produce a 1-1 mapping of the nodes of G into a “small” set of integers. The encoding serves as an almost perfect hash function of G, in that the number of integers is not much larger than the number the number of nodes. The results in [8] show how to use such a 1-1 mapping to store a spanning tree using storage of only log_{2}(3) bits times the size of the “small” integer set. This is especially important for the larger graphs. For example, given 16 chips and 4 bus lines (|C| = 16, |B| = 4), the number of cosets, Hg, to explore is |G/H| = (16 + 4)!/4! ≈ 1.0 × 10^{17}. Yet the reduced graph has only 3,950 nodes. The following technique allows a unique encoding of those 3,950 nodes within the range [0, 5,822].

In order to construct a unique encoding of [Hg], we require two auxiliary functions, r(x, y) and s(x, y). We denote by r(x, y) the number of partitions of x indistinguishable elements, such that the largest set within the partition is of size no larger than y. So, for example, r(5, 2) = 3 since the set of 5 elements can be partitioned into subsets of size (2, 2, 1), (2, 1, 1, 1) and (1, 1, 1, 1, 1) for which no subset has more than 2 elements. In general,

r(x, y) = ∑_{i=1}^{y} r(x − i, min(i, y, x − i)).

Also, s(x, y) is the number of ways in which x+y indistinguishable elements can be partitioned, where the x + y elements are first split into two distinguished subsets, the first of size at most x and the second of size at least y. So, for example, s(1, 2) = 5 and the partitions are of the form ((1), (2)), ((1), (1, 1)), ((), (3)), ((), (2, 1)) and ((), (1, 1, 1)). In general,

s(x, y) = r(x, x)r(y, y) + s(x − 1, y + 1)

for x > 0 and s(0, y) = r(y, y).

We now give a unique characterization of a node of the reduced graph in terms of a sequence of invariants. The proof that this is a unique characterization is easy, but is not included here. In the restriction of g to the union of the cycles that fix B, let c_{i} be the length of the i-th such cycle. Let b_{i} be the number of points x ∈ C such that x^{g^{j}} ∈ C for all j < i and x^{g^{i}} ∉ C. Then [Hg] is uniquely characterized by (a) the sequence c_{1}, …, c_{|C|} and (b) the sequence b_{1}, …, b_{|B|}. Alternatively, one can say that the c_{i} and b_{i} are invariants of any permutation h ∈ [Hg] and the collection of invariants identifies a unique [Hg].

We can now describe the encoding of the equivalence class [Hg] in terms of its invariants, c_{i} and b_{i} for fixed |C|. Let b = ∑_{i} b_{i} and let c = ∑_{i} c_{i}. Note that b + c = |C|. Then the encoding is given by

Encoding of [Hg]: s(b − 1, c + 1) + t((b_{1}, …, b_{|B|}))r(c, c) + t((c_{1}, …, c_{|C|})).

(We set s(b − 1, c + 1) = 0 when b = 0.) Here, for fixed b, if ∑_{j=1}^{i} x_{i} = b, then t((x_{1}, …, x_{i})) is a unique encoding of the partition (x_{1}, …, x_{i}) among all partitions of b elements. The value of the function “t” is defined to be independent of the order of its arguments. We re-order the arguments so that x_{1} ≥ ⋯ ≥ x_{i} and define

t((x_{1}, …, x_{i})) = t((x_{2}, …, x_{i})) + r(∑_{j=1}^{i} x_{i}, x_{1} − 1)

for i > 0 and t(()) = 0 for i = 0. Note that t((x_{1}, …, x_{i})) ≤ r(∑_{j=1}^{i} x_{i}, max_{1≤j≤i} x_{i}) ≤

r(∑_{j=1}^{i} x_{i}, ∑_{j=1}^{i} x_{i}).

3.2. Optimization: Use of Reduced Generating Sets. Since the reduced labelled multigraph (defined in section 3) is a multigraph, an edge between nodes in the reduced graph may have multiple labels. One can recognize, a priori, that certain edge labels in the reduced graph are redundant. This allows us to moderate the exponential explosion in the number of generators as |C| and |B| increase. This is critical, since |S| = ∑_{i=1}^{|B|} \binom{|C|}{i}\binom{|B|}{i}i!. To take an extreme example, for 16 chips and 4 bus lines, |S| = 58,624. Yet for x = 1 ∈ G, there are only 4 non-redundant generators, g, (each uniquely characterized by the number of transpositions in g) yielding distinct equivalence classes [Hxg]. All other elements of xS are conjugate to one of the 12 under U.

In order to discover these redundant edge labels, consider the the node [Hx], \overline{x} = x, with outgoing edge labelled by g_{0}. One must eliminate those g ∈ S such that g ≠ g_{0} and [H\overline{x}g] = [H\overline{x}g_{0}]. Equivalently, for a given x ∈ G and g_{0} ∈ S, one must find those g ∈ S with g ≠ g_{0} such that h(\overline{x}g)^{u} = \overline{x}g_{0} for some h ∈ H and u ∈ U.

The following three heuristics are used to remove certain g ∈ S from consideration. The statement assumes some arbitrary ordering of the points C ∪ B, so that “smallest” and “<” are well-defined. The correctness of these heuristics follows from the results of section 4, which define a total ordering on S. So, if g, g_{0} ∈ S, g_{0} < g, and the heuristic can establish that [H\overline{x}g] = [H\overline{x}g_{0}], then g is eliminated. Let C′ = {a: a^{x^{i}} ∈ C ∀i} ⊆ C.

(1) First, g can be removed if there is a point a ∈ C′ moved by g that is not the smallest in the cycle of \overline{x} containing a and for which g does not move the point that is first in that cycle. (There is a conjugation in U that “rotates” the points of the cycle until a is first in the cycle, while leaving \overline{x} unchanged.)

(2) Second, g can be removed when there is a point of C′ moved by g such that it is smallest in a cycle of \overline{x} if there is an earlier cycle of points of the same length as the current cycle, and g does does not move the point that

#  # bus lines
chips 1 2 3 4 5 6 7 8
4 6/12 3/17 3/19 3/20
0.05 0.2 0.7 0.7
5 7/19 4/28 3/33 3/35 3/36
0.1 0.3 1.0 3.1 5.6
6 9/30 5/47 4/57 3/62 3/64 3/65
0.2 0.6 3.5 11.8 30 56
7 10/45 6/73 4/92 3/102 3/107 3/109 3/110
0.9 1.2 6.7 37 120 293 699
8 12/67 6/114 5/147 4/167 3/177 3/182 3/184 3/185
0.4  2.2  17  104  460 1432 4259 13351

is smallest in that cycle. (In that case, there is a conjugation in U that interchanges the two cycles, and so leaves \overline{x} unchanged.)

(3) Third, g can be removed if there are points a, a′ ∈ B such that a′ < a, (a′)\overline{x} = a′, (a′)^{g} = a′, a\overline{x} = a and a^{g} ≠ a. (The transposition (a a′) ∈ U leaves \overline{x} unchanged.)

3.3. Experimental Results. The following table describes the maximum length permutation route, the CPU time, and the number of nodes in the reduced graph for various values of the number of chips and the number of buses. The computation was carried out under AKCL 1.615 (Common LISP). A SPARCstation-2 was used. For each tested combination of number of chips and bus lines, three numbers are reported. The first is the number of steps for an optimal permutation route for the worst case permutation (the diameter of the reduced labelled multigraph). The second is the number of nodes required to store the internal data structure. For large numbers of nodes, this will usually dominate the space requirements. Only two bits are required to store each node [8]. So, storage requirements are minimal for the examples shown. The third number is the number of seconds of CPU time to generate the data structure. From this data structure, an optimal permutation route can be computed in less than a millisecond for any desired permutation.

For 12 chips with 4 bus lines and 16 chips with 4 bus lines, two special tests were made. The results were a diameter of 5 with 919 nodes (5/919) and a diameter of 6 with 3,950 nodes (6/3950), respectively. The computation was carried out on a SPARCserver 670 in 43 minutes and 10 hours of CPU time, respectively.

The range of encodings is larger than, but usually close to the actual number of states. The range of encodings is independent of the number of bus lines. For example, at the beginning of section 3.1, we saw an example of 16 chips and 4 bus lines, in which the range [0, 5,822] was needed for 167 nodes. If the 2-bit encoding scheme is used, space must be allotted for the total range of encodings. Where the actual number of states used is much smaller, one can use hashing techniques to require space proportional to the actual number of states. Naturally, the constant of proportionality would be much higher than two bits.

Note that the length of the optimal permutation route for the worst case is always at least three. The reason for this is easy to see, since a one-step permutation route is required to move the data from the chips to the bus lines. A second one-step permutation route moves the data from the bus lines to other chips. A third onestep route then places some of the data back on the bus lines. In practice, one is only interested in permutation routes that leave all data on the chip, and none on the bus lines. Hence, for permutation routes of interest, with sufficiently many bus lines, there is always a permutation route of length at most two.

4. Pruning Locally Redundant Generators

Although G̃ was previously defined as the reduced labelled multigraph, we also identify it with the labels the nodes of the graph, which are the equivalence classes

[Hx] for x ∈ G. For [Hx] ∈ G̃ and y ∈ S, we define [Hx]y = [H(\overline{x}y)] as in section 3. The next theorem characterizes a set of representatives, \overline{x}S_{x}, for the distinct

equivalence classes [Hx]S ⊆ G̃. Equivalently, this characterizes representatives for the nearest neighbors in the reduced labelled multigraph.

Theorem 3. Let ρ be a total ordering on S. Let H ⊆ U, H^{U} = H and S^{U} = S. For x ∈ G, let S_{x} = \{g ∈ S: g ≤_{ρ} h ∀h ∈ (\overline{x}^{−1}(\overline{x}g)^{U}H) ∩ S\}. Then [Hx]S = [Hx]S_{x} and |[Hx]S| = |S_{x}| — i.e. the number of nearest neighbors of [Hx] in G̃ is |S_{x}|.

Proof. [Hx]S = [Hx]S_{x} follows from the definitions of [Hx] and S_{x}, along with the properties of H. Let g, h ∈ S. Then

[Hx]h = [Hx]g ⇔ H(\overline{x}h)^{U} = H(\overline{x}g)^{U} ⇔ (\overline{x}h) ∈ H(\overline{x}g)^{U}
⇔ h ∈ \overline{x}^{−1}H(\overline{x}g)^{U} = \overline{x}^{−1}(\overline{x}g)^{U}H.

Thus if g, h ∈ S_{x} and [Hx]h = [Hx]g then g and h must both be lexically least, and so g = h.

Define the centralizer of x ∈ G in U to be Cent_{U}(x) = {g ∈ U: x^{g} = x}.

Corollary 4. Let ρ be a total ordering on S. Let H ⊆ U, H^{U} = H and S^{U} = S. For x ∈ G, let S′_{x} = \{g ∈ S: g ≤_{ρ} h ∀h ∈ (g^{Cent_{U} (\overline{x})}H) ∩ S\}. Then [Hx]S = [Hx]S′_{x} and |[Hx]S| ≤ |S′_{x}| for [Hx]S ⊆ G̃.

Proof. Note that since Cent_{U}(\overline{x}) ⊆ U, g^{Cent_{U} (\overline{x})}H = \overline{x}^{−1}(\overline{x}g)^{Cent_{U} (\overline{x})}H ⊆ \overline{x}^{−1}(\overline{x}g)^{U}H. So, S_{x} ⊆ S′_{x} ⊆ S.

The advantage of S′_{x} over S_{x} is that, given Cent_{U}(\overline{x}), there are well-known techniques for enumerating the elements of S′_{x} [4]. For U equal to Sym(C) × Sym(B), Sym(Ω) and many other special cases of interest, computing Cent_{U}(\overline{x}) is also efficient [10].

The heuristics of section 3.2 follow from the special case for S′_{x}. The order, ρ, is a variation of lexical ordering.

g >_{ρ} h iff i^{g} = i^{h} ∀i < j, j^{g} ≠ j^{h}, and either j^{h} = j or j^{g} < j^{h} ≠ j

The use of a lexical ordering means that one can generate all elements of S′_{x} in lexical order and if a permutation g ∈ X′_{x} satisfies i^{g} ≤ i^{h} or i^{h} = i ∀i ≤ j, ∀h ∈ g^{Cent_{U} (\overline{x})}H, then the subtree \{h ∈ g^{Cent_{U} (\overline{x})}H: j^{g} ≠ j^{h}, i^{g} = i^{h} ∀i < j\} ∩ S′_{x} = ∅ and so the entire subtree can be eliminated.

Where it is feasible to compute S_{x} or where S′_{x} is not too much larger than S_{x}, the entire computation of a data structure for the spanning tree of the reduced labelled multigraph has a nice complexity characterization. Since |S_{x}| ≤ |G̃, the algorithm examines at most |G̃|^{2} directed edges in its breadth-first search. Note that enumeration of S′_{x} in lexical order costs O(|S′_{x}|n) for n = |Ω|, since on the current branch, either the entire subtree will be eliminated, or a new element of S′_{x} will be found before the necessity of backtracking. Computing the product xg and its encoding cost O(n). So, the total cost of the algorithm is O(|G̃|^{2}(n + E) + |G̃|(A + Rn)), where A is the cost of computing the automorphism group and R is the cost of enumerating the elements of S_{x} of S′_{x}. Further, for the bus interconnection networks of section 3, O(|G̃|^{2}n) is the dominant term.

5. Generalization to Other Models

The previous section was described under the assumption that each chip had only one register (and hence hold only one piece of data at a time). Naturally, most implementations will allow multiple registers or memory cells on a single chip. Hence, shortest paths derived from previous calculations serve only as an upper bound on the shortest length path when multiple registers are allowed.

The model can be extended to k registers per chip, by including k copies of each chip. Every generator must also be replicated to include variation in which each bus is connected to an arbitrary register. Finally, the subgroup H must be extended to include generating elements that transpose arbitrary registers from the same chip.

The previous section was described in a situation with full connections between chips and registers. If there are fewer connections, in general, one will need to choose a subgroup of U = Sym(C) × Sym(B) that preserves the architecture under conjugation. Thus, the subgroup U can be viewed as the automorphism group of a labelled graph, where each node of the graph is labelled either by C or by B. Usually ease of manufacturing dictates a uniform architecture, and so most realworld example are still likely to have a fairly large automorphism group.

Finally, a few remarks about generalizations to other models besides bus interconnection networks is worthwhile. There is a common difficulty in translating routes in physical networks to permutation routes. Suppose one has nodes A, B and C with edges between A and B, and between B and C. One would like to add a transposition between A and B as a one-step permutation route. Similarly, one would like to add a transposition between B and C. Finally, one would like to to move data from A to B while other data is moved from B to C, in parallel, in a single one-step permutation route. However, a naive product of transpositions would send data from A to C, which cannot be done in one step. The solution is to split each node into two nodes corresponding to two registers/ports: a sending port and a receiving port. Thus, one can move data from A to B in parallel with distinct data moving from B to C, and this can be expressed as a permutation.

6. Conclusion

It has been demonstrated how to find permutation routes for larger data structures than would be possible by a direct approach. The solution involves precomputing a special data structure in seconds. One can then derive shortest permutation routes achieving an arbitrary permutation from the pre-computed data structure. Finding that solution is a computation that can be carried out in less than a millisecond (and much shorter times are possible with hardware support).

In implementations, one would pre-compute the data structure for a given hardware architecture off-line. The required space is very small, although the CPU time for the pre-computation can be appreciable. Since the pre-computation is done once only, long CPU times may be acceptable. Specific permutation routes would either be computed at compile-time for an individual application, or else it would be be computed as part of a set-up routine for a route determined at run-time. In the latter case, one would expect the computed permutation route to be used many times to justify the overhead of computing such a route at run-time.

7. Acknowledgements

The authors wish to thank Richard Draper, Chuck Fiduccia and Bryant York for stimulating discussions.

References

1. F. Annexstein and M. Baumslag, “A Unified Framework for Off-line Permutation Routing in Parallel Networks”, Math. Syst. Theory 23 (1991), pp. 233–252.

2. F. Annexstein, M. Baumslag, and A.L. Rosenberg, “Group Action Graphs and Parallel Architectures”, SIAM J. Computing 19 (1990), pp. 544–569.

3. J-C. Bermond, C. Delome, and J-J. Quisquater, “Strategies for interconnection networks: Some methods from graph theory”, Journal of Parallel and Distributed Computing 3 (1986), pp. 433-449.

4. G. Butler, Fundamental Algorithms for Permutation Groups, Lecture notes in computer science 559, Springer-Verlag, New York (1991).

5. L. Campbell, G.E. Carlsson, and M.J. Dinneen, “Small Diameter Symmetric Networks from Linear Groups”, IEEE Transactions on Computers 41, no. 2, (1992), pp. 218–220.

6. G.E. Carlson, J.E. Cruthirds, H.B. Sexton, and C.G. Wright, “Interconnection networks based on a generalization of cube-connected cycles”, I.E.E.E. Trans. Comp. C-34 (1985), pp. 769– 777.

7. D.V Chudnovsky, G.V. Chudnovsky and M.M. Denneau, “Regular Graphs with Small Diameter as Models for Interconnection Networks”, I.E.E.E. Trans. Comp. (1988), pp. 232–239.

8. G. Cooperman and L. Finkelstein, “New Methods for Using Cayley Graphs in Interconnection Networks”, Discrete Applied Mathematics 37/38 (special issue on Interconnection Networks) (1992), pp. 95–118.

9. G. Cooperman, L. Finkelstein and N. Sarawagi, “Applications of Cayley Graphs”, Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (AAECC-8, Tokyo, 1990) Springer-Verlag Lecture Notes in Computer Science 508, S. Sakata (ed.) (1991), pp. 367–378.

10. E. Luks, Permutation Groups and Polynomial-Time Computation, Proceedings of DIMACS Workshop on Groups and Computation, DIMACS-AMS 11, L. Finkelstein and W.M. Kantor (eds.), AMS, Providence, RI, (1993), pp. 139–175.

11. M. Ramras, “Routing Permutations on a Graph”, Networks 23, no. 4, (1993), pp. 391–398.

12. S.T. Schibell and R.M. Stafford, “Processor Interconnection Networks from Cayley Graphs”, Disc. Appl. Math. 40 (1992), pp. 333–362.

13. C.C. Sims, “Computation with Permutation Groups”, in Proc. Second Symposium on Symbolic and Algebraic Manipulation, S.R. Petrick (ed.), ACM, New York (1971).

College of Computer Science, Northeastern University, Boston, MA 02115 E-mail address: gene@ccs.neu.edu

College of Computer Science, Northeastern University, Boston, MA 02115 E-mail address: laf@ccs.neu.edu