Executing Algorithms with Hypercube Topology on Torus Multicomputers.
AbstractMany parallel algorithms use hypercubes as the communication topology among their processes. When such algorithms are executed on hypercube multicomputers the communication cost is kept minimum since processes can be allocated to processors in such a way that only communication between neighbor processors is required. However, the scalability of hypercube multicomputers is constrained by the fact that the interconnection cost-per-node increases with the total number of nodes. From scalability point of view, meshes and toruses are more interesting classes of interconnection topologies. This paper focuses on the execution of algorithms with hypercube communication topology on multicomputers with mesh or torus interconnection topologies. The proposed approach is based on looking at different embeddings of hypercube graphs onto mesh or torus graphs. The paper concentrates on toruses since an already known embedding, which is called standard embedding, is optimal for meshes. In this paper, an embedding of hypercubes onto toruses of any given dimension is proposed. This novel embedding is called xor embedding. The paper presents a set of performance figures for both the standard and the xor embeddings and shows that the latter outperforms the former for any torus. In addition, it is proven that for a one-dimensional torus (a ring) the xor embedding is optimal in the sense that it minimizes the execution time of a class of parallel algorithms with hypercube topology. This class of algorithms is frequently found in real applications, such as FFT and some class of sorting algorithms.
Introduction
A hypercube communication topology is frequently found in real parallel applications. Some
examples include parallel algorithms for FFT, sorts, etc. [3], [11]. These algorithms will be called
hypercube algorithms or d-cube algorithms, where d is the number of dimensions of the
hypercube. A hypercube algorithm of dimension d or d-cube algorithm, consists of 2 d processes
labeled from 0 to 2 d -1 such that every process communicates only with its d neighbors, one in
each dimension of the d-cube.
In this paper, the problem of executing d-cube algorithms on multicomputers [1] is
considered. A multicomputer is a distributed memory multiprocessor in which the nodes
(processor local memory) are interconnected through point to point links.
The nodes of a multicomputer are interconnected according to a given pattern or
interconnection topology. If this topology is a hypercube of dimension d (d-cube multicomputer)
then the d-cube algorithm can be executed on the multicomputer in such a way that neighbor
processes are mapped onto adjacent nodes (nodes directly connected through a point to point
link). In this case, it is said that each process of the d-cube algorithm has all its d neighbors at
distance 1 in the multicomputer (i.e., all required communication is between neighbor nodes). In
this way, the cost of the communication component of the d-cube algorithm is kept minimum
when it is executed on a hypercube multicomputer.
An important drawback of hypercube as interconnection topology for multicomputers is that
it is not scalable. In a d-cube multicomputer each of the 2 d nodes is directly connected to other d
nodes through point to point links. Therefore, the cost (and the complexity) of the interconnection
hardware per node increases with the number of nodes. Other interconnection topologies, such
as meshes or toruses are considered more suitable for multicomputers with a large number of
nodes, since the interconnection cost per node does not depend on the total number of nodes [13].
For instance, each node of a two-dimensional torus multicomputer is directly connected to other
4 nodes, it does not matter the number of nodes of the multicomputer.
To execute a d-cube algorithm on a multicomputer with topology other than hypercube, the
first step is to find a mapping function that allocates each process of the parallel program onto a
given processor of the multicomputer. The problem can be formulated as finding an embedding
of the graph that represents the topology of the program (a hypercube) onto the graph that
represents the topology of the multicomputer (a mesh or a torus).
The problem of embedding a given source graph into a destination graph has been
extensively studied in the literature. In particular, embedding any type of graph into a hypercube
is a widely studied topic (see, for instance, [2],[7],[11],[12], just to mention a few recent works).
However, the problem of embedding hypercubes onto a mesh or a torus has not been so
extensively studied. In section 2.3. we review the most relevant works in this subject.
When the topology of the algorithm and the multicomputer are different, it may be
impossible to allocate neighbor processes to neighbor processors. For instance, in a two-dimensional
torus multicomputer, every process of a d-cube algorithm has at most 4 of its d
neighbors at distance 1. It has at least d-4 neighbors at a distance greater than 1. A message to
any of these "far" neighbors is routed through the point to point links and nodes which are found
along the path to the destination node. A good mapping of a parallel algorithm onto a
multicomputer will keep the neighbor processes as close as possible in the multicomputer,
minimizing in this way the communication cost of the execution.
This paper begins by reviewing some related work on embeddings and then, it concentrates
on a particular type of embeddings that is called embeddings with constant distances. It will be
shown that these embeddings are more adequate for our purposes, that is, for executing d-cube
algorithms onto meshes or toruses. A well known embedding of hypercubes onto meshes is the
so called standard embedding [8]. It is an embedding with constant distances and it is optimal for
meshes of any given dimension. In consequence, the contribution of this paper centers on
embeddings of hypercubes onto toruses.
A new embedding, called xor embedding, is proposed. The paper presents a set of
performance figures and shows that this embedding outperforms the standard embedding when
it is used as the mapping function of a d-cube algorithm onto a torus multicomputer. In addition,
it is proven that the xor embedding is optimal for one-dimensional toruses (also called rings).
This paper is organized as follows. In section 2, we introduce some notation and describe
more precisely the contribution of this paper as well as some related work. Sections 3 presents
the xor embedding. Section 4 compares the performance of the xor embedding with that of the
standard embedding using a set of different performance metrics. In section 5, it is proven that
the proposed embedding is optimal for rings in the sense that it results in the shortest execution
time of a class of d-cube algorithms. Finally, some concluding remarks are presented.
2. Preliminaries and related work
2.1. Definitions
A d-cube algorithm is a parallel algorithm that consists of 2 d processes such that every process
communicates with exactly other d processes. These d processes are called its neighbors. We also
say that the communication topology of the algorithm is a hypercube. That means that the 2 d
processes can be labeled from 0 to 2 d -1 in such a way that processes n and m are neighbor (i.e.
they communicate) if the binary codes for n and m differ in a single bit. If this bit is the i-th bit
then m is the neighbor of n in dimension i, and n is the neighbor of m in the same dimension.
Then, it is written:
In this paper, we focus on d-cube algorithms in which every process has the following
structure:
do i=0,d-1
compute
communicate with neighbor in dimension i
In this algorithm every process consists of d stages, each of them composed of a computation
phase followed by a communication phase. In each stage, every process uses a different
dimension to exchange information with one of its neighbors.
The duration of the computation phase and the amount of information to be exchanged is
assumed to be the same for all the stages and all the processes of the d-cube algorithm. A d-cube
algorithm with the above features will be called a compute-and-communicate d-cube algorithm,
or a CC d-cube algorithm for short. This kind of d-cube algorithms are common in real
applications like FFT, some type of sorts, etc. [3], [11].
Parallel algorithms can be modelled by graphs. The vertices of the graph represent the
processes of the algorithm and the edges of the graph represent the neighbor relationship among
processes. A multicomputer can also be modelled by a graph. The vertices of the graph represent
the nodes of the multicomputer and the edges of the graph represent the point to point links which
interconnect these nodes. The terms edge and link will be used indistinctly in this paper.
Multicomputers can be classified according to their interconnection topology. The work
presented in this paper focuses on mesh and torus multicomputers, since they have scalable
interconnection topologies.
c-dimensional torus is an undirected graph in which the nodes can be labeled
as c-tuples (i 1 . Every node (i 1 ,i 2 ,.,i c ) of the graph has two neighbors in each
dimension of the torus. Its left neighbor in dimension j is (i 1 ,.,(i j -1) mod k j ,.,i c ) and its right
neighbor in this dimension is (i 1 ,.,(i j +1) mod k j ,.,i c ).
c-dimensional mesh is an undirected graph in which the nodes can be labeled
as c-tuples (i 1 . Every node of the graph has two neighbors in each dimension
j of the mesh if 0 < Its left neighbor is (i 1 ,.,i j -1,.,i c ) and its right neighbor is
the node has only a right neighbor and if i j =k j -1 then it only has a left
neighbor.
A line is a one-dimensional mesh while a one-dimensional torus is called a ring.

Figure

shows some examples and illustrates how their nodes are labeled.
The distance in a graph between two vertices is the minimum number of edges that join those
vertices. In the particular case of the graph that models a d-cube, the distance between two
vertices is known as the Hamming distance (number of different bits in their binary
representations).
An embedding of graph G into graph H is an injection from the vertices of G to the vertices
of H. In this paper, our attention is restricted to embeddings in which G and H have the same
number of vertices, and therefore the mapping is given by a bijective function.
The problem of executing a CC d-cube algorithm on a multicomputer can be restated as the
embedding of graph G, which represents the CC d-cube algorithm, onto graph H, which
represents the multicomputer.
The dilation of an edge (n,m) of G (edge joining vertices n and m) is the distance in H
between f(n) and f(m).
If G models a CC d-cube algorithm, an edge exists between vertices n and m if m=N i (n), for
some i - [0,d-1]. The dilation of this edge will be denoted by D i (n). Obviously, since n= N i (m),
(m). When a CC d-cube algorithm is executed on a multicomputer, as defined by a
given embedding f, a communication between processes n and N i (n) (required in iteration i of the
CC d-cube algorithm) is implemented by a message which is routed through D i (n) point to point
links and D i (n)-1 nodes of the multicomputer represented by H, which are found in the shortest
path between nodes f(n) and f(N i (n)). In the following, a store and forward routing strategy is
assumed. Therefore, the cost of sending a message from f(n) to f(N i (n)) is proportional to D i (n).
2.2. Contributions
As it was mentioned in the introduction, this paper focuses on executing CC d-cube algorithms
on scalable multicomputers. The function that maps processes onto processors is an embedding
of the graph defined by the communication topology of the algorithm (hypercube) onto the graph
defined by the interconnection topology of the multicomputer. In particular, we are interested in
torus multicomputers since for meshes, an already known embedding, called standard
embedding and described in the next section, is optimal for CC d-cube algorithms.
0,2 0,3
(c)
0,2 0,3
(d)

Figure

1: Different types of multicomputers: a) line, b) ring, c) (4,4) mesh and
d) (4,4) torus.The picture also shows how their nodes are labeled.
The work presented in this paper centers on those embeddings in which D i
[0,d-1] and n - [0,2 d -1]). This means that every process has its neighbor in dimension i at the
same distance in the target multicomputer. In the following, an embedding with this feature is
called embedding with constant distances and the values of D i (i - [0,d-1]) are called the
distances of the embedding.
Embeddings with constant distances have the property that every process takes the same
time to communicate in any given stage of the CC d-cube algorithm. Because the duration of the
compute phase is also the same for every process, waiting intervals are avoided since neighbor
processes arrive at the same time at the point where they have to communicate. This fact will be
illustrated later through an example.
In this paper, an embedding with constant distances of hypercubes onto toruses of any
arbitrary dimension is proposed. The embedding is called xor embedding. It will be shown that
this embedding outperforms the standard embedding using a set of different performance
metrics. Moreover, we prove that the proposed embedding is optimal for rings (one-dimensional
toruses) in the sense that it minimizes the execution time of CC d-cube algorithms when they are
executed on a ring multicomputer. Another additional property of the proposed embeddings is
their simplicity, which means a negligible cost to compute the location of any process in the
multicomputer. Some preliminary results about the xor embedding were presented in [4].
2.3. Related work
The problem of embedding d-cubes onto meshes and toruses has been previously considered by
other authors. Here, a review of the most related work is presented.
Matic presents in [10] a study of the standard embedding (defined below) of d-cubes onto
two-dimensional meshes and toruses. To define the standard embedding (which will be denoted
by f std ) of a d-cube onto a line or a ring, the nodes of the target multicomputer are numbered from
0 to 2 d -1 (see figures 1.a and 1.b). Then, the standard embedding is defined by (see figure 2.a):
In general, the standard embedding of a d-cube onto a c-dimensional mesh or
torus is defined as follows:
where:
f std n
f std n
Figure

