Generalized theory for deadlock-free adaptive wormhole routing and its application to Disha Concurrent

Author

Anjan, K.V. ; Pinkston, Timothy Mark ; Duato, Jose

Author_Institution

Pyramid Technol. Corp., San Jose, CA, USA

fYear

1996

fDate

15-19 Apr 1996

Firstpage

815

Lastpage

821

Abstract

This paper generalizes a theory for deadlock-free adaptive wormhole routing by considering a mixed set of resources: edge and central buffers. This generalized theory is then applied to a concurrent version of Disha deadlock-recovery which relaxes the sequential recovery requirement for simultaneous recovery from deadlocks. The proposed extension to Disha does not necessitate any additional resource cost; rather it serves to eliminate the requirement of mutual exclusive access to the deadlock-free lane implemented by a Token. With this extension, Disha Concurrent remains applicable to any topology with a Hamiltonian path including k-ary n-cube networks and is also applicable to tree-based networks

Keywords

concurrency control; fault tolerant computing; multiprocessor interconnection networks; network routing; parallel architectures; performance evaluation; system recovery; Disha Concurrent; Hamiltonian path; Token; central buffers; deadlock recovery; deadlock-free adaptive wormhole routing; deadlock-free lane; edge; k-ary n-cube networks; multiprocessor interconnection networks; mutual exclusive access; resource cost; sequential recovery; tree-based networks; Clocks; Communication switching; Costs; Fasteners; Multiprocessor interconnection networks; Network topology; Packet switching; Routing; System recovery; Visualization;

fLanguage

English

Publisher

ieee

Conference_Titel

Parallel Processing Symposium, 1996., Proceedings of IPPS '96, The 10th International

Conference_Location

Honolulu, HI

Print_ISBN

0-8186-7255-2

Type

conf

DOI

10.1109/IPPS.1996.508153

Filename

508153