A Theory for Total Exchange in Multidimensional Interconnection Networks.
AbstractTotal exchange (or multiscattering) is one of the important collective communication problems in multiprocessor interconnection networks. It involves the dissemination of distinct messages from every node to every other node. We present a novel theory for solving the problem in any multidimensional (cartesian product) network. These networks have been adopted as cost-effective interconnection structures for distributed-memory multiprocessors. We construct a general algorithm for single-port networks and provide conditions under which it behaves optimally. It is seen that many of the popular topologies, including hypercubes, k-ary n-cubes, and general tori satisfy these conditions. The algorithm is also extended to homogeneous networks with 2k dimensions and with multiport capabilities. Optimality conditions are also given for this model. In the course of our analysis, we also derive a formula for the average distance of nodes in multidimensional networks; it can be used to obtain almost closed-form results for many interesting networks.
Introduction
Multidimensional (or cartesian product) networks have prevailed the interconnection network design
for distributed memory multiprocessors both in theory and in practice. Commercial machines
like the Ncube, the Cray T3D, the Intel iPSC, Delta and Paragon, have a node interconnection
structure based on multidimensional networks such as hypercubes, tori and meshes. These networks
are based on simple basic dimensions: linear arrays in meshes [15], rings in k-ary n-cubes
[6] and general tori, complete graphs in generalized hypercubes [4]. Structures with quite powerful
dimensions have also been proposed, e.g. products of trees or products of graphs based on groups
[21, 9].
One important issue related to multiprocessor interconnection networks is that of information
dissemination. Collective communications for distributed-memory multiprocessors have recently
received considerable attention, as for example is evident from their inclusion in the Message
Passing Interface standard [18] and from their support of various constructs in High Performance
Fortran [12, 16]. This is easily justified by their frequent appearance in parallel numerical algorithms
[11, 13, 3].
Broadcasting, scattering, gathering, multinode broadcasting and total exchange constitute a
set of representative collective communication problems that have to be efficiently solved in order
to maximize the performance of message-passing parallel programs. A general survey regarding
such communications was given in [10]. In total exchange, which is also known as multiscattering
or all-to-all personalized communication, each node in a network has distinct messages to send
to all the other nodes. Various data permutations occurring e.g. in parallel FFT and basic linear
algebra algorithms can be viewed as instances of the total exchange problem [3].
The subject of this work is the development of a general theory for solving the total exchange
problem in multidimensional networks. A multitude of quantities or properties in such networks
can be decomposed to quantities and properties of the individual dimensions. For example, the
degree of a node is the sum of the degrees in each of the dimensions. We show here that the total
exchange problem can also be decomposed to the simpler problem of performing total exchange in
single dimensions. This is a major simplification to an inherently complex problem for inherently
complex networks. We provide general algorithms applicable to any multidimensional network
A Theory for Total Exchange in Multidimensional Interconnection Networks
given that we have total exchange algorithms for each dimension. Optimality conditions are given
and it is seen that they are met for many popular networks, e.g. hypercubes, tori and generalized
hypercubes to name a few.
The results presented here apply to packet-switched networks that follow the so-called constant
model [10]. The assumptions pertaining the model we will follow are:
ffl communication links are bidirectional and fully duplex
ffl a message requires one time unit (or step) to be transferred between two nodes
ffl only adjacent nodes can exchange messages.
Another parameter of the model is that of port capabilities. Depending on whether a node can
communicate with one or all of its neighbors at the same time unit, two basic possibilities arise:
Single-port: a node can send at most one message and receive at most one message at each step.
Multiport: a node can send and receive messages from all its neighbors simultaneously.
As discussed in [10], the above assumptions constitute the standard model when examining theoretical
aspects of communications in packet-switched networks. Furthermore, results and conclusions
under this model can form the basis of arguments for other models, such as the linear
one which also quantifies the effect of message lengths. Many recent works focus exclusively on
wormhole-routed networks (an excellent survey on collective communications for such machines
was given in [17]). However, we believe that studies should not be limited to one particular type of
architecture: "it is important to consider several types of communication models, given the broad
variety of present and future communication hardware" [2]. In addition, since a circuit-switched
or wormhole routed network can emulate a packet-switched network by performing only nearest-neighbor
communications, the results also constitute a reference point for methods developed for
the former type of networks.
Algorithms to solve the total exchange problem for specific networks and under a variety
of assumptions have appeared in many recent works, mostly concentrating in hypercubes and
two-dimensional tori (e.g. [22, 14, 2, 23]). Under the single-port model we know of two optimal
algorithms, in [3, pp. 81-83] for hypercubes, and in [19] for star graphs. In contrast, our results
are applicable not only to one particular structure but rather provide a general procedure for
solving the problem in any multidimensional network.
2. Multidimensional Networks 3
This paper is organized as follows. We introduce formally multidimensional networks in the
next section and we give some of their properties related to our study. Section 3 gives lower
bounds on the time required for solving the total exchange problem under both port assumptions.
In the same section we derive a new formula for the single-port bound as applied to the networks
of interest. The result has its own merit as it also provides almost closed-form formulas for the
average distance in networks for which no such formula was known up to now. In Section 4 we
concentrate on single-port networks. We develop a total exchange algorithm and we give conditions
under which it behaves optimally. We also review known results about simple dimensions and
conclude that our method can be optimally applied to hypercubes, k-ary n-cubes and other
popular interconnects. In Section 5 we modify the algorithm and adapt it to the multiport model.
The extension works for networks which have dimensions (homogeneous
networks). Again, we provide optimality conditions and observe that they are satisfied for a
number of interesting topologies. The results are summarized in Section 6.
2. Multidimensional Networks
E) be an undirected graph 1 [5] with node (or vertex) set V and edge (or link) set
E. This is the usual model of representing a multiprocessor interconnection network: processors
correspond to nodes and communication links correspond to edges in the graph. The number of
nodes in G is An edge in E between nodes v and u is written as the unordered pair
(v; u) and v and u are said to be adjacent to each other, or just neighbors.
A path in G from node v to node u, denoted as v ! u, is a sequence of nodes
u, such that all vertices are distinct and for all We say that the length
of a path is ' if it contains ' vertices apart from v. The distance, dist(v; u), between vertices v
and u is the length of a shortest path between v and u. Finally, the eccentricity of v, e(v), is the
distance to a node farthest from v, i.e.
The maximum eccentricity in G is known as the diameter of G.
1 The terms 'graph' and `network' are considered synonymous here.
4 A Theory for Total Exchange in Multidimensional Interconnection Networks
a b

Figure

1. Cartesian product of two graphs
Given k graphs G product is defined as the graph
E) whose vertices are labeled by a k-tuple (v
We will call such products of graphs multidimensional graphs and G i will be called the ith
dimension of the product. The ith component of the address tuple of a node will be called the
ith address digit or the ith coordinate. The definition of E above in simple words states that two
nodes are adjacent if they differ in exactly one address digit. Their differing coordinates should
be adjacent in the corresponding dimension. An example is given in Fig. 1. Dimension 1 is a
graph consisting of a two-node path with consists of a three-node
ring with 3g. Their product has node set
(a; 1); (a; 2); (a; 3); (b; 1); (b; 2); (b;
According to the definition, node (a; 1) has the following neighbors: since node a is adjacent to
node b in the first dimension, node (a; 1) will be adjacent to node (b; 1); since node 1 is adjacent
to both nodes 2 and 3 in the second dimension, node (a; 1) will also be adjacent to nodes (a; 2)
and (a; 3).
Hypercubes are products of two-node linear arrays (or rings), tori are products of rings. If
all dimensions of the torus consist of the same ring, we obtain k-ary n-cubes [6]. Meshes are
products of linear arrays [15]. Generalized hypercubes are products of complete graphs [4]. If all
dimensions G i , are identical then the network is characterized as homogeneous.
3. Lower Bounds for Total Exchange 5
Multidimensional graphs have is the number of nodes in
k. It is also known that if dist i (v is the distance between v i and u i in G i
then the distance between
dist
It will be convenient to use the don't care symbol `\Lambda' as a shorthand notation for a set of
addresses. An appearance of this symbol at an element of an address tuple represents all legal values
of this element. In the previous example, (a;
while denotes the whole node set of the graph.
3. Lower Bounds for Total Exchange
In the total exchange problem, a node v has to send messages, one for each of the
other nodes in an n-node network. Let us first assume that the single-port model is in effect. If
there exist n d nodes in distance d from v, where then the messages sent by v
must cross
links in total. For all messages to be exchanged, the total number of link traversals must be
The quantity s(v) is known as the total distance or the status [5] of node v.
Every time a message is communicated between adjacent nodes one link traversal occurs.
Under the single-port model nodes are allowed to transmit only one message per step, so that the
maximum number of link traversals in a single step is at most n. Consequently, we can at best
subtract n units from SG in each step, so that a lower bound on total exchange time is
In other words, total exchange under the single-port assumption requires time bounded below by
the average status, AS(G), of the vertices.
6 A Theory for Total Exchange in Multidimensional Interconnection Networks
For multiport networks tighter bounds are obtained through cuts of the network. Partition
the vertex set V in two disjoint sets V 1 and V 2 such that
be the number
of edges in E joining the two parts, i.e. edges
from nodes in V 1 destined for nodes in V 2 must cross these C V1 V2 edges. The total number of
such messages is jV 1 jjV 2 j. Since only C V1V2 messages are able to pass from V 1 to V 2 at a time, we
obtain the following lower bound for total exchange time:
We are of course interested in maximizing the fraction in the right-hand side by selecting V 1 and
appropriately so that the tightest possible bound results. In many cases a bisection of the graph
is the most appropriate choice, although any sensible partition will yield quite tight bounds.
3.1. Status in multidimensional networks
In the course of our analysis on the single-port model we will need to compare the time needed
for total exchange with the lower bound of (3). We present here a formula for the status and the
average status of vertices in multidimensional graphs, as required by (3). The results are based
on the status of vertices in individual dimensions.
Theorem 1 Let is the status of v i in G i ,
the status of
Proof. The status of node v can be calculated through (2) or by using the equivalent formula:
where dist(v; u) is the distance between v and u. Hence, the status of v i in G i can be written as
dist
3. Lower Bounds for Total Exchange 7
We know that in a multidimensional network the distance between two vertices is equal to
the sum of distances between the corresponding coordinates (Eq. (1)). Consequently, from (5) we
obtain
dist
dist
ae X
dist
oe
ae X
oe
ae n
oe
as claimed.
The quantity s(v)=(n \Gamma 1) is known as the average distance of node v, giving the average
number of links that have to be traversed by a message departing from v. It is an important
performance measure of the network since under uniform addressing distributions it is directly
linked with the average delay a message experiences before reaching its destination [20]. Hence,
Theorem 1 can also be used to calculate the average distance of vertices in many graphs for which
no closed-form formula was known up to now. As an example, in generalized hypercubes [4] each
dimension is a complete graph with m i vertices, In a complete graph all nodes are
adjacent to each other, so that s i (v Consequently, the average distance in generalized
hypercubes is
In [4] it was possible to derive a formula only for the case where all m i are equal to each other.
In the context of the total exchange problem we are interested in the average status of the
nodes in the network. Let AS(G i ) be the average status of G i , defined in (3) as
We have the following corollary.
8 A Theory for Total Exchange in Multidimensional Interconnection Networks
. If AS(G i ) is the average status of G i ,
then the average status of G is given by
Proof. From Theorem 1 we obtain
(v 1 ;:::;v k )2G
which, divided by n, gives the required result.
4. Single-port Algorithm
A \Theta B. A k-dimensional network G 1 \Theta \Delta \Delta \Delta \Theta G k can still be expressed as the product
of two graphs by taking so we may consider two dimensions
without loss of generality. Let
Finally, let
\Phi
Graph G consists of n 2 (interconnected) copies of VA . Let A j be the jth copy of A with node set
takes all values in VA . Similarly, G can be viewed as n 1 copies of B, and we let
be the ith copy of B with node set (v i ;  ). An example is shown in Fig. 2.
4. Single-port Algorithm 9
(a) (b)
A A A A1 2 3 43

Figure

2. A 4 \Theta 3 torus as (a) four copies of a three-node ring or (b) three copies of a four-node
ring
We will develop the basic idea behind our algorithm through the example in Fig. 2. Consider
the top node of A 1 . This node belongs to A 1 as well as B 1 . All nodes in A 1 have, among other
messages, messages destined for the rest of the nodes in A 1 . These messages can be distributed
by performing a total exchange within A 1 . In addition, nodes in A 1 have messages for all nodes in
A 2 , A 3 and A 4 . Somehow, these messages have to travel to their appropriate destinations. What
we will do is the following: all messages of the top node of A 1 meant for the nodes in A 2 will be
transferred to the top node of A 2 . All messages of the middle node of A 1 destined for the nodes
in A 2 will be transferred to the middle node of A 2 . Similar will be the case for the bottom node
of A 1 . Once all these messages have arrived in A 2 , the only thing remaining is to perform a total
exchange within A 2 and all these messages will be distributed to the correct destinations.
Next, nodes of A 1 have to transfer their messages meant for A 3 to nodes of A 3 . The procedure
will be identical to the procedure we followed for messages meant for A 2 . Finally, the remaining
messages in A 1 are destined for A 4 and one more repetition of the above procedure will complete
the task. Notice that what we did for messages originating at nodes of A 1 has to be done also for
messages originating at the other copies of A, i.e. A 2 , A 3 and A 4 . We are now ready to formalize
our arguments.
We are going to adopt the following the message of node
destined for node (v k ; u l ). We will furthermore introduce the ' ' symbol to denote a
corresponding set of messages. For example, messages of node (v
Theory for Total Exchange in Multidimensional Interconnection Networks
1 For every
2 For every
3 For every
5 For every
6 Do in parallel for all A j ,
7 In A j perform total exchange of messages m ( ;u k
(messages reside in node (v

Figure

3. Algorithm A1
destined for the nodes of A l , and m (v destined for node
messages of (v Notice that this last set normally
includes nodes. Since no node sends messages to itself, it is
always implied that from any set of messages, we have removed every message whose source and
destination are the same.
Consider the set of messages set represents our total exchange problem:
every node has one message for every other node. Next consider the set m ( This is the
set of messages of nodes in A j destined for the other nodes in A j : they can be distributed by a
total exchange operation within A j . Finally, consider the set m (v
for the nodes of A k . This set will be transferred to node (v Thus, after such transfers,
node (v
and so on. Notice that every node in A k will have received messages meant for every node in A k :
these messages clearly can be distributed to the appropriate destinations through a total exchange
operation within A k .
To recapitulate, we can solve the total exchange problem in using Algorithm A1
shown in Fig. 3. First we perform all the transfers we described above and then we perform the
total exchanges within each A j . The transfers correspond to lines 1-4 in Algorithm A1. After
they are completed, every node (v i ; u j ), for every i, j, will have received all messages meant for
the jth copy of A originating at nodes (v
4. Single-port Algorithm 11
Lines 5-7 of the algorithm distribute these messages to the correct vertices of A j in n 2 rounds.
In the kth round a total exchange is performed and the exchanged messages have originated from
A k .
Algorithm A1 solves the total exchange problem but lines 1-4 do not show how the transfer
of messages is exactly implemented. First of all, there may exist path collisions between transfers
from (v and transfers from (v i we try to do them
simultaneously. Let us consider again the example in Fig. 2. At some point all nodes in A 1 want
to transfer their messages, say, for nodes in A 4 . We make the observation that these transfers can
indeed be done in parallel. That is, the top node of A 1 can transfer its messages to the top node
in A 4 , the middle node of A 1 can transfer its own messages to the middle node of A 4 and so on,
without any interference between them. The trick is to use only paths in the second dimension
(B). That is, all the transfers of the top node of A 1 use links in B 1 , all transfers from the bottom
node of A 1 use links in B 3 , etc.
Consequently, a straightforward way of parallelizing line 1 is the following: when transferring
messages from (v allow use of links in the second dimension. In other
words, the allowable paths (v
paths (v have no node in common. Consequently, lines
1-4 can be rewritten in the improved form:
1 Do in parallel for all
2 For every
3 For every
using links in B
We may still improve matters by further parallelizing lines 1-3. Within B i we need to transfer
messages from every vertex u j to every other vertex u k . In Table 1 we list the
messages to be transferred by some vertex (v . Notice that we do not have to transfer
messages meant for A j anywhere, so the jth column of the table is actually unused (it will only
be used for a total exchange within A j ). Column k contains all messages of (v
to be transferred first to node (v
12 A Theory for Total Exchange in Multidimensional Interconnection Networks
For
.
.
.
.
.
.

Table

1. Messages to be transferred from node s actually unused since
messages of (v do not have to be transferred to any other copy of A.
Instead of transferring the messages column by column (i.e. transfer all messages in column
1 to A 1 , then all messages in column 2 to A 2 , etc.) we transfer them horizontally (row by row).
The batch R r of messages in row r contains all messages m (v We will transfer all of
them, except of course for m (v which is meant for a node of A j . Let us
consider again the network in Fig. 2 and assume that the bottom nodes of A 1 , A 2 , A 3 and A 4
want to transfer their first batch, R 1 . The batch of the bottom node of A 1 contains one message
for each of the bottom nodes of A 2 , A 3 and A 4 . Similarly, batch R 1 for the bottom node of A 2
contains one message for the other three nodes in question. It should be immediately clear that
these messages constitute an instance of the total exchange problem in every node has one
message for every other node in B 1 .
In general, when every node (v
transfers its own batch R r
of

Table

1, a total exchange within B i can distribute the messages appropriately. Consequently,
all rows of Table 1 of every node will be transferred where they should by performing n 1 total
exchanges in at the rth exchange all nodes (v batch of messages (rth
row of the corresponding tables).
Based on the above discussion, and recalling that transfers within B i do not interfere with
transfers within may express our total exchange algorithm in its final form, Algorithm
A2, appearing in Fig. 4. Algorithm A2 is a general solution to the total exchange problem
for any multidimensional network. If the network has k ? 2 dimensions,
4. Single-port Algorithm 13
2 Do in parallel for all
In B i perform total exchange with node (v
sending messages m (v
4 For every
5 Do in parallel for all A j ,
6 In A j perform total exchange with node (v
sending messages m (v

Figure

4. Algorithm A2
Algorithm A2 can be used recursively, by taking . The total
exchanges in A j (lines 4-6) can be performed by invoking the algorithm with
The algorithm is in a highly desirable form: it only utilizes total exchange algorithms for each
of the dimensions. The problem of total exchange in a complex network is now reduced to the
simpler problem of devising total exchange algorithms for single dimensions. For example, we are
in a position to systematically construct algorithms for tori, based on algorithms for rings.
We now proceed to determine the time requirements of the algorithm and the conditions under
which it behaves optimally.
4.1. Optimality conditions
It is not very hard to calculate the time required for Algorithm A2. This is because it is written in
a form suitable for the single-port model: every node participates in one total exchange operation
at a time. When each total exchange is performed under the single-port model, in effect no node
sends/receives more than one message at a time.
Theorem 2 If single-port total exchange algorithms for graphs A and B take steps
correspondingly then Algorithm A2 for
14 A Theory for Total Exchange in Multidimensional Interconnection Networks
time units.
Proof. The result is straightforward: lines 1-3 perform n 1 total exchanges within B i (for all
parallel), each requiring steps. Similarly, lines 4-6 perform n 2 total exchanges
within A j (for all in parallel), each requiring steps.
Corollary 2 If and a single-port total exchange algorithm for G i takes
total exchange in G under the single-port model can be performed in
steps, where
Proof. The proof is by induction. If we only have one dimension then the corollary is trivially
true. Assume as an induction hypothesis that it holds for up to dimensions. Then we must
have
where T 0 is the time needed for total exchange in G
j. If we let Theorem 2 gives
as required.
Theorem 3 If single-port total exchange for every dimension
can be performed in time equal to the lower bound of (3) then the same is true for G.
Proof. If in G i total exchange can be performed in time equal to the lower bound of (3) then
From Corollary 2, we must have
5. Multiport Algorithm 15
which, combined with Corollary 1, shows that and the algorithm is thus optimal.
The last theorem provides the main optimality condition for Algorithm A2. If we have total
exchange algorithms for every dimension and these algorithms achieve the bound of (3) then
Algorithm A2 also achieves this bound. For example, in hypercubes every dimension is a two-node
graph. Trivially, in a two-node graph the time for total exchange is just one step, equal
to the average status. Thus the optimality condition is met and the presented algorithm is an
optimal algorithm for single-port hypercubes.
More generally, we have shown elsewhere [8] that there exist algorithms that need time equal
to (3) for any Cayley [1] network. Consequently, the optimality condition is met for arbitrary
products of Cayley networks. Rings and complete graphs are examples of Cayley networks and
thus Algorithm A2 solves optimally the total exchange problem in k-ary n-cubes, general tori and
generalized hypercubes.
5. Multiport Algorithm
In this section we will modify Algorithm A2 to work better under the multiport model. In its
present form, Algorithm A2 is not particularly efficient under this model. This is because lines
4-6 are executed after lines 1-3 have finished. During execution of lines 1-3 only edges of the
second dimension (B) are used while lines 4-6 use only edges of the first dimension (A). In the
multiport model we try to keep as many edges busy as possible and the behavior of Algorithm A2
does not contribute to that effect. We seek, consequently, to transfer messages in both dimensions
simultaneously. In other words we will reconstruct the algorithm such that lines 1-3 overlap in
time as much as possible with lines 4-6.
The theory we present here applies to homogeneous networks. We recall that a multidimensional
network is homogeneous when all its dimensions are identical. Thus,
H k for some graph H. We will only consider the two-dimensional case, i.e.
also be seen that the algorithm we derive is applicable when the dimensionality of the graph is in
general a power of 2, i.e.
E) where is, G has n 2 nodes.
A Theory for Total Exchange in Multidimensional Interconnection NetworksBBB

Figure

5. A 3 \Theta 3 homogeneous mesh
For A 1 For A 2 For A 3

Table

2. Messages to be transferred from node (1,1)
The network in Fig. 5 will be used as an example for our arguments. For node (1; 1) we give
the messages it will distribute in Table 2. The messages in the first column are meant for the
other nodes in A 1 . A total exchange within A 1 may thus begin immediately to distribute such
messages. Since this total exchange uses only links in the first dimension, node (1,1) is also
available to participate in some total exchange in the second dimension (i.e. in B 1 ). In a general
network, node (v can participate in a total exchange within B i as soon as the first total
exchange in A j starts. Within A j the transferred messages are m (v in column
j of

Table

1.
Let us see what messages will be involved in the first total exchange within B i . Our objective
is the following: we want every node (v to receive messages so
that after this total exchange in B i is done, another total exchange can be initiated within A j .
Consequently, we seek to arrange the transfers so that (v receives one message for each node
in A j , i.e. receive messages with destinations Notice that any node (v receive
messages through a total exchange in B i : since A j has n nodes (including (v all the
receptions of (v should be meant for nodes other than (v
5. Multiport Algorithm 17
In the network in Fig. 5, we let for example node (1,1) send m (1;1) (2; 2). This message will at
some point be received by node (1,2) and it will provide one message for the forthcoming total
exchange in A 2 . If (1,2) sends m (1;2) (2; 3) then node (1,3) will also be provided with one message
for total exchange in A 3 . Similarly, needed by node (1,1).
We define the following operators:
\Theta
These operators work like addition/subtraction modulo n but produce numbers ranging from 1
to n instead of 0 to are better suited for our purposes here. Based on this operator
and the preceding discussion, we see that one effective scheduling is to let node (v
and all Hence, this node will also
receive will use for the next total exchange in
A j .
Let us see what other messages will be sent during this first total exchange in B i . In our
example it is seen that since node (1,1) decided to send m (1;1) (2; 2), it cannot send another
message to node (1,2). Thus it has to send a message to node (1,3). Since this node will receive
which covers one destination in A 3 , the only choice for (1,1) is to send m (1;1) (3; 3).
This message completes the set of messages needed by (1,3) for the next total exchange in A 3
since all other vertices in A 3 are now covered. Similarly, (1,2) and (1,3) must send m (1;2) (3; 1) and
three nodes will have a complete set of messages, suitable for total exchanges
within A 1 , A 2 and A 3 .
In general, the second message that node (v
provide node (v second message for the total exchange in A j \Phi . The pattern
should now be clear: during the first total exchange in B i , every node (v
sends the following messages:
A Theory for Total Exchange in Multidimensional Interconnection Networks
or, in a compact form:
This node will provide node (v with the 'th message it needs (i.e. a message destined for
node (v i\Phi Notice that the above set contains one message to be received by
each node (v i.e. it is a perfect set for participation in the first total exchange in B i .
Also, it should be clear that (v receive the following messages:
Again notice that this set contains one message for each node (v . Thus we
achieved our goal: every node in B i receives a full set of messages to be used for the subsequent
total exchange in A j .
B, the first total exchange in A j finishes exactly when the first total exchange in B i
finishes. Thus the second total exchange in A j can start immediately, using the newly acquired
(through the exchange in B i ) messages. Then the story repeats itself: a second total exchange
in B i can be performed simultaneously with the second total exchange in A j . Our goal for this
total exchange in B i remains the same: to distribute messages that can be used for a third total
exchange in A j .
The idea behind selecting a group of messages for this second total exchange in B i is similar
to the one in the first total exchange we saw above. Now, we let (v
The situation is repeated continuously. While the rth total exchange within A j is in progress, the
rth total exchange in B i is also performed in order to provide nodes with messages for the next
total exchange in A j . During the rth exchange in B i a node (v sends the
5. Multiport Algorithm 19
following messages:
Observe that the destinations v i\Phi n ' are in the order given by
That is, the natural sequence which we used in the first total exchange in B i is
left-rotated by r positions. Based on this observation, it is easy to verify that the above set of
messages can be given in the compact form:
Similarly, it is seen that after the rth exchange in B i , node (v received messages
which can be used during the (r + 1)th total exchange in A j .
Let us recapitulate. During the first total exchange in A j , (v
taneously, total exchanges in B i start. During the rth exchange in B i the same node sends the set
of messages given in (7), and receives the set given in (8). This set will be used for the (r
exchange in A j . This will occur for all total exchanges in B i are performed
in parallel with the total exchanges in A j .
The last (nth) total exchange in A j will involve the messages received during the (n \Gamma 1)th
total exchange in B i . It can be noticed that (v i ; u j ) has sent all its messages meant for nodes
in all other copies of A, A k (k 6= j), except for nodes (v In the example of Fig. 5, we saw
that during the first two exchanges in B 1 , node (1,1) sent all its messages with the exception of
messages m (1;1) (1; which are destined for node (1,2) and (1,3). The situation
is similar for nodes (1,2) and (1,3). In conclusion, messages m (v are the
20 A Theory for Total Exchange in Multidimensional Interconnection Networks
only messages remaining to be sent. Observe that this is a perfect set of messages for a (final)
total exchange in B i . This nth exchange can be performed while the nth exchange in A j occurs.
What we have described up to now is formulated as Algorithm A3 in Fig. 6. The total
exchanges in the copies of A and B are completely parallelized, hence lines 1-3. Lines 4-8
perform the transfers we described above in B i . Lines 9-13 perform the total exchanges in A j .
Notice how simple lines 11-13 are: whatever was sent through the rth exchange in B i is used
during the (r 1)th exchange in A j .
As it is, the algorithm works for any two-dimensional homogeneous network. Extension to
more than two dimensions seems rather difficult because the homogeneity will be lost, in the sense
that A could be different than B. For example, if can be written as only
vice versa.
However, it is easy to see that the algorithm is applicable if the dimensionality is a power
of 2 . If
then we let
. The algorithm can then be applied
recursively for A and B, by e.g. setting
, and so on.
We proceed now to determine the time requirements of Algorithm A3 and to give optimality
conditions.
5.1. Optimality conditions
Theorem 4 If H has n nodes and total exchange in H requires TH steps then Algorithm A3 in
Proof. Procedure TEA() performs n total exchanges in A j (for all
thus requiring nTH steps. Similarly, TEB() also requires nTH steps. The algorithm finishes when
both procedures have finished, i.e. at time
By the recursive application of the algorithm for networks where the dimensionality is a power
of 2 we have the following corollary.
5. Multiport Algorithm 21
1 Do in parallel
4 For
5 Do in parallel for all
6 Perform total exchange in
7 Do in parallel for all
8 Perform total exchange in
9 Do in parallel for all A j ,
Perform total exchange in A j : node (v
12 Do in parallel for all A j ,
Perform total exchange in A j : node (v
the messages received from the second dimension (B i );

Figure

6. Algorithm A3 for multiport homogeneous networks:
22 A Theory for Total Exchange in Multidimensional Interconnection Networks
Corollary 3 Let . If total exchange in H requires TH time units, then
total exchange in G can be performed in
steps.
Proof. The proof is by induction. The case of two dimensions was covered in Theorem 4. If, as
an induction hypothesis, for G
apply Theorem 4 with G 0 treated as H, T 0 treated as TH , and n d=2 treated as n. It is then seen
that claimed.
Theorem 5 Let . If total exchange in H can be performed in time equal
to the lower bound of (4) then the same is true for G.
Proof. From Corollary 3, total exchange in G requires
If TH achieves the lower bound in (4) then there exists a partition VH1 , VH2 of the node set of H
such that
is the number of links separating the two parts.
Consider the following partition of V , the node set of G:
Then clearly, . Notice that G contains n d\Gamma1 copies of H and
that in order to separate the two parts we only need to disconnect each copy of H, by removing
links only in the first dimension. Since C VH 1 VH 2
links are needed to disconnect each copy of H,
we obtain
Thus, V 1 and V 2 is a partition of G such that
6. Discussion 23
which is equal to T , the time needed for total exchange in G. Thus the bound in (4) is tight for
G, too.
Summarizing, Algorithm A3 is a multiport total exchange algorithm for homogeneous networks
whose dimensionality is a power of 2. If total exchange in H can be performed in time equal to
the lower bound of (4) then Algorithm A3 optimally solves the problem in G. For example, in [7]
we have given algorithms that achieve this lower bound in linear arrays and rings. Consequently,
Algorithm A3 leads to an optimal total exchange algorithm for homogeneous meshes and tori with
dimensions.
6. Discussion
We have given a systematic procedure for performing total exchange in multidimensional net-
works. The main contribution is probably the existence of a decomposition of the problem to
simpler subproblems. Given that we have total exchange algorithms for single dimensions, we can
synthesize an algorithm for the multidimensional structure. In contrast with all the other works
on the problem, this approach is not limited to one particular network but to any graph that can
be expressed as a cartesian product.
Except for the structured nature of our method, we also showed that it is optimal with
respect to the number of communication steps for many popular networks. Under the single-port
assumption, Algorithm A2 provides optimal solutions for hypercubes, k-ary n-cubes, general tori
and actually any product of Cayley graphs. For most of these networks, this is the first optimal
algorithm to appear in the literature.
Under the multiport assumption, we reached similar conclusions for homogeneous networks
dimensions: Algorithm A3 solves the problem in any such network. Optimality is also
guaranteed if the single-dimension algorithm achieves the bound of (4). In particular, based on
known results for linear arrays and rings, meshes and k-ary n-cubes with 2 k dimensions can optimally
take advantage of our algorithm. We are currently studying the behavior of the algorithm
in the case where the number of dimensions is not a power of two. Some preliminary results
indicate that the algorithm could still be applicable.
A Theory for Total Exchange in Multidimensional Interconnection Networks



--R

"A group-theoretic model for symmetric interconnection networks,"
"Optimal communication algorithms for hypercubes,"
Parallel and Distributed Computation: Numerical Meth- ods
"Generalized hypercube and hyperbus structures for a computer network,"
Distance in Graphs.
"Deadlock-free message routing in multiprocessor interconnection networks,"
"Optimal total exchange in linear arrays and rings,"
"Optimal total exchange in Cayley graphs,"

"Methods and problems of communication in usual networks,"
"On the impact of communication complexity on the design of parallel numerical algorithms,"
"Compiling Fortran D for MIMD distributed-memory machines,"
"Communication efficient basic linear algebra computations on hypercube architectures,"
"Optimum broadcasting and personalized communication in hypercubes,"
Introduction to Parallel Algorithms and Architectures: Arrays
"High Performance Fortran,"
"Collective communication in wormhole-routed massively parallel computers,"
"MPI: A message-passing interface standard,"
"Communication aspects of the star graph interconnection net- work,"
"The performance of multicomputer interconnection net- works,"
"Product-shuffle networks: towards reconciling shuffles and butterflies,"
"Data communications in hypercubes,"
"Communication algorithms for isotropic tasks in hypercubes and wraparound meshes,"
--TR

--CTR
Yu-Chee Tseng , Sze-Yao Ni , Jang-Ping Sheu, Toward Optimal Complete Exchange on Wormhole-Routed Tori, IEEE Transactions on Computers, v.48 n.10, p.1065-1082, October 1999
V. Dimakopoulos, All-port total exchange in cartesian product networks, Journal of Parallel and Distributed Computing, v.64 n.8, p.936-944, August 2004
Shan-Chyun Ku , Biing-Feng Wang , Ting-Kai Hung, Constructing Edge-Disjoint Spanning Trees in Product Networks, IEEE Transactions on Parallel and Distributed Systems, v.14 n.3, p.213-221, March
V. Dimakopoulos , Nikitas J. Dimopoulos, Optimal Total Exchange in Cayley Graphs, IEEE Transactions on Parallel and Distributed Systems, v.12 n.11, p.1162-1168, November 2001
total exchange;collective communications;interconnection networks;packet-switched networks;multidimensional networks