Lower Bounds on Communication Loads and Optimal Placements inTorus Networks

Fully-populated torus-connected networks, where every node has a processorattached, do not scale well since load on edges increases superlinearly withnetwork size under heavy communication, resulting in a degradation in networkthroughput. In a partially-populated network, processors occupy a subset ofavailable nodes, and a routing algorithm is specified among the processorsplaced. Analogous to multistage networks, it is desirable to have the totalnumber of messages being routed through a particular edge increase at mostlinearly with the size of the placement on torus networks. Recently, Blaum,Bruck, Pifarre, and Sanz investigated placements and provided both a lowerbound, and optimal placements in the cases of 2 and 3-dimensional $k$-tori,consisting of $k$ and $k^2$ processors, respectively. In this technical reportwe 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 toconstruct a tighter lower bound for the maximum load of a placement for 4 ormore dimensions. Based on these results, we give optimal placements and theircorresponding routing algorithms in tori with arbitrary number of dimensions.