Paper Info
Title
Routing in Modular Fault-Tolerant Multiprocessor Systems
Abstract
In this paper, we consider a class of modular multiprocessor architectures in which spares are added to each module to cover for faulty nodes within that module, thus forming a fault-tolerant basic block (FTBB). In contrast to reconfiguration techniques that preserve the physical adjacency between active nodes in the system, our goal is to preserve the logical adjacency between active nodes by means of a routing algorithm which delivers messages successfully to their destinations. We introduce two-phase routing strategies that route messages first to their destination FTBB, and then to the destination nodes within the destination FTBB. Such a strategy may be applied to a variety of architectures including binary hypercubes and three-dimensional tori. In the presence of f faults in hypercubes and tori, we show that the worst case length of the message route is min {驴+f, (K+ 1)驴}+c where 驴 is the shortest path in the absence of faults, K is the number of spare nodes in an FTBB, and c is a small constant. The average routing overhead is much lower than the worst case overhead.
Year
DOI
Venue
1992
10.1109/71.476192
Parallel and Distributed Systems, IEEE Transactions
Keywords
DocType
Volume
logical adjacency,average routing overhead,message route,active node,binary hypercubes,destination node,physical adjacency,modular fault-tolerant multiprocessor systems,two-phase routing strategy,routing algorithm,destination ftbb,computer architecture,fault tolerance,routing,topology,network routing,fault tolerant,degradation,three dimensional,hypercubes,tori,real time systems,shortest path
Conference
6
Issue
ISSN
Citations 
11
1045-9219
7
PageRank 
References 
Authors
0.60
18
2
Name
Order
Citations
PageRank
M. Sultan Alam1131.48
Rami G. Melhem252834.60