Lower bounds on communication loads and optimal placements in torus networks

Fully populated torus-connected networks, where every node has a processor attached, do not scale well since load on edges increases superlinearly wit h network size under heavy communication, resulting in a degradation in net work throughput. In a partially populated network. processors occupy a subs et of available nodes and a routing algorithm is specified among the proces sors 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 p lacement algorithm parameterized by k and d: We show formally, that to achi eve linear communication load in a d-dimensional k-torus, the number of pro cessors in the placement must be equal to ck(d-1) for some constant c. Our approach also gives a tighter lower bound than existing bounds for the maxi mum load of a placement for arbitrary number of dimensions for placements w ith sufficient symmetries-Based on these results, we give optimal placement s and corresponding routing algorithms achieving linear communication load in tori with arbitrary number of dimensions.