Adaptive and fault-tolerant routing with 100% node utilization for mesh multicomputer

Author

Wang, Sheng-De ; Tsai, Ming-Jer

Author_Institution

Dept. of Electr. Eng., Nat. Taiwan Univ., Taipei, Taiwan

fYear

1998

fDate

14-16 Dec 1998

Firstpage

367

Lastpage

374

Abstract

We propose an adaptive and deadlock-free routing algorithm to tolerate irregular faulty patterns using two virtual channels per physical link. It can improve the node utilization up to 100%. When a node becomes faulty or recovered, the central control unit constructs a directed path graph which is used for generating the intermediate nodes of the message path. Thus a message can be transmitted from sources or to destinations within faulty blocks via a set of “intermediate nodes”. Our method requires the global failure information if the central control unit is not available

Keywords

directed graphs; fault tolerant computing; message passing; parallel machines; central control unit; deadlock-free routing algorithm; directed path graph; fault tolerant routing; faulty blocks; global failure information; intermediate nodes; irregular faulty patterns; mesh multicomputer; message path; node utilization; virtual channels; Communication switching; Concurrent computing; Fault tolerance; Glass; Heuristic algorithms; Large-scale systems; Multiprocessor interconnection networks; Read only memory; Routing; System recovery;

fLanguage

English

Publisher

ieee

Conference_Titel

Parallel and Distributed Systems, 1998. Proceedings. 1998 International Conference on

Conference_Location

Tainan

ISSN

1521-9097

Print_ISBN

0-8186-8603-0

Type

conf

DOI

10.1109/ICPADS.1998.741099

Filename

741099