Algebraic Foundations and Broadcasting Algorithms for Wormhole-Routed All-Port Tori.
AbstractThe one-to-all broadcast is the most primary collective communication pattern in a multicomputer network. We consider this problem in a wormhole-routed torus which uses the all-port and dimension-ordered routing model. We derive our routing algorithms based on the concept of span of vector spaces in linear algebra. For instance, in a 3D torus, the nodes receiving the broadcast message will be spanned from the source node to a line of nodes, to a plane of nodes, and then to a cube of nodes. Our results require at most $2(k-1)$ steps more than the optimal number of steps for any square $k$-D torus. Existing results, as compared to ours, can only be applied to tori of very restricted dimensions or sizes and either rely on an undesirable non-dimension-ordered routing or require more numbers of steps.
Introduction
One-to-all broadcast is an essential communication
operator in multicomputer networks, which has many
applications, such as algebraic problems, barrier syn-
chronization, parallel graph and matrix algorithms,
cache coherence in distributed-share-memory systems,
and data re-distribution in HPF. Wormhole routing
[1, 4] is characterized with low communication latency
due to its pipelined nature and is quite insensitive
to routing distance in the absence of link contention.
Machines adopting such technology include the Intel
Touchstone DELTA, Intel Paragon, MIT J-machine,
Caltech MOSAIC, nCUBE 3, and Cray T3D and T3E.
In this paper, we study the scheduling of message
distribution for one-to-all broadcast in a wormhole-
This work is supported by the National Science Council of
the Republic of China under Grant # NSC87-2213-E-008-012
and #NSC87-2213-E-008-016.
routed torus, which type of architecture has been
adopted by parallel machines such as Cray T3D and
T3E (3-D tori). The network is assumed to use the
all-port model 1 and the popular dimension-ordered
routing. Following the formulation in many works
[2, 6, 8, 10, 12, 13], this is achieved by constructing
a sequence of steps, where a step consists of a set of
communication paths each indicating a
message delivery. The goal is to minimize the total
number of steps used.
The same problem has been studied in several works.
In [9, 10], schedules following the dimension-ordered
routing are proposed for 2-D 2 n \Theta 2 n and 3-D 2 n \Theta 2 n \Theta z
tori using n and respectively, where
. The numbers of steps used
are at least log 4 5 and log 6 7 times, i.e., about 16% and
8.6% more than, the optimal numbers of steps, respectively
(refer to the lower bounds in Lemma 1). A schedule
using the optimal number of steps is proposed in [8]
for any 2-D torus of size 5 p \Theta 5 p or (2 \Theta 5 p ) \Theta (2 \Theta 5 p ),
where p is any integer. The works in [6, 7] remain op-
timal, but can be applied to any square k-D torus with
nodes on each side. However, the disadvantages
of [6, 7, 8] include : (i) the tori must be square,
(ii) very few network sizes are solvable (e.g., for 2-D
tori, the possible sizes are 5 \Theta 5, 10 \Theta 10, 25 \Theta 25,
50 \Theta 50, 125 \Theta 125, 250 \Theta 250, etc.), and (iii) the routing
is not dimension-ordered (we comment that unfortunately
most current torus machines use dimension-
ordered routing). These drawbacks would greatly limit
the applicability of [6, 7, 8]. Generalization to tori supporting
multi-port capability is shown in [3]; however,
the routing is still non-dimension-ordered. Recently,
these deficiencies were eliminated by [11], which can
1 The reverse of this is the one-port model, in which case the
broadcast problem can be trivially solved by a recursive-doubling
technique.
be applied to 2-D tori of any size using dimension-
ordered routing; at most 2 (resp., 5) communication
steps more than the optimum are required when the
torus is square (resp., non-square). However, it still remains
as an open problem how to extend this scheme
to higher-dimensional tori.
One interesting technique used in [11] is the concept
of diagonal in a 2-D torus. In this paper, we extend
the work of [11] and show how to perform one-to-all
broadcast in a torus of any dimension. For practical
consideration, the routing should still follow the
dimension-ordered restriction. The extension turns out
to need some mathematical foundations when higher-dimensional
tori are considered. Our schemes are based
on the concept of "span of vector spaces" in linear al-
gebra. For instance, in a 3-D torus, the nodes receiving
the broadcast message will be "spanned" from the
source node to a line of nodes, to a plane of nodes,
and then to a cube of nodes. We develop the algebraic
foundations to solve this problem for any k-D torus of
size n on each dimension. Our results require at most
more than any optimal scheduling. Existing
results, as compared to ours, can only be applied
to tori of very restricted dimensions or sizes, and either
rely on an undesirable non-dimension-ordered routing
or require more numbers of steps.
2. Preliminaries
A k-D torus of size n is an undirected graph denoted
as Tn\Theta\Delta\Delta\Delta\Thetan . Each node is denoted as p x1;x2
Each node is of degree
2k. Node p x1 ;x2 has an edge connecting to
along dimension one, an edge to
along dimension two, and so on.
(Hereafter, we will omit saying "mod n" whenever the
context is clear.)
We will map the torus into an Euclidean integer
space Z k . Note that instead of being the normal integer
set, Z is in the domain f0; 1g. A node
in the torus can be regarded as a point
. A vector in Z k is a k-tuple
As a convention, the i-th positive
negative) elementary vector ~e i (resp., ~e \Gammai ) of Z k ,
1::k, is the one with all entries being 0, except the
i-th entry being 1 (resp., \Gamma1). We may write ~e i 1
as
, and similarly
. For instance, ~e
and ~e . The linear combination of vectors
(say a 1 are integers) follows
directly from the typical definition of vector addition,
except that a "mod n" operation is implicitly applied.
In Z k , given a node x, an m-tuple of
vectors and an m-tuple of integers
the span of x by
vectors B and distances N as
a i ~
Note that the above definition is different from the
typical definition of SPAN in linear algebra [5]. The
main purpose here is to identify a portion of the
torus. For instances, the main diagonals of Tn\Thetan
and Tn\Thetan\Thetan can be written as SPAN(p 0;0 ; (~e 1;2 ); (n))
and SPAN(p 0;0;0 ; (~e 1;2;3 ); (n)), respectively; an XY -
plane passing node p 0;0;i in Tn\Thetan\Thetan can be written as
In the one-to-all broadcast problem, a source node
needs to send a message to the rest of the network.
The all-port model will be assumed, in which a node
can simultaneously send and receive messages along all
outgoing and incoming channels. Since the node degree
is 2k, in the best case one may multiply the number of
nodes owning the broadcast message by 2k
each step. This leads to the following lemma.
Lemma 1 In a k-D all-port torus Tn\Theta\Delta\Delta\Delta\Thetan , a lower
bound on the number of steps to achieve one-to-all
broadcast is dlog 2k+1 n k e.
3. Broadcasting in 2-D Tori
In this section, we review the broadcasting scheme
for 2-D tori in [11]. This will be helpful to understand
our algorithms for higher-dimensional tori later. Consider
any 2-D torus Tn\Thetan . As the network is symmetric,
we let, without loss of generality, the source node be
We denote by M the message to be broadcast.
The scheme is derived in two stages.
Stage 1: In this stage, message M will be sent to
the main diagonal, SPAN(p 0;0 ,(~e 1;2 ); (n)). This is
achieved by two parts.
Stage 1.1 (Distribution): In this part, M will be
recursively distributed to one of the nodes in each row.
For easy of representation, let 5t. First, we regard
0;0 as the center of the torus and horizontally and
evenly slice the torus into five strips. In one step, we
let p 0;0 send four copies of M to nodes p 0;\Gamma2t , p \Gammat;\Gammat ,
. The above five nodes are located at the
center rows of the five strips and the routing is clearly
congestion-free, as illustrated in Fig. 1(a). Then, by
regarding these five nodes as the source node of the
five strips, we can recursively send M to more rows.
Fig. 1(b) illustrates the routing in the second step. This
is repeated until the height of each strip reduces to
one or zero. At the end, along each row in the torus,

