Fault-tolerant de Bruijn and shuffle-exchange networks
- 1 May 1994
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 5 (5) , 548-553
- https://doi.org/10.1109/71.282566
Abstract
This paper addresses the problem of creating a fault-tolerant interconnection network fora parallel computer. Three topologies, namely, the base-2 de Bruijn graph, the base-m deBruijn graph, and the shuffle-exchange, are studied. For each topology an N+k nodefault-tolerant graph is defined. These fault-tolerant graphs have the property that givenany set of k node faults, the remaining N nodes contain the desired topology as asubgraph. All of the constructions given are the best known in terms of the degree of thefault-tolerant graph. We also investigate the use of buses to reduce the degrees of thefault-tolerant graphs still further.Keywords
This publication has 12 references indexed in Scilit:
- Some practical issues in the design of fault-tolerant multiprocessorsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Fault-tolerant meshes with minimal numbers of sparesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- THE CUBE-CONNECTED CYCLES NETWORK IS A SUBGRAPH OF THE BUTTERFLY NETWORKParallel Processing Letters, 1992
- Designing fault-tolerant systems using automorphismsJournal of Parallel and Distributed Computing, 1991
- Reconfigurable cube-connected cycles architecturesJournal of Parallel and Distributed Computing, 1990
- On designing and reconfiguring k-fault-tolerant tree architecturesIEEE Transactions on Computers, 1990
- The de Bruijn multiprocessor network: a versatile parallel processing and sorting network for VLSIIEEE Transactions on Computers, 1989
- Fault-Tolerant Routing in DeBruijn Comrnunication NetworksIEEE Transactions on Computers, 1985
- The cube-connected cycles: a versatile network for parallel computationCommunications of the ACM, 1981
- Parallel Processing with the Perfect ShuffleIEEE Transactions on Computers, 1971