About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
IPDPS 1996
Conference paper
On optimal placements of processors in Tori networks
Abstract
Two and three dimensional k-tori are among the most used topologies in the designs of new parallel computers. Traditionally (with the exception of the Tera parallel computer), these networks have been used as fully-populated networks, in the sense that every routing node in the topology is subjected to message injection. However, fully-populated tori and meshes exhibit a theoretical throughput which degrades as the network size increases. In contrast, multistage networks (that are partially populated) scale well with the network size. Introducing slackness in fully-populated tori, i.e., reducing the number of processors, and studying optimal routing strategies for the resulting interconnections are the central subjects of this paper. The key concept that we study is the placement of the processors in a network together with a routing algorithm between them, where a placement is the subset of the nodes in the interconnection network that are attached to processors. Our main contribution is the construction of optimal placements for d-dimensional k-tori networks, of sizes k and k2 and the corresponding routing algorithms for the cases d = 2 and d = 3, respectively.