Figure

1. Stage 1.1 of broadcast in a 2-D torus:
(a) the first step, and (b) the second step.

Figure

2. Stage 2 of broadcast in a 2-D torus:
(a) the first step, and (b) the second step.
Note that for clarity only typical communication
paths are shown.
exactly one node will have received M . Overall, this
stage takes dlog 5 ne steps to complete.
Stage 1.2 (Alignment): For each node p i;j holding
message M , p i;j sends M along the first dimension to
all nodes on the main diagonal will
own M . This requires only one step.
Stage 2: In this stage, the torus is viewed as n diagonals
We evenly partition the torus into 5 strips S
\Gamma2::2 each contains t diagonals. This is illustrated in
Fig. 2(a).
In the first step, M will be sent to 4 other diagonals
. This can be done by having
each node p i;i in L 0 send M to nodes p i\Gamma2t;i , p i;i+t ,
. The communication, as illustrated
in Fig. 2(a), is clearly congestion-free.
In the second step, we can regard the diagonal L it
as the source of strip S i , recursively
perform the above diagonal-to-diagonal message distribution
in S i . (refer to Fig. 2(b)). The recursion
terminates when each strips contains one or zero di-
agonal. This stage takes dlog 5 ne steps to complete.
Hence, broadcast can be done in 2dlog 5 ne
which number of steps is at most 2 steps more than
the lower bound in Lemma 1.
4. Broadcasting in 3-D Tori
Now we develop our algorithm for a Tn\Thetan\Thetan with
any n. Without loss of generality, let p 0;0;0 be the
source node. The basic idea is to distribute the broadcast
message M in three stages: (i) from p 0;0;0 to a
line SPAN(p 0;0;0 ; (~e 1;3 ); (n)), (ii) from the above line
to a plane SPAN(p 0;0;0 ; (~e 1;3 ; ~e 1;2 ); (n; n)), and then
(iii) from the above plane to the whole torus. These
stages will use dlog 7 ne ne ne
steps, respectively. For simplicity, we may use X-, Y -
, and Z-axes to refer to the first, second, and third
dimensions, respectively.
4.1. Stage 1: From the Source Node to a Line
Again, this stage is divided into two parts. In
the first part, M will be distributed to one representative
node on each of the n XY -planes. In
the second part, M will be forwarded to the line
4.1.1 Stage 1.1 (Distribution)
For simplicity, let n be a multiple of 7, 7t. We
view the torus as consisting of the following
planes
We then partition the torus horizontally into 7 cubes
\Gamma3::3, such that the first cube consists of the
first t XY -planes in Eq. (2), the second cube the next
t XY -planes, etc. Let's identify the following nodes:
In one step, node m 0 can forward M to m
congestion. The communication
paths are illustrated in Fig. 3(a).
Now, observe that each m i is located at the central
XY -plane of the cube C \Gamma3::3. So we can regard
as the source of C i and recursively perform
broadcasting in C i , until each cube reduces to only one

