Embedding Complete Binary Trees Into Butterfly Networks.
The authors present embeddings of complete binary trees into butterfly networks with or without wrap-around connections. Let m be an even integer and q=m+(log m)-1. The authors show how to embed a 2/sup q+1/-1-node complete binary tree T(q) into a (m+1)2/sup m+1/-node wrap-around butterfly B/sub w/(m+1) with a dilation of 4, and how to embed T(q) into a (m+2)2/sup m+2/-node wrap-around butterfly B/sub w/(m+2) with an optimal dilation of 2. They also present an embedding of a wrap-around butterfly B/sub w/(m) into a (m+1)2/sup m/-node no-wrap-around butterfly B(m) with a dilation of 3. Using this embedding it is shown that T(q) can be embedded into a no-wrap butterfly B(m+1) (resp. B(m+2)) with a dilation of 8 (resp. 5).
Introduction
is an important issue in parallel processing [2, 3, 4, 5, 6, 7, 8, 10, 12]. In this paper we
study the relationship between a complete binary tree network T and a butterfly network
B and present embeddings of T into B: Let T (q) be a 2 q+1 \Gamma 1-node complete binary tree,
is an even integer. Let Bw (m) (resp. B(m)) be a m2 m -
node (resp. (m butterfly with (resp. without) wrap-around connections.
In [4], Bhatt et. al. showed how to embed T (q) into Bw (m+3) with a dilation of 4: While
this embedding has constant expansion, it uses a butterfly that has 8 times 1 as many
nodes as necessary. In this paper we first present two improved embeddings for T (q):
One embeds T (q) into Bw (m a dilation of 4: Another one embeds T (q) into
with an optimal dilation of 2: These two embeddings and the one presented
in [4], use the wrap-around connections of a butterfly heavily. We show that a butterfly
with wrap-around connections is (up to a constant factor) no more powerful than one
without wrap-around connections. More precisely, we show how to embed Bw (m) into a
no wrap-around butterfly network B(m) with a dilation of 3: Using this embedding we
are able to embed T (q) into B(m + 1) with a dilation of 8 and into B(m + 2) with a
dilation of 5: We next give definitions and notation used throughout this paper.
An embedding ! f; g ? of T into B is defined by a bijective mapping f from the
nodes of T to the nodes of B together with a mapping g that maps every edge
of T onto a path g(e) connecting f(v) and f(w). We refer to f as the assignment. Two
commonly and extensively studied cost measures of an embedding are the dilation and
the expansion [1, 4, 9, 11]. The dilation is defined as the maximum distance in B between
two adjacent nodes in T , and the expansion is defined as the ratio of the number of nodes
in B to the number of nodes in T:
Let T (q) be a complete binary tree having 2
The of T (q) are numbered 0; 1; . ; q: Let Bw (m) be a butterfly network
1 For simplicity we omit the lower order terms.
with wrap-around connections consisting of m levels, numbered 0;
level has 2 m nodes. Every node in Bw (m) is identified by the
where l indicates the level the node resides in, and fi 0 fi 1 . fi m\Gamma1 is the PWL (Posi-
tion Within Level) string, 1: The nodes in Bw (m)
are connected as follows. Node connected by a straight
edge to node ! (l and by a cross edge to node !
(l
l . fi that the nodes on level are connected
to nodes on level 0; representing the wrap-around edges. Let B(m) be a butterfly with
no wrap-around connections. The difference between B(m) and Bw (m) is that B(m)
contains an additional level, level m; and the wrap-around edges from level
level 0 in Bw (m) are replaced by edges from level m \Gamma 1 to level m:
In Section 2 we describe the embedding of tree T (q) into butterfly Bw (m + 1) which
has a dilation of 4: This embedding achieves the same dilation as the one in [4], but it
has an expansion of 2; versus an expansion of 8: We note that it is straight forward to
modify the embedding of [4] so that it uses a Bw (m+2) instead of a Bw (m+3): Section 3
contains the embedding of T (q) into Bw (m+2) which has a dilation of 2: With respect to
dilation this embedding is optimal since no embedding with O(1) expansion can achieve
a dilation less than 2 [4]. Section 4 shows how to embed Bw (m) into B(m) with a dilation
of 3 and how to use this result to obtain embeddings of T (q) into butterflies that have
no wrap-around connections.
The embeddings of Sections 2 and 3 use the same general approach as described in
[4]. More precisely, we also use the notion of a signatory 1 and a serial number in the
PWL strings. These concepts ensure that no two nodes of T (q) are assigned to the same
node of the butterfly. For our embeddings, as well as the embedding presented in [4], it is
crucial that at some point nodes on the same level of T (q) are assigned to different levels
in the butterfly. This is achieved in [4] and by the embedding described in Section 2 by
having subtrees grow upwards and then downwards in the butterfly for varying number
of levels. Doing so results in a dilation of 4: Our embedding described in Section 3 uses
a different technique to achieve assigning nodes on the same level of the tree to different
levels of the butterfly and thus achieves a dilation of 2:
Embedding T (q) into B w (m
In this section we describe how to embed T (q) into Bw (m a dilation of 4: The
embedding can be viewed as "fine-tuning" the strategy used in [4]. In the embedding
presented in [4], tree T (q) is embedded into three stages. The first stage
embeds levels 0 to log the second stage embeds levels log m to m+log
and the third stage embeds the remaining levels of T (q): In order to avoid collisions among
the embeddings of the three stages, each stage is simply embedded in a different copy
of Bw (m Our embedding uses bit positions in such a way that the
different stages of the embedding can share sub-butterfly networks as much as possible.
be the left half of Bw (m+1) and B 2 be the right half of Bw (m+1); as shown in

Figure

2: For clarity reasons, henceforth we refer to the nodes of T (q) as PEs (Processing
Elements) and to the nodes of the butterfly as nodes. We embed T (q) into Bw (m+ 1) in
four stages. Stage 1 embeds the first log m levels of T (q) with a dilation of 2 so that the
PEs on level log are assigned to nodes on level
uses only the odd-numbered levels in be the k th tree rooted at a PE on
level log embeds the
first with a dilation of 4: The PE on level 0 of T k (m) remains
assigned to the same node as in Stage 1. The PEs on level m=2 of T k (m) are assigned
to nodes on level m of B 2 . Stage 2 uses the odd-numbered levels in B 1 ; and in addition,
the even level and the even level m in B 2 . The last m=2 levels of T k (m); are
embedded in two stages. In Stage 3 we assign the next k levels of T k (m) with a dilation
of 4 so that the PEs on level m=2 are assigned to nodes on level
3 uses only the odd-numbered levels in B 2 . Stage 4 assigns the remaining
of T k (m) with a dilation of 2: Stage 4 uses even-numbered levels in both B 1 and B 2 . The
use of the levels is summarized in Table 1. Our embedding assigns no two PEs to the
same node of Bw (m + 1) and two adjacent PEs are at most distance 4 apart.
Levels used in B 1 Levels used in B 2
Stage 2 odd-numbered and level m
level
Stage 3 - odd-numbered
Stage 4 even-numbered even-numbered

Table

1: Use of levels by the four stages
For the description of the embedding given next assume that m is a power of two.
Our result holds, however, for any even m and we describe the necessary changes at the
end of Section 2.
A unary-straight branching is a branching from a node on level l to a node on level
using the straight edge. A unary-cross branching is a branching from a node on
level l to a node on level l using the cross edge. Finally, a binary branching is a
branching from a node on level l to two nodes on level l using the straight and the
cross edge.
Stage 1: Embedding the first log m levels of T (q)
Assign the root of T (q) to node ! We
then use a unary-straight and a binary branching to assign the two PEs on level 1 of
T (q) to the two nodes Note that the
binary branching generates a   in the PWL string and the unary-straight branching
keeps a 0 or a 1 as it is. Continuing in this fashion, we assign the 2 i PEs on level
of T (q) to nodes
Thus, the m=2 PEs on level log are assigned to nodes
In Figure 2; we show first few steps of the
embedding in this stage. It is easy to see that no two PEs are assigned to the same node,
i.e, there are no collisions.
occurrences of x when ff ? 0 and no occurrence of x when ff - 0:
3   denotes a wild card character indicating 0 and 1:
Stage 2: Embedding levels log m to m=2
As already defined, T k (m) is the k th tree rooted at a PE on level log
for assigns PEs on levels 1 through m=2 of
The PEs on levels 1 through are assigned to odd-numbered levels in B 1 .
The PEs on levels m=2 \Gamma 1 and m=2 are assigned to the even-numbered levels
are treated differently
in order to keep the dilation at 4 when embedding level m=2
The goal of Stage 2 is to assign the PEs on level m=2 of T k (m) to nodes ! m; (\Lambda0)
?. The '1' in position in the PWL strings is called the
signatory 1 [4]. Its purpose is to keep the nodes which have PEs of T k (m) assigned to be
different from the nodes that have PEs of T
the leftmost rightmost of a PWL string be
the head (resp. tail) of the PWL string. Consider a node that did get a PE assigned to it
in Stage 1. Its head consists of alternating 0's and 1's and its tail consists of alternating
's and 0's, with an additional 0 at the rightmost position. For the trees T k (m) with
positioned in the head of the PWL string (observe
that the position for the signatory 1 already contains a '1'). For the trees T k (m) with
positioned in the tail of the PWL strings (at the beginning
of Stage 2 this position contains a '0'). We first describe the embedding when the
signatory 1 is positioned in the head.
Stage 1 assigned the root of T k (m) to node !
Using two unary-straight branchings and a binary branching, we assign the two PEs on
level 1 of T k (m) to the two nodes results in a
dilation of 3 between the PEs of level 0 and level 1 of T k (m). For
we assign the 2 l PEs on level l of T k (m) to 2 l nodes on level 2l \Gamma 1 of B 1 using a unary-
cross and a binary branching. An exception occurs for the PEs on level
of T k (m) where, in order to keep the signatory 1; we use a unary-straight instead of a
4 In the string (  k the string   k   k .   k denotes the binary representation
of k: The   k in the r th position from left in   k   k .   k is the   k in position 2r of   k 0   k 0 .   k 0; for
2:
Level of T k (m) Nodes of Bw (m
l -
l -

Table

2: Assignments of Stage 2 in Section 2 for k - log
unary-cross branching. Figure 3 shows these first few steps. After having handled the
bits in the head of the PWL string, we now use unary-straight (which keeps the 0's)
and binary branchings to assign further levels. After having placed the PEs on level
to nodes in level we change the strategy for the remaining two
levels as follows. A unary-straight, a binary, and a unary-straight branching assigns the
PEs on level m=2 \Gamma 1 to nodes on level Finally, a binary, a unary-straight, a
unary-cross (to level 0 in B 2 ), and a unary-straight branching (to level m in assigns
the PEs on level m=2 of T k (m) to nodes on level m of This strategy results in a
dilation of 2 between levels l and l a dilation of

Table

2 shows the assignment of the PEs of T k (m) for k - log m \Gamma 1. The first line of
the table states the position of the root. The second line covers the levels up to the point
the position of the signatory 1 is encountered. Line 3 covers the remaining position in
the head. Line 4 covers the tail, excluding last two levels that are handled differently as
given in lines 5 and 6. Obviously, not all lines are meaningful in all situations. When
corresponds to the last position in the head and line 3 is
thus meaningless. For lines 2, 3, and 4 are meaningless. In this case the PEs on
level 1 of T 1 (4) are assigned to nodes on level 2 (using line 5) and the PEs on level 2 of
are assigned to nodes on level 4 (using line 6). The branchings done are somewhat
different, but the dilation is at most 4.
We next consider the case when the signatory 1 is positioned in the tail. The overall
strategy is as before. Table 3 shows the assignments for
the ones for briefly discuss Table 3. Line 1 states the position of the root
and line 2 covers the assignments of PEs for which bits in the head of the PWL string
are changed. Line 3 covers the tail positions up to just before a '0' is changed into a
signatory 1. Line 4 covers the remaining assignments up to and including level
of B 1 . The assignments for the last two levels are stated in lines 5 and 6. Again, not
all lines are meaningful. When line 3 only covers levels up to level m
line 4 is meaningless (since there are no more bits to be set before the two final
levels) and line 3 covers levels up to level m
2.

Table

4 shows the assignments for tree
In order to be consistent with Tables 2 and 3, we show   0 's in Table 4. However,
every   0 corresponds to a 0. The situation for tree T 0 (m) when similar to the
situation described for tree T 1 (4) whose assignments are given in Table 2. The PEs on
level 1 of T 0 (4) are assigned to nodes on level 2 (using line 4 of Table 4) and the PEs on
level 2 of T 0 (4) are assigned to nodes on level 4 (using line 5).
We next show that there are no collisions within Stage 2. Obviously, if a node gets
two PEs assigned, they must come from different T k (m)'s. Let x k and x j be two PEs
from T k (m) and T j (m); respectively, that are assigned to nodes on level r. Let y k and y j
be the PWL strings of these nodes, respectively. We show that y k 6= y
loss of generality, that j ! k: We consider two cases depending on the value of k:
Case 1: k - log
Case 1.1: 1: The PWL strings y k and y j differ in the tail.
PWL string y k has (  k as the rightmost 2 log
as the rightmost 2 log
Case 1.2: differ because of the
signatory 1. The PWL string y k has a 1 in position while the
PWL string y j has a 0 in that position.
Case 2:
Case 2.1: This case is similar to Case 1:1:
Level of T k (m) Nodes of Bw (m
l -
l -

Table

3: Assignments of Stage 2 in Section 2 for
Level of T 0 (m) Nodes of Bw (m
l -
l -

Table

4: Assignments of Stage 2 in Section 2 for
Case 2.2: 1: The PWL strings y k and y j are
log differ in at least one of the rightmost blog kc bits.
Case 2.3: m: The PWL string y k has a 1 in position
while the same position in the PWL string y j has a 0:
We complete the discussion of Stage 2 by showing that there are no collisions between
Stage 1 and Stage 2: For there cannot be any collisions since T 0 (4) and T 1 (4) use
only even-numbered levels in Stage 2. Hence, assume r be a level in B 1 that
has PEs assigned both from Stage 1 and Stage 2. Since Stage 1 places the root at level
is the largest odd-numbered level used by Stage 2, we
have the PWL string of any node containing
a PE from Stage 1 starts off with 0101; i.e., it contains a 1 in both position 1 and 3.
any node which is assigned a PE from Stage 2 starts off with either \Lambda0   0,
\Lambda0   1, or \Lambda1   0 and thus there cannot be any collisions. For
Stage 1 and Stage 2 can only occur on level 3. In this case Stage 2 handles four
trees, namely trees T 0 (8). The PWL strings of the nodes on level
3 that get PEs of T k (8), k - 2, assigned in Stage 2 are of the form \Lambda0   1   k 0   k 00 and
hence there cannot be any collisions. The PWL strings of the nodes on level 3 that get
PEs of T 3 (8) assigned in Stage 2 are of the form \Lambda1   1   3 0   3 00 with   3
assigns one PE, namely the root of T (q), to level 3 and it is assigned to the node with
PWL string 010100000. Hence, no collision is possible. This completes our description
of Stage 2 in which we embedded levels 1 through m=2 of T k (m):
The embedding of the last m=2 levels of T k (m) is similar to Stage 3 in [4]. However,
for our purpose, we divide the embedding of the last m=2 levels of T k (m) into two stages,
namely Stages 3 and 4 which embed levels m=2
to m of T k (m); respectively. This division shows precisely how we use only the right half
and the full Bw (m + 1) in Stages 3 and 4; respectively.
Stage 3: Embedding levels m=2
be the i th subtree of height rooted at a PE on level m=2 of T k (m);
shown in Figure 4: Subtrees S i (0) consists only of one PE and these
PEs were already assigned in Stage 2. Hence, Stage 3 embeds the S i (k)'s for k - 1. In
Stage 2 the root of S i (k) was assigned to node ! m; (  i As in
[4], we refer to positions fi 0 fi 2 . fi as the serial number of S i (k): We
embed S i (k) in Stage 3 so that the serial number and signatory 1 remain fixed. The serial
number helps to keep the subtrees S i (k) and S i 0
helps to keep S i (k) and
We embed the first dk=2e levels of S i (k) by growing upwards (i.e., towards lower
numbered levels) in B 2 ; the right half of Bw (m
in B 2 to embed the remaining levels of S i (k): The leaves of S i (k) are placed at nodes
upwards or downwards, we
use every fourth level of B 2 and hence the embedding incurs a dilation of 4: The precise
process of embedding S i (k) is described next.
For we assign the PEs on level l of S i (k) to nodes on level
The root of S i (k) was assigned in Stage 2 to node ! m; (  i
using a binary and two unary-straight branchings, assign the 2 PEs on level 1 of S i (k)
to two nodes We now successively use a
unary-straight, a binary, and two unary straight branchings to assign the 2 l PEs on level
l of S i (k), l - 2, to nodes
If k is odd, we assign the 2 dk=2e PEs on level dk=2e of S i (k) by using a unary-straight
and a binary branching to nodes
An exception occurs for 1. The leaves of S i (1) are at level 1 in S i (1) and they are
assigned to level making a binary branching from a node on level m.
5   i denotes a 0 or a 1 depending on the binary representation of i:
For now grow S i (k) downwards and assign the 2 l PEs on level l
to nodes
The dilation between the root of S i (k) and the two PEs on level 1 is at most 3 (it is 1
1). The dilation between the remaining levels of S i (k) is 4:
An exception occurs between levels bk=2c and dk=2e when k is odd, and between levels
bk=2c and bk=2c is even: in these cases the dilation is 2: Since signatory 1 is
not changed in Stage 3, an argument similar to the one in Stage 2; combined with the
observation that serial number is kept fixed in Stage 3; shows that there are no collisions
within Stage 3: stage 3 uses only odd-numbered levels of B 2 . Since Stages 1 and 2 use
only odd-numbered levels of B 1 , even level level m of
are no collisions among Stages and 3: This completes the description of stage 3:
Before describing stage 4, we briefly explain why the last two levels of T k (m) embedded
in stage 2 (i.e., levels m=2 \Gamma 1 and m=2) were handled differently from the other
levels. stage 2 places the PEs on level
3 places the PEs on level m=2 . In order to keep the
dilation at 4, the PEs on level are placed on level and the PEs on
level m=2 are placed on level m of B 2 , resulting in the different strategy for the last two
levels of T k (m) in stage 2. In addition, placing the PEs of level
of allows us to set the signatory 1 correctly for T 0 (m).
stage 4: Embedding levels m=2
the subtree of T k (m) rooted at the root of T k (m) with height
m=2. Let R k be the forest formed by T k
shown
in

Figure

4: stage 4 embeds the trees in R k with a dilation of 2 using the even levels
in both B 1 and B 2 . Every tree in R k has m=2 \Gamma k levels that need to be embedded.
Recall that the roots of these trees (i.e., the leaves of S i (k)) were assigned for k - 1 in
stage 3 to nodes stage 2 to nodes
To make the necessary branchings we need positions
in the PWL strings. stage 4 uses the positions containing a 0 (and which are
to the left of the signatory 1) and the rightmost position (which is '1' to start with). stage
4 assigns the PEs on the first level of a tree in R k to nodes ! 0; (  i
This is done by a unary-straight and then a binary branching for k - 1 and simply a
binary branching for the trees in R 0 . We now successively use a unary-straight and a
binary branching to embed the remaining levels of R k . Thus, PEs on level l of R k are
assigned to nodes
Since the serial number and signatory 1 remain fixed in this stage, it is easy to see
that there are no collisions within stage 4: stage 4 uses only even-numbered levels and
since Stages 1 and 3 use only odd-numbered levels, there are no collisions between stage
4 and Stages 1 or 3: See Table 1. Note that while level m is used by stage 2 in B 2 , stage
4 does not use level m. Hence, the only possible collisions between stage 2 and stage
4 can occur on level In stage 4 only leaves of T 0 (m) are assigned to level
thus the PWL strings of nodes which have PEs assigned on level are
strings of nodes on level which have PEs assigned in stage 2
are (\Lambda0) position
has a 0 in stage 2; while the same position has a 1 in stage 4 and no collision is
possible. This completes stage 4 and hence the embedding of T (q) into Bw (m 1).
We conclude this section by showing how to modify our embedding when m is even
and not a power of 2. Recall that In stage 1 we embed the
first blog mc levels of T (q) by assigning the root of T (q) to node !
are embedded as before.
Every occurrence of log m is now replaced by blog mc. After stage 1 we don't have m=2
PEs embedded on level . The other three stages embed the
remaining m levels of T (q). stage 2 embeds the next m=2 levels (which are levels blog mc
to m=2 embed the final m=2 levels of T (q).
Since the trees T k (m) are now rooted at PEs on level blog mc \Gamma 1 of T (q), the range of k
is from 0 to 2 blog By reflecting this change throughout Stages 2, 3, and 4 and by
using blog mc instead of log m, we obtain the desired embedding of T (q) into Bw (m+ 1).
The argument of correctness carries over in a straightforward way. The proof that there
are no collisions between the different stages must now consider the interaction between
stage 1 and stage 2 for the case when However, in this case stage 1 uses levels
3 and 5, whereas stage 2 uses levels 1, 4, and 6 and no collisions can occur.
Embedding T (q) into B w (m
In Section 2 we described how to embed T (q) into Bw (m a dilation of 4:
Naturally, the question arises whether there exists an embedding that achieves a smaller
dilation. We do not yet know how to embed T (q) into Bw (m + 1) with a dilation less
than 4; but we next show how to embed T (q) into Bw (m + 2) with a dilation of 2: This
embedding achieves an optimal dilation since no embedding with O(1) expansion can
achieve a dilation less than 2 [4]. For the purposes of description, we again assume that
m is a power of two. Our results hold, however, for any even integer m and the necessary
changes are described at the end of Section 3.
be the i th quarter of Bw (m
shown in Figure 5: We embed T (q) into Bw (m + 2) in three stages. In stage 1 we use
to embed the first log m levels of T (q) so that the PEs on level
log are assigned to nodes on level m+ 1 of be again the k th
tree rooted at a PE on level log
embeds levels 1 to m=2 such that the PEs on level m=2
are assigned to nodes on either level In stage 3 we embed the
remaining levels of T k (m) into B 3 and
The main difference between this embedding and the one described in the previous
section is in stage 2: Our previous embedding and the one in [4] achieve assigning the
PEs on the same level of T (q) to different levels in the butterfly by growing subtrees
upwards and downwards for varying number of levels. The embedding of this section
achieves the same effect by having different subtrees grow for different number of levels
already in stage 2 right after the signatory 1 has been placed. Avoiding the upwards and
downwards growth, together with other modifications, allows us to reduce the dilation
from 4 to 2: We now describe each stage in the embedding of this section in more detail.
stage 1: Embedding the first log m levels of T (q)
In this stage we could use the embedding of stage 1 as given in Section 2: However,
since we are using a Bw (m instead of a Bw (m + 1); we use a simpler embedding
(similar to the one in [4]) that allows us to simplify the remaining stages. We can not use
this version of stage 1 in the embedding of Section 2 since it would result in collisions
between Stages 1 and 2: For the sake of clarity and completeness, we describe stage 1 in
detail.
Assign the root of T (q) to node ! Using binary branchings
we assign, as done in [4], the 2 l PEs on level l of T (q) to nodes
2: Finally, by using a binary and then
a unary-cross branching we assign the m=2 PEs on level log to nodes
In Figure 5 we show a few steps of the embedding in
this stage. Observe that in this stage we use only B 1 and level m+ 1 of dilation
between levels l and l
log It is straightforward to see that there are no collisions in this
stage.
stage 2: Embedding levels 1 to m=2
As done in Section 2, we partition a PWL string into head and tail. The head now
consists of leftmost bits and the tail consists of rightmost log
of the PWL string. While in Section 2 the head was of even and the tail of odd length,
we now have both either even or odd. This is the reason for using d's in the following
description. Observe that a node with a PE assigned to it from stage 1 has a head
consisting of 0's and a tail consisting of \Lambda's with 10 as the two rightmost positions.
The goal of this stage is to assign, with a dilation of 2, the PEs on level m=2 + k of
and the PEs on level m=2 of T 0 (m)
to nodes ?. For tree T k (m), k - 1, the PWL strings get a signatory
l -
l -

Table

5: Assignments of stage 2 in Section 3 for k - d log m\Gamma1e:
set in position will be set. We first describe the
embedding when signatory 1 is placed in the head (i.e., we have k - d log
stage 1 assigned the root of T k (m) to node ! m
we assign the 2 l PEs on level l of T k (m) to nodes on level 2l \Gamma 1 of
by using a unary-straight and a binary branching. We then place the signatory 1 by
making a unary-cross branching and then use a binary branching to assign the PEs on
level to nodes on level Once the signatory 1
has been placed, we use only binary branchings to assign the PEs on level l of T k (m) to
nodes on level shows the precise
assignment for T k (m) with k - d log m\Gamma1e. The first line of the table shows assignment
of the root and the second line covers the assignments up to the point the position of
the signatory 1 is encountered. The third line covers the remaining positions in the
head and the fourth line covers the tail. As in Section 2, not all lines are meaningful
for all situations. For
e, line 3 is meaningless. In this case the signatory 1
corresponds to the rightmost position of the head in case log m is odd and to the second
rightmost position in case log m is even.
The embedding for the case when the signatory 1 is positioned in the tail is similar.
In order to place 0's in the odd-numbered positions before the placement of the signatory
1, we now make a unary-cross or unary-straight branching depending on the value of  .
We show the assignments for log m\Gamma1e in

Table

6. The assignments for tree
are shown in Table 7. For T 0 (m) we stop at level by assigning the
leaves of T 0 (m) to nodes
As already stated, no signatory 1 is set
l -

Table

Assignments of stage 2 in Section 3 for
e:
Level of T 0 (m) Nodes of Bw (m
log
l - b m\Gammalog m+1

Table

7: Assignments of stage 2 in Section 3 for
for T 0 (m). The position for the signatory 1 for T 0 (m) would be position in the
PWL strings. Setting this 1 would require the use of the unary-cross edges from level
thus place the PEs on level m=2 of T 0 (m) on level m. This would
result in a dilation of 3 since the PEs on level are assigned to level
. Not having the signatory 1 set for T 0 (m) requires stage 3 to handle T 0 (m)
somewhat differently.
It is easy to see that the dilation is 2 in stage 2: The argument to show that there
are no collisions within this stage is similar to the one given for stage 2 in Section 2 and
it is omitted. stage 1 uses only B 1 and level only up
to level m. Hence, there are no collisions between stage 1 and stage 2:
stage 3: Embedding levels m=2
This stage is similar to stage 4 in Section 2: However, since the PEs on level m=2
of T 0 (m) are assigned to nodes on level
differently. Let R i be the i th subtree rooted at a PE on level m=2 + k of
first describe the
embedding of the last m=2 levels of T 0 (m) (i.e., embedding R i (m=2) for
and then describe the embeddings of R i
Recall that in stage 2 we assigned the root of R i (m=2) to node !
using a binary branching we next assign the two PEs on level 1 of
to two nodes ! m; (  i assign the PEs on level 2 of
using a binary and a unary-cross branching,
i.e., the PEs on level 2 are placed on level 0 of B 3 or B 4 : We now use a unary-straight and
a binary branching successively to assign the remaining levels of R i (m=2): In general, the
l PEs on level l of R i (m=2) are assigned to nodes
for 3 - l - m=2: The leaves of R i (m=2) are thus assigned to level
stage 2 assigned the root of R i
Assign the PEs on level 1 of R i
using
a binary and a unary-cross branching. Then use a unary-straight and a binary branching
to assign the 2 l PEs on level l of R i
The leaves of R i are thus assigned to level
2.
We now show that there are no collisions within stage 3: Since the serial number
(denoted by the   i 's in the PWL strings) is kept fixed, there are no collisions between
not changed in stage 3
and hence there are no collisions between R i
1: The signatory 1 in position
also avoids the possibility of collision between R i (m=2) and R i This is seen
as follows. Assume level has PEs of both R i (m=2) and R i
assigned. Then, a node containing a PE of R i has its signatory 1 in the position
its PWL string and the leaves of R i are placed on level 2.
A node containing a PE of R i (m=2) starts off with a 0 in position
is changed into a 1 (by a binary branching) when going from level level
never changed.) Hence, there cannot exist a node
that is assigned both a PE from R i (m=2) and R i
Finally, it is easy to see that there are no collisions between Stages 1 or 2 and stage 3:
Stages 1 and 2 use only
also uses level m of B 2 in stage 3: However, the signatory 1's keep the nodes on level
m that have PEs of T k (m) assigned in stage 2; for k - 1; distinct from the nodes that
have PEs of T 0 (m) assigned in stage 3: This completes stage 3 and hence our second
embedding.
We conclude this section by showing how to modify our embedding of this section
when m is an even integer and not a power of two. In stage 1, we embed PEs on levels
0 to blog mc \Gamma 2 of T (q) to nodes on levels . The PEs on
level blog are assigned to nodes on level Every occurrence
of log m is now replaced by blog mc. After stage 1 we have 2 blog m\Gamma1c PEs embedded on
level m+ 1 of B 2 . Hence, we have 2 blog m\Gamma1c trees T k (m)'s and the range of k is from 0 to
By reflecting this change throughout Stages 2 and 3 and by using blog mc
instead of log m, we obtain the desired embedding of T (q) into Bw (m
4 Embeddings using no wrap-around
In the previous two sections we described two embeddings of complete binary trees into a
butterflies with wrap-around connections. Both embeddings make heavy use of the wrap-around
connections. In this section we first show that, while wrap-around connections
are convenient, they do not make the butterfly more powerful (in an asymptotic sense).
More precisely, we next describe an embedding of Bw (m) into B(m) which has a dilation
of 3: To the best of our knowledge this useful result has not been documented in the
literature. By making use of this result, we then show that T (q) can be embedded into
with a dilation of 8 (resp. 5).
For clarity, henceforth we refer to the nodes of Bw (m) as PEs and to the nodes of B(m)
as nodes. The embedding of Bw (m) into B(m) achieves an expansion of (m+1)2 m
2:
This is optimal since B(m) is the smallest butterfly with no wrap-around consisting of at
least m2 m nodes. Any embedding of Bw (m) into B(m) must achieve a dilation of at least
2: To show this, assume, for the sake of contradiction, that there exists an embedding
ae with a dilation of 1: In ae every node of B(m) is assigned at most one PE of Bw (m):
Furthermore, an edge in B(m) is assigned an edge in Bw (m): Since the number of nodes
in B(m) is greater than the number of PEs in Bw (m); there exists a node v in B(m)
that has no PE of Bw (m) assigned to it. No edge incident to v has an edge of Bw (m)
assigned to it (otherwise the dilation would be more than 1). Now, since v has at least 2
incident edges, at most m2 edges of B(m) have edges of Bw (m) assigned to them
in ae. Since Bw (m) consists of m2 m+1 edges and every edge of B(m) is assigned at most
1 edge of Bw (m); ae can not have a dilation of 1:
We assign the PEs on level 0 of Bw (m) to nodes on level 0 of B(m): The remaining
PEs are assigned so that two PEs on adjacent levels in Bw (m) are at most 2 levels apart
in B(m) and the PEs on level are assigned to nodes on level 3: Furthermore, nodes
on level 1 of B(m) get no PE assigned. Formally, let p =! be a PE of
assigned to node ! f(l); ff 0 ff 1 . ff
For example, when string fi 0 fi 1 fi 2 fi 3 fi 4 fi 5 fi 6 fi 7 is assigned to the
node that has PWL string ff
on levels 0; 1; 2; 3; 4 are assigned to nodes on levels 0; 2; 4; 6; 8; respectively, and PEs on
levels 5; 6; 7 are assigned to nodes on levels 7; 5; 3; respectively.
It is easy to see that no two PEs are assigned to the same node and hence we have an
embedding of Bw (m) into B(m). We next show that the dilation is 3: Assume that m is
an even integer (the argument for odd m's is analogous). Let (p cross edge of
Bw (m) with
l . fi
1: Depending on the value of l we distinguish four cases.
Case 1:
are assigned to nodes v 1 =! 2l; fi 0 fi
connected
to v 2 by a path consisting of a cross and a straight edge resulting in a dilation of
2:
Case 2:
assigned to node v 1 =! m; fi 0 fi assigned
to node v
are connected by a
cross edge and the dilation between p 1 and p 2 is 1:
Case 3: 2:
assigned to node v 1
and PE p 2 is assigned to node v 2 =!
l . fi
Hence v 1 and v 2 are connected by a path that consists of a straight and a cross edge,
and the dilation is 2:
Case 4:
assigned to node v 1 =! 3; fi 0 fi is assigned to
node v 2 =! 0; fi 0
connected to v 2 by a path consisting
of a straight, a cross, and a straight edge, and hence the dilation between p 1 and p 2 is 3:
While in our embedding the wrap-around edges are the ones having a dilation of 3;
any level l of Bw (m) can be chosen so that edges from level l to l dilation of
3: This completes the embedding of Bw (m) into B(m) with a dilation of 3; and we next
briefly describe the embedding of T (q) into a no wrap-around butterfly.
By first embedding T (q) into Bw (m a dilation of 4 (using the embedding
of Section 2) and then embedding Bw (m a dilation of 3; it
immediately follows that T (q) can be embedded into a dilation of at
most 4   Similarly, T (q) can be embedded into with a dilation of at
most 2   However, since only the wrap-around edges incur a dilation of 3 and the
remaining edges incur a dilation of at most 2; we can do better. Every edge of T (q) maps
onto a path of length at most 4 in Bw (m + 1) and every such path contains at most one
wrap-around edge. Hence, the dilation of every edge of T (q) is at most 3
Similar arguments can be used to embed T (q) into B(m + 2) with a dilation of only
5:
In order to obtain the claimed dilation of 8 for the embedding of T (q) into B(m+ 1);
we change the embedding of Bw (m so that the edges from level 1 to
2 of Bw (m+ 1) have a dilation of 3 in B(m+ 1) and the remaining edges have a dilation
of at most 2: Edges of T (q) using an edge from level 1 to 2 of Bw (m+ 1) have a dilation
of only 2 and thus have a dilation of 3 having a
dilation of 4 in Bw (m + 1) now incur a dilation of 4
Conclusions
In this paper we described two embeddings of a complete binary tree T into a wrap-around
butterfly Bw , and two embeddings of T into a no wrap-around butterfly B: The
first embedding embeds T (q) into Bw (m a dilation of 4; where
1: The second one embeds T (q) into Bw (m + 2) with a dilation of 2: The first
embedding achieves an expansion of 2; while the second one achieves an expansion of 4
and an optimal dilation. An embedding optimizing both the dilation and the expansion
would embed T (q) into Bw (m a dilation of 2 (for even m) [4]. We feel that
a technique different from the one using signatory 1's is needed to achieve this bound.
Our third (resp. fourth) embedding embeds T (q) into B(m
a dilation of 8 (resp. 5).
6

Acknowledgements

We would like to thank an anonymous referee for helpful suggestions and comments.



--R

On embedding rectangular grids into square grids.
On multidimensional arrays of processors.
Embedding Grids into Hypercubes.
Optimal simulations by Butterfly networks.
Optimal simulations of tree machines.
On embedding rectangular grids in hypercubes.
Quotient networks.
Embedding large tree machines into small ones.
Cost trade-offs in graph embeddings
Optimal simulations between mesh connected array of processors.
Preserving proximity in arrays.
Topological properties of hypercubes.
--TR
Optimal simulations between mesh-connected arrays of processors
Topological Properties of Hypercubes
On Embedding Rectangular Grids in Hypercubes
On Multidimensional Arrays of Processors
Optimal simulations by Butterfly Networks
Embedding large tree machines into small ones
Cost Trade-offs in Graph Embeddings, with Applications
Embedding Grids into Hypercubes

--CTR
Xiaojun Shen , Weifa Liang , Qing Hu, On Embedding Between 2D Meshes of the Same Size, IEEE Transactions on Computers, v.46 n.8, p.880-889, August 1997
multiprocessor interconnection networks;butterfly networks;trees mathematics;wrap-around connections;embeddings;complete binary trees