Published Articles >> Table of Contents >> Abstract

3rd Euromicro Workshop on Parallel and Distributed Processing   p. 288
An adaptive deadlock and livelock free routing algorithm
M. Coli, Dipartimento di Ingegneria Elettronica, Univ. La Sapienza, Via Eudossian, Italy
P. Palazzari, Dipartimento di Ingegneria Elettronica, Univ. La Sapienza, Via Eudossian, Italy

Full Article Text:

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/EMPDP.1995.389126
Send link to a friend

Abstract
The paper is concerned with store and forward deadlocks (DL) arising in interprocessor network systems with buffered packet switched communications. Algorithms which implement DL free routing use adaptive or nonadaptive routing modality. Nonadaptive algorithms underuse the interconnection network bandwidth because they impose restrictions to the routing paths; adaptive algorithms are DL free only if certain hypotheses on the communication topology occur. In order to override these drawbacks, we have implemented an adaptive DL free routing which fully exploits the connectivity of the network and which is unrelated to its topology. DL is avoided by adopting a recovery policy. Whenever DL arises, our algorithm is able to remove it within a finite time. We demonstrate 'deadlock' and 'livelock' avoidance by ensuring the presence of a hole in the network buffers; the hole is subjected to casual movement. Performance tests, executed on a transputer based parallel machine, show the effectiveness of the algorithm and demonstrate its fault tolerance capabilities.
Back to Top Additional Information
Index Terms- packet switching; multiprocessor interconnection networks; fault tolerant computing; adaptive systems; livelock free routing algorithm; store and forward deadlocks; interprocessor network systems; buffered packet switched communications; DL free routing; nonadaptive routing modality; interconnection network bandwidth; communication topology; adaptive DL free routing; deadlock free routing; network buffers; casual movement; performance tests; transputer based parallel machine; fault tolerance capabilities Citation:  M. Coli, P. Palazzari, "An adaptive deadlock and livelock free routing algorithm," pdp, p. 288,  3rd Euromicro Workshop on Parallel and Distributed Processing,  1995