Figure

3. Stage 1.1 of broadcast in a 3-D torus:
(a) the first step, and (b) the second step.
or zero XY -plane. The second step is illustrated in
Fig. 3(b).
At this point, we would introduce some notations to
our later presentation.
Consider a k-D torus. A routing matrix
is a matrix with entries \Gamma1; 0, or 1 such
that each row indicates a message delivery; if r
(resp. \Gamma1), the corresponding message will travel along
the positive (resp. negative) direction of dimension j;
if r the message will not travel along dimension
j. A distance matrix is an integer
diagonal matrix (all non-diagonal elements are 0); d i;i
represents the distance to be traveled by the i-th message
described in R along each dimension.
For instance, the six message deliveries in Fig. 3(a)
have three directions and thus can be represented by a
routing matrix:
~e 2;3
~e
In general, the six nodes receiving M are
(note that ff \Sigmai - \Sigma in
deriving ff \Sigmai ). So we can use two distance matrices:
and represent the 6 message deliveries in Fig. 3(a) by
matrix multiplication:
where each row represents one routing path.
4.1.2 Stage 1.2 (Alignment)
The goal is to "align" the nodes receiving M to the line
(n)). This can be done in one step
by having every p x;y;z holding M send to p z;0;z along

Figure

4. Stage 2 of broadcast in a 3-D
torus: (a) viewing the torus from the perspective
partitioning the torus into 7 cubes C
\Gamma3::3. Stage 3 of broadcast in a 3D torus:
(c) viewing the torus from the perspective
(d) partitioning the torus into 7 cubes C
\Gamma3::3.
the path . This is congestion-free
as communications only happen in individual XY -
planes.
4.2. Stage 2: From a Line to a Plane
In this stage, we will view the torus from a different
perspective:
Fig. 4(a) for an illustration. With this view, we
partition the network along the direction ~e 1 into the following
The message M will be sent from the line
lines, each
spanned along the same direction ~e 1;3 but located on a
different plane in Eq. (6). Finally, we will align these
lines to a plane SPAN(p 0;0;0 ; (~e 1;3 ; ~e 1;2 ); (n; n)).
It is easy to send messages from a line of
nodes to another parallel line in one communication
step. For instance, to deliver messages
from line SPAN(p 0;0;0 ; (~e 1;3 ); (n)) to line
simply let each p i;0;i (of
the former line) send to p i+2;3;i+4 (of the latter line).
One can easily generalize this to a line sending to six
other parallel lines in one step.
4.2.1 Stage 2.1 (Distribution)
This stage is based on a recursive structure as follows.
For simplicity, let 7t. We partition the torus into 7