2.b shows an example in which c=2 and k 1 =k 2 =4. Obviously, the standard
embedding is an embedding with constant distances. For the particular case in which k i =2 d/c ,
i-[1,c], the distances of the standard embedding are:
It can be shown that the standard embedding is optimal for meshes, in the sense that it
minimizes the average distance [5], which in turns results in the shortest execution time.
However, it is not optimal for toruses, as it will be shown later in this paper.
Harper in [6] and Lai and Spague in [8] solve the problem of embedding d-cubes onto
meshes to minimize the dilation of the embedding (the maximum dilation of any edge). Both
proposals use the byweight embedding, denoted by f bw , which is not an embedding with constant
distances. Next, this embedding is briefly described.
In the case of a line, the labels of the vertices which represent the processes of the d-cube
algorithm are ordered by their weights. The weight of a label is the number of 1's in its binary
representation. Labels with the same weight are ordered in descending order. Then, the processes
of the d-cube ordered in that way are allocated to the nodes of the line, from left to right. Figure
3.a shows an example. The byweight embedding can be extended to meshes of any dimension.
In particular, Lai and Spague extend this embedding to two-dimensional meshes in [8]. Figure
3.b shows an example.
The byweight embedding minimizes the dilation of the embedding for lines and it has a
lower dilation than the standard embedding for two-dimensional meshes. This is an interesting
property in some particular applications of embeddings. For instance, Lai and Spague propose
this embedding to solve the problem of placing the processors of a hypercube on a printed circuit
board or a chip (which can be modelled as a two-dimensional mesh). However, the byweight
embedding is not an embedding with constant distances, which is an important property in the
(b)

