Lower bounds on communication loads and optimal placements in torus networks

• Main Authors: Azizoglu, M.C., Egecioglu, O.
• Format: Conference Proceeding
• Language: English
• Subjects: Computer networks; Computer science; Concurrent computing; Degradation; Intelligent networks; Multiprocessor interconnection networks; Network topology; Routing; Telecommunication traffic; Throughput
• ISSN: 1063-7133
• DOI: 10.1109/IPPS.1998.669957

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/sup 2/ 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/sup 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.