Figure

5. Stage 2 of broadcast in a 3-D torus:
(a) the first step, and (b) the second step.
cubes \Gamma3::3, such that C \Gamma3 consists of the first
t planes in Eq. (6), C \Gamma2 the next t planes, etc. (refer
to Fig. 4(b)).
be the line already
owning M . By having each p i;0;i 2 L 0 send M
to the following six nodes:
we can distribute M to six other lines in one step:
This communication step, as illustrated in Fig. 5(a), is
congestion-free. The resulting line L it is on the central
plane of C i for all To see this, let's prove
the case of L 2t :
which is indeed the central plane of C 2 . The other
cases can be proved similarly. The routing matrix can
be written as:
Using the distance matrices in Eq. (4), the six routing
paths in Fig. 5(a) can be described by the six rows in
Next, we can recursively perform the similar line-
to-line distribution in each C i using L it as the source.
The next step is shown in Fig. 5(b).
4.2.2 Stage 2.2 (Alignment)
From stage 2.1, on each plane
line owns M .
The goal is to "align" these n lines to the plane
n)). This can be done by
having each node 2 L send M along the second dimension
by hops, which is obviously congestion-free.
This will forward M to the lines
lines constitute the
plane Only one step
is used in this stage.
4.3. Stage 3: From a Plane to More Planes
In this stage, we view the torus from another perspective

