Fault-tolerant routing in MIN-based supercomputers

Author

Chalasani, Suresh ; Raghavendra, C.S. ; Varma, Anujan

Author_Institution

Dept. of Electr. Eng-Syst., Univ. of Southern California, Los Angeles, CA, USA

fYear

1990

fDate

12-16 Nov 1990

Firstpage

244

Lastpage

253

Abstract

The authors study methods for routing data in supercomputers that use multistage interconnection networks (MINs) in the presence of faulty components in the network. These methods are applicable to existing multiprocessors such as the IBM GF11 and RP3. These methods are based on the concept of dynamic full-access (DFA) which refers to the ability of the network to route data from any processor in the system to any other processor in a finite number of passes through the network. The authors introduce a graph-model called the DFA graph of a MIN and show how it can be used to determine the DFA capability of the MIN under a given set of network faults. When the faults in the network satisfy certain special properties, algorithms for routing any arbitrary permutation in a faulty Benes network and any Omega permutation in a faulty Omega network are presented

Keywords

fault tolerant computing; graph theory; multiprocessor interconnection networks; parallel architectures; DFA graph; IBM GF11; MIN-based supercomputers; Omega permutation; RP3; dynamic full-access; fault tolerant routing; faulty Benes network; faulty Omega network; faulty components; multistage interconnection networks; network faults; Computer networks; Contracts; Degradation; Doped fiber amplifiers; Fault tolerance; Multiprocessor interconnection networks; Quantum computing; Routing; Supercomputers; Switches;

fLanguage

English

Publisher

ieee

Conference_Titel

Supercomputing '90., Proceedings of

Conference_Location

New York, NY

Print_ISBN

0-8186-2056-0

Type

conf

DOI

10.1109/SUPERC.1990.130027

Filename

130027