Proc. IEEE 1998 IPPS/SPDP Symposium, Orlando, March 1998, pp. 460-464.
Ömer Egecioglu and Cemil M. Azizoglu
Lower Bounds on Communication Loads and
Optimal Placements in Torus Networks (Extended Abstract)
Abstract.
Fully-populated tori, 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 are placed on a
subset of available nodes, and a routing algorithm is
specified among the processors.
Analogous to multistage networks, it is desirable to have
the total number of messages being routed through a
particular edge increases at most linearly with the size
of the placement on torus networks. Recently, Blaum,
Bruck, Pifarre, and Sanz investigated placements and
provided both a lower bound, and optimal placements in
the cases of 2 and 3-dimensional k-tori, consisting
of k and k^2 processors, respectively.
In this paper we show formally that to achieve linear
load in a d-dimensional k-torus, the number of
processors in the placement must be O(k^{d-1}). We
use this to construct a tighter lower bound for the
maximum load of a placement for 4 or more dimensions.
Based on these results, we give optimal placements and
their corresponding routing algorithms in tori with
arbitrary number of dimensions.
omer@cs.ucsb.edu