which is illustrated in Fig. 4(c). With this view, we
partition the torus along the direction ~e 1 into n planes
For simplicity, let 7t. Following the same philosophy
as before, we divide the torus into 7 cubes
\Gamma3::3, such as the first cube consists of the
first t planes, the second cube the next t planes, etc.
This is shown in Fig. 4(d).
The central plane in Eq. (8) already owns message
M . In this stage, plane-to-plane message distribution
will be performed. For instance, if every node on plane
sends M along the Y -
and Z-axes to nodes that are +3 and +5 hops way,
respectively, then two planes will receive
which are \Gamma3 and \Gamma5 planes next to the source plane.
Specifically, we will use the routing matrix:
The distance D + and D \Gamma remain the same. The resulting
6 routing paths can be represented by the 6 rows
in the following matrices:
// the next t planes
// the next 2t planes
// the next 3t planes
// the next \Gammat planes
// the next \Gamma2t planes
// the next \Gamma3t planes
Now we have 7 planes owning M on the centers of the
cubes so the recursion can be proceeded,
until each C i reduces to one or zero plane. Totally
dlog 7 ne steps will be used in this stage.
Theorem 1 In a 3-D Tn\Thetan\Thetan torus with dimension-
ordered routing and all-port capability, broadcast can be
done in 3dlog 7 ne which number of steps is
at most 4 steps more than optimum.
5. Broadcasting in k-D Tori
In this section, we extend our broadcasting algorithm
to a k-D Tn\Theta\Delta\Delta\Delta\Thetan torus. Following the same
philosophy as before, broadcasting in Z k (a k-D torus)
will be achieved by distributing the broadcast message
M in k stages: from the source to a line, from a line to
a plane, from a plane to a cube, from a cube to a 4-D
cube, etc. In the following, we discuss in general how
stage 1::k. Still, this has two parts: distribution
and alignment. Throughout this section, we
0;:::;0 be the source node and N i be a vector
of length i equal to (n;
5.1. Distribution Sub-stage
First, we need to define the set of nodes receiving
the broadcast message after stage i.
Definition 3 The set of nodes receiving message M
after stage i is defined to be:
The number of nodes in U i is n times that of U
Also, we can think of U i as n copies of U expanding
along the vector ~e 1;k\Gammai+1 , i.e.,
where a vector ~v plus a set of nodes S (~v + S) means
a "translation" operation which moves each node of
S to a node relative to the former by a vector of ~v.
The following lemma guarantees that M will really be
received by all nodes after stage k.
The
being selected is to insure the following
two lemmas, which are important later to guarantee
our routing to be congestion-free. The following two
lemmas can be simply proved by the Gaussian Elimination
method.
Lemma 3 For any i and j such that 1 -
the union
of\Omega i and the vector ~e j is
linearly independent.
Lemma 4 For any
of\Omega i and
is linearly independent.

Figure

6. Partitioning V i along ~s i into a "super
linear path".
To expand U i\Gamma1 to U i , we need to view the torus
from a different perspective defined as follows.
Definition 4 In stage i, we view the torus as:
where
~
(Here "\Delta" means the concatenation of two sequences.)
The earlier perspectives Fig. 3(a), Fig. 4(a) and (c)
of a 3-D torus are derived based on this formula. The
above perspective provides us a way to partition the
torus. As we have seen earlier, partitioning is used to
solve our problem in a recursive manner.
Definition 5 In stage i, V i is partitioned along direction
~s i into the following n sub-networks (j =
\Gammab
The partitioning is illustrated in Fig. 6. Examples of
such partitioning of a 3-D torus at different stages can
be seen in Fig. 3(b), Fig. 4(b) and (d). We can imagine
j as a "super-node" which is connected through a
vector ~s i to two "super-nodes" W i
j+1 in a
wrap-around manner. So these super-nodes actually
form a "super linear path" of length n. Also note that
U (which already has the message M) is resident
in the central super-node W i
0 . In the distribution sub-
stage, we try to send M from W i
0 to the other
1 super-nodes; the sets of nodes receiving M in each
super-node will have a shape "isomorphic" to U i\Gamma1 .
This is done based on the following recursive structure:
(i) partition the linear path into 2k
send M to a representative super-node in each segment,
and then (iii) perform the distribution in each segment
recursively.
Given a segment of super-nodes of length m, we use
a routing matrix and two distance matrices to describe
the routing in one recursive step.
Definition 6 In stage i, the routing matrix is a k \Theta k
matrix defined as:
~e 1;k
~e 2;k
~e k\Gamma1;k
~e 2;\Gammak
~e k\Gammai+1;\Gammak
\Gamma~e k\Gammai+2
I k\Gammai+1
Definition 7 In stage i, given a segment of super-nodes
of length m, the distance matrices with respect
to m are (intuitively, ff \Sigmai - \Sigma im
are derived in [14]):
ff \Gamma2 ~e 2
\Gammam
Using these matrices, the intuitive meanings of routing
paths in one recursive step can be described by the 2k
rows through the following matrix multiplication:
m \Theta R i
routing paths to W i
routing paths to W i
routing paths to W i
routing paths to W i
m \Theta R i
routing paths to W i
routing paths to W i
ff \Gamma2 (ff \Gamma2 - \Gamma2m
routing paths to W i
ff \Gamma3
routing paths to W i
ff \Gammak (ff \Gammak - \Gammakm
Consider the first communication step where U
(resident in W i
following the second row of
(which is equal to ff 2 ~e 2;\Gammak ). Then, the message
M will be sent to:
The meanings of routing paths in the other rows can
be proved similarly, so we omit the details.

Figure

7. Aligning S to S 0 in W i
d .
Lemma 5 [14]In the distribution sub-stage of stage i,
each communication step is congestion-free.
5.2. Alignment Sub-stage
Now each super-node W i
already has a
set of nodes (of shape isomorphic to U
The next job is to align these n sets to form U i . In the
following, we show the routing in W i
d . Suppose the set
of nodes owning M after the distribution sub-stage in
d is S. As S is isomorphic to U i\Gamma1 , we can write S
as (v 1 Also, recall that U i consists
of n copies U spanned along direction
~e 1;k\Gammai+1 . So the set of nodes that we expect to own
M in W i
d should be S (see the
illustration in Fig. 7).
is no need of alignment. Otherwise, some alignment
may be necessary. Intuitively, if we take a difference of
these two vectors:
then the resulting vector can be used to represent the
routing paths leading S to S 0 . However, such a routing
may not be congestion-free. The following lemma
shows that S in fact can be rewritten in a different
form.
Lemma 6
d)   U
where   means a "don't care''.
Using the new form in Lemma 6, we perform the
following subtractions:
The resulting vectors indicate how to align S to S 0 .
the alignment may go along dimensions
(by observing the locations where  's
appear in Eq. (12)). As ~e 1 the routing
only happens inside W 1
d . Thus, we only need to
prove that the routing for the alignment inside individual
d 's is congestion-free. The proof is similar to
that of Lemma 5, so we omit the details. Similarly,
the alignment may go along dimensions
(by observing the locations where  's
appear in Eq. (13)). As ~e , the
routing only happens inside W i
d .
Also note that when reduces to a zero
vector, which means no need of alignment sub-stage in
stage k. This leads to the following theorem.
Theorem 2 In a k-D Tn\Theta\Delta\Delta\Delta\Thetan torus with dimension-
ordered routing and all-port capability, broadcast can
be done in kdlog 2k+1 ne which number of
steps is at most 2(k \Gamma 1) steps more than optimum.
6. Conclusions
We compare our scheme for 3-D tori against two
other known schemes: (i) Tsai and McKinley [10],
which works for T 2 d \Theta2 d \Thetaz and requires d+1 or d+m+2
steps when 2 - z - 7 or 7 \Theta 6 m
respectively, and (ii) Park et al. [6, 7], which works for
steps. In Fig. 8, we draw the
numbers of communication steps required by these and
our schemes in a Tn\Thetan\Thetan torus.
We make the following observations. First, in terms
of the numbers of steps uses, the Park scheme is the
best and always coincides with the lower bound; the
TM scheme is better than ours when n is small, but is
outperformed by ours as n becomes larger. Second, in
terms of network sizes allowed, ours has the broadest
applicability because any n is allowed; the TM and the
Park schemes have quite limited applicability, and the
situation is getting worse especially when n becomes
larger. Third, in terms of communication capability,
both TM and our schemes assume a dimension-ordered
routing, while the Park scheme assumes a stronger non-
dimension-ordered routing.
We are currently trying to extend our result to other
port models such as [3].



--R

The torus routing chip.
Optimal broadcasting in all-port wormhole-routed hypercubes
Optimal broadcast in ff-port wormhole-routed mesh networks
A survey of wormhole routing techniques in directed network.
Linear Algebra with Applications.



A broadcasting algorithm for all-port wormhole-routed torus networks
A broadcasting algorithm for all-port wormhole-routed torus networks
A dilated-diagonal-based scheme for broadcast in a wormhole-routed 2d torus


Algebraic foundations and broadcasting algorithms for wormhole-routed tori
--TR

--CTR
Xiaotong Zhuang , Vincenzo Liberatore, A Recursion-Based Broadcast Paradigm in Wormhole Routed Networks, IEEE Transactions on Parallel and Distributed Systems, v.16 n.11, p.1034-1052, November 2005
Olivier Beaumont , Arnaud Legrand , Loris Marchal , Yves Robert, Pipelining Broadcasts on Heterogeneous Platforms, IEEE Transactions on Parallel and Distributed Systems, v.16 n.4, p.300-313, April 2005
Yuanyuan Yang, A New Conference Network for Group Communication, IEEE Transactions on Computers, v.51 n.9, p.995-1010, September 2002
Yuh-Shyan Chen , Chao-Yu Chiang , Che-Yi Chen, Multi-node broadcasting in all-ported 3-D wormhole-routed torus using an aggregation-then-distribution strategy, Journal of Systems Architecture: the EUROMICRO Journal, v.50 n.9, p.575-589, September 2004
San-Yuan Wang , Yu-Chee Tseng , Sze-Yao Ni , Jang-Ping Sheu, Circuit-Switched Broadcasting in Multi-Port Multi-Dimensional Torus Networks, The Journal of Supercomputing, v.20 n.3, p.217-241, November 2001
torus;wormhole routing;interconnection network;one-to-all broadcast;parallel processing;collective communication