IEEE Trans. on Computers, 49 (3), 2000, pp. 259-266
Ömer Egecioglu and Cemil M. Azizoglu
Lower Bounds on Communication Loads and
Optimal Placements in Torus Networks
Abstract.
Fully-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 a pair 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
of the form
$c k^{d-1}$.
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.
omer@cs.ucsb.edu