A Caltech Library Service

On Optimal Placements of Processors in Tori Networks

Blaum, Mario and Bruck, Jehoshua and Pifarré, Gustavo D. and Sanz, Jorge L. C. (1996) On Optimal Placements of Processors in Tori Networks. In: Eighth IEEE Symposium on Parallel and Distributed Processing. IEEE Computer Society , Los Alamitos, CA, pp. 552-555. ISBN 0-8186-7683-3.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


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 the paper. The key concept 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. The main contribution is the construction of optimal placements for d-dimensional k-tori networks, of sizes k and k^2 and the corresponding routing algorithms for the cases d=2 and d=3, respectively.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Bruck, Jehoshua0000-0001-8474-0812
Additional Information:© 1996 IEEE. Date of Current Version: 06 August 2002. Supported in part by the NSF Young Investigator Award CCR-9457811, by the Sloan Research Fellowship and by a grant from the IBM Almaden Research Center, San Jose, California. Supported in part by the Universidad de Buenos Aim through the research project EX-155 and through the scholarships program Rene Hugo Thalman.
Funding AgencyGrant Number
NSF Young Investigator AwardCCR-9457811
Sloan Research FellowshipUNSPECIFIED
IBM Almaden Research CenterUNSPECIFIED
Universidad de Buenos AiresEX-155
Rene Hugo Thalman Scholarships ProgramsUNSPECIFIED
Other Numbering System:
Other Numbering System NameOther Numbering System ID
INSPEC Accession Number5465376
Record Number:CaltechAUTHORS:20120207-113452642
Persistent URL:
Official Citation:Blaum, M.; Bruck, J.; Pifarre, G.D.; Sanz, J.L.C.; , "On optimal placements of processors in tori networks," Parallel and Distributed Processing, 1996. Eighth IEEE Symposium on , vol., no., pp.552-555, 23-26 Oct 1996 doi: 10.1109/SPDP.1996.570382 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:29170
Deposited By: Ruth Sustaita
Deposited On:07 Feb 2012 23:56
Last Modified:09 Nov 2021 17:04

Repository Staff Only: item control page