Low Expansion Packings and Embeddings of Hypercubes into Star Graphs.
AbstractWe discuss the problem of packing hypercubes into an n-dimensional star graph S(n), which consists of embedding a disjoint union of hypercubes U into S(n) with load one. Hypercubes in U have from $\lfloor n/2 \rfloor$ to $(n+1)\cdot \left\lfloor {\log_2\,n} \right\rfloor -2^{\left\lfloor {\log_2n} \right \rfloor +1}+2$ dimensions, i.e., they can be as large as any hypercube which can be embedded with dilation at most four into S(n). We show that U can be embedded into S(n) with optimal expansion, which contrasts with the growing expansion ratios of previously known techniques.We employ several performance metrics to show that, with our techniques, a star graph can efficiently execute heterogeneous workloads containing hypercube, mesh, and star graph algorithms. The characterization of our packings includes some important metrics which have not been addressed by previous research (namely, average dilation, average congestion, and congestion). Our packings consistently produce small average congestion and average dilation, which indicates that the induced communication slowdown is also small. We consider several combinations of node mapping functions and routing algorithms in S(n), and obtain their corresponding performance metrics using either mathematical analysis or computer simulation.
Introduction
The star graph [1] was proposed as an attractive interconnection
network for parallel processing, featuring smaller degree
and diameter than a hypercube [2] of comparable size.
However, the earlier introduction of hypercube networks,
along with their interesting characteristics, has given to such
networks considerable popularity. A number of hypercube-
configured parallel computers was built in recent years [2],
and many hypercube-compatible algorithms have been proposed
[3]. Despite the fact that some parallel algorithms
have also been specifically devised for the star graph (e.g.,
sorting [4], FFT [5]), we believe that the repertory of star
graphs algorithms can be significantly increased via hyper-cube
embeddings.
Research on embedding hypercubes into star graphs was
initiated by Nigam, Sahni, and Krishnamurthy [6]. The interesting
techniques introduced in [6] reveal a major challenge
for embedding hypercubes into star graphs. Namely,
topological differences between the two networks (e.g., degree
and minimum cycle length) make it difficult to obtain an
This research is supported in part by Conselho Nacional de Desenvolvimento
under the grant
No. 200392/92-1.
embedding that simultaneously achieves small dilation and
expansion (see Sec. 2 for definitions).
In this paper, we present a hypercube embedding technique
that reduces the trade-off between dilation and expansion
significantly. Our technique is referred to as packing, and
consists of embedding a disjoint union
k=kmin
containing p k many copies of each k-dimensional hypercube
Q(k), kmin  k  kmax , into an n-dimensional star graph
S(n). Our packings lie in two categories, namely fixed-sized
packings (i.e., packings in which all of the embedded hypercubes
have the same size, or kmin = kmax ) and multiple-sized
packings (i.e., packings in which the embedded hypercubes
are of various sizes, or kmin 6= kmax ). All of our packings
have load 1, i.e. any node in S(n) is image to at most one
node of U .
Packings support multiple tasks, providing a means by
which a star graph can be efficiently used to run hypercube
algorithms. Moreover, they can also be used as a foundation
for implementing node allocation and task migration
strategies, making it possible to handle such issues as load
balancing and fault tolerance (see [7] for more on this topic).
The main contribution of our packing techniques relates to
expansion, which can be either: 1) a slow growing function of
n, in the case of fixed-sized packings (an expansion between
1 and 2.46 is obtained for n  10), or 2) optimal (i.e., 1),
in the case of multiple-sized packings. These small expansion
ratios need not sacrifice dilation (e.g., Sec. 4 presents
packing techniques that produce dilation 3 for all embedded
hypercubes).
We also consider in this paper an extension of our packing
techniques, which we refer to as variable-dilation embed-
dings. Variable-dilation embeddings address the necessity of
accommodating tasks requiring hypercubes that are larger
than each of the copies made available through our basic
packing techniques. Larger hypercubes Q(k + ') are formed
from 2 ' packed copies of lower-dimensional hypercubes Q(k),
which assures that small expansion is still achieved. While
these Q(k)'s are embedded with a fixed dilation d base = 3,
larger dilation (e.g., 4, 6, and so on) is produced along higher
dimension links of Q(k + '). However, the average dilation
of such an embedding (d avr ) is not much larger than d base
(e.g., d avr ranges from 3 to 4.25 for k
This paper is organized as follows. Sec. 2 introduces basic
definitions and the terminology used in the paper. Sec. 3
presents some background information. Sec. 4 presents our
techniques for packing hypercubes into the star graph. Sec. 5
discusses variable-dilation embeddings. A comparison with
related work is given in Sec. 6 and Sec. 7 concludes the paper.
Definitions and Terminology
Let G(k) be a k-dimensional graph with hierarchical struc-
ture, such that G(k + 1) is obtained recursively from c(k)
many copies of G(k). Several graphs belonging to the class
of Cayley graphs have this recursive decomposition property,
such as the hypercube and the star graph [1, 2]. The links
connecting the c(k) copies of G(k) that exist within G(k+1)
are referred to as dimension links.
We denote the set of nodes and the set of links of G(k)
by V (G(k)) and E(G(k)), respectively. An embedding of
into H(n), which we denote by F : G(k) 7! H(n),
is a mapping of V (G(k)) into V (H(n)) and of E(G(k)) into
paths of H(n). G(k) and H(n) are respectively referred to
as the guest and the host of F [3]. The node image of F
is F (G(k))g. The load of F is the
maximum number of nodes of G(k) that are mapped to any
single node of H(n), and is denoted by The dilation
of F is
where dist H (a; b) is the distance in H(n) between two vertices
a and b of H(n). The expansion of F is X(F
k=kmin
disjoint union of p k
many copies of each G(k), with k ranging from kmin to kmax .
For each k, we index G j (k) with 0  . The set of nodes
in U is V
g. Accordingly, the set of links in U is
g. A packing of U
into H(n), which we denote by P : U 7! H(n), is a mapping
of V (U) into V (H(n)) and of E(U) into paths of H(n). P
is a fixed-sized packing if Otherwise, P is
a multiple-sized packing. The node image of P is P
(U)g. The load of P is the maximum number
of nodes in U that are mapped to any single node of H(n),
and is denoted by (P ). We denote the embedding of G j (k)
into H(n), in the context of P , by P j;k . The dilation of P j;k
is (k))g.
The base dilation of P is d base (P
g. P is referred to as a template packing
if . The
expansion of P , denoted by X(P ), is:
(1)
Embeddings of guest graphs whose dimensionality exceeds
can often be built from a packing P , and are defined as
follows. For
the number of G(k)'s needed
to hierarchically compose one G(k '). We denote
the disjoint union of G(k)'s that compose G
dilation embedding of G which we denote
is a mapping of V
into V (H(n)) and of E(G into paths of H(n),
constrained by a packing P : U 7! H(n), such that
Equivalently, W can be
thought of as applying a transformation to P as follows. Let
be the disjoint union produced
from U , when c(k hierarchically compose
packing produced
when W is constructed within P . In general, one can apply
a series of similar transformations to P , producing a packing
P general that will hold several variable-dilation embed-
dings. Previously given definitions also apply to packings
holding variable-dilation embeddings. In particular, note
that
0;k+' .
Some terms that more precisely characterize a variable-
dilation embedding are defined as follows. The dilation
of W along the i th dimension of G
denotes the set of dimension i links of
'g. The dilation vector of W is d(W
)]. The average dilation of W is:
d avr (W
(2)
A major advantage of variable-dilation embeddings, as opposed
to conventional embedding methods, is that the dilation
can be made significantly smaller on the average. Since
many algorithms use a limited number of dimensions at any
given step of their execution, a smaller communication slow-down
is obtained.
3 Background
3.1 The hypercube
A k-dimensional hypercube graph
E(Q(k))g contains 2 k nodes, which are labeled with binary
strings of length k. A node connected
to k distinct nodes, respectively labeled with strings
denotes the binary
negation of bit q i [2]. The link connecting OE and OE i is
a dimension i link of Q(k).
3.2 The star graph
An n-dimensional star graph
contains n! nodes which are labeled with the n! possible
permutations of n distinct symbols. In this paper, we use
the integers f1, ng to label the nodes of S(n).
A node  is connected to (n \Gamma 1) distinct
nodes, respectively labeled with permutations
label is obtained
by exchanging the first and the i th symbol of 's la-
bel) [1]. The link connecting  and  i is a dimension i link
of S(n).
3.3 Embedding of a mesh into S(n)
The packing and embedding techniques presented in this
paper use a two-step mapping algorithm, in which hypercubes
are initially packed into an (n \Gamma 1)-dimensional mesh
of size 2 \Theta 3 \Theta
embedded
into S(n) with load 1, dilation 3, and expansion 1 via Algorithm
1 below, which is inspired by a mapping algorithm
proposed by Ranka et al. [8]. An interesting property of
Alg. 1 is presented later in this paper (see Lemma 2).
Algorithm 1 (Mapping
mesh to star (int n, m[
f int i, h, temp;
for
for
for
the width of M(n \Gamma 1) along its
th dimension. We label the nodes of M(n \Gamma 1) with an
Alg.
(S(n)). The pseudocode represents
node labels with vectors, such that
4 Template Packings
4.1 Preliminaries
In this section, we discuss template packings of hypercubes
into S(n), which have load 1 and base dilation 3. We present
both fixed-sized and multiple-sized packings, which respectively
embed into S(n): 1) a disjoint union
for some fixed k 2 [bn=2c; n \Gamma 1], and 2) a disjoint union
is the largest hypercube
considered in this paper as far as template packings into S(n)
are concerned. In addition, because fixed-sized packings of
Q(bn=2c) and multiple-sized packings produce expansion 1,
we do not discuss the cases k ! bn=2c, which can be obtained
by tearing larger hypercubes after they are packed into S(n).
From the viewpoint of how hypercubes are packed into
classify our packings as symmetric or asym-
metric. Symmetric packings are those in which all dimension
a links of E(U) are mapped to dimension b links of
Accordingly,
asymmetric packings are those in which two dimension a
links (u; v) and (x; y) of E(U) may be mapped to links of
different dimensions b and c in E(M(n \Gamma 1)), unless (u; v)
and (x; y) belong to the same Q j (k) 2 U .
The dimension mapping rules that characterize a given
packing technique are not preserved when M(n \Gamma 1) is ultimately
embedded into S(n) via Alg. 1. In both symmetric
and asymmetric template packings, a dimension a link of
E(U) is mapped either to a dimension b link of E(S(n)), or
to a path b ! c ! b in S(n), where b, c can be any of the dimensions
of S(n). Although the symmetry (or asymmetry)
of a particular technique used to pack Q(k) into S(n) can
not be distinguished unless for the intermediary step where
the hypercubes are packed into M(n \Gamma 1), we use throughout
the paper the terms symmetric (or asymmetric) packings of
into S(n).
Our discussion about fixed-sized packings considers both
the symmetric and the asymmetric cases. However, our
multiple-sized packings are all asymmetric. Symmetric packings
provide a very regular arrangement of the copies of Q(k)
in M(n \Gamma 1), which is particularly useful for constructing
variable-dilation embeddings. However, they do not achieve
as small expansion as asymmetric packings do. In order to
combine the desired features of low expansion and support to
variable-dilation embeddings, we build our asymmetric packings
as an extension of their symmetric counterparts. Hence,
an asymmetric packing will often be the method of choice to
pack hypercubes into the star graph.
Intuitively, one should expect smaller expansion when: 1)
smaller hypercubes are packed into S(n), and 2) asymmetric
techniques are used.
4.2 Embedding of Q(k) into
Our packing techniques take advantage of the regular structure
of to achieve low expansion ratios. A preliminary
result on which our techniques are based is given
below:
can be embedded into load
dilation 1, if k  n \Gamma 1.
To prove the lemma, we present an algorithm which
produces the desired embedding (see Alg. 2). Assume that
the argument origin[ ] taken by Alg. 2 is set to all 0's. In
addition, let use dim[ ] be a binary string with exactly k 1's.
The image of the embedding contains the mesh nodes that
match the pattern m
ae origin[i]; if use
use
This image is available if k  since: 1) the width
of along any of its dimensions is at least 2, which
guarantees that the range selected for the coordinates of the
image nodes exists, and 2) at least k different mesh coordinates
are needed, which is satisfied when k  n \Gamma 1. To
show that Alg. 2 embeds Q(k) into M(n \Gamma 1) with load 1 and
dilation 1, it suffices to note that: 1) each node q 2 V (Q(k))
has a unique image node in V (M(n \Gamma 1)), and 2) if q, q i are
adjacent in Q(k), then their respective image nodes m, m i
are adjacent in M(n \Gamma 1). 2
Algorithm 2 (Embedding Q(k) onto M(n \Gamma 1)):
cube to mesh (int k, n, q[ use dim[ ])
for
use dim[i] \Theta q[i cube
if (use dim[i] ==
Alg. 2 uses only a limited range of the coordinates available
in M(n \Gamma 1), producing expansion n!=2 k . With multiple calls
to Alg. 2 and a proper selection of arguments origin[ ] and
use dim[ ], one can embed multiple image-disjoint copies of
1). This is exactly the basis for the packing
techniques we present in this section. Naturally, our ultimate
goal is to pack hypercubes into S(n), which can be
accomplished with Alg. 1.
4.3 Symmetric fixed-sized packings
In this subsection, we present a symmetric fixed-sized packing
which embeds the disjoint union U
into S(n) with load 1 and base dilation 3, for some k 2
To make our discussion simpler, we define
Theorem 1 For 1  t  b(n + 1)=2c, there is a symmetric
fixed-sized packing P f which embeds the disjoint union
dilation d base (P f
and (4)
bn=2c
Noting that the width of M(n\Gamma1) along its i th dimension
is we refer to i as an even-sized dimension if s i
is even, and as an odd-sized dimension if s i is odd.
has bn=2c even-sized dimensions and b(n \Gamma 1)=2c odd-sized
dimensions. We partition slices of width 1
along the first t \Gamma 1 odd-sized dimensions of M(n \Gamma 1), and
slices of width 2 along all other dimensions of M(n \Gamma 1).
This partitioning process produces p f
sional induced submeshes, which we denote by M j (n \Gamma
1)[m
n\Gammat . Each of
these submeshes contain all of the nodes of M(n \Gamma 1) whose
labels match the pattern m
even
is an invariant such that
is an invariant such
that 0  b
Due to the partitioning process, these submeshes are dis-
joint. Each induced submesh has width 2 along its (n \Gamma t)
dimensions, and can host a copy of Q(n \Gamma t) with load 1,
dilation 1, which follows from Lemma 1. To embed a copy of
into an induced submesh M j (n \Gamma 1)[m
one can use Alg. 2 with arguments:
use
ae 0; for even i
otherwise, and (6)
use
use
We denote the number of usable slices produced by partitioning
its i th dimension by  i , where:
The number of induced submeshes produced by the partitioning
process equals the number of packed hypercubes,
and is given by:
Alg. 2 produces the same dimension assignment for each
copy of Q(n \Gamma t), which characterizes a symmetric packing.
If we now embed using Alg. 1, a packing
with load 1 and base dilation 3 results. To complete the
proof, we note that the expansion of the packing can be
obtained by direct application of Eq. 1. 2
An algorithm that symmetrically packs Q(n \Gamma t) into S(n)
is given in [9], and is not presented here due to space constraints

The partitioning technique described in the proof of
Theor. 1 discards 1=(i along each odd-sized
which poses a restriction on the expansion
ratios that can be achieved. Each unused slice has width
along dimension i, and is in fact an (n \Gamma 2)-dimensional sub-mesh
of size 2 \Theta 3 \Theta n. For even i ?
we denote the submesh discarded along dimension i by
is the induced sub-mesh
formed by all nodes
such that m
Discarded submeshes occur along the last b(n
odd-sized dimensions i of M(n \Gamma 1). For
(or there are no discarded submeshes. This
characterizes a symmetric, fixed-sized packing of Q(bn=2c)
into S(n) with load 1, base dilation 3, and expansion 1.
Because discarded submeshes are (n \Gamma 2)-dimensional, they
cannot be used to pack additional hypercubes Q(k) with the
desired load and base dilation when
from Lemma 1. However, we can use such submeshes if
which produces an asymmetric fixed-sized
packing.
4.4 Asymmetric fixed-sized packings
In this subsection, we present an asymmetric fixed-sized
packing P f+ which embeds the disjoint union U
into S(n) with load 1 and base dilation 3, for
some As in the symmetric case, we
define
Theorem 2 For 2  t  b(n \Gamma 1)=2c, there is an asymmetric
fixed-sized packing P f+ which embeds the disjoint union
base dilation d base (P f+
bn=2c
h=th
first pack p f
as described in
the proof of Theor. 1, which produces discarded submeshes
2. Because the
dimensions of interest are odd-sized (i.e., i is even), we define
i=2. For each h such that t  h  b(n \Gamma 1)=2c, let
n\Gammat h2hi denote the number of Q(n \Gamma t)'s that can be packed
into
slices of width 1 along the first t \Gamma 2 odd-sized
dimensions of M(n \Gamma 1)[m slices of width
along all other dimensions of M(n \Gamma 1)[m
partitioning method produces p f
n\Gammat h2hi (n \Gamma t)-dimensional
submeshes of width at least 2 along any dimension, where:
Partitioning shown above allows us
to pack p f
n\Gammat h2hi additional copies of Q(n \Gamma t) into M(n \Gamma 1),
with load 1 and dilation 1. Note, however, that the first
do not have any of their links mapped onto
dimension links of M(n \Gamma 1). The p f
n\Gammat h2hi extra
copies, however, use dimension links of M(n \Gamma 1).
Hence, the resulting packing is asymmetric.
We can use the technique just described for all induced
submeshes
This produces a total of p f+
h=t
n\Gammat h2hi packed copies of Q(n \Gamma t). The theorem
4.5 Results on fixed-sized packings
Fig. 1 depicts expansion ratios produced by our fixed-sized
packing techniques. Note that by reducing the size of the
hypercubes being packed, one achieves smaller expansion.
For example, the expansion of our
symmetric packings drops from 2.46 to 1.13 as we vary t from
to 4. Asymmetry also proves to be an efficient technique
to achieve denser packings, resulting in an expansion of at
most 1.20 among all asymmetric packings shown in Fig. 1.
4.6 Multiple-sized packings
In this subsection, we present an asymmetric multiple-
sized packing P m which embeds the disjoint union
into S(n) with load 1, base dilation
3, and expansion 1. P m supports hypercube tasks with
different node allocation requirements, and guarantees 100%
utilization of S(n), 8n.
Dimensionality of the star graph (n)1.52.5
Expansion
of
the
packing
Q(n-4), asym.
Q(n-4), sym.
Q(n-3), asym.
Q(n-3), sym.
Q(n-2), asym.
Q(n-2), sym.
Q(n-1), sym.

Figure

1: Expansion ratios of packings of Q(n \Gamma t) into S(n)
The technique used to construct P m can be summarized as
follows. Initially, we pack Q(n \Gamma 1)'s symmetrically into S(n)
as described in the proof of Theor. 1. Using the submeshes
that are left after this step, we pack Q(n \Gamma 2)'s asymmet-
rically. This process continues with asymmetric packings of
using in each step
nodes of M(n \Gamma 1) that were not used in the previous steps.
The resulting packing uses all of the nodes in S(n).
Theorem 3 There is an asymmetric multiple-sized packing
which embeds the disjoint union U
dilation
d base
nk
Y
Omitted due to space constraints. The interested
reader is referred to [9] for a proof.
5 Variable-Dilation Embeddings
5.1 Basic techniques
In this section, we describe how a ')-dimensional hypercube
can be embedded with variable dilation into S(n),
As described in Sec. 2, a variable-dilation embedding
produced by grouping
copies of Q(k), embedded into S(n) by a packing
packing
S(n) with dilation d(P 0
at least one variable-dilation embedding are not template
packings. As we shall see, the average dilation d aver (P 0
of the embedding of can often be made
close to d base (P ).
One particularity of our variable-dilation embedding techniques
is that the copies of Q(k) needed to compose one
must have
been packed symmetrically by P into S(n). Formally, P
should map all dimension a links of E(U 0;k+' ) to dimension
b links of E(M(n \Gamma 1)), where 1  a  k and 1  b ! n. This
requirement can be met by any template packing P containing
a sufficiently large group of symmetrically packed Q(k)'s.
Hence, even in the case of asymmetric template packings, one
will often find one or more usable groups of packed Q(k)'s.
To keep our discussion short, we derive the main results of
this section for the case In Subsec. 5.4, we give examples
of variable-dilation embeddings that are formed from
Q(k)'s for which k ! n \Gamma 1.
Our variable-dilation embeddings of Q(n \Gamma 1+') into S(n)
are supported by two template packings that were presented
in Sec. 4, namely: 1) the fixed-sized packing of Q(n \Gamma 1)
into S(n), which we denote by P f , and 2) the multiple-sized
packing of Q(k) into S(n) (bn=2c  k  which we
denote by P m . Both P f and P m contain
symmetrically
packed which limits the number of
additional hypercube dimensions that can be produced by a
variable-dilation embedding of Q(n
log 2
(15)010011110010110124
1000 1010
Hypercube
dimensions:

Figure

2: A variable-dilation embedding of Q(4) into M(3)
Fig. 2 depicts an example of the technique we will be describing
in this section. Q(4) is embedded into M(3) by
grouping two packed Q(3)'s, which produces dilation 2, average
dilation 1.25, and dilation vector [1; If we now
embed M(3) into S(4) using Alg. 1, the corresponding embedding
of Q(4) into S(4) has dilation 4, average dilation
3.25, and dilation vector [3; 3; 3; 4], which is justified by the
following lemma:
be a pair of nodes
separated by ' links along the i th dimension of M(n \Gamma 1),
Alg. 1 produces an embedding
of S(n), such that the images of ! and ! i;'
are connected by a path containing at most ' links.
Omitted due to space constraints. The interested
reader is referred to [9] for a proof.
Theorem 4 Let f(x;
h, and ' be integers such that n  4, 2  h  blog 2 nc, and
n). There is a variable-dilation
embedding W of Q(n \Gamma 1+') into S(n), with load (W
dilation along dimension i of Q(n \Gamma 1+') d i (W ), average dilation
d avr (W ), dilation d(W ), and expansion X(W ), where:
d avr (W
and X(W
Omitted due to space constraints. The interested
reader is referred to [9] for a proof.
We now present an algorithm that produces a variable-
dilation embedding of Q(n Such an embedding
has the properties specified in Theor. 4.
Algorithm 3 (Embedding of Q(n
var embed cube (int n,
f int i, m[ ], last;
for
for
last
for
mesh to star (n, m[ ], p[ ]); g
int f(int x, y)
5.2 Advanced techniques
Let Q(k a ) denote the largest hypercube that can be embedded
into S(n) via Alg. 3. Due to the restrictions 2  h
n) in Theor. 4, we
have 2.
Accordingly, let Q(k b ) denote the largest hypercube that can
be embedded with load 1 and variable dilation into S(n), considering
only the availability of Q(n \Gamma 1)'s that are produced
by either of the packings P f or P m . From Eq. 15, we have
\Delta\Pi . Finally, let Q(kmax ) denote
the largest hypercube that can be embedded with load
We note that an embedding
of Q(kmax ) into S(n) can be obtained trivially by a
random one-to-one mapping algorithm. Such an approach,
however, may result in a dilation of up to \Phi(S(n)), where
1)=2c is the diameter of S(n).

Table

lists values of k a , k b , and kmax for star graphs of
practical size. Note that Alg. 3 matches the upper limit k b ,
for 4  n  6, and produces a maximum dimensionality k a
that is one less than the upper limit k b , for 7  n  10.

Table

1: Upper limits k a , k b and kmax
Reference [9] discusses how a load 1, variable-dilation embedding
of Q(k b ) into S(n) can be constructed from packed
Dilation vectors for embeddings
of Q(k b ) into S(n), for 7  n  10, are given in Table 2.
We note that, for 6  n  10, the maximum hypercube
dimensionality achieved by our variable-dilation embeddings
is still one less than kmax . To produce an additional hyper-cube
dimension via a variable-dilation embedding, one needs
more Q(n\Gamma1)'s than those produced by packings P f and P m .
Additional Q(n \Gamma 1)'s can be obtained by grouping smaller
hypercubes that are available in P m , which is discussed in [9].
The details of how these Q(n \Gamma 1)'s can compose Q(kmax ),
however, are beyond the scope of this paper.
5.3 Average dilation
Fig. 3 depicts the average dilation d avr produced by the
variable-dilation embeddings presented in Subsecs. 5.1 and
5.2. We consider the cases 3  k  20 and 4  n  10, which
correspond respectively to hypercubes of sizes 8 through
1,048,576, and star graphs of sizes 24 through 3,628,800.
As explained in Sec. 2, parallel algorithms that employ a
limited amount of hypercube dimensions at any given step
may benefit from the smaller average dilation produced by
variable-dilation embeddings. Moreover, improved performance
can be obtained by reassigning hypercube dimensions
prior to the embedding into S(n), which is possible due to
the symmetry properties of Q(k). Namely, one can relabel
the hypercube nodes, such that in the final embedding into
S(n) the most frequently used hypercube dimensions have
the smallest dilation.
5.4 Compound var.-dilation embeddings
The variable-dilation embeddings discussed earlier in this
section are formed by grouping packed Q(n \Gamma 1)'s. In what
follows, we give an example that illustrates how this concept
can also be adopted in the case of smaller packed hyper-
cubes. Moreover, we use the example to demonstrate the
Dimensionality of the embedded hypercube (k)3.24.2
Average
dilation

Figure

3: Average dilation of embeddings of Q(k) into S(n)
inherent flexibility that results from combining our multiple-
sized packing and variable-dilation embedding techniques.
We consider the template multiple-sized packing P m presented
in Subsec. 4.6. Although P m is an asymmetric pack-
ing, it uses a partitioning technique that produces groups of
symmetrically packed Q(k)'s [9]. These groups of Q(k)'s can
form variable-dilation embeddings into S(n).

Table

3 lists a few among the many possible transformations
that can be produced by applying a series of variable-
dilation embeddings to P m , for the case tables
can be constructed for other values of n). Quantities marked
with an   in Table 3 are obtained via variable-dilation embedding
techniques. Details of how such quantities are computed
are given in [9]. Note that all multiple-sized packings
shown in Table 3 have expansion 1.
Packing
# of Q(4)'s
# of Q(5)'s 144 12   -
# of Q(6)'s 264 72   6
# of Q(7)'s 144 132   36
# of Q(8)'s - 72   66
# of Q(9)'s - 36
# of Q(10)'s -
# of Q(11)'s -
# of Q(12)'s -
# of Q(13)'s -
# of Q(14)'s -

Table

3: Some mult.-sized packings of hypercubes into S(8)
6 Comparison with related work
Research on embedding hypercubes into star graphs was pioneered
by Nigam, Sahni, and Krishnamurthy, who proposed
dilation 2, 3, and 4 embeddings of Q(k) into S(n) [6]. Table
4 lists the largest Q(k)'s that can be embedded into
Embedding (W ) Dilation vector (d(W dilation (d avr (W

Table

2: Variable-dilation embeddings of Q(k b ) into S(n), 7
with dilation 4, using the techniques of Nigam et al., for
were chosen because
they produce the smallest expansion ratios among the
embeddings presented in [6]. Also listed in Table 4 are the
corresponding average dilation and expansion produced by
our techniques.
Our variable-dilation embedding techniques are an interesting
alternative to the dilation 4 embeddings of [6]. For
4  n  10, we achieve an average dilation ranging from
3.25 to 3.95. Our techniques produce dilation 4, for the cases
dilation 6, for the cases 8  n  10. Note
also that, for the cases 8  n  10, dilation 6 is produced
only along: 1) dimension 13 links of Q(13), 2) dimension 15
and 16 links of Q(16), and links
of Q(19).
Dilation Aver. dil. Expan. Expan.
Embedding (Nigam (this (Nigam (this
et al.) paper) et al.) paper)

Table

4: Comparison with related work
If we consider solely the embedding listed at the left of
each row in Table 4, then clearly the expansion ratios resulting
from the techniques of [6] and the techniques presented in
this paper should be equal. However, as discussed in Secs. 4
and 5, our multiple-sized packings achieve 100% utilization
of S(n), meaning that any node of the star graph not used
in the embeddings listed in Table 4 can still be used to embed
some other hypercube. This certainly allows an efficient
use of the star graph, and hence we compute our expansion
ratios within the context of a packing (see Eq. 1). From this
viewpoint, our optimal expansion (i.e., 1) is always smaller
than that achieved in [6].
7 Conclusion
This paper presented novel techniques for packing hypercubes
into star graphs, which achieve small expansion and
dilation. In particular, the expansion of our multiple-sized
packings is optimal. Variable-dilation embeddings resulting
from connecting packed Q(n \Gamma 1)'s into S(n) demonstrated
the possibility of embedding large hypercubes into the star
graph, with corresponding small expansion while maintaining
a small dilation on the average. Our techniques can
provide the required support for node allocation and task
migration strategies in applications where S(n) must handle
a workload of parallel algorithms originally devised for the
hypercube.



--R

"The Star Graph: An Attractive Alternative to the n-Cube,"
"Hypercube Supercomput- ers,"
Introduction to Parallel Algorithms and Architectures: Arrays
"An Efficient Sorting Algorithm for the Star Graph Interconnection Network,"
"A Parallel Algorithm for Computing Fourier Transforms on the Star Graph,"
"Embed- ding Hamiltonians and Hypercubes in Star Interconnection Networks,"
"Task Allocation in the Star Graph,"
"Embedding Meshes on the Star Graph,"
Spaceand Time-Efficient Packings and Embeddings of Hypercubes into Star Graphs
--TR
routing;graph embeddings;star graphs;interconnection networks;hypercubes