Figure

2: Standard embeddings of: a) a 3-cube onto a line or a ring and b) a
4-cube onto a (4,4) mesh or torus. Each label indicates which vertex
of the d-cube is mapped onto each node of the multicomputer.
Wrap-around links are not shown for clarity.
context of executing CC d-cube algorithms onto multicomputers. Variable distances result in
waiting intervals during the execution of the CC d-cube algorithm. These are due to the fact that
two neighbors that are going to communicate finish their respective previous computation at
different time. The one that finish earlier must wait for the other to finish. These waiting intervals
contribute to increase the execution time. To illustrate this fact, figure 4 shows an example in
which the execution times of a CC 3-cube algorithm on a line for both the standard embedding
and the byweight embedding are compared. The waiting intervals which contribute to make the
byweight embedding run slower than the standard embedding are also shown.
. In [9], E. Ma and L. Tao proposed several embeddings among toruses and meshes of
different dimensions. Their proposals are based on generalizing the concept of gray code from
numbering system to mix-radix numbering systems. Since a d-cube can also be seen as a
d-dimensional mesh or torus with two elements in each dimension, their embedding can also be
applied to solve the problem addressed in this paper. However, they focus on minimizing the
dilation (the longest dilation of any link of the d-cube) and therefore the resulting embeddings in
general do not have constant distances, which is a desirable property for our objective. However,
if one starts with a d-cube represented by means of a (2,2,.,2) d-dimensional mesh or torus, then
the resulting embedding onto a ring or a two-dimensional torus has constant distances.
Nevertheless, its average distance and therefore its performance for executing our target
algorithm is worse than the embedding proposed in this paper.
3. The xor embedding
Since the standard embedding is optimal for meshes, we focus just on toruses. The proposed
embedding is called xor embedding and it is denoted by f xor . It belongs to the class of embeddings
with constant distances. In this section, the xor embedding for the case of a one-dimensional torus
(a ring) is first described and then it is generalized for any dimension.
28 26
(b)

Figure

3: Byweight embeddings of: a) a 3-cube onto a line and b) a 5-cube onto
a
3.1. One-dimensional Torus (Ring)
Given a positive integer x, let x(i) denote the ith bit of the binary representation of x. The least
significant bit is considered to be the 0th bit. Let G be the graph which represents the CC d-cube
algorithm and R be the graph which represents the ring multicomputer. Assume that the vertices
of R are labeled from 0 to 2 d -1clockwise (see figure 1.b). Let (n(d-1), n(d-2),.,n(1),n(0)) be the
label (in binary code) of vertex n in G. This vertex is mapped onto vertex m=f xor (n) in R, whose
label in binary code (m(d-1),.,m(0)) is:
where XOR (a,b) is the exclusive-or of bits a and b. Figure 5 shows an example for d=4.
node
(b) (c)
Computation
Communication
Waiting interval

Figure

