Browse Prior Art Database

Efficient Fault Tolerant Mesh and Hypercube Architectures

IP.com Disclosure Number: IPCOM000108522D
Original Publication Date: 1992-Jun-01
Included in the Prior Art Database: 2005-Mar-22
Document File: 2 page(s) / 75K

Publishing Venue

IBM

Related People

Bruck, J: AUTHOR [+3]

Abstract

Defined below are techniques and implementation issues related to the fault-tolerant meshes described in (*). 1. Efficient layouts for one-fault-tolerant two- and three- dimensional meshes. (See Fig. 1 for the two-dimensional case.)

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 86% of the total text.

Efficient Fault Tolerant Mesh and Hypercube Architectures

       Defined below  are techniques and implementation issues
related to the fault-tolerant meshes described in (*).
     1.    Efficient layouts for one-fault-tolerant two- and three-
dimensional meshes.  (See Fig. 1 for the two-dimensional case.)

      The layout is based on an interleaved ordering technique
applied to each dimension of the meshes.  For the 2-dimensional
1-fault-tolerant mesh, it can be laid out with wires of length at
most 3 (in terms of Manhattan distance). For the 3-dimensional
1-fault-tolerant mesh, it can be laid out with wires of length at
most 4.
     2.  Implementations, which use buses to reduce the degree, of
the fault-tolerant d-dimensional meshes.  (See Fig. 2 as an example.)

      Specifically, to tolerate k faults, the degree of the
fault-tolerant d-dimensional mesh can be reduced from (k+1)d to
d(k+3)/2 when k is odd, and reduced from (k+2)d to d(k+4)/2 when k is
even.
     3.  Apply the techniques of fault-tolerant meshes to hypercube
architectures.

      Specifically,  to tolerate k faults, our fault-tolerant
hypercube, which uses only k spare nodes, has degree (k+1)d - k  + 1
when k is odd and degree (k+2)d-k-1 when k is even.
     4.  Implementation, which uses multiplexers to reduce the
degree, of the fault-tolerant hypercubes.

      For instance, a one-fault-tolerant hypercube defined in (3) has
degree 2d.  Using multiplexe...