Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Fault Tolerant de Bruijn and Shuffle Exchange Networks

IP.com Disclosure Number: IPCOM000122299D
Original Publication Date: 1991-Nov-01
Included in the Prior Art Database: 2005-Apr-04
Document File: 1 page(s) / 30K

Publishing Venue

IBM

Related People

Bruck, J: AUTHOR [+3]

Abstract

Disclosed is a technique for adding fault tolerance to de Bruijn and shuffle-exchange networks by adding spare nodes and extra edges.

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

Fault Tolerant de Bruijn and Shuffle Exchange Networks

      Disclosed is a technique for adding fault tolerance to de
Bruijn and shuffle-exchange networks by adding spare nodes and extra
edges.

      The problem of creating fault-tolerant interconnection networks
for parallel computers is addressed.  Three topologies, namely the
base-2 de Bruijn graph, the base-m de Bruijn graph, and the
shuffle-exchange are studied.  For each topology, an N+k node
fault-tolerant graph is defined. These fault-tolerant graphs have the
property that, given any set of k node faults, the remaining N nodes
contain the desired topology as a subgraph.

      The constructions are based on ordering the N nodes in the
target graph and adding extra edges by shifting each node to each of
the k following nodes.

      All of the constructions given here are the best known in terms
of the degree of the fault-tolerant graph.

      Disclosed anonymously.