4: a) Dilations for the standard and byweight embeddings (d=3).
Executing a CC 3-cube algorithm on a line using: b) the standard
embedding and c) the byweight embedding.
3.2. General Case
The xor embedding of a d-dimensional hypercube onto a (2 d1 ,2 d2 ,.,2 dc ) c-dimensional torus
such that d 1 +d 2 +.+d c =d is now presented.
Let us first define K j in the following way: K 1 =0, and for every 1<j-c+1 we have that:
Let G be the graph which represents the d-cube and T be the graph which represents the torus.
Then, vertex n of G is mapped onto vertex (m 1 ,m 2 ,.,m c )=f xor (n) in T as follows:

Figure

6 shows an example for d=6. It can be noted that both the standard and the xor
embedding of a d-cube onto a c-dimension torus can be viewed as multiple embeddings of
smaller hypercubes onto rings. For instance, in figure 6, nodes from 8 to 13 of the 6-cube
constitute a 3-cube that is mapped onto the 8 nodes of the second row of the torus which
constitute a ring. This embedding is again a xor embedding.
Note the simplicity of function f xor (n). This function, which is used very frequently for
routing messages during the execution of the CC d-cube algorithm, consists of simple bit
operations and its computational cost is negligible.
4. Performance analysis
In this section, the performance of the xor embedding and the standard embedding are compared
using a set of different performance metrics. Most of these metrics were used by Matic in [10] to
evaluate the standard embedding for two-dimensional meshes and toruses. Here, the
corresponding expressions for both the standard and the xor embeddings of a d-cube onto a

Figure

5: A xor embedding of a 4-cube onto a ring. The labels indicate which node
of the d-cube is mapped onto the corresponding node of the ring.
d-cube nodes
c-dimensional torus are derived. In some cases where the general expressions are
not easy to compare, we derive the expression corresponding to the particular case of a squared
torus. A squared torus is a (2 d/c ,2 d/c ,.,2 d/c ) c-dimensional torus, that is, a torus whose all
dimensions have the same size. These list of metrics is the following:
. The execution time (T f (d 1 ,d 2 ,.,d c )). This represents the execution time of a CC
(d 1 +d 2 +.+d c )-cube algorithm onto a (2 d1 ,2 d2 ,.,2 dc ) c-dimensional torus when the
embedding f is used as the mapping function.
. The links dilation spectrum . This gives the number of links with
dilation D when a (d 1 +d 2 +.+d c )-cube is embedded onto a (2 d1 ,2 d2 ,.,2 dc )
c-dimensional torus as defined by the mapping function f.
. The longest dilation . This is the maximum dilation of any link of
the hypercube when it is embedded onto a (2 d1 ,2 d2 ,.,2 dc ) c-dimensional torus as defined
by the embedding f.
. The total dilation . This represents the sum of dilations of all links
of the hypercube

Figure

xor embedding of a 6-cube onto a (8,8) torus. The wrap-around
links are not shown, for clarity.
48
d-cube nodes
A d 1 d 2 . d c
f D
. The maximum load and minimum load .
The load of a node due to communication tasks is measured as the number of links of the
hypercube that traverse that particular node (those links that begin or finish at that node
are not considered). These parameters give the maximum and minimum value of the load
of any node as a result of using the embedding f.
. The average load . This is the average load of a node due to
communication tasks.
4.1. Execution time
When using an embedding as a mapping function of a parallel algorithm onto a multicomputer,
the most important performance measure of the embedding is the time that the execution of the
algorithm takes as a result of using such a mapping.
Let T a be the duration of the arithmetic computation phase in every stage of the CC d-cube
algorithm, when it is executed on the target multicomputer. Let T c be the cost of sending a
message through a point to point link on the multicomputer.
The time to execute a CC d-cube algorithm on a multicomputer with 2 d nodes, using the
embedding f can be expressed as:
where T cf is the cost of the communication component of the CC d-cube algorithm. T cf can be
expressed as follows:
In the above expressions, T i (n) is the cost of the communication component for process n
from the beginning of the execution to the end of stage i. Expression (a) indicates that T cf is equal
to the highest communication component cost of any process at the end of the d stages of the CC
d-cube algorithm. Expression (b) gives the communication component cost for process n at the
end of stage i. In this stage process n must exchange information with its neighbor N i (n). The cost
of exchanging this information is D i (n)T c . (since a store and forward routing is assumed).
However, this exchange cannot start until both processes n and N i (n) are ready to do it. In general,
either process n or process N i (n) will have to wait for its neighbor to arrive to the point in which
communication can be started. This is why the term "max" appears in expression (b). These idle
intervals were called waiting intervals in figure 4.
ave
Obviously, if the multicomputer has a d-cube interconnection topology then the best
embedding is embedding). In this case D i n) and the
execution time is
If the embedding has constant distances then D i every n. In this case, the time to
execute a CC d-cube algorithm onto a multicomputer, as defined by an embedding f is:
where D a is the average distance of the embedding:
For a (2 d1 , .,2 dc ) c-dimensional torus, the average distance of the standard embedding is:
and the average distance corresponding to the xor embedding is:
Since the execution time of the CC d-cube algorithm is proportional to the average distance
of the embedding we can conclude that the standard embedding results in about a 33% increase
in the execution time when compared with the xor embedding.
Obviously, the embedding with constant distances which minimizes the execution time of
the CC d-cube algorithm is that whose average distance D a is minimum. An embedding with such
property is said to be optimal. The standard embedding is optimal for meshes of any dimension
but not for toruses since we have just seen that the xor embedding outperforms it. In addition, it
will be proven in section 5 that the xor embedding is optimal for one-dimensional toruses.
- dT a T c D i
D a
d
averagedistance f
D a
std
c
c
d
D a
xor
c
c
d
4.2. Links dilation spectrum
4.2.1. Standard embedding on rings
Here, the links dilation spectrum for the standard embedding in the case of a one-dimensional
torus is derived.
Notice that any node of the hypercube has its neighbor in dimension i at distance 2 i in the
torus. Since there are 2 d nodes, we have 2 d-1 links with dilation 2 i for each i-[0, d-1]. We can
then conclude that the links dilation spectrum is:
4.2.2. Xor embedding on rings
In the xor embedding for rings, every node has a neighbor at distance 2 i for each i-[0, d-2] and
two neighbors at distance 2 d-2 . In consequence, the links dilation spectrum is as follows:
4.2.3. General case
The links dilation spectrum for both the standard and xor embeddings can be computed from the
spectrum of the one-dimensional case using the following expression:
In the particular case of a squared c-dimensional torus, for the standard embedding we have
that
and, assuming d/c - 2, for the xor embedding the corresponding expression is
A d
A d
A d 1 d 2 . d c
c
c
A d 1 d 2 . d c
A d 1 d 2
. d c
4.3. Longest dilation
The longest dilation can be obtained from the links dilation spectrum functions previously
developed. For the standard embedding we have that
and for the xor embedding the corresponding expression is (assuming )
It can be seen that the longest dilation of the xor embedding is 50% shorter than that of the
standard embedding.
4.4. Total dilation
This parameter can also be computed using the links dilation spectrum. It is given by the
following
where . Next, this expression is further developed for both the standard and the xor
embeddings and for some particular toruses.
In the case of the standard embedding on rings we have that
whereas for the xor embedding on rings the total dilation is
In the case of a squared c-dimensional torus we have that
std d 1 d 2 . d c
xor d 1 d 2 . d c
x
std d
xor d
std d c
/ . d c
xor d c
/ . d c
d c 3
Notice that the total dilation of the standard embedding is about 33% higher than that of the
xor embedding in both cases.
4.5. Maximum and minimum load
In this section, the load due to communication tasks of every node is analyzed. The objective is
to determine the value for the most loaded node and the least loaded one.
4.5.1. Standard embedding on rings
Assume that a d-dimensional hypercube is to be embedded onto a one-dimensional torus with 2 d
nodes. Let be the load of node n due to the links whose dilation is 2 i . We have that
Notice that is a periodic function with period and it is defined in the interval
.

