Lower bounds on communication loads and optimal placements in torus networks

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 increase at most linearly with the size of the placement on torus networks. Blaum, Bruck, Pifarre, and Sanz (1996, 1997) 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² processors, respectively. The authors 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). They use this to construct a tighter lower bound for the maximum load of a placement for 4 or more dimensions. Based on these results, they give optimal placements and their corresponding routing algorithms in tori with arbitrary number of dimensions