The Flexible Hypercube: A New Fault-Tolerant Architecture for Parallel Computing
✍ Scribed by Tom Hameenanttila; Xin-Li Guan; Jo Dale Carothers; Jian-Xin Chen
- Publisher
- Elsevier Science
- Year
- 1996
- Tongue
- English
- Weight
- 265 KB
- Volume
- 37
- Category
- Article
- ISSN
- 0743-7315
No coin nor oath required. For personal study only.
✦ Synopsis
This paper presents the new Flexible Hypercube architecture. The Flexible Hypercube is a fault-tolerant network topology that can be constructed for an arbitrary number of nodes and is incrementally expandable. This topology maintains the strong features of the Hypercube while overcoming deficiencies in expandability. It is shown to have strong node connectivity, a small diameter, and to be tolerant of faults. The Flexible Hypercube is a suitable architecture for the design of both tightly coupled parallel systems and distributed systems. Efficient fault-free and fault-tolerant algorithms for message routing and broadcasting are presented for the architecture. The fault-free algorithm guarantees successful routing in O(log N) time, where N is the number of nodes in the system, and the fault-tolerant algorithm guarantees routing to functioning nodes if a route exists. The fault-free and fault-tolerant broadcasting algorithms have time complexity O(log N), and the fault-tolerant algorithm guarantees success if no two faulty nodes are adjacent and no functioning node is adjacent to two faults.