Figure

7 illustrates an example when d=4. The figure shows the load of every
node due to links whose dilation is 2 2 .
Let be the load of node n due to links whose dilation is either 2 i or 2 i-1 , that is,
It can be shown that
Again is a periodic function with period and it is defined in the interval
.

Figure

8 shows graphically how these expressions were obtained.
std n
std n
std n

Figure

7: Load of each node due to links with dilation equal to 4 for the standard
embedding of a 4-cube onto a ring.
std n
std n
std n
std n
std n
std n
Now, the total load of a given node, which is denoted by , can be computed. If d
is even then
and if d is odd we have that
and obviously,
Due to the fact that the period of is four times the period of , there
are always two periods of where is maximum for every n inside these
two periods. In consequence, there is always at least one node n such that both and
get its maximum value for this node (see figure 9).Therefore, if d is even then
and if d is odd
Since
std d n
std d n
std n
std n
std n
std n
std d n
std n
std n
std n
std d
std d n
std n
std n
std n
std n
std n
std n
std d
std n
std n
std n

Figure

8: Computing from and
std n
std n
std n
std n
std n
std n
std n
std n
std d
std n
std n
std n
std n
the maximum load of the standard embedding on rings is given by the following expression:
Regarding the minimum load, it can be seen that nodes 0 and 2 d -1 have a null load; then,
4.5.2. Xor embeddings on rings .
Notice that the load of a node due to links whose dilation is less than 2 d-2 is the same for both the
standard and the xor embedding, that is
In consequence
The load due to links whose dilation is 2 d-2 is equal to . This is
illustrated in figure 10 by means of a particular example. Since this is a constant function, we can
conclude that
std d
std d
std n
std n
is maximum for every n belonging to this range
(two periods of ).
std n
std n

Figure

9: This figure illustrates that
std n
std n
std n
std n
.
xor n
std n
xor d n
xor n
std d 2
xor n
xor d
std d 2
which results in
Regarding the minimum load, we have that
since .
4.5.3. General case
Since both the standard and xor embeddings of a hypercube onto a c-dimensional torus can be
regarded as several embeddings of smaller hypercubes onto rings, there is always at least one
node for which the load is maximum in all the dimensions of the torus, and at least one other node
for which the load is minimum in all the dimensions. Then, it follows that
xor n

Figure

10: Load of each node due to links with dilation equal to 4 for the xor embedding
of a 4-cube onto a ring.
xor d
std d 2
std d 2
Table

1 compares the maximum and minimum load of both embeddings onto different
toruses. We can conclude that the xor embedding has a higher minimum load but a lower
maximum load. That is, the load of the nodes with communication tasks is more evenly
distributed, which is a desirable property.
4.6. Average load
Taking into account that a link with dilation D results in a unitary additional load to D-1 nodes,
the average load of nodes due to communication tasks can be computed from the links dilation
spectrum using the following expression for both embeddings:
where .
For the particular case of a ring, the average load is

Table

