A Caltech Library Service

On Optimal Placements of Processors in Tori Networks

Blaum, Mario and Bruck, Jehoshua and Pifarre, Gustavo ED. and Sanz, Jorge L. C. (1996) On Optimal Placements of Processors in Tori Networks. California Institute of Technology . (Unpublished)

PDF (Adobe PDF (1.4MB))
See Usage Policy.

See Usage Policy.


Use this Persistent URL to link to this item:


Two and three dimensional k-tori are among the most used topologies in the design 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 addition, the performance of those networks is sensitive to link faults. In contrast, multistage networks (that are partially populated) scale well with the network size. We propose to add slackness in fully-populated tori by reducing the number of processors and we study optimal fault-tolerant routing strategies for the resulting interconnections. The key concept that we study is the average link load in an interconnection network with a given placement and a routing algorithm, where a placement is the subset of the nodes in the interconnection network that are attached to processors. Reducing the load on the links by the choice of a placement and a routing algorithm leads to improvements in both the performance and the fault tolerance of the communication system. Our main contribution is the construction of optimal placements for 2 and 3-dimensional k-tori networks and their corresponding routing algorithms. Those placements yield a linear (in the number of processors) link load and are of optimal size.

Item Type:Report or Paper (Technical Report)
Related URLs:
URLURL TypeDescription
Bruck, Jehoshua0000-0001-8474-0812
Group:Parallel and Distributed Systems Group
Record Number:CaltechPARADISE:1996.ETR012
Persistent URL:
Usage Policy:You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.
ID Code:26062
Deposited By: Imported from CaltechPARADISE
Deposited On:04 Sep 2002
Last Modified:22 Nov 2019 09:58

Repository Staff Only: item control page