Lower Bounds on Communication Loads and Optimal Placements in Torus Networks.
AbstractFully populated torus-connected networks, where every node has a processor attached, do not scale well since load on edges increases superlinearly with network size under heavy communication, resulting in a degradation in network throughput. In a partially populated network, processors occupy a subset of available nodes and a routing algorithm is specified among the processors placed. Analogous to multistage networks, it is desirable to have the total number of messages being routed through a particular edge in toroidal networks increase at most linearly with the size of the placement. To this end, we consider placements of processors which are described by a given placement algorithm parameterized by $k$ and $d$: We show formally, that to achieve linear communication load in a $d$-dimensional $k$-torus, the number of processors in the placement must be equal to $c k^{d-1}$ for some constant $c$. Our approach also gives a tighter lower bound than existing bounds for the maximum load of a placement for arbitrary number of dimensions for placements with sufficient symmetries. Based on these results, we give optimal placements and corresponding routing algorithms achieving linear communication load in tori with arbitrary number of dimensions.
Introduction
Meshes and torus based interconnection networks have been utilized extensively in the design
of parallel computers in recent years [5]. This is mainly due to the fact that these
families of networks have topologies which reflect the communication pattern of a wide
An extended abstract was presented in the IEEE Symposium IPPS/SPDP 1998, April 1998, Orlando.
y Supported in part by a fellowship from - Izmir Institute of Technology, -
Izmir, Turkey.
variety of natural problems, and at the same time they are scalable, and highly suitable
for hardware implementation. An important factor determining the efficiency of a parallel
algorithm on a network is the efficiency of communication itself among processors. The
network should be able to handle "large" number of messages without exhibiting degradation
in performance. Throughput, the maximum amount of traffic which can be handled by
the network, is an important measure of network performance [3]. The throughput of an
interconnection network is in turn bounded by its bisection width, the minimum number of
edges that must be removed in order to split the network into two parts each with about
equal number of processors [8].
Here, following Blaum, Bruck, Pifarr'e, and Sanz [3, 4], we consider the behavior of torus
networks with bidirectional links under heavy communication load. We assume that the
communication latency is kept minimum by routing the messages through only shortest
(minimal length) paths. In particular, we are interested in the scenario where every processor
in the network is sending a message to every other processor (also known as complete
exchange or all-to-all personalized communication). This type of communication pattern
is central to numerous parallel algorithms such as matrix transposition, fast Fourier trans-
distributed table-lookup, etc. [6], and central to efficient implementation of high-level
computing models such as the PRAM and Bulk-Synchronous Parallel (BSP). In Valiant's
BSP-model for parallel computation [14] for example, routing of h-relations, in which every
processor in the network is the source and destination of at most h packets, forms the main
communication primitive. Complete-exchange scenario that we investigate in this paper
has been studied and shown to be useful for efficient routing of both random and arbitrary
h-relations [7, 12, 13].
The network of d-dimensional k-torus is modeled as a directed graph where each node
represents either a router or a processor-router pair, depending on whether or not a processor
is attached at this node, and each edge represents a communication link between
two adjacent nodes. Hence, every node in the network is capable of message routing, i.e.
directly receiving from and sending to its neighboring nodes.
A fully-populated d-dimensional k-torus where each node has a processor attached,
contains k d processors. Its bisection width is 4k which gives k d =2 processors
on each component of the bisection. Under the complete-exchange scenario, the number
of messages passing through the bisection in both directions is 2(k d =2)(k d =2). Dividing by
the bisection bandwidth, we find that there must exist an edge in the bisection with a load
This means that unlike multistage networks, the maximum load on a link is
not linear in the number of processors injecting messages into the network. To alleviate
this problem, Blaum et al. [3, 4] have proposed partially-populated tori . In this model, the
underlying network is torodial, but the nodes do not all inject messages into the network.
We think of the processors as attached to a (relatively small) subset of nodes (called a
placement), while the other nodes are left as routing nodes. This is similar to the case of a
multistage network: A multistage network with k \Theta k switches (routing nodes) and log k n
stages serves n injection points, and utilizes n log k n routing nodes [3].
In partially-populated tori, a routing algorithm which utilizes shortest paths is specified
together with the placement. An optimal placement is a placement that achieves linear load
on edges using maximum number of processors possible.
The notion of resource placement in general has been investigated by a number of researchers
such as Bose et al. [5], Alverson et al. [1], F. Pitteli and D. Smitley [11]. Our
aim is to give placements and routing algorithms which will enable efficient communication
between processors, and at the same time reduce the susceptibility of the network to
link faults by reducing the number of messages relying upon a particular edge [3]. This
is achieved by providing routing algorithms in which the number of minimal paths specified
between pairs of processors in the placement is kept large, without compromising the
linearity of load.
denote the maximum load over all the edges for the placement P . Blaum et
al. give the lower bound
which means that for constrained
to be of the form k i , then they also give placements of sizes k for
together with routing algorithms. These placements are optimal in the sense that the two
lower bounds are actually achieved by the placements.
How do we justify that in general a maximal size placement that can achieve linear load
is O(k d\Gamma1 )? If the placement has size ck d\Gamma1 for some constant c, then mimicking the case
of the fully-populated d-dimensional k-torus,
2(ck
This seems to imply that linear load is at least possible for jP ck d\Gamma1 . This is a faulty
argument however, as we do not know a priori that number of edges needed to split P
into two equal size pieces is the same as the bisection width of the whole torus. This may
push the size of an optimal placement above or below k d\Gamma1 . In this paper, we introduce
the concept of bisection width with respect to a placement P , and use its properties to
prove that in a d-dimensional k-torus, the size of an optimal placement is \Theta(k Given
a placement P of maximal size, we also prove that there exists an edge separator of size
which splits the torus into two components with \Theta(k processors of P on each
side. This gives a lower bound of the form
ck
for maximum load. In (2) c is a constant independent of d. This is a tighter lower bound
for the load for large d than the lower bound (1).
Finally, we give optimal placements (called linear placements ) achieving the lower
bound (2) and corresponding routing algorithms (Ordered Dimensional Routing (ODR)
and Unordered Dimensional Routing (UDR)) in tori with arbitrary number of dimensions.
Of the two routing algorithms ODR is simpler, but UDR provides fault tolerance by allowing
more routes. We also show how tho extend these to more general placements in tori that
we refer to as multiple linear placements.
The outline of the paper is as follows. Section 2 gives necessary definitions and the
formal statement of the problem. In section 3, a lower bound on the maximum load on an
edge is given, which is also a generalization of the lower bound given by [3]. This bound,
along with the notion of bisection width with respect to a placement, is used to get an
upper bound on the number of processors in an optimal placement. We introduce the
notion of ff\Gammaseparator with respect to a placement in section 4, and use it to give a new
lower bound on the maximum load which is independent of the dimension parameter in
section 5. Finally, in sections 6-8, we define and analyze an important class of placements
called linear placements, and give associated routing algorithms which achieve linear load
and fault tolerance. Section 9 includes conclusions and some future considerations.
Preliminaries and Problem Definition
In this section, we start out with the problem definition, and follow it by a sequence of
formal definitions and terminology that will be used in the rest of the paper.
Problem Definition
Our aim is to find placements and associated routing algorithms in the d-dimensional k-torus
k that have linear message load (in number of processors in the placement) on edges
under the complete exchange scenario. Specifically, we like to devise a placement P , and a
routing algorithm A for P for which
The d-dimensional k-torus is a directed graph T d
E), with vertex set
where ZZ k denotes the integers modulo k, and edge set
9j such that a
k has a total of k d nodes. Each node has two neighbors in each dimension, for a total
of 2d neighbors. Directed edges of T d
are also referred to as links.
placement P of processors in T d
E) is a subset of V .
We use the term node for a generic element of the vertex set of T d
k . A node with a processor
attached is simply called a processor.
fRouting Algorithmg
Let P be a placement in T d
k . A routing algorithm A is a subset C A
~ p!~q of the set of all shortest
paths between ~p and ~q for every pair ~ p , ~q 2 P (See Figure 1).
The routing algorithm A is used to deliver packets from ~ p to ~q : When ~
p needs to
communicate with ~q , a shortest path in C A
~ p!~q is selected randomly with uniform probability.
For any link l, we denote the set of paths in C A
~
p!~q going through l by C A
~ p!l!~q , and use
the following definition of load as given in [3].
Given a placement P in a T d
k along with a routing algorithm A, the load of an edge l is
defined as
~
jC A
jC A
The maximum value of E(l) for a network with placement P and a routing algorithm A is
called the maximum load and denoted by E max . Thus
Considering the expression (3) for E(l), the more paths the routing algorithm provides
between any two processors, the smaller the load on any edge that is used to route messages
between these processors. In addition to this, availability of a large number of choices means
better fault tolerance.
We shall consider algorithms which use minimal (shortest) paths. Minimal paths are
associated with the notion of cyclic distance and Lee distance which we define next.
Definition 6 fCyclic Distance, Lee Distanceg
Given three integers, i, j and k, the cyclic distance between i and j modulo k is given by
where the equivalence classes modulo k are taken to be 0; 1. The Lee distance
between two nodes ~
k is the sum of the cyclic distances between the coordinates of ~
and ~q.
The Lee distance between ~
k is the length of a shortest path between ~p and ~q on
the torus [5, 9].
Definition 7 fBisection Widthg
The bisection width of a graph is the minimum number of edges which must be removed in
order to split the node set into two parts of equal (within one) cardinality.
Definition 8 fBisection Width with respect to a Placementg
The bisection width with respect to a placement P of T d
E) is the minimum number
of edges which must be removed from E in order to split V into two parts each of which
containing an equal (within one) number of processors in P .
We denote by @ b P a minimal cardinality set of edges of T d
which needs to be removed
to bisect P . Thus j@ b P j is the bisection width with respect to the placement P .
Definition 9 fff-separator Width with respect to a Placementg
An ff-separator with respect to a placement P in T d
k is a set of edges whose removal splits
the graph into two parts containing (approximately) ffjP j and (1 \Gamma ff)jP j processors, for
1. The ff-separator width of T d
k with respect to a placement P is the size of a
minimal ff-separator with respect to P .
We denote the set of edges in an ff-separator by @ ff P . Thus j@ ff P j is the ff-separator
width of T d
k with respect to P . Note that when are equivalent.
We use the notation ck
for some constant c ? 0 whenever k - k 0 .
ck for infinitely many values of k.
loosely use
The problem we are interested in is the construction of placements P and associated
routing algorithms in T d
k such that under the complete exchange scenario,
for some constant c.
For et al. [3, 4] have investigated placements with k d\Gamma1 processors.
Evidently, placements with provably maximum possible number of processors are desirable.
This raises another important question which we shall address: what is the maximum
number of processors a placement could have on T d
k without compromising linear load on
Another important issue is fault tolerance. Specifically, the routing algorithm should
provide multiple routing paths between each pair of processors so that, if any of the links
fails, the network will remain functional by routing the messages through paths which do
not include the defective link. Consequently we also address the following problem: is it
possible to construct optimal placements which are at the same time fault tolerant?
In the following sections, we analyze lower bounds for maximum load and study the
above questions.