1: Maximum and minimum load for both the standard and the xor embeddings.
Size of the torus
ave d 1 d 2 . d c
x
ave
std d
ave
xor d
For a c-dimensional squared torus the average load is
In both cases, the average load of the standard embedding is about 33% higher than that of
the xor embedding. The difference is even higher for small hypercubes. We can then conclude
that for the execution of any parallel algorithm with a hypercube communication topology the
xor embedding will result in a quite less number of communication conflicts. Notice that in the
case of the CC d-cube algorithms analyzed in this paper, due to their particular structure, conflicts
never occur for the two embeddings.
5. Proof of optimality of f xor for rings
The average distance as defined in section 4.1, will be used as the main criterion to measure the
goodness of any embedding with constant distances, since minimizing the average distance
implies minimizing the execution time of CC d-cube algorithms. In this section, it is proven that
the xor embedding has the minimum average distance for embeddings with constant distances of
hypercubes onto rings.
To show that the xor embedding is optimal for rings, we will prove that the average distance
of any embedding with constant distances is higher than or equal to the average distance of the
f xor embedding. This is stated by theorem 10. Before this theorem, several lemmas and
corollaries that are needed to prove that result are presented. First, a lower bound for the sum of
any set of d-1distances corresponding to any embedding with constant distances is found. Then,
a lower bound for the highest distance of the embedding is computed. Both together give a lower
bound for the average distance of any embedding with constant distances. This lower bound is
the average distance of the f xor embedding, which proves its optimality.
Given any node of a hypercube, we define N D (n), where D is any subset of
dimensions of the hypercube, as the node that is reached by starting at node n and moving through
every dimension in D, one after another, using each dimension exactly once (as we know, the
order in which the dimensions are used does not matter, the result will be the same). For instance,
if D={1,3}, then N D
ave
std d 1 d 2 . d c
ave
xor d 1 d 2 . d c
d c
In the following, N i (N j (n)) will be written as N i N j (n). The parenthesis are removed for the
sake of clarity, but the meaning referring the order in which dimensions are used is preserved.
That is, N i N j (n) means that we move from node n first using dimension j and then dimension i.
The first lemma of this section proves that the sum of any subset of d-1 distances
corresponding to d-1 dimensions must be at least 2 d-1 -1.
Lemma 1: Let f d be an embedding with constant distances (D i , i-[0, d-1]) of a d-cube onto
a ring. Let V be any subset with d-1 of the dimensions of the d-cube, that is, V contains all the
dimensions of the d-cube excepting one. Then,
Proof: Let H(d,n,V) be the subset of nodes of a d-cube that consists of nodes n and N W (n) for
every W-V. Obviously, the number of elements in H(d,n,V) is two to the power of the number
of elements in V. In particular, if V has d-1 elements, then H(d,n,V) consists of 2 d-1 elements.
Given any set of 2 d-1 nodes of a ring, there will always be two nodes in this set whose distance is
at least 2 d-1 -1. Since it is possible to go from any node in H(d,n,V) to any other node in the same
set, using each dimension in V at most once, the distances corresponding to the dimensions in V
must add up to at least 2 d-1 -1. q
The next lemma states that if two distances are equal when embedding a d-cube onto a ring
then these distances must be equal to 2 d-2
Lemma 2: Let f d be an embedding with constant distances (D i , i-[0, d-1]) of a d-cube onto
a ring with 2 d nodes. If D i =D j =K (i - (in the following, x - n y means that x
n=d we will just write x - y).
Proof: Suppose the nodes of the ring are labeled clockwise from 0 to 2 d -1. Let us take any
node n of the hypercube and let (n). Suppose that D i =D j =K (i - j). Then, y= f d (N i (n)) is
equal to either (x+K) mod 2 d or (x-K) mod 2 d . For short we will write f d (N i (n))=(x-K) mod 2 d .
We have also that z=f d (N j (n), the only possible solution is
either y=(x+K) mod 2 d and z =(x-K) mod 2 d or y=(x-K) mod 2 d and z=(x+K) mod 2 d . Since both
situations are symmetrical, let us suppose the first one holds without loss of generality.
We have also that N j N i (n) is the same as N i N j (n). Let w=f d (N j N i (n)). Then w=(y+K) mod 2 d
(it cannot be equal to (y-K) mod 2 d since (y-K) mod 2 must be different). Since
w is also equal to f d (N i N j (n)), w=(z-K) mod 2 d . Therefore, y+K - z-K, that is, x+2K - x-2K. This
means that 4K - 0 which implies that K - d-2 0. Then K=k.2 d-2 for some integer k>0 (distances
must be positive integers). However, K cannot be a multiple of 2 d-1 because this would imply that
y=z. In consequence,
Given two nodes x and y of a ring we say that y is clockwise in relation to x if the
shortest path from x to y is clockwise. Otherwise we say that y is counterclockwise in relation to
x. Obviously, if y is clockwise in relation to x, then x is counterclockwise in relation to y.
d be an embedding with constant distances (D i , i-[0, d-1]) of a d-cube onto
a ring. Let us define that is, S (it stands for Short) is the set of
dimensions whose corresponding distances are less than 2 d-2 when a hypercube is embedded
onto a ring. Given any node n of the hypercube, we define
clockwise in relation to f d (n)} and is counterclockwise in relation
to f d (n)}. Obviously, C(n) -
Given any node, its neighbor in a given dimension of the hypercube is at a fixed distance in
the ring, but it can be clockwise or counterclockwise. The next two lemmas prove that, if we take
into account only those dimensions of the hypercube such that their corresponding D i are less
than 2 d-2 , there is always a node which has all its neighbors in those dimensions clockwise in the
ring (there is another node with all the neighbors in those dimensions being counterclockwise).
Lemma 3: Let f d be an embedding with constant distances (D i , i-[0, d-1]) of a d-cube onto
a ring with 2 d nodes. Let n be any node of the hypercube. Then, for any j - C(n), C(n) - {j} -
Proof: It is obvious that j - C(N j (n)) because N j N j
in relation to n then, N j N j is clockwise in relation to N j (n).
It only remains to be proved that for every k - C(n), k - C(N j (n)). Let suppose that there is
a k such that k - C(n), k - C(N j (n)). Assume that the nodes of the ring are labeled clockwise
from 0 to 2 d -1 and let x=f d (n). Since N j (n) is counterclockwise in relation to n, then f d (N j (n))
. By hypothesis N k N j (n) is counterclockwise in relation to N j (n), so f d (N k N j (n))
is clockwise in relation to n, then f d (N k (n)) =(x+D k ) mod 2 d and
. Because N k N j (n) and N j N k (n) are the same node, x-D j -D k -
This implies that either D j +D k - d-1 0 or D k - d-1 0; but none of these can hold since 0
the hypothesis was wrong and then k - C(N j (n)). q
Lemma 4: Let f d be an embedding with constant distances (D i , i-[0, d-1]) of a d-cube onto
a ring with 2 d nodes. Then, there is a node n of the hypercube such that
us an algorithm to find this node n. We can start from any node m of
the hypercube. If not, take any i - C(m) and move to N i (m). Lemma 3
states that the number of elements in C(N i (m)) is strictly less than the number of elements in
C(m). Repeating this step we will finally find a node n such that C(n)=-, that is,
From now on we will refer to the node designated by lemma 4 as node c of the hypercube.
The nodes of the ring can be labeled in the most convenient way for us. From now on, the node
f d (c) will be labeled as node 0, and the rest of the nodes of the ring will be labeled clockwise from
0 to 2 d -1. By the above lemma, f d (N i S. The next lemma states that for any
the neighbors of N i (c) in every dimension j - S - {i} are clockwise. Obviously, the
neighbor of N i (c) in dimension i is counterclockwise, since it is c.
Lemma 5: Let f d be an embedding with constant distances (D i , i-[0, d-1]) of a d-cube onto
a ring with 2 d nodes. Then, for any i - S, C(N i This is equivalent to say that
Proof: Suppose there is some j - S - {i} such that j - C(N i (c)). That means that
implies that either
. D i - d-1 D j , which is not possible because D i -D j (by lemma 2) and D i ,D j < 2 d-2 , or
. D j - d-1 0, which cannot hold since 0 < D j < 2 d-2 .
In consequence, for every j - S - {i}, j - C(N i (c)) and then C(N i
Next, it is proven that given any subset of dimensions W-S, the neighbors of N W (c) in every
are clockwise
Lemma d be an embedding with constant distances (D i , i-[0, d-1]) of a d-cube onto
a ring with 2 d nodes. Then, for any W - S, C(N W (c)) - S - W.
Proof: The lemma will be proved by induction over the number of elements in W.
If W has just one element the lemma holds (it has been proved in lemma 5, which can be seen
as a particular case of lemma 6).
Assume that the lemma holds for any set with less than N elements and let us suppose that it
does not hold for a set Wwith N elements. This means that there is a dimension k-S-W such that
f d (N k (N W (c))) is counterclockwise in relation to f d (N W (c)).
The fact that the lemma holds for any subset with less than N elements implies that
for any subset D-S with N elements. Therefore, since W has N elements
Let V be equal to the set W after taking any element of it and being replaced by k, that is, let
i-W be any element of W, then V=(W-{i}) - {k}. Since V has also N elements
f d N D c
f d N W c
f d N V c
We know that N k (N W
since N k is counterclockwise in relation to N W (c), then the left part of the equality must be equal
to (r-D k ) mod 2 d . The right part is equal to s-D i mod 2 d . In consequence, r-D k -s-D i .
Substituting r and s by their corresponding expressions and simplifying we obtain that
This equation can be satisfied just in two ways: either D k - d-1 0 or D i - d-1 D k .
None of them can hold since 0 < D i , D k < 2 d-2 , and as lemma 2 states, D i and D j cannot be equal.
We then conclude that for every k-S-W, f d (N k (N W (c))) is clockwise in relation to f d (N W (c))
and therefore, C(N W (c)) - S-W. q
Corollary 7: If we start from node c and we want to move to node N W (c) for any W-S, using
each dimension in W exactly once, any time we move through a dimension in W we will be
moving clockwise in the ring, no matter in which order we use the dimensions in W, that is,
Proof: It is a direct implication of lemmas 4 and 6. The former states that node c has all its
neighbors in S clockwise, so the first hop must be necessarily clockwise. Then lemma 6 says that
if we have moved from node c to a node r using a subset W of dimensions of S, making use of
each dimension just once, all the neighbors of node r in any dimension not used yet (i.e.
belonging to S-W) are clockwise, so the next hop must also be clockwise. q
Next, it is proven that, when embedding a hypercube onto a ring with constant distances, if
all distances are lower than 2 d-2 , the sum of all distances must be at least 2 d -1.
Lemma 8: Let f d be an embedding with constant distances (D i , i - [0, d-1]) of a d-cube onto
a ring with 2 d nodes such that every D i < 2 d-2 . If such embedding exists, then
Proof: Since all distances are less than 2 d-2 , S (set of dimensions whose distance is less than
consists of all dimensions of the d-cube. Then, lemma 4 states that there must be a node c
such that all its neighbors are clockwise. In addition, corollary 7 says that it is possible to go from
node c to any node of the hypercube given at most d hopes (each one corresponding to a different
dimension) and going always clockwise. In particular, we can go from node c to the node just
next to it counterclockwise. Moving always clockwise, the distance between these two nodes is
so the sum of all distances must be at least equal to this amount. q
Corollary 9: An embedding with constant distances such that all distances are less than 2 d-2
is not optimal, if it exists. In this context, to be optimal means that it has the lowest average
distance for embeddings with constant distances. In other words, the optimal embedding must
have at least one distance greater than or equal to 2 d-2 .
f d N W c
states that, if such embedding exists, then the sum of its distances is at least
To prove this corollary it suffices to find an embedding whose distances add up to less than
this amount. Such embedding can be the xor embedding, the one proposed in section 3. q
We are now ready to prove that the xor embedding is optimal. This is proved in the next
theorem and its corollary.
Theorem 10: Let f d be an embedding with constant distances (D i , i - [0, d-1]) of a d-cube
onto a ring with 2 d nodes. Then the average distance of f d is at least (3.2 d-2 -1)/d.
Proof: The proof is based on lemma 1 and corollary 9. The lemma says that the sum of any
subset of d-1 distances is at least 2 d-1 -1, so in particular, the sum of the d-1 lowest distances of
the embedding must be at least equal to this amount. Corollary 9 states that the optimal
embedding has at least one distance that is higher than or equal to 2 d-2 , so in particular, the
highest distance of the embedding must be higher than or equal to 2 d-2 Both together imply that
Corollary 11: The xor embedding of a d-cube onto a ring proposed in section 3 is optimal in
the sense that it has the lowest average distance for embeddings with constant distances.
Proof: The average distance of the xor embedding is equal to the lower bound introduced in
theorem 10. q
6. Conclusions
This paper focuses on the execution of algorithms with a hypercube communication topology
onto multicomputers with a torus interconnection topology. The problem is tackled by means of
graph embeddings. An embedding of hypercubes onto toruses of any arbitrary dimension has
been presented. This embedding, called xor embedding, belongs to a class of embeddings whose
distinguishing property is that all the links of the same dimension of the hypercube have the same
dilation on the torus. This class of embeddings are called embeddings with constant distances.
Many parallel algorithms with hypercube topology have the property that all the processes
perform the same activity with different data. This activity consists of a number of stages (usually
as many as number of dimensions of the hypercube) and each stage is composed of a computing
phase followed by a communication phase in which data is interchanged with one of its
neighbors. This structure is found in parallel algorithms for FFT and sorting among others. For
this type of algorithms, called CC d-cube algorithms, constant distances may be desirable
because they imply that the communication phase has the same duration for every process,
avoiding waiting intervals which can degrade performance.
averagedistance f d
The xor embedding has been compared to the standard embedding using a set of different
performance metrics (execution time of a CC d-cube algorithm, links dilation spectrum, longest
dilation, total dilation, maximum and minimum load, and average load). For all of them the
performance of the xor embedding is significantly better than that of the standard embedding.
For CC d-cube algorithms, the embedding with constant distances that results in the shortest
execution time is that whose average distance is minimum. It has been proven that the average
distance of the xor embedding is minimum for rings (one-dimensional torus), and therefore, it
maximizes the performance of the multicomputer for those algorithms.
Another important property of the xor embedding is the simplicity of the function which
determines the location where a node of the d-cube is found in the target multicomputer.
We are currently working on the generalization of this work in two different directions. First,
we are looking at more general hypercube algorithms. Second, we are considering more general
torus multicomputers in which the number of processing elements is not necessarily a power of
two.

Acknowledgments

This work has been supported by the Ministry of Education and Science of Spain (CICYT
TIC-92/880 and TIC-91/1036) and the CEPBA (European Center for Parallelism in Barcelona).



--R

"Multicomputers: Message-Passing Concurrent Computers"
" Embedding Networks with Ring Connections in Hypercube Machines"
Solving Problems on Concurrent Processors
"The Xor Embedding: Embedding Hypercubes onto Rings and Toruses"
"Optimal Assignments of Numbers to Vertices"
"Optimal Numbering and Isoperimetric Problems on Graphs"
" Embedding Three-Dimensional Meshes in Boolean Cubes by Graph Decomposition"
"Placement of the Processors of a Hypercube"
"Embeddings among Meshes and Tori"
"Emulation of Hypercube Architecture on Nearest-Neighbor Mesh-Connected Processing Elements"
" Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes"
" Contention-Free 2D-Mesh Cluster Allocation in Hypercubes"
Interconnection Networks for Multiprocessors and Multicomputers: Theory and Practice
--TR

--CTR
Mikhail S. Tarkov , Youngsong Mun , Jaeyoung Choi , Hyung-Il Choi, Mapping adaptive fuzzy Kohonen clustering network onto distributed image processing system, Parallel Computing, v.28 n.9, p.1239-1256, September 2002
Luis Daz de Cerio , Miguel Valero-Garca , Antonio Gonzlez, Hypercube Algorithms on Mesh Connected Multicomputers, IEEE Transactions on Parallel and Distributed Systems, v.13 n.12, p.1247-1260, December 2002
Otto Wohlmuth , Friedrich Mayer-Lindenberg, A method for them embedding of arbitrary communication topologies into configurable parallel computers, Proceedings of the 1998 ACM symposium on Applied Computing, p.569-574, February 27-March 01, 1998, Atlanta, Georgia, United States
Ali Karci, Generalized parallel divide and conquer on 3D mesh and torus, Journal of Systems Architecture: the EUROMICRO Journal, v.51 n.5, p.281-295, May 2005
graph embeddings;torus multicomputers;hypercubes;mapping of parallel algorithms;scalable distributed memory multiprocessors