Survey and Comparison of Fault-Tolerant Multistage Interconnection Networks

摘要

The means for communication among processors, memory modules, and other devices of a parallel computer is the interconnection network. Conventional von Neumann computers have relatively few subsystems to connect, yet a simple communication scheme such as a time-shared bus is an important system component. Large-scale multiprocessor computers have numerous communicating components, and therefore place great performance demands on an interconnection network. Many interconnection networks for large-scale multiprocessor computer systems have been proposed. Of these, multistage interconnection networks (MINs) compose a large subset, are well suited to communication among tightly coupled system components, and offer a good balance between cost and performance. For complex systems, assuring high reliability is a significant task. Thus, a crucial quality for MINs serving the communication needs of large-scale multiprocessor systems is fault-tolerance. This article focuses on MINs that are intrinsically fault tolerant. Many have been proposed, and new ideas are published frequently. The survey herein, while not exhaustive due to space constraints, attempts to portray the diversity of fault-tolerant MINs and, through them the scope of fault-tolerance techniques.