Figure

1: A placement of 3 processors on T 2
3 . Among the links, the ones on specified
shortest paths between the processors are highlighted.
3 A General Lower Bound for Maximum Load
We start out with an important lemma which will prove to be a very useful tool in the
subsequent sections. The lower bound for maximum load originally given by Blaum et al.
[3] is
2d (4)
The following lemma gives a more general form of (4).
be a placement in a T d
and @S be the set of all
edges each connecting a node in S with another node not in S. Then
Proof The total number of messages exchanged between processors in S and processors
in either direction, is personalized communication
scenario. Also, these messages must go through one of the edges in @S. The average
number of messages going through an edge in @S is and the lemma
It is easy to see that (5) reduces to (4) if the set S is taken to contain only one processor,
4d. The lower bound (5) is valid independent of the routing
algorithm used. Another interesting form of (5) that we shall subsequently make use of is
obtained when the set S consists of half of the processors in P , i.e.,
Note that in this case @S becomes @ b P , which is the bisection width of T d
k with respect
to placement P . Next we give an upper bound on the size of @ b P , which we then use to
calculate the maximum number of processors an optimal placement can contain.
Proposition 1 Any subset P of nodes of the d-dimensional k-torus can be bisected by removing
k . In particular, any subgraph of T d
k has bisection width O(k
Proof Omitted. See Appendix I. 2
The constant in O(k d\Gamma1 ) of Proposition 1 is no larger than 6d when we consider directed
edges. As a particular case of the proposition we view a placement P as a subgraph of T d
with no edges. Then
Corollary 1 The d-dimensional k-torus T d
k has bisection width of at most 6dk d\Gamma1 with
respect to any placement P , i.e. j@ b
Remark
Although the assertion of Proposition 1 appears intuitive because of its geometric nature
for it is easy to come up with examples of general graphs for which the
bisection width of subgraphs can become arbitrarily far from that of the original graph.
As an example, two copies of the complete graph K 2n on 2n nodes joined by a single edge
has bisection width 1. Its subgraphs with 2n nodes have bisection widths ranging from 1
to depending on how evenly the 2n nodes are distributed among the two copies of
K 2n .
Maximum Placement Size
An upper bound for the maximum number of processors an optimal placement can contain
can now be obtained by substituting the bound for j@ b P j given in the corollary into the
inequality (6), while at the same time insuring that E i.e. the load remains
linear in the number of processors in the placement.
ck
for That is, the size of an optimal placement
in T d
k is O(k Thus, we are justified in seeking placements which have ck
for some constant c. However, for ease of exposition, we will give analyses of placements of
size k d\Gamma1 first (i.e. 1). Subsequently, we also consider the construction of placements
with c ? 1.
4 ff-Separator Width with respect to a Placement
From corollary 1, we know that the bisection width of T d
k with respect to a placement P is
no larger than 6dk d\Gamma1 . The lower bound on maximum load that one can obtain using this
result is a function of dimension d, however. In this section we show that given a placement
on T d
k with jP possible to divide the network into two parts each having
processors by removing O(k d\Gamma1 ) edges, where the constants involved in \Theta(jP j) and
are independent of d. This will be useful in obtaining a better lower bound for
load on edges than (4). We give a proof of this result in Theorem 1, assuming that the
number of processors placed in subtori of T d
k are given by "reasonable" functions of k, such
as polynomials. Theorem 1 holds in general without this assumption, see Appendix II.
Theorem 1 Relative to a placement P of size \Theta(k
k has an edge separator @ ff P of
size O(k d\Gamma1 ) which splits T d
k into two parts each with \Theta(k processors (specifically, ffk
processors, respectively, for some ff, 0 ! ff ! 1), where the constants are
independent of d.
Proof
Let us fix a dimension. There are k copies of a lower dimensional torus T
embedded
along this dimension, indexed from 0 through k \Gamma 1. Let a j (k) be the number of processors
P has in the j th subtorus, 1. There are two cases to consider depending on
whether or not a i First we assume that there
is such an a i (k). The situation is especially simple if there are two indices
a we remove the edges between subtori i and
separating T d
k into two parts each with
processors. The total number of edges removed is \Theta(k
If there is only a single index i for which a i
an argument as above can again be used to split P by removing 4k d\Gamma1 edges. We can thus
assume that P
time we cannot separate T d
k using the argument
above however. Now let S
k be the subtorus for which a i
k can be bisected relative to the processors it contains by removing no more than
6dk d\Gamma2 edges. Therefore T d
k has a bisection relative to P obtained by removing at most
6dk d\Gamma2 +4d
edges. This is because there are a total of 4d
incident
on the processors in all the subtori excluding S
k . Therefore
a
whenever d ! k. Thus, it is possible to split the T d
k into two parts, each containing \Theta(k
processors by removing no more than O(k (actually o(k edges.
Now consider the case that no a i (k) is \Omega\Gamma k
at the same time
We outline the proof here for the case when the
a i (k) are polynomial functions of k (It follows from Proposition 2 in Appendix II that this
assumption is not necessary). Let 1g. Note that
must be \Omega\Gamma k), since otherwise jP j could not be \Theta(k are polynomial
functions and all a i whose indices are in U must each have \Theta(k d\Gamma2 )
processors. Furthermore this forces jU Thus we can find aek subtori that have
1. Consequently we can split T d
k into two parts each having
ae
processors by removing O(k
5 An Improved Lower Bound for Maximum Load
We have shown in the previous section that given a placement P of size c 1 k d\Gamma1 , it is possible
to split T d
k into two parts having ffjP j and (1 \Gamma ff)jP j processors by removing at most c 2 k
edges, for some constants c 1 , c 2 , and ff, We use this result to establish a lower
bound on load which shows that the lower bound E max - (jP
as the parameter d grows larger.
Taking in (5), we have
ck
. Note that the constant c is independent of parameter d. Hence,
this lower bound comes to characterize the quantity E max more closely than (4) as the
parameter d grows. We will use this lower bound to gauge the optimality of the placements
and routing algorithms that we give next.
6 Linear Placements
We have established in section 3 that optimal placements have \Theta(k processors. In this
section, we introduce the notion of a linear placement: these are placements in which the
coordinates of each processors in P satisfy a particular type of a linear equation over ZZ k .
Definition 11 A placement P on T d
which satisfies
, and at least one of c i 2 ZZ k is relatively prime to k is called a linear
placement.
For simplicity, we will use placements where c even though our
analyses apply to linear placements in general form (i.e. (7)) provided that c 1 and c d are
relatively prime to k. Note that there are exactly k d\Gamma1 processors satisfying the expression
specific c 2 ZZ k . Originally, linear placements of this
form were used in three dimensional tori by Blaum et al. [3, 4], where they were called
shifted diagonal placements.
We can also specify placements of size tk d\Gamma1 where t is a fixed integer less than k. For
instance, the placement
has tk d\Gamma1 processors. We shall call such placements multiple linear placements.
Remark
We would like to point out that linear (and multiple linear) placements themselves do not
guarantee the linearity of the load on edges. Linear only refers to the fact that the coordinates
of the processors in the placement satisfy a linear equation over ZZ k . We still need
to construct routing algorithms which enable communication between pairs of processors
in a way that yields load that is linear in jP j.
In the remaining sections, we will specify different routing algorithms and analyze their
maximum communication load on edges. As we have mentioned earlier, the routing algorithms
will use minimal (shortest) paths between processors. To deliver a message from
processor ~p to ~q , the value of ~p in each dimension is "corrected" towards the corresponding
value in ~q by the amount and direction (\Sigma) dictated by the shortest cyclic distance
between the values in that dimension. The exact way of correcting the dimensions to route
the packets is specified by the routing algorithm.
We consider two classes of routing algorithms and the analysis of the load in each case
both for linear and multiple linear placements: Ordered Dimensional Routing (ODR) and
Unordered Dimensional Routing (UDR).
7 The Ordered Dimensional Routing Algorithm (ODR)
The algorithm is simple. Given a placement P on T d
k to route a packet from
to
for to d do
in the direction of shortest cyclic distance
That is, the routing path will include the following nodes:
Note that if k is odd, jC ODR
there is only 1 path specified by the ODR algorithm
for any given ~p and ~q 2 P . However, when k is even the ODR algorithm may
result in multiple paths between some pairs of processors in the placement. To aid in the
analysis, we will use the following (restricted) version which ensures the existence of only
one canonical routing path between any given pair of processors regardless of the parity of k.
for to d do
begin
if there is more than one way of correcting p i then
Pick the path that corrects p i in the (+) direction (mod k);
in the direction of shortest cyclic distance
Thus if there are two choices for some coordinate pair, the algorithm routes through
. The shortcoming of having only one path between
a pair of processors is the lack of fault-tolerance in the network. Specifically, if an edge
over which a pair of processors communicate fails then the pair will no longer be able to
exchange messages. In section 8 we look at another routing algorithm which does not suffer
from this limitation.
7.1 Load Analysis for Linear Placements with ODR
Theorem 2 Given a linear placement
Ordered Dimensional Routing Algorithm results in linear load on edges.
Proof Since ODR algorithm ensures one path between each pair of processors, each
denominator in the expression (3) for E(l) is 1. Thus, in order to compute E max , we need
only to count the (maximum) number of pairs of processors that communicate through a
specific edge. Without loss of generality, consider an edge l 2 E, where
We will count pairs of processors which communicate using l. Let ~ p and ~q 2 P be two
processors where ~p sends messages to ~q through l. Since ODR algorithm is used, we must
have
and
with and ~q are both in P and P is linear, the coordinates
and
Therefore
Note that if ~ p and ~q are to use the edge l then, in order to ensure that messages follow
shortest paths, we must also have,
by the property of cyclic distance. The number of processors satisfying equation (8) is less
than or equal to k s\Gamma1 while those satisfying (9) is less than or equal to k d\Gammas . Thus, the total
number of processor pairs cannot be more than k
and the maximum load is linear in jP
Note that we are actually overcounting since we have not taken the restrictions p s - i s ,
on the s-th dimension into account when
we count the solutions of (8) and (9). These conditions affect the choices of p s and q s .
A more accurate expression (though of the same order) can be obtained by paying closer
attention to these parameters: To determine the number of different ways p s and q s may
be chosen, consider the 1-dimensional k-subtorus (ring) on which the edge l lies. Assume
first that k is even. Without loss of generality, also assume that the nodes in the ring are
enumerated from 0 to 1. Then, the ODR algorithm will use l to
deliver messages from node 0 to only node k=2 on this ring. Similarly, it will use edge l for
messages from node 1 to node k=2 and from node 1 to node k=2
from node k=2 can be sent using l to any node indexed k=2 to k \Gamma 1. The total
number of choices for p s and q s will therefore be
Now assume that k is odd, and also that i 1)=2. In this case, messages from
node 1 can be delivered to only node (k while messages from node 2 can
be routed to nodes on. Thus there are a total of
k\Gamma1( k\Gamma1+ 1)choices for p s and q s when k is odd.
Therefore the number of solutions to equations (8) and (9) which satisfy the conditions
d\Gamma2when k is even, and
Therefore regardless of the parity of k, for a linear placement P with ODR, jP
7.2 Multiple Linear Placements with ODR
Theorem 3 Multiple linear placements along with ODR algorithm on T d
k results in linear
load on edges.
Proof The analysis is conceptually similar to that of the previous section. Consider a
multiple linear placement
E) with ODR where for some
fixed constant
Note that jP As before, consider an edge l 2 E of the form
and a pair of processors ~ p , ~q 2 P , which communicate using l. Since ODR algorithm is
used, we must have
and
with and ~q are
both in P , each must satisfy an equation among
and
The number of solutions to equations (10) is no more than tk . Similarly, the number
of solutions to equations (11) is no more than tk d\Gammas . Therefore, the total number of
processor pairs communicating through l is bounded by t 2 k d\Gamma1 , which is linear in jP j for
constant t. 2
8 Unordered Dimensional Routing (UDR)
We mentioned in section 7 that ODR algorithm suffers from lack of fault-tolerance, since
there is only one path between each pair of processors. In this section, we introduce Un-ordered
Dimensional Routing (UDR), which eliminates this problem. The algorithm is as
follows: To route a packet from ~
for to d do
begin
Select a number j from the set f1; dg that has not been used before;
in the direction of shortest cyclic distance
As was the case in ODR, a dimension is corrected completely before another is selected.
Unlike ODR, however, the order in which the dimension to be corrected next is picked
is arbitrary. This algorithm thus provides multiple paths for each pair of processors and
improves the fault-tolerance of the system. If ~p and ~q are two processors differing in s
dimensions, then there will be s! different paths from ~p to ~q in UDR, i.e. jC UDR
we show that UDR algorithm results in linear load in edges.
8.1 Load Analysis for Linear Placements with UDR
For a linear placement P which uses UDR algorithm, the load on an edge l is
~ p2P;~q2P
Since there exist some pairs of processors for which jC UDR
~ p2P;~q2P
The upper bound on the right hand side of this inequality specifies the number of messages
sent between pairs of processors which could "potentially" route their messages through
l. Such processors can also use other paths that do not include l, since UDR algorithm
provides multiple routing paths.
Theorem 4 Given a linear placement
Unordered Dimensional Routing Algorithm results in linear load on edges.
Proof Without loss of generality l 2 E is of the form
l =! (i
Suppose ~ p and ~q 2 P are two processors communicating through l. Our aim is to find an
upper bound on the number of pairs of processors communicating through l. A moment of
thought reveals that ~ p and ~q must have either arbitrary or q
arbitrary, for j 6= s. This means the number of possible choices in dimension j is less than
2k. Hence, the total number of choices for all of the coordinates of ~p and ~q excluding s is
less than 2 and ~q are both in P they satisfy
and
There are at most one solution pair for each one of 2 choices (as before, the co-ordinates
in the s-th dimension are restricted by the conditions p s
Therefore, the total number of processor pairs communicating
through l is bounded by 2
f
~ p2P;~q2P
which is linear in jP fixed d. 2
8.2 Multiple Linear Placements with UDR
Theorem 5 Multiple linear placements along with UDR algorithm on T d
k results in linear
load on edges.
Proof We have As before, consider a processor pair ~p , ~q 2 P which
communicate using l where
The number of choices for processor pairs using l is strictly less than 2 as in the
case of linear placements with UDR. Since there are t equations for each of ~ p and ~q , there
are t 2 solutions for every one of 2 choices of pairs. Therefore the number of pairs of
processors communicating through l is less than t which is linear in jP j for any
fixed constant t ! k. 2
9 Conclusion
Following the work of Blaum, Bruck, Pifarr'e, and Sanz [3, 4], we have considered communication
in partially-populated torus networks in terms of placements of processors and
associated routing algorithms. We have provided lower bounds for the maximum load under
the all-to-all communication scenario, and found bounds on the size of an optimal place-
ment. We have shown that arbitrary placements can be bisected by removing a set of edges
of the same order as the bisection width of the torus. We then provided optimal placements
of size \Theta(k d\Gamma1 ) on the d-dimensional k-torus using what we call linear and multiple linear
placements, and gave load analyses of each under two different routing algorithms.
There are some interesting combinatorial properties of placements still to be resolved.
Among these are the characterization of optimal placements in terms of restrictions to
subtori and an extensive analysis of the properties of edge separators of tori relative to
optimal placements.



--R

The Tera Computer System.
Resource Placement in Torus-Based Networks
On Optimal Placements of Processors in Tori Networks.
On Optimal Placements of Processors in Fault-Tolerant Tori Networks
Lee Distance and Topological Properties of k-ary n-cubes

Direct Bulk-Synchronous Parallel Algorithms
Introduction to Parallel Algorithms and Architectures: Arrays
The Theory of Error-Correcting Codes
A Survey of Wormhole Routing Techniques in Direct Networks.
Analysis of a 3D Toroidal Network for a Shared Memory architecture.
Efficient Communication Using Total Exchange.
Routing on Triangles
A Bridging Model for Parallel Computation.
--TR
routing;torus;interconnection network;edge separator;bisection;placement